Affinity Propagationのための高速化アルゴリズム

摘要

Affinity PropagationはFreyらによつて近年提案されたクラスタリング手法である.Affinity Propagationはk-means法などに代表される既存のクラスタリング手法よりクラスタリング精度が良いため，様々な分野において用いられている.オリジナルのAffinity Propagationでは全てのデータポイント間でメッセージと呼ばれる値を繰返し収束するまで計算する.しかしこのオリジナルの手法はデータポイントの数の2乗の計算コストを要するため，データポイントの数が多い場合は非常に計算時間がかかるという問題点がある.本論文では収束後においてオリジナルのAffinity Propagationとクラスタリング結果が同じになることを保証する高速化手法を提案する.提案手法は（1)収束値を計算するのに不必要なデータペアを枝刈りするアイデアと，(2)枝刈りされたデータペアの収束値を枝刈りされなかったデータペアの収束値から計算するアイデアから構成される.実データを用いて比較実験を行い，提案手法はオリジナルの手法より高速にクラスタリングを行えることを確認した.