裴衛(wèi)杰，龐天杰

(太原師范學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)系，山西 晉中 030619)

0 引言

聚類分析是機(jī)器學(xué)習(xí)領(lǐng)域中一個(gè)重要的研究方向，其主要思想是將數(shù)據(jù)對(duì)象劃分成不同的簇，使得同一簇中的數(shù)據(jù)對(duì)象具有較高的相似度，而不同簇中的數(shù)據(jù)對(duì)象具有較低的相似度.目前，基于劃分、層次、密度、網(wǎng)格等的諸多聚類算法在社會(huì)科學(xué)、地球科學(xué)、生物學(xué)以及醫(yī)學(xué)等領(lǐng)域有廣泛的應(yīng)用[1-3].然而針對(duì)帶有缺失值的不完備數(shù)據(jù)，眾多學(xué)者提出了不同的處理策略，Hathaway等[4]針對(duì)缺失數(shù)據(jù)對(duì)象利用模糊C均值聚類(FCM)算法提出兩種舍棄策略，但是由于舍棄缺失數(shù)據(jù)而丟失了大量信息，導(dǎo)致聚類效果欠佳.目前，不完備數(shù)據(jù)的聚類主要采用了填充策略[5].Li等[6]針對(duì)缺失數(shù)據(jù)提出了一種最近鄰區(qū)間填充法，將不完備數(shù)據(jù)集轉(zhuǎn)化為完備的區(qū)間型數(shù)據(jù)集，而后通過改進(jìn)的FCM算法進(jìn)行聚類；蘇婷等[7]利用q近鄰填充法對(duì)不完備數(shù)據(jù)進(jìn)行填充，然后在完備的數(shù)據(jù)集上進(jìn)行聚類；史倩玉等[8]分別使用均值填充法、K最近鄰填充法和有序最近鄰填充法將缺失值填充，然后在3種填充后的數(shù)據(jù)集上通過K-Prototypes算法多次產(chǎn)生基聚類，最后將基聚類結(jié)果進(jìn)行集成，得到最終聚類結(jié)果.雖然上述方法較好地解決了不完備數(shù)據(jù)聚類問題，但是由于傳統(tǒng)填充法都是一次性填充，而且填充策略帶有一定的主觀性，進(jìn)而影響了聚類結(jié)果的準(zhǔn)確性.因此，針對(duì)數(shù)值型不完備數(shù)據(jù)，如何有效利用含缺失值數(shù)據(jù)的信息，對(duì)其進(jìn)行動(dòng)態(tài)填充并聚類顯得十分重要.

本文針對(duì)不完備數(shù)據(jù)，提出一種基于動(dòng)態(tài)填充的不完備數(shù)據(jù)聚類算法.該算法利用均值填充法對(duì)缺失數(shù)據(jù)進(jìn)行初始化填充，然后對(duì)填充后的數(shù)據(jù)集用K-means算法進(jìn)行聚類，將缺失值用其所在類的類中心的對(duì)應(yīng)屬性值進(jìn)行再次填充，直到聚類結(jié)果不再變化時(shí)停止.

1 相關(guān)工作

1.1 不完備信息系統(tǒng)

I=(U，A，V，f)是一個(gè)不完備信息系統(tǒng)[9].其中，U={x1，x2，…，xn}是非空有限數(shù)據(jù)對(duì)象集合，稱為論域，n是論域中對(duì)象的個(gè)數(shù)；A={a1，a2，…，am}是非空有限屬性集合，m是對(duì)象屬性的個(gè)數(shù)；V={V1，V2，…，Vm}是屬性的值域集，Vi是ai的值域；f是信息函數(shù)，f：Vil=f(xi，al)∈Vl,表示對(duì)象xi在屬性al上的取值為Vil,f(xi，al)=″*″表示屬性值缺失.

xi為第i個(gè)對(duì)象，具有|A·=m個(gè)屬性，即xi=(xi1，xi2，…，xip，…，xim)T,其中，xi表示第i個(gè)對(duì)象xi的第p維屬性值，(j=1，2，…，n；p=1，2，…，m).

