一種基于多重信息的不完全數(shù)據(jù)的模糊C均值聚類算法

朱崢瑜，宋 燕

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093) E-mail:sonya@usst.edu.cn

1 引 言

隨著數(shù)據(jù)信息時(shí)代的來(lái)臨，數(shù)據(jù)種類和數(shù)量不斷增加，使得數(shù)據(jù)挖掘技術(shù)成為研究者們的熱門話題.聚類是一種比較流行的數(shù)據(jù)處理方法，廣泛應(yīng)用于模式識(shí)別、機(jī)器學(xué)習(xí)、計(jì)算機(jī)視覺(jué)、圖像處理等領(lǐng)域[1，2].聚類根據(jù)目標(biāo)函數(shù)將一組樣本進(jìn)行同構(gòu)劃分，從而提高同一簇內(nèi)的相似性，降低不同簇間的相似性[3].根據(jù)此種劃分原理可定量地確定樣本的相似性關(guān)系，從而獲得研究對(duì)象合理劃分.

在眾多的聚類算法中，K均值算法[4]由于其簡(jiǎn)單、易于理解，是應(yīng)用最廣泛的聚類算法之一.在K均值算法中，每個(gè)樣本屬于某一確定的簇，并通過(guò)“簇內(nèi)距離平方和最小化”準(zhǔn)則來(lái)實(shí)現(xiàn)對(duì)樣本的劃分.K均值算法對(duì)數(shù)據(jù)的歸屬是一種硬性的劃分(即:反映樣本隸屬于某個(gè)簇的程度的值只能取0或1)[5].然而，現(xiàn)實(shí)中的數(shù)據(jù)往往具有簇的不確定性，因而導(dǎo)致簇之間存在模糊邊界.基于此，在聚類分析中引入模糊劃分的概念十分必要.Bezdek[6]提出的模糊C均值(FCM，F(xiàn)uzzy C Means)算法是一種典型的模糊聚類算法.FCM算法中隸屬度可以取0～1之間的任何數(shù)，并且通過(guò)“簇內(nèi)距離平方和最小化”準(zhǔn)則來(lái)實(shí)現(xiàn)對(duì)隸屬度的模糊化.

盡管FCM算法的提出解決了不確定性數(shù)據(jù)集的聚類問(wèn)題，但其本身還具有一些固有的缺點(diǎn)[7]，比如模糊指標(biāo)m的選擇，對(duì)噪聲數(shù)據(jù)和初始聚類中心敏感，迭代容易陷入局部極值點(diǎn)等[8].迄今為止，有很多學(xué)者對(duì)傳統(tǒng)FCM算法的改進(jìn)研究做出了巨大貢獻(xiàn)，例如文獻(xiàn)[9]中用閔可夫斯基距離代替歐式距離，使聚類算法能適用于復(fù)雜幾何形狀的數(shù)據(jù)；文獻(xiàn)[10]提出結(jié)合硬劃分和軟劃分的半模糊C均值算法，提高聚類的緊致性；文獻(xiàn)[11]利用稀疏表示方法得到樣本與樣本間的相似性，并將此作為判別特征加入目標(biāo)函數(shù)，有效提高了聚類精度；文獻(xiàn)[12]利用粒子群算法(PSO，Particle Swarm Optimization)的全局搜索能力，解決FCM算法對(duì)初始值敏感，以及容易陷入局部極值的缺點(diǎn)；文獻(xiàn)[13-15]針對(duì)每一特征的不同重要性，提出了特征加權(quán)的FCM算法；文獻(xiàn)[7]引入模糊熵作為FCM算法的約束條件，從而提高了聚類的準(zhǔn)確性和抗噪性；在圖像分割領(lǐng)域的研究中，文獻(xiàn)[16]融合空間信息引入的模糊聚類，提高了圖像分割精度.

