基于自適應(yīng)近鄰信息的模糊C 均值聚類算法

高云龍，李建鵬，鄭興莘，邵桂芳，祝青園，曹 超

（1.廈門大學(xué) 薩本棟微米納米科學(xué)技術(shù)研究院，福建 廈門 361102；2.廈門大學(xué) 自動(dòng)化系，福建 廈門 361102；3.自然資源部 第三海洋研究所，福建 廈門 361005）

1 引言

作為一種無(wú)監(jiān)督方法，聚類的基本任務(wù)是將數(shù)據(jù)點(diǎn)劃分為不相交的簇，使得同一簇內(nèi)數(shù)據(jù)點(diǎn)之間的相似度最大化，而不同簇之間數(shù)據(jù)點(diǎn)的相似度最小化。在文本分析方面，聚類算法可以將市場(chǎng)細(xì)分為不同的消費(fèi)者群體，幫助企業(yè)了解不同群體的需求和偏好，有助于市場(chǎng)營(yíng)銷策略的制定和產(chǎn)品定價(jià)。在計(jì)算機(jī)視覺領(lǐng)域，聚類算法可以將圖像分割為不同的區(qū)域或?qū)ο螅怀霾煌瑓^(qū)域之間色塊的差異和相同區(qū)域色塊的相似，從而實(shí)現(xiàn)圖像分析和目標(biāo)檢測(cè)等任務(wù)。聚類算法可以用于分析基因表達(dá)數(shù)據(jù)，幫助研究人員識(shí)別基因表達(dá)模式并發(fā)現(xiàn)疾病相關(guān)基因。數(shù)據(jù)當(dāng)中的異常點(diǎn)或離群點(diǎn)可以通過聚類算法進(jìn)行檢測(cè)，可應(yīng)用于故障診斷和網(wǎng)絡(luò)安全等領(lǐng)域?？偟膩碚f，聚類算法在模式識(shí)別、圖像處理和數(shù)據(jù)挖掘等領(lǐng)域有著十分廣泛的應(yīng)用，可以幫助人們分析數(shù)據(jù)，理解數(shù)據(jù)的本質(zhì)結(jié)構(gòu)特征，從數(shù)據(jù)中獲取有用信息。

當(dāng)標(biāo)簽信息不可用時(shí)，將數(shù)據(jù)分區(qū)成不同的塊是很困難的。為了解決這個(gè)問題，聚類算法被提出，用以探索樣本之間的內(nèi)在相關(guān)性和差異。在過去的幾十年里，許多類型的聚類算法被提出，具有代表性的有K-Means 聚類［1］、模糊C 均值聚類［2-4］和譜聚類［5］等。其中，由于算法理論的簡(jiǎn)單高效，K-Means 聚類和模糊C 均值聚類引起了很多關(guān)注。K-Means 聚類也被稱為硬聚類，其中每個(gè)樣本被分配到距離最近的聚類原型。然而，隨著信息技術(shù)的高速發(fā)展，數(shù)據(jù)的維度和規(guī)模也在快速增長(zhǎng)，維數(shù)災(zāi)難問題出現(xiàn)，高維空間中的樣本分布復(fù)雜，各個(gè)類別之間的邊界模糊不清。因此，K-Means 聚類的性能會(huì)受到嚴(yán)重影響。為了解決這個(gè)問題，模糊C 均值聚類（Fuzzy CMeans Clustering，F(xiàn)CM）算法被提出。對(duì)于FCM 聚類，根據(jù)隸屬度將樣本與每個(gè)類別相關(guān)聯(lián)，并使用模糊指數(shù)來控制隸屬度的稀疏性。Yu等分析了選擇適當(dāng)?shù)哪：笖?shù)的規(guī)則，并在多個(gè)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。結(jié)果表明，在大多數(shù)情況下，推薦使用［1.5，2.5］的范圍［6-7］。

