文献

J-GLOBAL ID：201802245747341053   整理番号：18A2207134

下位次元空間における総和可能下界を用いたLloyd型k-meansクラスタリングアルゴリズムの加速

Accelerating a Lloyd-Type k-Means Clustering Algorithm with Summable Lower Bounds in a Lower-Dimensional Space

著者 (3件)： AOYAMA Kazuo (NTT Communication Science Laboratories) ,  SAITO Kazumi (Kanagawa University) ,  IKEDA Tetsuo (University of Shizuoka)
資料名： IEICE Transactions on Information and Systems (Web)  (IEICE Transactions on Information and Systems (Web))
巻： E101.D  号： 11  ページ： 2773-2783(J-STAGE)  発行年： 2018年 
JST資料番号： U0469A  ISSN： 1745-1361  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 本論文は,潜在的に多数のクラスを有する大規模で高次元のデータセットに適したLloyd型k-meansクラスタリングのための効率的な加速アルゴリズムを提示した。このアルゴリズムは,不必要な距離計算を避けるために,新しい射影型フィルタ(PRJ)を採用し,標準のLloydアルゴリズムと同じ結果を有したまま高速性をもたらした。PRJは,データ点が射影される下位次元空間で定義した二乗距離に関する総和可能下限を利用した。他の加速アルゴリズムで使用されている既存の下限は固定フィルタとして一度だけしか作用しないが,総和可能下限は反復計算毎に下位次元空間における要素の増加を加算することにより下限を動的にタイトにすることができた。大規模で高次元の実画像データセットに関する実験結果は,提案したアルゴリズムが,最先端のアルゴリズムと比較して,大きなk値が与えられと,高速かつ少ないメモリ消費で動作することを実証した。(翻訳著者抄録)

シソーラス用語： 限界 ,  次元 ,  射影 ,  *高速アルゴリズム ,  主成分分析 ,  数学的変換 ,  クラスタ化 ,  *クラスタ分析 ,  *平均法
準シソーラス用語： *K-meansクラスタリングアルゴリズム ,  下界 ,  画像クラスタリング ,  固有値分解 ,  低次元

著者キーワード (8件)： アルゴリズム ,  クラスタリング ,  K平均 ,  下界 ,  特異値分解 ,  主成分分析 ,  次元縮小 ,  性能

分類 (2件)： その他の計算機利用技術  (JE14000C) ,  計算理論  (JB02000A)

引用文献 (35件)：

• [1] M. Mahajan, P. Nimbhorkar, and K. Varadarajan, “The planar k-means problem is NP-hard,” Theoretical Computer Science, vol.442, pp.13-21, 2012.
• [2] D. Aloise, A. Deshpande, P. Hansen, and P. Popat, “NP-hardness of Euclidean sum-of-squares clustering,” Machine Learning, vol.75, no.2, pp.245-248, 2009. 10.1007/s10994-009-5103-0
• [3] O. du Merle, P. Hansen, B. Jaumard, and N. Mladenovic, “An interior point algorithm for minimum sum-of-squares clustering,” SIAM J. Sci. Comput., vol.21, no.4, pp.1485-1505, 2000. 10.1137/s1064827597328327
• [4] B. Babaki, T. Guns, and S. Nijssen, “Constrained clustering using column generation,” Proc. 11th Int. Conf. Integration of AI and OR Techniques in Constraint Programming (CPAIOR), ed. H. Simonis, Lecture Notes in Computer Science, vol.8451, pp.438-454, Springer, Cham, 2014. 10.1007/978-3-319-07046-9_31
• [5] A. Kumar, Y. Sabharwal, and S. Sen, “Linear-time approximation schemes for clustering problems in any dimensions,” J. ACM, vol.57, no.2, article 5, 2010. 10.1145/1667053.1667054

タイトルに関連する用語 (5件)： 次元 ,  総和 ,  下界 ,  K-meansクラスタリングアルゴリズム ,  加速