Affinity Propagation を書いてみた

[追記] damping の値をあまり良くない値に設定してしまっていたらしいので、修正。→ http://d.hatena.ne.jp/nojima718/20101029/1288377507

Affinity Propagation を書いてみた．

おそらく自分でクラスタリングをするときは疎な空間でクラスタリングをすることになると思うので，疎な類似度に対して効率的にクラスタリングを行えるように，隣接リスト表現を使って Affinity Propagation を実装した．

計算量は，データ点の数をN，反復回数をTとして，グラフが密な場合は O(TN^2)，疎な場合は O(TN)．

(2010/10/30 修正
 バグを見つけたのでコードは削除。
 http://d.hatena.ne.jp/nojima718/20101029/1288377507 の方を見てください)

おなじみの Old faithful に対して 類似度=二乗誤差の-1倍 として適用してみた結果：

preference を類似度の最小値にした場合．3つのクラスタに分かれた．

preference を類似度の最小値の1.2倍にした場合．2つのクラスタに分かれた．一番それっぽい．

preference を類似度の中央値にした場合．12個のクラスタに分かれた．