動(dòng)態(tài)區(qū)間的加權(quán)模糊聚類算法*

羅 浩，王彥捷，牛明航，邱存月，張 利

遼寧大學(xué) 信息學(xué)院，沈陽110036

1 引言

進(jìn)入信息時(shí)代，數(shù)據(jù)激增，隨時(shí)都能積累大量數(shù)據(jù)，為了充分挖掘數(shù)據(jù)中的價(jià)值，對(duì)數(shù)據(jù)進(jìn)行聚類分析是一種有效的方法。模糊C 均值（fuzzy C-means，F(xiàn)CM）是一種應(yīng)用最廣泛、最成熟的聚類算法，但是模糊C 均值算法的局限性是不能處理不完整的數(shù)據(jù)集，需要把不完整的數(shù)據(jù)集填充完整才能聚類分析[1]。在數(shù)據(jù)采集過程中由于噪聲干擾、傳感器異常等原因不可避免地產(chǎn)生不完整數(shù)據(jù)，這對(duì)聚類造成很大影響，因而也成為一個(gè)研究熱點(diǎn)。

為解決不完整數(shù)據(jù)的模糊C均值聚類問題，許多學(xué)者提出了對(duì)缺失屬性估值填補(bǔ)的改進(jìn)算法[2-9]。其中文獻(xiàn)[5]構(gòu)造了一種高斯RBF（radial basis function）核函數(shù)，對(duì)樣本中的缺失屬性進(jìn)行填充。文獻(xiàn)[6]提出一種新的貝葉斯估值算法對(duì)缺失數(shù)據(jù)進(jìn)行估值填補(bǔ)。文獻(xiàn)[7]提出一種新的模糊聚類規(guī)則模型，利用中智模糊聚類得到的隸屬度矩陣生成初始模糊規(guī)則，能夠有效處理數(shù)據(jù)中的噪聲，整體提高模型的逼近性。文獻(xiàn)[8]以互信息為依據(jù)對(duì)數(shù)據(jù)集中的屬性進(jìn)行排序，充分考慮了數(shù)據(jù)集中與位置相關(guān)的屬性值特征，對(duì)排序后的不完整數(shù)據(jù)集進(jìn)行估值填充。文獻(xiàn)[9]提出基于稀疏表示的混合屬性數(shù)據(jù)填補(bǔ)方法，將局部約束線性編碼和局部約束稀疏編碼引入到最近鄰樣本構(gòu)建過程，更好地保留了數(shù)據(jù)的局部結(jié)構(gòu)特征。

隨著對(duì)估值填補(bǔ)算法的深入研究，發(fā)現(xiàn)使用區(qū)間型數(shù)據(jù)能夠進(jìn)一步提高不完整數(shù)據(jù)聚類的模糊性和魯棒性[10-12]。文獻(xiàn)[10]提出一種改進(jìn)BP（back propagation）神經(jīng)網(wǎng)絡(luò)的區(qū)間填補(bǔ)不完整數(shù)據(jù)聚類算法，通過神經(jīng)網(wǎng)絡(luò)對(duì)缺失屬性進(jìn)行區(qū)間范圍填補(bǔ)。文獻(xiàn)[11]提出一種區(qū)間型核函數(shù)模糊聚類算法，利用最近鄰規(guī)則確定缺失屬性區(qū)間，使用核函數(shù)模糊C均值對(duì)樣本進(jìn)行高維映射和聚類。文獻(xiàn)[12]提出一種區(qū)間型模糊協(xié)同聚類算法，將區(qū)間型數(shù)據(jù)應(yīng)用于協(xié)同聚類使聚類結(jié)果更加準(zhǔn)確。

為了減小離群點(diǎn)對(duì)聚類中心的影響，結(jié)合近鄰區(qū)域內(nèi)樣本的數(shù)量，一些學(xué)者也提出新的加權(quán)聚類算法。文獻(xiàn)[13]提出一種自然最近鄰優(yōu)化的密度峰值聚類算法，根據(jù)樣本局部分布密度峰值及稀疏區(qū)域劃分的特點(diǎn)確定聚類中心。文獻(xiàn)[14]提出一種基于超球面密度的聚類算法，能夠更快獲得位于數(shù)據(jù)密集區(qū)域的初始聚類中心，從而加速算法收斂。文獻(xiàn)[15]提出一種基于約束性密度峰的快速搜索聚類算法，充分利用約束條件下的結(jié)構(gòu)信息，快速獲取密度度量從而加速聚類。文獻(xiàn)[16]提出一種自適應(yīng)區(qū)間加權(quán)聚類算法，動(dòng)態(tài)調(diào)整區(qū)間樣本的關(guān)聯(lián)權(quán)值來明確不同區(qū)間樣本對(duì)聚類中心的貢獻(xiàn)大小。

