最小費用流問題を活用したサイズ均等クラスタリングの高速化手法に関する一考察

カテゴリ: 部門大会

論文No: MC3-3

グループ名: 【C】2024年電気学会電子・情報・システム部門大会

発行日: 2024/08/28

タイトル(英語): A Study on the Acceleration of Size-Equalized Clustering Using the Minimum Cost Flow Problem

著者名: 岩﨑 明人（近畿大学）,濵砂 幸裕（近畿大学）

著者名(英語): Haruto Iwasaki (Kindai University),Yukihiro Hamasuna (Kindai University)

キーワード: クラスタリング|最小費用流|Clustering|Minimum cost flow problem

要約(日本語): 各クラスタに含まれるデータ個体数を制限した手法として、サイズコントロールクラスタリングがある。
サイズコントロールクラスタリングでは制約条件を満たしつつ、帰属度の値を整数計画問題を解くことによって求めるため、
クラスタの分割に要する実行時間は k-means と比較して、帰属度の更新に要する実行時間の差異によって増加すると考えられる。
帰属度の更新は、二部グラフの割り当て問題と考えることができ、最小費用流問題に変換することで解くことができる。
本研究では、サイズコントロール機能を持つクラスタリングの高速化を検討し、数値実験を通じた検証を行った。最小費用流問題の観点に基づく手法では、計算速度の大きな向上は見られなかった。