一種自適應(yīng)AP算法的matlab實(shí)現(xiàn)

向培素

(西南民族大學(xué)電氣信息工程學(xué)院, 四川 成都 610041)

一種自適應(yīng)AP算法的matlab實(shí)現(xiàn)

向培素

(西南民族大學(xué)電氣信息工程學(xué)院, 四川 成都 610041)

AP算法是FeyBJ.等人提出的一種聚類算法.與傳統(tǒng)的K均值聚類算法相比, AP算法不需要選擇初始的聚類中心點(diǎn), 因此, 聚類結(jié)果更客觀.但AP算法中相似度矩陣對角線上的偏向值需要人為設(shè)定, 而這個值會影響到聚類數(shù)目;另外, 當(dāng)AP算法發(fā)生震蕩時, 算法無法自動退出震蕩.為解決AP算法中的振蕩問題及相似度矩陣對角線上元素值的確定問題, 王開軍等人提出了自適應(yīng)AP算法, 逐步改變偏向值p, 得到不同的聚類結(jié)果, 再根據(jù)聚類結(jié)果的Silhouette指標(biāo), 找出最好的Silhouette指標(biāo)對應(yīng)的偏向值及聚類結(jié)果.當(dāng)震蕩發(fā)生時, 逐步增加阻尼因子值, 直到算法退出震蕩.使用MATLAB實(shí)現(xiàn)了自適應(yīng)AP算法和Silhouette評價指標(biāo), 為后續(xù)的研究工作打下基礎(chǔ).

自適應(yīng)AP算法; Silhouette指標(biāo); 聚類算法; Matlab

1 引言

在自然科學(xué)和社會科學(xué)中, 存在著大量的分類問題.聚類和分類的不同之處在于, 聚類對象的類別是未知的, 而分類對象的類別是已知的.這個特點(diǎn)非常適用于當(dāng)前大數(shù)據(jù)背景下的數(shù)據(jù)挖掘.隨著各個領(lǐng)域數(shù)據(jù)的增多, 數(shù)據(jù)聚類分析成為一個非常重要的分析工具.

AP(Affinity propagation clustering)算法[1]是在貝葉斯網(wǎng)絡(luò)[2]的基礎(chǔ)上, 由對數(shù)域中的和積算法[3]——最大和算法推導(dǎo)出來的.這個算法通過在數(shù)據(jù)點(diǎn)之間傳遞消息, 來獲得使各個數(shù)據(jù)點(diǎn)與所屬類的類代表點(diǎn)的相似度之和取最大值的聚類結(jié)果.

正如王開軍等人指出的, AP算法有兩個缺陷, 一個是在計(jì)算相似度矩陣時, 其對角線上的取值只能人手工設(shè)定, 這就很難設(shè)定為最優(yōu)值, 而這個取值會影響到最后的聚類結(jié)果.另一個缺陷是當(dāng)振蕩發(fā)生后, 就很難自己停下來.為解決這兩個問題, 提出了自適應(yīng)AP算法[4-5].

鑒于文獻(xiàn)[6]已無效, 無法獲取算法源程序, 本文使用matlab重新實(shí)現(xiàn)了王開軍等人提出的自適應(yīng)AP算法,為后期的研究工作打下了基礎(chǔ).

本文分為兩個部分: 1)介紹了AP算法和自適應(yīng)AP算法, 并用matlab實(shí)現(xiàn)了自適應(yīng)AP算法; 2)介紹了Silhouette聚類評價指標(biāo), 并使用matlab在自適應(yīng)AP算法中實(shí)現(xiàn)了該評價指標(biāo)的計(jì)算.

2 AP算法和自適應(yīng)AP算法

2.1 AP算法

在AP算法中, 對N個數(shù)據(jù)點(diǎn)的聚類, 可以看做是尋找使各個數(shù)據(jù)點(diǎn)與其所屬類代表點(diǎn)相似度之和最大的那種聚類方式.用公式可以表示為:

上面等式的右邊, 正好適用于最大和算法.由于最大和算法是對數(shù)域的和積算法.因此, 可以使用因子圖來表示上面的等式.由此推導(dǎo)出了下面的遞推迭代公式:

其中rold指上次迭代計(jì)算出的r值, aold指上次迭代計(jì)算出的a值.從算法結(jié)束條件及為避免振蕩采取的措施來看, 一旦發(fā)生振蕩, 算法是無法自行結(jié)束的.

2.2 自適應(yīng)AP算法