借鑒上述學(xué)者的研究，提出一種動(dòng)態(tài)區(qū)間的加權(quán)模糊聚類算法（dynamic interval weighted interval fuzzy C-means clustering algorithm，DI-WIFCM）。首先，根據(jù)屬性相關(guān)度計(jì)算缺失樣本和其他樣本之間的距離，確定最近鄰樣本集，從而確定缺失屬性區(qū)間大小。為減少最近鄰樣本區(qū)間填補(bǔ)缺失屬性的誤差，提出區(qū)間因子來控制填補(bǔ)缺失數(shù)據(jù)區(qū)間的大小，實(shí)現(xiàn)動(dòng)態(tài)區(qū)間填補(bǔ)對(duì)應(yīng)的缺失屬性，將不完整數(shù)據(jù)集轉(zhuǎn)化為完整的區(qū)間型數(shù)據(jù)集。其次，為減小樣本離群點(diǎn)對(duì)聚類的影響，提高聚類準(zhǔn)確率，對(duì)區(qū)間型樣本賦予權(quán)值。權(quán)重通過計(jì)算樣本在近鄰區(qū)域內(nèi)的密度得到，密度越大權(quán)值越大，反之權(quán)值越小，增強(qiáng)中心樣本對(duì)迭代過程中聚類中心選取的影響程度，減弱離群點(diǎn)對(duì)聚類中心點(diǎn)選取的影響。最后進(jìn)行區(qū)間型加權(quán)聚類分析。在多個(gè)UCI 數(shù)據(jù)集和人工數(shù)據(jù)集上與四種經(jīng)典算法[17]和近年來的幾種同類算法比較，驗(yàn)證本文算法的有效性。

2 模糊聚類算法

聚類是將數(shù)據(jù)對(duì)象分為多個(gè)不相交的類（稱為簇）的過程，同一個(gè)類中的對(duì)象彼此之間具有很高的相似性，而不同類中屬性差異明顯。FCM 算法是運(yùn)用最普遍、最成熟的聚類算法，在語音識(shí)別[18]、模型辨別[19]、模糊決策[20]和控制[21]等領(lǐng)域得到廣泛應(yīng)用。本章主要是對(duì)FCM 算法和區(qū)間型FCM 算法（interval fuzzy C-means，IFCM）進(jìn)行的算法分析。

2.1 FCM聚類算法

FCM 是一種很成熟的聚類算法，包含三個(gè)基本算子：模糊隸屬度函數(shù)、分類中心矩陣和目標(biāo)函數(shù)。首先，建立極小化目標(biāo)函數(shù)；其次，利用迭代的思想，優(yōu)化目標(biāo)函數(shù)極小化；最后，根據(jù)每個(gè)樣本依據(jù)隸屬度的大小判斷自己將隸屬于哪一類。

2.2 區(qū)間型FCM聚類算法

區(qū)間型FCM 聚類（IFCM）的數(shù)據(jù)均是區(qū)間型數(shù)據(jù)集[22-23]。設(shè)屬性維度為s的區(qū)間型數(shù)據(jù)集，被分為c類。每個(gè)數(shù)據(jù)都是區(qū)間型，表示 為，其中，1≤j≤s。區(qū)間型模糊C均值算法的目標(biāo)函數(shù)公式如式（1）所示：

隸屬度uik的約束條件如式（2）所示：

區(qū)間樣本xk與聚類中心vi的歐式距離計(jì)算如式（3）所示：

其中，區(qū)間樣本xk的屬性區(qū)間上界向量與下界向量分別為：

聚類中心的區(qū)間上界向量和下界向量分別為：

區(qū)間型聚類中心的更新如式（4）、式（5）所示：

2.3 區(qū)間型FCM聚類算法流程

IFCM算法的基本步驟如下所示：

步驟1初始化算法參數(shù)：設(shè)定迭代停止閾值ε，模糊聚類參數(shù)m，聚類的類別數(shù)c(2≤c≤)，最大迭代次數(shù)G，初始化隸屬度矩陣U(0)。

步驟2更新聚類中心矩陣：當(dāng)?shù)降趌次時(shí)，結(jié)合隸屬度劃分矩陣U(l-1)，利用聚類原型計(jì)算公式（4）和式（5）更新聚類中心矩陣。

步驟3更新隸屬度矩陣：利用式（6）和式（7）更新劃分隸屬度矩陣U(l)。

