動態區間的加權模糊聚類算法*

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

遼寧大學 信息學院，沈陽110036

1 引言

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

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

隨著對估值填補算法的深入研究，發現使用區間型數據能夠進一步提高不完整數據聚類的模糊性和魯棒性[10-12]。文獻[10]提出一種改進BP（back propagation）神經網絡的區間填補不完整數據聚類算法，通過神經網絡對缺失屬性進行區間范圍填補。文獻[11]提出一種區間型核函數模糊聚類算法，利用最近鄰規則確定缺失屬性區間，使用核函數模糊C均值對樣本進行高維映射和聚類。文獻[12]提出一種區間型模糊協同聚類算法，將區間型數據應用于協同聚類使聚類結果更加準確。

為了減小離群點對聚類中心的影響，結合近鄰區域內樣本的數量，一些學者也提出新的加權聚類算法。文獻[13]提出一種自然最近鄰優化的密度峰值聚類算法，根據樣本局部分布密度峰值及稀疏區域劃分的特點確定聚類中心。文獻[14]提出一種基于超球面密度的聚類算法，能夠更快獲得位于數據密集區域的初始聚類中心，從而加速算法收斂。文獻[15]提出一種基于約束性密度峰的快速搜索聚類算法，充分利用約束條件下的結構信息，快速獲取密度度量從而加速聚類。文獻[16]提出一種自適應區間加權聚類算法，動態調整區間樣本的關聯權值來明確不同區間樣本對聚類中心的貢獻大小。

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

2 模糊聚類算法

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

2.1 FCM聚類算法

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

2.2 區間型FCM聚類算法

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

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

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

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

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

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

2.3 區間型FCM聚類算法流程

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

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

步驟2更新聚類中心矩陣：當迭代到第l次時，結合隸屬度劃分矩陣U(l-1)，利用聚類原型計算公式（4）和式（5）更新聚類中心矩陣。

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

步驟4算法終止迭代條件：當迭代次數達到最大值時，或時停止迭代，則FCM 算法停止，輸出劃分矩陣U和聚類原型矩陣；否則l=l+1，返回步驟2。

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

3 不完整數據動態區間估計

根據最近鄰規則[24]提出一種新的樣本間屬性相關度計算方法，計算不完整數據和其他數據之間的相關度，構建出不完整數據的最近鄰樣本集。依據最近鄰樣本的屬性取值范圍預測不完整樣本缺失屬性的區間范圍。為進一步減小區間取值帶來的誤差，提出動態控制區間大小的區間因子，通過最近鄰樣本的離散度確定的區間因子來控制對應區間的大小，即對不完整樣本的動態區間填補。

3.1 近鄰樣本的選取

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

式中，Ai和Bi分別代表變量A和B中的第i個數據。

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

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

Ij的計算如式（10）所示：

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

3.2 動態區間估計

3.2.1 區間因子的機制

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

為了進一步提高算法的準確率，降低區間大小對模糊聚類結果準確率的干擾，提出動態控制區間范圍的區間因子，對缺失屬性填補區間進行控制。近鄰樣本都具有很高的相似性，因而最近鄰樣本集中樣本的分布也能體現屬性的分布情況。對于不完整樣本的待填充屬性，其最近鄰樣本集的離散度反映了樣本遠離預測中心的程度，樣本密集則區間因子控制的屬性估值區間減小。

3.2.2 區間因子的計算

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

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

3.2.3 區間大小的確定

對缺失屬性xkj，通過提出的屬性相關度計算公式（9）構造最近鄰樣本集，并確定填補區間。

為進一步減小區間化填補數據的誤差，利用最近鄰樣本集中樣本分散程度計算出的區間因子來控制填補區間的大小，即，新的填補區間為。

例如，通過xkj最近鄰樣本集確定的填補區間[1，3]，區間中值=2，若樣本集較發散，區間因子α=0.9，則新填補區間為[1.1，2.9]；若樣本集較密集，區間因子α=0.3，則新填補區間為[1.7，2.3]，從而對缺失屬性進行動態區間填補。

4 加權模糊聚類算法

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

