胡久松,劉宏立,顏 志,徐 琨

(湖南大學(xué) 電氣與信息工程學(xué)院,湖南 長沙 410082)

仿射傳播聚類算法(Affinity propagation clustering, APC)是Frey等人在science上提出的通過數(shù)據(jù)點之間相互傳播消息來確定聚類的新方法[1-2]，文獻[3]公開了其源碼。由于APC算法可以在短時間內(nèi)獲得更低的誤差聚類結(jié)果、不依賴于初值的選取、不需要相似矩陣必須對稱等優(yōu)點,已被廣泛應(yīng)用于眾多領(lǐng)域,例如文獻[2]將其應(yīng)用于圖像處理、基因識別和路線規(guī)劃;文獻[4]將其應(yīng)用于文本聚類;文獻[5-7]將其應(yīng)用于數(shù)據(jù)流分類;文獻[8]將其應(yīng)用于室內(nèi)定位中等。許多文獻針對算法收斂速度和準確率方面,在仿射傳播算法應(yīng)用中進行了改進研究。文獻[9]通過數(shù)據(jù)的約束對等先驗知識調(diào)整相似度矩陣來提高APC聚類算法的性能。文獻[10]通過采用可變度量來改善相似性矩陣,以此提高APC算法處理多種數(shù)據(jù)的能力。文獻[11]將MapReduce與APC算法結(jié)合,加速了APC算法的收斂速度。文獻[12]將分層聚類的思想引入APC聚類的過程中,提升了算法的準確性和收斂速度。文獻[13]設(shè)計了一種新的聚類有效性指標來確定APC算法的最優(yōu)聚類數(shù)。

這些研究的基礎(chǔ)是建立在公開APC源碼的基礎(chǔ)上的，在公開源碼中,阻尼因子是APC算法的一個重要參數(shù)，算法的收斂問題主要通過調(diào)整阻尼因子的值解決。在公開源碼中,采用的是固定阻尼策略，若將阻尼因子設(shè)置成一個較小的值(0.5),則有可能導(dǎo)致算法因發(fā)生震蕩而難以收斂。因此,通常通過將阻尼因子設(shè)置為一個較大的值(0.9)的策略來有效避免震蕩,但是這樣會減慢算法的收斂速度。本文所提算法通過設(shè)置一個監(jiān)視窗,不斷監(jiān)視算法的震蕩情況，根據(jù)算法的震蕩情況自適應(yīng)調(diào)整阻尼因子的值。當算法發(fā)生震蕩時,以一定的步幅不斷增加阻尼因子的值以消除震蕩；當算法不再震蕩時,就不再增加阻尼因子的值以保證算法的收斂速度。這種策略相比公開源碼中的固定阻尼策略,不僅可以有效避免震蕩,而且可以很大程度地保持阻尼因子較小時的收斂速度。試驗數(shù)據(jù)來源于公開的UCI數(shù)據(jù)集[14],代碼在公開源碼的基礎(chǔ)上進行的修改,因此可以再驗證。通過多個UCI公開數(shù)據(jù)集試驗證明了所提算法的有效性。

1 APC算法

定義L維的數(shù)據(jù)集X={x1,x2,…,xM},其中M表示數(shù)據(jù)樣本個數(shù),xi={xi,1,xi,2,…,xi,L}(i∈{1,2,…,M})表示數(shù)據(jù)的行向量。則任意兩個參考點之間的相似度為

sim(i,j)=-‖xi-xj‖2,

?i,j={1,2,…,M},i≠j。

(1)

其中，用對角線上的數(shù)值sim(i,i)不使用式(1)計算。它的值用來表示參考度p,其值越大，代表其成為聚類中心的可能性就越大。通常作法是將p取一個相同的固定值(一般取sim(i,i)的中值),即將所有的數(shù)據(jù)成員都看作潛在的聚類中心。

