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

藤原　靖宏  入江　豪  北原　友恵  

誌名
電子情報通信学会論文誌 D   Vol.J96-D    No.5    pp.1178-1187
発行日: 2013/05/01
Online ISSN: 1881-0225
DOI: 
Print ISSN: 1880-4535
論文種別: 特集論文 (データ工学と情報マネジメント論文特集)
専門分野: データマイニング
キーワード: 
クラスタリング,  Affinity Propagation,  高速化,  正確,  

本文: PDF(1.1MB)>>
論文を購入


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