FCM 聚類面臨的常見問題是對(duì)噪聲和異常值的敏感性。為了解決該問題，研究人員采用稀疏規(guī)范化來減少異常值的干擾，通常將FCM算法中距離的度量方式從平方范數(shù)替換為一種稀疏范數(shù)，通過這種方式，異常值對(duì)目標(biāo)函數(shù)的貢獻(xiàn)將被抑制。Xu 等提出了一種穩(wěn)定的FCM算法，使用l2，1范數(shù)和截?cái)嗟膌1范數(shù)替換原有的平方范數(shù)，分別構(gòu)建了兩個(gè)模糊聚類模型并提出了兩種迭代加權(quán)算法來求解［8］。Chang 等通過使用稀疏規(guī)范化范數(shù)（lp范數(shù)）重新構(gòu)造FCM目標(biāo)函數(shù)，提出了一個(gè)非凸優(yōu)化模型，通過這種方式評(píng)估每個(gè)特征對(duì)目標(biāo)函數(shù)的貢獻(xiàn)［9］。Zhang等修改譜聚類，并提出了一種模糊聚類和譜聚類結(jié)合的算法，引入σ-norm，以自適應(yīng)地提高FCM 對(duì)微小或較大異常值的穩(wěn)定性［10-11］。另一種方法是引入局部空間信息，為了提高圖像分割的性能，Chuang 等提出了一個(gè)兩步過程的FCM 算法［12］。在第一步中，通過常規(guī)FCM 算法獲得隸屬度矩陣。之后，通過空間信息更新該矩陣的元素，其中每個(gè)像素都落在一個(gè)小窗口中，其屬于某個(gè)類別的概率由窗口中各像素屬于該類別的概率的加權(quán)平均值確定。Cai 等將局部空間關(guān)系和局部灰度關(guān)系都納入模糊聚類模型中，以保證圖像的抗噪性和保留細(xì)節(jié)的能力［13］。Nie 等基于距離較小的數(shù)據(jù)點(diǎn)應(yīng)該具有更大的概率成為鄰居這一前提假設(shè)，提出了一種新的視角來解決聚類問題，為每個(gè)數(shù)據(jù)點(diǎn)分配自適應(yīng)最優(yōu)近鄰，基于局部連通性學(xué)習(xí)數(shù)據(jù)相似性矩陣；并對(duì)學(xué)習(xí)到的相似性矩陣的拉普拉斯矩陣施加秩約束，以實(shí)現(xiàn)理想的鄰居分配，從而使數(shù)據(jù)中的連通分量恰好等于聚類數(shù)，并且每個(gè)連通分量對(duì)應(yīng)一個(gè)簇，以達(dá)到優(yōu)異的聚類結(jié)果［14］。上述算法主要依賴于數(shù)據(jù)的原始分布結(jié)構(gòu)進(jìn)行聚類。然而，現(xiàn)實(shí)世界中的數(shù)據(jù)往往包含噪聲，數(shù)據(jù)中的噪聲可能破壞其結(jié)構(gòu)并影響聚類結(jié)果。受收縮模式［15-17］的思想啟發(fā)，研究人員通過在靈活的流形上進(jìn)行聚類，而不是在原始數(shù)據(jù)空間中，可以避免噪聲對(duì)數(shù)據(jù)結(jié)構(gòu)的影響。為了獲得原始數(shù)據(jù)合適的流形結(jié)構(gòu)，進(jìn)行收縮模式的學(xué)習(xí)。收縮模式可以視為一種映射，它將數(shù)據(jù)映射到具有相同維數(shù)，但不是更低維數(shù)的靈活流形上。流形空間比原始數(shù)據(jù)空間具有更好的抵抗噪聲，能增強(qiáng)聚類的穩(wěn)定性［18］。

受局部結(jié)構(gòu)信息在提升聚類性能的多個(gè)成功算法應(yīng)用的啟發(fā)，本文提出了一種基于自適應(yīng)近鄰信息的模糊C 均值聚類算法（Adaptive Neighour Fuzzy C-Means，ANFCM）。具體來說，對(duì)于每個(gè)樣本點(diǎn)，根據(jù)其余樣本點(diǎn)與其歐氏距離度量，基于距離較近的樣本點(diǎn)成為近鄰的可能性更大這一先驗(yàn)假設(shè)，挖掘數(shù)據(jù)的局部結(jié)構(gòu)信息指導(dǎo)聚類過程，從而達(dá)到減弱噪聲、離群點(diǎn)影響的作用。首先，通過近鄰信息學(xué)習(xí)樣本點(diǎn)的相似性以及簇中心和樣本點(diǎn)之間的相似性，挖掘簇中心和樣本點(diǎn)局部結(jié)構(gòu)信息，指導(dǎo)聚類過程；其次，將上述兩種相似性引入傳統(tǒng)FCM 框架，補(bǔ)償FCM 單一歐式距離平方的度量方式，使得算法在考慮全局聚類結(jié)構(gòu)的同時(shí)，也能關(guān)注局部鄰域信息，提升算法的穩(wěn)定性，降低對(duì)噪聲和異常值的敏感性。

2 相關(guān)工作

2.1 模糊C 均值聚類和K 均值聚類