在對(duì)FCM算法改進(jìn)的過(guò)程中，考慮信息特征是非常重要的.因?yàn)椴煌奶卣鞅硎静煌囊饬x.特征加權(quán)方案是一種增強(qiáng)重要特征而減少瑣碎特征影響的有效方法.由于其有顯著作用，在機(jī)器學(xué)習(xí)是許多學(xué)者的研究重點(diǎn)，例如文獻(xiàn)[17]自動(dòng)計(jì)算個(gè)體特征的權(quán)重，同時(shí)減少不相關(guān)的特征成分；文獻(xiàn)[18]提出基于信息熵特征加權(quán)核函數(shù)的SVM分類方法，以避免核函數(shù)設(shè)計(jì)的盲目性；文獻(xiàn)[19]提出基于全局冗余最小化(AGRM)的特征選擇框架，從全局的角度可以大大減少特征之間的冗余；文獻(xiàn)[20]在基于圖的半監(jiān)督學(xué)習(xí)中引入特征選擇和自動(dòng)加權(quán)，提取出有效的、魯棒的特征；文獻(xiàn)[21]在圖像分類中提出基于特征融合和加權(quán)的少樣本學(xué)習(xí)多尺度決策網(wǎng)絡(luò)，計(jì)算支持集和查詢集特征之間的余弦相似度作為權(quán)重，引入了關(guān)注機(jī)制，使關(guān)系網(wǎng)絡(luò)更加關(guān)注同一類圖像.

此外，傳統(tǒng)的FCM算法通常需要滿足信息完全的假設(shè)前提.但是，由于數(shù)據(jù)采集環(huán)境的復(fù)雜多變和儀器測(cè)量能力的限制等因素，很難獲取研究對(duì)象的全部信息.據(jù)研究發(fā)現(xiàn)，機(jī)器學(xué)習(xí)領(lǐng)域的基準(zhǔn)數(shù)據(jù)庫(kù)—UCI數(shù)據(jù)集中，有高達(dá)40%的數(shù)據(jù)集包含缺失信息[22].在面對(duì)這樣的數(shù)據(jù)集時(shí)，目前的大多聚類算法是無(wú)效的.因此，研究不完全數(shù)據(jù)集的聚類分析方法是非常必要的.

對(duì)于不完全數(shù)據(jù)的聚類分析，通常可以分為兩步:先對(duì)缺失值進(jìn)行填補(bǔ)[23]；然后再對(duì)填補(bǔ)后的完整數(shù)據(jù)集進(jìn)行聚類.需要說(shuō)明的是，這樣分兩步的實(shí)施策略往往比較耗時(shí).針對(duì)這一問(wèn)題，文獻(xiàn)[24]提出了4種改進(jìn)的FCM策略:完全數(shù)據(jù)策略(WDS，Whole Data Strategy)，部分距離策略(PDS，Partial Distance Strategy)，最優(yōu)完成策略(OCS，Optimal Completion Strategy)和最近原型策略(NPS，Nearest Prototype Strategy)，這4種策略能有效避免增加額外的計(jì)算負(fù)擔(dān).具體來(lái)說(shuō)，WDS是在缺失量占比很小的時(shí)候直接刪除缺少屬性值的樣本，依此策略提出了WDSFCM算法；PDS定義了一種距離函數(shù)，通過(guò)所使用的部分信息的占比的倒數(shù)將僅依賴于已知屬性的結(jié)果縮放到與完整目標(biāo)數(shù)據(jù)集相同的范圍，依此策略提出了PDSFCM算法；OCS把缺失的元素視為附加變量，通過(guò)對(duì)其進(jìn)行迭代優(yōu)化，找到目標(biāo)函數(shù)的最優(yōu)解，依此策略提出了OCSFCM算法；在OCS的基礎(chǔ)上，NPS直接用最接近缺失元素的集群原型替換缺失值，依此策略提出了NPSFCM算法.

盡管FCM算法在完全數(shù)據(jù)聚類的研究中已有相當(dāng)?shù)难芯砍晒?，但不完全?shù)據(jù)的FCM聚類分析尚處于起步階段，更不要說(shuō)能綜合解決不完全數(shù)據(jù)的FCM算法中如對(duì)初始值敏感性、易于陷入局部極值、未充分考慮簇間與簇內(nèi)的樣本差異等問(wèn)題，這也是我們研究的主要?jiǎng)訖C(jī).本文研究不完全數(shù)據(jù)集的聚類問(wèn)題，綜合考慮不同特征權(quán)重、簇內(nèi)間距的最小化和簇間距離的最大化以及避免對(duì)初始值的敏感和局部極值問(wèn)題，提出一種基于多重信息的不完全數(shù)據(jù)的FCM聚類算法.該算法的主要優(yōu)點(diǎn)在于:

