基于自適應近鄰信息的模糊C 均值聚類算法

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

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

1 引言

作為一種無監督方法，聚類的基本任務是將數據點劃分為不相交的簇，使得同一簇內數據點之間的相似度最大化，而不同簇之間數據點的相似度最小化。在文本分析方面，聚類算法可以將市場細分為不同的消費者群體，幫助企業了解不同群體的需求和偏好，有助于市場營銷策略的制定和產品定價。在計算機視覺領域，聚類算法可以將圖像分割為不同的區域或對象，突出不同區域之間色塊的差異和相同區域色塊的相似，從而實現圖像分析和目標檢測等任務。聚類算法可以用于分析基因表達數據，幫助研究人員識別基因表達模式并發現疾病相關基因。數據當中的異常點或離群點可以通過聚類算法進行檢測，可應用于故障診斷和網絡安全等領域。總的來說，聚類算法在模式識別、圖像處理和數據挖掘等領域有著十分廣泛的應用，可以幫助人們分析數據，理解數據的本質結構特征，從數據中獲取有用信息。

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

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

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

2 相關工作

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

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

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

當h=1 時，式（1）等價于：

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

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

基于FCM 的聚類算法對異常值敏感，為了增強FCM 對異常值的穩定性，徐等提出用l2，1范數和截斷的l1范數替換原有的平方范數，減小異常值對聚類結果的影響。將l2，1范數的魯棒稀疏模糊K 均值聚類（Robust Sparse Fuzzy K-Mean，RSFKM）模型定義為：

截斷的l1范數的RSFKM 模型定義為：

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

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

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

假設數據集X=[x1，x2，…，xn]∈Rd×n，xi∈Rd是數據集中第i個樣本點，xi在收縮模式中的對應點定義為zi，且Z=[z1，z2，…，zn]∈Rd×n。FKPS 算法的目標函數定義為：

3 自適應近鄰信息模糊C 均值聚類

3.1 模型設計

在聚類領域中，自適應近鄰信息指的是一種基于數據點之間相似度的度量，用于指導聚類算法中的簇劃分過程。每個數據點都可以被看作是其他數據點的近鄰，但是不同數據點之間的相似度是不同的，基于距離較小的數據點應該具有更大的概率成為鄰居這一前提假設，可以認為距離較近的樣本點同屬一個類別的概率較大。因此，自適應近鄰信息會根據每個數據點與其他數據點的相似度，自適應地選擇最相關的近鄰點進行類別劃分，從而提高聚類的準確性和穩定性。

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

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

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

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

為利用近鄰信息提高FCM 算法聚類的準確性和穩定性，在得到樣本點的近鄰信息GX和類中心點的近鄰信息GV后，本文將它們融入基礎FCM 模型中得到引入自適應近鄰信息的模糊C均值聚類算法模型（Adaptive Neighbors Fuzzy CMeans Algorithm，ANFCM）。ANFCM 的模型定義如下：

自適應體現在求解Gxj與Gvi的過程中，將參數λ的選擇轉換為近鄰個數的選擇，故模型參數的尋優轉化為了自適應調節近鄰個數，具體證明見模型優化部分。參數α起到調整原聚類結構信息與自適應近鄰信息在聚類過程中的重要性，增大參數α的值，自適應近鄰信息對聚類過程的影響增大，反之減小。

3.2 模型優化

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

該模型中包含3 個最小值優化問題。因為Gxj的值只與數據X有關，所以在一開始就可進行求解。先定義：

針對這個優化問題，可根據拉格朗日法和KKT 條件求解：

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

將以上推導整理成求解Gxj問題的算法1。

算法開始時，先隨機初始化隸屬度矩陣U和類中心矩陣V。Gvi的優化與數據X和類中心矩陣V有關，每次根據更新后的類中心矩陣V，Gvi的求解過程與Gxj的求解過程類似，使用算法2 計算其最小值。

優化目標函數J時，Gxj和Gvi當作常數，根據拉格朗日乘數法進行求解。

構造拉格朗日函數：

令函數L對uij求偏導數，并令其為零：

令函數L對vi求偏導數，并令其為零：

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

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

4 實 驗

4.1 數據集概況

UCI 數據集是機器學習領域中最常用的驗證算法性能的數據集之一。對比實驗中，使用8個真實基準數據集，如表1 所示。

表1 基準數據集情況描述Tab.1 Description of benchmark datasets

4.2 對比算法

本文采用KM，FCM，模糊緊密性與分離性聚類算法（FCS），ATKM，RSFKM 和KFS 6 種先進的相關聚類方法作為對比算法：

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

（2）FCM 算法是K-Means 算法的擴展，每個簇視為一個模糊集合，而隸屬度函數測量每個數據點屬于簇的可能性，每個聚類原型由所有樣本的加權平均值形成；

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

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

（5）RSFKM 采用稀疏結構范數來減小異常值對目標函數的影響，并提出了一種重新加權的算法來有效求解模型；

（6）FKPS 直接在得到的收縮模式上執行模糊聚類，收縮模式可以視為沒有噪聲干擾的干凈數據，因此擁有理想的流形結構。

4.3 參數設置

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

4.4 評價指標

ACC，NMI 和Purity 是評估聚類結果質量的常用指標。其中，ACC（Accuracy）是聚類的準確率，它度量聚類結果與真實標簽之間的匹配程度；NMI（Normalized Mutual Information）是標準化互信息，它測量聚類結果與真實標簽之間的相似程度，將互信息歸一化，并考慮到聚類結果和真實標簽的熵，取值為0 到1，值越高表示聚類結果越與真實標簽相似；Purity 是純度，它度量聚類結果中同一類別的數據點所占比例。它計算每個聚類中出現次數最多的真實標簽，將這些標簽的出現次數相加并除以總數據點數得到聚類結果的純度，取值為0 到1，值越高表示聚類結果中同一類別的數據點越多。