FCM 是最早提出的處理重疊聚類的算法之一。FCM 的核心是將每個(gè)數(shù)據(jù)點(diǎn)根據(jù)隸屬度分配到多個(gè)聚類原型中。形式上，給定一個(gè)數(shù)據(jù)集X=[x1，x2，…，xn]∈Rd×n，其中d是維度，n是數(shù)據(jù)集中樣本點(diǎn)的個(gè)數(shù)。xi∈Rd是第i個(gè)數(shù)據(jù)點(diǎn)。假設(shè)這些數(shù)據(jù)點(diǎn)來自c個(gè)類簇。在標(biāo)簽信息不可用的情況下將n個(gè)數(shù)據(jù)點(diǎn)分到c個(gè)類中，F(xiàn)CM 算法的目標(biāo)函數(shù)及約束條件如下：

其中h是模糊指數(shù)，用于調(diào)整模糊程度，通常為大于1 的實(shí)數(shù)。uik是矩陣U∈Rn×c的第(i，k)個(gè)元素，它反映第i個(gè)數(shù)據(jù)點(diǎn)屬于第k個(gè)聚類的程度。mk是第k個(gè)聚類的聚類原型，M=[m1，…，mc]。根據(jù)以下步驟分別更新U和M的元素，則可以實(shí)現(xiàn)對(duì)式（2）的求解：

當(dāng)h=1 時(shí)，式（1）等價(jià)于：

式（4）就是K-Means 算法的優(yōu)化目標(biāo)函數(shù)及約束條件。通常情況下，如果事先給定初始的聚類原型，隸屬度矩陣U中各個(gè)元素可以根據(jù)下式進(jìn)行計(jì)算：

2.2 魯棒稀疏模糊K 均值聚類

基于FCM 的聚類算法對(duì)異常值敏感，為了增強(qiáng)FCM 對(duì)異常值的穩(wěn)定性，徐等提出用l2，1范數(shù)和截?cái)嗟膌1范數(shù)替換原有的平方范數(shù)，減小異常值對(duì)聚類結(jié)果的影響。將l2，1范數(shù)的魯棒稀疏模糊K 均值聚類（Robust Sparse Fuzzy K-Mean，RSFKM）模型定義為：

截?cái)嗟膌1范數(shù)的RSFKM 模型定義為：

其中：參數(shù)γ是用于調(diào)整隸屬度矩陣U的稀疏程度的正則化參數(shù)。如果γ=0，則每個(gè)樣本點(diǎn)的隸屬度向量是稀疏的（只有一個(gè)元素是非零的，其他元素都是零）。當(dāng)γ＞0 時(shí)，隸屬度向量比γ=0 時(shí)更稠密。通過調(diào)整γ，隸屬度向量的稀疏性是一個(gè)漸進(jìn)的變化，隨著γ的逐漸增加，隸屬度向量中包含越來越多的非零元素。當(dāng)γ達(dá)到一個(gè)較大的值時(shí)，隸屬度向量的所有元素都是非零的，此時(shí)隸屬度向量是非稀疏的。通過參數(shù)尋優(yōu)可以找到合理的隸屬度向量的稀疏性，以獲得更準(zhǔn)確的聚類結(jié)果。參數(shù)ε可以視為一個(gè)閾值，當(dāng)樣本點(diǎn)與聚類中心點(diǎn)的距離大于給定閾值ε后，距離取值為閾值ε，這樣可以顯著減少異常值對(duì)目標(biāo)函數(shù)的影響。式（6）可以通過交替迭代算法來求解。

2.3 模式收縮模糊K 均值聚類

傳統(tǒng)FCM 算法在原始數(shù)據(jù)上進(jìn)行聚類，易受到噪聲和異常值的影響。因此，本文提出了模式收縮模糊K 均值聚類算法（FKPS），對(duì)原始數(shù)據(jù)的結(jié)構(gòu)進(jìn)行放縮，得到理想的數(shù)據(jù)流形結(jié)構(gòu)，稱為收縮模式。收縮模式可看作原始數(shù)據(jù)結(jié)構(gòu)的近似，近似程度可由參數(shù)β控制，進(jìn)而在學(xué)習(xí)得到的收縮模式上展開模糊聚類，并提出了迭代算法將縮小模式的學(xué)習(xí)和模糊聚類集成到一個(gè)統(tǒng)一的框架中。由于收縮模式具有所需的理想流形結(jié)構(gòu)，直接進(jìn)行聚類可以提高聚類性能和模糊聚類的穩(wěn)定性。

假設(shè)數(shù)據(jù)集X=[x1，x2，…，xn]∈Rd×n，xi∈Rd是數(shù)據(jù)集中第i個(gè)樣本點(diǎn)，xi在收縮模式中的對(duì)應(yīng)點(diǎn)定義為zi，且Z=[z1，z2，…，zn]∈Rd×n。FKPS 算法的目標(biāo)函數(shù)定義為：

