张远鹏 邓赵红 钟富礼 杭文龙 王士同,

1(江南大学数字媒体学院 江苏无锡 214122)

2(南通大学医学信息学系 江苏南通 226019)

3(香港理工大学计算学系 香港 999077)

(155297131@qq.com)

聚类分析是一种无监督的学习方法，在模式识别领域占有非常重要的地位，成熟的聚类算法目前在图像分割、数据挖掘、生物信息学以及计算机视觉等领域得到了广泛的应用[1-3].聚类的目标是找到数据集中样本的“自然分组”，即相似样本的集合，称之为“簇”.目前聚类的方法有很多种，其中基于代表点的聚类算法近年来受到了广泛的关注.

代表点(exemplar)是数据集中实际存在的样本，代表簇中心.目前，基于代表的聚类算法可大体分为3类：

1) 以AP(affinity propagation)[4]和EEM (enhancedα-expansion move)[5]等为代表的聚类算法.该类算法可以通过优化Markov随机场(Markov random field, MRF)进行求解.优化MRF的方法有2种：①AP所采用的基于信息传递的LBP(loop belief propagation)算法[6]；②EEM所采用基于Graph Cuts的方法[7].在该类算法中，将数据集中所有的样本都当成潜在的类中心，然后通过迭代不断更新每个样本的吸引度值和归属度值，直到产生高质量的代表点[5].

2) 以K-medoid[8]及其模糊版本FCMdd(fuzzyc-medoids)[9]等为代表的聚类算法.该类算法首先以随机的方式选择代表点，然后通过不断迭代调整，使得距离平方误差之和达到最小[4].

3) 以CDP(clustering by fast search and find of density peaks)[10]及其相关改进算法为代表的基于密度的聚类算法[11]，该类算法通过密度估计，可以发现任意形状数据集的密度峰值点(代表点).

上述不同类型的基于代表点聚类算法，有着各自的优缺点.例如，AP算法突破了类中心及类中心个数需要预设的限……