4.1 區域密度加權算法

區域密度加權算法通過統計數據樣本點在近鄰區域內其他樣本點的個數，進而對該樣本賦予權值[26]。s維數據集X={x1,x2,…,xn}，其權值計算過程如下：

首先確定數據的統計范圍，如式（14）所示：

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

權值的計算公式如式（16）：

其中，mp代表數據xp一定范圍內近鄰點的個數，計算公式如式（17）和式（18）所示：

4.2 區間型數據權值計算

對數值型數據權值賦予方式進行改進，提出適用于區間型數據的權值賦予方式，改進如下：

對于有樣本總數為n的s維區間型數據集，樣本的每個屬性都是區間型數據，對于任意的數據表示形式為，其權值計算過程如下：

確定數據的統計范圍，如式（19）所示。

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

4.3 區間型加權模糊聚類模型

由于數據自身存在離群點的問題，填補后的區間型數據集仍有部分離群點的存在，為進一步減小區間值的誤差，增加區間數據集聚類的精度，本文對區間型模糊C均值的迭代過程進行了改進，把權值加入到區間型模糊C均值的迭代過程中。

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

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

區間型數據與聚類中心的計算如式（23）所示：

其中，φk表示樣本xk的權值，同時表示第i個聚類中心，為聚類中心矩陣。

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

對式（24）進行最優解求導得式（25）、式（26）：

對式（26）求解得式（27）：

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

進行最優解求導得式（30）：

4.4 DI-WIFCM聚類算法流程

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

步驟1確定最近鄰樣本數：通過最近鄰規則確定最近鄰樣本數q。

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

步驟3填補缺失屬性：利用式（11）、式（12）和式（13）計算區間因子，把數據改成區間的形式進行填補。

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

步驟5計算樣本權值：通過式（16）對樣本進行加權。

步驟6更新聚類中心矩陣：當迭代到第l次時，結合隸屬度劃分矩陣U(l-1)，利用聚類原型計算公式（31）和（32）更新聚類中心矩陣。

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

步驟8算法終止迭代條件：當迭代次數達到最大值時，或時停止迭代，則聚類算法停止，輸出劃分矩陣U和聚類中心矩陣V；否則l=l+1，返回步驟6。

上述DI-WIFCM 算法中，不完整數據的動態區間填充的時間復雜度為O(kn)，樣本加權的時間復雜度為O(n2)，DI-WIFCM 算法的時間復雜度為O(kn+n2+Gnsc)，其中k為不完整樣本個數，n為樣本個數，G為迭代最大次數，s為樣本維數，c為聚類中心個數。

5 實驗結果及分析

5.1 數據集及實驗參數選取

本文選取UCI 數據集中的三個數據集（Iris、Breast、Bupa）和兩個人工數據集（Test1、Test2）作為實驗樣本。這三個UCI 數據集信息的相關描述如表1所示。

Table 1 Description of UCI dataset表1 UCI數據集描述

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

Table 2 Parameters of artificial dataset表2 人工數據集參數

5.2 實驗對比結果

每種算法在不同數據集上進行多次實驗后的結果如表3～表11所示。

Table 3 Averaged number of misclassification using incomplete Iris dataset表3 不完整數據集Iris的平均聚類錯分數

Table 4 Averaged number of misclassification using incompleted Breast dataset表4 不完整數據集Breast的平均聚類錯分數

Table 5 Averaged number of misclassification using incompleted Bupa dataset表5 不完整數據集Bupa的平均聚類錯分數

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

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

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

Table 9 Averaged standard deviation of misclassification using incompleted Iris dataset表9 不完整數據集Iris的平均聚類錯分數標準差

Table 10 Averaged standard deviation of misclassification using incompleted Breast dataset表10 不完整數據集Breast的平均聚類錯分數標準差

Table 11 Averaged standard deviation of misclassification using incompleted Bupa dataset表11 不完整數據集Bupa的平均聚類錯分數標準差

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

