馮俊淇，張正軍，章 曼，嚴(yán) 濤

(南京理工大學(xué)理學(xué)院,江蘇 南京 210094)

0 引 言

聚類分析是一種常用的無監(jiān)督學(xué)習(xí)算法，對(duì)于一組未知類標(biāo)簽的數(shù)據(jù)集，它能夠根據(jù)樣本間的相似性，將樣本劃分到對(duì)應(yīng)的類別，從而使同一類別中樣本相似度較高，不同類別間樣本相似度較低。近年來，隨著數(shù)據(jù)爆炸式增長，聚類分析被廣泛應(yīng)用于圖像處理、數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)等領(lǐng)域。

聚類方法發(fā)展至今，已有許多成熟算法：劃分聚類算法K-means[1]和K-medoids[2]、密度聚類算法DBSCAN[3]、層次聚類算法CURE[4]、網(wǎng)格聚類算法STING[5]等。

根據(jù)隸屬度取值方法，聚類算法可以分為硬聚類算法和軟聚類算法。傳統(tǒng)聚類算法中的K-means就是硬聚類算法，樣本的隸屬度取值是0或1，即樣本只能屬于一類，這種“非黑即白”的分類方法并不符合生活中的現(xiàn)實(shí)關(guān)系。1973年Dunn[6]將模糊關(guān)系引入到K-means算法，提出了模糊C均值(FCM)算法，1981年Bezdek[7]將模糊指數(shù)引入目標(biāo)函數(shù)，擴(kuò)展了算法的一般性。

盡管模糊C均值(FCM)算法應(yīng)用于現(xiàn)實(shí)生活中的諸多領(lǐng)域，但是仍存在一些不足：1)算法中采用歐氏距離作為相似性度量，未考慮數(shù)據(jù)的各屬性對(duì)聚類的影響不同，導(dǎo)致聚類效果不理想；2)聚類過程中僅考慮樣本與聚類中心的距離，沒能有效利用鄰域樣本的信息，造成邊界樣本和噪聲樣本錯(cuò)分率較高。近年來，許多專家學(xué)者針對(duì)FCM算法缺點(diǎn)提出了改進(jìn)，取得了豐厚的研究成果。文獻(xiàn)[8-11]通過對(duì)數(shù)據(jù)賦予權(quán)重的方法來優(yōu)化算法，提高聚類性能；文獻(xiàn)[12-14]利用不同的方法對(duì)聚類中心初始化，有效減小了噪聲點(diǎn)對(duì)聚類過程的影響，提升了聚類的準(zhǔn)確性；文獻(xiàn)[15-16]從數(shù)據(jù)的空間鄰域信息出發(fā)，通過改變目標(biāo)函數(shù)進(jìn)而修正了隸屬度及聚類中心的迭代公式；文獻(xiàn)[17-18]通過松弛樣本隸屬度約束條件，降低噪聲樣本對(duì)聚類結(jié)果的影響；文獻(xiàn)[19-20]從模糊加權(quán)指數(shù)入手，提出各種方法以計(jì)算合理的模糊加權(quán)指數(shù)。

基于以上研究，本文提出基于熵與鄰域約束的FCM算法，利用熵權(quán)法對(duì)樣本加權(quán)，改進(jìn)樣本間的距離度量，利用鄰域約束修正目標(biāo)函數(shù)，從而提升聚類性能。

1 模糊C均值算法

模糊C均值(FCM)算法是一種基于目標(biāo)函數(shù)的聚類算法，通過最小化目標(biāo)函數(shù)使得類內(nèi)平方誤差達(dá)到最小值，其目標(biāo)函數(shù)(1)和約束條件(2)如下：

(1)

(2)

其中,c(c>1)是聚類數(shù)目；V=[v1,…,vc]表示聚類中心；U=uij是c×n的隸屬度矩陣；m∈[1,+∞)是模糊系數(shù)；uij是樣本xj對(duì)于第i類的隸屬度；‖xj-vi‖2表示樣本xj與聚類中心vi的歐氏距離。

采用拉格朗日乘數(shù)法計(jì)算得到uij、vi的迭代公式如式(3)、式(4)：

(3)

(4)

FCM算法具體步驟如下：