步驟4算法終止迭代條件：當(dāng)?shù)螖?shù)達(dá)到最大值時(shí)，或時(shí)停止迭代，則FCM 算法停止，輸出劃分矩陣U和聚類原型矩陣；否則l=l+1，返回步驟2。

上述IFCM算法的時(shí)間復(fù)雜度為O(Gnsc)，其中G為迭代最大次數(shù)，n為樣本個(gè)數(shù)，s為樣本維數(shù)，c為聚類中心個(gè)數(shù)。

3 不完整數(shù)據(jù)動(dòng)態(tài)區(qū)間估計(jì)

根據(jù)最近鄰規(guī)則[24]提出一種新的樣本間屬性相關(guān)度計(jì)算方法，計(jì)算不完整數(shù)據(jù)和其他數(shù)據(jù)之間的相關(guān)度，構(gòu)建出不完整數(shù)據(jù)的最近鄰樣本集。依據(jù)最近鄰樣本的屬性取值范圍預(yù)測(cè)不完整樣本缺失屬性的區(qū)間范圍。為進(jìn)一步減小區(qū)間取值帶來的誤差，提出動(dòng)態(tài)控制區(qū)間大小的區(qū)間因子，通過最近鄰樣本的離散度確定的區(qū)間因子來控制對(duì)應(yīng)區(qū)間的大小，即對(duì)不完整樣本的動(dòng)態(tài)區(qū)間填補(bǔ)。

3.1 近鄰樣本的選取

由于近鄰樣本間有著很高的相似性，因此對(duì)于缺失屬性的填補(bǔ)具有很好的指導(dǎo)性。在數(shù)據(jù)挖掘中，余弦相似性用來計(jì)算兩個(gè)對(duì)象之間的相似程度，計(jì)算得到的數(shù)值越大，說明對(duì)象間相似性越高[25]。對(duì)于任意的兩個(gè)隨機(jī)變量A、B，兩個(gè)變量之間的余弦相似性計(jì)算如式（8）所示：

式中，Ai和Bi分別代表變量A和B中的第i個(gè)數(shù)據(jù)。

對(duì)于一個(gè)屬性維度為s的不完整數(shù)據(jù)集X={x1,x2,…,xn}，X中至少存在一個(gè)樣本的某個(gè)屬性是缺失的，缺失屬性的樣本不能缺失該樣本的全部屬性，同時(shí)數(shù)據(jù)集中所有的樣本不能都缺失某種屬性。對(duì)于不完整數(shù)據(jù)集中的樣本xk和樣本xp相似性度量的計(jì)算，根據(jù)余弦相似定理本文提出的屬性相關(guān)度計(jì)算公式如式（9）：

式中，xjk和xjp分別代表樣本xk和樣本xp中的第j個(gè)屬性，m代表要填補(bǔ)的屬性，cos(jm)表示第j個(gè)屬性和第m個(gè)屬性之間的相關(guān)度。

Ij的計(jì)算如式（10）所示：

其中，k,p=1,2,…,n,j=1,2,…,s。

3.2 動(dòng)態(tài)區(qū)間估計(jì)

3.2.1 區(qū)間因子的機(jī)制

在區(qū)間分析法中，設(shè)有區(qū)間型變量X=[x-,x+]，其中x-為區(qū)間最小值，x+為區(qū)間最大值，Xc=為區(qū)間中值，Δx=×α為區(qū)間變量寬度。則X=[x-,x+]=[Xc-Δx,Xc+Δx]，其中α為區(qū)間因子，區(qū)間因子用來控制區(qū)間范圍的大小。對(duì)于任意已知上下限的區(qū)間變量，均可通過控制區(qū)間因子的大小，進(jìn)而約束區(qū)間變量X的大小。

為了進(jìn)一步提高算法的準(zhǔn)確率，降低區(qū)間大小對(duì)模糊聚類結(jié)果準(zhǔn)確率的干擾，提出動(dòng)態(tài)控制區(qū)間范圍的區(qū)間因子，對(duì)缺失屬性填補(bǔ)區(qū)間進(jìn)行控制。近鄰樣本都具有很高的相似性，因而最近鄰樣本集中樣本的分布也能體現(xiàn)屬性的分布情況。對(duì)于不完整樣本的待填充屬性，其最近鄰樣本集的離散度反映了樣本遠(yuǎn)離預(yù)測(cè)中心的程度，樣本密集則區(qū)間因子控制的屬性估值區(qū)間減小。

3.2.2 區(qū)間因子的計(jì)算

