具有抗噪性能適用高維數(shù)據(jù)的增量式聚類算法*

邵俊健，王士同

江南大學(xué) 數(shù)字媒體學(xué)院，江蘇 無錫 214122

1 引言

聚類是機器學(xué)習(xí)和數(shù)據(jù)挖掘領(lǐng)域中的一種常用的數(shù)據(jù)分析工具，目前已被廣泛地應(yīng)用到生物、醫(yī)學(xué)、交通等領(lǐng)域中。在過去的幾十年中，有不少學(xué)者提出了各種各樣的方法來解決不同場景下的聚類問題[1-2]。聚類方法是將具有一定規(guī)則的樣本劃分成具有同種性質(zhì)的樣本集的過程，沒有先驗知識的指導(dǎo)，是屬于“無監(jiān)督學(xué)習(xí)”的一種方法。聚類分析的內(nèi)容包括系統(tǒng)聚類法、動態(tài)聚類法、圖論聚類法等。20世紀80 年代由Bezdek 學(xué)者提出的模糊C 均值聚類算法[3]（fuzzy C-means clustering，F(xiàn)CM）成為一種經(jīng)典的聚類算法，并且被有效地應(yīng)用在數(shù)據(jù)分析、圖像分割、數(shù)據(jù)挖掘等領(lǐng)域，具有實際應(yīng)用價值和重要的理論指導(dǎo)意義。隨著研究與應(yīng)用的進一步發(fā)展，對FCM算法的研究也在不斷豐富。

進入信息化時代以來，隨著信息技術(shù)的不斷發(fā)展，數(shù)據(jù)的不斷累積，存放于數(shù)據(jù)庫中的數(shù)據(jù)不斷增多，對于大規(guī)模的高維數(shù)據(jù)的分析成為一個亟待解決的問題，這一問題在文獻[4]中也曾被提及。如果對這些大規(guī)模高維數(shù)據(jù)依舊采用原始的聚類算法進行數(shù)據(jù)分析，可能會出現(xiàn)以下問題：（1）由于樣本量過大，原始數(shù)據(jù)將會無法加載進入內(nèi)存；（2）程序時間運行過長，嚴重占用計算機資源，降低算法性能等。針對以上問題，目前一般可以采用子空間聚類方法[5-6]、增量式聚類方法[7]來對大規(guī)模的高維數(shù)據(jù)進行有效的數(shù)據(jù)分析。

近年來，也有不少學(xué)者提出了許多不同的增量式聚類算法。李桃迎等人在文獻[8]中對各種不同的聚類算法進行了簡單的介紹。結(jié)合該文獻和近年來提出的一些新的增量式聚類算法，大致可以將增量式聚類算法的幾種改進方法分為：（1）在傳統(tǒng)的聚類算法上進行改進；（2）在生物智能基礎(chǔ)上進行改進；（3）對數(shù)據(jù)流的聚類算法。此外，Hore提出了單程模糊C 均值聚類算法[9]（single-pass fuzzy C-means，SpFCM）和在線模糊C 均值聚類算法[10]（online fuzzy C-means，OFCM）。Mei 等人在SpFCM 和OFCM 算法的基礎(chǔ)上進行改進提出適用于對高維數(shù)據(jù)進行聚類的算法[11-12]。Wang 等人提出適合用于大規(guī)模數(shù)據(jù)集的多中心增量模糊聚類算法（incremental multiple medoids based fuzzy clustering，IMMFC）[13]。

