自適應(yīng)屬性加權(quán)近鄰傳播聚類算法

李海林，魏 苗

(1.華僑大學(xué)信息管理系 福建 泉州 362021；2.華僑大學(xué)現(xiàn)代應(yīng)用統(tǒng)計(jì)與大數(shù)據(jù)研究中心 福建 廈門 361021)

聚類分析是數(shù)據(jù)挖掘領(lǐng)域中較為基礎(chǔ)的數(shù)據(jù)處理手段，通過聚類算法對數(shù)據(jù)分類能夠?qū)⒁粋€數(shù)據(jù)集劃分為若干個類內(nèi)對象盡可能相似而類間數(shù)據(jù)對象相異的類簇[1]，從而在數(shù)據(jù)集中發(fā)現(xiàn)潛在的數(shù)據(jù)模式與內(nèi)在聯(lián)系[2]。由于數(shù)據(jù)分類應(yīng)用的廣泛性，聚類分析在多個領(lǐng)域扮演著重要角色，如：統(tǒng)計(jì)數(shù)學(xué)[3]、模式識別[4]、社交網(wǎng)絡(luò)[5]、天文學(xué)[6]、電氣電子學(xué)[7]和生物科學(xué)[8]等。

在眾多聚類算法中，文獻(xiàn)[9]提出的近鄰傳播聚類(affinity propagation, AP)不僅有效地解決了傳統(tǒng)K-Means聚類算法中初始聚類中心的選擇對聚類結(jié)果產(chǎn)生影響的問題，而且不需要提前設(shè)定聚類的類簇?cái)?shù)目。它在聚類過程中將每個數(shù)據(jù)對象視為潛在的數(shù)據(jù)代表點(diǎn)，通過在數(shù)據(jù)之間傳播兩種競爭信息，即代表度與有效性，最終獲得較為穩(wěn)定的聚類結(jié)果。近鄰傳播聚類算法自提出以來，不少學(xué)者對它進(jìn)行了研究并提出改進(jìn)方法，如文獻(xiàn)[10]提出一種可變相似性度量的近鄰傳播聚類，通過改進(jìn)近鄰傳播聚類中的相似性度量方法，拓展了近鄰傳播的應(yīng)用領(lǐng)域，并提升了近鄰傳播算法的性能。文獻(xiàn)[11]提出一種用于社區(qū)發(fā)現(xiàn)的基于近鄰傳播的多目標(biāo)演化算法，該算法通過結(jié)合近鄰傳播與演化算法，有效提升了社區(qū)發(fā)現(xiàn)的準(zhǔn)確率與效率。通常情況下，多數(shù)學(xué)者在進(jìn)行聚類分析研究時，將數(shù)據(jù)的所有屬性視為同等重要，即每個屬性在算法設(shè)計(jì)時都設(shè)為相同的權(quán)值[12]，沒有考慮因數(shù)據(jù)屬性權(quán)重不相等對數(shù)據(jù)挖掘分析結(jié)果的影響。如在醫(yī)學(xué)檢查記錄中，針對不同的疾病診斷，人們往往關(guān)注的是不同病歷指標(biāo)屬性的數(shù)值結(jié)果，存在指標(biāo)屬性重要程度的差異性問題。也有研究[13]表明，有意義的聚類模式和結(jié)果通常會出現(xiàn)在某幾個特定屬性組成的數(shù)據(jù)中，而不是所有屬性。由于屬性的重要性不相等，在聚類過程中提高較有實(shí)際意義的屬性權(quán)值，削減不重要屬性對聚類結(jié)果的影響，使得基于權(quán)重屬性分析的聚類算法能夠提高分類結(jié)果的質(zhì)量。部分學(xué)者在這方面做了相關(guān)研究[14-16]，并提出了更具有挖掘效果的聚類分析方法[15,17-18]。然而，這些方法因使用了K-Means聚類從而易受初始聚類中心選擇的影響，造成基于加權(quán)屬性的K-Means聚類方法不穩(wěn)定、聚類結(jié)果不準(zhǔn)確。

針對數(shù)據(jù)屬性的重要程度存在相異性和經(jīng)典聚類算法的加權(quán)改進(jìn)，如加權(quán)K-means算法的聚類結(jié)果存在不穩(wěn)定性的問題，本文提出一種自適應(yīng)數(shù)據(jù)屬性加權(quán)的近鄰傳播聚類算法(adaptive feature weight algorithm based on affinity propagation, AFW_AP)。該方法在傳統(tǒng)近鄰傳播聚類的過程中通過相似性矩陣考慮數(shù)據(jù)屬性權(quán)重的影響，根據(jù)每次迭代聚類結(jié)果的目標(biāo)評價函數(shù)來自適應(yīng)確定數(shù)據(jù)屬性的權(quán)值，動態(tài)更新近鄰傳播算法中的兩種競爭信息，進(jìn)而提升近鄰傳播聚類算法的效果。通過在傳統(tǒng)近鄰傳播聚類算法中加入屬性權(quán)值的計(jì)算，在提高近鄰傳播聚類質(zhì)量的同時，還繼承了近鄰傳播不受初始聚類中心影響的特點(diǎn)，使得聚類結(jié)果具有較好的穩(wěn)定性。數(shù)值實(shí)驗(yàn)結(jié)果表明，與其他聚類算法相比，新方法AFW_AP具有更好的數(shù)據(jù)聚類分析效果。