輸入：聚類數(shù)目c、模糊系數(shù)m、最大迭代次數(shù)T、閾值ε

輸出：隸屬度矩陣U，聚類中心矩陣V

步驟1 初始化迭代次數(shù)t=0；

步驟2 初始化隸屬度矩陣U；

步驟3 根據(jù)式(4)計(jì)算聚類中心矩陣V；

步驟4 根據(jù)式(3)計(jì)算隸屬度矩陣U；

步驟5 如果‖U(t)-U(t-1)‖≤ε或t>T，停止迭代；否則，t=t+1，轉(zhuǎn)到步驟3；

步驟6 完成上述步驟，得到最終的聚類中心矩陣V和隸屬度矩陣U，據(jù)此劃分?jǐn)?shù)據(jù)集，完成聚類。

2 算法設(shè)計(jì)

2.1 熵值賦權(quán)法

FCM算法中樣本隸屬度僅由樣本與聚類中心的歐氏距離決定，沒有考慮數(shù)據(jù)的不同屬性對(duì)聚類的影響不同。為了彌補(bǔ)這一缺陷，本文通過各屬性的熵值來確定權(quán)重，最終以加權(quán)歐氏距離作為距離度量。

在信息論[21]中，熵是對(duì)系統(tǒng)不確定性的度量。熵值賦權(quán)法[22]的思想是根據(jù)屬性的熵值來判斷其變異程度，屬性變異程度越大，熵越小，信息量越大，所以權(quán)重越大；反之，屬性離散程度越小，熵越大，信息量越小，所以權(quán)重越小。

對(duì)于n個(gè)包含r維屬性的樣本，熵值賦權(quán)法步驟如下：

1)數(shù)據(jù)標(biāo)準(zhǔn)化?，F(xiàn)實(shí)中的數(shù)據(jù)通常存在量綱的影響，通過計(jì)算樣本xj第t維屬性占所有樣本第t維屬性的比重將數(shù)據(jù)壓縮到[0,1]：

(5)

其中,xjt為樣本xj第t維屬性值，j=1,2,…,n；t=1,2,…,r。

2)計(jì)算第t維屬性的熵值：

(6)

3)計(jì)算第t維屬性的差異性系數(shù)：

qt=1-Et

(7)

其中，qt為差異性系數(shù)。

4)計(jì)算第t維屬性的權(quán)重wt：

(8)

利用各屬性權(quán)重，給出樣本xj和樣本xi的熵值賦權(quán)歐氏距離，計(jì)算公式如下：

(9)

權(quán)重系數(shù)wt表示各屬性對(duì)于聚類的重要性，其作用是將各屬性對(duì)聚類的影響進(jìn)行放縮，使得對(duì)聚類過程影響大的屬性權(quán)重更大，對(duì)聚類過程影響小的屬性權(quán)重更小。

2.2 鄰域隸屬度約束

對(duì)于聚類問題，樣本的隸屬度除了與自身特征有關(guān)，還受鄰域樣本隸屬度的影響。樣本間的空間位置越近，則二者屬于同一類別的概率越大。因此，鄰域樣本對(duì)于中心樣本所屬類別的影響取決于它們和中心樣本的空間距離，距離越小，其對(duì)中心樣本的影響越大，反之距離越大，對(duì)中心樣本的影響越小。定義鄰域樣本xk對(duì)中心樣本xj的影響系數(shù)如下：

(10)

其中,dkj表示鄰域樣本xk與中心樣本xj的熵值賦權(quán)歐氏距離，熵值賦權(quán)歐氏距離能夠區(qū)分不同屬性在聚類過程中的重要程度。從式(10)可以看出，若dkj越小，則zkj越大，此時(shí)鄰域樣本xk與中心樣本xj的隸屬情況相似度較高，當(dāng)dkj為0時(shí)，二者空間位置相同，zkj取到最大值1；若dkj越大，則zkj越小，此時(shí)鄰域樣本xk與中心樣本xj的隸屬情況相似度較低。

通過歸一化中心樣本xj鄰域內(nèi)的影響系數(shù)得到鄰域樣本xk對(duì)中心樣本xj的鄰域隸屬度權(quán)重，定義如下：

(11)

