一种自适应AP算法的matlab实现

向培素

(西南民族大学电气信息工程学院, 四川 成都 610041)

一种自适应AP算法的matlab实现

向培素

(西南民族大学电气信息工程学院, 四川 成都 610041)

AP算法是FeyBJ.等人提出的一种聚类算法.与传统的K均值聚类算法相比, AP算法不需要选择初始的聚类中心点, 因此, 聚类结果更客观.但AP算法中相似度矩阵对角线上的偏向值需要人为设定, 而这个值会影响到聚类数目;另外, 当AP算法发生震荡时, 算法无法自动退出震荡.为解决AP算法中的振荡问题及相似度矩阵对角线上元素值的确定问题, 王开军等人提出了自适应AP算法, 逐步改变偏向值p, 得到不同的聚类结果, 再根据聚类结果的Silhouette指标, 找出最好的Silhouette指标对应的偏向值及聚类结果.当震荡发生时, 逐步增加阻尼因子值, 直到算法退出震荡.使用MATLAB实现了自适应AP算法和Silhouette评价指标, 为后续的研究工作打下基础.

自适应AP算法; Silhouette指标; 聚类算法; Matlab

1 引言

在自然科学和社会科学中, 存在着大量的分类问题.聚类和分类的不同之处在于, 聚类对象的类别是未知的, 而分类对象的类别是已知的.这个特点非常适用于当前大数据背景下的数据挖掘.随着各个领域数据的增多, 数据聚类分析成为一个非常重要的分析工具.

AP(Affinity propagation clustering)算法[1]是在贝叶斯网络[2]的基础上, 由对数域中的和积算法[3]——最大和算法推导出来的.这个算法通过在数据点之间传递消息, 来获得使各个数据点与所属类的类代表点的相似度之和取最大值的聚类结果.

正如王开军等人指出的, AP算法有两个缺陷, 一个是在计算相似度矩阵时, 其对角线上的取值只能人手工设定, 这就很难设定为最优值, 而这个取值会影响到最后的聚类结果.另一个缺陷是当振荡发生后, 就很难自己停下来.为解决这两个问题, 提出了自适应AP算法[4-5].

鉴于文献[6]已无效, 无法获取算法源程序, 本文使用matlab重新实现了王开军等人提出的自适应AP算法,为后期的研究工作打下了基础.

本文分为两个部分: 1)介绍了AP算法和自适应AP算法, 并用matlab实现了自适应AP算法; 2)介绍了Silhouette聚类评价指标, 并使用matlab在自适应AP算法中实现了该评价指标的计算.

2 AP算法和自适应AP算法

2.1 AP算法

在AP算法中, 对N个数据点的聚类, 可以看做是寻找使各个数据点与其所属类代表点相似度之和最大的那种聚类方式.用公式可以表示为:

上面等式的右边, 正好适用于最大和算法.由于最大和算法是对数域的和积算法.因此, 可以使用因子图来表示上面的等式.由此推导出了下面的递推迭代公式:

其中rold指上次迭代计算出的r值, aold指上次迭代计算出的a值.从算法结束条件及为避免振荡采取的措施来看, 一旦发生振荡, 算法是无法自行结束的.

2.2 自适应AP算法

自适应AP算法包括了三部分内容: 1.自适应阻尼: 如果算法发生振荡, 则逐步增加阻尼因子的值以消除振荡.2.自适应逃离: 如果在>=0.85时, 算法仍然振荡, 则降低相似度矩阵对角线上元素的值(p值), 以退出振荡, 并使用新的p值重新进行迭代计算.3.自适应扫描: 逐步减少p值会导致不同的聚类数目, 以具有最优Silhouette评价指标的聚类结果为最后的聚类结果.

自适应阻尼算法中, 采用“非振荡特征”的出现次数来判断是否发生振荡.“非振荡特征”是指迭代产生的新的聚类数目等于或者小于本次迭代前的聚类数目.也就是说, 迭代产生的聚类数目不变或者减少, 则认为没有发生振荡.

自适应扫描算法, 是将相似度矩阵s对角线上元素的值设为矩阵s所有其它元素的均值的一半, 然后进行迭代运算, 当算法收敛后, 记录下来.再将p值减少, 进行迭代运算, 待收敛后, 再记录下来...持续这个过程, 直到聚类数K=2, 或者整个迭代次数超过50000次.然后将所有记录下来的聚类结果进行比较, 选取Silhouette评价指标最优的那个作为最后的聚类结果.

3 Silhouette聚类评价指标

这些距离都可以通过相似度矩阵求得.

自适应AP算法中, 该指标的matlab代码如下:

