基于密度敏感距離的改進模糊C 均值聚類算法

王治和，王淑艷，杜 輝

（西北師范大學計算機科學與工程學院，蘭州 730070）

0 概述

聚類分析是將樣本對象劃分成子集的過程，即把每個子集作為一個簇，簇中的對象相似程度高，不同簇中的對象相異程度高。目前，聚類分析已被廣泛應用于數據挖掘、模式識別和圖像處理等領域，很多經典算法被提出用于樣本對象的聚類，主要有基于劃分、層次、密度、網格和模型五大類［1］。模糊C 均值（Fuzzy C-means，FCM）聚類算法是一種基于劃分的聚類算法，其因簡潔、高效而得到了廣泛的應用［2］，但在建立相似度矩陣、隨機初始化聚類中心和預先確定聚類數目等方面還存在不足。在建立相似度矩陣的過程中，FCM 算法采用歐氏距離的相似性度量只對凸數據具有良好的處理性能，在復雜形狀和非凸數據中往往會失敗，因此，確定合適的相似度矩陣是提高FCM 算法聚類性能的關鍵因素。

相似度矩陣依賴于距離度量這一特點，吸引了很多學者的研究與關注。文獻［3］提出一種基于加權歐氏距離的改進FCM 算法，其中加權歐氏距離是將特征權值合并到常用的歐氏距離中，結果表明，適當的特征權值分配可以提高FCM 算法的聚類性能。文獻［4］引入一種魯棒的非歐氏距離度量方法來提高傳統FCM 算法的效率，從而減少噪聲和異常值對聚類性能的影響。文獻［5］提出使用馬氏距離和閔可夫斯基距離來代替歐氏距離，提高了FCM 算法對于高維數據的識別能力。文獻［6］提出一種基于散度相似性度量的FCM 算法，其對噪聲特征的擾動具有更強的魯棒性。以上文獻雖然提高了FCM 算法識別高維數據和噪聲等方面的聚類性能，但這些距離度量仍然無法對非凸數據聚類。文獻［7］提出一種模糊核C 均值聚類算法，該算法采用基于核的距離度量代替歐氏距離作為相似性度量，可以識別任意形狀的聚類，但其中核寬度σ都是通過反復實驗得出的，增加了算法的計算復雜度和時間復雜度。文獻［8］提出一種基于傳遞閉包和譜聚類的多中心FCM 算法，解決了FCM 算法無法處理非凸數據的問題，但算法中對于子簇初始數目和子簇數目的設置都缺乏理論支持。

本文借鑒文獻［9］提出的密度敏感距離度量方法，提出一種基于密度敏感距離的改進FCM 算法AMMF-DSD。在建立相似度矩陣時采用密度敏感距離代替歐氏距離，以解決FCM 算法無法對非凸數據聚類的問題。同時為進一步提高算法的聚類性能，利用近鄰傳播（Affinity Propagation，AP）聚類算法［10］獲取粗類數，快速確定最佳聚類數的搜索范圍上限，基于此改進最大最小距離算法獲得具有代表性的采樣點作為FCM 算法的初始聚類中心，最后結合輪廓系數［11］在聚類數搜索范圍內自動確定最佳聚類數。

1 相關工作

1.1 FCM 聚類算法

給定數據集：X=(x1，x2，…，xn)。其中，每個數據對象xi包含d個特征值，n是樣本數據集的個數。FCM 算法將X劃分為k個 類，［v1，v2，…，vk］為k個聚類中心。FCM 聚類算法的目標函數如式（1）所示：

其中，m是模糊指標，m＞1，uij是樣本點xi在第j分組中的隸屬度，‖ ‖xi-vj是樣本點xi和聚類中心vj之間的歐式距離。在滿足約束條件的情況下對目標函數使用拉格朗日（Lagrange）乘數法，得到隸屬度矩陣和聚類中心，分別如式（2）和式（3）所示：

FCM 聚類算法具體步驟如下：

算法1FCM 聚類算法

輸入聚類數k，初始聚類中心，模糊指標m，終止誤差ε

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

步驟1按式（2）更新隸屬度矩陣。

步驟2按式（3）更新聚類中心。

步驟3如果，則算法終止；否則回到步驟1，繼續進行迭代。

1.2 密度敏感距離