FCM 算法是一種基于劃分的聚類算法，在數(shù)據(jù)集存在異常數(shù)據(jù)的情況下，通常無法準確地對異常數(shù)據(jù)進行處理，亦就是說FCM 算法對噪聲數(shù)據(jù)有很大的敏感性。研究者們通常對FCM算法的目標函數(shù)進行修改或者采用新的聚類算法，提出新的可以適用于并且有效處理含有噪聲數(shù)據(jù)的算法。石文峰等人[14]通過擴展決策粗糙模糊集模型進行聚類的有效分析來確定FCM 算法的聚類數(shù)，可以避免初始化結(jié)果不好的缺點。劉滄生等人[15]在密度峰值聚類算法[16-17]的基礎(chǔ)上，提出基于密度峰值優(yōu)化的模糊C 均值聚類算法。該算法能更準確地得到聚類簇的數(shù)目，性能有明顯的提高。前者是有明顯的圖像分割效果，后者相比于FCM 可以有更少的迭代次數(shù)和更快的效率，但是以上兩種算法沒有提及噪聲或是高維數(shù)據(jù)對聚類算法產(chǎn)生的影響。陳加順等人[18]提出的非噪聲敏感性FCM算法能夠有效克服對噪聲的敏感性，從而提高算法的效率。該算法在人工生成的服從高斯分布的數(shù)據(jù)集上可以得到相對于FCM較好的聚類結(jié)果，但是沒有考慮到將實驗用于區(qū)間數(shù)據(jù)集上進行進一步的實驗分析。張辰等人[19]結(jié)合樣本加權(quán)的知識，在Zhang等人提出的改進可能模糊C均值聚類算法（improved possibilistic C-means clustering，IPCM）[20]基礎(chǔ)上提出一種概率模糊聚類新算法。該算法雖然具有處理大量噪聲數(shù)據(jù)的能力，但是在噪聲少或沒有的情況下，其聚類效果并不是特別明顯。此外，該算法僅是在低維數(shù)據(jù)的情況下分析，沒有考慮在含有噪聲的高維數(shù)據(jù)集的聚類效果。武斌等人[21]為了克服廣義噪聲聚類算法（generalized noise clustering，GNC）[22-23]對于參數(shù)選擇和運行該算法之前必須運行FCM 算法來獲取參數(shù)的缺點，結(jié)合可能聚類算法（possibilistic clustering algorithm,PCA）[24]提出一種快速的具有更快速度和更高準確率的廣義噪聲聚類算法（fast generalized noise clustering,FGNC）。該算法可以很好地處理含有噪聲數(shù)據(jù)，聚類準確性高且聚類時間更短，從文中實驗來看，該算法沒有處理高維機制下對聚類算法產(chǎn)生的影響。

為了克服FCM算法對初始化聚類中心敏感的問題以及高斯噪聲在高維數(shù)據(jù)進行聚類分析時會產(chǎn)生的影響，本文使用文獻[25]中提出的模糊（c+p）均值聚類算法（fuzzy(c+p)means clustering，F(xiàn)CPM）中的初始化聚類中心的方法。即通過FCPM 算法計算當(dāng)前數(shù)據(jù)子塊的聚類中心，并且將距離聚類中心最近的部分樣本點加入到下一個即將進行聚類的數(shù)據(jù)子塊中進行聚類。此外，使用一種適合于含有高斯噪聲的高維數(shù)據(jù)的新的距離度量方式來減少高斯噪聲在高維數(shù)據(jù)進行聚類分析時帶來的影響，本文提出一種適用于高維數(shù)據(jù)且含有高斯噪聲的聚類算法ANFCM(c+p)（anti-noise fuzzy(c+p)means clustering）。

2 相關(guān)工作

2.1 模糊C均值聚類算法

假設(shè)X=(x1,x2,…,xn),X是一個含有N個樣本的集合，其中xk(k=1,2,…,n)表示集合X中的一個樣本。FCM算法的目標是將這N個樣本按照其固有的特征屬性劃分成c(1≤c≤N)類。Bezdek 定義FCM 的目標函數(shù)如式（1）所示：

其中，U∈Uf為X的模糊隸屬度矩陣，V={v1,v2,…,vc}表示聚類中心，uik表示第k個樣本屬于第i類的隸屬程度，||xk-vi||表示樣本xk與vi的歐氏距離，m為模糊指數(shù)。通過式（1）和拉格朗日乘子法可以求出隸屬度矩陣U和聚類中心V的迭代公式，如式（2）、式（3）。

對于模糊C均值聚類算法而言，需要滿足以下三個條件：

在本文中由于篇幅原因，對FCM 算法的具體步驟和迭代計算不做詳細介紹，該算法的基本思想可以參看文獻[3]。

