基于穩(wěn)定閾值的吸引子傳播算法

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

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

基于穩(wěn)定閾值的吸引子傳播算法

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

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

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

吸引子傳播算法； 穩(wěn)定閾值； 收斂因子

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

1 吸引子傳播聚類算法

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

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

（1）

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

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

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

其中,t為當(dāng)前迭代次數(shù).本文設(shè)當(dāng)類代表點在連續(xù)10次迭代過程中不發(fā)生變化或達到最大迭代次數(shù)時, 算法結(jié)束.

2 STAP算法描述

2.1偏向參數(shù)優(yōu)化技術(shù)

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

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

其中： SN表示樣本數(shù); dim表示維度.

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

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

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

基于穩(wěn)定閾值吸引子傳播聚類算法提出基于穩(wěn)定因子、震蕩因子和弱穩(wěn)定因子的線性函數(shù)作為穩(wěn)定閾值的度量函數(shù).穩(wěn)定因子為聚類重復(fù)度, 震蕩因子為聚類震蕩度, 弱穩(wěn)定因子數(shù)為聚類結(jié)果順序遞減度.引入弱穩(wěn)定因子能更準(zhǔn)確地捕捉震蕩度少的數(shù)據(jù)集類空間的穩(wěn)定狀態(tài).因此穩(wěn)定閾值為

其中： SF為穩(wěn)定因子; CF為震蕩因子; WSF為弱穩(wěn)定因子.

2.2S型收斂因子加速技術(shù)

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

（9）

基于穩(wěn)定閾值的吸引子傳播聚類算法如下：

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

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

3) 初始化穩(wěn)定閾值ST及其相關(guān)參數(shù), 迭代更新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) 更新穩(wěn)定閾值ST, 達到極限值, 算法結(jié)束.

3 仿真模擬實驗與分析

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

表2 實驗數(shù)據(jù)集參數(shù)Table 2 Characteristic parameters of experimental data sets

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

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

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

圖3 傳統(tǒng)AP聚類算法聚類結(jié)果Fig.3 Clustering result of traditional AP clustering algorithm

AP算法和改進AP算法對標(biāo)準(zhǔn)數(shù)據(jù)集的聚類結(jié)果比較列于表4.由表4可見, 與傳統(tǒng)AP算法相比, 改進AP算法 Silhouette值明顯提高, 在Wine,Iris等數(shù)據(jù)集中, 實現(xiàn)了對偏向參數(shù)的優(yōu)化, 聚類類數(shù)均能達到真實類數(shù), 大幅度提高了傳統(tǒng)AP算法的聚類性能.

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

綜上所述, 傳統(tǒng)吸引子傳播聚類算法具有無法獲取先驗偏向參數(shù), 高維大數(shù)據(jù)收斂速度慢的弊端.基于穩(wěn)定閾值的吸引子傳播聚類算法通過穩(wěn)定閾值的方法, 在類空間捕捉穩(wěn)定狀態(tài)和該狀態(tài)下的偏向參數(shù), 達到了優(yōu)化偏向參數(shù)的目的.將Sigmoid函數(shù)引入到該算法中作為收斂因子, 可加快算法的單次循環(huán)收斂速度.偏向參數(shù)優(yōu)化策略和算法加速方法的結(jié)合克服了傳統(tǒng)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].計算機輔助設(shè)計與圖形學(xué)學(xué)報, 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]楊傳慧, 吉根林, 章志剛.基于分塊加權(quán)顏色直方圖的圖像聚類算法研究 [J].南京師范大學(xué)學(xué)報: 工程技術(shù)版, 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].光學(xué)學(xué)報, 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]湯健, 管云雁, 劉文廣, 等.馬氏珠母貝家系遺傳結(jié)構(gòu)的微衛(wèi)星分析 [J].海洋科學(xué), 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]文翰, 肖南峰.基于強類別特征近鄰傳播的半監(jiān)督文本聚類 [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].小型微型計算機系統(tǒng), 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]張震, 汪斌強, 李向濤, 等.基于近鄰傳播學(xué)習(xí)的半監(jiān)督流量分類方法 [J].自動化學(xué)報, 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]張震, 汪斌強, 伊鵬, 等.一種分層組合的半監(jiān)督近鄰傳播聚類算法 [J].電子與信息學(xué)報, 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]王文帥, 陳剛.基于半監(jiān)督近鄰傳播的數(shù)據(jù)流聚類算法 [J].計算機工程與應(yīng)用, 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—), 女, 漢族, 博士, 教授, 從事機器學(xué)習(xí)、數(shù)據(jù)挖掘和金融工程的研究, E-mail: wlm_new@163.com.通信作者： 韓旭明(1971—), 男, 漢族, 博士, 副教授, 從事機器學(xué)習(xí)和數(shù)據(jù)挖掘的研究, E-mail: hanxvming@163.com.

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

TP301

A

1671-5489(2014)06-1249-06

10.13413/j.cnki.jdxblxb.2014.06.27

韓 嘯)