1 近鄰傳播聚類

AP是一種高效的基于圖論的聚類方法，以數(shù)據(jù)間的相似性矩陣為聚類基礎(chǔ)，在每次迭代過程中不斷在數(shù)據(jù)間交換兩種競爭信息：代表度(responsibility)和有效性(availability)，直到產(chǎn)生一個收斂的聚類結(jié)果為止。與K-Means聚類不同，近鄰傳播聚類不需要限定聚類簇?cái)?shù)，并且不進(jìn)行初始聚類代表點(diǎn)的選擇，它在聚類過程中將數(shù)據(jù)集中的每個數(shù)據(jù)對象都作為潛在的數(shù)據(jù)代表點(diǎn)。由于近鄰傳播不需要初始化聚類代表點(diǎn)，它所產(chǎn)生的聚類結(jié)果較K-Means聚類更加穩(wěn)定。

近鄰傳播算法中的任意兩個數(shù)據(jù)對象之間的相似性定義為兩點(diǎn)間距離平方的負(fù)數(shù)。例如，數(shù)據(jù)點(diǎn)xi和數(shù)據(jù)點(diǎn)xj的相似性表示為特別的，在相似性矩陣中，s(i,i)的值被稱為偏向參數(shù)(preferences)。偏向參數(shù)的選擇會影響聚類結(jié)果中的類簇?cái)?shù)目，偏向參數(shù)的取值為相似性矩陣中的元素最小值時能產(chǎn)生類簇較少的聚類結(jié)果，偏向參數(shù)取相似性矩陣中的最大值時會產(chǎn)生類簇?cái)?shù)目較多的聚類結(jié)果[19]。一般情況下取相似性矩陣的中位數(shù)作為偏向參數(shù)的值。

在近鄰傳播聚類算法的迭代過程中，代表度和有效性兩種信息的計(jì)算目的是在數(shù)據(jù)之間不斷傳遞以產(chǎn)生勝出的代表點(diǎn)。代表度r(i,j)是從數(shù)據(jù)點(diǎn)xi傳到候選代表點(diǎn)xj的信息，反映點(diǎn)xj對點(diǎn)xi的代表程度。有效性a(i,j)是從代表點(diǎn)xj傳遞到數(shù)據(jù)點(diǎn)xi的信息，反映點(diǎn)xj作為點(diǎn)xi的代表點(diǎn)的有效程度。代表度和有效性的更新為：

代表度和有效性在聚類過程中不斷迭代更新，直到產(chǎn)生一個收斂的聚類結(jié)果為止。其中，為了避免近鄰傳播在聚類過程中發(fā)生數(shù)據(jù)震蕩，在迭代過程引入阻尼因子λ，使得每次迭代的值都為上一次迭代舊值和當(dāng)前迭代新值的加權(quán)計(jì)算結(jié)果。λ的取值能夠影響近鄰傳播的迭代次數(shù)，當(dāng)λ較小時，迭代次數(shù)較少；若λ較大，迭代次數(shù)也會增加。研究[20]表明當(dāng)λ的取值區(qū)間為(0.5,1)時能夠明顯增強(qiáng)算法的穩(wěn)定性。為了減少數(shù)據(jù)震蕩的幾率，本文將λ的取值設(shè)為0.9。另外，在近鄰傳播算法的任意迭代階段，可以通過式(4)利用代表度矩陣R和有效性矩陣A得出聚類結(jié)果，即每個數(shù)據(jù)對象選擇代表度與有效性之和最大的數(shù)據(jù)點(diǎn)作為自身的聚類代表點(diǎn)：

式中，a(i,j)為矩陣中A的元素；r(i,j)為矩陣R的元素。近鄰傳播算法通過在聚類過程中對兩種傳播信息的更新計(jì)算得出聚類結(jié)果，無需初始化聚類中心，并且不用指定聚類結(jié)果中類簇的數(shù)目，算法易用性較強(qiáng)。然而，大多數(shù)對近鄰傳播算法的研究缺少考慮在聚類過程中屬性權(quán)值的影響，因此在對高維數(shù)據(jù)集進(jìn)行聚類時，有必要進(jìn)一步研究基于屬性權(quán)值的近鄰傳播聚類算法。

2 自適應(yīng)屬性加權(quán)近鄰傳播聚類

自適應(yīng)屬性加權(quán)近鄰傳播聚類算法是在傳統(tǒng)近鄰傳播聚類算法的基礎(chǔ)上，考慮了屬性權(quán)重的影響，使得屬性權(quán)值能夠根據(jù)近鄰傳播聚類過程中每次迭代的聚類結(jié)果實(shí)現(xiàn)自適應(yīng)調(diào)整，并且通過更新后的相似性矩陣將屬性權(quán)值的調(diào)整反映到下次迭代過程中，重新計(jì)算兩種競爭信息，以便獲得更好的近鄰傳播聚類效果。

2.1 自適應(yīng)屬性權(quán)值