在其基礎(chǔ)上，將U分為兩個(gè)子集，即缺失數(shù)據(jù)集合UM和非缺失數(shù)據(jù)集UC,且滿足U=UM∪UC和UM∩UC=?.其中，UM是所有含缺失屬性值對(duì)象的集合，UC是所有不含缺失屬性值對(duì)象的集合.

1.2 缺失值填充方法

目前，相關(guān)學(xué)者針對(duì)缺失值問題提出了很多解決策略，其中，填充法是一種重要的處理技術(shù).該方法是利用數(shù)據(jù)集中的完備數(shù)據(jù)對(duì)缺失值進(jìn)行填充，達(dá)到不完備數(shù)據(jù)完備化的效果.其中均值填充法[10]、隨機(jī)熱卡填充法[10]和近鄰填充法[8]由于簡(jiǎn)單有效而得到廣泛應(yīng)用.

1.2.1 均值填充法

均值填充法是通過UC中所有非缺失對(duì)象相應(yīng)屬性值的平均值對(duì)UM中的缺失屬性值進(jìn)行填充.該填充法利用數(shù)據(jù)集中非缺失數(shù)據(jù)的平均信息對(duì)缺失值進(jìn)行估計(jì)，通過最可能的屬性值進(jìn)行填充，具有簡(jiǎn)單易行的優(yōu)點(diǎn).

1.2.2 隨機(jī)抽樣熱卡填充法

隨機(jī)抽樣熱卡填充法是在UC中隨機(jī)抽取一個(gè)對(duì)象利用其相應(yīng)的屬性值對(duì)UM中的缺失屬性值進(jìn)行填充.該填充法通過隨機(jī)抽樣的方式，避免了均值填充法所導(dǎo)致的方差低估問題.但是該方法中的填充值為數(shù)據(jù)集中的隨機(jī)值，準(zhǔn)確性較低.

1.2.3K近鄰填充法

K近鄰填充法是將UM中的缺失屬性值通過UC中最相似的K個(gè)非缺失對(duì)象平均值的相應(yīng)屬性值進(jìn)行填充.對(duì)象間的距離通過局部歐式距離公式[4]計(jì)算，該公式只使用缺失對(duì)象中沒有缺失的屬性來計(jì)算它們之間的距離，具體公式如下：

(1)

2 基于動(dòng)態(tài)填充的不完備數(shù)據(jù)聚類算法

目前，不完備數(shù)據(jù)聚類算法主要是利用填充法對(duì)不完備數(shù)據(jù)進(jìn)行填充，進(jìn)而對(duì)其聚類.因此，填充方法的優(yōu)劣直接影響聚類結(jié)果的好壞.而傳統(tǒng)填充方法通常先對(duì)數(shù)據(jù)集進(jìn)行某種假設(shè)，然后基于該假設(shè)填充缺失值.如均值填充法將數(shù)據(jù)集視為基于高斯分布，利用最可能的均值對(duì)缺失值進(jìn)行填充.這些填充方法具有一定的主觀性，且沒有對(duì)已知數(shù)據(jù)充分利用，往往填充效果較差，進(jìn)而對(duì)聚類結(jié)果造成影響.基于此，本文提出一種基于動(dòng)態(tài)填充的不完備數(shù)據(jù)聚類算法.在該方法中，首先利用均值填充法進(jìn)行初始化填充，然后通過基于類中心的算法進(jìn)行動(dòng)態(tài)填充，直到聚類相似度達(dá)到閾值為止.

2.1 初始化填充方法

在不完備數(shù)據(jù)進(jìn)行聚類時(shí)，需要利用全體數(shù)據(jù)集的分布信息對(duì)缺失值進(jìn)行動(dòng)態(tài)填充.因此，在聚類之前，需要對(duì)缺失數(shù)據(jù)進(jìn)行初始化填充.由于均值填充法簡(jiǎn)單高效，同時(shí)可以反映數(shù)據(jù)的分布情況，所以采用其對(duì)不完備數(shù)據(jù)進(jìn)行初始化填充.將缺失值利用非缺失數(shù)據(jù)集UC中所有對(duì)象均值的相應(yīng)屬性值進(jìn)行填充.

