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

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

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

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

1 APC算法

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

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

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

(1)

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

APC算法的流程主要是傳遞吸引度(responsibility)和歸屬度(availability)兩種類型的消息,算法不斷循環(huán)迭代更新這兩種消息。定義R(i,j)為參考點(diǎn)i與候選聚類中心參考點(diǎn)j的吸引度,反映了參考點(diǎn)j適合作為參考點(diǎn)i的聚類中心的程度。定義A(i,j)為參考點(diǎn)i與候選聚類中心參考點(diǎn)j的歸屬度,反映了參考點(diǎn)i選擇參考點(diǎn)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)之和越大代表參考點(diǎn)j作為參考點(diǎn)i的聚類中心的可能性就越大。APC算法通過不斷迭代更新R(i,j)和A(i,j)的值,直到收斂產(chǎn)生若干個(gè)高質(zhì)量的聚類中心,同時(shí)產(chǎn)生了其類別下的類成員。

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

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

2.1 問題描述

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

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

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

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

定義1聚類數(shù)的增長(zhǎng)方向:定義每次迭代中獲取的聚類數(shù)的增長(zhǎng)方向?yàn)閐ir，

dir=Kiter-Kiter-1。

(7)

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

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

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

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

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

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

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

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

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

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

當(dāng)在監(jiān)視窗中檢測(cè)到震蕩因子數(shù)大于0時(shí),此時(shí)可以認(rèn)為可能將要發(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是增長(zhǎng)步幅,本文設(shè)置為0.01。由式(8)可知,lam會(huì)根據(jù)震蕩因子數(shù)的情況,向lam的最大值0.9增長(zhǎng),而當(dāng)震蕩因子數(shù)為0的時(shí)候,就會(huì)停止增長(zhǎng)。此時(shí),APC算法將得到使得震蕩因子數(shù)最小的lam值。而這個(gè)值,可以有效避免震蕩的同時(shí),保持較快的收斂速度。值得注意的是,監(jiān)視窗窗寬W的大小不宜取值過大或者過小,過大會(huì)導(dǎo)致lam增長(zhǎng)過慢,而過小會(huì)導(dǎo)致lam增長(zhǎng)過快,推薦的取值范圍為[5,10]。

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

3.1 實(shí)驗(yàn)數(shù)據(jù)說明

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

表1 實(shí)驗(yàn)數(shù)據(jù)Tab.1 Experimental dataset

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

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

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

圖4 數(shù)據(jù)集未歸一化的各類數(shù)據(jù)集運(yùn)行時(shí)間對(duì)比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ù)集運(yùn)行時(shí)間對(duì)比Fig.5 Comparison of the running time of the normalized dataset

數(shù)據(jù)集未歸一化收斂情況 歸一化后收斂情況 未歸一化運(yùn)行時(shí)間/s 歸一化后運(yùn)行時(shí)間/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è)置一個(gè)監(jiān)視窗不斷監(jiān)視算法的震蕩情況，并統(tǒng)計(jì)監(jiān)視窗內(nèi)的震蕩因子數(shù),通過震蕩因子數(shù)調(diào)節(jié)阻尼因子的值來消除震蕩。消除震蕩后,不再增加阻尼因子的值,使得算法能保持一個(gè)較快的收斂速度。本文的阻尼策略不僅可以有效避免算法震蕩而導(dǎo)致算法難以收斂,而且可以保持一個(gè)較好的收斂速度。最后，通過多個(gè)UCI數(shù)據(jù)集進(jìn)行試驗(yàn),證明了本文算法的有效性。

參考文獻(xiàn)：

[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]. 自動(dòng)化學(xué)報(bào),2014,40(2):277-288.

[6] 張震,汪斌強(qiáng),李向濤,等. 基于近鄰傳播學(xué)習(xí)的半監(jiān)督流量分類方法[J]. 自動(dòng)化學(xué)報(bào),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é)報(bào),2008,19(11): 2803-2813.

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

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

[12] 張震,汪斌強(qiáng),伊鵬,等. 一種分層組合的半監(jiān)督近鄰傳播聚類算法[J]. 電子與信息學(xué)報(bào),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.