不完整數(shù)據(jù)聚類算法研究

冷泳林，孫曉紅

(1.渤海大學(xué) 信息科學(xué)與技術(shù)學(xué)院，遼寧 錦州 121000；2.渤海大學(xué) 管理學(xué)院，遼寧 錦州 121000)

0 引 言

電子政務(wù)是國(guó)家機(jī)關(guān)在政務(wù)活動(dòng)中，應(yīng)用信息、網(wǎng)絡(luò)和辦公自動(dòng)化技術(shù)進(jìn)行辦公、管理和為社會(huì)提供公共服務(wù)的一種全新的管理模式。電子政務(wù)系統(tǒng)產(chǎn)生的數(shù)據(jù)除了具有海量、異構(gòu)和實(shí)時(shí)等特性，還具有價(jià)值密度低的特性[1]。具體地說(shuō)，表現(xiàn)為采集數(shù)據(jù)中具有大量不正確、不精確、不完全、過(guò)時(shí)陳舊或者重復(fù)冗余的數(shù)據(jù)。其中以不完全特性表現(xiàn)的尤為突出。導(dǎo)致電子政務(wù)中數(shù)據(jù)缺失的原因包括數(shù)據(jù)采集終端的智能化，如傳感器發(fā)生錯(cuò)誤時(shí)導(dǎo)致數(shù)據(jù)不能被采集到，網(wǎng)絡(luò)傳輸故障或人為因素造成的采集錯(cuò)誤或漏填等[2-3]。

由于缺失數(shù)據(jù)的存在，給決策者的數(shù)據(jù)分析及公民數(shù)據(jù)參考都帶來(lái)了巨大的挑戰(zhàn)。聚類是一種無(wú)監(jiān)督的數(shù)據(jù)挖掘算法，該算法依據(jù)數(shù)據(jù)間的特點(diǎn)將數(shù)據(jù)劃分成不同的類，使得類別內(nèi)的數(shù)據(jù)相似性較大而類別間的數(shù)據(jù)相似度較小[4]。針對(duì)不完整數(shù)據(jù)集，傳統(tǒng)方法都是采用數(shù)據(jù)填充或丟棄缺失數(shù)據(jù)對(duì)象的方式構(gòu)成完整數(shù)據(jù)集后再進(jìn)行聚類。而數(shù)據(jù)填充或丟棄缺失數(shù)據(jù)對(duì)聚類結(jié)果有極大的不確定性，影響聚類精度[5]。

針對(duì)以上問(wèn)題，文中提出一種基于KNN的不完整數(shù)據(jù)AP聚類算法(IAPKNN)。算法首先利用近鄰傳播(affinity propagation，AP)聚類算法對(duì)數(shù)據(jù)集中的完整數(shù)據(jù)進(jìn)行聚類[6]，然后利用KNN思想將完整數(shù)據(jù)集中的吸引度矩陣和歸屬度矩陣擴(kuò)展至整個(gè)數(shù)據(jù)集，繼續(xù)迭代，直至收斂[7]。

1 基于區(qū)間劃分的相似度度量方式

計(jì)算數(shù)據(jù)對(duì)象間的相似性是數(shù)據(jù)聚類的重要前提，對(duì)于完整數(shù)據(jù)，可以使用歐幾里距離、馬氏距離，余弦相似度等方法計(jì)算對(duì)象間的相似性[8]。但這些傳統(tǒng)的度量方法都不適用于不完整數(shù)據(jù)。另外，在不完整信息系統(tǒng)理論中[9]，當(dāng)任意兩個(gè)數(shù)據(jù)對(duì)象的所有屬性值已知并且對(duì)應(yīng)的值不相等時(shí)，它們之間的相似性就為0。很明顯，這是不符合數(shù)據(jù)對(duì)象的相似度規(guī)律。針對(duì)以上問(wèn)題，文中重新定義了連續(xù)數(shù)值型和分類型數(shù)據(jù)的相似性度量方法。

1.1 歸一化處理

為了消除因?yàn)閷傩匀≈捣秶煌a(chǎn)生的不平衡性，需要將所有的屬性值歸一化到一個(gè)確定的數(shù)值范圍內(nèi)，使不同的屬性擁有相同的權(quán)重值[10]。文中采用標(biāo)準(zhǔn)方差來(lái)歸一化屬性集中的連續(xù)特征值。設(shè)數(shù)據(jù)集中每個(gè)屬性的完整對(duì)象數(shù)目為q，其中每個(gè)數(shù)據(jù)對(duì)象oi由m個(gè)屬性{a1,a2,…,am}組成的m維空間的特征向量{ai1,ai2,…,aim}來(lái)描述。則數(shù)據(jù)集中所有向量的屬性值的均值和方差分別為：