令?xj∈UM,xj=(xj1，xj2，…，xjm)T,其中，xjp=″*″.缺失值xjp的填充公式為

(2)

其中，|UC·表示非缺失數(shù)據(jù)集UC中對(duì)象的個(gè)數(shù).通過公式(2)，將缺失數(shù)據(jù)集UM進(jìn)行填充，令填充后的數(shù)據(jù)集為U′.

2.2 動(dòng)態(tài)填充方法

通過以上分析，為消除均值填充法因主觀假設(shè)所帶來的不良影響，本文采用基于聚類中心的填充法對(duì)缺失值進(jìn)行填補(bǔ).首先利用K-means算法[11]對(duì)填充后的數(shù)據(jù)集U′進(jìn)行聚類，得到聚類中心c={c1，c2，…，cK}(其中，cs∈c,cs=(cs1，cs2，…，csm)T)和聚類結(jié)果C={C1，C2，…，CK}.對(duì)缺失數(shù)據(jù)集UM中缺失值通過其所在類中心的相應(yīng)屬性值再次填充.

令?xj∈UM且xj∈Cr,xj=(xj1，xj2，…，xjm)T,xjp=″*″.缺失值xjp的再次填充公式為

xjp=crp.

(3)

通過公式(3)，將缺失數(shù)據(jù)集UM進(jìn)行再次填充，令填充后的數(shù)據(jù)集為U1.

該方法有效地利用聚類算法自動(dòng)尋找近鄰的功能，對(duì)缺失值用最可能的值進(jìn)行填充，進(jìn)而降低初始填充法對(duì)填充效果的誤差.具體算法如表1所示.

表1 基于類中心的填充算法(算法1)

算法1的時(shí)間復(fù)雜度分為O(Knmt+Km),其中，O(Knmt)為K-means算法的時(shí)間復(fù)雜度(即第2步的時(shí)間復(fù)雜度)，O(Km)為缺失值填充的時(shí)間復(fù)雜度(即第3步的時(shí)間復(fù)雜度)，K是聚類個(gè)數(shù)，n是不完備數(shù)據(jù)集U的對(duì)象總數(shù)，m是屬性個(gè)數(shù)，t是K-means最大迭代次數(shù).

通過以上分析，盡管填充效果有較大的提高，但是填充后數(shù)據(jù)集的改變及K-means算法對(duì)初始點(diǎn)敏感不可避免地帶來了部分填充誤差.為盡可能地降低這部分誤差，本文設(shè)計(jì)了一種動(dòng)態(tài)填充方法.該方法利用聚類中心對(duì)缺失值進(jìn)行填充，然后在填充后的數(shù)據(jù)集上聚類得到聚類中心，并將缺失值通過其所在的類中心進(jìn)行動(dòng)態(tài)填充.此方法充分利用了數(shù)據(jù)集中的已知信息，有效消除了初始填充法所帶來的主觀性問題.同時(shí)所采用的K-means算法[12]不僅簡(jiǎn)單易行，而且具有穩(wěn)定性和收斂性，有利于保證聚類結(jié)果的穩(wěn)定.

2.3 聚類終止條件

上述方法利用聚類中心對(duì)缺失值進(jìn)行填充，通過多次迭代，可以得到一個(gè)較好的聚類結(jié)果.因此，在迭代過程中需要對(duì)聚類效果進(jìn)行評(píng)價(jià)，進(jìn)而確定聚類終止條件.我們利用聚類相似度作為終止準(zhǔn)則，同時(shí)衡量動(dòng)態(tài)填充的充分程度.由于K-means算法具有穩(wěn)定性，當(dāng)相鄰聚類結(jié)果極其相似時(shí)，動(dòng)態(tài)填充后的數(shù)據(jù)集已經(jīng)趨于穩(wěn)定，不完備數(shù)據(jù)集充分填充.本文采用分類準(zhǔn)確度[13]來度量相鄰聚類結(jié)果的相似度.相似度S表示如下：

(4)

其中，K為類個(gè)數(shù)，bi表示兩個(gè)聚類結(jié)果中對(duì)應(yīng)類Ci中共有的對(duì)象個(gè)數(shù)，n表示對(duì)象總數(shù).