APC算法的流程主要是傳遞吸引度(responsibility)和歸屬度(availability)兩種類型的消息,算法不斷循環(huán)迭代更新這兩種消息。定義R(i,j)為參考點i與候選聚類中心參考點j的吸引度,反映了參考點j適合作為參考點i的聚類中心的程度。定義A(i,j)為參考點i與候選聚類中心參考點j的歸屬度,反映了參考點i選擇參考點j作為聚類中心的合適程度。A的初始值設(shè)為零，R的初始值設(shè)為sim(i,j)。R(i,j)通過式(2)和式(3)更新:

sim(i,j′)}，

(2)

Riter=(1-lam)×Riter+lam×Riter-1。

(3)

其中，Riter表示本次迭代中吸引度的值,Riter-1表示上一次迭代中吸引度的值。lam表示阻尼因子。

A(i,j)通過式(4)更新，

A(i,j)=min{0,R(j,j)+

(4)

Aiter=(1-lam)×Aiter+lam×Aiter-1。

(5)

其中

(6)

R(i,j)和A(i,j)之和越大代表參考點j作為參考點i的聚類中心的可能性就越大。APC算法通過不斷迭代更新R(i,j)和A(i,j)的值,直到收斂產(chǎn)生若干個高質(zhì)量的聚類中心,同時產(chǎn)生了其類別下的類成員。

（4）加強對招投標代理機構(gòu)的管理。強化招標代理機構(gòu)的法律責(zé)任和自律意識，制定招標代理機構(gòu)行為規(guī)范和紀律規(guī)定。招標代理機構(gòu)在招標投標活動中處于非常重要的地位，在行使其代理權(quán)時，要嚴格遵循法律和行為規(guī)范，不得超越。對招標代理機構(gòu)違反法律規(guī)定進行招標代理，損害招標人或投標人合法權(quán)益的，應(yīng)視其違法性質(zhì)和情節(jié)，采取經(jīng)濟處罰，取消資格，直至追究刑事責(zé)任。

2 自適應(yīng)阻尼因子的APC算法

2.1 問題描述

APC算法的收斂特性是個開放性難題[15]。文獻[2]通過在相似度加入少量的噪聲和引入阻尼因子(lam)試圖解決APC的震蕩問題,但文獻[16]的研究表明，加入微小數(shù)量的噪音到相似度矩陣不是必須的,因此，如何保證APC算法收斂主要依賴于lam的選擇。lam的建議取值范圍是[0.5,0.9][2]。

APC算法是一個搜索能量函數(shù)最小值的方法。lam越小,APC算法的全局搜索能力就越強,數(shù)據(jù)點之間的消息更新速度也就更快,因此可以更快地找到能量函數(shù)最小值,但可能會導(dǎo)致算法發(fā)生震蕩,拖慢收斂速度,甚至使得算法難以收斂;反之,lam取值越大,APC算法的局部搜索能力就越強,可以很大可能地避免震蕩,但同時使得數(shù)據(jù)點之間的消息更新速度變慢而降低收斂速度。因此,一個較好的方式就是在有效避免震蕩的情況下,取一個較小的阻尼因子的值,才能保證算法有一個較好的收斂速度。

2.2 對發(fā)生震蕩可能性的檢測

要有效避免震蕩,就需要提前檢測到發(fā)生震蕩的可能性,并及時采取避免震蕩的措施。因此，及時檢測到發(fā)生震蕩的可能性是非常重要的。文獻[16]給出了APC算法發(fā)生震蕩的公式,但仍然指出APC算法的收斂問題是個開放性的難題,因此很難去證明在什么條件下,APC算法一定收斂而不會發(fā)生震蕩。盡管很難找到完全避免震蕩的方法,但通過檢測發(fā)生震蕩的可能性并預(yù)防震蕩的方式，盡可能地避免震蕩是可行的。為了描述震蕩的特征并檢測發(fā)生震蕩的可能性,本文提出了以下定義。

定義1聚類數(shù)的增長方向:定義每次迭代中獲取的聚類數(shù)的增長方向為dir，

dir=Kiter-Kiter-1。

(7)

其中，Kiter和Kiter-1表示本次迭代和上一次迭代中獲取到的聚類數(shù)。

定義2震蕩因子:當每次迭代中獲取的聚類數(shù)的增長方向沒有朝向目標聚類數(shù)時,稱之為出現(xiàn)了一次震蕩因子。在APC算法中,每次迭代中獲取的聚類數(shù)應(yīng)不斷下降，最終收斂到一個穩(wěn)定的聚類結(jié)果。因此，當dir>0時,可以判定為出現(xiàn)了一次震蕩因子，出現(xiàn)震蕩因子說明算法有了發(fā)生震蕩的可能性。

震蕩因子和震蕩因子數(shù)可以用于檢測和描述震蕩的特征。震蕩的可能方式可以分為以下3種:

1) 有限的震蕩,即震蕩因子出現(xiàn)的次數(shù)是有限的,表現(xiàn)為震蕩因子數(shù)會最終趨向為0，并一直為0。例如在APC算法起初階段,都有可能發(fā)生有限的震蕩。這種有限的震蕩并不會造成算法的不收斂。