3 自適應(yīng)近鄰信息模糊C 均值聚類

3.1 模型設(shè)計(jì)

在聚類領(lǐng)域中，自適應(yīng)近鄰信息指的是一種基于數(shù)據(jù)點(diǎn)之間相似度的度量，用于指導(dǎo)聚類算法中的簇劃分過程。每個(gè)數(shù)據(jù)點(diǎn)都可以被看作是其他數(shù)據(jù)點(diǎn)的近鄰，但是不同數(shù)據(jù)點(diǎn)之間的相似度是不同的，基于距離較小的數(shù)據(jù)點(diǎn)應(yīng)該具有更大的概率成為鄰居這一前提假設(shè)，可以認(rèn)為距離較近的樣本點(diǎn)同屬一個(gè)類別的概率較大。因此，自適應(yīng)近鄰信息會(huì)根據(jù)每個(gè)數(shù)據(jù)點(diǎn)與其他數(shù)據(jù)點(diǎn)的相似度，自適應(yīng)地選擇最相關(guān)的近鄰點(diǎn)進(jìn)行類別劃分，從而提高聚類的準(zhǔn)確性和穩(wěn)定性。

本文采用歐氏距離作為距離的度量方式。給定一個(gè)數(shù)據(jù)集X=[x1，x2，…，xn]∈Rd×n，其中d是維度，n是數(shù)據(jù)集中樣本點(diǎn)的個(gè)數(shù)。xj∈Rd是第j個(gè)樣本點(diǎn)，其余樣本點(diǎn)與xj成為鄰居的概率設(shè)為sjk，越小的距離對(duì)應(yīng)著更大的近鄰概率sjk。近鄰信息以相似度矩陣S的形式體現(xiàn)，上述數(shù)據(jù)集X中各樣本點(diǎn)間的相似度矩陣中各元素sjk，即為n個(gè)樣本點(diǎn)兩兩之間的近鄰概率。數(shù)據(jù)集X的相似度矩陣S∈Rn×n可用下式求解：

本文將樣本點(diǎn)xj的近鄰信息定義為Gxj，Gxj為一數(shù)值，數(shù)據(jù)集X中所有樣本點(diǎn)的近鄰信息構(gòu)成向量GX∈R1×n，Gxj為其第j個(gè)元素，正則化參數(shù)λ的作用是調(diào)節(jié)相似性矩陣S的稀疏性。Gxj的定義如下：

假設(shè)數(shù)據(jù)集X中的n個(gè)樣本點(diǎn)可分為c個(gè)類別，則類別中心矩陣V∈Rd×c中第i列向量vi即為第i個(gè)類別的中心點(diǎn)。同理，將類中心點(diǎn)vi與n個(gè)樣本點(diǎn)的近鄰信息定義為Gvi，Gvi為一數(shù)值，類別中心矩陣V中所有類中心點(diǎn)的近鄰信息構(gòu)成向量GV∈R1×c，Gvi為第i個(gè)元素，如圖1所示 。Gvi的定義如下：

圖1 近鄰信息示意圖Fig.1 Neighborhood information

為利用近鄰信息提高FCM 算法聚類的準(zhǔn)確性和穩(wěn)定性，在得到樣本點(diǎn)的近鄰信息GX和類中心點(diǎn)的近鄰信息GV后，本文將它們?nèi)谌牖A(chǔ)FCM 模型中得到引入自適應(yīng)近鄰信息的模糊C均值聚類算法模型（Adaptive Neighbors Fuzzy CMeans Algorithm，ANFCM）。ANFCM 的模型定義如下：

自適應(yīng)體現(xiàn)在求解Gxj與Gvi的過程中，將參數(shù)λ的選擇轉(zhuǎn)換為近鄰個(gè)數(shù)的選擇，故模型參數(shù)的尋優(yōu)轉(zhuǎn)化為了自適應(yīng)調(diào)節(jié)近鄰個(gè)數(shù)，具體證明見模型優(yōu)化部分。參數(shù)α起到調(diào)整原聚類結(jié)構(gòu)信息與自適應(yīng)近鄰信息在聚類過程中的重要性，增大參數(shù)α的值，自適應(yīng)近鄰信息對(duì)聚類過程的影響增大，反之減小。

3.2 模型優(yōu)化

本文提出的ANFCM 模型具體定義如下：

該模型中包含3 個(gè)最小值優(yōu)化問題。因?yàn)镚xj的值只與數(shù)據(jù)X有關(guān)，所以在一開始就可進(jìn)行求解。先定義：

