基于奇異值分解的自適應(yīng)近鄰傳播聚類算法

王麗敏，姬 強(qiáng)，韓旭明，黃 娜，3

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

基于奇異值分解的自適應(yīng)近鄰傳播聚類算法

王麗敏1，姬 強(qiáng)1，韓旭明2，黃 娜1，3

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

針對近鄰傳播算法無法有效處理高維數(shù)據(jù)而導(dǎo)致聚類效果不佳的問題，提出一種基于奇異值分解的自適應(yīng)近鄰傳播（SVD－SAP）聚類算法.通過引入奇異值分解，對高維數(shù)據(jù)進(jìn)行重構(gòu)、降維，消除冗余信息，并在此基礎(chǔ)上采用非線性函數(shù)策略，自適應(yīng)地調(diào)整阻尼系數(shù)，提高算法的聚類性能.仿真實驗結(jié)果表明，與已有算法相比，該改進(jìn)算法聚類精度更高，收斂速度更快.

近鄰傳播聚類算法；奇異值分解；非線性函數(shù)策略；阻尼系數(shù)

基于歐氏距離的相似性度量方法在處理低維數(shù)據(jù)時具有重要意義，但在高維空間中，由于高維數(shù)據(jù)存在稀疏性和空空間現(xiàn)象，導(dǎo)致歐式距離無法準(zhǔn)確地度量數(shù)據(jù)點間的距離，且算法采用靜態(tài)固定阻尼系數(shù)，無法自適應(yīng)調(diào)節(jié)算法不同階段的搜索性能.為了有效克服上述缺點，本文提出一種基于奇異值分解的自適應(yīng)近鄰傳播聚類算法.一方面對高維數(shù)據(jù)進(jìn)行重構(gòu)、降維，降低信息冗余性；另一方面，在算法的迭代過程中采用非線性函數(shù)策略，自適應(yīng)地調(diào)整阻尼系數(shù)，均衡算法的全局探索和局部搜索能力.仿真實驗結(jié)果表明，本文提出的改進(jìn)算法能有效降低高維數(shù)據(jù)中冗余信息的影響，提高聚類精度，加快收斂速度，提升聚類性能.

1 近鄰傳播聚類算法

近鄰傳播聚類算法不同于其他聚類算法，它是將所有樣本點都作為潛在的聚類中心，通過循環(huán)迭代，每個樣本點競爭聚類中心［1］.其目的是得到最優(yōu)的類代表簇，使類內(nèi)樣本相似度最大，類間樣本相似度最小.

設(shè)樣本數(shù)量為N的樣本空間，任意兩個樣本點xi和xk間的相似度s（i，k）用負(fù)的歐氏距離度量，其值儲存于N×N的相似度矩陣中，數(shù)學(xué)表達(dá)式為

矩陣對角線上的元素為偏向參數(shù)P，近鄰傳播聚類算法初始假設(shè)每個樣本成為類代表點的可能性相同，即設(shè)定所有s（k，k）為相同值P，一般情況P值為相似度矩陣所有值的中位數(shù).P值的大小影響聚類的個數(shù)，增大P值會增加類的數(shù)目，降低P值會減少類的數(shù)目，數(shù)學(xué)公式為

為找到合適的聚類中心xk，不斷地從數(shù)據(jù)樣本中搜集證據(jù)r（i，k）和a（i，k）.r（i，k）表示樣本點xi傳遞給樣本點xk的信息，表示xi選擇xk作為自己聚類中心的支持程度（吸引度）；a（i，k）表示樣本點xk發(fā)送給樣本點xi的信息量，表示xi選擇xk作為其聚類中心的適合程度（歸屬度）；樣本間通過歸屬度和吸引度兩種消息不斷傳遞更新，尋找到最優(yōu)的聚類中心，其過程為

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

其中t表示當(dāng)前迭代次數(shù).當(dāng)類代表點連續(xù)幾步迭代過程中不發(fā)生變化或達(dá)到最大迭代次數(shù)時，近鄰傳播算法結(jié)束.

2 算法描述

2.1 奇異值分解