區(qū)間因子由缺失樣本的最近鄰樣本離散度決定，區(qū)間因子α的計(jì)算如式（11）所示：

其中，β表示樣本集的離散程度，β的計(jì)算如式（12）所示：

3.2.3 區(qū)間大小的確定

對(duì)缺失屬性xkj，通過提出的屬性相關(guān)度計(jì)算公式（9）構(gòu)造最近鄰樣本集，并確定填補(bǔ)區(qū)間。

為進(jìn)一步減小區(qū)間化填補(bǔ)數(shù)據(jù)的誤差，利用最近鄰樣本集中樣本分散程度計(jì)算出的區(qū)間因子來控制填補(bǔ)區(qū)間的大小，即，新的填補(bǔ)區(qū)間為。

例如，通過xkj最近鄰樣本集確定的填補(bǔ)區(qū)間[1，3]，區(qū)間中值=2，若樣本集較發(fā)散，區(qū)間因子α=0.9，則新填補(bǔ)區(qū)間為[1.1，2.9]；若樣本集較密集，區(qū)間因子α=0.3，則新填補(bǔ)區(qū)間為[1.7，2.3]，從而對(duì)缺失屬性進(jìn)行動(dòng)態(tài)區(qū)間填補(bǔ)。

4 加權(quán)模糊聚類算法

同類樣本具有很高的相似度，因而同類樣本間距離較近，在屬性空間中密度大。傳統(tǒng)樣本的權(quán)值計(jì)算是一種基于距離的計(jì)算，通過該樣本和聚類中心的距離或者和其他樣本之間的距離對(duì)其進(jìn)行權(quán)值計(jì)算，沒有考慮區(qū)域內(nèi)樣本個(gè)數(shù)或密度。同時(shí)數(shù)據(jù)集中存在一些與聚類中心距離遠(yuǎn)的離群點(diǎn)，它們不能有效反映出類別信息，影響聚類中心的選擇和聚類迭代的穩(wěn)定性。針對(duì)以上問題提出一種新的基于區(qū)域密度加權(quán)的聚類算法。對(duì)傳統(tǒng)權(quán)值計(jì)算進(jìn)行改進(jìn)，將樣本的近鄰區(qū)域內(nèi)同類樣本的密度引入聚類權(quán)值的計(jì)算，從而避免了單一距離的計(jì)算，同時(shí)減少離群點(diǎn)對(duì)聚類中心的影響。

4.1 區(qū)域密度加權(quán)算法

區(qū)域密度加權(quán)算法通過統(tǒng)計(jì)數(shù)據(jù)樣本點(diǎn)在近鄰區(qū)域內(nèi)其他樣本點(diǎn)的個(gè)數(shù)，進(jìn)而對(duì)該樣本賦予權(quán)值[26]。s維數(shù)據(jù)集X={x1,x2,…,xn}，其權(quán)值計(jì)算過程如下：

首先確定數(shù)據(jù)的統(tǒng)計(jì)范圍，如式（14）所示：

其中，yj代表數(shù)據(jù)集中的第j個(gè)屬性，||?||2代表范數(shù)。樣本xp和其他樣本之間的距離計(jì)算如式（15）所示：

權(quán)值的計(jì)算公式如式（16）：

其中，mp代表數(shù)據(jù)xp一定范圍內(nèi)近鄰點(diǎn)的個(gè)數(shù)，計(jì)算公式如式（17）和式（18）所示：

4.2 區(qū)間型數(shù)據(jù)權(quán)值計(jì)算

對(duì)數(shù)值型數(shù)據(jù)權(quán)值賦予方式進(jìn)行改進(jìn)，提出適用于區(qū)間型數(shù)據(jù)的權(quán)值賦予方式，改進(jìn)如下：

對(duì)于有樣本總數(shù)為n的s維區(qū)間型數(shù)據(jù)集，樣本的每個(gè)屬性都是區(qū)間型數(shù)據(jù)，對(duì)于任意的數(shù)據(jù)表示形式為，其權(quán)值計(jì)算過程如下：

確定數(shù)據(jù)的統(tǒng)計(jì)范圍，如式（19）所示。

樣本xp和其他樣本之間的距離計(jì)算如式（20）所示：

4.3 區(qū)間型加權(quán)模糊聚類模型

由于數(shù)據(jù)自身存在離群點(diǎn)的問題，填補(bǔ)后的區(qū)間型數(shù)據(jù)集仍有部分離群點(diǎn)的存在，為進(jìn)一步減小區(qū)間值的誤差，增加區(qū)間數(shù)據(jù)集聚類的精度，本文對(duì)區(qū)間型模糊C均值的迭代過程進(jìn)行了改進(jìn)，把權(quán)值加入到區(qū)間型模糊C均值的迭代過程中。

