粒子群改進(jìn)模糊C 均值的不完整數(shù)據(jù)聚類

華東計(jì)算技術(shù)研究所 邴兆虹 黃麗茜

在實(shí)際應(yīng)用中，由于各種原因，采集出來的數(shù)據(jù)可能是不完整的，比如，數(shù)據(jù)模糊不清或者是數(shù)據(jù)丟失。因此在數(shù)據(jù)庫中會(huì)經(jīng)常出現(xiàn)不完整數(shù)據(jù)，而且沒有辦法獲得數(shù)據(jù)的真實(shí)值[1]，如果不對(duì)缺失數(shù)據(jù)作出相應(yīng)的處理，對(duì)后續(xù)工作會(huì)造成嚴(yán)重影響。為解決不完整數(shù)據(jù)聚類的問題，國內(nèi)外學(xué)者根據(jù)現(xiàn)有的聚類方法提出了各種新策略。

1 模糊聚類

對(duì)于不完整數(shù)據(jù)的處理方法主要分為兩種：一種是通過估算填充缺失值，即用相對(duì)應(yīng)的已知屬性值的平均值等方法來替換缺失屬性值；另一種方法是直接刪除缺失屬性。對(duì)不完整數(shù)據(jù)進(jìn)行模式識(shí)別最早開始于20 世紀(jì)60 年代，例如，基于概率的估算、EM 算法[2]等。其中基于模糊C 均值處理不完整數(shù)據(jù)的方法應(yīng)用最為廣泛。

模糊C 均值是一種基于模糊理論的聚類算法，即將數(shù)據(jù)集中的數(shù)據(jù)根據(jù)其相對(duì)于聚類中心的隸屬度進(jìn)行分類[3]。

在模糊C 均值中，隨機(jī)選擇的聚類中心容易使算法在迭代過程中陷入局部收斂[4]，而且對(duì)初始值的選取比較敏感，用粒子群改進(jìn)模糊C 均值可以有效地解決這一問題。粒子群優(yōu)化算法是一種新的全局優(yōu)化進(jìn)化算法，它源于對(duì)鳥類捕食行為的模擬。這種算法通過在全部個(gè)體中共享信息來尋找最優(yōu)值。與其他技術(shù)相比，粒子群算法更易實(shí)現(xiàn)，收斂速度更快，需要調(diào)整的參數(shù)較少。但基本粒子群存在易陷入局部最優(yōu)的問題，本文使用變異粒子群優(yōu)化模糊C 均值解決這一問題。

本文在引用[5]基礎(chǔ)上對(duì)聚類算法進(jìn)行了改進(jìn)，首先用最近鄰近點(diǎn)的方法將不完整數(shù)據(jù)集轉(zhuǎn)換成區(qū)間數(shù)據(jù)；然后用變異粒子群優(yōu)化后的模糊C 均值算法對(duì)數(shù)據(jù)集進(jìn)行聚類；最后通過仿真實(shí)驗(yàn)，對(duì)比其他方法的聚類結(jié)果，驗(yàn)證了本文提出方法的有效性。

2 不完整數(shù)據(jù)的處理

不完整數(shù)據(jù)的分類分為兩個(gè)步驟：首先通過各種方法將不完整數(shù)據(jù)集轉(zhuǎn)換成完整數(shù)據(jù)集，然后用合適的聚類方法進(jìn)行聚類。

其中和是與的第j個(gè)屬性，如果和都是非缺失的，則Ij為1，否則為0。

然后按相關(guān)性的大小排列，從中選出6 個(gè)距離缺失屬性最近的數(shù)據(jù)，并用其已知屬性替換缺失屬性；然后在這6 個(gè)屬性值中找出最大值和最小值，確定缺失屬性的區(qū)間，這樣就將不完整數(shù)據(jù)轉(zhuǎn)換成了區(qū)間數(shù)據(jù)。

3 粒子群優(yōu)化模糊C 均值

3.1 區(qū)間數(shù)據(jù)的模糊C 均值

數(shù)據(jù)集中的數(shù)據(jù)如果完全屬于某一類，則該數(shù)據(jù)對(duì)應(yīng)該類的隸屬度為1；完全不屬于，則隸屬度為0，其他情況按照如式（7）所示的公式計(jì)算隸屬度：

模糊C 均值算法首先要初始化隸屬度和聚類中心，所以算法過度依賴初值的選取，而且易陷入局部極小，收斂速度較慢。針對(duì)以上問題，本文采用變異粒子群對(duì)模糊C 均值算法進(jìn)行優(yōu)化。

3.2 變異粒子群

粒子群算法中每個(gè)粒子代表一個(gè)可能的解，群體中每個(gè)粒子在每次迭代過程所經(jīng)歷過的最好位置稱為個(gè)體極值。整個(gè)群體所經(jīng)歷過的最好位置稱為全局極值。每個(gè)粒子都通過上述兩個(gè)極值不斷地更新自己的位置和速度，從而產(chǎn)生新一代群體，在這個(gè)過程中整個(gè)群體對(duì)解空間進(jìn)行全面搜索[5]。

群體規(guī)模為n的粒子群表示為X={x1,x2,...,xn}，第i個(gè)粒子的位置表示為xi，速度為vi，它的個(gè)體極值記為pb，全局極值記為gb，則粒子的速度和位置更新公式如式（8）、式（9）所示：

其中w為慣性權(quán)重，c1，c2是學(xué)習(xí)因子，rand是隨機(jī)產(chǎn)生的0～1 之間的數(shù)。

