Art

J-GLOBAL ID：201802245747341053   Reference number：18A2207134

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

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

Author (3)： AOYAMA Kazuo (NTT Communication Science Laboratories) ,  SAITO Kazumi (Kanagawa University) ,  IKEDA Tetsuo (University of Shizuoka)
Material： IEICE Transactions on Information and Systems (Web)  (IEICE Trans Inf Syst (Web))
Volume： E101.D  Issue： 11  Page： 2773-2783(J-STAGE)  Publication year： 2018 
JST Material Number： U0469A  ISSN： 1745-1361  Document type： Article
Article type： 原著論文  Country of issue： Japan (JPN)  Language： ENGLISH (EN)

Thesaurus term： limit ,  dimension ,  projection (mathematics) ,  *fast algorithm ,  Principal Component Analysis ,  mathematical transformation ,  clustering ,  *Cluster Analysis ,  *average method ,  lower bound ,  eigenvalue decomposition ,  low dimension ,  modification
Semi thesaurus term： *K-means clustering algorithm ,  image clustering

Author keywords (8)： algorithm ,  clustering ,  k-means ,  lower bound ,  singular value decomposition ,  principal component analysis ,  dimensionality reduction ,  performance

JST classification (2)： Other computer utilization technology  (JE14000C) ,  Theory of computation  (JB02000A)

Reference (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

Terms in the title (5)： 次元 ,  総和 ,  下界 ,  K-meansクラスタリングアルゴリズム ,  加速