針對(duì)這個(gè)優(yōu)化問題，可根據(jù)拉格朗日法和KKT 條件求解：

根據(jù)Nie 等提出的方法［14］，解決步驟為：

將以上推導(dǎo)整理成求解Gxj問題的算法1。

算法開始時(shí)，先隨機(jī)初始化隸屬度矩陣U和類中心矩陣V。Gvi的優(yōu)化與數(shù)據(jù)X和類中心矩陣V有關(guān)，每次根據(jù)更新后的類中心矩陣V，Gvi的求解過程與Gxj的求解過程類似，使用算法2 計(jì)算其最小值。

優(yōu)化目標(biāo)函數(shù)J時(shí)，Gxj和Gvi當(dāng)作常數(shù)，根據(jù)拉格朗日乘數(shù)法進(jìn)行求解。

構(gòu)造拉格朗日函數(shù)：

令函數(shù)L對(duì)uij求偏導(dǎo)數(shù)，并令其為零：

令函數(shù)L對(duì)vi求偏導(dǎo)數(shù)，并令其為零：

ANFCM 算法流程如圖2 所示，整體求解步驟歸納為算法3。

圖2 ANFCM 算法流程Fig.2 Flowchart of ANFCM algorithm

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

4.1 數(shù)據(jù)集概況

UCI 數(shù)據(jù)集是機(jī)器學(xué)習(xí)領(lǐng)域中最常用的驗(yàn)證算法性能的數(shù)據(jù)集之一。對(duì)比實(shí)驗(yàn)中，使用8個(gè)真實(shí)基準(zhǔn)數(shù)據(jù)集，如表1 所示。

表1 基準(zhǔn)數(shù)據(jù)集情況描述Tab.1 Description of benchmark datasets

4.2 對(duì)比算法

本文采用KM，F(xiàn)CM，模糊緊密性與分離性聚類算法（FCS），ATKM，RSFKM 和KFS 6 種先進(jìn)的相關(guān)聚類方法作為對(duì)比算法：

（1）K-Means是最為知名的聚類算法之一，它將一組數(shù)據(jù)點(diǎn)分成若干簇，使得每個(gè)數(shù)據(jù)點(diǎn)被分配到一個(gè)簇中，且每個(gè)數(shù)據(jù)點(diǎn)只屬于一個(gè)簇；

（2）FCM 算法是K-Means 算法的擴(kuò)展，每個(gè)簇視為一個(gè)模糊集合，而隸屬度函數(shù)測(cè)量每個(gè)數(shù)據(jù)點(diǎn)屬于簇的可能性，每個(gè)聚類原型由所有樣本的加權(quán)平均值形成；

（3）FCS［19］為每個(gè)聚類分配一個(gè)硬核邊界，以便硬隸屬度和模糊隸屬度可以共存于聚類結(jié)果中。因此，F(xiàn)CS可以被看作是介于K-Means聚類和模糊C均值聚類之間的一種新型聚類算法；

（4）與FCM 相比，聚合模糊K 均值聚類算法（AFKM）［20］采用正則化參數(shù)來調(diào)整模糊隸屬度，并引入最大熵信息以優(yōu)化聚類分區(qū)；

（5）RSFKM 采用稀疏結(jié)構(gòu)范數(shù)來減小異常值對(duì)目標(biāo)函數(shù)的影響，并提出了一種重新加權(quán)的算法來有效求解模型；

（6）FKPS 直接在得到的收縮模式上執(zhí)行模糊聚類，收縮模式可以視為沒有噪聲干擾的干凈數(shù)據(jù)，因此擁有理想的流形結(jié)構(gòu)。

4.3 參數(shù)設(shè)置

