Affinity Propagation によるクラスタリング - nojimaの日記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,
