基于變異賦權(quán)的吸引子傳播算法

韓旭明，孫海波，王麗敏

（1.長春工業(yè)大學(xué) 軟件學(xué)院，長春 130012；2.吉林財(cái)經(jīng)大學(xué) 經(jīng)濟(jì)模擬研究所，長春 130117；3.吉林財(cái)經(jīng)大學(xué) 管理科學(xué)與信息工程學(xué)院，長春 130117）

吸引子傳播算法（affinity propagation，AP）是一種新的無監(jiān)督聚類方法［1］.與其他聚類算法相比，該算法具有快速、高效、聚類效果穩(wěn)定且不必預(yù)先給定聚類數(shù)目等優(yōu)點(diǎn)，在解決大規(guī)模數(shù)據(jù)處理問題時(shí)具有獨(dú)特的優(yōu)勢.因此，被廣泛應(yīng)用于基因發(fā)現(xiàn)［2］、文本聚類［3］、人臉識(shí)別［4］和設(shè)施選址［5］等領(lǐng)域.張震等［6］通過引入近鄰傳播聚類機(jī)制構(gòu)建分類模型，提出一種基于近鄰傳播學(xué)習(xí)的半監(jiān)督流量分類方法；于明等［7］提出了一種基于半監(jiān)督近鄰傳播聚類算法的P2P流量識(shí)別方法；儲(chǔ)岳中等［8］結(jié)合人工免疫系統(tǒng)的自適應(yīng)識(shí)別能力與全局搜索能力及近鄰傳播算法自動(dòng)確定最佳聚類數(shù)目的能力，提出一種基于人工免疫系統(tǒng)與近鄰傳播相結(jié)合的分類算法.

吸引子傳播算法是基于近鄰信息傳播的聚類算法，它在數(shù)據(jù)形成相似度矩陣的基礎(chǔ)上進(jìn)行聚類，通常選用歐式距離作為相似度測算指標(biāo)［9］.歐式距離涉及樣本所有屬性，每種屬性對聚類結(jié)果貢獻(xiàn)度相似或相同，因此增加了與聚類無關(guān)屬性的作用而降低聚類效果.本文在傳統(tǒng)吸引子傳播算法的基礎(chǔ)上進(jìn)行改進(jìn)，為每個(gè)屬性賦予權(quán)重，并與聚類結(jié)果的貢獻(xiàn)度相匹配，提出一種基于變異系數(shù)賦權(quán)的吸引子傳播聚類算法，即CV－AP算法（coefficient of variation affinity propagation，CV－AP）.實(shí)驗(yàn)結(jié)果表明，本文提出的CV－AP算法在聚類過程中能有效降低冗余信息的誤導(dǎo)作用，明顯提高聚類質(zhì)量，且聚類性能優(yōu)于傳統(tǒng)吸引子傳播算法和K－均值算法.

1 吸引子傳播算法

吸引子傳播算法的基本思想是將所有樣本作為潛在的聚類中心，樣本間通過歸屬度和吸引度兩種信息進(jìn)行不斷傳遞，可認(rèn)為是信息在雙向圖上按照一定概率進(jìn)行傳播，尋找能量函數(shù)最小值的聚類策略.該算法輸入為樣本相似度矩陣，輸出為類代表點(diǎn)和各樣本與類代表點(diǎn)的所屬關(guān)系.設(shè)樣本xi和xk間的相似度為s（i，k），則

表示樣本xk適合xi類代表點(diǎn)的程度.

吸引子傳播算法為每個(gè)樣本xk設(shè)定一個(gè)偏向參數(shù)s（k，k），表示樣本xk成為類代表點(diǎn)的可能性大小，其值越大表明樣本xk被選為類代表點(diǎn)的可能性越大.該算法初始假設(shè)每個(gè)樣本成為類代表點(diǎn)的可能性相同，即設(shè)定所有s（k，k）為相同值P.一般情況下，P值為相似度矩陣所有值的中位數(shù).P值大小影響聚類數(shù)目，增大P值將增加類的數(shù)目，降低P值減小類的數(shù)目.

吸引子傳播算法中引入兩個(gè)重要信息參數(shù)共同確定每個(gè)樣本的類代表點(diǎn)，分別為歸屬度矩陣A＝（a（i，k））m×n和吸引度矩陣R＝（r（i，k））m×n，算法的迭代過程是兩種信息量迭代更新的過程.其中：a（i，k）表示樣本xk發(fā)送樣本xi的信息量，反映樣本xi選擇樣本xk為類代表點(diǎn)的適合程度；r（i，k）表示樣本xi發(fā)送樣本xk的信息量，指樣本xk積累的證據(jù)，反映樣本xk為樣本xi類代表點(diǎn)的代表程度.在吸引子傳播算法結(jié)束時(shí)，計(jì)算所有樣本歸屬度a（i，k）和吸引度r（i，k）之和，通過

