基于穩定閾值的吸引子傳播算法

王麗敏, 王依章, 韓旭明, 黃 娜

(1.吉林財經大學 管理科學與信息工程學院, 長春 130117；2.長春工業大學 計算機科學與工程學院, 長春 130012；3.上海財經大學 信息管理與工程學院, 上海 200433)

基于穩定閾值的吸引子傳播算法

王麗敏1, 王依章1, 韓旭明2, 黃 娜3

(1.吉林財經大學 管理科學與信息工程學院, 長春 130117；
2.長春工業大學 計算機科學與工程學院, 長春 130012；
3.上海財經大學 信息管理與工程學院, 上海 200433)

針對傳統吸引子傳播算法(AP)聚類性能受偏向參數影響較大的問題, 提出一種改進的吸引子傳播算法, 即基于穩定閾值的吸引子傳播聚類算法(STAP).該算法通過穩定閾值, 衡量獲得真實類數時的收斂狀態, 然后捕捉該狀態下的偏向參數； 為加快算法的收斂速度, 采用S型函數作為收斂因子調節阻尼系數.仿真模擬實驗結果表明, 與傳統吸引子傳播聚類算法相比, 基于穩定閾值的吸引子傳播聚類算法聚類精度更高, 收斂速度更快.

吸引子傳播算法； 穩定閾值； 收斂因子

吸引子傳播算法(affinity propagation, AP)是一種新聚類算法.目前, 該算法已成功應用于圖像分割[1-3]、圖像檢索[4]、基因識別[5]、文本聚類[6]和最優航空路線確定[7]等領域.目前, 對該算法已有多種改進方法, 如Sakellariou等[8]提出了將多重假設檢驗和吸引子傳播算法相結合, 對基因表達數據進行分類的方法； Qasim等[9]提出了將吸引子傳播算法與文本概念圖半自動生成技術相結合的方法； 于吉紅等[10]提出了用空間向量模型計算特征相似度, 并已應用于艦船三維模型進行視點空間均勻投影； 張震等[11]提出了將吸引子傳播算法與半監督流量分類相結合的方法, 即STI-AP算法.針對上述算法, 本文提出一種穩定閾值函數優化偏向參數, 提高吸引子傳播算法對類空間搜索準確度的方法——基于穩定閾值的吸引子傳播聚類算法(STAP), 該方法采用Sigmoid函數作為收斂因子的加速策略, 以提高算法對高維大數據的處理能力, 加快算法的收斂速度.

1 吸引子傳播聚類算法

吸引子傳播聚類算法將數據集的所有樣本點均視為候選類代表點, 利用數據點間的相似度構造相似度關系矩陣S[12-13], 其中相似度是兩點間距離的相反數[14], 公式如下：

s(i,k)=-‖xi-xk‖.

（1）

在吸引子傳播聚類算法中, 初始假設每個樣本成為類代表點的可能性相同[15], 即設定所有s(k,k)為相同值P,P值是相似度矩陣所有值的中位數[16].該算法引入兩個重要信息參數共同決定各樣本的類代表點, 分別是歸屬度矩陣A=(a(i,k))m×n和吸引度矩陣R=(r(i,k))m×n, 算法迭代過程是兩種信息量迭代更新的過程, 其中:a(i,k)是樣本Xk發送給樣本Xi的信息量, 描述i點選擇k點作為聚類中心的適合程度;r(i,k)是樣本Xi發送給樣本Xk的信息量, 描述k點適合作為數據點i的聚類中心的適合程度[17].算法結束時, 通過公式

計算歸屬度a(i,k)、吸引度r(i,k)及二者之和, 獲得每個樣本的類代表點[18-19].

在吸引子傳播聚類算法中, 引入阻尼因子增強算法迭代的穩定性[20], 公式如下:

其中,t為當前迭代次數.本文設當類代表點在連續10次迭代過程中不發生變化或達到最大迭代次數時, 算法結束.

2 STAP算法描述

2.1偏向參數優化技術

表1列出了偏向參數在不同倍數下的各項試驗參數.由表1可見, 偏向參數P值對聚類精度、聚類類數和迭代速度均有較大影響.通過選取合適的偏向參數, 能獲得標準數據集的最佳聚類類數, 提高聚類性能.本文提出的基于穩定閾值的吸引子傳播聚類算法能有效解決偏向參數的優化問題, 使類空間的搜索精度更準確.圖1為在不同偏向參數下Ionosphere數據集的聚類類數.由圖1可見, Ionosphere數據集的聚類類數隨偏向參數的增大出現3個階段的變化: 第一階段為收斂階段, 該階段聚類結果較好, 較少發生重復現象, 算法收斂速度較快; 第二階段為穩定階段, 該階段獲得該數據集的最優聚類類數, 同時聚類精度較高； 第三階段是震蕩階段, 算法發生震蕩, 此時該算法所得到的聚類結果失真.大量數據集實驗表明, 使用吸引子傳播聚類算法進行仿真模擬聚類均有上述3個階段的變化.

