K-Multiple-Meansの高速化アルゴリズム
[Japanese|English]
どんな研究？
多次元データに対するクラスタリング手法としてK-Meansが有名ですが、K-Meansはデータを最も近い代表点に割り当てるため複雑な形のクラスタを抽出することが困難であるという課題があります。この課題を解決するためにK-Multiple-Meansが提案されました。K-Multiple-Meansは複数のサブクラスタをグループ化することで複雑な形のクラスタを効果的に抽出することができます。しかしK-Multiple-Meansはクラスタリングを行う計算コストが大きいという問題がありました。考案した技術は大規模なデータに対してK-Multiple-Meansによるクラスタリングを高速に行うことができます。
どこがすごい？
K-Multiple-Meansのサブクラスタのグループ化は代表点-データポイントの距離を繰り返し計算し、二部グラフを分割することで行います。しかし二部グラフを分割するためにそれを表す行列の特異値分解を計算するため計算コストが高くなります。提案手法は代表点間のグラフの連結成分を用いて代表点間の小さなブロック行列を求め、小さなブロック行列から特異値分解を高速に求めることでクラスタリングを高速に行います。
実験結果
本技術はオリジナルのK-Multiple-Meansより最大230倍以上高速にクラスタリングを実行可能です。例えばオリジナルの手法ではクラスタリングに10日以上が必要だったデータに対して、提案手法は1時間程度でクラスタリングを行うことができます。
めざす未来
本技術はクラスタリング結果を犠牲にすることなくK-Multiple-Meansを高速化することを可能にします。 K-Multiple-Meansはブラインド信号源分離、画像セグメンテーション、ネットワークの負荷分散などの様々なアプリケーションで利用されていて、本成果はこれらのアプリケーションを大規模のデータに対しても実行可能にするブレークスルーとなることが期待されます。
関連文献
- Fujiwara, Kumagai, Ida, Nakano, Nakatsuji, Kimura, “Efficient Algorithm for K-Multiple-Means”, Proc. ACM Manag. Data 2(1) (2024).
https://dl.acm.org/doi/pdf/10.1145/3639273
連絡先
藤原 靖宏 (Yasuhiro Fujiwara)
コミュニケーション科学基礎研究所 メディア情報研究部 メディア認識研究グループ