根據上述FCM 算法的過程可以明顯看出，所獲得相似度矩陣的準確性直接影響聚類性能。此外，相似度矩陣主要取決于距離度量的確定。因此，選擇合適的距離度量方法對于提高FCM 算法聚類性能至關重要。基于該距離獲得的數據點之間的相似性度量必須滿足以下兩個一致性關系［9］：1）局部一致性，即空間上相鄰的數據點之間應具有較高的相似性；2）全局一致性，即位于同一流形上的數據點之間應具有較高的相似性。

傳統的FCM 算法通常采用歐氏距離來確定數據點之間的相似性，然而歐氏距離只考慮數據點之間的局部一致性特征，忽略了全局一致性特征。因此，對于復雜數據和非凸數據，基于歐氏距離的相似性矩陣往往無法準確地捕獲實際的數據結構，從而導致聚類性能較差。如圖1 所示，根據相似測度的全局一致性要求，同一流形上的數據點應具有較高的相似性，即點1 與點3 之間的相似性應高于點1 與點2 之間的相似性，但是在按照歐氏距離進行相似性度量時，點1 與點3 的相似性要明顯小于點1 與點2，這與期望不一致，即將歐氏距離作為相似性度量不能滿足全局一致性。

圖1 歐式距離無法滿足樣本全局一致性的情況Fig.1 The case of Euclidean distance not satisfying the global consistency of samples

為滿足聚類結果的全局一致性，使相同流形結構中數據對的相似度高于不同的流形結構，必須使得穿過高密度區域以較短邊相連的路徑長度低于穿過低密度區域直接相連的兩點間距離，即，如圖2 所示。

圖2 全局一致性距離Fig.2 Global consistency distance

本文提出一種基于密度敏感距離度量創建相似度矩陣的算法，通過引入密度敏感距離能夠同時考慮全局一致性和數據分布的局部一致性，使獲得的相似性矩陣可以更準確地捕獲真實數據結構，從而解決FCM 算法無法識別復雜非凸數據的問題。具體如下：

定義1密度調整長度如式（4）所示：

其中，d(x，y)表示點x與點y間的歐氏距離，ρ為伸縮因子，通過調節伸縮因子ρ來放大或縮短兩點間線段長度，可以同時滿足全局一致性和局部一致性。基于密度調整長度進一步定義密度敏感距離，通過在圖中尋找最短路徑來測量一對點之間的距離。

定義2將數據點看作一個加權無向圖G={V，E}，V表示頂點集合，E表示邊集合。令P∈Vl為圖上長度為l=|p|-1 的連接點p1、p||p之間的路徑，其中，邊（pk，pk+1）∈E，1≤k＜l，pij為連接數據點對{xi，xj}的所有路徑的集合，1≤i，j＜n，xi與xj之間的密度敏感距離如式（5）所示：

其中，dsp(xi，xj)表示圖G上節點xi和xj之間的最短路徑距離，d（pk，pk+1）是節點xi到xj最短路徑上任意相鄰兩點的歐氏距離。不難看出，本文提出的距離度量方法可同時滿足距離度量的以下4 種特性：

1.3 輪廓系數

輪廓系數是由KAUFMAN 等人提出的一種用于評價算法聚類質量的有效性指標。該指標結合了凝聚度和分離度，不僅能夠評價聚類質量，而且還可用于獲取最佳聚類數。假設數據集的樣本對象xi屬于類A。數據集的聚類輪廓系數Sk（平均輪廓系數）定義如式（7）所示：

其中，n為數據集中的樣本個數，a(i)表示樣本點i與同簇剩余樣本對象的平均距離，b(i)表示樣本點i與剩余每個簇的樣本對象平均距離的最小值。輪廓系數的取值范圍在[ -1，1]之間，其值越大，表明聚類的質量越好。對于現有的分類數，求取輪廓系數的最大值，與之對應的k值就是最佳聚類數［12］。結合相關資料和實驗情況可知，本文采用輪廓系數來評價聚類效果從而獲得最佳聚類數的方法是有效的。

2 基于密度敏感距離的改進FCM 算法

2.1 基于密度敏感距離的FCM 距離度量

改進后的FCM 算法距離度量采用密度敏感距離，目標函數如式（8）所示：

基于密度敏感距離度量的FCM 算法具體步驟如下：

算法2基于密度敏感距離度量的FCM 算法

輸入聚類數k，模糊指標m，初始聚類中心，終止誤差ε

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

步驟1第c次迭代，根據式（9）更新隸屬度矩陣。

步驟2根據式（11）更新聚類中心。

步驟3根據新得的聚類中心從密度敏感距離矩陣中獲得新的Dij，重新計算隸屬度函數uij，迭代循環，直到聚類中心不發生變化，算法結束。