獲得每個(gè)樣本類代表點(diǎn).

吸引子傳播算法歸屬度和吸引度更新過程如下：

初始化a（i，k）＝0.

為了避免吸引子傳播算法發(fā)生振蕩，本文在信息更新過程中引入阻尼因子λ∈［0，1），分別對當(dāng)前a（i，k）和r（i，k）的值與上一步迭代結(jié)果加權(quán)求和，得到更新的a（i，k）和r（i，k），迭代過程如下：

其中：λ＝0.5；t為當(dāng)前迭代次數(shù).當(dāng)類代表點(diǎn)在迭代過程中不再發(fā)生變化或達(dá)到最大迭代次數(shù)時(shí)，算法結(jié)束.

2 CV－AP算法

2.1 特征賦權(quán)有效性分析

聚類分析中通常假設(shè)樣本每種屬性對聚類結(jié)果作用相同，但由于樣本中存在噪聲屬性和聚類無關(guān)屬性，導(dǎo)致聚類效果不理想［10］.為更好地說明問題，本文以文獻(xiàn)［11］為例，從UCI機(jī)器學(xué)習(xí)數(shù)據(jù)集中選取Iris數(shù)據(jù)和Wine數(shù)據(jù)進(jìn)行說明.Iris數(shù)據(jù)共有150個(gè)樣本，4種屬性，分成3類，對第1維和第2維屬性散點(diǎn)圖與第3維和第4維屬性散點(diǎn)圖進(jìn)行對比，結(jié)果如圖1和圖2所示.Wine數(shù)據(jù)共有178個(gè)樣本，13種屬性，分成3類，對第1維和第3維屬性散點(diǎn)圖與第7維和第13維屬性散點(diǎn)圖進(jìn)行對比，結(jié)果如圖3和圖4所示.

圖1 Iris數(shù)據(jù)第1維和第2維屬性散點(diǎn)分布Fig.1 1st and 2nd dimensional attribute scatter of Iris

圖2 Iris數(shù)據(jù)第3維和第4維屬性散點(diǎn)分布Fig.2 3rd and 4th dimensional attribute scatter of Iris

圖3 Wine數(shù)據(jù)第1維和第3維屬性散點(diǎn)分布Fig.3 1th and 3rd dimensional attribute scatter of Wine

圖4 Wine數(shù)據(jù)第7維和第13維屬性散點(diǎn)分布Fig.4 7th and 13th dimensional attribute scatter of Wine

由圖1～圖4可見，圖1中第2類與第3類交叉樣本較多，而圖2能明顯看出分為3類且交叉樣本數(shù)少；圖3中第3類樣本分布在第1類和第2類樣本中，沒有清晰界限，而圖4界限清晰，分為3類.通過結(jié)果分析可知，Iris數(shù)據(jù)的第3維和第4維屬性對可分性優(yōu)于第1維和第2維屬性對，Wine數(shù)據(jù)中第7維和第13維屬性對可分性優(yōu)于第1維和第3維屬性對.因此，樣本的屬性不同，其可分性也不同.數(shù)據(jù)的分布影響聚類質(zhì)量，對于可分性好、重疊信息少的數(shù)據(jù)，其聚類結(jié)果更優(yōu).鑒于此，本文利用變異系數(shù)賦權(quán)方法提高可分性好的屬性貢獻(xiàn)度，降低無關(guān)屬性和噪聲屬性對聚類結(jié)果的影響.

2.2 變異系數(shù)

對于一組數(shù)據(jù)x1，x2，…，xn，其變異系數(shù)計(jì)算過程［12］如下：

其中：ˉX表示均值；Sx表示標(biāo)準(zhǔn)差；vx表示變異系數(shù).

2.3 CV－AP算法流程

本文將變異系數(shù)引入到吸引子傳播算法中，提出一種基于變異系數(shù)賦權(quán)的吸引子傳播算法，即CV－AP算法.在CV－AP算法中先利用變異系數(shù)對樣本屬性進(jìn)行賦權(quán)，得到新的相似度計(jì)算方法：

其中：ωd表示第d維屬性權(quán)重；vd表示第d維屬性的變異系數(shù)；T表示樣本屬性數(shù)目.