1)由于不同特征信息常常表示不同的物理意義，本文使用局部賦權(quán)方法充分考慮各個(gè)特征的重要性，以獲得更好的性能表現(xiàn)；

2)在聚類分析的代價(jià)函數(shù)中不僅考慮了傳統(tǒng)FCM算法中“簇內(nèi)距離平方和最小化”，還合理增加了“簇間距離平方和最大化”；

3)此外，本文采用粒子群優(yōu)化算法(PSO)搜索全局最優(yōu)值，有效地克服FCM算法對(duì)初始值敏感、易于陷入局部最小值的缺點(diǎn).

最后，通過(guò)對(duì)比實(shí)驗(yàn)證明了本文提出的聚類算法不僅能處理不完全數(shù)據(jù)的聚類問(wèn)題，還能有效地提高模糊聚類效果.

2 FCM算法、PDS策略及PSO算法

2.1 FCM算法

FCM算法是通過(guò)最小化如下所示目標(biāo)函數(shù)，將一個(gè)由有限的數(shù)據(jù)組成的集合X={x1，…，xN}劃分為C個(gè)模糊聚類[6]:

(1)

其中，xi∈表示原始數(shù)據(jù)集X的第i列；N和C表示樣本數(shù)和聚類個(gè)數(shù)；pj表示第j個(gè)聚類中心；U?{uij}，i=1，…，N，j=1，…，C是一個(gè)隸屬度矩陣；m是模糊因子，通常取m≥1.

通過(guò)運(yùn)用拉格朗日乘子法，可以得出隸屬度和聚類中心的迭代公式如下:

(2)

(3)

FCM算法執(zhí)行流程:

1)設(shè)定最大迭代步數(shù)Steps，模糊指數(shù)m，終止閾值ε；

2)初始化隸屬度矩陣U=[uij]，聚類中心P=[pj]；

3)利用式(2)計(jì)算隸屬度U=[uij]；

4)利用式(3)計(jì)算新的聚類中心P=[pj]；

5)若‖U(r+1)-U(r)‖<ε或迭代次數(shù)iter>Steps，結(jié)束算法，否則返回步驟3).

2.2 部分距離策略(PDS)及PDSFCM算法

參照文獻(xiàn)[24]，PDS相關(guān)概念描述如下.

首先通過(guò)示例說(shuō)明PDS的計(jì)算形式:

(4)

由式(4)可推出，部分距離公式的一般形式:

(5)

其中，XM表示所有缺失元素的集合，XP表示所有已知元素的集合；S表示數(shù)據(jù)集維數(shù)；xis和pjs分別表示第i個(gè)樣本的第s維特征和第j個(gè)聚類中心的第s維特征.

PDSFCM算法是FCM算法的PDS版本，經(jīng)過(guò)對(duì)傳統(tǒng)FCM算法進(jìn)行修改可以得到:

1)根據(jù)式(5)完成不完全數(shù)據(jù)在式(2)中的計(jì)算，得到的uij更新公式為:

(6)

2)將式(3)的pj替換為：

(7)

由于算法使用交替優(yōu)化，所以有模糊聚類的標(biāo)準(zhǔn)收斂性[25].

2.3 粒子群優(yōu)化算法(PSO)

粒子的位置代表優(yōu)化問(wèn)題在搜索空間中的潛在解，粒子的飛行的方向和距離由它們的速度決定，所有粒子都有一個(gè)被適應(yīng)度函數(shù)f決定的適應(yīng)值[26，27].假設(shè)在一個(gè)S維的目標(biāo)搜索空間中，有N個(gè)粒子組成一個(gè)群落.第i個(gè)粒子的位置表示為矢量(xi1，xi2，…，xiS)，飛行速度表示為(vi1，vi2，…，viS).每個(gè)粒子通過(guò)跟蹤兩個(gè)“最好的位置”來(lái)更新自己，一個(gè)是粒子本身目前所找到的最好位置(pbest)，另一個(gè)是目前整個(gè)群體中所有粒子發(fā)現(xiàn)的最好位置(gbest)，gbest是在pbest中的最好值.對(duì)于第k次迭代，每個(gè)粒子按下式進(jìn)行更新：

(8)

(9)