其中，N表示鄰域樣本集。顯然ωkj∈[0,1]且任意樣本的鄰域隸屬度權(quán)重和為1，即：

(12)

根據(jù)式(11)可知，影響系數(shù)zkj越大，鄰域隸屬度權(quán)重ωkj越大，則鄰域樣本xk對(duì)中心樣本xj的隸屬度約束力越強(qiáng)。

利用鄰域隸屬度權(quán)重ωkj對(duì)鄰域內(nèi)的樣本隸屬度進(jìn)行加權(quán)求和，得到鄰域隸屬度pij，定義如下：

(13)

(14)

鄰域隸屬度pij描述了樣本xj的鄰域樣本對(duì)于第i類的隸屬情況，pij∈[0,1]，pij越大，表明鄰域樣本對(duì)第i類的隸屬度越高，則中心樣本xj屬于第i類的可能性就越大；反之，pij越小，表明鄰域樣本對(duì)第i類的隸屬度越低，則中心樣本xj屬于第i類的可能性就越小。

2.3 NEFCM算法

本文提出的算法稱為NEFCM(Neiborhood Constraint and Entropy FCM)算法，其針對(duì)FCM算法的改進(jìn)主要在距離度量和修正隸屬度迭代這2個(gè)方面，主要思想為：通過計(jì)算各屬性的熵值來為樣本各屬性賦予權(quán)重，從而改進(jìn)歐氏距離；在隸屬度迭代的過程中，根據(jù)樣本的鄰域隸屬度對(duì)其自身進(jìn)行修正，從而有效利用鄰域信息，優(yōu)化FCM算法性能。

結(jié)合式(9)的熵值賦權(quán)歐氏距離及式(14)的鄰域隸屬度，在原FCM算法的基礎(chǔ)上提出基于熵與鄰域約束的FCM算法(NEFCM)，該算法的目標(biāo)函數(shù)及約束條件如下：

(15)

在FCM算法中，聚類過程僅考慮樣本與聚類中心的歐氏距離，沒能區(qū)分各屬性對(duì)聚類過程的重要程度，同時(shí)忽略了鄰域樣本的信息，無法準(zhǔn)確劃分邊界樣本和噪聲樣本，導(dǎo)致聚類效果不理想。本文算法改進(jìn)了距離度量，同時(shí)利用鄰域隸屬度約束目標(biāo)函數(shù)，從而修正隸屬度迭代過程，提高聚類性能。

NEFCM算法在約束條件下的拉格朗日函數(shù)為：

(16)

(17)

(18)

2.4 算法步驟

輸入：聚類數(shù)目c、模糊系數(shù)m、最大迭代次數(shù)T、閾值ε、懲罰因子α

輸出：隸屬度矩陣U，聚類中心矩陣V

步驟1 初始化迭代次數(shù)t=0；

步驟2 初始化隸屬度矩陣U；

步驟3 根據(jù)式(13)計(jì)算鄰域隸屬度矩陣P；

步驟4 根據(jù)式(18)計(jì)算聚類中心矩陣V；

步驟5 根據(jù)式(17)計(jì)算隸屬度矩陣U；

步驟6 如果‖U(t)-U(t-1)‖≤ε或t>T，停止迭代；否則，t=t+1，轉(zhuǎn)到步驟3；

步驟7 完成上述步驟，得到最終的聚類中心矩陣V和隸屬度矩陣U，據(jù)此劃分?jǐn)?shù)據(jù)集，完成聚類。

3 實(shí) 驗(yàn)

為驗(yàn)證本文所提出的NEFCM算法的有效性，分別在人造數(shù)據(jù)集和UCI數(shù)據(jù)庫中的多個(gè)真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。

本文實(shí)驗(yàn)采用的計(jì)算機(jī)硬件配置為Intel Core i7處理器(主頻3.4 GHz)，16 GB內(nèi)存，Windows 10 64位操作系統(tǒng)，Python 3.7(IDLE)編程實(shí)現(xiàn)算法。

本文采用FCM、KFCM、PCM、KPCM及文獻(xiàn)[12]提出的DSFCM(Density Peaks and Spatial Neighborhood FCM)算法作為對(duì)比算法，并選取2個(gè)經(jīng)典的聚類性能指標(biāo)：標(biāo)準(zhǔn)互信息(Normalized Mutual Information，NMI)[23]、蘭德系數(shù)(Rand Index，RI)。定義如下：