(1)

(2)

(3)

通過(guò)以上處理，去掉了數(shù)據(jù)對(duì)象中各屬性之間的量綱，使數(shù)據(jù)對(duì)象服從N(0,1)的正態(tài)分布。下一步式(5)通過(guò)max-min方法將數(shù)據(jù)歸一到[0,1]之間的連續(xù)值：

(4)

(5)

(6)

至此，完成數(shù)據(jù)的歸一化處理。

1.2 連續(xù)數(shù)值型數(shù)據(jù)

對(duì)于連續(xù)數(shù)值型數(shù)據(jù)，文中提出了一種基于區(qū)間劃分的相似性度量方法。假設(shè)屬性aj是一個(gè)數(shù)值型屬性，其值域范圍是[x,y]。設(shè)avg(aj)為屬性值aj的平均值，則avg(aj)∈[x,y]。定義α和β是兩個(gè)相似度的度量系數(shù)，它們?nèi)≈等缦拢?/p>

(7)

對(duì)于數(shù)據(jù)集O中任意兩個(gè)數(shù)據(jù)對(duì)象o1和o2，它們?cè)趯傩詀j下取相同值的概率定義如下：

(8)

其中，|Vj|表示屬性aj所包含的不同元素的個(gè)數(shù)。由于數(shù)值型數(shù)據(jù)的連續(xù)性，在真實(shí)的數(shù)據(jù)集中，|Vj|的取值非常大，1/|Vj|的取值則非常小。為了解決這種問(wèn)題，文中采用離散化的方法將連續(xù)數(shù)值型數(shù)據(jù)轉(zhuǎn)化成離散值，|Vj|就可以表示離散后類別數(shù)目，用Dc表示。

常用的離散器有比例離散器(proportional discretizer，PD)和固定頻率離散器(fixed frequency discretizer，F(xiàn)FD)[11]。用Dc和Dr表示離散器中所包含類別數(shù)目和每個(gè)類別中所包含的數(shù)據(jù)數(shù)目。則Dc和Dr滿足DcDr=n。在比例離散器中滿足Dc=Dr=在固定頻率離散器中，Dr可以根據(jù)實(shí)際情況自己設(shè)定，Dc=「n/Dr?。圖1給出了PD和FFD離散器在連續(xù)數(shù)值型屬性a下的離散結(jié)果。數(shù)據(jù)集中共包含16個(gè)數(shù)據(jù)對(duì)象，在比例離散器中，Dc=Dr=4。設(shè)固定頻率離散器中Dr=2，則Dc=8。理想的離散結(jié)果應(yīng)滿足：

(1)同一離散類別中的離散數(shù)據(jù)相近；

(2)不同類別間不能存在相同數(shù)據(jù)。

但由圖1可以看出，比例離散器不滿足條件(1)，而固定頻率離散器不滿足條件(2)。為此，提出了一種等步長(zhǎng)離散器(equal step length discretizer，ESLD)。

(9)

則屬性a的第i個(gè)對(duì)象的離散后所對(duì)應(yīng)的類別為：

(10)

圖1 三種離散器原理

1.3 分類型數(shù)據(jù)

分類型數(shù)據(jù)通常代表數(shù)據(jù)的分類，數(shù)據(jù)之間不存在大小關(guān)系。假設(shè)屬性b對(duì)應(yīng)的是分類型數(shù)據(jù)，用|Vb|=n表示屬性b中分類型數(shù)據(jù)的分類數(shù)。兩個(gè)數(shù)據(jù)對(duì)象o1和o2，它們?cè)趯傩詁下取相同值的概率定義如下：

(11)

依據(jù)上述定義，在不完整數(shù)據(jù)集中，度量?jī)蓚€(gè)對(duì)象的相似性可以使用式(12)：

(12)

2 基于KNN的不完整數(shù)據(jù)聚類算法

2.1 矩陣擴(kuò)展

對(duì)于不完整數(shù)據(jù)集，如果通過(guò)度量數(shù)據(jù)對(duì)象間的相似性后直接聚類，由于缺失數(shù)據(jù)的存在，聚類的精度必然受到影響。文中采用兩步聚類的方式，提高不完整數(shù)據(jù)的聚類精度。首先，采用傳統(tǒng)的AP聚類方法在完整數(shù)據(jù)集上執(zhí)行聚類，獲得完整數(shù)據(jù)集的吸引度矩陣和歸屬度矩陣。然后依據(jù)K近鄰思想，將吸引度矩陣和歸屬度矩陣擴(kuò)展到不完整數(shù)據(jù)空間，然后繼續(xù)迭代整個(gè)數(shù)據(jù)集，直到聚類收斂，完成整個(gè)數(shù)據(jù)集的聚類[12]。