針對傳統(tǒng)近鄰傳播算法缺少考慮屬性權(quán)重的問題，提出基于數(shù)據(jù)屬性權(quán)值的近鄰傳播聚類方法。從傳統(tǒng)近鄰傳播的過程中易知，近鄰傳播算法能通過逐步更新兩種競爭信息來逐漸獲取更好的聚類結(jié)果，最終使得聚類算法結(jié)果趨于穩(wěn)定。在每次迭代過程中，近鄰傳播聚類都可以獲得相應(yīng)的聚類結(jié)果，根據(jù)該結(jié)果的數(shù)據(jù)分布不僅可以確定屬性的重要程度，還可實(shí)現(xiàn)動態(tài)自適應(yīng)的屬性權(quán)值更新，進(jìn)而使近鄰傳播算法產(chǎn)生更好的聚類效果。

為了得到自適應(yīng)的數(shù)據(jù)屬性權(quán)值，在近鄰傳播的聚類過程中需要考慮兩個問題：1)什么樣的聚類結(jié)果是好的，即確定聚類結(jié)果的評價目標(biāo)函數(shù)；2)如何根據(jù)聚類結(jié)果來確定數(shù)據(jù)的屬性權(quán)值，即確定每次迭代計(jì)算中數(shù)據(jù)屬性權(quán)值的更新規(guī)則。

且須滿足：

式中，Z代表各個類簇中的數(shù)據(jù)對象與其聚類代表點(diǎn)之間的距離之和，Z越小表示當(dāng)前聚類質(zhì)量越高，即期望最終的聚類結(jié)果使其最??；U代表一個N×K的分類二元矩陣；當(dāng)時，表示數(shù)據(jù)點(diǎn)xn屬于第k個類簇；否則，該數(shù)據(jù)點(diǎn)不在第k類；代表k個類簇中的聚類中心，在K-Means算法中，該聚類中心為每個簇中所有對象的均值，K為類簇?cái)?shù)目；代表每個屬性的權(quán)值；表示數(shù)據(jù)點(diǎn)xn和第k個聚類中心點(diǎn)ck在第l個屬性上的距離。

實(shí)際上，在近鄰傳播的聚類分析過程中，除了需要考慮每個簇中對象的聚合性外，還需要進(jìn)一步考慮簇與簇之間的耦合性，即類內(nèi)數(shù)據(jù)盡可能相似與類間數(shù)據(jù)盡可能相異。為此，式(5)可轉(zhuǎn)化為：

為了使P值盡可能的大，每次迭代后屬性的權(quán)值應(yīng)根據(jù)當(dāng)前聚類結(jié)果進(jìn)行調(diào)整，使得P值趨于遞增。同時，如果某個屬性對于聚類結(jié)果的貢獻(xiàn)較大，那么應(yīng)該增大其屬性權(quán)值，使得P值變大。假設(shè)第t次迭代中的屬性權(quán)值代表第t次迭代過程中第l個屬性的權(quán)值。則在計(jì)算第t+1次迭代中第l個屬性的權(quán)值時除了考慮第t次的權(quán)值外，還需要考慮根據(jù)當(dāng)前聚類結(jié)果用以增大P值的屬性權(quán)重的變化量，即：

通過在迭代過程中計(jì)算每個屬性對聚類結(jié)果做出的貢獻(xiàn)從而更新屬性權(quán)值，使P值逐步趨向最優(yōu)，從而提升聚類質(zhì)量。另外，通過初始化各屬性權(quán)重，結(jié)合式(9)的權(quán)重變化和迭代過程，使得聚類過程中的權(quán)重值不需要人工干預(yù)，可以實(shí)現(xiàn)根據(jù)具體數(shù)據(jù)分布自適應(yīng)地確定，增強(qiáng)了算法的穩(wěn)定性和適用性。

2.2 加權(quán)近鄰傳播聚類算法

傳統(tǒng)近鄰傳播聚類算法通過一次計(jì)算數(shù)據(jù)點(diǎn)之間的距離來獲得相似性矩陣，并通過更新兩種競爭信息來實(shí)現(xiàn)迭代過程中的聚類分析，聚類思想過程如圖1所示。若聚類分析結(jié)果滿足聚類要求或迭代次數(shù)達(dá)到終止條件，則可獲得最終聚類結(jié)果，否則進(jìn)一步迭代更新兩種競爭信息，以便獲得更好的聚類結(jié)果。然而，傳統(tǒng)近鄰傳播聚類算法過程缺少考慮數(shù)據(jù)屬性權(quán)重的影響，同時每次迭代過程獲得的聚類結(jié)果缺少目標(biāo)函數(shù)的評價。為了更好地提高近鄰傳播聚類算法的性能，本文提出一種基于屬性權(quán)值的近鄰傳播聚類算法，該方法不僅考慮了屬性權(quán)重的影響，還在聚類過程中通過目標(biāo)函數(shù)評價功能自適應(yīng)地更新屬性權(quán)值，使其在迭代過程中逐步獲得更好的聚類效果。

圖2描述了本文AFW_AP算法的聚類思想過程?？梢钥闯?，AFW_AP算法在近鄰傳播的聚類過程中，根據(jù)當(dāng)前迭代聚類結(jié)果的目標(biāo)函數(shù)P值，將屬性權(quán)值自適應(yīng)地往增大P值的方向調(diào)整，并將屬性權(quán)值調(diào)整反映到加權(quán)相似性矩陣S的計(jì)算中。從式(1)～式(3)易知，代表度矩陣R是根據(jù)相似性矩陣S計(jì)算得到的，有效性矩陣A是根據(jù)代表度矩陣R計(jì)算得出。因此，利用更新后的屬性權(quán)值W獲得加權(quán)相似性矩陣S，可以將屬性權(quán)值的影響通過兩種競爭信息在近鄰傳播聚類迭代過程中不斷傳播，實(shí)現(xiàn)更好的聚類效果。