3 基于多重信息的不完全數(shù)據(jù)的FCM聚類算法

文獻(xiàn)[24]通過(guò)PDS直接利用FCM算法對(duì)不完全數(shù)據(jù)集進(jìn)行聚類分析.其中采用的還是傳統(tǒng)的FCM算法聚類準(zhǔn)則，并沒(méi)有進(jìn)行改進(jìn)，無(wú)法避免FCM算法本身缺點(diǎn)對(duì)聚類結(jié)果造成的影響.而本文引言部分中提及的改進(jìn)文獻(xiàn)都只能針對(duì)完全的數(shù)據(jù)集，并且也不能同時(shí)解決對(duì)初始聚類中心敏感、易于陷入局部最優(yōu)、簇間距離及特征權(quán)重的問(wèn)題.因此，開(kāi)發(fā)一種新的聚類準(zhǔn)則來(lái)同時(shí)解決上述缺點(diǎn)是非常重要的.根據(jù)上述缺陷和已有相關(guān)工作，本文提出一種基于多重信息的不完全數(shù)據(jù)的FCM聚類算法，使得提出的算法能夠解決缺失數(shù)據(jù)聚類問(wèn)題的同時(shí)克服傳統(tǒng)FCM算法的易于陷入局部極值、對(duì)初始聚類中心敏感及未充分考慮類間距離因素以及數(shù)據(jù)集信息的缺點(diǎn)，有效提高聚類的性能表現(xiàn).

3.1 改進(jìn)的算法推導(dǎo)

基于上述考慮，本文將局部特征動(dòng)態(tài)加權(quán)、PSO、簇間距離引入FCM算法，提出了用于不完全數(shù)據(jù)集的改進(jìn)算法.詳細(xì)的目標(biāo)函數(shù)如下:

(10)

其中xis和pis表示第i個(gè)樣本的第s維特征以及第j個(gè)聚類中心的第s維特征；ωjs表示第j類的第s維特征的權(quán)重，β≥0是一個(gè)平衡權(quán)重影響的參數(shù).

隸屬度uij和權(quán)重ωjs被定義為：

(11)

聚類分析的準(zhǔn)則是尋找最優(yōu)的隸屬度矩陣和聚類中心使得目標(biāo)函數(shù)Jm2在約束條件下達(dá)到極小值.通過(guò)本文設(shè)計(jì)的目標(biāo)函數(shù)，可以在數(shù)據(jù)不完全情況下，對(duì)數(shù)據(jù)集進(jìn)行聚類分析，并且能夠動(dòng)態(tài)地根據(jù)特征重要性賦予不同的權(quán)重，以及在考慮“簇內(nèi)距離”的同時(shí)考慮“簇間距離”(即:當(dāng)目標(biāo)函數(shù)Jm2達(dá)到最小時(shí)，“簇間距離”就達(dá)到最大，而“簇內(nèi)距離”就達(dá)到最小).

為了求解帶約束條件式(11)的最小化問(wèn)題式(10)，利用拉格朗日乘子法可構(gòu)造如下目標(biāo)函數(shù):

(12)

在給定KKT條件下，uij、wjs、pjs更新規(guī)則如下:

(13)

(14)

(15)

基于以上討論，本文提出了一種基于多重信息的不完全數(shù)據(jù)FCM聚類算法.與現(xiàn)有的PDSFCM算法相比，通過(guò)隸屬度公式(6)與公式(13)，以及聚類中心公式(7)與公式(15)的對(duì)比可以發(fā)現(xiàn)，本文提出的算法有以下顯著優(yōu)勢(shì):1)在求某個(gè)樣本屬于某個(gè)類的隸屬度的時(shí)候，考慮了在此類別中每一特征的不同權(quán)重；2)在求隸屬度時(shí)，不僅考慮“簇內(nèi)距離”，還額外考慮“簇間距離”最大化.所以通過(guò)以上改進(jìn)，本文的改進(jìn)算法增加考慮多方面信息比PDSFCM算法更合理和全面，能有效克服原算法不足.

基于以上的改進(jìn)并不能幫助算法解決對(duì)初始值敏感和易于陷入局部極值的不足，所以基于上述改進(jìn)的算法，本文再利用具有強(qiáng)大全局搜索能力的PSO算法與之結(jié)合，來(lái)解決對(duì)初始值敏感和易于陷入局部極值的問(wèn)題.