匯總本文數(shù)據(jù)，所有數(shù)據(jù)均經(jīng)過SPSS20.0版進(jìn)行處理，兩組高血壓伴心力衰竭患者的血壓水平與生存質(zhì)量評(píng)分均以均數(shù)差表示，用t檢驗(yàn)。若P<0.05則代表兩組數(shù)據(jù)比對(duì)差異具統(tǒng)計(jì)學(xué)意義。

基本粒子群的一個(gè)缺點(diǎn)是容易停滯，在停滯階段，粒子的速度幾乎為0，粒子會(huì)聚集在某一點(diǎn)附近，即陷入局部最優(yōu)[7]。而在粒子群迭代的過程中加入變異，可以使種群跳出局部最優(yōu)。當(dāng)粒子群的全局最優(yōu)位置的適應(yīng)值連續(xù)A次都沒有得到改進(jìn)，則認(rèn)為粒子群已經(jīng)聚集到某一局部最優(yōu)位置，此時(shí)整個(gè)粒子群的位置以一定的變異概率進(jìn)行變異。本文取變異概率為，t為迭代次數(shù)，用如式（10）所示的公式改變粒子的位置：

其中max 和min 為搜索空間的上界和下界。

3.3 改進(jìn)的模糊C 均值算法

粒子群優(yōu)化模糊C 均值算法中每個(gè)粒子要存的是各種分類方式下的聚類中心。用粒子群優(yōu)化后得到的聚類中心計(jì)算隸屬度，從而計(jì)算出目標(biāo)函數(shù)，將其作為各粒子的適應(yīng)度值，通過粒子群位置和速度的更新，找到適應(yīng)度最好的粒子，即最小目標(biāo)函數(shù)作為最終解。

對(duì)于一個(gè)不完整數(shù)據(jù)集X={x1,x2,...,xn}，用粒子群優(yōu)化后的模糊C 均值進(jìn)行分類的算法流程如下：

（2）確定粒子群中粒子的個(gè)數(shù)、粒子維數(shù)、初始化粒子速度和位置，設(shè)定最大迭代次數(shù)。

（3）計(jì)算隸屬度和目標(biāo)函數(shù)。

（4）計(jì)算各粒子的適應(yīng)度值。

（5）對(duì)每個(gè)粒子，將它的適應(yīng)度值與它的歷史最優(yōu)的適應(yīng)度值比較，如果更好，則將其作為歷史最優(yōu)。

（6）對(duì)每個(gè)粒子，比較它的適應(yīng)度值和群體所經(jīng)歷的最好位置的適應(yīng)度值，如果更好，則將其作為全局最優(yōu)。

（7）判斷是否滿足變異條件，若滿足則進(jìn)行變異，否則進(jìn)行下一步。

（8）更新粒子的速度和位置。

（9）判斷是否滿足終止條件（迭代次數(shù)達(dá)到最大或者誤差小于給定誤差），滿足則終止，得到分類矩陣和聚類中心，否則轉(zhuǎn)到第（3）步。

4 實(shí)驗(yàn)

為驗(yàn)證本文提出方法的有效性，將該方法與最近鄰區(qū)間法、局部距離法等5 種方法進(jìn)行對(duì)比，同時(shí)對(duì)UCI數(shù)據(jù)庫里的Iris、Wine 兩個(gè)數(shù)據(jù)集進(jìn)行仿真實(shí)驗(yàn)。實(shí)驗(yàn)中的有關(guān)參數(shù)設(shè)定如下：粒子群規(guī)模為100，最大迭代次數(shù)為200 次，最大誤差為10-6，數(shù)據(jù)缺失率分別取5%、10%、15%、20%。

為了測(cè)試本文算法的有效性，將引用[7]提出的4 種方法WDS、PDS、OCS、NPS，最近鄰近區(qū)間法NNI 與本文方法NPF 的實(shí)驗(yàn)室結(jié)果進(jìn)行對(duì)比。

如表1，表2 所示，可以看出，隨著缺失屬性的增加，各種方法的準(zhǔn)確率都有所下降，第一個(gè)數(shù)據(jù)集的準(zhǔn)確率比較穩(wěn)定，下降幅度不是很大。本文提出的方法在Iris數(shù)據(jù)集的缺失率為15%，Wine 數(shù)據(jù)集缺失率為20%時(shí)的正確率較低，其他情況下，本文方法的準(zhǔn)確率是較高的。同時(shí)，本文方法的迭代次數(shù)較多，但是在缺失率為15%和20%時(shí)，NNI 和NPF 的迭代次數(shù)相差并不是很多。

表1 不完整Iris 數(shù)據(jù)集30 次實(shí)驗(yàn)結(jié)果的平均值及平均迭代次數(shù)Tab.1 Averaged results of 30 trials using incomplete iris data set

表2 不完整Wine 數(shù)據(jù)集30 次實(shí)驗(yàn)結(jié)果的平均值及平均迭代次數(shù)Tab.2 Averaged results of 30 trials using incomplete Wine data set

5 結(jié)論

本文采用變異粒子群改進(jìn)的模糊C 均值算法對(duì)不完整數(shù)據(jù)進(jìn)行分類，針對(duì)模糊C 均值存在對(duì)初值敏感和粒子群易陷入局部最優(yōu)的缺點(diǎn)，提出用變異粒子群改進(jìn)模糊C 均值，當(dāng)粒子群陷入局部最優(yōu)時(shí)，通過對(duì)粒子位置的改變，使粒子跳出局部最優(yōu)。主要過程分為兩部分:首先用最近鄰近點(diǎn)的方法將不完整數(shù)據(jù)轉(zhuǎn)換成區(qū)間數(shù)據(jù)；然后用變異粒子群改進(jìn)的模糊C 均值算法對(duì)區(qū)間數(shù)據(jù)分類。通過與各種方法的實(shí)驗(yàn)結(jié)果對(duì)比，說明了本文方法的有效性。