為了解決類標(biāo)簽對(duì)應(yīng)問題，本文采用周志華等[12]提出的最大覆蓋法進(jìn)行合并類標(biāo)簽.相似度算法具體如表2的所示.

表2 相似度算法(算法2)

算法2只需要K×K的空間來存儲(chǔ)相似度矩陣，時(shí)間復(fù)雜度為O(K2).

2.4 一種基于動(dòng)態(tài)填充的不完備數(shù)據(jù)聚類算法

基于以上分析，本文提出了一種基于動(dòng)態(tài)填充的不完備數(shù)據(jù)聚類算法(IDCA-DF算法)，具體如表3所示.

表3 IDCA-DF算法(算法3)

通過分析可知，本文提出算法的時(shí)間復(fù)雜度為O((1-r)*n+Knmtl+K(m+K)(l-1)),均值填充K-means算法的時(shí)間復(fù)雜度為O((1-r)*n+Knmt),k近鄰填充K-means的時(shí)間復(fù)雜度為O(r(1-r)n2+Knmt),其中r是缺失數(shù)據(jù)占對(duì)象總數(shù)的百分比，K是聚類個(gè)數(shù)，n是不完備數(shù)據(jù)集U的對(duì)象總數(shù)，m是屬性個(gè)數(shù)，t是K-means最大迭代次數(shù)，l是動(dòng)態(tài)填充最大次數(shù).由于現(xiàn)實(shí)數(shù)據(jù)中n?m,n?t,n?l,所以當(dāng)n足夠大時(shí)，O((1-r)*n+Knmtl)和O((1-r)*n+Knmt)相對(duì)于n來說是線性的，O(r(1-r)n2+Knmt)相對(duì)于n來說是超線性.

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

3.1 實(shí)驗(yàn)數(shù)據(jù)與實(shí)驗(yàn)環(huán)境

從UCI真實(shí)數(shù)據(jù)集中選取了數(shù)據(jù)規(guī)模不同的7個(gè)完備數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，數(shù)據(jù)集信息如表4所示.

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

實(shí)驗(yàn)的計(jì)算機(jī)環(huán)境為：處理器Inter i7-4790 3.6 GHz ，內(nèi)存4G ，操作系統(tǒng)Windows7 ，編程環(huán)境MATLAB2013a.

3.2 聚類有效性度量指標(biāo)

為了對(duì)聚類結(jié)果的有效性進(jìn)行評(píng)價(jià)，本文采用外部評(píng)價(jià)指標(biāo)分類準(zhǔn)確率CA[13]和內(nèi)部評(píng)價(jià)準(zhǔn)則CUN[14]對(duì)聚類結(jié)果進(jìn)行評(píng)價(jià).

3.2.1 分類準(zhǔn)確率CA

(5)

其中，K為類個(gè)數(shù)，ci表示正確聚類與對(duì)應(yīng)類Ci中共有的對(duì)象個(gè)數(shù)，n表示對(duì)象總數(shù).CA在已知數(shù)據(jù)真實(shí)類劃分的情況下，用來評(píng)價(jià)聚類結(jié)果與真實(shí)類標(biāo)簽的相似度.

3.2.2 有效性函數(shù)CUN

(6)

可見，CA值越大，CUN值越大，聚類效果越好.

3.3 實(shí)驗(yàn)與結(jié)果分析

本文選取三種傳統(tǒng)的填充法將不完備數(shù)據(jù)集完備化后，通過K-means算法產(chǎn)生聚類結(jié)果.對(duì)比算法一是對(duì)不完備數(shù)據(jù)集通過均值填充法填充后再用K-means算法聚類；對(duì)比算法二是對(duì)不完備數(shù)據(jù)集通過隨機(jī)抽樣熱卡填充法填充后再用K-means算法聚類；對(duì)比算法三是對(duì)不完備數(shù)據(jù)集通過k近鄰填充法填充后再用K-means算法聚類.

