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

大规模复杂数据聚类方法的发展及其理论特性的阐明

• 批准号: 20K19756
• 负责人: 寺田 吉壱
• 金额: $ 1.91万
• 依托单位: Osaka University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Early-Career Scientists
• 财政年份: 2020
• 资助国家: 日本
• 起止时间: 2020-04-01 至 2024-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-20K19756/
• 关键词: 教師なし学習; 大規模データ; クラスタリング; 計算量削減; 漸近理論; 動的計画法

本年度は, 大規模クラスタリングの近似法に関する研究（研究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に関しては論文化し, 投稿を行った.

This year, we conducted research on approximation methods for large-scale clustering (Study 1) and development of feasible clustering algorithms for large-scale clustering (Study 2). (Study 1) Study 1, the parent group of the first study to solve the problem point, the new selection of the sample to approximate the problem point to develop. In this study, we propose a new method for density estimation, which is based on the approximate method that may be widely used in high dimensional density estimation. (Study 2) Convex clustering k-means method On the one hand, the existing optimization algorithm is not suitable for calculation, but for large-scale optimization. Study 2: To solve this problem, we need to develop a solution to the problem. Specifically, the L2 convex clustering algorithm (CCMM) is proposed for Majorization-Minimization. In addition, L1 convex clustering is suitable for the optimization of wood structures with high efficiency, especially for limited applications, and for large-scale applications with high efficiency (TGCC). This method is used in the middle, 1 million points of the data is related to the problem, 1 minute to the cluster path, call to the solution of the orbital hierarchy of the structure is obtained. CCMM is concerned about culture, contribution and behavior.

项目成果

クラスタリングにおける汎用的な計算コスト削減法について

关于聚类中通用计算成本降低方法

• 发表时间: 2021
• 作者: 寺田吉壱;山本倫生
• 通讯作者: 山本倫生

Classification from only positive and unlabeled functional data

仅根据阳性和未标记的功能数据进行分类

• DOI: 10.1214/20-aoas1404
• 发表时间: 2020
• 期刊: The Annals of Applied Statistics
• 作者: Terada Yoshikazu;Ogasawara Issei;Nakata Ken
• 通讯作者: Nakata Ken

大規模なクラスタリングにおける計算量削減法について

关于大规模聚类中计算复杂度降低方法

• 发表时间: 2020
• 作者: 寺田吉壱;山本 倫生
• 通讯作者: 山本 倫生

ベクトル量子化による大規模クラスタリングの近似法とその性質

大规模聚类矢量量化逼近方法及其性质

• 发表时间: 2022
• 作者: Takehiro Ito;Yuni Iwamasa;Yasuaki Kobayashi;Yu Nakahata;Yota Otachi;Kunihiro Wasa;寺田吉壱，山本倫生．
• 通讯作者: 寺田吉壱，山本倫生．

代表点を用いた大規模クラスタリングの近似法とその性質

大规模聚类的代表点逼近方法及其性质

• 发表时间: 2022
• 作者: 寺田吉壱;山本倫生
• 通讯作者: 山本倫生