4.5 聚類性能評估

由于聚類結果受隨機初始化的影響，所有實驗結果均為在同等條件下，隨機初始化聚類中心的10 次聚類結果取平均值。各聚類算法在8 個基準數據集上進行聚類，評價指標分別如表2～表4 所示，最優算法結果加粗標出。從表4 可以看出，ANFCM 算法在Ionosphere 和Jain 數據集上的聚類性能，比對比算法的指標高出10%以上；總體上看，與傳統FCM 相比，ANFCM 算法在實驗中的所有數據集上的平均表現，即Accuracy，NMI 和 Purity 3 個指標上分別有11.872 5%，15.442 5%，6.616 3% 的提升。說明引入局部近鄰信息有效指導了隸屬度矩陣的學習，進而提高了聚類算法的精度。

表2 各算法在8 個數據集上的Accuracy 值Tab.2 Accuracy values for each algorithm on 8 datasets

表3 各算法在8 個數據集上的NMI 值Tab.3 NMI values for each algorithm on 8 datasets

表4 各算法在8 個數據集上的Purity 值Tab.4 Purity values for each algorithm on 8 datasets

4.6 參數敏感性分析

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

圖3 固定α 條件下聚類精度對參數kx 和kv 的參數敏感性實驗結果Fig.3 Experimental results of parameter sensitivity of clustering accuracy to parameters kx and kv under fixed α condition

在4 個基準數據集上進行實驗，聚類精度對參數kx和kv的參數敏感性實驗結果如圖3 所示，聚類精度對參數kv和α的參數敏感性實驗結果如圖4 所示，聚類精度對參數kx和α的參數敏感性實驗結果如圖5 所示。若聚類性能受參數變化的影響起伏較大，說明引入的這項參數對聚類結果能產生重要影響。由圖可以看出，ANFCM 算法的聚類精度對3 個參數都較為敏感，隨參數的變化較大，同時較優的結果集中在較小范圍內。

圖4 固定kx 條件下聚類精度對參數kv 和α 的參數敏感性實驗結果Fig.4 Experimental results of parameter sensitivity of clustering accuracy to parameters kv and α under fixed kx condition

圖5 固定kv 條件下聚類精度對參數kx 和α 的參數敏感性實驗結果Fig.5 Experimental results of parameter sensitivity of clustering accuracy to parameters kx and α under fixed kv condition

4.7 收斂性分析

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

（1）收斂性證明：證明算法能夠在有限的迭代次數內收斂到一個穩定的狀態，即每個數據點的隸屬度和簇的中心點不再發生明顯的變化。

（2）收斂速度分析：分析算法的收斂速度，即算法需要多少次迭代才能達到一個滿意的精度，這對算法的實際應用具有重要的指導意義。

（3）收斂性檢測方法：設計一些有效的方法來檢測算法是否已經收斂，例如通過計算中心點的變化量、隸屬度的變化量或目標函數值的變化量來判斷算法是否還需要繼續迭代。

本文采用目標函數值的下降情況來研究算法的收斂性，ANFCM 算法在6 個基準數據集上的收斂性實驗結果如圖6 所示。可以明顯地看出，優化模型的目標函數值在快速下降直至收斂，還可以進一步觀察到，所提出的算法通常可以在10 次迭代內收斂。RSFKM 算法可以在較少迭代次數下達到收斂，在各數據集通常在50次迭代以內收斂［8］。此外，FKPS 算法在各數據集可以在15 次迭代以內達到收斂［18］。對比可以得出，ANFCM 模型也具有良好的迭代收斂性能。

圖6 在6 個數據集上目標函數值與聚類表現隨迭代步數的變化情況Fig.6 Changes in objective function values and clustering performance with iteration steps on 6 datasets

為了更加直觀地展示聚類模型的性能，在算法迭代過程中，隨著迭代次數的增加，聚類性能的變化情況如圖6 所示。可以看出，隨著迭代次數逐漸增加，聚類性能逐漸改善。綜上，本文提出的ANFCM 模型具有優異的收斂特性。

4.8 消融實驗

消融實驗是一種用于評估機器學習模型中各個組成部分對模型性能影響的實驗方法。在消融實驗中，對模型的某些組成部分進行＂切除＂，然后觀察模型的性能變化，從而確定這些組成部分對模型性能的貢獻。

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

為體現引入的局部自適應近鄰信息對聚類效果的提升，對模型進行如下變動：

（1）ANFCM0：將參數α設置為0，同時去除局部自適應近鄰信息Gx與Gv，模型退化為基礎FCM 模型：

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

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

4 個算法在4 個基準數據集上進行實驗，所有實驗結果均在同等條件下，隨機初始化聚類中心的10 次聚類結果取平均值。對比實驗結果如圖7 所示，可以看出在4 個數據集上，ANFCM 算法在Accuracy，NMI，Purity 3 個評價指標上均取得最好的效果，在Ionosphere 數據集和Jain 數據集上有很大的提升。由此可以得出，加入局部自適應近鄰信息Gx與Gv對提升聚類結果的表現有很大的作用。

圖7 在4 個數據集上的消融實驗結果Fig.7 Ablation experimental results on 4 datasets

5 結論

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