title: A fast clustering algorithm for data with a few labeled instances.
abstract: The diameter of a cluster is the maximum intracluster distance between pairs of instances within the same cluster, and the split of a cluster is the minimum distance between instances within the cluster and instances outside the cluster. Given a few labeled instances, this paper includes two aspects. First, we present a simple and fast clustering algorithm with the following property: if the ratio of the minimum split to the maximum diameter (RSD) of the optimal solution is greater than one, the algorithm returns optimal solutions for three clustering criteria. Second, we study the metric learning problem: learn a distance metric to make the RSD as large as possible. Compared with existing metric learning algorithms, one of our metric learning algorithms is computationally efficient: it is a linear programming model rather than a semidefinite programming model used by most of existing algorithms. We demonstrate empirically that the supervision and the learned metric can improve the clustering quality.
authors: Electric Power Research Institute of Guangdong Power Grid Corporation, Guangzhou 510080, China.
authors: Jinfeng
authors: J
authors: Yang
authors: Electric Power Research Institute of Guangdong Power Grid Corporation, Guangzhou 510080, China.
authors: Yong
authors: Y
authors: Xiao
authors: School of Computer Science and Engineering, South China University of Technology, Guangzhou 510006, China.
authors: Jiabing
authors: J
authors: Wang
authors: School of Computer Science and Engineering, South China University of Technology, Guangzhou 510006, China.
authors: Qianli
authors: Q
authors: Ma
authors: School of Materials Science and Engineering, South China University of Technology, Guangzhou 510006, China.
authors: Yanhua
authors: Y
authors: Shen
mesh_terms: D000465:Algorithms; D001185:Artificial Intelligence; D016000:Cluster Analysis; D019295:Computational Biology / Q000379:methods; D007858:Learning / Q000502:physiology*; D008962:Models, Theoretical