圖1 傳統(tǒng)近鄰傳播聚類過程

圖2 AFW_AP算法聚類過程

與傳統(tǒng)近鄰傳播聚類相同，將偏向參數(shù)p設(shè)為相似性矩陣的中位數(shù)，即

利用式(1)～式(3)更新代表度矩陣R(1)和有效性矩陣A(1)，利用式(4)根據(jù)代表度矩陣和有效性矩陣找出第一次迭代后的聚類代表點(diǎn)和每個代表點(diǎn)所代表對象。然后，分別利用式(9)和式(10)得到更新后屬性權(quán)值和加權(quán)相似性矩陣需要注意的是，為了產(chǎn)生穩(wěn)定的聚類結(jié)果，在每次迭代過程中加權(quán)相似性矩陣中的對角線元素的值不會隨著迭代次數(shù)的變化而改變。將S(1)帶入式(1)～式(3)中進(jìn)行下一輪迭代，隨著近鄰傳播產(chǎn)生的聚類結(jié)果不斷更新屬性權(quán)值和加權(quán)相似性矩陣，直到產(chǎn)生一個收斂的聚類結(jié)果或達(dá)到最大迭代次數(shù)為止。

AFW_AP聚類算法：Y=AFW_AP(X)

1)初始化阻尼因子λ=0.9和屬性權(quán)值其中

2)根據(jù)式(10)計(jì)算加權(quán)相似性矩陣S(t)，且

3)根據(jù)式(1)～式(3)計(jì)算代表度矩陣R和有效性矩陣A。

4)根據(jù)式(4)求出當(dāng)前各個數(shù)據(jù)對象的代表點(diǎn)。

5)根據(jù)式(9)更新屬性權(quán)值W(t+1)。

6)重復(fù)步驟2)～步驟5)直到產(chǎn)生收斂的聚類結(jié)果。

7)根據(jù)式(4)得到第i個數(shù)據(jù)對象所對應(yīng)的代表

從上述算法過程易知，AFW_AP算法不要求輸入過多的參數(shù)，可以大大地提高傳統(tǒng)近鄰傳播聚類算法的易用性和結(jié)果的穩(wěn)定性，無需更多的先驗(yàn)知識即可產(chǎn)生較好的聚類結(jié)果。與傳統(tǒng)近鄰傳播算法相比，AFW_AP算法在迭代過程中增加了一個根據(jù)當(dāng)前聚類結(jié)果調(diào)整權(quán)值并更新相似性矩陣的步驟，該步驟根據(jù)屬性的貢獻(xiàn)水平調(diào)整屬性權(quán)值使屬性權(quán)值逐步達(dá)到最優(yōu)。與近鄰傳播相同，AFW_AP算法產(chǎn)生的類簇?cái)?shù)目隨著偏向參數(shù)的取值不同而改變，并且算法迭代次數(shù)受到阻尼因子的影響(一般情況下λ為0.9)。

新算法在聚類過程中通過屬性權(quán)值的更新改變相似性度量矩陣的值，會影響近鄰傳播的計(jì)算結(jié)果。隨著迭代次數(shù)的增加，屬性權(quán)值逐漸達(dá)到穩(wěn)定，在聚類后期，由于屬性權(quán)值不再改變，相似性度量矩陣能夠達(dá)到穩(wěn)定狀態(tài)使得新算法能夠隨著近鄰傳播聚類的收斂而收斂。

本文提出的算法時間復(fù)雜度較高，加入權(quán)值更新后時間復(fù)雜度在近鄰傳播聚類的基礎(chǔ)上增加其中D為數(shù)據(jù)集中的屬性個數(shù)，k為當(dāng)前聚類結(jié)果中的類簇?cái)?shù)目，n為數(shù)據(jù)集中的樣本個數(shù)，但是加入調(diào)整的屬性權(quán)值對算法結(jié)果的精度能夠有一定的提高。因此在面對大數(shù)據(jù)量的數(shù)據(jù)集時，可以在小樣本、抽樣或訓(xùn)練集數(shù)據(jù)上執(zhí)行所提出的算法，獲得更新的屬性權(quán)值后，直接將該值代入相似性矩陣的計(jì)算，并將屬性加權(quán)的相似性矩陣作為近鄰傳播聚類的輸入?yún)?shù)，從而提升近鄰傳播聚類的聚類效果。在計(jì)算過程中為了提高AFW_AP聚類的計(jì)算速度，增強(qiáng)算法的穩(wěn)定性，可將屬性的權(quán)值和相似性矩陣的更新頻率設(shè)為一個固定的值。

3 實(shí)驗(yàn)與結(jié)果分析

本文使用UCI與文本數(shù)據(jù)集結(jié)合常用的聚類評價指標(biāo)(F-Measure、Folkes_Mallows和corrected rand index)進(jìn)行算法聚類質(zhì)量的評價。同時，分別從目標(biāo)函數(shù)P值、屬性權(quán)值變化、聚類結(jié)果和迭代收斂性分析來檢驗(yàn)新方法的性能。另外，由于基于近鄰傳播的聚類所產(chǎn)生的類簇?cái)?shù)目受到偏向參數(shù)的影響，因此實(shí)驗(yàn)中將所有基于近鄰傳播的聚類方法中的偏向參數(shù)設(shè)為相似性矩陣的中位數(shù)，并根據(jù)AP算法所產(chǎn)生的類簇?cái)?shù)目限定K-Means等傳統(tǒng)限定類簇?cái)?shù)目聚類算法的聚類參數(shù)。