2.2 FCPM聚類算法

傳統(tǒng)的FCM 算法對于聚類中心的初始化很敏感，常常會得到局部最優(yōu)解，其聚類效果不是特別穩(wěn)定。在FCPM算法中，采用將已知的一類固定來計算另一類的方法。在該方法下，某一類的聚類中心會吸引屬于該類的樣本，而排斥來自其他類的樣本。

假設(shè)有c個聚類中心來自同一類，有p個聚類中心來自另外一類，F(xiàn)CPM 算法的任務(wù)是將這N個樣本集合劃分成c個類，其目標函數(shù)如式（4）所示：

式（4）中的uik與tjk需要滿足式（5）的約束條件：

在式（4）中，Q=[q1,q2,…,qc]∈Rd×c，即Q為c個聚類中心所構(gòu)成的矩陣。Z=[z1,z2,…,zp]∈Rd×p，即Z為已知的p個聚類中心所構(gòu)成的矩陣。U=[uik]∈[0,1]c×N與T=[tjk]∈[0,1]p×N分別代表的是未知類和已知類的模糊隸屬度矩陣。uik代表第k個樣本xk與聚類中心qi的隸屬度，tjk代表第k個樣本xk與聚類中心zj的隸屬度。

根據(jù)拉格朗日乘子法，式（4）在滿足式（5）的約束條件下，可以求解得到模糊隸屬度矩陣U和T以及聚類中心V的計算公式：

在文獻[25]中，作者對FCPM算法的隸屬度矩陣和聚類中心的解法進行了詳細的介紹。此外，由于FCM 算法對于初始化聚類中心敏感性的問題，在該文中，作者通過FCPM算法初始化未知類的聚類中心V，依舊用原始的FCM算法初始化已知類的聚類中心Z，最后通過式（6）～式（8）迭代計算得到模糊隸屬度矩陣U和聚類中心V，算法的具體步驟見FCPM 算法的描述。

算法1FCPM算法

步驟1設(shè)置一個空索引，記為l。

步驟2計算每個樣本點的幾何中心xmean=

步驟3計算各個樣本到幾何中心的距離，ak=||xk-xmean||,k=1,2,…,N。

步驟4找出距離幾何中心最近的樣本點xl1作為新的聚類中心加入集合A。

步驟5計算bk=ak||xl-xk||,k=1,2,…,N。

步驟6找出距離bk最遠的樣本點xl2作為第二個聚類中心加入集合A。

步驟7重復(fù)步驟6直至有c個聚類中心。

步驟8通過vk=xlk-0.1(xlk-xmean)計算聚類中心，其中k=1,2,…,N;l={l1,l2,…,lc}。該式中的系數(shù)0.1不是必要的，它可以加快聚類方法的收斂速度，并且減少邊遠數(shù)據(jù)的影響。

3 具有抗噪性能的增量式模糊聚類算法

3.1 ANFCM(c+p)

傳統(tǒng)的FCM 算法對聚類中心敏感，導(dǎo)致一般的基于FCM算法的增量式聚類算法也有此問題。針對這一問題，文中使用FCPM算法中提及的一種新方法來初始化聚類中心。以往，原有的SpFCM 和OFCM算法都是通過WFCM（weighted fuzzy C-means clustering algorithm）算法進行加權(quán)，即通過賦予每個數(shù)據(jù)塊的樣本不同的權(quán)值來進行聚類，從而影響其聚類結(jié)果。但是數(shù)據(jù)塊之間聚類中心的相互影響程度可能會由于上一次聚類結(jié)果的加入而影響聚類結(jié)果。本文不采用加權(quán)的方式賦予各個樣本不同的權(quán)值，而是將經(jīng)過上一次聚類的數(shù)據(jù)子塊的聚類中心附近的部分樣本點加入到下一個數(shù)據(jù)子塊進行聚類。通過計算樣本點到距離中心的距離，可以快速地獲取需要添加到下一個數(shù)據(jù)子塊的樣本點。同時在算法的目標函數(shù)中添加一個相關(guān)項用來維持原數(shù)據(jù)塊之間聚類中心的相互影響程度，其中β稱為相關(guān)因子。當(dāng)β=0 時，算法不考慮數(shù)據(jù)塊間聚類中心的影響，僅僅考慮了某一數(shù)據(jù)塊的聚類中心及其周圍的幾個樣本點對下一個數(shù)據(jù)塊的聚類性能的影響。當(dāng)β≠0 時，既考慮數(shù)據(jù)塊間聚類中心的影響，又考慮到某一數(shù)據(jù)塊的聚類中心及其周圍的幾個樣本點對下一個數(shù)據(jù)塊的聚類性能的影響。在FCPM 算法中，uik與tjk需要滿足式（5）的約束，為了能區(qū)別已知類和未知類在算法中的重要性程度，在原FCPM算法中的約束條件里加入一個判別因子λ，如式（9）所示。