設(shè)屬性維度為s的區(qū)間數(shù)據(jù)集。數(shù)據(jù)，對(duì)于任意的j(1≤j≤s)，，區(qū)間型模糊C均值算法的目標(biāo)函數(shù)如式（21）所示：

其中，隸屬度uik的約束條件如式（22）所示：

區(qū)間型數(shù)據(jù)與聚類中心的計(jì)算如式（23）所示：

其中，φk表示樣本xk的權(quán)值，同時(shí)表示第i個(gè)聚類中心，為聚類中心矩陣。

利用拉格朗日乘子法增廣泛函得式（24）。

對(duì)式（24）進(jìn)行最優(yōu)解求導(dǎo)得式（25）、式（26）：

對(duì)式（26）求解得式（27）：

將式（27）帶入式（25）后i改為t得式（28）：

進(jìn)行最優(yōu)解求導(dǎo)得式（30）：

4.4 DI-WIFCM聚類算法流程

DI-WIFCM算法的具體流程如下：

步驟1確定最近鄰樣本數(shù)：通過最近鄰規(guī)則確定最近鄰樣本數(shù)q。

步驟2計(jì)算最鄰近樣本：根據(jù)式（8）、式（9）和式（10）的屬性距離相似度計(jì)算公式，確定待填補(bǔ)數(shù)據(jù)的最近鄰樣本。

步驟3填補(bǔ)缺失屬性：利用式（11）、式（12）和式（13）計(jì)算區(qū)間因子，把數(shù)據(jù)改成區(qū)間的形式進(jìn)行填補(bǔ)。

步驟4初始化參數(shù)：設(shè)定迭代停止閾值ε，模糊聚類參數(shù)m，聚類的類別數(shù)c(2≤c≤)，最大迭代次數(shù)G，初始化隸屬度矩陣U(0)。

步驟5計(jì)算樣本權(quán)值：通過式（16）對(duì)樣本進(jìn)行加權(quán)。

步驟6更新聚類中心矩陣：當(dāng)?shù)降趌次時(shí)，結(jié)合隸屬度劃分矩陣U(l-1)，利用聚類原型計(jì)算公式（31）和（32）更新聚類中心矩陣。

步驟7更新隸屬度矩陣：根據(jù)聚類中心矩陣，利用式（29）更新隸屬度矩陣U(l)。

步驟8算法終止迭代條件：當(dāng)?shù)螖?shù)達(dá)到最大值時(shí)，或時(shí)停止迭代，則聚類算法停止，輸出劃分矩陣U和聚類中心矩陣V；否則l=l+1，返回步驟6。

上述DI-WIFCM 算法中，不完整數(shù)據(jù)的動(dòng)態(tài)區(qū)間填充的時(shí)間復(fù)雜度為O(kn)，樣本加權(quán)的時(shí)間復(fù)雜度為O(n2)，DI-WIFCM 算法的時(shí)間復(fù)雜度為O(kn+n2+Gnsc)，其中k為不完整樣本個(gè)數(shù)，n為樣本個(gè)數(shù)，G為迭代最大次數(shù)，s為樣本維數(shù)，c為聚類中心個(gè)數(shù)。

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

5.1 數(shù)據(jù)集及實(shí)驗(yàn)參數(shù)選取

本文選取UCI 數(shù)據(jù)集中的三個(gè)數(shù)據(jù)集（Iris、Breast、Bupa）和兩個(gè)人工數(shù)據(jù)集（Test1、Test2）作為實(shí)驗(yàn)樣本。這三個(gè)UCI 數(shù)據(jù)集信息的相關(guān)描述如表1所示。

Table 1 Description of UCI dataset表1 UCI數(shù)據(jù)集描述

相關(guān)實(shí)驗(yàn)中的參數(shù)設(shè)置如下：區(qū)間模糊C均值算法的模糊化參數(shù)m=2，迭代停止閾值ε=10-5，最大迭代次數(shù)G=100，設(shè)置數(shù)據(jù)集的隨機(jī)缺失比例為5%、10%、15%和20%，為減小缺失數(shù)據(jù)的隨機(jī)生成的不確定性給聚類結(jié)果帶來的影響，每個(gè)算法運(yùn)行10次的結(jié)果取平均值，最優(yōu)結(jié)果和次優(yōu)結(jié)果分別用加粗和加下劃線標(biāo)出。兩個(gè)人工數(shù)據(jù)集參數(shù)設(shè)置如表2所示。