(19)

其中，X表示樣本真實(shí)劃分結(jié)果，Y表示聚類劃分結(jié)果。I(X,Y)表示X和Y的互信息，H(X)和H(Y)分別表示X和Y的信息熵。NMI的取值范圍為[0,1]，越接近于1，聚類效果越好。

(20)

其中，a表示不同類別中不同類標(biāo)簽的樣本數(shù)，b表示同類別中相同類標(biāo)簽的樣本數(shù)，n表示樣本數(shù)。RI的取值范圍為[-1,1]，同樣越接近于1，聚類效果越好。

3.1 人造數(shù)據(jù)集實(shí)驗(yàn)

N3數(shù)據(jù)集是本文人造的邊界模糊數(shù)據(jù)集，包含3個(gè)簇，共400個(gè)樣本點(diǎn)。同時(shí)，為驗(yàn)證NEFCM算法在噪聲數(shù)據(jù)集上的效果，在N3數(shù)據(jù)集上添加40個(gè)噪聲樣本，主要參數(shù)如表1所示。

表1 人造數(shù)據(jù)集主要參數(shù)

使用上述2個(gè)數(shù)據(jù)集對(duì)FCM、PCM、KFCM、KPCM、DSFCM及本文提出的NEFCM算法進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)中模糊加權(quán)指數(shù)m=2，迭代終止閾值ε=1e-5，最大迭代次數(shù)為T=500，懲罰因子α=0.9，懲罰因子的取值和樣本與聚類中心的距離有關(guān)，根據(jù)實(shí)際情況綜合考慮。

圖1和圖2是6種算法分別在N3數(shù)據(jù)集和含噪聲的N3數(shù)據(jù)集上的對(duì)比實(shí)驗(yàn)結(jié)果，每個(gè)數(shù)據(jù)都取算法運(yùn)行10次后得到的平均值。

圖1 NMI比較

圖2 RI比較

由圖1和圖2可以看出，在N3數(shù)據(jù)集上，本文提出的NEFCM算法在NMI和RI這2個(gè)指標(biāo)上都優(yōu)于其他5種算法，這說明NEFCM能夠區(qū)分各屬性在聚類過程中的重要程度，并且有效利用鄰域信息，即使在邊界模糊的數(shù)據(jù)集上，也能較為準(zhǔn)確地聚類。同時(shí)，在加入噪聲后，KFCM、DSFCM和NEFCM算法受噪聲影響較小，仍能保持良好的性能，其中本文算法表現(xiàn)最優(yōu)，表明具有較強(qiáng)的魯棒性。

圖3和圖4是FCM算法和NEFCM算法在N3數(shù)據(jù)集上的聚類效果圖，可以看到，F(xiàn)CM算法對(duì)于簇間邊界處的樣本錯(cuò)分率較高，而NEFCM算法對(duì)這部分樣本劃分效果良好，原因是2簇邊界處的樣本與2個(gè)聚類中心的距離相差不大，僅根據(jù)歐氏距離無法保證正確劃分，NEFCM算法通過邊界樣本的鄰域隸屬度約束自身隸屬度，綜合考慮距離與鄰域樣本的隸屬情況，提升了邊界處樣本的聚類效果。

圖3 FCM算法在N3數(shù)據(jù)集上的聚類效果

圖4 NEFCM算法在N3數(shù)據(jù)集上的聚類效果

3.2 真實(shí)數(shù)據(jù)集實(shí)驗(yàn)

上述實(shí)驗(yàn)均為人造數(shù)據(jù)集，為了進(jìn)一步分析NEFCM算法的有效性，本節(jié)選取UCI數(shù)據(jù)庫中Iris、Wine等6個(gè)真實(shí)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，選取數(shù)據(jù)集的詳細(xì)信息如表2所示。

表2 實(shí)驗(yàn)使用的UCI數(shù)據(jù)集 單位：個(gè)