3.1 聚類評價指標(biāo)

由于實(shí)驗(yàn)所用的UCI數(shù)據(jù)集其分類簇的結(jié)果是已知的，可以使用外部度量的聚類指標(biāo)對新方法的聚類結(jié)果進(jìn)行有效性評價。實(shí)驗(yàn)中使用3種不同的外部度量指標(biāo)對聚類結(jié)果進(jìn)行評價，以便更好地比較說明方法的有效性。

1)F-Measure

F-Measure[21]指標(biāo)是常用的聚類質(zhì)量測評指標(biāo)之一，它同時考慮了準(zhǔn)確率(precision)和召回率(recall)兩個指標(biāo)，能夠得到綜合的評價結(jié)果：

2)Folkes_Mallows

Folkes_Mallows(FM)[22]指標(biāo)是一個落在[0,1]之間的聚類評價指標(biāo)，F(xiàn)M越大，表明聚類的正確率越高。當(dāng)聚類結(jié)果中的類簇?cái)?shù)目與正確的類簇?cái)?shù)目不相同時，F(xiàn)M評價指標(biāo)能夠得出更客觀的評價結(jié)果：

式中，TP表示同一類的數(shù)據(jù)對象被分到同一個簇；TN表示不同類的數(shù)據(jù)對象被分到不同簇；FP表示不同類的數(shù)據(jù)對象被分到同一個簇；FN表示同一類的數(shù)據(jù)對象被分到不同簇。

3)Corrected Rand Index

Corrected rand index(CRI)[23]是常用的半監(jiān)督聚類評價指標(biāo)，它在rand index的基礎(chǔ)上進(jìn)行了改進(jìn)：

式中，A和B是數(shù)據(jù)集的兩個分類，分類A中有KA個類簇，分類B中有KB個類簇；Nij代表在A中屬于第i個簇同時也在B中屬于第j個簇中數(shù)據(jù)對象的數(shù)量；Ni和Nj分別表示A中第i個簇與B中第j個簇中數(shù)據(jù)對象的數(shù)量；符號C代表組合數(shù)的計(jì)算。

3.2 目標(biāo)函數(shù)P值

屬性權(quán)值在近鄰傳播的聚類過程中，根據(jù)當(dāng)前聚類結(jié)果，以增大目標(biāo)函數(shù)P值為目的不斷更新。在本次實(shí)驗(yàn)中，通過計(jì)算每次屬性權(quán)值更新后的P值驗(yàn)證屬性權(quán)值對P值的影響，實(shí)驗(yàn)結(jié)果如圖3和圖4所示(實(shí)驗(yàn)數(shù)據(jù)集的具體信息見3.4節(jié))。

圖3 Iris和Glass數(shù)據(jù)集的P值變化過程

圖4 Leuk和Image數(shù)據(jù)集的P值變化過程

由于近鄰傳播聚類將所有數(shù)據(jù)對象視為潛在的代表點(diǎn)，在聚類初始階段，近鄰傳播聚類往往傾向于生成類簇較多的聚類結(jié)果(極端情況為每個數(shù)據(jù)對象自成一類)，然后在迭代中逐步將類簇?cái)?shù)目調(diào)整為合適的值。因此，目標(biāo)函數(shù)P值在聚類初始階段并不是一個穩(wěn)定上升的過程。若類簇?cái)?shù)目較多，初始階段的P值很可能為一個較大數(shù)值(即Iris與Image數(shù)據(jù)集曲線所示情況，初始曲線變化呈現(xiàn)一個快速下降的趨勢)，隨著類簇?cái)?shù)目的不斷調(diào)整，P將達(dá)到穩(wěn)定點(diǎn)，即在該點(diǎn)以后聚類結(jié)果中的類簇?cái)?shù)目為一個穩(wěn)定的值。因此，P到達(dá)穩(wěn)定點(diǎn)以后，類簇?cái)?shù)目不再變動，屬性權(quán)值對目標(biāo)函數(shù)P值具有穩(wěn)定的影響。

從圖3和圖4中可以看出，目標(biāo)函數(shù)P值由于類簇?cái)?shù)目的逐步穩(wěn)定，在初期的波動結(jié)束后達(dá)到某個穩(wěn)定點(diǎn)(即圖中的實(shí)心點(diǎn))。穩(wěn)定之后的P值會隨著屬性權(quán)值的不斷調(diào)整，呈現(xiàn)一個逐漸增大并穩(wěn)定的過程，即目標(biāo)函數(shù)能夠通過屬性權(quán)值的調(diào)整逐步接近最優(yōu)。上述過程驗(yàn)證了屬性權(quán)值的調(diào)整對P值能夠產(chǎn)生積極影響，使目標(biāo)函數(shù)逐步接近最優(yōu)。

3.3 屬性權(quán)值分析

圖5 Iris數(shù)據(jù)集上的屬性權(quán)值變化

