基于K近鄰的增量式聚類算法*

樊 路, 錢雪忠, 姚琳燕

(1.江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院 智能系統(tǒng)與網(wǎng)絡(luò)計(jì)算研究所,江蘇 無錫 214122;2.物聯(lián)網(wǎng)技術(shù)應(yīng)用教育部工程研究中心，江蘇 無錫 214122; 3.江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫 214122)

0 引 言

如今互聯(lián)網(wǎng)的信息迅速增長，而大多數(shù)聚類方法只能處理靜態(tài)數(shù)據(jù),這意味著在運(yùn)行聚類算法之前，輸入數(shù)據(jù)必須完整。當(dāng)聚類算法運(yùn)行時(shí)，無法向該算法添加任何新數(shù)據(jù)。然而，在大多數(shù)情況下，信息隨時(shí)都會(huì)出現(xiàn),在這種不穩(wěn)定的情況下簡(jiǎn)單的聚類數(shù)據(jù)方法是，當(dāng)新數(shù)據(jù)來臨時(shí)，將原始數(shù)據(jù)和新的數(shù)據(jù)一起使用來構(gòu)建新的聚類模型。但會(huì)浪費(fèi)很多時(shí)間，且沒有使用已經(jīng)從這些原始數(shù)據(jù)中獲得的知識(shí)。

Ester M等人[1]最早提出了基于密度的聚類算法(density-based spatial clustering of application with noise,DBSCAN)的增量聚類算法，在DBSCAN算法的基礎(chǔ)上，針對(duì)數(shù)據(jù)倉庫環(huán)境中增量式數(shù)據(jù)加載要求而改造的。該算法依次將更新表的一條當(dāng)前記錄與數(shù)據(jù)倉庫中的記錄比較，更新聚類結(jié)果，但算法在增量聚類過程中，更新對(duì)象依次單獨(dú)處理，而沒有考慮更新對(duì)象之間的關(guān)系，效率較低。

傳統(tǒng)增量聚類算法往往是通過增量與質(zhì)心的距離來判斷增量的歸屬性，該單一條件并無法較好地判定增量數(shù)據(jù)與已有類的相似性，而且無法聚類出噪聲點(diǎn)或者新的簇。而在現(xiàn)有的關(guān)于增量聚類的文獻(xiàn)中[3,4]，大部分依然注重的是對(duì)初始聚類算法的改進(jìn)，而針對(duì)增量部分?jǐn)?shù)據(jù)的處理往往是根據(jù)傳統(tǒng)的距離判別方法將其劃分到已有的簇中，鮮有針對(duì)增量聚類的創(chuàng)新。因此,本文考慮使用新的數(shù)據(jù)和原始數(shù)據(jù)中的幾個(gè)樣本來改變從原始數(shù)據(jù)獲得的聚類模型，使得該模型適合原始數(shù)據(jù)和新的數(shù)據(jù)。

本文在K近鄰(K-nearest neighbor,KNN)算法的基礎(chǔ)上結(jié)合簇特征概念提出了一種新的動(dòng)態(tài)增量聚類算法，即基于K近鄰的增量聚類算法，改進(jìn)增量聚類算法的有效性和可擴(kuò)展性，實(shí)驗(yàn)證明該算法能夠較為準(zhǔn)確地處理增量數(shù)據(jù)點(diǎn)，包括劃分為已有的簇、生成新簇、合并分裂部分簇、識(shí)別噪聲點(diǎn)。

1 增量式聚類算法

1.1 增量聚類