在式（9）中，根據(jù)λ的不同取值，可以從以下兩方面進行分析。

第一種情況，當(dāng)λ=0 時，式（9）就變成了傳統(tǒng)的FCM 算法的約束條件。根據(jù)前文中提到的FCM 算法對初始化聚類中心敏感性的問題，當(dāng)λ=0 時，所提出的算法也會對初始化聚類中心敏感，因此在文中實驗時，不對λ=0 這一情況進行討論和分析。

第二種情況，當(dāng)λ=1 時，式（9）即為原FCPM 算法的約束條件，即把c個未知類和p個已知類在算法中賦予相同的權(quán)值，不區(qū)分兩種類的不同影響程度，與原FCPM算法無異。

結(jié)合以上分析，為了能更好地區(qū)分已知類和未知類的影響程度以及體現(xiàn)本文算法的優(yōu)越性，一般實驗的時候不考慮以上兩方面所述。當(dāng)λ值大于0且小于1 時，說明已知類在算法中的影響程度并不高，而當(dāng)λ大于1 時，說明未知類在算法中的影響程度不高。

結(jié)合文獻[26]在大量高維數(shù)據(jù)的實驗場景中對各種不同距離度量的討論，可以從其實驗結(jié)果中看出余弦距離處理高維數(shù)據(jù)時能獲得較好的結(jié)果。在文獻[27-29]中，作者均指出余弦距離在高維海量數(shù)據(jù)集中能有效地度量樣本之間的相似性。在高維數(shù)據(jù)中，隨著數(shù)據(jù)維度的不斷增加，數(shù)據(jù)將變得越來越稀疏，傳統(tǒng)的歐式距離是用向量之間的間隔長度大小衡量距離，在面對高維數(shù)據(jù)時，通過其計算的相似性幾乎是完全一致的，不能很好地判斷兩個樣本之間的差異。余弦距離是通過計算兩個向量之間的夾角來衡量兩個樣本之間的相似度。對于任意兩個向量x=(x1,x2,…,xn)和y=(y1,y2,…,yn)，由數(shù)學(xué)知識余弦相似度為兩個向量夾角的余弦，即：

根據(jù)文獻[26]對余弦距離的描述，可以使用如式（11）所示的余弦距離公式。

對于一個數(shù)據(jù)集X={x1,x2,…,xn}，任取其中的兩個樣本記為X和Y，分別對這兩個樣本加入一定的高斯噪聲ε1=(0,σ)和ε2=(0,σ)，其中0表示高斯噪聲的均值，σ表示高斯噪聲的標準差。設(shè)加入高斯噪聲后的兩個樣本分別記為X′和Y′，其中X′=X+ε1，Y′=Y+ε2。分別計算在加入高斯噪聲之后的兩個樣本在均值情況下式（11）的后半項的分子和分母，如式（12）所示：

根據(jù)數(shù)學(xué)期望的性質(zhì)和加入的高斯噪聲的特點，可以將式（12）化簡得到式（13）：

那么，根據(jù)式（13）可以推出一個適用于含有高斯噪聲的樣本集的新的距離公式，如式（14）所示：

其中，Δ=ε2，Δ指的是所加入的高斯噪聲的方差。

