親和性の伝播

統計学とデータマイニングにおいて、アフィニティ伝播（AP）は、データポイント間の「メッセージパッシング」の概念に基づくクラスタリングアルゴリズムです。 ^[1] $k$ 平均法や $k$ メドイドなどのクラスタリングアルゴリズムとは異なり、アフィニティ伝播では、アルゴリズムを実行する前にクラスターの数を決定または推定する必要はありません。kメドイドと同様に $、$ アフィニティ伝播は、クラスターを代表する入力セットのメンバーである「サンプル」を見つけます。^[1]

アルゴリズム

$x 1$ から $x n$ をデータポイントの集合とし、その内部構造については仮定を置かないものとする。また、s $を$ 任意の 2 点間の類似性を定量化する関数とし、 $x$ $i$ $がx$ $j$ よりも $x$ $k$ に類似している場合に限り、 $s (i, j) > s (i, k)となるものとする。この例では、2 つのデータポイントの負の二乗距離、すなわち点$ $x$ $i$ と $x$ $k$ について、が使用されている。^[1] $s(i,k)=-\left\|x_{i}-x_{k}\right\|^{2}$

$s$ の対角線(つまり) は、インスタンスの優先度、つまり特定のインスタンスが模範になる可能性を表すため、特に重要です。すべての入力に対して同じ値に設定されている場合、アルゴリズムが生成するクラスの数が制御されます。最小類似度に近い値では生成されるクラスが少なくなり、最大類似度に近いかそれより大きい値では生成されるクラスが多くなります。通常、すべての入力ペアの類似度の中央値に初期化されます。 $s(i,i)$

このアルゴリズムは、2つのメッセージパッシングステップを交互に実行することで進行し、2つの行列を更新します。^[1]

「責任」マトリックス $R に$ $は、 x$ $i$ の他の候補模範と比較して、 $x$ $k$ $がx$ $i$ の模範としてどの程度適しているかを定量化する値 $r (i, k)$ があります。
「可用性」行列 $A$ $には、他の点が$ $x k を$ $模範$ として好むかどうかを考慮して、 $x$ $i が$ $x$ $k を$ 模範として選択することが $どの程度$ $「適切$ $」$ であるかを表す値 $a ( i ,$ $k )$ が含まれます。

両方の行列はすべてゼロに初期化され、対数確率テーブルとして表示できます。次に、アルゴリズムは次の更新を繰り返し実行します。

まず、責任の更新が送信されます。 $r(i,k)\gets s(i,k)-\max _{k'\neq k}{\left\{a(i,k')+s(i,k')\right\}}$
その後、空き状況は更新され、 $a(i,k)\gets \min {\left(0,r(k,k)+\sum _{i'\not \in \{i,k\}}\max(0,r(i',k))\right)}\quad {\text{ for }}i\neq k$ $a(k,k)\leftarrow \sum _{i'\neq k}\max(0,r(i',k)).$

反復は、クラスター境界が反復回数を超えて変化しないか、または事前に決定された反復回数に達するまで実行されます。最終的なマトリックスから、それ自身に対する「責任 + 可用性」が正であるもの (つまり) として標本が抽出されます。 $(r(i,i)+a(i,i))>0$

アプリケーション

アフィニティ伝播の発明者は、人間の顔の写真のクラスタリングや規制された転写産物の識別など、特定のコンピュータービジョンや計算生物学のタスクでは、 $k$ 平均法よりもアフィニティ伝播の方が優れていることを示しました。 ^[1] $k$ 平均法では、多くのランダム再起動が許可され、PCAを使用して初期化された場合でも同様です。^{[2]タンパク質相互作用グラフの分割に関してアフィニティ伝播と}マルコフクラスタリングを比較した研究では、マルコフクラスタリングの方がその問題に適していることがわかりました。^[3]テキストマイニングアプリケーション向けに、半教師ありのバリアントが提案されています。^[4]最近の別のアプリケーションは経済学で、アフィニティ伝播を使用して、1997年から2017年までの米国経済の産出乗数のいくつかの時間的パターンを見つけました。^[5]

ソフトウェア

ELKIデータマイニングフレームワークにはJava実装が含まれています。
アフィニティ伝播のJulia実装は、Julia Statistics の Clustering.jl パッケージに含まれています。
Pythonバージョンはscikit-learnライブラリの一部です。
R実装は「apcluster」パッケージで利用可能です。

参考文献

^ abcde Brendan J. Frey; Delbert Dueck (2007). 「データポイント間でメッセージを渡すことによるクラスタリング」. Science . 315 (5814): 972–976. Bibcode :2007Sci...315..972F. CiteSeerX 10.1.1.121.3145 . doi :10.1126/science.1136800. PMID 17218491. S2CID 6502291.
^ Delbert Dueck、Brendan J. Frey (2007)。教師なし画像分類のための非計量類似性伝播。コンピュータビジョンに関する国際会議。doi : 10.1109/ICCV.2007.4408853。
^ James Vlasblom 、 Shoshana Wodak (2009)。 「タンパク質相互作用グラフの分割におけるマルコフクラスタリングとアフィニティ伝播の比較」。BMC Bioinformatics。10 ( 1): 99。doi : 10.1186 / 1471-2105-10-99。PMC 2682798。PMID 19331680。
^ Renchu Guan、Xiaohu Shi、Maurizio Marchese、Chen Yang、Yanchun Liang (2011)。「シードアフィニティ伝播によるテキストクラスタリング」。IEEE Transactions on Knowledge and Data Engineering。23 ( 4): 627–637。doi : 10.1109/tkde.2010.144。hdl : 11572/ 89884。S2CID 14053903 。
^ Almeida, Lucas Milanez de Lima; Balanco, Paulo Antonio de Freitas (2020-06-01). 「構造変化に関する研究における補完的手段としての多変量解析の応用：米国経済における乗数効果の例」.構造変化と経済ダイナミクス. 53 : 189–207. doi :10.1016/j.strueco.2020.02.006. ISSN 0954-349X. S2CID 216406772.

[science-1] Brendan J. Frey; Delbert Dueck (2007). 「データポイント間でメッセージを渡すことによるクラスタリング」. Science . 315 (5814): 972–976. Bibcode :2007Sci...315..972F. CiteSeerX 10.1.1.121.3145 . doi :10.1126/science.1136800. PMID 17218491. S2CID 6502291.

[2] Delbert Dueck、Brendan J. Frey (2007)。教師なし画像分類のための非計量類似性伝播。コンピュータビジョンに関する国際会議。doi : 10.1109/ICCV.2007.4408853。

[3] ^ James Vlasblom 、 Shoshana Wodak (2009)。 「タンパク質相互作用グラフの分割におけるマルコフクラスタリングとアフィニティ伝播の比較」。BMC Bioinformatics。10 ( 1): 99。doi : 10.1186 / 1471-2105-10-99。PMC 2682798。PMID 19331680。

[4] Renchu Guan、Xiaohu Shi、Maurizio Marchese、Chen Yang、Yanchun Liang (2011)。「シードアフィニティ伝播によるテキストクラスタリング」。IEEE Transactions on Knowledge and Data Engineering。23 ( 4): 627–637。doi : 10.1109/tkde.2010.144。hdl : 11572/ 89884。S2CID 14053903 。

[5] Almeida, Lucas Milanez de Lima; Balanco, Paulo Antonio de Freitas (2020-06-01). 「構造変化に関する研究における補完的手段としての多変量解析の応用：米国経済における乗数効果の例」.構造変化と経済ダイナミクス. 53 : 189–207. doi :10.1016/j.strueco.2020.02.006. ISSN 0954-349X. S2CID 216406772.