CV－AP算法步驟如下：

1）通過式（7）～（9）計(jì)算樣本各屬性的變異系數(shù)；

2）初始化矩陣A，a（i，k）＝0，根據(jù)式（10）計(jì)算相似度矩陣S，并根據(jù)文獻(xiàn)［3］中偏向參數(shù)計(jì)算方法對P賦初值，

其中：φ表示調(diào)節(jié)權(quán)；N表示樣本數(shù)；

3）根據(jù)式（3）～（6）更新矩陣A和矩陣R；

4）根據(jù)式（2）獲得相應(yīng)類代表點(diǎn)；

5）若算法達(dá)到最大迭代次數(shù)或類代表點(diǎn)若干次迭代后均不再變化，則算法結(jié)束；否則返回3）.

表1 數(shù)據(jù)特征Table 1 Data characteristics

3 仿真實(shí)驗(yàn)

為了驗(yàn)證CV－AP算法的可行性與有效性，選取UCI機(jī)器學(xué)習(xí)數(shù)據(jù)集中 Haberman，ecoli，Iris，Wine，glass數(shù)據(jù)作為實(shí)驗(yàn)對象，分別采用CV－AP算法與傳統(tǒng)AP算法、K－均值算法進(jìn)行對比實(shí)驗(yàn)，數(shù)據(jù)特征列于表1，選擇Silhouette指標(biāo)作為聚類質(zhì)量評價(jià)指標(biāo).

3.1 Silhouette指標(biāo)

設(shè)一個(gè)樣本容量為N的數(shù)據(jù)集被分為k類

Ci（i＝1，2，…，k），a（t）表示類Cj中的樣本t與Cj內(nèi)其他樣本平均距離或非相似度，d（t，Ci）表示Cj中的樣本t與另一個(gè)類Ci中所有樣本平均距離或非相似度，b（t）＝min｛d（t，Ci）｝，其中i＝1，2，…，k且i≠j，則樣本t的Silhouette指標(biāo)計(jì)算方法［13］為

在數(shù)據(jù)集中，所有樣本的平均Sil值不僅能反映聚類結(jié)構(gòu)的類內(nèi)緊湊性，且能有效反映類間可分性，Sil值越大表明聚類效果越好.

3.2 實(shí)驗(yàn)結(jié)果與分析

圖5 實(shí)驗(yàn)結(jié)果對比Fig.5 Comparisons of experimental results

分別利用CV－AP算法、傳統(tǒng)AP算法和K－均值算法進(jìn)行實(shí)驗(yàn)驗(yàn)證，通過調(diào)節(jié)偏向參數(shù)調(diào)節(jié)權(quán)φ值得到CV－AP算法的最佳聚類結(jié)果，φ值列于表2，實(shí)驗(yàn)結(jié)果如圖5所示.由圖5可見，CV－AP算法在5個(gè)測試數(shù)據(jù)中獲得的聚類結(jié)果均優(yōu)于AP算法.與K－均值算法相比，CV－AP算法除了在Iris數(shù)據(jù)得到與K－均值算法相同的聚類結(jié)果外，在其他數(shù)據(jù)聚類質(zhì)量均高于K－均值算法.Sil＞0.5表明聚類質(zhì)量高，各類之間能夠明顯區(qū)分；Sil＜0.5表明聚類間存在重疊；Sil＜0.2則表明缺乏實(shí)質(zhì)聚類結(jié)構(gòu).CV－AP算法在Iris，Wine和glass數(shù)據(jù)的Sil值均大于0.5，在Haberman和ecoli數(shù)據(jù)的Sil值也均大于0.4，表明對樣本屬性賦予一定權(quán)重不僅能降低冗余信息的影響，且能提高聚類效果，一定程度上改善了聚類結(jié)構(gòu)與聚類精度.

表2 CV－AP調(diào)節(jié)權(quán)φ值Table 2 Adjust weightφvalues obtained by CV－AP method

綜上可見，傳統(tǒng)吸引子傳播算法未考慮到樣本屬性與聚類結(jié)果貢獻(xiàn)度間的聯(lián)系，按樣本屬性對聚類結(jié)果貢獻(xiàn)度相似或相同進(jìn)行處理，聚類效果較差.針對此問題，本文提出了一種基于變異系數(shù)賦權(quán)的吸引子傳播算法，并給出新的相似度計(jì)算方法.實(shí)驗(yàn)對比分析結(jié)果表明，本文提出的改進(jìn)吸引子傳播算法，能有效克服冗余信息影響，該算法不僅具有傳統(tǒng)吸引子傳播算法的快速、高效等優(yōu)點(diǎn)，且具有更好的聚類性能，聚類效果明顯優(yōu)于傳統(tǒng)吸引子傳播算法和K－均值算法.