在式（15）中，uik是第k個樣本相對于第i類的隸屬度，qi是第i類的聚類中心，tjk是第k個樣本相對于第j類的隸屬度，zj是已知的p個類的聚類中心，是由FCPM算法計算得到的新的聚類中心。

采用拉格朗日乘子法對式（15）在滿足式（9）的約束條件下求解新的隸屬度矩陣U和T,新的聚類中心Q。

對式（16）中的P(U,T,Q,λk)的各變量分別求偏導(dǎo)并且令其等于0，得到式（17）所示的等式。

對式（17）求解可以得到隸屬度uik和tjk以及聚類中心qi的計算公式（18）。

從式（18）可以看出，更新過后的模糊隸屬度矩陣U和T與相關(guān)因子β的取值無關(guān)，更新過后的聚類中心qi在β等于0 或者不等于0 時又分為兩種情況討論。當(dāng)β=0 時，從目標函數(shù)式（14）就可以看出忽略了數(shù)據(jù)塊之間聚類中心的相互影響，為了能更好地提高算法性能，一般考慮β不等于0的情況。

3.2 算法實現(xiàn)

通過結(jié)合FCPM 算法中提及的新初始化中心的方法，給出ANFCM(c+p)算法的具體步驟。

算法2ANFCM(c+p)

輸入：樣本集X，未知類的類數(shù)c，已知類的類數(shù)p，模糊指數(shù)m，迭代終止條件ε，聚類中心臨近點數(shù)a。

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

步驟1將樣本集X根據(jù)不同增量比例隨機劃分成大小相等的t個子集，即X={x1,x2,…,xt}。

步驟2設(shè)置兩個空集合Xnear和Xnew。Xnew用來存放每一個數(shù)據(jù)塊產(chǎn)生的聚類中心，Xnear用于存放聚類中心附近的a個樣本點。

步驟3依次循環(huán)對每一個數(shù)據(jù)塊遍歷獲取聚類中心。

（1）初始化未知類和已知類的聚類中心Q和Z。

（2）將通過上一個數(shù)據(jù)塊處理得到的樣本集Xnear添加到當(dāng)前數(shù)據(jù)塊中，即Xc={Xc?Xnear}。

（3）通過式（17）計算當(dāng)前數(shù)據(jù)塊更新過后的隸屬度矩陣U和T以及聚類中心Ql。

（4）將距離聚類中心Ql最近的a個樣本點存入Xnew中。

（5）將聚類中心Ql及其附近的a個樣本點存入Xnear中，即Xnear={Ql?Xnew}。

步驟4循環(huán)結(jié)束，得到隸屬度矩陣U。

在步驟3 中，初始化聚類中心的方法是采用FCPM 算法來初始化未知類的聚類中心，采用原FCM 算法來初始化已知類的聚類中心。FCPM 算法的迭代停止條件為目標函數(shù)的連續(xù)變化值小于迭代終止條件ε，當(dāng)所有子集數(shù)據(jù)塊都遍歷完畢獲得最終的聚類中心Q和隸屬度矩陣U時，整個ANFCM(c+p)算法結(jié)束。

ANFCM(c+p)算法通過FCPM 算法中提及的初始化聚類中心的方法和新的距離度量公式，用來對含有高斯噪聲的高維數(shù)據(jù)進行聚類分析。此外，通過判別已知類的重要性程度和數(shù)據(jù)塊的c個聚類中心及其附近的a個樣本點作為輔助聚類信息加入到下一個即將進行聚類的數(shù)據(jù)子塊中，從而來提高算法的聚類效果，并且保持算法良好的魯棒性。

4 實驗研究