沿用FCM、KFCM、PCM、KPCM及DSFCM算法作為對(duì)比算法，NMI、RI作為聚類性能指標(biāo)，每個(gè)算法在每個(gè)數(shù)據(jù)集上分別運(yùn)行10次，取平均值作為實(shí)驗(yàn)結(jié)果如表3、表4所示。

表3 各算法在UCI真實(shí)數(shù)據(jù)集上的NMI對(duì)比

表4 各算法在UCI真實(shí)數(shù)據(jù)集上的RI對(duì)比

在6個(gè)UCI數(shù)據(jù)集上，從NMI指標(biāo)上看，F(xiàn)CM算法的平均值為0.531，KFCM算法的平均值為0.557，PCM算法的平均值為0.536，KPCM算法的平均值為0.549，DSFCM算法的平均值為0.523，而NEFCM算法的平均值為0.605，比FCM高出0.074，比KFCM高出0.048，比PCM高出0.069，比KPCM高出0.056，比DSFCM高出0.082。從RI指標(biāo)上看，F(xiàn)CM算法的平均值為0.743，KFCM算法的平均值為0.8，PCM算法的平均值為0.78，KPCM算法的平均值為0.785，DSFCM算法的平均值為0.79，而NEFCM算法的平均值為0.825，比FCM高出0.082，比KFCM高出0.025，比PCM高出0.045，比KPCM高出0.04，比DSFCM高出0.035。這表明NEFCM算法不僅在處理邊界模糊的數(shù)據(jù)集上展現(xiàn)出良好的性能，同時(shí)在處理真實(shí)數(shù)據(jù)集上有著不錯(cuò)的效果，進(jìn)一步驗(yàn)證了本文算法的實(shí)用價(jià)值。

3.3 時(shí)間復(fù)雜度分析

NEFCM算法的時(shí)間復(fù)雜度主要包含2個(gè)部分。第1部分是計(jì)算樣本的鄰域隸屬度權(quán)重，對(duì)于包含n個(gè)樣本的數(shù)據(jù)集來說，NEFCM計(jì)算n次樣本的鄰域隸屬度權(quán)重，因此這部分的時(shí)間復(fù)雜度表示為O(n×l)，其中l(wèi)表示樣本的鄰域數(shù)量；第2部分來自于算法聚類過程中，NEFCM分別迭代計(jì)算隸屬度矩陣U、鄰域隸屬度矩陣P、聚類中心矩陣V，這部分的時(shí)間復(fù)雜度表示為O(n×c×T)，其中，c為聚類中心個(gè)數(shù)，T為迭代次數(shù)。因此，整個(gè)NEFCM算法的時(shí)間復(fù)雜度為O(n×l+n×c×T)。

表5列出了NEFCM算法和其他對(duì)比算法的運(yùn)行時(shí)間。從表5可以看出，大多數(shù)情況下FCM算法的運(yùn)行時(shí)間比其他5種算法要短，其原因是FCM算法僅考慮樣本與聚類中心的歐氏距離，且在聚類過程中僅對(duì)隸屬度矩陣U、聚類中心矩陣V進(jìn)行迭代。大多數(shù)情況下KFCM、PCM、KPCM算法耗時(shí)較高，NEFCM算法在達(dá)到最佳聚類效果的情況下，消耗的時(shí)間比DSFCM算法略長，但基本上都快于KFCM、PCM、KPCM算法。

表5 6種算法的運(yùn)行時(shí)間 單位：s

4 結(jié)束語

本文針對(duì)FCM算法不能區(qū)分樣本各屬性對(duì)聚類過程的影響以及未有效利用鄰域信息的問題，提出了一種基于熵與鄰域約束的FCM算法。該算法首先通過計(jì)算樣本各屬性的熵值來為各屬性賦予權(quán)重，對(duì)距離計(jì)算函數(shù)進(jìn)行了改進(jìn)，然后利用樣本鄰域隸屬度約束目標(biāo)函數(shù)，進(jìn)而修正隸屬度迭代過程，最終達(dá)到提升FCM算法聚類性能的目的。本文從理論分析、人造數(shù)據(jù)集和多個(gè)UCI數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，并與DSFCM、FCM及其他3種FCM改進(jìn)算法進(jìn)行了對(duì)比分析，驗(yàn)證了NEFCM算法的有效性。