圖6 Pima數(shù)據(jù)集上的屬性權(quán)值變化

經(jīng)過AFW_AP算法在聚類過程中對屬性權(quán)值的調(diào)整，數(shù)據(jù)集中的某個對聚類結(jié)果貢獻(xiàn)較大的屬性會在調(diào)整中不斷增大，而剩余屬性值則隨著更新次數(shù)逐漸減小。實(shí)驗(yàn)過程中屬性權(quán)值的變化如圖5和圖6所示。

從圖5中可以看到Iris數(shù)據(jù)集中的表示花瓣長的屬性隨著屬性權(quán)值在迭代中的調(diào)整，在聚類過程中所占的比重逐漸增大，而其余的屬性權(quán)重則不斷減小。這說明在對Iris進(jìn)行分類時，花瓣的長度對分類所起到的作用遠(yuǎn)大于其余屬性對分類結(jié)果的影響，并且增大花瓣長度的屬性權(quán)值可以提高聚類結(jié)果的質(zhì)量。

從圖6中可以得出，在Pima數(shù)據(jù)集上屬性五相較其余屬性對聚類質(zhì)量的改進(jìn)作用更大，它在更新的過程中不斷上升至0.4，而剩余的5個屬性的權(quán)值則不斷降低最終穩(wěn)定在一個相似的值上。因此，從實(shí)驗(yàn)結(jié)果來看，屬性權(quán)值隨著更新次數(shù)變化到一定階段時，會達(dá)到一個穩(wěn)定值，促使新聚類算法產(chǎn)生穩(wěn)定的聚類結(jié)果。

3.4 聚類實(shí)驗(yàn)

為了進(jìn)一步驗(yàn)證AFW_AP算法的聚類結(jié)果，使用UCI數(shù)據(jù)集對算法進(jìn)行聚類分析。實(shí)驗(yàn)中使用11個UCI數(shù)據(jù)集和一個文本數(shù)據(jù)集進(jìn)行算法驗(yàn)證，數(shù)據(jù)集的具體信息如表1所示，其中Text數(shù)據(jù)集為中文文本數(shù)據(jù)集，數(shù)據(jù)集來源為搜狗實(shí)驗(yàn)室。

表1 實(shí)驗(yàn)數(shù)據(jù)集信息

表1中的分類數(shù)為將偏向參數(shù)設(shè)為相似性矩陣的中位數(shù)時AP算法對數(shù)據(jù)集的聚類結(jié)果中含有的類簇?cái)?shù)目。可以看出當(dāng)數(shù)據(jù)集中樣本較多時，聚類結(jié)果中含有的類簇?cái)?shù)目遠(yuǎn)大于樣本中的類別數(shù)。該現(xiàn)象同樣出現(xiàn)在AFW_AP算法與SAP算法的聚類結(jié)果中。在實(shí)際應(yīng)用中可根據(jù)需要，對近鄰傳播的偏向參數(shù)進(jìn)行調(diào)整，使得聚類結(jié)果中的分類數(shù)目達(dá)到理想。

本次實(shí)驗(yàn)所使用的對比算法有AP、子空間近鄰傳播聚類算法(SAP)[16]、加權(quán)K-Means算法(WK-means)、clara算法[24]、譜聚類算法(spectal)和增量AP聚類算法(IAPKMA)[25]，并結(jié)合3種評價指標(biāo)進(jìn)行聚類結(jié)果分析。為了提升算法的穩(wěn)定性與計(jì)算速度，實(shí)驗(yàn)中將AFW_AP算法中的權(quán)值更新頻率設(shè)為每十次迭代更新一次。在實(shí)際應(yīng)用中也可根據(jù)需要設(shè)定更新頻率，這里綜合考慮算法效率與屬性權(quán)值的更新準(zhǔn)確性將屬性權(quán)值的更新頻率設(shè)為10。特別地，由于Iris數(shù)據(jù)集較小，將Iris數(shù)據(jù)集中的權(quán)值更新頻率設(shè)為每次迭代更新，以充分體現(xiàn)權(quán)值更新對聚類的影響。聚類實(shí)驗(yàn)結(jié)果如表2，表3和表4所示。

表2 7種方法聚類結(jié)果的F-Measure指標(biāo)值

從表2中可以看出加權(quán)K-Means算法在12個數(shù)據(jù)集中的2個數(shù)據(jù)集上能獲得優(yōu)勢的聚類結(jié)果，而SAP, IAPKM和譜聚類算法分別在其中1個數(shù)據(jù)集中有突出表現(xiàn)，AFW_AP算法則在剩余的數(shù)據(jù)集上的聚類效果占優(yōu)勢。最后，從算法均值上看AFW_AP在F-Measure指標(biāo)上的表現(xiàn)優(yōu)于對比算法。

表3 7種方法聚類結(jié)果的CRI指標(biāo)值

從表3中可以看出，在所使用的12個數(shù)據(jù)集中，AFW_AP算法在其中8個數(shù)據(jù)集上能獲得優(yōu)勢聚類結(jié)果，而加權(quán)的K-Means聚類算法則能在其中兩個數(shù)據(jù)集中領(lǐng)先對比算法。最后，從均值上看AFW_AP算法能夠取得較高質(zhì)量的結(jié)果。

表4 7種方法聚類結(jié)果的Folkes_M指標(biāo)值