在實(shí)驗(yàn)過程中，針對(duì)表4中的每個(gè)數(shù)據(jù)集分別隨機(jī)刪除10%對(duì)象的20%屬性值(不為整數(shù)時(shí)，向上取整)作為不完備數(shù)據(jù)集.分別將本文算法與三種對(duì)比算法運(yùn)行20次，計(jì)算CA和CUN的平均值與標(biāo)準(zhǔn)偏差以及聚類的平均時(shí)間.在k近鄰填充法中，k取值為5.本文提出的算法與三種對(duì)比算法在不同評(píng)價(jià)指標(biāo)下實(shí)驗(yàn)結(jié)果的平均值和標(biāo)準(zhǔn)偏差如表5和表6所示，不同算法的平均運(yùn)行時(shí)間如表7所示.

表5 不同算法CA的平均值±標(biāo)準(zhǔn)偏差比較

表6 不同算法CUN的平均值±標(biāo)準(zhǔn)偏差比較

其中，表5和表6中每個(gè)數(shù)據(jù)集上不同算法的最優(yōu)實(shí)驗(yàn)結(jié)果用粗體標(biāo)識(shí).通過對(duì)表5和表6中數(shù)據(jù)分析可知，對(duì)于以上7個(gè)數(shù)據(jù)集，除了Glass數(shù)據(jù)集外，本文提出的算法在兩種指標(biāo)下均優(yōu)于三種對(duì)比算法；在Glass數(shù)據(jù)集上，本文算法的CA值最優(yōu)而CUN值次優(yōu).

表7 不同算法每次運(yùn)行的時(shí)間/s

由于本文算法利用每次聚類的類中心對(duì)缺失值動(dòng)態(tài)地進(jìn)行填充，多次有效地利用了含缺失值數(shù)據(jù)的已知信息，使得填充效果更好，從而聚類結(jié)果更優(yōu).相較于三種對(duì)比算法，本文算法在填充缺失值的同時(shí)，不斷地尋找更接近于真實(shí)數(shù)據(jù)的聚類中心，從而得到更優(yōu)的聚類結(jié)果.對(duì)于以上的7個(gè)數(shù)據(jù)集，除了ImageSeg數(shù)據(jù)集，本文算法在CA指標(biāo)下的標(biāo)準(zhǔn)偏差都最小；除了Wine數(shù)據(jù)集，本文算法在CUN指標(biāo)下的標(biāo)準(zhǔn)偏差都最小.由于使用的K-means算法是收斂算法，將所得到的聚類中心對(duì)缺失屬性值填充，不僅合理地將聚類結(jié)果融入缺失值填充過程中，而且利用了K-means算法的收斂性，使得聚類效果相對(duì)穩(wěn)定.從Iris，optdigis和pendigits三個(gè)數(shù)據(jù)集的CA和CUN值可知，K-means算法在數(shù)據(jù)集上效果越好，本文算法聚類準(zhǔn)確率提高幅度越大.

表7中最長(zhǎng)運(yùn)行時(shí)間用粗體標(biāo)識(shí).通過表7中數(shù)據(jù)分析可知，當(dāng)數(shù)據(jù)規(guī)模較小時(shí)，本文提出的算法耗時(shí)較多；當(dāng)數(shù)據(jù)量較大時(shí)，本文算法的運(yùn)行時(shí)間要低于對(duì)比算法三，而高于對(duì)比算法一和對(duì)比算法二.從mGamma數(shù)據(jù)集的運(yùn)行時(shí)間對(duì)比可知，本文算法的運(yùn)行時(shí)間取決于對(duì)缺失屬性值進(jìn)行填充的次數(shù)，對(duì)缺失屬性值進(jìn)行填充的次數(shù)越少，運(yùn)行時(shí)間越短.從ImageSeg,optdigits和pendigits數(shù)據(jù)集的運(yùn)行時(shí)間對(duì)比可知，本文運(yùn)行時(shí)間相對(duì)于對(duì)比算法一的運(yùn)行時(shí)間越長(zhǎng)，聚類效果較好.

4 結(jié)論

針對(duì)不完備數(shù)據(jù)聚類問題，本文提出了一種動(dòng)態(tài)填充的聚類算法，在UCI數(shù)據(jù)集上，通過與傳統(tǒng)填充聚類算法進(jìn)行實(shí)驗(yàn)對(duì)比分析，結(jié)果表明提出的算法可以得到較好的聚類效果.