2) 周期性的震蕩,即震蕩因子出現(xiàn)的次數(shù)呈現(xiàn)周期性,表現(xiàn)為震蕩因子數(shù)也呈現(xiàn)周期性。這種震蕩會導(dǎo)致算法難以收斂。

3) 非周期性的無限震蕩,即震蕩因子出現(xiàn)的次數(shù)不呈現(xiàn)周期性,但會無限地出現(xiàn)。這種震蕩也會導(dǎo)致算法難以收斂。

對3種震蕩情況都要提前檢測出發(fā)生震蕩的可能性,可以通過震蕩因子數(shù)是否大于0來進行判斷。因此本文采取的檢測發(fā)生震蕩的可能性的方式為判斷震蕩因子數(shù)是否大于0。當檢測到發(fā)生震蕩的可能性時,通過自適應(yīng)調(diào)整阻尼因子的值來避免震蕩。

2.3 自適應(yīng)阻尼因子

根據(jù)前文的描述,如何合理地自適應(yīng)調(diào)整lam的值是本文論述的重點。lam值較小會導(dǎo)致震蕩問題,而lam較大會導(dǎo)致數(shù)據(jù)點間的消息速度更新過慢,那么一個合理的方法就是,根據(jù)震蕩因子數(shù)來調(diào)節(jié)lam的值,使得lam停留在一個使得震蕩因子數(shù)為0的最小的lam值上。圖1給出了自適應(yīng)阻尼因子的APC算法流程。

圖1 自適應(yīng)阻尼因子的APC算法流程Fig.1 The APC algorithm flow with adaptive damping factor

當在監(jiān)視窗中檢測到震蕩因子數(shù)大于0時,此時可以認為可能將要發(fā)生震蕩,因此需要調(diào)節(jié)lam的值。較為合理的方式就是采用震蕩因子數(shù)來調(diào)節(jié)lam的值,使得lam逐漸調(diào)節(jié)到震蕩因子數(shù)為0為止。使用震蕩因子數(shù)調(diào)節(jié)lam的方式為

lam=lam+step*c,lam∈[0.5,0.9]。

(8)

其中，step是增長步幅,本文設(shè)置為0.01。由式(8)可知,lam會根據(jù)震蕩因子數(shù)的情況,向lam的最大值0.9增長,而當震蕩因子數(shù)為0的時候,就會停止增長。此時,APC算法將得到使得震蕩因子數(shù)最小的lam值。而這個值,可以有效避免震蕩的同時,保持較快的收斂速度。值得注意的是,監(jiān)視窗窗寬W的大小不宜取值過大或者過小,過大會導(dǎo)致lam增長過慢,而過小會導(dǎo)致lam增長過快,推薦的取值范圍為[5,10]。

3 試驗結(jié)果和分析

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

試驗數(shù)據(jù)采用的是UCI的11個標準數(shù)據(jù)集[14],表1列出了數(shù)據(jù)集的相關(guān)信息。為了證明本文算法的有效性,對不同的阻尼策略分別在收斂性、運行時間等方面進行了對比,以證明本文阻尼策略的優(yōu)勢。