Table 2 Parameters of artificial dataset表2 人工數(shù)據(jù)集參數(shù)

5.2 實(shí)驗(yàn)對(duì)比結(jié)果

每種算法在不同數(shù)據(jù)集上進(jìn)行多次實(shí)驗(yàn)后的結(jié)果如表3～表11所示。

Table 3 Averaged number of misclassification using incomplete Iris dataset表3 不完整數(shù)據(jù)集Iris的平均聚類錯(cuò)分?jǐn)?shù)

Table 4 Averaged number of misclassification using incompleted Breast dataset表4 不完整數(shù)據(jù)集Breast的平均聚類錯(cuò)分?jǐn)?shù)

Table 5 Averaged number of misclassification using incompleted Bupa dataset表5 不完整數(shù)據(jù)集Bupa的平均聚類錯(cuò)分?jǐn)?shù)

Table 6 Averaged number of iteration using incompleted Iris dataset表6 不完整數(shù)據(jù)集Iris的平均迭代次數(shù)

Table 7 Averaged number of iteration using incompleted Breast dataset表7 不完整數(shù)據(jù)集Breast的平均迭代次數(shù)

Table 8 Averaged number of iteration using incompleted Bupa dataset表8 不完整數(shù)據(jù)集Bupa的平均迭代次數(shù)

Table 9 Averaged standard deviation of misclassification using incompleted Iris dataset表9 不完整數(shù)據(jù)集Iris的平均聚類錯(cuò)分?jǐn)?shù)標(biāo)準(zhǔn)差

Table 10 Averaged standard deviation of misclassification using incompleted Breast dataset表10 不完整數(shù)據(jù)集Breast的平均聚類錯(cuò)分?jǐn)?shù)標(biāo)準(zhǔn)差

Table 11 Averaged standard deviation of misclassification using incompleted Bupa dataset表11 不完整數(shù)據(jù)集Bupa的平均聚類錯(cuò)分?jǐn)?shù)標(biāo)準(zhǔn)差

在本文的算法對(duì)比實(shí)驗(yàn)中，完備數(shù)據(jù)策略模糊C均值聚類算法（whole data strategy fuzzy C-means clustering，WDS-FCM）和局部距離策略模糊C 均值聚類算法（partial distance strategy fuzzy C-means clustering，PDS-FCM）是舍棄法。WDS-FCM 算法把數(shù)據(jù)集中不完整的樣本數(shù)據(jù)全部剔除，只對(duì)完整的樣本數(shù)據(jù)進(jìn)行模糊聚類，算法在不完整樣本比例增大時(shí)聚類精度會(huì)受到很大影響。PDS-FCM算法將不完整樣本數(shù)據(jù)中的完整屬性加入迭代運(yùn)算，未考慮不完整樣本缺失的屬性信息，沒有充分發(fā)揮不完整樣本的信息價(jià)值。其余的兩種算法，優(yōu)化完整策略模糊C 均值聚類算法（optimal completion strategy fuzzy C-means clustering，OCS-FCM）、最近原型策略模糊C均值聚類算法（nearest prototype strategy fuzzy C-means clustering，NPS-FCM）對(duì)數(shù)據(jù)的處理方式都屬于估值法。OCS-FCM 算法將缺失屬性看作待優(yōu)化變量，在聚類中心和隸屬度矩陣迭代更新過程中同步更新缺失屬性，但是算法需要反復(fù)迭代更新缺失屬性值，使算法迭代次數(shù)增加。NPS-FCM算法用不完整樣本的最近聚類中心對(duì)應(yīng)的屬性值來填補(bǔ)缺失的屬性值，然后繼續(xù)參與算法迭代。隨著迭代次數(shù)的增加，估值的誤差會(huì)被放大，同時(shí)兩個(gè)估值算法都沒有考慮近鄰樣本會(huì)對(duì)缺失屬性的填補(bǔ)起到很好的指導(dǎo)作用，也沒有考慮到樣本屬性彼此之間的關(guān)聯(lián)。

從表3～表5中平均聚類錯(cuò)分?jǐn)?shù)來看，DI-WIFCM算法在每個(gè)數(shù)據(jù)集中都取得了最好的結(jié)果，平均聚類錯(cuò)分?jǐn)?shù)作為最重要的聚類算法評(píng)價(jià)指標(biāo)，說明DIWIFCM 有很好的聚類準(zhǔn)確率。且樣本隨著缺失率的增加平均聚類錯(cuò)分?jǐn)?shù)相對(duì)于其他算法進(jìn)一步降低，說明DI-WIFCM 算法中區(qū)間因子對(duì)區(qū)間范圍的約束有效性高，隨著數(shù)據(jù)缺失比例的增加，更能體現(xiàn)數(shù)據(jù)的信息價(jià)值，有著很強(qiáng)的適應(yīng)能力。