增量聚類算法首先使用原始數(shù)據(jù)構(gòu)建初始聚類模型，當(dāng)新數(shù)據(jù)來臨時(shí)，使用新的數(shù)據(jù)來改變這個(gè)聚類模型，使其適合新的數(shù)據(jù)。本文提出的增量聚類算法是在K近鄰的思想上，融合了劃分與層次的聚類方法中優(yōu)點(diǎn)[2,6]。首先計(jì)算增量數(shù)據(jù)最近k個(gè)近鄰樣本，判斷這k個(gè)近鄰樣本所屬的簇，計(jì)算k個(gè)近鄰中樣本點(diǎn)所屬各個(gè)簇的比重，這是進(jìn)行增量數(shù)據(jù)劃分的首要依據(jù)，比重最大的優(yōu)先考慮將增量數(shù)據(jù)劃為該簇。然后結(jié)合增量與K近鄰中的樣本數(shù)據(jù)的相似性比較和各自對(duì)應(yīng)的簇特征的變化情況，對(duì)增量數(shù)據(jù)進(jìn)行進(jìn)一步的處理。因?yàn)樵肼朁c(diǎn)相對(duì)其他樣本的距離都較遠(yuǎn)，在增量過程中，其所在簇中樣本數(shù)目的增長就會(huì)非常緩慢，甚至不增長。第一階段的工作中，是將聚類過程中增長非常緩慢的簇作為噪聲點(diǎn)除去。第二個(gè)階段的工作(聚類基本結(jié)束的時(shí)候)是將數(shù)目明顯少的簇作為噪聲點(diǎn)除去。一般增量處理過程包含以下三種情況：

1)增量按K近鄰原則插入到與之最近的簇中，(圖1(a))。

2)增量與現(xiàn)有簇相似性較低，獨(dú)自形成新簇，(圖1(b))。

3)增量在逐步增加的過程中改變了原有簇的相似性，使之合并成一個(gè)簇。如圖1(c)所示或者分裂成兩個(gè)簇，如圖1(d)所示。其中A,B為原始簇，A',B'是增量后的簇，C是新形成的簇。

圖1 增量處理過程

1.2 相似度度量

相似度度量主要依據(jù)數(shù)據(jù)間的距離關(guān)系，本文統(tǒng)一采用歐氏距離來表示樣本與聚類中心之間的距離d12，即

(1)

式中x1和x2為樣本，n為兩個(gè)數(shù)據(jù)樣本的維度數(shù)。對(duì)于任意兩個(gè)數(shù)據(jù)樣本p和q，dist(p,q)為p和q間的相似度。

在處理增量的過程中，每個(gè)簇的質(zhì)心都會(huì)隨之變化，更新每個(gè)簇的質(zhì)心為

(2)

式中u為某一簇，m.meannew為增量后的質(zhì)心，u.meanold為增量前的質(zhì)心，u.num為簇u中樣本個(gè)數(shù)，u.xnew為屬于簇u的增量數(shù)據(jù)。

1.3 增量過程

本文提出的算法步驟詳細(xì)介紹如下：

步驟1 采用K-means算法對(duì)原始數(shù)據(jù)集聚類[7,8]，得到原始聚類結(jié)果并對(duì)結(jié)果進(jìn)行統(tǒng)計(jì)。包括聚類數(shù)，各個(gè)簇的樣本數(shù)、質(zhì)心和凝聚度。

步驟2 利用K近鄰算法的思想，利用步驟(1)的結(jié)果計(jì)算尋找增量數(shù)據(jù)的k個(gè)近鄰樣本，單獨(dú)存儲(chǔ)為一個(gè)K近鄰矩陣，并統(tǒng)計(jì)K近鄰矩陣中簇的分布情況以及各個(gè)簇所占比重。

步驟3 根據(jù)步驟(2)中得到K近鄰矩陣的統(tǒng)計(jì)信息。

對(duì)于增量的處理方法：

1)如果增量的k個(gè)近鄰全部屬于同一簇時(shí)，這時(shí)候可能會(huì)出現(xiàn)兩種情況，一是增量數(shù)據(jù)屬于該簇，二是增量數(shù)據(jù)可能產(chǎn)生一個(gè)新簇。此時(shí)計(jì)算k個(gè)近鄰之間的相互距離的均值k.mean和增量與個(gè)近鄰之間距離的均值in.mean，用兩者的差值來衡量增量和k個(gè)近鄰的緊密度關(guān)系。

a.若k.mean-in.mean>=τ(τ為緊密度系數(shù)，針對(duì)不同數(shù)據(jù)集取值不同)，則增量數(shù)據(jù)屬于該簇。為增量數(shù)據(jù)添加該簇的簇標(biāo)簽，并更新簇的特征CF。

