基于變異賦權的吸引子傳播算法

韓旭明，孫海波，王麗敏

（1.長春工業大學 軟件學院，長春 130012；2.吉林財經大學 經濟模擬研究所，長春 130117；3.吉林財經大學 管理科學與信息工程學院，長春 130117）

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

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

1 吸引子傳播算法

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

表示樣本xk適合xi類代表點的程度.

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

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

獲得每個樣本類代表點.

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

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

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

其中：λ＝0.5；t為當前迭代次數.當類代表點在迭代過程中不再發生變化或達到最大迭代次數時，算法結束.

2 CV－AP算法

2.1 特征賦權有效性分析

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

圖1 Iris數據第1維和第2維屬性散點分布Fig.1 1st and 2nd dimensional attribute scatter of Iris

圖2 Iris數據第3維和第4維屬性散點分布Fig.2 3rd and 4th dimensional attribute scatter of Iris

圖3 Wine數據第1維和第3維屬性散點分布Fig.3 1th and 3rd dimensional attribute scatter of Wine

圖4 Wine數據第7維和第13維屬性散點分布Fig.4 7th and 13th dimensional attribute scatter of Wine

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

2.2 變異系數

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

其中：ˉX表示均值；Sx表示標準差；vx表示變異系數.

2.3 CV－AP算法流程

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

其中：ωd表示第d維屬性權重；vd表示第d維屬性的變異系數；T表示樣本屬性數目.

CV－AP算法步驟如下：

1）通過式（7）～（9）計算樣本各屬性的變異系數；

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

其中：φ表示調節權；N表示樣本數；

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

4）根據式（2）獲得相應類代表點；

5）若算法達到最大迭代次數或類代表點若干次迭代后均不再變化，則算法結束；否則返回3）.

表1 數據特征Table 1 Data characteristics

3 仿真實驗

為了驗證CV－AP算法的可行性與有效性，選取UCI機器學習數據集中 Haberman，ecoli，Iris，Wine，glass數據作為實驗對象，分別采用CV－AP算法與傳統AP算法、K－均值算法進行對比實驗，數據特征列于表1，選擇Silhouette指標作為聚類質量評價指標.

3.1 Silhouette指標

設一個樣本容量為N的數據集被分為k類

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

在數據集中，所有樣本的平均Sil值不僅能反映聚類結構的類內緊湊性，且能有效反映類間可分性，Sil值越大表明聚類效果越好.

3.2 實驗結果與分析

圖5 實驗結果對比Fig.5 Comparisons of experimental results

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

表2 CV－AP調節權φ值Table 2 Adjust weightφvalues obtained by CV－AP method

綜上可見，傳統吸引子傳播算法未考慮到樣本屬性與聚類結果貢獻度間的聯系，按樣本屬性對聚類結果貢獻度相似或相同進行處理，聚類效果較差.針對此問題，本文提出了一種基于變異系數賦權的吸引子傳播算法，并給出新的相似度計算方法.實驗對比分析結果表明，本文提出的改進吸引子傳播算法，能有效克服冗余信息影響，該算法不僅具有傳統吸引子傳播算法的快速、高效等優點，且具有更好的聚類性能，聚類效果明顯優于傳統吸引子傳播算法和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］管仁初，裴志利，時小虎，等.權吸引子傳播算法及其在文本聚類中的應用 ［J］.計算機研究與發展，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，Frey 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］張震，汪斌強，李向濤，等.基于近鄰傳播學習的半監督流量分類方法 ［J］.自動化學報，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］于明，朱超.利用半監督近鄰傳播聚類算法實現P2P流量識別 ［J］.哈爾濱工程大學學報，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］儲岳中，徐波，高有濤.一種融合人工免疫系統與AP算法的分類器設計 ［J］.南京航空航天大學學報，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］肖宇，于劍.基于近鄰傳播算法的半監督聚類 ［J］.軟件學報，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，Feature Weighting and Anomalous Cluster Initializing inK－Means Clustering［J］.Pattern Recognition，2012，45（3）：1061－1075.

［12］薛麗香，邱保志.基于變異系數的邊界點檢測算法 ［J］.模式識別與人工智能，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］王開軍，張軍英，李丹，等.自適應仿射傳播聚類 ［J］.自動化學報，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.）