奇異值分解是一種重要的矩陣分解，在信號處理［14］、圖像去噪［15］、統(tǒng)計學(xué)［16］和數(shù)據(jù)處理［17］等領(lǐng)域應(yīng)用廣泛.奇異值矩陣適用于任意一個矩陣.對于任意一個矩陣A，設(shè)ATA的特征值為λ1≥λ2≥…≥λr≥λr＋1＝…＝λn＝0，則稱σi＝（ i＝1，2，…，r）為矩陣A的奇異值，r為A的秩.存在m階行正交矩陣U和m階列正交矩陣V，使得其中該分解過程即為矩陣A的奇異值分解.

2.2 基于奇異值分解的降維過程

首先，對于一個原始數(shù)據(jù)Am×n，其中m為樣本數(shù)，n為維數(shù)（屬性），在MATLAB中運用函數(shù)（U，S，V）＝svd（A）返回一個與A大小相同的對角矩陣S，兩個正交矩陣U和V，且滿足A＝USVT.其中：U為m×m陣；V為n×n陣.奇異值在S的對角線上，非負(fù)且按降序排列.

其次，根據(jù)求得的S矩陣，選取合適的k個分量，即從矩陣U中選取k個特征向量，記為Ur，矩陣大小為m×k，對于一個n維的向量A，即可降到k維.再利用奇異值分解的逆過程得到原矩陣A的近似矩陣，將矩陣和原矩陣A對應(yīng)的元素加和求平均，即可得到降噪后的數(shù)據(jù)矩陣A′.

對于選取分量個數(shù)k，本文根據(jù)錯失率（error ratio）判定，即錯失率不大于10%即可接受，表示為

本文設(shè)定一個降維自由度矩陣Pn×k，該矩陣是列正交矩陣，則A′m×k＝m×nPn×k即為基于奇異值分解的矩陣降維表示.

2.3 自適應(yīng)動態(tài)阻尼策略

阻尼系數(shù)是近鄰傳播聚類算法的輸入?yún)?shù)，選擇不同的阻尼系數(shù)會對算法的全局搜索和局部搜索能力產(chǎn)生不同的影響，進(jìn)而影響算法的收斂性能.傳統(tǒng)的近鄰傳播聚類算法在迭代過程中，阻尼系數(shù)始終是靜態(tài)固定值，無法動態(tài)地調(diào)節(jié)算法在不同階段的搜索性能.針對上述問題，本文引入非線性函數(shù)策略，提出自適應(yīng)動態(tài)阻尼策略，使該算法在迭代過程中阻尼系數(shù)不再是靜態(tài)固定值，而是自適應(yīng)的動態(tài)改變值，從而更好地提升算法在不同階段的搜索能力.

自適應(yīng)動態(tài)阻尼策略中阻尼系數(shù)動態(tài)改變初始值為λs，最終值為λe，最大迭代次數(shù)為tmax，當(dāng)前迭代次數(shù)為t，函數(shù)策略改變點的迭代次數(shù)為tc，則自適應(yīng)動態(tài)阻尼策略為

本文設(shè)定初始值λs＝0.4，最終值λe＝0.9，tc＝100，當(dāng)0≤t≤tc時，λ∈［0.4，0.9］，策略函數(shù)為凹函數(shù)，因此λ以緩慢的速度增長，可保證算法初期以全局搜索為主，加快收斂速度；當(dāng)tc＜t≤tmax時，λ∈（0.9，1），確保算法后期主要進(jìn)行局部搜索，避免發(fā)生震蕩.

2.4 SVD－SAP算法流程

算法1 SVD－SAP算法.

輸入：數(shù)據(jù)集Tm×n＝｛x1，x2，…，xm｝，相似度矩陣S（i，j），迭代次數(shù)tmax；

輸出：各聚類中心點，Silhouette有效性指標(biāo)，迭代次數(shù)，消耗時間.

1）初始化r（i，k）＝0，a（i，k）＝0；

2）對數(shù)據(jù)矩陣進(jìn)行奇異值分解，用函數(shù)（U，S，V）＝svd（A）返回一個與A大小相同的對角矩陣S；

4）根據(jù)錯失率條件選取分量個數(shù)k，則A′m×k＝m×nPn×k即為基于奇異值分解的矩陣降維表示；

5）利用AP原理，AP中的r（i，k）和a（i，k）按如下規(guī)則更新：