算法2 中的聚類中心更新方式如下：將數據集中的樣本點作為聚類中心，在確定初始聚類中心后，由上述密度敏感距離得到。目標函數如式（10）所示：

則第j類的聚類中心vj如式（11）所示：

2.2 最佳聚類數的確定

傳統的FCM 算法采用多種方法獲取最佳聚類數kopt。文獻［13］提出一些檢驗聚類有效性的函數來評估聚類結果并確定kopt，但是這些有效性函數自身存在一定的問題，一般很難直接確定。文獻［14-15］提出使用一種新的緊密度和分離度的指標，文獻［16-17］使用輪廓系數來確定kopt，這些算法在每次迭代中，通過有效性函數衡量聚類結果，最后利用指標值來估計kopt，但是對于大型數據集，需要較高的計算量資源。以上研究雖然確定了最佳聚類數，但仍存在k值最優搜索不穩定、計算復雜度高等問題，因此，需要事先確定k的搜索范圍，即確定kopt的上下限[kmin，kmax]。由于kmin=1 表示樣本均勻分布，無法區分樣本基本特征，因此一般情況下設置kmin最小為2。關于如何確定kmax，目前尚無明確的理論指導，很多學者根據經驗規則來獲取，其中n為樣本點的個數［18］，而文獻［19］中所有數據集的樣本數和實際類數并不具有這樣的性質。由此可見，僅僅利用有效性指標或者經驗規則確定FCM 算法的最佳聚類數不具有普遍性，且FCM 算法聚類中心的隨機初始化更是對聚類質量造成了極大的影響。本文在引入密度敏感距離的基礎上，利用AP 算法獲取粗類數作為kmax，并結合輪廓系數自動確定最佳聚類數。AP 算法的基本原理是經過樣本對象彼此的消息傳遞以獲取高質量的聚類中心，對于類內緊密、類間遠離的聚類結構，AP 算法能獲得比較準確的聚類結果，但對于比較松散的聚類結構，算法傾向于產生較多的局部聚類，這使得算法產生的聚類數往往偏多，從而不能給出準確的聚類結果［20］。AP 算法中的偏向參數p(i)表示樣本點xi被選作聚類中心的傾向性，它對聚類數的大小有重要影響，p(i)越大，傾向于產生的聚類數越多。本文將p(i)統一設置為相似度矩陣的最小值smin［10］。經實驗可證明，當p=smin時，算法結束時得到的聚類數和經驗規則相比，AP 算法獲得的聚類數kAP更接近正確類數。

2.3 初始聚類中心的確定

在上述聚類數搜索范圍確定的前提下，基于密度敏感距離度量的FCM 算法搜索聚類空間逐步增加聚類數。當聚類數為kmin時，基于最大最小距離算法原則［21］選取kmin個樣本點初始化FCM 算法的聚類中心，之后每增加一個聚類數，在保持上一次初始聚類中心不變的基礎上，再按照最大最小距離算法原則增加一個初始聚類中心，從而保持聚類結果的穩定性和延續性。基于最大最小距離算法選出的聚類中心傾向于屬于不同類別的可能性比較大，這樣可以得到較好的聚類結果。傳統的最大最小距離算法利用比例系數θ作為限制條件來確定聚類數對聚類結果影響很大，而本文是在聚類數已知的前提下進行的，因此無需設定比例系數θ。此外，最大最小距離算法隨機選擇初始聚類中心，會使聚類結果不穩定。根據數據的實際分布情況，選取密度最大點作為最大最小距離算法的第一個聚類中心，這樣所有的初始聚類中心都是確定的，其最終聚類結果也就保證了唯一且穩定，同時此方法有效地避免了噪聲點的選取。

改進的最大最小距離算法具體步驟如下：

算法3改進的最大最小距離算法

輸入聚類數搜索范圍kmin=2，kmax=kAP

輸出k個聚類中心。

步驟1求出各樣本點之間的距離dij，將密度最大的一個樣本點作為第1 個聚類中心。根據確定i點的密度大小，以i點為圓心，包含在以截斷距離dc為半徑的圓內點的個數，即為i點的密度大小。

步驟2當聚類數為2 時，計算剩余樣本對象到Z1的距離，找到距離Z1最大的樣本點作為第2 個聚類中心Z2。

步驟3當聚類數為3 時，計算剩余樣本對象與Z1、Z2之間的距離，并求出它們之中的最小值DZi，將第r個樣本作為第3 個聚類中心。