表1 實驗數(shù)據(jù)Tab.1 Experimental dataset

表2列出了算法運行的參數(shù)和運行環(huán)境。為了不讓迭代次數(shù)影響算法,設(shè)置最大迭代次數(shù)為100 000；噪聲“noise”設(shè)置為“′nonoise′”,即不加入噪聲；其他參數(shù)值采用APC算法源碼的默認參數(shù)。程序均運行在同一臺臺式電腦上。

表2 算法運行的參數(shù)和運行環(huán)境

Tab.2 The parameters and runtime environment of the algo-rithm

參數(shù)值 maxits100 000 noise'nonoise' CPUIntel core i5-3470 3.20GHz 內(nèi)存4GB 系統(tǒng)Win10 64bit

3.2 自適應(yīng)阻尼因子的APC算法

在本文選取的11個UCI數(shù)據(jù)集中,采取未處理過的數(shù)據(jù)進行試驗時,并未發(fā)現(xiàn)APC算法因為震蕩而不收斂的情況,但是當將數(shù)據(jù)集進行歸一化處理后,air和zoo數(shù)據(jù)集中出現(xiàn)了算法震蕩且難以收斂。圖 2和圖 3分別是未歸一化和歸一化處理后的air數(shù)據(jù)集采用公開源碼固定阻尼策略0.5和0.9，以及本文阻尼策略的聚類數(shù)變化結(jié)果。從圖 2可知，lam越小，數(shù)據(jù)點之間的消息更新速度就越快，獲取到的聚類數(shù)變化就越大，引起震蕩的可能性就越大。lam越大，數(shù)據(jù)點之間的消息更新速度就越慢，獲取到的聚類數(shù)變化相對較穩(wěn)定，因此引起震蕩的可能性就很低，但導(dǎo)致的問題是， 由于數(shù)據(jù)點之間消息更新速度緩慢， 因此需要更多的迭代次數(shù)才能收斂。 圖3歸一化的air數(shù)據(jù)集的聚類數(shù)變化結(jié)果中表明， 阻尼因子0.5的情況就導(dǎo)致了算法的無限震蕩而使得算法無法收斂。圖2和圖 3都表明了本文的阻尼策略，起初階段同阻尼因子0.5的情況，聚類數(shù)變化較快，但隨著檢測到震蕩，通過增加阻尼因子的值，使得聚類數(shù)變化逐漸趨于平穩(wěn)，最后當算法不再震蕩時，則停止增長，保持當前收斂速度。圖 4和圖 5給出了所有數(shù)據(jù)集未歸一化和歸一化后的收斂情況和運行時間，表 3給出了具體的數(shù)據(jù)情況。從圖4可以看出，自適應(yīng)阻尼策略保持了與固定阻尼值0.5差不多和大于固定阻尼值0.9的收斂速度。從圖5可以看出，阻尼值0.5引發(fā)了部分歸一化后的數(shù)據(jù)集的震蕩而使得算法難以收斂,而自適應(yīng)阻尼策略在可以避免震蕩的同時,還能保持較好的收斂速度。通過圖4和圖5的對比分析，進一步證明了本文阻尼策略的優(yōu)勢。

圖2 未歸一化的air數(shù)據(jù)集的聚類數(shù)變化結(jié)果Fig.2 The changes of cluster number of no-normalized air dataset

圖4 數(shù)據(jù)集未歸一化的各類數(shù)據(jù)集運行時間對比Fig.4 Comparison of the running time of no-normalized dataset

圖3 歸一化的air數(shù)據(jù)集的聚類數(shù)變化結(jié)果Fig.3 The changes of cluster number of normalized air dataset

圖5 數(shù)據(jù)集歸一化后的各數(shù)據(jù)集運行時間對比Fig.5 Comparison of the running time of the normalized dataset