在PSO算法中，將本文提出的基于多重信息的不完全數(shù)據(jù)FCM聚類算法的聚類準(zhǔn)則函數(shù)式(10)作為適應(yīng)度函數(shù):

(16)

粒子通過(guò)改變每一維不同的取值即簇中心的取值從而產(chǎn)生多種聚類結(jié)果，直到找到可接受的簇中心即適應(yīng)度函數(shù)達(dá)到終止條件或整個(gè)循環(huán)達(dá)到最大循環(huán)次數(shù).

3.2 改進(jìn)算法的算法流程

基于多重信息的不完全數(shù)據(jù)FCM聚類算法的基本流程如下:

輸入:聚類個(gè)數(shù)C，數(shù)據(jù)集樣本數(shù)N，學(xué)習(xí)因子c1、c2，慣性權(quán)重δ，最大迭代次數(shù)T，模糊因子m

輸出:每個(gè)樣本的類別標(biāo)簽

1.初始化N個(gè)聚類中心P，形成初代粒子.每個(gè)粒子的pbest為其當(dāng)前位置，gbest為當(dāng)前種群中所有粒子中的最好位置；

2.使用式(13)計(jì)算隸屬度矩陣U；

3.使用式(14)計(jì)算特征W權(quán)重；

4.使用式(16)計(jì)算每個(gè)粒子的適應(yīng)度值，如果優(yōu)于該粒子當(dāng)前的最好位置的適應(yīng)度，則更新該粒子個(gè)體最好位置.如果所有粒子中的最好位置的適應(yīng)度優(yōu)于當(dāng)前全局最好位置的適應(yīng)度值，則更新全局最好位置；

5.使用式(8)和式(9)對(duì)每個(gè)粒子的速度和位置進(jìn)行更新，產(chǎn)生下一代粒子群；

6.如果迭代次數(shù)達(dá)到設(shè)定的最大值，則輸出全局最好位置的粒子，即簇中心的集合，并根據(jù)式(13)得出樣本集的隸屬度矩陣，從而得到聚類標(biāo)簽；如果沒(méi)有達(dá)到最大迭代次數(shù)，則重復(fù)返回步驟2).

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

4.1 實(shí)驗(yàn)數(shù)據(jù)與評(píng)估指標(biāo)

實(shí)驗(yàn)環(huán)境:操作系統(tǒng)為Ubuntu16.04，配置為2.10GZ，24Inter(R)Xeon(R)，2塊TITAN，在Python3平臺(tái)開(kāi)發(fā).實(shí)驗(yàn)采用的數(shù)據(jù)集選自UCI數(shù)據(jù)庫(kù)中的Iris、ParkinsonSpeech、Abalone、Blood、Wine、Ionosphere、Letter Recognition(A，B，C)、Balance-Scale、Vowel數(shù)據(jù)集，具體的信息，如表1所示.

表1 實(shí)驗(yàn)數(shù)據(jù)集信息Table 1 Details of datasets

此外，在所有數(shù)據(jù)集上，我們使用5折交叉驗(yàn)證尋找最優(yōu)超參數(shù)β.總體實(shí)驗(yàn)設(shè)計(jì)，1)數(shù)據(jù)集被隨機(jī)分成5個(gè)互斥的子集，每個(gè)子集都包含數(shù)據(jù)集20%的數(shù)據(jù)；2)選擇4個(gè)子集訓(xùn)練模型，其余子集進(jìn)行驗(yàn)證；3)重復(fù)步驟2)5次根據(jù)不同超參數(shù)下模型的表現(xiàn)，選擇最優(yōu)超參數(shù)；4)根據(jù)選擇的超參數(shù)運(yùn)行10次算法，最后結(jié)果為取10次結(jié)果的均值±標(biāo)準(zhǔn)差形式.

在本文實(shí)驗(yàn)中，5種聚類算法的結(jié)果通過(guò)以下精度(ACC%±STD)，記作M1和歸一化互信息(NMI%±STD)，記作M2來(lái)評(píng)估:

(17)

(18)