令t＝0，λs＝0.9，λe＝0.5，使用式（9）更新阻尼系數(shù)；

for t＝1to tmax

r（t＋1）（i，k）←（1－λ）r（t＋1）（i，k）＋λr（t）（i，k）／／動態(tài)阻尼系數(shù)更新R

a（t＋1）（i，k）←（1－λ）a（t＋1）（i，k）＋λa（t）（i，k）／／動態(tài)阻尼系數(shù)更新A

t＝t＋1；

結(jié)束.

3 仿真實驗與分析

實驗環(huán)境：處理器為Inter（R）Pentium 2.9GHz，4Gb內(nèi)存，500Gb硬盤，操作系統(tǒng)為Windows XP專業(yè)版，編程語言為MATLAB 2012b.

3.1 實驗數(shù)據(jù)

為了驗證SVD－SAP算法的可行性和有效性，本文選取UCI數(shù)據(jù)集中wine，glass，ecoli和pima數(shù)據(jù)進(jìn)行仿真實驗，并引入對聚類結(jié)構(gòu)有良好評價能力的Silhouette有效性指標(biāo)作為聚類質(zhì)量評價標(biāo)準(zhǔn)對聚類效果進(jìn)行判斷，數(shù)據(jù)信息列于表1.

表1 UCI數(shù)據(jù)集Table 1 Data sets of UCI

3.2 實驗結(jié)果與分析

仿真實驗對AP，K－means和SVD－SAP算法分別在4個數(shù)據(jù)集上進(jìn)行測試，因為已知各數(shù)據(jù)集的分類情況，所以根據(jù)此先驗知識調(diào)節(jié)并確定偏向參數(shù)P，使兩種算法都達(dá)到標(biāo)準(zhǔn)的聚類數(shù)，再比較三者的聚類精度和迭代次數(shù)，實驗結(jié)果分別列于表2和表3.

表2 聚類精度對比Table 2 Comparison of clustering accuracy

表3 迭代次數(shù)對比Table 3 Comparison of the number of iterations

由表2和表3可見，3種算法在聚類類數(shù)都達(dá)到標(biāo)準(zhǔn)聚類的情況下（控制變量的作用），SVD－SAP算法的聚類精度在數(shù)據(jù)集wine和pima上有明顯提高，在迭代次數(shù)上優(yōu)勢更突出，表明改進(jìn)的算法不僅能顯著降低高維數(shù)據(jù)的信息冗余性，提高聚類精度，且在迭代過程中能自適應(yīng)地應(yīng)用動態(tài)阻尼策略，合理地調(diào)節(jié)算法的全局搜索和局部搜索，在不發(fā)生震蕩的前提下，加快收斂速度.如在wine數(shù)據(jù)集上，SVD－SAP算法的迭代次數(shù)僅為傳統(tǒng)近鄰傳播聚類算法的1／10以下，也遠(yuǎn)低于K－means算法.雖然在glass數(shù)據(jù)集上三者的聚類精度相差較小，但在迭代次數(shù)上差距較大，表明基于奇異值分解的自適應(yīng)動態(tài)阻尼策略能對高維數(shù)據(jù)去噪、降維，不僅降低冗余信息的影響、提高聚類質(zhì)量，且在一定程度上改善了聚類的結(jié)構(gòu)和算法搜索方式，提升了算法效率.

綜上所述，本文針對近鄰傳播聚類算法在處理高維數(shù)據(jù)時出現(xiàn)的聚類精度不高、搜索性能低下問題，基于奇異值分解的思想，提出了一種基于奇異值分解的自適應(yīng)近鄰傳播聚類算法.該算法顯著提升了處理高維數(shù)據(jù)的能力，有效降低了冗余信息對聚類過程的影響，提高了聚類質(zhì)量.同時，通過自適應(yīng)動態(tài)地調(diào)節(jié)阻尼系數(shù)，合理改善了算法不同階段的搜索性能，最終實現(xiàn)了在全局搜索和局部搜索上的近似最優(yōu).仿真實驗結(jié)果表明，所提出的改進(jìn)算法具有聚類精度高、收斂速度快等優(yōu)勢.

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