基于穩定閾值的吸引子傳播聚類算法是一種偏向參數優化技術, 即用穩定閾值衡量算法的穩定狀態并通過數學建模量化該狀態.穩定閾值描述聚類結果的重復度, 重復度越大, 算法迭代越穩定, 聚類類數越接近真實類數.此時, 在類空間對應的偏向參數下, 聚類性能更優.數據集的樣本數和維度對吸引子傳播聚類算法的聚類結果影響較大, 因此, 本文提出一種關于樣本數與維度比的線性函數作為穩定閾值的極限值:

其中： SN表示樣本數; dim表示維度.

表1 不同偏向參數下AP聚類算法對Wine數據集的聚類參數Table 1 Clustering parameters of Wine data set by AP clustering algorithm at different P values

圖1 在不同偏向參數P下Ionosphere數據集的聚類類數Fig.1 Class number of Ionosphere at different P values

穩定閾值的大小主要由樣本數和維度決定.樣本數越大, 維度越小, 動態搜索程度越大, 這符合吸引子傳播聚類算法的聚類原理.n與樣本數和維度的比值成正比, 通過基于穩定閾值吸引子傳播聚類算法的遍歷搜索n, 使算法與數據集的擬合度最高.

基于穩定閾值吸引子傳播聚類算法提出基于穩定因子、震蕩因子和弱穩定因子的線性函數作為穩定閾值的度量函數.穩定因子為聚類重復度, 震蕩因子為聚類震蕩度, 弱穩定因子數為聚類結果順序遞減度.引入弱穩定因子能更準確地捕捉震蕩度少的數據集類空間的穩定狀態.因此穩定閾值為

其中： SF為穩定因子; CF為震蕩因子; WSF為弱穩定因子.

2.2S型收斂因子加速技術

針對傳統吸引子傳播聚類算法在對大數據和高維數據聚類時存在處理速度較慢的問題, 本文提出一種基于S型收斂因子的加速技術.在吸引子傳播聚類算法中, 阻尼系數越大, 收斂速度越慢, 合適的阻尼系數將會減少算法運行時間.以Sigmoid函數為篩選器尋找最優收斂因子, 將其引入該算法提高算法的迭代速度:

（9）

基于穩定閾值的吸引子傳播聚類算法如下：

1) 輸入相似性矩陣S(i,j)；

2) 優化搜索偏向參數, 步長為1, 初始偏向參數是相似性矩陣S(i,j)的中位數；

3) 初始化穩定閾值ST及其相關參數, 迭代更新ST,SF,CF,WSF；

4) 更新矩陣R和矩陣A;

5) 更新吸引度和歸屬度矩陣:

r(i,k)(t+1)=f(net)·λ·r(i,k)(t)+(1-λ)·r(i,k)(t-1),

a(i,k)(t+1)=f(net)·λ·a(i,k)(t)+(1-λ)·a(i,k)(t-1);

6) 更新穩定閾值ST, 達到極限值, 算法結束.

3 仿真模擬實驗與分析

仿真模擬實驗環境為Pentium G645 2.9 GHz CPU, 4 Gb內存.實驗參數是阻尼系數λ=0.5,t=10, 算法評價指標選用Silhouette指標.為了有效驗證本文改進算法的可行性與有效性, 選取高維和低維兩類數據集作為仿真模擬實驗的數據樣本, 實驗數據列于表2.

表2 實驗數據集參數Table 2 Characteristic parameters of experimental data sets

用本文提出的基于穩定閾值吸引子傳播聚類算法進行仿真模擬實驗, 實驗結果列于表3.低維數據中樣本數少的Wine,Iris,Seeds,Harberman數據集, 其算法運行時間差異較小, 而高維Ionosphere數據集算法運行時間卻減少了73.3%； 多樣本數Cmc數據集算法運行時間減少了11%.上述實驗結果表明： 樣本數和維度越大, 算法運行時間越少, 因此本文提出的改進算法能有效提高高維大數據聚類效率.圖2和圖3是采用人工數據集, 分別利用傳統AP算法及本文提出的改進AP算法進行仿真模擬實驗獲得的聚類結果.人工數據集由MATLAB自動生成二項分布隨機數據.對于同一個人工數據集, 采用傳統AP聚類算法獲得的聚類結果為6類, 而本文算法獲得的聚類結果為2類, 改進的AP聚類結果更符合數據的實際空間分布特征, 識別率為100%.因此, 改進的AP聚類算法具有更優的聚類性能.

