朱崢瑜，宋 燕

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

1 引 言

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

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

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

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

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

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

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

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

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

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

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

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

2.1 FCM算法

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

(1)

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

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

(2)

(3)

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

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

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

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

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

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

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

參照文獻[24]，PDS相關概念描述如下.

首先通過示例說明PDS的計算形式:

(4)

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

(5)

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

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

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

(6)

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

(7)

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

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

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

(8)

(9)

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

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

3.1 改進的算法推導

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

(10)

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

隸屬度uij和權重ωjs被定義為：

(11)

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

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

(12)

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

(13)

(14)

(15)

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

基于以上的改進并不能幫助算法解決對初始值敏感和易于陷入局部極值的不足，所以基于上述改進的算法，本文再利用具有強大全局搜索能力的PSO算法與之結合，來解決對初始值敏感和易于陷入局部極值的問題.

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

(16)

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

3.2 改進算法的算法流程

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

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

輸出:每個樣本的類別標簽

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

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

3.使用式(14)計算特征W權重；

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

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

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

4 實驗結果與分析

4.1 實驗數(shù)據(jù)與評估指標

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

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

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

在本文實驗中，5種聚類算法的結果通過以下精度(ACC%±STD)，記作M1和歸一化互信息(NMI%±STD)，記作M2來評估:

(17)

(18)

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

4.2 實驗結果分析

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

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

A2:PDS+文獻[15]，應用文獻[15]中的MWFCM，結合特征權值信息和簇間距離信息；

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

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

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

因為大部分算法無法直接分析不完全數(shù)據(jù)，本文采用組合形式，將PDS應用于文獻[3，15，27]，使其能應用于不完全數(shù)據(jù)集從而進行性能比較.實驗結果見表2-表4.此外，本文對聚類結果進行了顯著性驗證.原假設H0為聚類算法結果與原標簽結果之間不存在顯著性差異，在顯著性水平α=0.05的情況下，p>0.05接受原假設，p≤0.05則拒絕原假設.實驗結果見表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 不同缺失率下聚類算法顯著性檢驗結果Table 5 Significance test results of clustering algorithmswith different missing rates

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

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

從表2-表4可以看出，在相同缺失率的情況下，本文提出的基于多重信息的不完全數(shù)據(jù)FCM算法在絕大多數(shù)數(shù)據(jù)集上的聚類準確性最高，具有較好的NMI指標.并且通過對聚類結果的顯著性檢驗，絕大多數(shù)都能接受原假設，除了數(shù)據(jù)集D6和D8.主要因為在算法迭代過程中，本文提出的算法不但考慮了特征權重，而且是動態(tài)地更新權重，而非固定權重.此外，本文提出的算法的目標函數(shù)值要小于對比算法，主要是因為引入了PSO算法，通過其全局尋優(yōu)能力克服FCM算法易于陷入局部極值的缺點.因此，本文提出的改進算法聚類性能是優(yōu)于文獻[3]、文獻[15]以及文獻[27]的.

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

(19)

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

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

4.3 計算復雜度

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

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

5 結束語

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