［2］ 唐東明，朱清新，楊凡，等.一種有效的蛋白質(zhì)序列聚類分析方法［J］.軟件學(xué)報，2011，22（8）：1827－1837.（TANG Dongming，ZHU Qingxin，YANG Fan，et al.Efficient Cluster Analysis Method for Protein Sequences［J］.Journal of Software，2011，22（8）：1827－1837.）

［3］ 王駿，王士同，鄧趙紅.特征加權(quán)距離與軟子空間學(xué)習(xí)相結(jié)合的文本聚類新方法 ［J］.計算機(jī)學(xué)報，2012，35（8）：1655－1665.（WANG Jun，WANG Shitong，DENG Zhaohong.A Novel Text Clustering Algorithm Based on Feature Weighting Distance and Soft Subspace Learning［J］.Chinese Journal of Computers，2012，35（8）：1655－1665.）

［4］ Yang C，Bruzzone L，Guan R C，et al.Incremental and Decremental Affinity Propagation for Semi－supervised Clustering in Multispectral Images［J］.IEEE Transactions on Geoscience and Remote Sensing，2013，51（3）：1666－1679.

［5］ Xu B，Hu R，Guo P.Combining Affinity Propagation with Supervised Dictionary Learning for Image Classification［J］.Neural Computing and Applications，2013，22（7／8）：1301－1308.

［6］ 唐東明，朱清新，楊凡，等.基于仿射傳播聚類的大規(guī)模選址布局問題求解［J］.計算機(jī)應(yīng)用研究，2010，27（3）：841－844.（TANG Dongming，ZHU Qingxin，YANG Fan，et al.Solving Large Scale Location Problem Using Affinity Propagation Clustering［J］.Application Research of Computers，2010，27（3）：841－844.）

［7］ Saracli S.Performance of Rand’s Cstatistics in Clustering Analysis：An Application to Clustering the Regions of Turkey［J］.Journal of Inequalities and Applications，2013（1）：1－9.

［8］ 李麗娟，宋坤，趙英凱.基于仿射傳播聚類的ARA發(fā)酵過程建模［J］.化工學(xué)報，2011，62（8）：2116－2121.（LI Lijuan，SONG Kun，ZHAO Yingkai.Modeling of ARA Fermentation Based on Affinity Propagation Clustering［J］.CIESC Journal，2011，62（8）：2116－2121.）

［9］ 王偉濤，王寶善.基于聚類分析的多尺度相似地震快速識別方法及其在汶川地震東北端余震序列分析中的應(yīng)用［J］.地球物理學(xué)報，2012，55（6）：1952－1962.（WANG Weitao，WANG Baoshan.Quick Identification of Multilevel Similar Earthquakes Using Hierarchical Clustering Method and Its Application to Wenchuan Northeast Aftershock Sequence［J］.Chinese J Geophysics，2012，55（6）：1952－1962.）

［10］ Fujiwara Y，Irie G，Kitahara T.Fast Algorithm for Affinity Propagation［C］／／Proceedings of the Twenty－Second International Joint Conference on Artificial Intelligence.Menlo Park，California：AAAI Press，2011：2238－2243.

［11］ Givoni I，Chung C，F(xiàn)rey B J.Hierarchical Affinity Propagation［J／OL］.2012.http：／／arxiv.org／ftp／arxiv／papers／1202／1202.3722.pdf.

［12］ 馮曉磊，于洪濤.基于流形距離的半監(jiān)督近鄰傳播聚類算法［J］.計算機(jī)應(yīng)用研究，2011，28（10）：3656－3658.（FENG Xiaolei，YU Hongtao.Semi－supervised Affinity Propagation Clustering Based on Manifold Distance［J］.Application Research of Computers，2011，28（10）：3656－3658.）

［13］ 王羨慧，覃征，張選平，等.采用仿射傳播的聚類集成算法 ［J］.西安交通大學(xué)學(xué)報，2011，45（8）：1－6.（WANG Xianhui，QIN Zheng，ZHANG Xuanping，et al.Cluster Ensemble Algorithm Using Affinity Propagation［J］.Journal of Xi’an Jiaotong University，2011，45（8）：1－6.）

［14］ Capozzoli A，Curcio C，Liseno A，et al.Multi－frequency Planar Near－Field Scanning by Means of Singular－Value Decomposition（SVD）Optimization［J］.IEEE Antennas ＆Amp，2011，53（6）：212－221.

