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

王治和，王淑艷，杜 輝

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

0 概述

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

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

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

1 相關(guān)工作

1.1 FCM 聚類算法

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

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

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

算法1FCM 聚類算法

輸入聚類數(shù)k，初始聚類中心，模糊指標(biāo)m，終止誤差ε

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

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

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

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

1.2 密度敏感距離

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

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

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

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

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

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

定義1密度調(diào)整長度如式（4）所示：

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

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

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

1.3 輪廓系數(shù)

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

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

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

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

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

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

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

輸入聚類數(shù)k，模糊指標(biāo)m，初始聚類中心，終止誤差ε

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

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

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

步驟3根據(jù)新得的聚類中心從密度敏感距離矩陣中獲得新的Dij，重新計算隸屬度函數(shù)uij，迭代循環(huán)，直到聚類中心不發(fā)生變化，算法結(jié)束。

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

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

2.2 最佳聚類數(shù)的確定

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

2.3 初始聚類中心的確定

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

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

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

輸入聚類數(shù)搜索范圍kmin=2，kmax=kAP

輸出k個聚類中心。

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

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

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

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

2.4 AMMF-DSD 算法

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

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

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

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

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

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

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

3 實驗與結(jié)果分析

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

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

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

3.1 聚類數(shù)搜索范圍

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

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

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

3.2 算法對比與分析

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

3.2.1 最佳聚類數(shù)

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

表2 最佳聚類數(shù)Table 2 The optimal number of clusters

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

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

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

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

3.2.2 人工數(shù)據(jù)集上的實驗

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

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

圖7 4 種聚類算法對數(shù)據(jù)集Spiral 的聚類結(jié)果Fig.7 Clustering results of four clustering algorithms on Spiral data set

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

圖9 4 種聚類算法對數(shù)據(jù)集Aggregation 的聚類結(jié)果Fig.9 Clustering results of four clustering algorithms on Aggregation data set

圖10 4 種聚類算法對數(shù)據(jù)集Square1 的聚類結(jié)果Fig.10 Clustering results of four clustering algorithms on Square1 data set

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

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

3.2.3 UCI 數(shù)據(jù)集上的實驗

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

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

4 結(jié)束語

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