クラスタリング

http://www.math.psu.edu/petrunin/papers/alexandrov/bbi.pdf
距離空間には、
Euclid空間への埋め込みに対して、
内在的に定まる距離(intrinsic)と
埋め込みに依存する距離(extrinsic)がある。

有限距離空間のisometry類の集合上の距離として、
Gromov-Hausdorff距離が定義できる。
これはcorrespondenceに対応する点対の距離の差により算出される。

* point could dataの解析
point cloudは点の集まりであるが、それに付随して、
データに内在する距離(intrinsic metric)と
データの観測に伴う距離(extrinsic metric)
により、距離空間とユークリッド空間への埋め込みが与えられている、
とみることができる。

point cloud dataの例として、
複数の都市に存在する人間の位置をすべて記録したものを想像してみる。
高い密度で都市に集中し、それよりも少ない密度で都市間の交通網上に存在しているはずだ。
point cloud dataから都市を推定することがクラスタリングと呼ばれる技法であり、
交通網を捉えるための技法が、Persistent homologyになる。
つまり、対象の粗視化、という操作を取り入れて、トポロジーの計算手法を応用しよう、
というもの。


* クラスタリング

point cloud dataを解析するために、荒い分類を行う、
すなわち粗視化のスケールを変えながら連結成分に分ける、という操作を行う。

これを(階層化)クラスタリングと呼ぶわけだが、
Classifying Clustering Schemes
http://arxiv.org/abs/1011.5270
では、
まず、理想的なクラスタリングアルゴリズムは存在しない、というKleinbergの定理に言及して、
その定理の仮定を緩めて、ある性質を満たすクラスタリングアルゴリズムは唯一存在する、
という定理を示している。
(数学の応用としては、
最善のものは存在しない、という形で限界を示し、
限界から少し条件を緩めたものの存在を構成的に示す、
という形のフレームワークは非常に有効なもので、
シャノンによる通信の符号化
もその一例とみることができる。)

point cloudの分割は、point cloudを有限集合と見た時、
有限集合に対して位相開基を与えることと同等である。
いわゆる有限空間と呼ばれるものであるが、
この位相は、密着位相と離散位相の間で、半順序をなす。
クラスタリングは粗視化のスケールを変えて分割を変更するものであるから、
位相開基の減少フィルトレーションが必要である。
この半順序を取り出す位相開基の減少フィルトレーションを定めると、
それに対応して木構造、いわゆる、デンドログラムというものになる。
そこで、有限集合とその位相開基の右連続減少フィルトレーションの組で、
先頭が必ずしも離散位相ではないが最後は密着位相となるものを
persistent setと呼ぶ。
なお、point cloudが距離空間の構造を持っている時、距離から定まる位相は点を分離するので、
クラスタリングが定める位相はそれよりも弱い。

クラスタリングのアルゴリズムとは、
有限距離空間を対象、しかるべき条件を満たす距離空間の写像を射とする圏から
persitent setsの圏への関手、
として定義される。


入力の有限距離空間の射の条件として、
iso:isometry
inj:距離が非増大の単射
gen:距離が非増大
という３種類について考察されている。
よく知られているk-means法は、どの入力の圏に対しても
関手の意味でのクラスタリングアルゴリズムを与えない。
(ex. Persistent Clustering and a Theorem of J. Kleinberg 4.1
http://arxiv.org/abs/0808.2241)
クラスタリングのあるスケールによって定まる分割に対して、クラスタリングを行っても、
そのスケールでは分割が変化しないことが望ましい。
この冪等性の性質をexcisivenessと呼ぶ。
標準的なクラスタリング関手として、Vietoris-Rips関手がある。

これは、2点からなる距離空間によって表現されている、と見なすことができ、
その拡張として、有限距離空間の集合によって表現可能な関手が定義される。
(Def6.3)
上記論文では、(階層化でない)分割の場合にexcisiveクラスタリングアルゴリズムは表現可能と同値
であることを示している。(Th6.2)
Th7.2では、入力の圏がgenの場合に、クラスタリングアルゴリズムに、
Vietoris-Rips関手が対応することを示している。

* クラスタリングのstability
クラスタリングを行う元のpoint cloud dataは、
サンプリング結果として、確率的、不完全、という性質を持っている。
そのため、
クラスタリングアルゴリズムには、安定性が必要となるわけだが、
そのために、入力の圏の対象の距離を測る道具として、
Gromov-Hausdorff距離を使用することができる。
(Persistent Clustering and a Theorem of J. Kleinberg section 5)



* 形の把握
Gromov-Hausdorff Stable Signatures for Shapes using Persistence
http://math.stanford.edu/~memoli/papers/dgh-persistence.pdf

point cloudの形を把握するには、単純なホモロジーでは点の数しか出てこないので、
粗視化のスケールを変えて特徴を取り出す必要がある。
それがpersistencyということになる。
2つのpoint cloudの距離を測るのに、point cloudに内在的な距離および埋め込みによる距離を与えて、
距離空間間の距離、すなわちGromov-Hausdorff距離により、形の相違を測る。
この距離を下から評価するために、persistencyの結果が利用できる。
すなわち、filtered Rips complexを定義して、
それから得られるpersistent diagramを、point cloudに対して対応させる。
2つのpersistent diagramsをbottleneck distanceを使用して距離を測った結果が
Gromov-Hausdorff距離で抑えられる。
(Th3.1)

Spectral Gromov-Wasserstein Distances for Shape Matching
http://math.stanford.edu/~memoli/papers/dgw-spec-nordia-theo.pdf