Locally Linear Metric Adaptation for Semi-Supervised Clustering
Hong Chang - Hong Kong University of Science and Technology Dit-Yan Yeung - Hong Kong University of Science and Technology
Many supervised and unsupervised learning algorithms are very sensitive to the choice of an appropriate distance metric. Whileclassification tasks can make use of class label information for metriclearning, such information is generally unavailable in conventional clusteringtasks. Some recent research sought to address a variant of the conventionalclustering problem called semi-supervised clustering, which performsclustering in the presence of some background knowledge or supervisoryinformation expressed as pairwise similarity or dissimilarity constraints. However, existing metric learning methods for semi-supervised clusteringmostly perform global metric learning through a linear transformation. Inthis paper, we propose a new metric learning method which performs nonlineartransformation globally but linear transformation locally. In particular, weformulate the learning problem as an optimization problem and present twomethods for solving it. Through some toy data sets, we show empirically thatour locally linear metric adaptation (LLMA) method can handle some difficultcases that cannot be handled satisfactorily by previous methods. We alsodemonstrate the effectiveness of our method on some real data sets.