為了對各聚類算法的聚類效果做出評價，本文采用歸一化互信息（normalized mutual information，NMI）和蘭德指數(shù)（rand index，RI）對算法性能進行分析。首先，為了分析加入不同樣本點的個數(shù)對算法產(chǎn)生的影響，選擇兩個數(shù)據(jù)集進行簡單的實驗，主要分析不加入樣本點和加入不同個數(shù)樣本的ANFCM(c+p)算法的性能。其次，選擇FCPM 算法、IFCM(c+p)（incremental fuzzy(c+p)means clustering）算法以及SpFCM 算法作為對比算法，將不同的噪聲加入后與ANFCM(c+p)算法進行對比，從而驗證算法的有效性。通過文獻[9]對SpFCM 算法的介紹，可以計算SpFCM 算法的時間復(fù)雜度為O(ndT′c2)。通過文獻[21]對FCPM 算法的介紹，可以計算FCPM 算法的時間復(fù)雜度為O(Tnd(c+p)+T′c)，其中T指的是算法迭代次數(shù)，n是樣本數(shù)目，d是樣本維度，c是未知類的類數(shù)，p是已知類的類數(shù)。由于FCPM算法不是增量式的算法，但是SpFCM、IFCM(c+p)和ANFCM(c+p)是增量式的，因此在其時間復(fù)雜度的計算中，需要對每個不同增量比例的數(shù)據(jù)塊的迭代次數(shù)求其平均才是IFCM(c+p)和ANFCM(c+p)的時間復(fù)雜度，即O(T′nd(c+p)+T′c)，T′即為每個數(shù)據(jù)塊的平均迭代次數(shù)。

4.1 評價指標

（1）歸一化互信息（NMI）[30-31]

在式（19）中，N是指該數(shù)據(jù)集的樣本總數(shù)，Ai指經(jīng)本文聚類算法之后第i類的樣本總數(shù)，Bj指真實數(shù)據(jù)集的第j類的樣本總數(shù)，Ri,j是指第i類與第j類的共有樣本總數(shù)。

（2）蘭德指數(shù)（RI）[30-32]

在式（20）中，N為該數(shù)據(jù)集的樣本總數(shù)，a指經(jīng)本文聚類算法之后與實際類別信息中同類別的樣本個數(shù)，b指經(jīng)本文聚類算法之后與實際類別信息中不同類別的樣本個數(shù)。

NMI與RI指標的取值范圍均在[0,1]之間，其中當(dāng)值越接近1 越能反映該聚類算法在某一數(shù)據(jù)集上的聚類效果越好，越靠近0時說明該算法在這一數(shù)據(jù)集上的聚類效果越差。

4.2 實驗結(jié)果

4.2.1 實驗環(huán)境

文中的實驗在表1所示的實驗環(huán)境中進行。

4.2.2 實驗數(shù)據(jù)集

在實驗中使用的數(shù)據(jù)集包括人臉表情數(shù)據(jù)集jaffe（http://www.kasrl.org/jaffe.html）、人臉數(shù)據(jù)庫ORL數(shù)據(jù)集（http://www.cl.cam.ac.uk/Research/DTG/attarchive:pub/data/att_faces.tar.Z）、Coil 數(shù)據(jù)集、warp-AR10P數(shù)據(jù)集（http://featureselection.asu.edu/datasets.php）、Bin-alpha 數(shù)據(jù)集、MSRA 數(shù)據(jù)集（https://mmcheng.net/msra10k/）。各數(shù)據(jù)集的具體參數(shù)如表2所示。

Table 1 Experiment environment表1 實驗環(huán)境

Table 2 Parameters of datasets表2 數(shù)據(jù)集的具體參數(shù)

4.2.3 實驗參數(shù)設(shè)置