4 结论

针对AP算法偏向值p无法自动设定, 及算法发生震荡, 无法自动退出的问题, 王开军等人提出了自适应AP算法, 本文中使用matlab实现了自适应AP算法和Silhouette聚类评价指标, 该程序可以作为matlab的工具箱应用于图像检索、图像分割、图像识别、设施选址、文本挖掘等领域, 也可以作为聚类算法研究的基础: 在此基础上进行进一步的聚类算法优化, 或者不同聚类算法的特征比对, 或者新的聚类算法的应该领域, 应用方法的研究.

[1]FreyBJ, DUeCkD.Clustering by Passing messages between data points[J].Science, 2007, 315: 972-976.

[2]JUDEA PEARL.Fusion, Propagation, and Structuring in Belief Networks [J].Artificial Intelligence , 1986, 29: 241-288.

[3]FRANK R, KSCHISCHANG,BRENDAN J, et al.Factor Graphs and the Sum-Product Algorithm[J].Trans Inform Theory , 2001, 47(2): 498-519.

[4]KAIJUN WANG, JUNYING ZHANG, DAN LI, et al.Adaptive Affinity Propagation Clustering [J].Acta Automatica Sinica, 2007, 33(12): 1242-1246.

[5]王开军, 张军英, 李丹, 等.自适应仿射传播聚类[J].自动化学报, 2007, 33(12): 1242-1246.

[6]WANG K J.Supplement of adaptive affinity propagation clustering[EB/OL].(2007-12-11)[2014-03-19]http://www.mathworks.com/ matlabcentral/ fileexchange/loadAuthor.do?objectType=arthor&objectId=1095267.

[7]向培素.近邻半监督聚类算法的MATLAB实现[J].数字技术与应用, 2012, 08: 100-101.

[8]HALKIDI M, VAZIRGIANNIS M, BATISTAKIS Y.Quality scheme assessment in the clustering process [A].Proc of 4thEur Conf Principles and Practice of Knowledge Discovery in Databases[C].2000:165-276.

[9]张连文, 郭海鹏.贝叶斯网引论[M].北京: 科学出版社, 2006.

[10]张殿祜, 方绍辉, 丁潇君.熵——度量随机变量不确定性的一种尺度[J].系统工程与电子技术, 1997, 11: 1-8.

[11]陈峰, 刘红, 徐文立.递推信度传播算法——按良序的信度传播[J].自动化学报, 2010, 36(8): 1091-1098.

[12]杨燕, 靳蕃.KAMEL Mohamed聚类有效性评价综述[J].计算机应用研究, 2008, 25(6): 1630-1638.

[13]向培素.聚类算法综述[J].西南民族大学学报: 自然科学版, 2011(1): 112-114.

[14]张惟皎, 刘春煌, 李芳玉.聚类质量的评价方法[J].计算机工程, 2005, 31(20): 10-12.

[15]孙吉贵, 刘杰, 赵连宇.聚类算法研究[J].软件学报, 2008, 19(1): 48-61.

[16]周世兵, 徐振源, 唐旭清.基于近邻传播算法的最佳聚类数确定方法比较研究[J].计算机科学, 2011,38(2):225-228.

The MATLAB program designing of adaptive AP algorithm

XIANG Pei-su
( School of Electrical & Information Engineering, Southwest University for Nationalities,Chengdu 610041, P.R.C.)

The AP algorithm is a kind of clustering algorithm proposed by FeyBJ.et al. Compared with the traditional k-means clustering algorithm, the AP algorithm does not need to select the initial exemplare. Therefore, the cluster results are more objective. The diagonal of the similarity matrix in AP algorithm is hard to determine, and the value will affect the clustering number. In addition, the AP algorithm oscillate algorithm cannot automatically exit. To solve the problem of oscillation of the AP algorithm and to determine the diagonal element value of the similarity matrix, WANG Kai-jun et al.proposed adaptive AP algorithm, changing p step by step, obtain the different clustering result, according to the clustering results's Silhouette index, find out the best clustering results. When oscillations occurs, AP algorithm increases the damping factor value step by step, until the oscillation stops. The paper proposed a MATLAB programming of adaptive AP and Silhouette Index. It provides a foundation work for further study.

adaptive AP; silhouette; clustering algorithm; Matlab

TP301.6

A

1003-4271(2014)06-0877-06

10.3969/j.issn.1003-4271.2014.06.14

2014-10-08

向培素(1974-), 女, 汉族, 湖北人, 副教授, 主要研究方向: 计算机应用.

2012年度西南民族大学中央高校基本科研业务费专项项目(12NZYQN05).