表3 AP算法和改進AP算法運行時間的比較Table 3 Comparison of time by AP and improved AP algorithms

圖2 改進的AP聚類算法聚類結果Fig.2 Clustering result of improved AP clustering algorithm

圖3 傳統AP聚類算法聚類結果Fig.3 Clustering result of traditional AP clustering algorithm

AP算法和改進AP算法對標準數據集的聚類結果比較列于表4.由表4可見, 與傳統AP算法相比, 改進AP算法 Silhouette值明顯提高, 在Wine,Iris等數據集中, 實現了對偏向參數的優化, 聚類類數均能達到真實類數, 大幅度提高了傳統AP算法的聚類性能.

表4 AP算法和改進AP聚類算法實驗結果比較Table 4 Comparison of experimental results between AP and improved AP clustering algorithms

綜上所述, 傳統吸引子傳播聚類算法具有無法獲取先驗偏向參數, 高維大數據收斂速度慢的弊端.基于穩定閾值的吸引子傳播聚類算法通過穩定閾值的方法, 在類空間捕捉穩定狀態和該狀態下的偏向參數, 達到了優化偏向參數的目的.將Sigmoid函數引入到該算法中作為收斂因子, 可加快算法的單次循環收斂速度.偏向參數優化策略和算法加速方法的結合克服了傳統AP算法存在的弊端.

[1]Napoleon D, Praneesh M, Subramanian M S.Manhattan Distance Based Affinity Propagation Technique for Clustering in Remote Sensing Images [J].International Journal, 2012, 2(3): 327-329.

[2]許曉麗, 盧志茂, 張格森, 等.改進近鄰傳播聚類的彩色圖像分割 [J].計算機輔助設計與圖形學學報, 2012, 24(4)： 514-519.(XU Xiaoli, LU Zhimao, ZHANG Gesen, et al.Color Image Segmentation Based on Improved Affinity Propagation Clustering [J].Journal of Computer-Aided Design & Computer Graphics, 2012, 24(4): 514-519.)

[3]楊傳慧, 吉根林, 章志剛.基于分塊加權顏色直方圖的圖像聚類算法研究 [J].南京師范大學學報: 工程技術版, 2013, 13(1)： 40-44.(YANG Chuanhui, JI Genlin, ZHANG Zhigang.Research on Image Clustering Algorithm Based on Block Weighted Color Histogram [J].Journal of Nanjing Normal University: Engineering and Technology Edition, 2013, 13(1): 40-44.)

[4]孫永宣, 謝昭, 高雋.圖像奇異性檢測的核分類新方法 [J].光學學報, 2013, 33(10)： 1015001.(SUN Yongxuan, XIE Zhao, GAO Jun.A Novel Kernel Classification Method via Image Novelty Detection [J].Acta Optica Sinica, 2013, 33(10): 1015001.)

[5]湯健, 管云雁, 劉文廣, 等.馬氏珠母貝家系遺傳結構的微衛星分析 [J].海洋科學, 2013, 37(8)： 35-41.(TANG Jian, GUAN Yunyan, LIU Wenguang, et al.Microsatellite DNA Analysis of Genetic Structures about 9 Families of Pinctada Fucata [J].Marine Sciences, 2013, 37(8): 35-41.)

[6]文翰, 肖南峰.基于強類別特征近鄰傳播的半監督文本聚類 [J].模式識別與人工智能, 2013, 27(7): 646-654.(WEN Han, XIAO Nanfeng.A Semi-supervised Text Clustering Based on Strong Classification Features Affinity Progation [J].PR & AI, 2013, 27(7): 646-654.)[7]鄭志敏, 徐青.基于仿射傳播算法的城市航空便利性分析 [J].硅谷, 2013(9)： 72-74.(ZHENG Zhimin, XU Qing.Analysis of City Aviation Convenience Based on Affinity Propagation [J].Silicon Valley, 2013(9): 72-74.)

[8]Sakellariou A, Sanoudou D, Spyrou G.Combining Multiple Hypothesis Testing and Affinity Propagation Clustering Leadsto Accurate, Robust and Sample Size Independent Classification on Gene Expression Data [J].BMC Bioinformatics, 2012, 13: 270.

[9]Qasim I, Jeong J W, Heu J U, et al.Concept Map Construction from Text Documents Using Affinity Propagation [J].Journal of Information Science, 2013, 39(6): 719-736.

