大規模・複雑データに対するクラスタリング法の開発とその理論的性質の解明

点击翻译按钮获取中文摘要

本年度は, 大規模クラスタリングの近似法に関する研究（研究1）と大規模データにも適用可能なconvex clustering algorithmの開発（研究2）を行った.（研究1）研究1では, 先行研究の母集団レベルでのズレの問題点を解決した新たなスペクトルクラスタリングの近似アルゴリズムを開発した. また, このアルゴリズムは, 本研究でこれまでに提案した密度推定を必要とする方法と異なり, 高次元データに対しても適用可能な汎用的な近似法となっている.（研究2）Convex clusteringはk-means法とは異なり局所解の問題が無く, 適切な重みを与えることで柔軟なクラスタ構造を捉えることができる. 一方で, 既存の最適化アルゴリズムは計算コストが高く, 大規模なデータに対しては適用することができなかった. 研究2では, この問題を解決するため, サンプルサイズが100万を超える大規模データに対しても適用可能なconvex clusteringのアルゴリズムを開発した. 具体的には, 一般の重みを伴ったL2 convex clusteringに対して, Majorization-Minimizationに基づく効率の良いalgorithm (CCMM) を提案した. さらに, L1 convex clusteringに対しては, 重みが木構造をもつときに効率良く最適化できることに注目し, 重みが木構造をもつ場合に限定されるが, 大規模データに適用可能な非常に効率的なアルゴリズム (TGCC) を提案した. この方法を用いれば, 100万点のデータに対して, １分ほどでcluster pathと呼ばれる解の軌道と階層的クラスタ構造を得ることができる. CCMMに関しては論文化し, 投稿を行った.