在FCM 類型的算法中，大量實(shí)驗(yàn)表明，隸屬度權(quán)重指數(shù)設(shè)置為2 時(shí)能得到較好的結(jié)果。根據(jù)經(jīng)驗(yàn)，該部分中所有算法的隸屬度權(quán)重指數(shù)均設(shè)置為2，其余需要調(diào)整的參數(shù)采用網(wǎng)格搜索策略進(jìn)行選擇。ANFCM 算法有3 個(gè)需要調(diào)整的參數(shù)，第一個(gè)是正則化參數(shù)α，用于調(diào)節(jié)全局信息與樣本點(diǎn)近鄰信息對(duì)聚類的影響程度，依次取值為［0.001，0.01，0.1，1，10，100，1000，10000］；第二個(gè)參數(shù)是最近鄰樣本點(diǎn)個(gè)數(shù)kx，第三個(gè)參數(shù)是最近鄰聚類原型個(gè)數(shù)kv，兩個(gè)參數(shù)的設(shè)置相同，均為［2，3，5，7，9，15，19，25］。AFKM 算法的正則化參數(shù)λ 設(shè)置為［0.001，0.01，0.1，1，2，5，10，100］。FKPS 算法需要調(diào)整的兩個(gè)參數(shù)分別被命名為γ和β，第一個(gè)參數(shù)γ用于調(diào)整隸屬度矩陣的模糊程度，取值為［0.1，0.5，1，5，10，50，100，500，1 000］。而第二個(gè)參數(shù)β則用于調(diào)整原始數(shù)據(jù)和學(xué)習(xí)到的收縮模式之間的差異，取值為［0.005，0.01，0.05，0.1，0.5，1，5］。在RSFKM算法中，有兩個(gè)重要的參數(shù)，即正則化參數(shù)γ和閾值?。正則化參數(shù)γ對(duì)數(shù)據(jù)點(diǎn)和聚類中心之間的最小距離設(shè)定了限制，并防止隸屬度具有極端值，即0 和1，其取值為[10-1，10]，步長(zhǎng)為0.5。閾值?主要控制離群值的數(shù)量，并與表示的殘差相關(guān)，設(shè)置為［0，0.5，1，1.5，2，2.5，3］。

4.4 評(píng)價(jià)指標(biāo)

ACC，NMI 和Purity 是評(píng)估聚類結(jié)果質(zhì)量的常用指標(biāo)。其中，ACC（Accuracy）是聚類的準(zhǔn)確率，它度量聚類結(jié)果與真實(shí)標(biāo)簽之間的匹配程度；NMI（Normalized Mutual Information）是標(biāo)準(zhǔn)化互信息，它測(cè)量聚類結(jié)果與真實(shí)標(biāo)簽之間的相似程度，將互信息歸一化，并考慮到聚類結(jié)果和真實(shí)標(biāo)簽的熵，取值為0 到1，值越高表示聚類結(jié)果越與真實(shí)標(biāo)簽相似；Purity 是純度，它度量聚類結(jié)果中同一類別的數(shù)據(jù)點(diǎn)所占比例。它計(jì)算每個(gè)聚類中出現(xiàn)次數(shù)最多的真實(shí)標(biāo)簽，將這些標(biāo)簽的出現(xiàn)次數(shù)相加并除以總數(shù)據(jù)點(diǎn)數(shù)得到聚類結(jié)果的純度，取值為0 到1，值越高表示聚類結(jié)果中同一類別的數(shù)據(jù)點(diǎn)越多。

4.5 聚類性能評(píng)估

由于聚類結(jié)果受隨機(jī)初始化的影響，所有實(shí)驗(yàn)結(jié)果均為在同等條件下，隨機(jī)初始化聚類中心的10 次聚類結(jié)果取平均值。各聚類算法在8 個(gè)基準(zhǔn)數(shù)據(jù)集上進(jìn)行聚類，評(píng)價(jià)指標(biāo)分別如表2～表4 所示，最優(yōu)算法結(jié)果加粗標(biāo)出。從表4 可以看出，ANFCM 算法在Ionosphere 和Jain 數(shù)據(jù)集上的聚類性能，比對(duì)比算法的指標(biāo)高出10%以上；總體上看，與傳統(tǒng)FCM 相比，ANFCM 算法在實(shí)驗(yàn)中的所有數(shù)據(jù)集上的平均表現(xiàn)，即Accuracy，NMI 和 Purity 3 個(gè)指標(biāo)上分別有11.872 5%，15.442 5%，6.616 3% 的提升。說明引入局部近鄰信息有效指導(dǎo)了隸屬度矩陣的學(xué)習(xí)，進(jìn)而提高了聚類算法的精度。

表2 各算法在8 個(gè)數(shù)據(jù)集上的Accuracy 值Tab.2 Accuracy values for each algorithm on 8 datasets

表3 各算法在8 個(gè)數(shù)據(jù)集上的NMI 值Tab.3 NMI values for each algorithm on 8 datasets

表4 各算法在8 個(gè)數(shù)據(jù)集上的Purity 值Tab.4 Purity values for each algorithm on 8 datasets

4.6 參數(shù)敏感性分析