從表4中可以看出，與CRI指標(biāo)不同，在FM指標(biāo)上SAP算法在Contraceptive數(shù)據(jù)集與文本數(shù)據(jù)集數(shù)據(jù)集上的聚類結(jié)果要優(yōu)于AFW_AP算法，但AFW_AP算法在多數(shù)數(shù)據(jù)集與均值上的聚類表現(xiàn)仍較對比算法占優(yōu)勢。綜合表2～表4的聚類結(jié)果，與近鄰傳播聚類和傳統(tǒng)聚類算法相比，AFW_AP算法在3個聚類有效性評價指標(biāo)上均有較明顯的提升，說明AFW_AP算法通過自適應(yīng)權(quán)值的更新和使用對近鄰傳播聚類方法能夠起到積極的效果。

3.5 迭代收斂性比較

AFW_AP算法較于傳統(tǒng)AP算法在大部分?jǐn)?shù)據(jù)集中能夠使用更少的迭代收斂次數(shù)取得較好的聚類結(jié)果，迭代收斂次數(shù)結(jié)果比較如圖7所示。圖中曲線值表示AFW_AP算法所用迭代次數(shù)與AP算法所用迭代次數(shù)的相對值(在多數(shù)數(shù)據(jù)集的計(jì)算中近鄰傳播聚類所用的收斂迭代次數(shù)落入[150, 250]區(qū)間內(nèi))。容易看出，AFW_AP算法通過對屬性權(quán)值進(jìn)行調(diào)整，在12個實(shí)驗(yàn)數(shù)據(jù)集中的7個數(shù)據(jù)集上比AP算法使用更少的迭代收斂次數(shù)(除AFW_AP算法在Ecoli和Yeast上未能取得收斂的聚類)。為了進(jìn)一步對比兩個算法的迭代收斂性，將AP算法與AFW_AP算法在Glass數(shù)據(jù)集上的收斂曲線進(jìn)行比較，實(shí)驗(yàn)結(jié)果如圖8所示。圖中縱坐標(biāo)的值為聚類過程中類簇中的點(diǎn)與類簇代表點(diǎn)的距離之和。聚類凈相似度隨著算法的收斂會逐漸減小并達(dá)到穩(wěn)定值。

從圖8與圖9可以看出AFW_AP聚類在最初的幾次迭代中由于屬性權(quán)值的調(diào)整收斂曲線產(chǎn)生一次大幅震蕩，隨后AFW_AP聚類逐步趨向收斂，并且在更短的迭代周期內(nèi)完成聚類收斂。而AP聚類的收斂曲線不產(chǎn)生大幅震蕩，而是在小幅的調(diào)整中逐步達(dá)到收斂，這也使得AP聚類的收斂需要較多的迭代周期。

圖7 AFW_AP和AP算法的迭代收斂次數(shù)對比

圖8 AP算法在Glass數(shù)據(jù)集上的收斂曲線

圖9 AFW-AP算法在Glass數(shù)據(jù)集上的收斂曲線

4 結(jié)束語

本文對屬性權(quán)值在近鄰傳播聚類過程中的影響進(jìn)行了研究，提出一種基于自適應(yīng)屬性權(quán)值的近鄰傳播聚類算法AFW_AP。該方法在近鄰傳播算法中根據(jù)每次迭代聚類結(jié)果的目標(biāo)評價函數(shù)來自適應(yīng)更新屬性權(quán)值，使得當(dāng)前數(shù)據(jù)劃分的結(jié)果可以計(jì)算各個屬性對聚類的貢獻(xiàn)程度，從而調(diào)整屬性權(quán)值與相似性矩陣，逐步使聚類結(jié)果接近最優(yōu)進(jìn)而提升整體近鄰傳播的聚類質(zhì)量。同時，AFW_AP算法不需要額外的參數(shù)設(shè)定，增強(qiáng)了聚類算法的適用性，且屬性權(quán)值在后期迭代過程的穩(wěn)定性促使近鄰算法可以獲得穩(wěn)定的聚類效果。數(shù)值實(shí)驗(yàn)結(jié)果表明，屬性權(quán)值的更新過程在新算法中能夠起到積極作用，與傳統(tǒng)聚類算法相比，AFW_AP算法能夠獲得好的聚類準(zhǔn)確率。然而，雖然AFW_AP聚類產(chǎn)生收斂的聚類結(jié)果所使用的迭代次數(shù)較AP聚類少，但是迭代過程中新增權(quán)值和相似性矩陣的計(jì)算等步驟使得AFW_AP聚類需要額外的時間開銷，這也是將來應(yīng)需要進(jìn)一步探討和研究問題。

[1]JAIN A K, DUBES R C.Algorithms for clustering data[M].New Jersey: Prentice-Hall, 1988.

[2]DU Ke-lin, SWAMY M N S.Neural networks and statistical learning[M].Berlin: Springer, 2014.

[3]MCLACHLAN G，KRISHNAN T.The EM algorithm and extensions[M].New York: Wiley, 2008.

[4]張衡, 譚曉陽, 金鑫, 等.基于多視圖聚類的自然圖像邊緣檢測[J].模式識別與人工智能, 2016(2): 163-170.ZHANG Heng, TAN Xiao-yang, JIN Xin, et al.Multi-view clustering based natural image contour detection[J].Pattern Recognition and Artificial Intelligence, 2016(2): 163-170.