b.若k.mean-in.mean<τ，則增量數(shù)據(jù)產(chǎn)生新的簇，簇標(biāo)簽為maxLab+1(maxLab為目前已有的最大類標(biāo)簽),并計(jì)算新簇的簇特征CF。如果最終新形成的簇的樣本數(shù)量過小，則認(rèn)為是噪聲點(diǎn)。

2)如果增量數(shù)據(jù)的k個(gè)近鄰屬于n(n≤k)個(gè)簇，這時(shí)可能會(huì)出現(xiàn)3種情況，屬于近鄰中某個(gè)的簇;形成一個(gè)新簇;可能需要合并一些原始聚類數(shù)據(jù)中的樣本。接下來需要判斷該增量數(shù)據(jù)是否為關(guān)鍵增量點(diǎn)(key of incremental data,KID)，如果是則合并K近鄰，否則,繼續(xù)計(jì)算增量數(shù)據(jù)與近鄰中各個(gè)簇間的平均距離in1，in2,…,inn和所有近鄰之間的平均距離k.mean，若min{in1，in2,…,inn}>k.mean則生成新簇，否則,增量屬于min{in1，in2,…,inn}簇。

判定KID：首先增量數(shù)據(jù)的k個(gè)近鄰中出現(xiàn)屬于這樣兩個(gè)簇，第一這兩個(gè)簇所占比重相當(dāng)(|A%-B%|

圖2 關(guān)鍵點(diǎn)

判定為關(guān)鍵增量點(diǎn)后，合并增量數(shù)據(jù)和K近鄰中比重次高樣本點(diǎn)的到比重最高的簇中去。最后每條增量數(shù)據(jù)處理完后即成為原始數(shù)據(jù)。

步驟4 適時(shí)判斷是否需要執(zhí)行簇分裂操作。

為了進(jìn)一步準(zhǔn)確地處理增量聚類，在增量的數(shù)量增加到一定的情況下，簇分裂的可能性逐步增大，因此在增量的過程中適時(shí)需要執(zhí)行簇分裂操作。

1)判斷類分裂條件：根據(jù)子簇的簇特征檢查各個(gè)子簇是否滿足需求，主要從子簇的質(zhì)心和子簇的凝聚性兩方面來判斷是否需要分裂某子簇。首先判斷子簇的樣本數(shù)N是否達(dá)到可以進(jìn)行分裂的數(shù)目，達(dá)到,則計(jì)算該簇中所有點(diǎn)均值與簇凝聚度差，大于閾值t，即dist(u.mean,u.R)>t，則說明增量破壞了該簇的簇特征，需要對(duì)該簇分裂。

2)實(shí)施分裂：確定需要分裂后，使用K-means算法分裂子簇[9]，在實(shí)施分裂中K-means算法的初始點(diǎn)設(shè)為該子簇中距離相對(duì)較遠(yuǎn)的兩個(gè)點(diǎn)，聚類數(shù)k=2。

綜上所述，該算法偽代碼如下：

input：Original data setX；

Incremental data InX;

output：Clustering resultidx;

1)(idxold,C,CF)=kmeans(X);

2)for each InXdo

3)knn[k]=Findknn(OriginalResult,InX);

4) if(knn全部屬于同一個(gè)簇)

5)k.mean= AverageDist(knn[1],knn[2]…knn[k]);

6)in.mean=AverageDist(InX,knn[1],knn[2]…knn[k]);

7) if(k.mean-in.mean>=τ)

8)knn[k].cluster←InX;

9) Update(cluster.CF);

10) end if

11) if(k.mean-in.mean<τ)

12)New.cluster←InX;

13) Update(cluster.CF);

14) end if

15) if((knn全部屬于多個(gè)簇))

16) if(InXis KID)

17) merge(knn[i],knn[j]);

18)knn[k].max.cluster←InX;

19) Update(cluster.CF);

20) end if

21) if(InXisn’t KID)

22) in[n]=dist(InX,knn.cluster[1],

knn.cluster[2]…knn.cluster[n])

23) if(min{in}>k.mean)

24)New.cluster←InX;

25) Update(cluster.CF);

26) end if

27) end if

28)end for

30) split(cluster);

31)end if

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