[10]于吉紅, 白曉明, 呂俊偉.改進相似度的仿射傳播聚類算法 [J].小型微型計算機系統, 2013, 34(3)： 602-605.(YU Jihong, BAI Xiaoming, Lü Junwei.Affinity Propagation Clustering Based on New Similarity [J].Journal of Chinese Computer Systems, 2013, 34(3): 602-605.)

[11]張震, 汪斌強, 李向濤, 等.基于近鄰傳播學習的半監督流量分類方法 [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.)

[12]Sattar F, Driessen P F.Non-stationary Signals Separation Using STFT and Affinity Propagation Clustering Algorithm [C]//2013 IEEE Pacific Rim Conference on Communications, Computers and Signal Processing.Victona, BC: IEEE, 2013: 389-394.

[13]Foster B, Bagci U, Luna B, et al.Robust Segmentation and Accurate Target Definition for Positron Emission Tomography Images Using Affinity Propagation [C]//2013 IEEE 10th International Symposium on Biomedical Imaging (ISBI).San Francisco: IEEE, 2013: 1461-1464.

[14]張震, 汪斌強, 伊鵬, 等.一種分層組合的半監督近鄰傳播聚類算法 [J].電子與信息學報, 2013, 35(3)： 645-651.(ZHANG Zhen, WANG Binqiang, YI Peng, et al.Semi-supervised Affinity Propagation Clustering Algorithm Based on Stratified Combination [J].Journal of Electronics & Information Technology, 2013, 35(3): 645-651.)

[15]王文帥, 陳剛.基于半監督近鄰傳播的數據流聚類算法 [J].計算機工程與應用, 2013, 49(8)： 6-8.(WANG Wenshuai, CHEN Gang.Data Stream Clustering Algorithm Based on Semi-supervised Affinity Propagation [J].Computer Engineering and Applications, 2013, 49(8): 6-8.)

[17]Vannieuwenhoven N, Vandebril R, Meerbergen K.A New Truncation Strategy for the Higher-Order Singular Value Decomposition [J].SIAM Journal on Scientific Computing, 2012, 34(2): A1027-A1052.

[18]Makbol N M, Khoo B E.Robust Blind Image Watermarking Scheme Based on Redundant Discrete Wavelet Transform and Singular Value Decomposition [J].International Journal of Electronics and Communications, 2013, 67(2): 102-112.

[19]Hassanbadi B, Shea C, Zhang L, et al.Clustering in Vehicular and Hoc Networks Using Affinity Propagation [J].Ad Hoc Networks, 2014, 13: 535-548.

[20]Quera V, Beltran F S, Givoni I E, et al.Determing Shoal Membership Using Affinity Propagation [J].Behavioural Brain Research, 2013, 241: 38-49.

StabilityThreshold-BasedAffinityPropagationAlgorithm

WANG Limin1, WANG Yizhang1, HAN Xuming2, HUANG Na3
(1.SchoolofManagementScienceandInformationEngineering,JilinUniversityofFinanceandEconomics,
Changchun130117,China; 2.SchoolofComputerScienceandEngineering,ChangchunUniversityofTechnology,Changchun130012,China; 3.SchoolofInformationManagementandEngineering,
ShanghaiUniversityofFinanceandEconomics,Shanghai200433,China)

In view of the performance of traditional affinity propagation algorithm greatly influenced by parameterP, a novel affinity propagation algorithm based on stability threshold was proposed.The improved algorithm can obtain the convergence of the real class number by stabilizing threshold, and then gain the corresponding parameterP.In order to improve the convergence speed,Sfunction as convergence factor was applied to adjust damp parameter.In addition, it was successfully applied to the field of financial evaluation of listed companies.Simulation experimental results show that the improved clustering algorithm could obtain better precision and quicker convergence, and is obviously better than traditional affinity propagation clustering algorithm.

affinity propagation algorithm; stability threshold; convergence factor

2014-05-13.

王麗敏(1975—), 女, 漢族, 博士, 教授, 從事機器學習、數據挖掘和金融工程的研究, E-mail: wlm_new@163.com.通信作者： 韓旭明(1971—), 男, 漢族, 博士, 副教授, 從事機器學習和數據挖掘的研究, E-mail: hanxvming@163.com.

國家自然科學基金(批準號： 61202306; 61472049; 61402193)、教育部規劃項目(批準號： 13YJAZH130)、吉林省科技廳項目(批準號： 20100507; 201215119; 20130522177JH; 20130101072JC)、吉林省教育廳重點規劃項目(批準號： 2012185; 2012189)、吉林省高校新世紀優秀人才支持計劃項目(批準號： 2014159)和吉林省社會科學基金(批準號： 2014B166).

TP301

A

1671-5489(2014)06-1249-06

10.13413/j.cnki.jdxblxb.2014.06.27

韓 嘯)