［15］ Ajit R，Anand R，Arunava B，et al.Image Denoising Using the Higher Order Singular Value Decomposition［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2013，35（4）：849－862.

［16］ Vannieuwenhoven N，Vandebril R，Meerbergen K，et al.A New Truncation Strategy for the Higher－Order Singular Value Decomposition［J］.SIAM Journal on Scientific Computing，2012，34（2）：A10271052.

［17］ Makbol N M，Khoo B E.Robust Blind Image Watermarking Scheme Based on Redundant Discrete Wavelet Transform and Singular Value Decomposition［J］.AEU：International Journal of Electronics and Communications，2013，67（2）：102－112.

（責(zé)任編輯：韓 嘯）

WANG Limin1，JI Qiang1，HAN Xuming2，HUANG Na1，3
（1.School of Management Science and Information Engineering，Jilin University of Finance and Economics，Changchun130117，China；2.School of Software，Changchun University of Technology，Changchun130012，China；3.School of Information Management and Engineering，Shanghai University of Finance and Economics，Shanghai 200433，China）

Aiming at the problem that affinity propagation algorithm has a difficult to deal with highdimensional data，the authors put forward an selfdaptive affinity propagation algorithm based on singular value decomposition.With the aid of singular value decomposition introdued，the highdimensional data were reconstructed and dimensions were reduced to eliminate the redundant information，based on which，a nonlinear function strategy was adopted to adjust the damping factor adaptively and improve the clustering performance of the algorithm.Experimental results show that the proposed algorithm has obviously better clustering performance than the traditional algorithm on clustering accuracy and the number of iterations.

affinity propagation clustering algorithm；singular value decomposition；nonlinear function strategy；dampingfactor

TP301

A

1671－5489（2014）04－0753－05

近鄰傳播（affinity propagation，AP）是一種基于歐式距離為相似度的快速、有效聚類算法.近鄰傳播聚類算法的優(yōu)點是不需要事先確定聚類個數(shù)，而將所有樣本點作為潛在的類代表點，并通過不斷迭代得到最優(yōu)的聚類中心［1］，因此，被廣泛應(yīng)用于基因序列［2］、文本聚類［3］、圖像處理［4－5］和設(shè)施選址［6］等領(lǐng)域［7－9］.目前，關(guān)于該算法及相應(yīng)的改進(jìn)算法已有許多研究結(jié)果，如Fujiwara等［10］通過在算法迭代過程中刪減不必要的信息交換，在不損失聚類結(jié)果準(zhǔn)確率的基礎(chǔ)上，大幅度提升算法的收斂速度，提出一種快速高效的近鄰傳播聚類算法；Givoni等［11］將近鄰傳播算法與層次聚類相結(jié)合，提出一種分層近鄰傳播聚類算法，并應(yīng)用于真實的HIV基因序列數(shù)據(jù)，取得較好效果；馮曉磊等［12］通過引入流形學(xué)習(xí)的思想，提出一種基于流形距離的半監(jiān)督近鄰傳播聚類算法，更準(zhǔn)確地反映數(shù)據(jù)的潛在結(jié)構(gòu)，提高算法的聚類性能；王羨慧等［13］將近鄰傳播聚類算法與K均值算法相結(jié)合，提出一種基于近鄰傳播的聚類集成算法，有效地提高了K均值聚類的準(zhǔn)確性、魯棒性和穩(wěn)定性.

10.13413／j.cnki.jdxblxb.2014.04.23

2014－05－13.

王麗敏（1975—），女，漢族，博士，教授，從事機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘和金融工程的研究，E－mail：wlm＿new＠163.com.通信作者：韓旭明（1971—），男，漢族，博士，副教授，從事機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘的研究，E－mail：hanxvming＠163.com.

國家自然科學(xué)基金（批準(zhǔn)號：61202306）、吉林省科技廳項目（批準(zhǔn)號：20100507；201215119；20130522177JH）、吉林省教育廳重點規(guī)劃項目（批準(zhǔn)號：2012185）、吉林省高校新世紀(jì)優(yōu)秀人才支持計劃項目（批準(zhǔn)號：2014159）和吉林財經(jīng)大學(xué)青年學(xué)俊支持計劃項目.