Learning low-rank kernel matrices for constrained clustering

被引:15
作者
Baghshah, Mahdieh Soleymani [1 ]
Shouraki, Saeed Bagheri [2 ]
机构
[1] Sharif Univ Technol, Dept Comp Engn, Tehran, Iran
[2] Sharif Univ Technol, Dept Elect Engn, Tehran, Iran
关键词
Low-rank kernel; Kernel learning; Distance metric; Constrained clustering; Semi-supervised; Spectral; ALGORITHM;
D O I
10.1016/j.neucom.2011.02.009
中图分类号
TP18 [人工智能理论];
学科分类号
140502 [人工智能];
摘要
Constrained clustering methods (that usually use must-link and/or cannot-link constraints) have been received much attention in the last decade. Recently, kernel adaptation or kernel learning has been considered as a powerful approach for constrained clustering. However, these methods usually either allow only special forms of kernels or learn non-parametric kernel matrices and scale very poorly. Therefore, they either learn a metric that has low flexibility or are applicable only on small data sets due to their high computational complexity. In this paper, we propose a more efficient non-linear metric learning method that learns a low-rank kernel matrix from must-link and cannot-link constraints and the topological structure of data. We formulate the proposed method as a trace ratio optimization problem and learn appropriate distance metrics through finding optimal low-rank kernel matrices. We solve the proposed optimization problem much more efficiently than SDP solvers. Additionally, we show that the spectral clustering methods can be considered as a special form of low-rank kernel learning methods. Extensive experiments have demonstrated the superiority of the proposed method compared to recently introduced kernel learning methods. Crown Copyright (C) 2011 Published by Elsevier B.V. All rights reserved.
引用
收藏
页码:2201 / 2211
页数:11
相关论文
共 52 条
[1]
[Anonymous], P 24 INT C MACH LEAR
[2]
[Anonymous], P ICML
[3]
[Anonymous], 2006, DISTANCE METRIC LEAR
[4]
[Anonymous], 2005, THESIS U TEXAS AUSTI
[5]
[Anonymous], P IEEE COMP SOC C CO
[6]
[Anonymous], 2003, Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence
[7]
[Anonymous], 2004, P 10 ACM SIGKDD INT, DOI DOI 10.1145/1014052.1014062
[8]
Baghshah MS, 2009, 21ST INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE (IJCAI-09), PROCEEDINGS, P1217
[9]
Kernel-based metric learning for semi-supervised clustering [J].
Baghshah, Mahdieh Soleymani ;
Shouraki, Saeed Bagheri .
NEUROCOMPUTING, 2010, 73 (7-9) :1352-1361
[10]
Metric learning for semi-supervised clustering using pairwise constraints and the geometrical structure of data [J].
Baghshah, Mahdieh Soleymani ;
Shouraki, Saeed Bagheri .
INTELLIGENT DATA ANALYSIS, 2009, 13 (06) :887-899