Affinity Propagation(AP)とは

あらかじめクラスタ数を決めることなくクラスタリングできる方法。

Affinity Propagationの概要

オブジェクトのペア(i, j)について以下の2つのメッセージを計算する。

responsibility $r_{i,j}$
availability $a_{i,j}$

収束するか、資源が尽きるまで、イテレーションごとに
$r_{i,j}$と$a_{i,j}$は更新される。

収束したら、オブジェクトiのexempler:$c_{i}$は、
$$c_{i} = arg\max_{j}\left( a_{i,j} + r{i,j} \right)$$
で得られる。

responsibility

オブジェクトiがオブジェクトjをどれくらいexamplerとしたいか、という指標。
以下のように計算される。
$$ r_{i,j} = \boldsymbol{L_{i,j}} \left( \sum_{k:k \neq j}{a_{i,k}\boldsymbol{L_{i,k}}} \right)^{-1}$$

ここで、$\boldsymbol{L}$は尤度行列。つまり$\boldsymbol{L_{i,j}}$はオブジェクトi,j間の類似度を表す。$\boldsymbol{L_{i,j}}$が大きくなると、i,jは似ている、ということになる。$\boldsymbol{L}$の対角成分は自分で決定する。対角成分の大小はクラスタ数の大小に影響を与える。経験的には、$\boldsymbol{L}$の非対角成分の平均値か中央値にすると良いらしい。

availability

オブジェクトjが、どれくらいオブジェクトiのexamplerでいたいか、という指標。
初期値は1にセットされ、以下のように計算される。

$$ a_{j,j} = -1 + \prod_{k:k \neq j}{(1+r_{k,j})} $$
$$ a_{i,j} = [ {1 + (\frac{1}{r_{i,i}} - 1) \prod_{k:k \neq i, k \neq j}{(1+r_{k,j})^{-1}}}]^{-1} $$

参考文献

[Alejando et al.] [Clustering-Based Anomaly Detection in Multi-View Data] (http://www.kecl.ntt.co.jp/people/kimura.akisato/pdf/cikm2013.pdf)