[5]朱張祥, 劉詠梅.在線社交網(wǎng)絡(luò)謠言傳播的仿真研究-基于聚類系數(shù)可變的無標(biāo)度網(wǎng)絡(luò)環(huán)境[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué), 2016, 13(2): 74-82.ZHU Zhang-xiang, LIU Yong-mei.Simulation study of propagation of rumor in online social network based on scale-free network with tunable clustering[J].Complex Systems and Complexity Science, 2016, 13(2): 74-82.

[6]王光沛, 潘景昌, 衣振萍, 等.基于線指數(shù)特征的海量恒星光譜聚類分析研究[J].光譜學(xué)與光譜分析, 2016, 36(8):2646-2650.WANG Guang-pei, PAN Jing-chang, YI Zhen-ping.Research on the clustering of massive stellar spectra based on line index[J].Spectroscopy and Spectral Analysis, 2016,36(8): 2646-2650.

[7]徐毅非, 蔣文波, 程雪麗, 等.基于譜聚類的無功電壓分區(qū)和主導(dǎo)節(jié)點(diǎn)選擇[J].電力系統(tǒng)保護(hù)與控制, 2016,44(15): 73-78.XU Yi-fei, JIANG Wen-bo, CHENG Xue-li.Partitioning for reactive voltage based on spectral clustering and pilot nodes selection[J].Power System Protection and Control, 2016,44(15): 73-78.

[8]王宇超, 周亞福, 王得祥, 等.秦嶺南坡中段主要森林群落類型劃分及環(huán)境梯度解釋[J].生態(tài)環(huán)境學(xué)報(bào), 2016,25(6): 965-972.WANG Yu-chao, ZHOU Ya-fu, WANG De-xiang.The quantitative classification and environmental interpretation of forest communities in the middle area of south slope of Qinling mountains[J].Ecology and Environment Sciences,2016, 25(6): 965-972.

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

[10]董俊, 王鎖萍, 熊范綸.可變相似性度量的近鄰傳播聚類[J].電子與信息學(xué)報(bào), 2010(3): 509-514.DONG Jun, WANG Suo-ping, XIONG Fan-lun.Affinity propagation clustering based on variable-similarity measure[J].Journal Of Electronics & Information Technology, 2010(3): 509-514.

[11]SHANG Ron-ghua, LUO Shuang, ZHANG Wei-tong, et al.A multiobjective evolutionary algorithm to find community structures based on affinity propagation[J].Physica A:Statistical Mechanics and its Applications, 2016(453):203-227.

[12]YU Jian.General C-means clustering model[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2005, 27(8): 1197-1211.

[13]HUAN Liu, YU Lei.Toward integrating feature selection algorithms for classification and clustering[J].IEEE Transactions on Knowledge and Data Engineering, 2005,17: 491-502.

[14]劉銘, 吳沖, 劉遠(yuǎn)超, 等.基于特征權(quán)重量化的相似度計(jì)算方法[J].計(jì)算機(jī)學(xué)報(bào), 2015(7): 1420-1433.LIU Ming, WU Chong, LIU Yuan-Chao, et al.Similarity calculation based on feature weight evaluation[J].Chinese Journal of Computers, 2015(7): 1420-1433.

[15]de AMORIM R C, MIRKIN B.Minkowski metric, feature weighting and anomalous cluster initializing in K-Means clustering[J].Pattern Recognition, 2012, 45(3): 1061-1075.

[16]GAN G J, NG M K.Subspace clustering using affinity propagation[J].Pattern Recognition, 2015, 48: 1455-1464.

[17]HUANG J, NG M, RONG H, et al.Automated variable weighting in k-means type clustering[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27:657-668.

[18]TSAI C Y, CHIU C C.Developing a feature weight self-adjustment mechanism for a K-means clustering algorithm[J].Computational Statistics & Data Analysis 2008, 52(10): 4658-4672.

[19]周世兵, 徐振源, 唐旭清.一種基于近鄰傳播算法的最佳聚類數(shù)確定方法[J].控制與決策, 2011, 8: 1147-1152.ZHOU Shi-bin, XUN Zhen-yuan, TANG Xu-qing.Method for determining optimal number of cluster based on affinity propagation clustering[J].Control and Decision, 2011, 8:1147-1152.

[20]GUI Bin, YANG Xiao-ping.Advanced technologies,embedded and multimedia for human-centric computing[M].Berlin: Springer Netherlands, 2013: 637-644.

[21]POWERS D.Evaluation: from precision, recall and F-measure to ROC, informedness, markedness and correlation[J].Journal of Machine Learning Technologies,2011, 2(1): 37-63.

[22]FOWLKES E B, MALLOWS C L.A method for compareng two hierarchical clusterings[J].Journal of the American Statistical Association, 1983, 78(383): 553-569.

[23]WARRENS M J.On the equivalence of Cohen’s Kappa and the Hubert-Arabie adjusted rand index[J].Journal of Classification, 2008, 25(2): 177-183.

[24]KAUFMAN L, ROUSSEEUW P J. Clustering large applications (program clara)finding groups in data: an introduction to cluster analysis[M].New York: John Wiley& Sons Inc, 2008.

[25]GUO C.Incremental affinity propagation clustering based on message passing[J].IEEE Transactions on Knowledge& Data Engineering, 2014, 26(11): 2731-2744.