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

Pairwise Constrained Semi-supervised Maximum Margin Clustering

作　　者：胡洋[1] 王井东 俞能海[1] 华先胜[2] 

机构地区：[1]中国科学技术大学电子工程与信息科学系,安徽合肥230027 [2]微软亚洲研究院,北京100190

出　　处：《小型微型计算机系统》2010年第5期932-936,共5页Journal of Chinese Computer Systems

基　　金：国家自然科学基金资助项目(60672056)资助;高等学校博士学科点专项科研基金资助课题项目(20070358040)资助

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

关 键 词：最大间隔 聚类 半监督 成对约束 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]