從表6～表8 中平均迭代次數(shù)來看，DI-WIFCM算法在大多數(shù)情況下沒有取得最少迭代次數(shù)的結(jié)果。DI-WIFCM算法較其他對(duì)比算法計(jì)算復(fù)雜，但是經(jīng)過一定次數(shù)迭代后也能取得穩(wěn)定收斂。

從表9～表11 中錯(cuò)誤分類標(biāo)準(zhǔn)差來看，相對(duì)于其他不完整數(shù)據(jù)算法，DI-WIFCM 有著較低的標(biāo)準(zhǔn)差。證明本文算法在不完整數(shù)據(jù)聚類方面有很高的準(zhǔn)確性和魯棒性。

圖1～圖3 是DI-WIFCM 算法在進(jìn)行不完整數(shù)據(jù)聚類時(shí)，在三種數(shù)據(jù)集下目標(biāo)函數(shù)迭代變化趨勢(shì)圖，可以看出在不同情況下算法迭代都很穩(wěn)定。

Fig.1 Iteration graph of DI-WIFCM in Iris圖1 Iris中DI-WIFCM聚類迭代圖

Fig.2 Iteration graph of DI-WIFCM in Breast圖2 Breast中DI-WIFCM聚類迭代圖

Fig.3 Iteration graph of DI-WIFCM in Bupa圖3 Bupa中DI-WIFCM聚類迭代圖

將最近幾年不完整數(shù)據(jù)處理算法區(qū)間監(jiān)督的混雜蟻群優(yōu)化聚類算法（interval supervision hybird ant colony optimization fuzzy C-means clustering algorithm，IS-HAC）[27]、缺失屬性區(qū)間大小調(diào)控的模糊C均值聚類算法（missing attribute interval size fuzzy C-means clustering algorithm，MIS-FCM）[28]、改進(jìn)遺傳優(yōu)化的局部加權(quán)模糊C 均值聚類算法（improved genetic optimized local weighted fuzzy C-means clustering algorithm，GLW-FCM）[29]、信息反饋RBF 網(wǎng)絡(luò)估值的區(qū)間型模糊C 均值聚類算法（information feedback RBF network interval estimation fuzzy C-means clustering，IFRBF-IFCM)[30]與本文算法在UCI 數(shù)據(jù)集下進(jìn)行對(duì)比實(shí)驗(yàn)。

從表12～表14 中平均聚類錯(cuò)分?jǐn)?shù)來看，DIWIFCM在整體上優(yōu)于其他算法。從表15～表17中聚類錯(cuò)分?jǐn)?shù)標(biāo)準(zhǔn)差來看，DI-WIFCM算法多次取得最優(yōu)解，尤其在Breast 中三種情況下得到最小值，整體性能及穩(wěn)定性優(yōu)于其他算法。

Table 12 Averaged number of misclassification of five improved FCMs in incompleted Iris dataset表12 五種改進(jìn)FCM算法在不完整數(shù)據(jù)集Iris中平均聚類錯(cuò)分?jǐn)?shù)

Table 13 Averaged number of misclassification of five improved FCMs in incompleted Breast dataset表13 五種改進(jìn)FCM算法在不完整數(shù)據(jù)集Breast中平均聚類錯(cuò)分?jǐn)?shù)

Table 14 Averaged number of misclassification of five improved FCMs in incompleted Bupa dataset表14 五種改進(jìn)FCM算法在不完整數(shù)據(jù)集Bupa中平均聚類錯(cuò)分?jǐn)?shù)

Table 15 Standard deviation of misclassification of five improved FCMs in incompleted Iris dataset表15 五種改進(jìn)FCM算法在不完整數(shù)據(jù)集Iris中聚類錯(cuò)分?jǐn)?shù)標(biāo)準(zhǔn)差

Table 16 Standard deviation of misclassification of five improved FCMs in incompleted Breast dataset表16 五種改進(jìn)FCM算法在不完整數(shù)據(jù)集Breast中聚類錯(cuò)分?jǐn)?shù)標(biāo)準(zhǔn)差

Table 17 Standard deviation of misclassification of five improved FCMs in incompleted Bupa dataset表17 五種改進(jìn)FCM算法在不完整數(shù)據(jù)集Bupa中聚類錯(cuò)分?jǐn)?shù)標(biāo)準(zhǔn)差