文中實驗的參數(shù)設(shè)置為：模糊指數(shù)m取值為1.5，最大迭代次數(shù)max_iter取值為100，迭代終止參數(shù)min_impro取值為1E-3，在新初始化聚類中心方法（即FCPM算法）中距聚類中心最近的樣本點n0取值為5，對各個數(shù)據(jù)集樣本點在1 000 以下的數(shù)據(jù)集重復(fù)進行20次實驗，對數(shù)據(jù)集的樣本點在1 000以上的重復(fù)進行15次實驗。由于是基于增量式方法的聚類算法，因此實驗中每次加載進入內(nèi)存的數(shù)據(jù)塊大小是不同的。根據(jù)表2所示的數(shù)據(jù)集的樣本總數(shù)，結(jié)合考慮IFCM算法初始化聚類中心的特點，分別對jaffe、ORL和Coil數(shù)據(jù)集樣本總數(shù)的5%、10%、20%、25%、50%，對warpAR10P 數(shù)據(jù)集樣本總數(shù)的10%、20%、30%、40%和50%，對MSRA 和Bin-alpha 數(shù)據(jù)集的1%、5%、10%、20%、25%和50%隨機抽取進行增量聚類。由于MSRA 和binalpha 數(shù)據(jù)集的樣本點無法合理地按照以上增量比例進行實驗，在本文中一般隨機選取MSRA數(shù)據(jù)集的1 700個樣本點和binalpha數(shù)據(jù)集的1 400個樣本點進行實驗。在本文實驗中，設(shè)置已知類p的值為按照不同比例進行增量的小數(shù)據(jù)塊中最后一塊的類的個數(shù)。例如，對于Coil數(shù)據(jù)集，當(dāng)選取5%的樣本進行增量聚類時，每一個數(shù)據(jù)小塊的樣本數(shù)是72，把最后一個小數(shù)據(jù)塊即第1 369到第1 440 的樣本的類別數(shù)目作為p值。此外，還對參數(shù)相關(guān)因子β進行參數(shù)尋優(yōu)，其尋優(yōu)范圍分別在{0.1,0.2,…,1.0}。

4.2.4 算法性能比較

第一部分實驗，選擇Coil、jaffe兩個數(shù)據(jù)集，在每次聚類時，加入不同個數(shù)的樣本點到下一個聚類數(shù)據(jù)子塊中。由隸屬度矩陣計算得到的NMI和RI評價指標分析結(jié)果如圖1和圖2所示。

根據(jù)圖1和圖2的實驗結(jié)果來看，在不加入樣本點的情況下，在增量比例較小的情況下，其聚類效果比較好，但是當(dāng)增量比例逐漸增大時，其聚類效果就低于加入樣本點到下一個數(shù)據(jù)子塊中去聚類的情形?？傮w來說，加入聚類中心附近的樣本點到下一個要聚類的數(shù)據(jù)子塊中進行聚類是可以得到較好的聚類結(jié)果。此外，加入不同個數(shù)的樣本點同樣也會對算法產(chǎn)生一定的影響。在不同增量比例時，樣本點個數(shù)的加入也會有不同的結(jié)果。在文中加入聚類中心附近的樣本點是為了考慮數(shù)據(jù)塊之間聚類中心的相互影響。

第二部分實驗，在表2所示的數(shù)據(jù)集上分別添加均值為0，標準差為0.3 和2.0 的高斯噪聲后，將ANFCM(c+p)與非增量式的FCPM 算法、增量式的SpFCM 算法和IFCM(c+p)算法進行對比實驗，計算經(jīng)過以上4 個算法聚類得到的隸屬度矩陣而得出的NMI和RI評價指標，如表3～表14所示，表中加粗的結(jié)果即是在文中所示實驗環(huán)境下，模糊指數(shù)m為1.5時的結(jié)果。

Fig.1 NMI of Coil and jaffe with different samples圖1 Coil和jaffe數(shù)據(jù)集加入不同樣本點后的NMI值

Fig.2 RI of Coil and jaffe with different samples圖2 Coil和jaffe數(shù)據(jù)集加入不同樣本點后的RI值