參數(shù)敏感性實(shí)驗(yàn)是指在模型開發(fā)和優(yōu)化過程中，對(duì)不同參數(shù)取值進(jìn)行實(shí)驗(yàn)，以評(píng)估模型對(duì)參數(shù)變化的敏感性，從而確定最佳參數(shù)組合的方法。參數(shù)敏感性實(shí)驗(yàn)的重要性在于可以了解模型在不同參數(shù)設(shè)置下的性能，從而在確定模型最佳參數(shù)組合時(shí)提供指導(dǎo)，以最大限度地提高模型的性能，同時(shí)也可以評(píng)估模型對(duì)參數(shù)變化的穩(wěn)定性，即在參數(shù)變化的情況下模型的表現(xiàn)是否穩(wěn)定。ANFCM 算法模型具有近鄰樣本點(diǎn)個(gè)數(shù)kx，近鄰聚類中心點(diǎn)個(gè)數(shù)kv和正則化參數(shù)α 3 個(gè)參數(shù)。對(duì)于給定某個(gè)數(shù)據(jù)集，首先根據(jù)4.3 節(jié)參數(shù)的設(shè)置范圍進(jìn)行遍歷尋優(yōu)，找出該數(shù)據(jù)集最佳的一組參數(shù)。確定最優(yōu)參數(shù)組合后，本文采用“定一議二”的策略可視化各參數(shù)變化對(duì)聚類精度的影響。具體方法如下：得到最佳參數(shù)組合后，每次固定一個(gè)參數(shù)為最優(yōu)值，依據(jù)原先設(shè)定的取值范圍調(diào)節(jié)其余兩個(gè)參數(shù)，并繪制出聚類準(zhǔn)確率隨這兩個(gè)參數(shù)的變化曲線，如圖3～圖5 所示。

圖3 固定α 條件下聚類精度對(duì)參數(shù)kx 和kv 的參數(shù)敏感性實(shí)驗(yàn)結(jié)果Fig.3 Experimental results of parameter sensitivity of clustering accuracy to parameters kx and kv under fixed α condition

在4 個(gè)基準(zhǔn)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，聚類精度對(duì)參數(shù)kx和kv的參數(shù)敏感性實(shí)驗(yàn)結(jié)果如圖3 所示，聚類精度對(duì)參數(shù)kv和α的參數(shù)敏感性實(shí)驗(yàn)結(jié)果如圖4 所示，聚類精度對(duì)參數(shù)kx和α的參數(shù)敏感性實(shí)驗(yàn)結(jié)果如圖5 所示。若聚類性能受參數(shù)變化的影響起伏較大，說明引入的這項(xiàng)參數(shù)對(duì)聚類結(jié)果能產(chǎn)生重要影響。由圖可以看出，ANFCM 算法的聚類精度對(duì)3 個(gè)參數(shù)都較為敏感，隨參數(shù)的變化較大，同時(shí)較優(yōu)的結(jié)果集中在較小范圍內(nèi)。

圖4 固定kx 條件下聚類精度對(duì)參數(shù)kv 和α 的參數(shù)敏感性實(shí)驗(yàn)結(jié)果Fig.4 Experimental results of parameter sensitivity of clustering accuracy to parameters kv and α under fixed kx condition

圖5 固定kv 條件下聚類精度對(duì)參數(shù)kx 和α 的參數(shù)敏感性實(shí)驗(yàn)結(jié)果Fig.5 Experimental results of parameter sensitivity of clustering accuracy to parameters kx and α under fixed kv condition

4.7 收斂性分析

在模糊C 均值聚類算法中，關(guān)鍵步驟是計(jì)算每個(gè)數(shù)據(jù)點(diǎn)與每個(gè)簇的隸屬度，然后根據(jù)這些隸屬度來更新每個(gè)簇的中心點(diǎn)。算法迭代直到滿足收斂條件為止，例如中心點(diǎn)的變化量小于某個(gè)閾值。因此，收斂性分析是模糊C 均值算法的重要組成部分。如果算法無(wú)法收斂，無(wú)法得到正確的簇劃分結(jié)果，影響算法的應(yīng)用效果。模糊C 均值算法的收斂性分析通常包括以下幾個(gè)方面：

（1）收斂性證明：證明算法能夠在有限的迭代次數(shù)內(nèi)收斂到一個(gè)穩(wěn)定的狀態(tài)，即每個(gè)數(shù)據(jù)點(diǎn)的隸屬度和簇的中心點(diǎn)不再發(fā)生明顯的變化。

（2）收斂速度分析：分析算法的收斂速度，即算法需要多少次迭代才能達(dá)到一個(gè)滿意的精度，這對(duì)算法的實(shí)際應(yīng)用具有重要的指導(dǎo)意義。

（3）收斂性檢測(cè)方法：設(shè)計(jì)一些有效的方法來檢測(cè)算法是否已經(jīng)收斂，例如通過計(jì)算中心點(diǎn)的變化量、隸屬度的變化量或目標(biāo)函數(shù)值的變化量來判斷算法是否還需要繼續(xù)迭代。

