一种基于成对约束的半监督最大间隔聚类算法

Pairwise Constrained Semi-supervised Maximum Margin Clustering

最大间隔聚类是近来聚类分析的一个研究热点,为进一步提高其聚类准确性,提出一种基于成对约束的半监督最大间隔聚类算法.该算法在最大间隔聚类的目标函数中添加针对成对约束的损失项,从而对违反给定约束条件的分界面进行惩罚.对所得到的非凸优化问题,本文提出一种基于约束凹凸过程的迭代算法来进行高效求解.实验表明,本文提出的算法能极大地提高最大间隔聚类的准确性,其聚类性能也明显优于其他两种半监督聚类算法.

Maximum margin clustering （MMC） has been an active research topic recently. In order to further improve its performance,this paper presents a semi-supervised maximum margin clustering algorithm that incorporates additional pairwise constraints. A pairwise loss function is introduced into the clustering objective function which effectively penalizes the violation of the given constraints. To solve the resulting non-convex optimization problem,an efficient algorithm is proposed based on constrained concave-convex procedure（CCCP）. The experimental results demonstrate that the pairwise constrained semi-supervised MMC algorithm greatly outperforms the previous MMC algorithms and two other semi-supervised clustering algorithms.