［1］Frey B J，Dueck D.Clustering by Passing Messages between Data Points［J］.Science，2007，315：972－976.

［2］Sumedha M L，Weigt M.Clustering by Soft－Constraint Affinity Propagation Applications to Gene－Expression Data［J］.Bioinformatics，2007，23（20）：2708－2715.

［3］管仁初，裴志利，時(shí)小虎，等.權(quán)吸引子傳播算法及其在文本聚類中的應(yīng)用 ［J］.計(jì)算機(jī)研究與發(fā)展，2010，47（10）：1733－1740.（GUAN Renchu，PEI Zhili，SHI Xiaohu，et al.Weight Affinity Propagation and Its Application to Text Clustering［J］.Journal of Computer Research and Development，2010，47（10）：1733－1740.）［4］DU Chunhua，YANG Jie，WU Qiang，et al.Locality Preserving Projections Plus Affinity Propagation：A Fast Method for Face Recognition［J］.Optical Engineering，2008，47（4）：040501.

［5］Lazic N，F(xiàn)rey B J，Aarabi P.Solving the Incapacitated Facility Location Problem Using Message Passing Algorithms［C］／／Proceedings of the 13th International Conference on Artificial Intelligence and Statistics.Sardinia：［s.n.］，2010：429－436.

［6］張震，汪斌強(qiáng)，李向濤，等.基于近鄰傳播學(xué)習(xí)的半監(jiān)督流量分類方法 ［J］.自動(dòng)化學(xué)報(bào)，2013，39（7）：1100－1109.（ZHANG Zhen，WANG Binqiang，LI Xiangtao，et al.Semi－supervised Traffic Identification Based on Affinity Propagation［J］.Acta Automatica Sinica，2013，39（7）：1100－1109.）

［7］于明，朱超.利用半監(jiān)督近鄰傳播聚類算法實(shí)現(xiàn)P2P流量識(shí)別 ［J］.哈爾濱工程大學(xué)學(xué)報(bào)，2013，34（5）：653－657.（YU Ming，ZHU Chao.P2PTraffic Identification Based on Semi－supervised Affinity Propagation Clustering［J］.Journal of Harbin Engineering University，2013，34（5）：653－657.）

［8］儲(chǔ)岳中，徐波，高有濤.一種融合人工免疫系統(tǒng)與AP算法的分類器設(shè)計(jì) ［J］.南京航空航天大學(xué)學(xué)報(bào)，2013，45（2）：232－238.（CHU Yuezhong，XU Bo，GAO Youtao.Design of Classifier Based on Combination of Artificial Immune System and AP Algorithm ［J］.Journal of Nanjing University of Aeronautics ＆ Astronautics，2013，45（2）：232－238.）

［9］肖宇，于劍.基于近鄰傳播算法的半監(jiān)督聚類 ［J］.軟件學(xué)報(bào)，2008，19（11）：2803－2813.（XIAO Yu，YU Jian.Semi－supervised Clustering Based on Affinity Propagation Algorithm ［J］.Journal of Software，2008，19（11）：2803－2813.）

［10］Ahmad W，Narayanan A.Feature Weighing for Efficient Clustering ［C］／／Proceedings of the 6th International Conference on Advanced Information Management and Service.Piscataway：IEEE Press，2010：236－242.

［11］Amorim R C，de，Mirkin B.Minkowski Metric，F(xiàn)eature Weighting and Anomalous Cluster Initializing inK－Means Clustering［J］.Pattern Recognition，2012，45（3）：1061－1075.

［12］薛麗香，邱保志.基于變異系數(shù)的邊界點(diǎn)檢測算法 ［J］.模式識(shí)別與人工智能，2009，22（5）：799－802.（XUE Lixiang，QIU Baozhi.Boundary Points Detection Algorithm Based on Coefficient of Variation［J］.PR ＆AI，2009，22（5）：799－802.）

［13］王開軍，張軍英，李丹，等.自適應(yīng)仿射傳播聚類 ［J］.自動(dòng)化學(xué)報(bào)，2007，33（12）：1242－1246.（WANG Kaijun，ZHANG Junying，LI Dan，et al.Adaptive Affinity Propagation Clustering［J］.Acta Automatica Sinica，2007，33（12）：1242－1246.）