樊 路, 錢雪忠, 姚琳燕

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

0 引 言

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

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

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

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

1 增量式聚類算法

1.1 增量聚類

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

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

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

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

圖1 增量處理過程

1.2 相似度度量

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

(1)

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

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

(2)

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

1.3 增量過程

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

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

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

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

對于增量的處理方法：

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

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

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

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

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

圖2 關(guān)鍵點

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

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

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

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

2)實施分裂：確定需要分裂后，使用K-means算法分裂子簇[9]，在實施分裂中K-means算法的初始點設(shè)為該子簇中距離相對較遠的兩個點，聚類數(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全部屬于同一個簇)

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全部屬于多個簇))

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 實驗分析

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

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

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

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

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

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

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

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

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

3 結(jié)束語

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