從圖4～圖6 中可以看出DI-WIFCM 算法在大部分情況均取得最優(yōu)值?；谙伻簝?yōu)化的不完整數(shù)據(jù)聚類算法（IS-HAC）與信息反饋式的RBF網(wǎng)絡(luò)填充算法（IFRBF-IFCM）都是構(gòu)造模型通過最近鄰樣本集對(duì)不完整數(shù)據(jù)進(jìn)行估值填充，然而其估值的不確實(shí)性限制了算法的魯棒性。區(qū)間分析模糊聚類算法（MIS-FCM）和局部加權(quán)的不完整數(shù)據(jù)聚類算法（GLW-FCM）對(duì)不完整數(shù)據(jù)進(jìn)行區(qū)間化模糊處理和加權(quán)聚類，但是沒有考慮樣本集中離群點(diǎn)對(duì)聚類中心的影響，因而聚類準(zhǔn)確性不高，迭代過程不穩(wěn)定。

為驗(yàn)證DI-WIFCM算法的泛化性，將DI-WIFCM算法應(yīng)用于兩個(gè)人工數(shù)據(jù)集（Test1 和Test2）進(jìn)行測(cè)試，如表18～表20所示。

從表18～表20中可以看出，DI-WIFCM算法在不同數(shù)據(jù)集聚類效果良好，泛化性強(qiáng)。從圖7、圖8中可以看出，在不同人工數(shù)據(jù)集中，DI-WIFCM 算法經(jīng)過一定迭代次數(shù)能夠很快達(dá)到收斂。

本文所提出的DI-WIFCM 算法充分利用了不完整數(shù)據(jù)的屬性特征，確定的最近鄰樣本集能夠很好估計(jì)缺失屬性的范圍，進(jìn)而實(shí)現(xiàn)缺失屬性的區(qū)間填補(bǔ)，同時(shí)使用區(qū)間因子對(duì)區(qū)間范圍進(jìn)行更好的約束。對(duì)樣本進(jìn)行區(qū)域密度加權(quán)，從而減小離群點(diǎn)對(duì)數(shù)據(jù)聚類中心的影響，使聚類迭代過程更穩(wěn)定。通過實(shí)驗(yàn)證明，對(duì)于不完整的數(shù)據(jù)的聚類問題，DIWIFCM算法聚類效果更好。

Fig.4 Comparison of clustering algorithms in Iris圖4 Iris中聚類算法對(duì)比圖

Fig.5 Comparison of clustering algorithms in Breast圖5 Breast中聚類算法對(duì)比圖

Fig.6 Comparison of clustering algorithms in Bupa圖6 Bupa中聚類算法對(duì)比圖

Table 18 Averaged number of misclassification using incompleted artificial dataset表18 不完整人工數(shù)據(jù)集中平均聚類錯(cuò)分?jǐn)?shù)

Table 19 Averaged number of iteration using incompleted artificial dataset表19 不完整人工數(shù)據(jù)集中平均迭代次數(shù)

Table 20 Averaged standard deviation of misclassification using incompleted artificial dataset表20 不完整人工數(shù)據(jù)集中平均聚類錯(cuò)分?jǐn)?shù)標(biāo)準(zhǔn)差

Fig.7 Iteration graph of DI-WIFCM in Test1圖7 Test1中DI-WIFCM聚類迭代圖

Fig.8 Iteration graph of DI-WIFCM in Test2圖8 Test2中DI-WIFCM聚類迭代圖

6 結(jié)束語

針對(duì)不完整數(shù)據(jù)聚類的問題，本文提出動(dòng)態(tài)區(qū)間的加權(quán)模糊聚類算法（DI-WIFCM），根據(jù)最近鄰規(guī)則確定待填補(bǔ)樣本的最近鄰樣本集，通過最近鄰樣本集中屬性值的離散程度確定區(qū)間因子，從而動(dòng)態(tài)調(diào)整缺失屬性的估值區(qū)間。為減小離群點(diǎn)對(duì)模糊聚類的影響，進(jìn)一步提高算法的精度，算法對(duì)樣本賦予基于密度的權(quán)值，并加入到模糊聚類的迭代過程中，使聚類迭代過程更穩(wěn)定。本文采用三個(gè)UCI 數(shù)據(jù)集和兩個(gè)人工數(shù)據(jù)集對(duì)提出的DI-WIFCM 算法進(jìn)行檢驗(yàn)，結(jié)果表明算法具有較高的準(zhǔn)確率。