其中，N是樣本數(shù)，C是聚類數(shù)目，ei是正確分配到第i個(gè)類的樣本數(shù)；Y是一個(gè)混淆矩陣，Yij表示在A劃分中屬于簇i的樣本個(gè)數(shù)，在B劃分中屬于簇j的樣本個(gè)數(shù)；YA(YB)是在A(B)劃分中的簇的樣本數(shù)；Yi·(Y·j)表示矩陣Y中第i行(第j列)的元素個(gè)數(shù).NMI越大，A和B劃分的相似性就越大.顯然，NMI屬于[0，1]，特別是當(dāng)NMI為1時(shí)，意味著A和B是相同劃分.

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

為了測(cè)試本文提出算法的性能，采用表1所示的數(shù)據(jù)集，在數(shù)據(jù)集具有不同缺失率(缺失比例為:10%、30%、50%)的情況下，本文采用5種算法進(jìn)行對(duì)比，算法1-算法5分別記作A1-A5.

A1:PDSFCM算法[24]，應(yīng)用傳統(tǒng)FCM算法進(jìn)行聚類；

A2:PDS+文獻(xiàn)[15]，應(yīng)用文獻(xiàn)[15]中的MWFCM，結(jié)合特征權(quán)值信息和簇間距離信息；

A3:PDS+文獻(xiàn)[27]，將PSO算法與傳統(tǒng)的FCM算法相結(jié)合；

A4:PDS+文獻(xiàn)[3]，利用大密度區(qū)域以及樣本的密度值變化方法，選取初始聚類中心以及候選初始聚類中心；

A5:本文提出的基于多重信息的不完全數(shù)據(jù)模糊C均值聚類算法.

因?yàn)榇蟛糠炙惴o(wú)法直接分析不完全數(shù)據(jù)，本文采用組合形式，將PDS應(yīng)用于文獻(xiàn)[3，15，27]，使其能應(yīng)用于不完全數(shù)據(jù)集從而進(jìn)行性能比較.實(shí)驗(yàn)結(jié)果見(jiàn)表2-表4.此外，本文對(duì)聚類結(jié)果進(jìn)行了顯著性驗(yàn)證.原假設(shè)H0為聚類算法結(jié)果與原標(biāo)簽結(jié)果之間不存在顯著性差異，在顯著性水平α=0.05的情況下，p>0.05接受原假設(shè)，p≤0.05則拒絕原假設(shè).實(shí)驗(yàn)結(jié)果見(jiàn)表5.

表2 聚類算法性能比較(缺失率10%)Table 2 Performance of different algorithms with 10% missing

表3 聚類算法性能比較(缺失率30%)Table 3 Performance of different algorithms with 30% missing

表4 聚類算法性能比較(缺失率50%)Table 4 Performance of different algorithms with 50% missing

表5 不同缺失率下聚類算法顯著性檢驗(yàn)結(jié)果Table 5 Significance test results of clustering algorithmswith different missing rates

表2-表4實(shí)驗(yàn)結(jié)果，均是算法運(yùn)行10次取平均值.此外，參數(shù)設(shè)置為m=2，c1=c2=2，β為在[-10，10]以2為步長(zhǎng)，進(jìn)行靈敏度測(cè)試的最佳值，具體見(jiàn)表7.

表7 不同數(shù)據(jù)集的參數(shù)設(shè)置 Table 7 Parameters settings of different datasets

從表2-表4可以看出，在相同缺失率的情況下，本文提出的基于多重信息的不完全數(shù)據(jù)FCM算法在絕大多數(shù)數(shù)據(jù)集上的聚類準(zhǔn)確性最高，具有較好的NMI指標(biāo).并且通過(guò)對(duì)聚類結(jié)果的顯著性檢驗(yàn)，絕大多數(shù)都能接受原假設(shè)，除了數(shù)據(jù)集D6和D8.主要因?yàn)樵谒惴ǖ^(guò)程中，本文提出的算法不但考慮了特征權(quán)重，而且是動(dòng)態(tài)地更新權(quán)重，而非固定權(quán)重.此外，本文提出的算法的目標(biāo)函數(shù)值要小于對(duì)比算法，主要是因?yàn)橐肓薖SO算法，通過(guò)其全局尋優(yōu)能力克服FCM算法易于陷入局部極值的缺點(diǎn).因此，本文提出的改進(jìn)算法聚類性能是優(yōu)于文獻(xiàn)[3]、文獻(xiàn)[15]以及文獻(xiàn)[27]的.