本文采用目標(biāo)函數(shù)值的下降情況來研究算法的收斂性，ANFCM 算法在6 個(gè)基準(zhǔn)數(shù)據(jù)集上的收斂性實(shí)驗(yàn)結(jié)果如圖6 所示?？梢悦黠@地看出，優(yōu)化模型的目標(biāo)函數(shù)值在快速下降直至收斂，還可以進(jìn)一步觀察到，所提出的算法通?？梢栽?0 次迭代內(nèi)收斂。RSFKM 算法可以在較少迭代次數(shù)下達(dá)到收斂，在各數(shù)據(jù)集通常在50次迭代以內(nèi)收斂［8］。此外，F(xiàn)KPS 算法在各數(shù)據(jù)集可以在15 次迭代以內(nèi)達(dá)到收斂［18］。對(duì)比可以得出，ANFCM 模型也具有良好的迭代收斂性能。

圖6 在6 個(gè)數(shù)據(jù)集上目標(biāo)函數(shù)值與聚類表現(xiàn)隨迭代步數(shù)的變化情況Fig.6 Changes in objective function values and clustering performance with iteration steps on 6 datasets

為了更加直觀地展示聚類模型的性能，在算法迭代過程中，隨著迭代次數(shù)的增加，聚類性能的變化情況如圖6 所示?？梢钥闯觯S著迭代次數(shù)逐漸增加，聚類性能逐漸改善。綜上，本文提出的ANFCM 模型具有優(yōu)異的收斂特性。

4.8 消融實(shí)驗(yàn)

消融實(shí)驗(yàn)是一種用于評(píng)估機(jī)器學(xué)習(xí)模型中各個(gè)組成部分對(duì)模型性能影響的實(shí)驗(yàn)方法。在消融實(shí)驗(yàn)中，對(duì)模型的某些組成部分進(jìn)行＂切除＂，然后觀察模型的性能變化，從而確定這些組成部分對(duì)模型性能的貢獻(xiàn)。

與基礎(chǔ)FCM 模型相比，本文提出的模型引入局部自適應(yīng)近鄰信息Gx與Gv，即：

為體現(xiàn)引入的局部自適應(yīng)近鄰信息對(duì)聚類效果的提升，對(duì)模型進(jìn)行如下變動(dòng)：

（1）ANFCM0：將參數(shù)α設(shè)置為0，同時(shí)去除局部自適應(yīng)近鄰信息Gx與Gv，模型退化為基礎(chǔ)FCM 模型：

（2）ANFCM1：去除樣本點(diǎn)與近鄰樣本點(diǎn)之間的位置信息Gx：

（3）ANFCM2：去除樣本點(diǎn)與近鄰聚類中心點(diǎn)的位置信息Gv：

4 個(gè)算法在4 個(gè)基準(zhǔn)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，所有實(shí)驗(yàn)結(jié)果均在同等條件下，隨機(jī)初始化聚類中心的10 次聚類結(jié)果取平均值。對(duì)比實(shí)驗(yàn)結(jié)果如圖7 所示，可以看出在4 個(gè)數(shù)據(jù)集上，ANFCM 算法在Accuracy，NMI，Purity 3 個(gè)評(píng)價(jià)指標(biāo)上均取得最好的效果，在Ionosphere 數(shù)據(jù)集和Jain 數(shù)據(jù)集上有很大的提升。由此可以得出，加入局部自適應(yīng)近鄰信息Gx與Gv對(duì)提升聚類結(jié)果的表現(xiàn)有很大的作用。

圖7 在4 個(gè)數(shù)據(jù)集上的消融實(shí)驗(yàn)結(jié)果Fig.7 Ablation experimental results on 4 datasets

5 結(jié)論

本文提出了一種模糊C 均值聚類算法，同時(shí)挖掘簇中心和樣本點(diǎn)局部結(jié)構(gòu)信息，指導(dǎo)聚類過程，在保證模糊C 均值算法優(yōu)點(diǎn)的同時(shí)，減弱噪聲、離群點(diǎn)的影響，提升算法的穩(wěn)定性。通過實(shí)驗(yàn)、定量驗(yàn)證以及定性分析了算法的有效性和可行性。但該算法對(duì)初始值較為敏感，這是由于FCM 本質(zhì)上是非凸優(yōu)化問題，而算法的實(shí)現(xiàn)采用迭代更新的策略，這使得初始值的選取會(huì)影響算法的進(jìn)程。這個(gè)問題將在未來做進(jìn)一步的研究。