實(shí)驗(yàn)中采用加州大學(xué)爾灣分校(UCI)中提供的Iris數(shù)據(jù)集和Wine數(shù)據(jù)集，兩種數(shù)據(jù)集常常被用來檢測(cè)分類聚類算法的有效性，分別擁有150個(gè)數(shù)據(jù)樣本和178個(gè)數(shù)據(jù)樣本，描述屬性分別是4個(gè)和13個(gè)，類別數(shù)都是3類。為了實(shí)現(xiàn)增量聚類過程，需要人工篩選出初始聚類數(shù)據(jù)集和增量聚類數(shù)據(jù)集，為了全面檢測(cè)本文中增量聚類算法的實(shí)效性，對(duì)增量數(shù)據(jù)聚類設(shè)計(jì)了三種實(shí)驗(yàn)。

為了驗(yàn)證算法對(duì)噪聲點(diǎn)的識(shí)別，分別模擬了Iris數(shù)據(jù)集和Wine數(shù)據(jù)集的噪聲點(diǎn)數(shù)據(jù)，并進(jìn)行如下實(shí)驗(yàn)。

實(shí)驗(yàn)1分別從各個(gè)類中各選出部分樣本數(shù)據(jù)，組成一個(gè)增量數(shù)據(jù)集，以此來檢測(cè)該增量聚類算法整體有效性[11]。實(shí)驗(yàn)數(shù)據(jù)和結(jié)果如表1所示。

表1 實(shí)驗(yàn)1數(shù)據(jù)與結(jié)果

實(shí)驗(yàn)2將原始數(shù)據(jù)集中的3類樣本，取其中兩類作為初始聚類數(shù)據(jù)，另外一類作為增量數(shù)據(jù)，并加入模擬的噪聲點(diǎn)，檢測(cè)該增量聚類算法是否能有效聚類出新增的簇和識(shí)別出噪聲點(diǎn)[12]。實(shí)驗(yàn)數(shù)據(jù)和結(jié)果如表2所示。

表2 實(shí)驗(yàn)2數(shù)據(jù)與結(jié)果

實(shí)驗(yàn)3將初始數(shù)據(jù)集的三類聚成兩類，然后再聚類增量，檢測(cè)算法是否能有效分裂聚類結(jié)果[13]。實(shí)驗(yàn)數(shù)據(jù)和結(jié)果如表3所示。

表3 實(shí)驗(yàn)3數(shù)據(jù)與結(jié)果

通過以上實(shí)驗(yàn)可以看出，在實(shí)驗(yàn)1中本文算法的聚類純度分別是0.891 1和0.692 5,都高于傳統(tǒng)增量K-means。在實(shí)驗(yàn)2中本文算法的聚類純度分別為0.907 2和0.891 2，不僅聚類出了新的簇而且較好地識(shí)別出噪聲。在實(shí)驗(yàn)3中本文算法的聚類純度分別為0.918 3和0.895 2，并且準(zhǔn)確地實(shí)現(xiàn)類分裂操作。實(shí)驗(yàn)證明該算法可以有效處理增量數(shù)據(jù)，不論是插入現(xiàn)有的簇中還是產(chǎn)生新的簇還是分裂某些簇，都擁有較高的準(zhǔn)確率。

3 結(jié)束語

本文利用K近鄰的細(xì)想結(jié)合簇特征這一概念設(shè)計(jì)并實(shí)現(xiàn)了一種全新的增量式聚類算法，在處理增量過程中，不僅能準(zhǔn)確劃分為現(xiàn)有簇，而且也能正確合并或分裂某些簇和識(shí)別出噪聲點(diǎn)。并通過實(shí)驗(yàn)證明該算法的有效性和可行性。但該算法不足之處在于執(zhí)行增量過程中依賴初始數(shù)據(jù)集的聚類結(jié)果，初始聚類結(jié)果的準(zhǔn)確性對(duì)增量聚類的準(zhǔn)確性影響較大。而且該算法中對(duì)增量的處理是逐一進(jìn)行，沒有采用批處理方式，在面對(duì)增量數(shù)據(jù)過大時(shí)可能會(huì)導(dǎo)致算法效率大大降低，這也是接下來需要進(jìn)一步研究的內(nèi)容。