為了進(jìn)一步比較3種算法在聚類結(jié)果在“簇間距離最大化”和“簇內(nèi)距離最小化”上的表現(xiàn)，使用Xie-Beni(XB)指標(biāo)[28]作為評(píng)價(jià)指標(biāo)，具體公式如下:

(19)

在圖1(a)-圖1(c)中，每個(gè)數(shù)據(jù)集的5個(gè)柱狀從左至右分別是算法1-算法5的XB指標(biāo)值.從圖中可看出，在不同的缺失比率下，本文提出的算法在XB指標(biāo)上的性能表現(xiàn)對(duì)比于其他算法幾乎都有一定的提升.依據(jù)XB指標(biāo)的結(jié)構(gòu)來(lái)看，本文算法也充分體現(xiàn)了簇內(nèi)距離需要最小化而對(duì)應(yīng)的簇間距離需要最大化的聚類準(zhǔn)則，所以能夠有效地提升算法性能.

圖1 不同缺失率下5種算法XB指標(biāo)Fig.1 Values of XB indexes three algorithms with different missing ratio

4.3 計(jì)算復(fù)雜度

在這一節(jié)中將對(duì)上一節(jié)中的實(shí)驗(yàn)算法進(jìn)行計(jì)算復(fù)雜度分析，假設(shè)迭代次數(shù)為t，每一個(gè)樣本的特征維數(shù)為S，數(shù)據(jù)集樣本數(shù)為N，聚類簇個(gè)數(shù)為C.由于實(shí)驗(yàn)算法為了能處理缺失值，都應(yīng)用了PDS公式，所以不考慮此部分的計(jì)算復(fù)雜度.傳統(tǒng)的FCM算法(A1)的時(shí)間復(fù)雜度為O(NC2St)；文獻(xiàn)[15](A2)的時(shí)間復(fù)雜度為O(C3S3Nt)；文獻(xiàn)[27](A3)的時(shí)間復(fù)雜度為L(zhǎng)*O(NC2S)+O(NC2St)，其中L為PSO算法的迭代次數(shù)；文獻(xiàn)[3](A4)的時(shí)間復(fù)雜度由于t，N，C，S未知，所以為O(CSNt)或O(N2S)；本文算法(A5)的時(shí)間復(fù)雜度為O(C3SNt).具體的平均時(shí)間耗時(shí)見(jiàn)表6.通過(guò)對(duì)每個(gè)算法的時(shí)間復(fù)雜度分析及平均耗時(shí)可以看出本文提出算法計(jì)算復(fù)雜度略高于部分算法，這是因?yàn)樵谄涞^(guò)程中需要計(jì)算的信息量的增加，但是，在計(jì)算復(fù)雜度未爆炸式增長(zhǎng)的情況下，本文提出算法的聚類質(zhì)量是優(yōu)于對(duì)比算法的.

表6 不同缺失率下聚類算法平均時(shí)間(s)Table 6 Average time(s)of clustering algorithmswith different missing rates

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

針對(duì)已有的不完全數(shù)據(jù)集聚類，往往忽略了數(shù)據(jù)特征的不同重要性、簇間距離以及算法對(duì)初始值敏感和易于陷入局部極值，本文通過(guò)特征加權(quán)、簇間距離最大化和PSO算法，提出了針對(duì)于不完全數(shù)據(jù)集的模糊聚類新方法.該方法首先在FCM算法中引入局部特征動(dòng)態(tài)加權(quán)、簇間距離，充分考慮不同特征重要性和簇間距離最大化因素，形成同時(shí)考慮上述因素的目標(biāo)函數(shù).然后把新的目標(biāo)函數(shù)作為適應(yīng)度函數(shù)結(jié)合PSO算法進(jìn)行迭代更新.通過(guò)測(cè)試多個(gè)數(shù)據(jù)集不同缺失率的實(shí)驗(yàn)結(jié)果表明，本文提出的基于多重信息的不完全數(shù)據(jù)FCM算法具有較高的聚類準(zhǔn)確性和較好的聚類效果.當(dāng)然，本文還存在一定的缺陷，如計(jì)算復(fù)雜度略高等，這也將是我們未來(lái)工作的努力方向.