王治和，王淑艷，杜 輝

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

0 概述

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

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

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

1 相關(guān)工作

1.1 FCM 聚類算法

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

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

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

算法1FCM 聚類算法

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

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

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

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

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

1.2 密度敏感距離

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

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

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

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

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

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

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

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

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

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

1.3 輪廓系數(shù)

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

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

2 基于密度敏感距離的改進(jìn)FCM 算法

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 初始聚類中心的確定

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

改進(jìn)的最大最小距離算法具體步驟如下：

算法3改進(jìn)的最大最小距離算法

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

輸出k個(gè)聚類中心。

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

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

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

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

2.4 AMMF-DSD 算法

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

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

對(duì)AMMF-DSD 算法的時(shí)間復(fù)雜度進(jìn)行分析，主要包含以下3 個(gè)部分：

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

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

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

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

3 實(shí)驗(yàn)與結(jié)果分析

通過(guò)在人工數(shù)據(jù)集和UCI 數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)評(píng)估和分析本文算法性能。實(shí)驗(yàn)環(huán)境為Intel?CoreTMi5-1035G1CPU@ 1.00 GHz，內(nèi)存為8 GB。編程環(huán)境為Eclipse，MATLAB R2016b顯示實(shí)驗(yàn)結(jié)果。在Windws10操作系統(tǒng)的計(jì)算機(jī)上運(yùn)行通過(guò)。實(shí)驗(yàn)數(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）。對(duì)比算法包括FCM、K-means 和CFSFDP 算法，其中，CFSFDP 算法是一種快速搜索查詢的利用決策圖確定中心的算法［22］，K-means 算法采用歐氏距離建立相似度矩陣，是一種只適用于凸數(shù)據(jù)的聚類算法［24］。本文采用聚類準(zhǔn)確率（ACC）［25］和調(diào)整蘭德系數(shù)（ARI）［26］對(duì)算法的聚類性能進(jìn)行評(píng)估。

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

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

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

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

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

從表1 可以看出，當(dāng)運(yùn)用AP 算法確定kmax時(shí)，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)驗(yàn)規(guī)則確定的kmax相比，顯然AP 算法獲取的聚類數(shù)更接近正確類數(shù)，大幅縮小了kopt的搜索范圍，由此驗(yàn)證了將AP 算法獲取的聚類數(shù)作為kmax是合理的。

3.2 算法對(duì)比與分析

在聚類數(shù)搜索范圍確定的基礎(chǔ)上，分別對(duì)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進(jìn)行的實(shí)驗(yàn)。其中，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 算法和隨機(jī)選取初始聚類中心的FCM 算法進(jìn)行實(shí)驗(yàn)對(duì)比，比較這兩種算法關(guān)于聚類中心的不同初始化方法對(duì)輪廓系數(shù)Silhouette的影響，進(jìn)而比較對(duì)最佳聚類數(shù)kopt的確定造成的影響。為減少誤差，對(duì)每個(gè)數(shù)據(jù)集實(shí)驗(yàn)重復(fù)運(yùn)行10 次，所確定的最佳聚類數(shù)kopt如表2 所示。

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

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

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

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

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

3.2.2 人工數(shù)據(jù)集上的實(shí)驗(yàn)

分別在Three-circles、Spiral、Line-blobs、Aggregation和Square1 這5 個(gè)人工數(shù)據(jù)集上使用4 種聚類算法進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)數(shù)據(jù)集見(jiàn)表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 種聚類算法對(duì)數(shù)據(jù)集Three-circles 的聚類結(jié)果Fig.6 Clustering results of four clustering algorithms on Three-circles data set

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

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

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

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

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

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

3.2.3 UCI 數(shù)據(jù)集上的實(shí)驗(yàn)

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

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

4 結(jié)束語(yǔ)

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