AP在聚類完整數(shù)據(jù)集后，完整數(shù)據(jù)集中的每個(gè)數(shù)據(jù)對(duì)象已經(jīng)累積了一些支持，即通過(guò)迭代的消息傳遞，吸引度矩陣和歸屬度矩陣中的元素已經(jīng)是非0元素。當(dāng)將矩陣擴(kuò)展到不完整數(shù)據(jù)集時(shí)，兩個(gè)矩陣中不完整數(shù)據(jù)對(duì)象間，不完整數(shù)據(jù)與完整數(shù)據(jù)對(duì)象間的吸引度和歸屬度都為0。如果直接進(jìn)行消息傳遞，即使不完整數(shù)據(jù)中存在適合條件的聚類中心，也很難在迭代中找到它。基于此，采用KNN來(lái)擴(kuò)展不完整數(shù)據(jù)對(duì)象的吸引度矩陣和歸屬度矩陣，即不完整數(shù)據(jù)對(duì)象與其k個(gè)近鄰，不僅在聚類時(shí)更容易聚到一類，而且它在吸引度矩陣和歸屬度矩陣中對(duì)應(yīng)的元素也與這k個(gè)近鄰接近[13]。

給定吸引度矩陣Rt和歸屬度矩陣At，對(duì)于任意不完整數(shù)據(jù)對(duì)象Ii'，其中t+1≤i'≤t+p，其k個(gè)近鄰為KNN(Ii')={cq1,cq2,…,cqk}，其中1≤q1,q2,…,qk≤t，則不完整數(shù)據(jù)的擴(kuò)展矩陣Rt+p如式(13)所示：

(13)

同理，歸屬度矩陣At+p可以描述如下：

(14)

2.2 基于KNN的不完整數(shù)據(jù)AP聚類算法

文中提出的基于KNN的不完整數(shù)據(jù)AP聚類算法主要包括以下幾個(gè)步驟：

(1)將數(shù)據(jù)集O劃分為完整數(shù)據(jù)集C與非完整數(shù)據(jù)集I，即O=C∪I。

(2)將C中所有數(shù)據(jù)對(duì)象的數(shù)值型屬性值進(jìn)行歸一化處理。

(3)根據(jù)式(7)～式(12)計(jì)算數(shù)據(jù)集C中數(shù)據(jù)對(duì)象的相似度矩陣S。

(4)將C中吸引度矩陣R和歸屬度矩陣A的所有元素設(shè)置為0，根據(jù)AP聚類算法更新吸引度矩陣R和歸屬度矩陣A。

(5)直到聚類中心不再發(fā)生變化，或者已經(jīng)完成了指定的迭代次數(shù)后，停止計(jì)算，否則重復(fù)。

(6)根據(jù)式(13)和式(14)擴(kuò)展吸引度矩陣R和歸屬度矩陣A到不完整數(shù)據(jù)集I。

(7)繼續(xù)迭代。

(8)對(duì)角線的值a(k,k)+r(k,k)>0的數(shù)據(jù)點(diǎn)k為自動(dòng)發(fā)現(xiàn)的聚類中心，而對(duì)于數(shù)據(jù)點(diǎn)i，使其a(i,k)+r(i,k)最大的候選類中心為其真正歸屬的聚類中心。

(9)將非聚類中心數(shù)據(jù)分配到與其相似度最大的簇中心。

2.3 參數(shù)k的確定

參數(shù)k的取值，將影響不完整數(shù)據(jù)對(duì)象在吸引度和歸屬度矩陣中元素的取值。如果k的取值過(guò)小，意味著擴(kuò)展矩陣元素取值的參照范圍太小，其準(zhǔn)確性將降低，如果取值過(guò)大，而混淆各子類間屬性特征，也很難得到正確的估算結(jié)果。實(shí)驗(yàn)表明，在不同的數(shù)據(jù)集中k的取值也不是固定的。因此，文中在不完整數(shù)據(jù)聚類過(guò)程中增加了一步k值的預(yù)測(cè)模型，確定k的最佳取值[14]。

前文已經(jīng)利用AP聚類算法在完整數(shù)據(jù)集C上執(zhí)行聚類得到吸引度矩陣和歸屬度矩陣。對(duì)于該完整數(shù)據(jù)集C，隨機(jī)從中選擇一定比例的數(shù)據(jù)對(duì)象，計(jì)算當(dāng)k的取值為2,3,…時(shí)，根據(jù)式(13)和式(14)計(jì)算這些對(duì)象所對(duì)應(yīng)的吸引度矩陣和歸屬度矩陣元素估計(jì)值。然后將這些估計(jì)值和實(shí)際值進(jìn)行比較，如果估計(jì)值和實(shí)際值小于閾值γ，則認(rèn)為估計(jì)值是準(zhǔn)確的，反之是不準(zhǔn)確的。當(dāng)k的取值不同，得到的估計(jì)準(zhǔn)確率也不同，文中取估計(jì)值準(zhǔn)確率最高時(shí)k所對(duì)應(yīng)的值作為最近鄰k的取值。

3 實(shí)驗(yàn)分析

3.1 數(shù)據(jù)集及環(huán)境設(shè)置

文中選擇3個(gè)UCI標(biāo)準(zhǔn)數(shù)據(jù)集來(lái)驗(yàn)證提出算法的有效性，數(shù)據(jù)集描述如表1所示。UCI數(shù)據(jù)集中IRIS的數(shù)據(jù)屬性是連續(xù)的數(shù)值型數(shù)據(jù)，而Heart和Abalone中既包含連續(xù)數(shù)值型數(shù)據(jù)也有分類型數(shù)據(jù)。在實(shí)驗(yàn)過(guò)程中，為了驗(yàn)證算法的性能，分別對(duì)每一個(gè)缺失率和數(shù)據(jù)集重復(fù)5次實(shí)驗(yàn)，并取5次實(shí)驗(yàn)的結(jié)果的平均值作為最終實(shí)驗(yàn)結(jié)果。

表1 數(shù)據(jù)集描述

為了比較聚類精度，并沒(méi)有直接采用不完整數(shù)據(jù)集做實(shí)驗(yàn)，而是通過(guò)刪除部分完整數(shù)據(jù)集中的數(shù)據(jù)對(duì)象方法來(lái)構(gòu)成不完整數(shù)據(jù)集。數(shù)據(jù)的刪除規(guī)則遵循下列兩條[15]：

(1)每個(gè)不完整數(shù)據(jù)對(duì)象至少一個(gè)屬性值是已知的；

(2)任意屬性在數(shù)據(jù)集中至少保留一個(gè)完整值。

實(shí)驗(yàn)硬件環(huán)境為：Inter Xeon CPU@2.00 GHz×24 CPU處理器，20 GB內(nèi)存和1 TB硬盤。軟件環(huán)境為L(zhǎng)inux操作系統(tǒng)，Java編程語(yǔ)言。

對(duì)原始數(shù)據(jù)集O中的數(shù)據(jù)，按缺失比例為0%、5%、10%、15%、20%、25%的情況將每個(gè)數(shù)據(jù)集生成6個(gè)不同的數(shù)據(jù)集。為了驗(yàn)證文中提出的不完整數(shù)據(jù)聚類算法的性能，進(jìn)行如下的三組實(shí)驗(yàn)。

3.2 k的取值對(duì)擴(kuò)展矩陣精度的影響

前文2.3中闡述了k的取值策略，本部分檢驗(yàn)了k的取值為2～10時(shí)將擴(kuò)展矩陣中去掉5%～25%元素時(shí)，根據(jù)式(13)和式(14)得到的擴(kuò)展矩陣估計(jì)值的準(zhǔn)確率。從圖2中可以看出，對(duì)于IRIS數(shù)據(jù)集，當(dāng)k的值在5或6時(shí)，擴(kuò)展矩陣準(zhǔn)確率最高，而Heart，Abalone的最高準(zhǔn)確率均出現(xiàn)在k的取值是6或7時(shí)。文中依據(jù)此在后續(xù)實(shí)驗(yàn)中取k值的最好效果進(jìn)行實(shí)驗(yàn)。

3.3 不完整數(shù)據(jù)聚類算法驗(yàn)證

為了測(cè)試文中提出的不完整聚類算法的聚類精度，將算法應(yīng)用在數(shù)據(jù)集P、不完整數(shù)據(jù)集C+I和不完整數(shù)據(jù)集中的完整數(shù)據(jù)子集C上進(jìn)行聚類。聚類精度使用如下公式描述：

(15)

其中，ωk表示聚類后的第k個(gè)集合，Cj表示數(shù)據(jù)真實(shí)分類的第j個(gè)集合。

圖3顯示了在不同缺失率下對(duì)幾種數(shù)據(jù)集進(jìn)行聚類的結(jié)果。其中IAPKNN-AP是執(zhí)行在原始沒(méi)有缺失的數(shù)據(jù)集P上的聚類精度，多次聚類結(jié)果相同，說(shuō)明IAPKNN聚類算法在完整數(shù)據(jù)集上具有穩(wěn)定性。在對(duì)完整數(shù)據(jù)子集C進(jìn)行聚類時(shí)，由于不同缺失率下數(shù)據(jù)集C是不一樣的，因此聚類結(jié)果也不相同。但其在數(shù)據(jù)集P的聚類結(jié)果上下浮動(dòng)，有時(shí)數(shù)據(jù)缺失率高，聚類精度反而高。分析其原因是當(dāng)刪除的缺失值所對(duì)應(yīng)數(shù)據(jù)集是數(shù)據(jù)集中造成負(fù)面影響的離群點(diǎn)時(shí)，IAPKNN對(duì)數(shù)據(jù)集C進(jìn)行聚類時(shí)，受這些離群點(diǎn)的影響減小。因此，此時(shí)對(duì)數(shù)據(jù)集C的聚類精度高于對(duì)原始數(shù)據(jù)集P的聚類精度。反之，將低于對(duì)原始數(shù)據(jù)集P的聚類精度。在對(duì)不完整數(shù)據(jù)集C+I進(jìn)行聚類時(shí)，由于受到非完整數(shù)據(jù)集I的影響，從整體上看，IAPKNN的聚類精度都低于對(duì)原始數(shù)據(jù)集P和完整數(shù)據(jù)子集C的聚類精度。而且數(shù)據(jù)缺失比率越高，聚類準(zhǔn)確度越低。

3.4 IAPKNN同其他聚類算法的比較

本部分將所提出的不完整數(shù)據(jù)聚類算法IAPKNN同KNNI-AP和KNNM-AP聚類算法在聚類精度上進(jìn)行了比較。圖3表明，提出的IAPKNN算法在聚類精度上要優(yōu)于這兩種算法，其原因在于，首先KNNI-AP在計(jì)算對(duì)象相似度時(shí)忽略缺失屬性，考慮對(duì)象中已有的屬性信息，如2.3所闡述的，將影響k近鄰的精度。而文中在確定對(duì)象k近鄰時(shí)，采用概率的方法將缺失屬性加以考慮，提高了k近鄰的準(zhǔn)確性。其次，KNNM-AP算法先用k近鄰的均值進(jìn)行缺失數(shù)據(jù)的填充，然后再聚類。而本身數(shù)據(jù)填充算法在填充精度上存在一定誤差，即k近鄰均值不能準(zhǔn)確無(wú)誤地表示出缺失數(shù)據(jù)，魯棒性較差，再在填充數(shù)據(jù)集上進(jìn)行聚類，聚類精度更低。

(a)IRIS (b)Heart (c)Abalone

(a)IRIS (b)Heart (c)Abalone

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

電子政務(wù)數(shù)據(jù)采集過(guò)程中，由于硬件、網(wǎng)絡(luò)穩(wěn)定性、隱私等問(wèn)題不可避免地在數(shù)據(jù)采集過(guò)程中發(fā)生漏采集、傳輸丟失、漏填寫等問(wèn)題，進(jìn)而導(dǎo)致數(shù)據(jù)的不完整性，阻礙數(shù)據(jù)分析的精度。文中提出了一種基于KNN的不完整數(shù)據(jù)AP聚類算法(IAPKNN)，該算法不同于傳統(tǒng)的先填充后聚類的算法思想，首先將數(shù)據(jù)集分為完整數(shù)據(jù)集和不完整數(shù)據(jù)集，然后針對(duì)完整數(shù)據(jù)集直接利用AP聚類算法。對(duì)于不完整數(shù)據(jù)，首先依據(jù)定義的不完整信息系統(tǒng)的數(shù)據(jù)相似度度量方法，然后利用KNN尋找數(shù)據(jù)k個(gè)近鄰，并依據(jù)k近鄰對(duì)不完整數(shù)據(jù)集的吸引度矩陣和歸屬度矩陣進(jìn)行擴(kuò)展，最后實(shí)現(xiàn)AP聚類。實(shí)驗(yàn)結(jié)果表明，該算法能夠有效地對(duì)不完整數(shù)據(jù)進(jìn)行聚類。