從表3～表5中平均聚類錯分數來看，DI-WIFCM算法在每個數據集中都取得了最好的結果，平均聚類錯分數作為最重要的聚類算法評價指標，說明DIWIFCM 有很好的聚類準確率。且樣本隨著缺失率的增加平均聚類錯分數相對于其他算法進一步降低，說明DI-WIFCM 算法中區間因子對區間范圍的約束有效性高，隨著數據缺失比例的增加，更能體現數據的信息價值，有著很強的適應能力。

從表6～表8 中平均迭代次數來看，DI-WIFCM算法在大多數情況下沒有取得最少迭代次數的結果。DI-WIFCM算法較其他對比算法計算復雜，但是經過一定次數迭代后也能取得穩定收斂。

從表9～表11 中錯誤分類標準差來看，相對于其他不完整數據算法，DI-WIFCM 有著較低的標準差。證明本文算法在不完整數據聚類方面有很高的準確性和魯棒性。

圖1～圖3 是DI-WIFCM 算法在進行不完整數據聚類時，在三種數據集下目標函數迭代變化趨勢圖，可以看出在不同情況下算法迭代都很穩定。

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聚類迭代圖

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

從表12～表14 中平均聚類錯分數來看，DIWIFCM在整體上優于其他算法。從表15～表17中聚類錯分數標準差來看，DI-WIFCM算法多次取得最優解，尤其在Breast 中三種情況下得到最小值，整體性能及穩定性優于其他算法。

Table 12 Averaged number of misclassification of five improved FCMs in incompleted Iris dataset表12 五種改進FCM算法在不完整數據集Iris中平均聚類錯分數

Table 13 Averaged number of misclassification of five improved FCMs in incompleted Breast dataset表13 五種改進FCM算法在不完整數據集Breast中平均聚類錯分數

Table 14 Averaged number of misclassification of five improved FCMs in incompleted Bupa dataset表14 五種改進FCM算法在不完整數據集Bupa中平均聚類錯分數

Table 15 Standard deviation of misclassification of five improved FCMs in incompleted Iris dataset表15 五種改進FCM算法在不完整數據集Iris中聚類錯分數標準差

Table 16 Standard deviation of misclassification of five improved FCMs in incompleted Breast dataset表16 五種改進FCM算法在不完整數據集Breast中聚類錯分數標準差

Table 17 Standard deviation of misclassification of five improved FCMs in incompleted Bupa dataset表17 五種改進FCM算法在不完整數據集Bupa中聚類錯分數標準差

從圖4～圖6 中可以看出DI-WIFCM 算法在大部分情況均取得最優值。基于蟻群優化的不完整數據聚類算法（IS-HAC）與信息反饋式的RBF網絡填充算法（IFRBF-IFCM）都是構造模型通過最近鄰樣本集對不完整數據進行估值填充，然而其估值的不確實性限制了算法的魯棒性。區間分析模糊聚類算法（MIS-FCM）和局部加權的不完整數據聚類算法（GLW-FCM）對不完整數據進行區間化模糊處理和加權聚類，但是沒有考慮樣本集中離群點對聚類中心的影響，因而聚類準確性不高，迭代過程不穩定。

為驗證DI-WIFCM算法的泛化性，將DI-WIFCM算法應用于兩個人工數據集（Test1 和Test2）進行測試，如表18～表20所示。

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

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

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

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

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

Table 18 Averaged number of misclassification using incompleted artificial dataset表18 不完整人工數據集中平均聚類錯分數

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

Table 20 Averaged standard deviation of misclassification using incompleted artificial dataset表20 不完整人工數據集中平均聚類錯分數標準差

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 結束語

針對不完整數據聚類的問題，本文提出動態區間的加權模糊聚類算法（DI-WIFCM），根據最近鄰規則確定待填補樣本的最近鄰樣本集，通過最近鄰樣本集中屬性值的離散程度確定區間因子，從而動態調整缺失屬性的估值區間。為減小離群點對模糊聚類的影響，進一步提高算法的精度，算法對樣本賦予基于密度的權值，并加入到模糊聚類的迭代過程中，使聚類迭代過程更穩定。本文采用三個UCI 數據集和兩個人工數據集對提出的DI-WIFCM 算法進行檢驗，結果表明算法具有較高的準確率。