自適應(yīng)AP算法包括了三部分內(nèi)容: 1.自適應(yīng)阻尼: 如果算法發(fā)生振蕩, 則逐步增加阻尼因子的值以消除振蕩.2.自適應(yīng)逃離: 如果在>=0.85時, 算法仍然振蕩, 則降低相似度矩陣對角線上元素的值(p值), 以退出振蕩, 并使用新的p值重新進(jìn)行迭代計(jì)算.3.自適應(yīng)掃描: 逐步減少p值會導(dǎo)致不同的聚類數(shù)目, 以具有最優(yōu)Silhouette評價指標(biāo)的聚類結(jié)果為最后的聚類結(jié)果.

自適應(yīng)阻尼算法中, 采用“非振蕩特征”的出現(xiàn)次數(shù)來判斷是否發(fā)生振蕩.“非振蕩特征”是指迭代產(chǎn)生的新的聚類數(shù)目等于或者小于本次迭代前的聚類數(shù)目.也就是說, 迭代產(chǎn)生的聚類數(shù)目不變或者減少, 則認(rèn)為沒有發(fā)生振蕩.

自適應(yīng)掃描算法, 是將相似度矩陣s對角線上元素的值設(shè)為矩陣s所有其它元素的均值的一半, 然后進(jìn)行迭代運(yùn)算, 當(dāng)算法收斂后, 記錄下來.再將p值減少, 進(jìn)行迭代運(yùn)算, 待收斂后, 再記錄下來...持續(xù)這個過程, 直到聚類數(shù)K=2, 或者整個迭代次數(shù)超過50000次.然后將所有記錄下來的聚類結(jié)果進(jìn)行比較, 選取Silhouette評價指標(biāo)最優(yōu)的那個作為最后的聚類結(jié)果.

3 Silhouette聚類評價指標(biāo)

這些距離都可以通過相似度矩陣求得.

自適應(yīng)AP算法中, 該指標(biāo)的matlab代碼如下:

4 結(jié)論

針對AP算法偏向值p無法自動設(shè)定, 及算法發(fā)生震蕩, 無法自動退出的問題, 王開軍等人提出了自適應(yīng)AP算法, 本文中使用matlab實(shí)現(xiàn)了自適應(yīng)AP算法和Silhouette聚類評價指標(biāo), 該程序可以作為matlab的工具箱應(yīng)用于圖像檢索、圖像分割、圖像識別、設(shè)施選址、文本挖掘等領(lǐng)域, 也可以作為聚類算法研究的基礎(chǔ): 在此基礎(chǔ)上進(jìn)行進(jìn)一步的聚類算法優(yōu)化, 或者不同聚類算法的特征比對, 或者新的聚類算法的應(yīng)該領(lǐng)域, 應(yīng)用方法的研究.

[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]王開軍, 張軍英, 李丹, 等.自適應(yīng)仿射傳播聚類[J].自動化學(xué)報(bào), 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]向培素.近鄰半監(jiān)督聚類算法的MATLAB實(shí)現(xiàn)[J].數(shù)字技術(shù)與應(yīng)用, 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]張連文, 郭海鵬.貝葉斯網(wǎng)引論[M].北京: 科學(xué)出版社, 2006.

[10]張殿祜, 方紹輝, 丁瀟君.熵——度量隨機(jī)變量不確定性的一種尺度[J].系統(tǒng)工程與電子技術(shù), 1997, 11: 1-8.

[11]陳峰, 劉紅, 徐文立.遞推信度傳播算法——按良序的信度傳播[J].自動化學(xué)報(bào), 2010, 36(8): 1091-1098.

[12]楊燕, 靳蕃.KAMEL Mohamed聚類有效性評價綜述[J].計(jì)算機(jī)應(yīng)用研究, 2008, 25(6): 1630-1638.

[13]向培素.聚類算法綜述[J].西南民族大學(xué)學(xué)報(bào): 自然科學(xué)版, 2011(1): 112-114.

[14]張惟皎, 劉春煌, 李芳玉.聚類質(zhì)量的評價方法[J].計(jì)算機(jī)工程, 2005, 31(20): 10-12.

[15]孫吉貴, 劉杰, 趙連宇.聚類算法研究[J].軟件學(xué)報(bào), 2008, 19(1): 48-61.

[16]周世兵, 徐振源, 唐旭清.基于近鄰傳播算法的最佳聚類數(shù)確定方法比較研究[J].計(jì)算機(jī)科學(xué), 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-), 女, 漢族, 湖北人, 副教授, 主要研究方向: 計(jì)算機(jī)應(yīng)用.

2012年度西南民族大學(xué)中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)項(xiàng)目(12NZYQN05).