步驟4當聚類數為k且k≤kmax時，對于已有的（k-1）個聚類中心，計算剩余不屬于聚類中心的樣本對象分別到每個聚類中心的距離Dij，并計算Dt=，將第t個樣本作為第k個聚類中心。當算法滿足結束條件時，算法結束。

2.4 AMMF-DSD 算法

為提高傳統FCM 算法對復雜數據和非凸數據的聚類性能，提高算法聚類結果的穩定性，本文在原有FCM 算法思想的基礎上，提出基于密度敏感距離度量創建相似度矩陣的改進FCM 算法AMMF-DSD。首先利用密度敏感距離代替歐式距離創建相似度矩陣；然后通過設定AP 算法的偏向參數p=smin，獲取粗類數作為kmax，基于此改進最大最小距離算法獲取一些有代表性的樣本點初始化FCM 算法的聚類中心；最后結合輪廓系數自動確定最佳聚類數。AMMF-DSD 算法流程如圖3 所示。

圖3 AMMF-DSD 算法流程Fig.3 Procedure of AMMF-DSD algorithm

對AMMF-DSD 算法的時間復雜度進行分析，主要包含以下3 個部分：

1）利用AP 算法遍歷整個數據集，以獲取粗類數作為kmax，其時間復雜度為O(n2)，其中n是數據點的個數。

2）利用改進最大最小距離算法獲取具有代表性的樣本點作為FCM 算法的初始聚類中心，其時間復雜度為O(n2)。

3）改進的FCM 算法中主要涉及歐氏距離的計算，其計算復雜度為O(n2)，引入的密度敏感距離度量由于采用Dijkstra 的最短路徑算法［23］來實現最小路徑距離的計算，其時間復雜度也為O(n2)。

綜上所述，AMMF-DSD 算法的時間復雜度為3 個部分時間復雜度之和O(n2)，即AMMF-DSD 算法的時間復雜度相比原FCM 算法沒有改變。但AMMF-DSD 算法具有明顯的優勢：按照本文方法獲取的kmax由n降低為粗類數kAP，同時改進最大最小距離算法確定的聚類中心避免了FCM 算法聚類中心初始化時可能出現的初始聚類中心過于鄰近以及多個初始聚類中心都選自同一個類中而小類中沒有初始聚類中心的情況。因此，AMMF-DSD 算法收斂速度較快，可有效減少迭代次數。

3 實驗與結果分析

通過在人工數據集和UCI 數據集上進行實驗評估和分析本文算法性能。實驗環境為Intel?CoreTMi5-1035G1CPU@ 1.00 GHz，內存為8 GB。編程環境為Eclipse，MATLAB R2016b顯示實驗結果。在Windws10操作系統的計算機上運行通過。實驗數據集包括UCI 數據集（Iris、Wine、TAE、Seeds、CMC、Blood、Heart-stat-log、Thyroid、Haber-man、Bu-pa）和人工數據集（Three-circles、Spiral、Line-blobs、Aggregation、Square1）。對比算法包括FCM、K-means 和CFSFDP 算法，其中，CFSFDP 算法是一種快速搜索查詢的利用決策圖確定中心的算法［22］，K-means 算法采用歐氏距離建立相似度矩陣，是一種只適用于凸數據的聚類算法［24］。本文采用聚類準確率（ACC）［25］和調整蘭德系數（ARI）［26］對算法的聚類性能進行評估。

聚類準確率（ACC）用于評估算法的準確性，如式（12）所示，其中，Ci是所提算法的類標簽，?是數據真實的類標簽，δ(x，y)表示函數，map(x)作為最好的映射函數使用了匈牙利算法進行映射，對獲得的中心和真實的中心進行映射。

調整蘭德系數（ARI）如式（13）所示，其中，a是屬于U的同類且屬于V的同類的數據對數目，b是屬于U的同類但屬于V的不同類的數據對數目，c是屬于U的不同類而屬于V的同類的數據對數目，d是屬于U的不同類且屬于V的不同類的數據對數目。ARI 數值越接近1 代表聚類結果越好，越接近0 代表聚類結果越差。

3.1 聚類數搜索范圍

本節運用AP 算法確定聚類數的搜索范圍上限，kmax=kAP，其中設定AP 算法中的參考度為相似度矩陣S的最小值，即p=smin（忽略參數對聚類結果的影響）。與經驗規則進行對比實驗，實驗結果如表1 所示。