數(shù)據(jù)集未歸一化收斂情況 歸一化后收斂情況 未歸一化運行時間/s 歸一化后運行時間/s 0.50.9自適應(yīng)0.50.9自適應(yīng)0.50.9自適應(yīng)0.50.9自適應(yīng) iris0.10.20.10.10.20.2 air×0.72.50.7×2.41.5 sonar0.20.40.20.20.40.2 glass0.31.00.30.31.10.4 wine0.30.20.20.20.30.2 heart0.30.60.30.30.60.3 zoo×0.20.20.2×0.30.2 ionosphere0.60.60.50.40.60.5 vote2.02.41.22.22.61.4 vowel1.02.00.91.02.31.0 diabetes2.02.41.81.74.21.8

4 結(jié) 論

本文提出了一種自適應(yīng)阻尼因子的APC算法。通過設(shè)置一個監(jiān)視窗不斷監(jiān)視算法的震蕩情況，并統(tǒng)計監(jiān)視窗內(nèi)的震蕩因子數(shù),通過震蕩因子數(shù)調(diào)節(jié)阻尼因子的值來消除震蕩。消除震蕩后,不再增加阻尼因子的值,使得算法能保持一個較快的收斂速度。本文的阻尼策略不僅可以有效避免算法震蕩而導(dǎo)致算法難以收斂,而且可以保持一個較好的收斂速度。最后，通過多個UCI數(shù)據(jù)集進行試驗,證明了本文算法的有效性。

參考文獻：

[1] FREY B J, DUECK D. Response to comment on "clustering by passing messages between data points"[J].Science，2008, 319(5864): 726.

[2] FREY B J, DUECK D. Clustering by passing messages between data points [J]. Science, 2007, 315(5814):972.

[3] Frey Lab Probabilistic and Statistical Inference Group. Affinity Propagation (University of Toronto)[EB/OL].[2017-03-10].http:∥www.psi.toronto.edu/index.php?q=affinity%20propagation.

[4] GUAN R, SHI X, MARCHESE M, et al. Text clustering with seeds affinity propagation[J]. IEEE Transactions on Knowledge and Data Engineering. 2011, 23(4): 627-637.

[5] 張建朋,陳福才,李邵梅,等. 基于密度與近鄰傳播的數(shù)據(jù)流聚類算法[J]. 自動化學(xué)報,2014,40(2):277-288.

[6] 張震,汪斌強,李向濤,等. 基于近鄰傳播學(xué)習(xí)的半監(jiān)督流量分類方法[J]. 自動化學(xué)報,2013,39(7): 1100-1109.

[7] ZHANG X, FURTLEHNER C, GERMAIN-RENAUD C, et al. Data stream clustering with affinity propagation[J].IEEE Transactions on Knowledge and Data Engineering, 2014, 26(7): 1644-1656.

[8] FENG C, AU W S A, VALAEE S, et al. Received-signal-strength-based indoor positioning using compressive sensing[J]. IEEE Transactions on Mobile Computing,2012, 11(12): 1983-1993.

[9] 肖宇,于劍. 基于近鄰傳播算法的半監(jiān)督聚類[J]. 軟件學(xué)報,2008,19(11): 2803-2813.

[10] 董俊,王鎖萍,熊范綸. 可變相似性度量的近鄰傳播聚類[J]. 電子與信息學(xué)報,2010,32(3):509-514.

[11] 魯偉明,杜晨陽,魏寶剛,等. 基于MapReduce的分布式近鄰傳播聚類算法[J]. 計算機研究與發(fā)展,2012,49(8):1762-1772.

[12] 張震,汪斌強,伊鵬,等. 一種分層組合的半監(jiān)督近鄰傳播聚類算法[J]. 電子與信息學(xué)報,2013,35(3):645-651.

[13] 周世兵, 徐振源, 唐旭清. 一種基于近鄰傳播算法的最佳聚類數(shù)確定方法[J]. 控制與決策, 2011, 26(8):1147-1152.

[14] BLAKE C L, MERZ C J. UCI repository of machine learning databases (University of California) [EB/OL].[2017-02-20].http:∥archive.ics.uci.edu/ml/.

[15] MéZARD M. Where are the exemplars? [J]. Science，2007,315(5814):949-951.

[16] YU J, JIA C. Convergence analysis of affinity propagation[J]. Ksem, 2009,5914:54-65.