Affinity Propagation によるクラスタリング
Affinity Propagation というクラスタリングのアルゴリズムがあるらしいので調べてみた．
Affinity Propagation は，同じクラスタリングのアルゴリズムである k-means と比較すると次のようなメリットがある．
- 予めクラスタ数を決めておく必要がない．アルゴリズムが自動的にクラスタ数を決定する．
- 初期値依存性がない．k-means は，クラスタの中心点の初期値の選び方によって結果が変わる．
- 類似度 s(i,j) の制約が緩い．s(i,j) は，対称でなくてもいいし，三角不等式をみたしてなくてもよい．k-means は，可測であることを仮定している．
Affinity Propagation は，k-means と同じく，漸化式を反復計算していくアルゴリズムで，計算時間は，データ点の数をN，反復回数をTとして O(TN^2) となる．ただし，類似度 s(i,j) が疎である場合，すなわち s(i,j) > -∞ であるような s(i,j) が O(N) 個しかない場合は，O(TN) で計算できる．
アルゴリズムの内容については，日本語の解説を見つけたのでこっちを見ると良いかも．(最初は自分で書こうと思ってたけど既にあったので書く気がなくなった)