表1 AP 算法確定的kmaxTable 1 kmaxdetermined by the AP algorithm

從表1 可以看出，當運用AP 算法確定kmax時，UCI 數據集Iris、Wine、Heart-stat-log、Bu-pa 和人工數據集Aggregation 獲取的聚類數目等于正確類數，而UCI數據集TAE、Seeds、CMC、Blood、Thyroid、Haber-man和人工數據集Three-circles、Spiral、Line-blobs、Square1獲取的聚類數均大于正確類數，但是與經驗規則確定的kmax相比，顯然AP 算法獲取的聚類數更接近正確類數，大幅縮小了kopt的搜索范圍，由此驗證了將AP 算法獲取的聚類數作為kmax是合理的。

3.2 算法對比與分析

在聚類數搜索范圍確定的基礎上，分別對UCI數據集Iris、Wine、TAE、Seeds、CMC、Blood、Heartstat-log、Thyroid、Haber-man、Bu-pa 和人工數據集Three-circles、Spiral、Line-blobs、Aggregation、Squarel進行的實驗。其中，Line-blobs、Three-circles 的伸縮因子ρ設置為e3，Iris、Wine、TAE、Seeds、CMC、Thyroid 的伸縮因子ρ設置為e2，Spiral、Aggregation、Squarel、Blood、Heart-stat-log、Haber-man、Bu-pa 的伸縮因子ρ設置為e。

3.2.1 最佳聚類數

本節將AMMF-DSD 算法和隨機選取初始聚類中心的FCM 算法進行實驗對比，比較這兩種算法關于聚類中心的不同初始化方法對輪廓系數Silhouette的影響，進而比較對最佳聚類數kopt的確定造成的影響。為減少誤差，對每個數據集實驗重復運行10 次，所確定的最佳聚類數kopt如表2 所示。

表2 最佳聚類數Table 2 The optimal number of clusters

從表2 可以看出，在聚類數搜索范圍確定時，AMMF-DSD 算法對于各種數據集獲得的最佳聚類數都等于正確類數，而FCM 算法只有Aggregation、Heart-stat-log、Bu-pa 數據集的kopt等于正確類數，且AMMF-DSD 算法得到的kopt對應的輪廓系數均大于FCM 算法，這進一步驗證了改進后的算法AMMF-DSD是有效的且獲得的最佳類數是合理的。

由于傳統的FCM 算法隨機選取初始聚類中心，使聚類結果存在不穩定的現象，因此隨機選取4 個數據集（Spiral、Line-blobs、Iris 和Wine）對AMMF-DSD和FCM 算法進行算法穩定性對比，實驗結果如圖4所示。從圖4 可以看出，FCM 算法的輪廓系數會隨著實驗次數的不同而呈現出不同的聚類結果，其原因是FCM 算法的初始聚類中心是隨機選取的，因此聚類結果也表現出不穩定的狀態，而AMMF-DSD 算法是對傳統FCM 算法的改進，避免了初始聚類中心隨機選取的問題，且聚類數的搜索范圍又是確定的，其聚類結果就表現出較強的穩定性。AMMF-DSD算法和FCM 算法聚類時得到的迭代次數如圖5 所示。從圖5 可以看出，AMMF-DSD 算法的迭代次數明顯小于FCM 算法，即AMMF-DSD 算法加快了算法的收斂速度，而FCM 算法的迭代次數仍在不斷變化。

圖4 FCM 和AMMF-DSD 算法在4 個數據集上的穩定性對比Fig.4 Stability comparison of FCM algorithm and AMMF-DSD algorithm on four data sets

圖5 FCM 和AMMF-DSD 算法在4 個數據集上的迭代次數對比Fig.5 Iteration time comparison of FCM algorithm and AMMF-DSD algorithm on four data sets

3.2.2 人工數據集上的實驗

分別在Three-circles、Spiral、Line-blobs、Aggregation和Square1 這5 個人工數據集上使用4 種聚類算法進行實驗，實驗數據集見表1，聚類結果如圖6～圖10 所示。從圖6 可以看出，FCM、K-means 和CFSFDP 算法在Three-circles數據集上的聚類效果都不理想，而AMMFDSD 算法能夠正確劃分數據類別。從圖7 可以看出，FCM、K-means 和CFSFDP 算法在Spiral 數據集上依然聚類效果不佳，不能正確聚類，而AMMF-DSD 算法將正確地劃分了數據類別。從圖8 可以看出，FCM 和K-means 算法在Line-blobs 數據集上的聚類效果不理想，CFSFDP 和AMMF-DSD 算法則得到了正確的聚類結果。從圖9 可以看出，AMMF-DSD 算法的聚類效果最好，CFSFDP 算法次之，FCM 和K-means 算法在Aggregation 數據集上的的聚類效果都不好。從圖10可以看出，在Square1 數據集上，AMMF-DSD 算法聚類效果最優，FCM 和CFSFDP 算法僅次之，而K-means 算法的聚類效果最差。