從表中的實驗結(jié)果可以看出，雖然FCPM算法在一兩個數(shù)據(jù)集里得到的RI和NMI評價指標比較好，但是在大部分情況下，該算法相比于增量式的聚類算法的聚類效果并不是特別理想。隨著維度逐漸增加，從表中實驗結(jié)果看出ANFCM(c+p)算法具有良好的抗噪性能。在給樣本添加高斯噪聲后，ANFCM(c+p)算法的抗噪性能在大部分情況下是優(yōu)于實驗中三種對比算法的。而對以上數(shù)據(jù)集加入不同標準差的高斯噪聲時，可以看出當(dāng)高斯噪聲的方差比較大時，ANFCM(c+p)算法在多數(shù)情況是能比其余三種算法得到更好的聚類結(jié)果。而噪聲方差比較小時，三種不同的增量式算法都在不同增量比例時達到最好的聚類結(jié)果。在Coil數(shù)據(jù)集中，本文所提出的ANFCM(c+p)算法是完全擁有了良好的抗噪性能。當(dāng)樣本的數(shù)量比較多的情況下，無論是噪聲方差比較大或較小的情況下，ANFCM(c+p)相比而言，更能得到良好的聚類結(jié)果。在表2所有的數(shù)據(jù)集中進行實驗時，亦可以發(fā)現(xiàn)，隨著樣本增量比例逐漸增加至50%左右，其聚類效果一般是低于增量比例較小的數(shù)據(jù)塊。這是由于，當(dāng)增量比例較大的時候，進行聚類的數(shù)據(jù)塊是趨向于對整個數(shù)據(jù)集進行數(shù)據(jù)分析，與傳統(tǒng)的非增量式聚類算法沒有差別，一般情況下，其聚類性能是比較低的。因此，在使用增量式聚類算法的時候，選擇一個合適的樣本比例是一個重要的選擇。ANFCM(c+p)算法在使用新的距離度量時，考慮到新增加進來高斯噪聲的影響，將這部分影響在進行聚類之前就將其減去，相比于傳統(tǒng)的歐氏距離其聚類效果是有很大提升的。

Table 3 NMI of Coil dataset表3 Coil數(shù)據(jù)集的NMI 值

Table 4 NMI of warpAR10P dataset表4 warpAR10P數(shù)據(jù)集的NMI 值

Table 5 NMI of MSRA dataset表5 MSRA數(shù)據(jù)集的NMI 值

Table 6 NMI of Bin-alpha dataset表6 Bin-alpha數(shù)據(jù)集的NMI 值

Table 7 NMI of ORL dataset表7 ORL數(shù)據(jù)集的NMI 值

Table 8 NMI of jaffe dataset表8 jaffe數(shù)據(jù)集的NMI 值

Table 9 RI of Coil dataset表9 Coil數(shù)據(jù)集的RI 值

Table 10 RI of warpAR10P dataset表10 warpAR10P數(shù)據(jù)集的RI 值

Table 11 RI of MSRA dataset表11 MSRA數(shù)據(jù)集的RI 值

Table 12 RI of Bin-alpha dataset表12 Bin-alpha數(shù)據(jù)集的RI 值

Table 13 RI of ORL dataset表13 ORL數(shù)據(jù)集的RI 值

Table 14 RI of jaffe dataset表14 jaffe數(shù)據(jù)集的RI 值

5 結(jié)束語

本文從兩個角度出發(fā)，一個是高維數(shù)據(jù)，另一個是含有高斯噪聲的樣本，提出了一種具有良好抗噪性能的ANFCM(c+p)算法。為了能有效地處理高維數(shù)據(jù)，該算法基于余弦距離度量進行改進用于處理含有高斯噪聲的高維數(shù)據(jù)。余弦距離可以有效地對高維數(shù)據(jù)進行樣本間相似性的計算，具有良好的魯棒性。為了解決原FCM算法對初始化聚類中心敏感的問題，該算法使用FCPM 算法初始化聚類中心，綜合考慮已知類和未知類在算法中的重要性程度，來有效提升含高斯噪聲的樣本的聚類性能。從第4 章的實驗結(jié)果分析，文中提出的ANFCM(c+p)算法確實可以提高含有高斯噪聲的數(shù)據(jù)集的聚類性能。文中兩個值，相關(guān)因子β和約束條件式（9）中的λ是在實驗中根據(jù)經(jīng)驗和大量參數(shù)尋優(yōu)而得，而這兩個值又是ANFCM(c+p)算法的關(guān)鍵所在，如何合適地選取是下一步的研究方向。根據(jù)文中實驗結(jié)果的分析，選取一個合適的增量比例進行增量聚類也是一個可以研究的方向。此外，噪聲的類別不只高斯噪聲，還有如重尾噪聲、拖尾噪聲等，對于如何處理這些噪聲也是一個可以繼續(xù)研究的方向。