[8D]クラスタリング・ルールマイニング

13:55 〜 14:20

[8D-02] k-means-3p: 要約情報による枝狩りを用いた k-means++法の高速化

*三谷 貴宏¹、Wu Xuanxin¹、藤原 靖宏²、鬼塚 真¹ (1. 大阪大学、2. 日本電信電話株式会社)

発表者区分：学生
論文種別：ロングペーパー
インタラクティブ発表：あり

キーワード：

クラスタリング、k-means、k-means++、高速化

クラスタリングはデータサイエンスにおいて重要な技術である．クラスタリングの代表的な手法であるk-means は精度および実行時間が初期点に依存するという課題があり，初期点の選択を改良する k-means++という手法によりクラスタリングの質の向上と高速化が実現されている．しかし，k-means++は初期点を選択するアルゴリズムの計算量が大きいという問題がある．この問題に対して，本論文では初期点の選択を正確性を保証しながら高速化する 3 つの新たなアルゴリズムを提案する．1 つ目の手法では，データをグループ化することで，データ点単位での探索をグループ単位での探索にすることで高速化する．2 つ目の手法では，三角不等式により距離計算を省略可能なデータのペアを特定して計算を省略する．3 つ目の手法では，データのペアの距離の下限値を計算し比較することで一部のデータのペアにおける正確な計算を省略する． 実験では，提案手法は初期点の決定での高い枝狩り率を達成し，従来手法と比較して高速なクラスタリングを可能にすることを示した．