圖6 4 種聚類算法對數據集Three-circles 的聚類結果Fig.6 Clustering results of four clustering algorithms on Three-circles data set

圖7 4 種聚類算法對數據集Spiral 的聚類結果Fig.7 Clustering results of four clustering algorithms on Spiral data set

圖8 4 種聚類算法對數據集Line-blobs 的聚類結果Fig.8 Clustering results of four clustering algorithms on Line-blobs data set

圖9 4 種聚類算法對數據集Aggregation 的聚類結果Fig.9 Clustering results of four clustering algorithms on Aggregation data set

圖10 4 種聚類算法對數據集Square1 的聚類結果Fig.10 Clustering results of four clustering algorithms on Square1 data set

通過對圖6～圖10 實驗的可視化對比實驗分析可知，AMMF-DSD 算法比 K-means、FCM 和CFSFDP 算法更擅長對非凸數據和復雜形狀的數據進行聚類。以上4 種聚類算法在人工數據集上的性能對比如表3 所示。從表3 可以看出，AMMF-DSD算法在Three-circles、Spiral、Line-blobs 和Squarel 數據集上的聚類指標值都是1，在Aggregation 數據集上的聚類指標值均大于對比算法，聚類性能最好，CFSFDP 算法僅在Line-blobs 數據集上的聚類指標值是1。從聚類指標值來看，AMMF-DSD 算法聚類性能最優，CFSFDP 算法次之，而FCM 和K-means算法最差。可見，用密度敏感距離代替歐氏距離創建相似度矩陣大幅提高了原始FCM 算法的聚類性能，聚類數搜索范圍的確定和初始聚類中心的確定也提高了AMMF-DSD 算法的穩定性，聚類效果較好。

表3 4 種聚類算法在人工數據集上的性能對比Table 3 Performance comparison of four clustering algorithms on artificial data sets

3.2.3 UCI 數據集上的實驗

本組實驗選取10 個UCI 數據集將AMMF-DSD算法的聚類結果同CFSFDP、FCM 和K-means 算法的聚類結果進行比較，實驗數據集見表1，各算法得到的ACC 和ARI 指標值見表4。為了減少實驗誤差，每個數據集獨立運行10 次。從表4 可以看出：AMMF-DSD 算法在這10 個UCI 數據集上的聚類指標值均高于K-means、FCM 和CFSFDP 算法，聚類性能最好；本文算法的聚類結果是相對穩定的，因此聚類效果較好；CFSFDP 算法次之；K-means、FCM 算法的指標值隨著實驗次數的不同而呈現出不同的聚類結果，聚類效果欠佳。通過上述分析可以看出，AMMF-DSD 算法具有較好的聚類性能，并且聚類結果也更穩定。

表4 4 種聚類算法在UCI 數據集上的性能對比Table 4 Performance comparison of four clustering algorithms on UCI data set

4 結束語

針對傳統FCM 算法無法識別非凸數據，同時對復雜形狀的數據聚類性能不佳的問題，本文提出使用密度敏感距離代替歐氏距離創建相似度矩陣的AMMF-DSD 算法。該距離度量通過調整伸縮因子ρ，可以同時滿足全局一致性和局部一致性，使得到的相似度矩陣能夠更準確地捕獲真實的數據結構，從而實現對非凸數據的聚類。同時，使用AP 算法確定最佳聚類數的搜索范圍上限kmax，基于此改進最大最小距離算法獲取代表點初始化FCM 算法的聚類中心，并結合輪廓系數確定最佳聚類數。實驗結果表明，AMMF-DSD 算法能夠對非凸數據和復雜形狀的數據進行聚類并提高算法的聚類性能和穩定性，同時加快算法的收斂速度。但是該算法在處理大規模數據時需要較大的存儲空間和計算時間，并且算法結果受參數取值的影響大，下一步將結合Spark 框架和抽樣技術實現算法的并行化，改善算法的大數據聚類性能并減小對參數的敏感度。