基于簇特征的增量聚類算法*

姚琳燕， 錢雪忠， 樊 路

(江南大學(xué) 物聯(lián)網(wǎng)技術(shù)應(yīng)用教育部工程研究中心，江蘇 無(wú)錫 214122)

0 引 言

隨著大數(shù)據(jù)時(shí)代的來(lái)臨，海量的數(shù)據(jù)存儲(chǔ)使得傳統(tǒng)聚類方式效率低下。Fisher D[1]在1987年提出了COBWEB算法，該算法除了增加對(duì)象之外，還涉及到集群重組。文獻(xiàn)[2,3]中討論了與數(shù)據(jù)庫(kù)動(dòng)態(tài)方面有關(guān)的增量聚類，且廣泛應(yīng)用于許多領(lǐng)域[4,5]。增量聚類不需要在主存內(nèi)保留對(duì)象之間的相互距離，且算法相對(duì)于對(duì)象集合的大小和屬性數(shù)量可擴(kuò)展[6]。

文獻(xiàn)[7]中的層次聚類算法——BIRCH首次提出了聚類特征(cluster feature,CF)的概念，在層次增量聚類算法中取得了較好的聚類效果。受此啟發(fā)，以提高準(zhǔn)確率和時(shí)間復(fù)雜度為目標(biāo)，分析K-means算法[8]和K最近鄰[9](K-nearest neighbour,KNN)的優(yōu)缺點(diǎn)，本文提出了一種基于簇特征的增量聚類算法，并在此基礎(chǔ)上提出簇特征概念輔以KNN思想添加增量處理部分，提出一種基于簇特征的增量算法。

1 距離測(cè)量(定義一)

采用歐氏距離計(jì)算質(zhì)心到數(shù)據(jù)點(diǎn)的距離，從點(diǎn)y到點(diǎn)m的距離為

(1)

2 基于簇特征的增量算法

為了減少迭代時(shí)間，避免算法陷入局部最優(yōu)，本文提出最大距離法選取k個(gè)中心點(diǎn)，簇中心為c={c1,c2,…,ck}，1≤i≤k。

2.1 最大距離法選擇初始中心

1)將所有的數(shù)據(jù)放入data中，中心點(diǎn)集合c置空。隨機(jī)在Data中選取1個(gè)點(diǎn)作為第1個(gè)中心點(diǎn)，將該點(diǎn)放入c中，并將該點(diǎn)從Data中移除。

2)計(jì)算數(shù)據(jù)集Data中的所有點(diǎn)與隨機(jī)選取的中心點(diǎn)的距離，選擇距離最遠(yuǎn)的點(diǎn)作為下一個(gè)中心點(diǎn)并放入c中,相應(yīng)的從Data中移除該點(diǎn)。

3)若集合c的數(shù)量等于k，結(jié)束；否則，跳入步驟(2)。

2.2 簇特征

2.2.1 CF(定義二)

本文使用mi和Fi(q)作為簇特征，CF={mi，F(xiàn)i(q)，Q}。其中，mi是簇ci的中心點(diǎn)，F(xiàn)i(q)是簇ci中距離中心點(diǎn)最遠(yuǎn)的q個(gè)最遠(yuǎn)點(diǎn)，Q是距離中心點(diǎn)最遠(yuǎn)的q個(gè)最遠(yuǎn)點(diǎn)中距離新增數(shù)據(jù)最近的點(diǎn)。

增量數(shù)據(jù)會(huì)對(duì)聚類結(jié)果產(chǎn)生影響而不會(huì)對(duì)當(dāng)前的集群產(chǎn)生廣泛的影響。數(shù)據(jù)更新之后，有3種可能性，加入已有簇，生成一個(gè)新簇或合并兩個(gè)已有簇，如圖1所示。

2.2.2 距離策略(定義三)

距離策略對(duì)于有效識(shí)別輸入數(shù)據(jù)點(diǎn)Δy的正確聚類是很重要的。 在本文提出的方法中，使用了不同的距離策略，利用平均值mi，最近鄰點(diǎn)Q和輸入數(shù)據(jù)點(diǎn)Δy3個(gè)點(diǎn)。在對(duì)數(shù)據(jù)集使用改進(jìn)的K-means算法聚類之后，對(duì)于即將到來(lái)的點(diǎn)，根據(jù)簇特征，計(jì)算新增數(shù)據(jù)點(diǎn)與mi之間的歐氏距離Dim(Δy，mi)，q個(gè)最遠(yuǎn)點(diǎn)中距離新增數(shù)據(jù)點(diǎn)最近的點(diǎn)Q和中心點(diǎn)mi之間的歐氏距離DQm(Q,mi)以及新增數(shù)據(jù)點(diǎn)與q個(gè)最遠(yuǎn)點(diǎn)中距離新增數(shù)據(jù)點(diǎn)最近的點(diǎn)Q之間的歐氏距離DQi(Q，Δy)，計(jì)算D=Dim+DQm×DQi的值。

2.3 更新簇特征

將某個(gè)新增數(shù)據(jù)點(diǎn)添加到簇后，CF的更新對(duì)數(shù)據(jù)進(jìn)一步的處理至為重要。為了更新CF，首先計(jì)算發(fā)生增量簇的平均值，并更新簇特征CF的第一個(gè)分量mi。然后，利用更新的平均值mi，對(duì)增量簇中的每個(gè)數(shù)據(jù)點(diǎn)計(jì)算歐氏距離ED。根據(jù)計(jì)算的距離測(cè)量對(duì)數(shù)據(jù)點(diǎn)進(jìn)行排序，并從排序列表中選擇最新的q個(gè)最遠(yuǎn)鄰居點(diǎn)，更新CF的第二個(gè)分量Fi，在下一個(gè)新增數(shù)據(jù)點(diǎn)進(jìn)入時(shí)重新計(jì)算q個(gè)最遠(yuǎn)鄰居點(diǎn)中距離新增數(shù)據(jù)點(diǎn)最近的點(diǎn)Q。

2.4 最近簇的合并

由于處理增量過(guò)程是每次處理一條增量數(shù)據(jù)，為了避免在增量過(guò)程中簇的數(shù)量過(guò)多形成非最優(yōu)聚類結(jié)構(gòu)，本文提出的方法在處理t個(gè)增量數(shù)據(jù)之后使用合并策略，使本文方法產(chǎn)生合理數(shù)量的簇。用于合并的過(guò)程描述為：

1)計(jì)算每個(gè)簇的平均值及和其他簇之間的歐氏距離；

2)選擇歐氏距離最小的兩個(gè)簇；

3)如果距離最小的兩個(gè)簇之間的距離小于某個(gè)閾值MT，則合并這兩個(gè)簇；

4)重新計(jì)算合并的新簇的平均值；

5)重復(fù)步驟(1)～步驟(3)，直到?jīng)]有簇可合并為止。

2.5 算法具體描述

輸入：靜態(tài)數(shù)據(jù)集data1，動(dòng)態(tài)數(shù)據(jù)集data2，合并閾值MT，閾值NT，k，t，q

輸出：聚類結(jié)果re

參數(shù)：Δy為到來(lái)的新增數(shù)據(jù)點(diǎn);CF為簇特征;D為歐氏距離;Fi(q)為q為最遠(yuǎn)鄰居點(diǎn);Q為距離新增數(shù)據(jù)最近的最遠(yuǎn)鄰居點(diǎn)。

1)使用最大距離法選擇初始中心點(diǎn)

2)運(yùn)行K-means(data1，K)算法

3)fori=1︰k

a.計(jì)算CF={mi，F(xiàn)i(q)，Q}

4)for增量數(shù)據(jù)中的每個(gè)點(diǎn)Δy

b.fori=1︰k

計(jì)算距離Dim和DQm和DQi

c.如果D=Dim+DQm×DQi

c1.若k個(gè)點(diǎn)所屬簇所占比例最大的簇和i簇一致，則加入i簇

c2.若所占比例最大的簇與i簇不一致，計(jì)算所占比例最大的簇的D=Dim+DQm×DQi

若D

若大于等于NT，則加入i簇

d.如果不滿足步驟(c)則生成一個(gè)新簇

e.更新簇特征CF

f.在處理完t個(gè)增量數(shù)據(jù)后

f1.計(jì)算各個(gè)簇中心點(diǎn)之間的歐氏距離

f2.若簇中心點(diǎn)之間的距離小于閾值MT則將這兩個(gè)簇合并更新合并新簇的中心點(diǎn)，只有一個(gè)數(shù)據(jù)的簇作為噪聲點(diǎn)返回步驟(f1)

5)得到聚類結(jié)果re

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

本文中所有的算法通過(guò)MATLAB工具實(shí)現(xiàn)并處理實(shí)驗(yàn)結(jié)果，試驗(yàn)環(huán)境為：CPU為Intel i3 3.7 GHz，內(nèi)存為4 GB，Windows7系統(tǒng)。數(shù)據(jù)集：采用UCI真實(shí)數(shù)據(jù)集中的Iris數(shù)據(jù)集和Wine數(shù)據(jù)集。

實(shí)驗(yàn)一為了將靜態(tài)數(shù)據(jù)集轉(zhuǎn)化成動(dòng)態(tài)問(wèn)題處理，本文將數(shù)據(jù)集分為2組。鳶尾花數(shù)據(jù)集——Iris，第一組的組成為35個(gè)第一類數(shù)據(jù)，35個(gè)第二類數(shù)據(jù)，30個(gè)第三類數(shù)據(jù)。剩余數(shù)據(jù)作為增量數(shù)據(jù)作為第二組。閾值NT=10，MT=4,k=3，q=5。Wine數(shù)據(jù)第一組選取第一類簇的38個(gè)數(shù)據(jù)，第二類簇的32個(gè)數(shù)據(jù)，第三類簇的24個(gè)數(shù)據(jù)，剩下的數(shù)據(jù)作為第二組增量數(shù)據(jù)。Iris數(shù)據(jù)集閾值NT=10，Wine數(shù)據(jù)集閾值NT=10×105，t=10。

以下表格中的數(shù)據(jù)都是通過(guò)重復(fù)運(yùn)行20次去掉一個(gè)最大值，一個(gè)最小值,取平均值。實(shí)驗(yàn)一結(jié)果如表1所示。

表1 Iris和Wine數(shù)據(jù)集實(shí)驗(yàn)一結(jié)果

實(shí)驗(yàn)結(jié)果表明，K-means算法針對(duì)Iris數(shù)據(jù)集相對(duì)DBSCAN等其他算法有比較好的聚類效果。由于IRIS數(shù)據(jù)集有兩類數(shù)據(jù)有重合，所以DBSCAN不能有效識(shí)別，準(zhǔn)確率大大低于K-means算法。由于增量數(shù)據(jù)較少，本文提出的算法較已有的增量K-means算法效率有一定的提高，但不明顯。算法準(zhǔn)確率也有較明顯的提升。而增量K-means(incremental K-means,In-K-means)雖然效率較高，但準(zhǔn)確率有所欠缺。

Wine數(shù)據(jù)中，本文所提出的算法較傳統(tǒng)K-means算法和In-K-means算法的聚類準(zhǔn)確率有所提高，但較Iris數(shù)據(jù)集的準(zhǔn)確率提高程度略有降低。由于增量數(shù)據(jù)較少，效率提升也不明顯。而In-K-means雖然效率較高，但準(zhǔn)確率有所欠缺。

實(shí)驗(yàn)二將原始數(shù)據(jù)集中的3類樣本，取其中兩類作為初始聚類數(shù)據(jù)，另一類作為增量數(shù)據(jù)。為了驗(yàn)證本文算法對(duì)噪聲點(diǎn)的識(shí)別能力，給Iris數(shù)據(jù)集添加人造數(shù)據(jù)10條。閾值NT=10，MT=4,k=3。噪聲數(shù)據(jù)參照文獻(xiàn)[8]，結(jié)果表明，本文算法能有效識(shí)別較遠(yuǎn)噪聲點(diǎn)，識(shí)別噪聲10條，準(zhǔn)確度90.67 %，且算法本身較穩(wěn)定，聚類算法精度較高。

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

由以上實(shí)驗(yàn)可以驗(yàn)證本文提出的基于簇特征的增量聚類算法，對(duì)于增量數(shù)據(jù)有較好的聚類精度；在處理增量數(shù)據(jù)時(shí)，避免遍歷所有的數(shù)據(jù)，在一定程度上提高了算法效率，且增量數(shù)據(jù)越多，效果提升越明顯。但僅能識(shí)別球形簇且時(shí)間復(fù)雜度較高，應(yīng)用于大型數(shù)據(jù)集處理較為麻煩，如何結(jié)合密度，使得算法能夠識(shí)別任意形狀的簇或者結(jié)合網(wǎng)格降低算法的時(shí)間復(fù)雜度，將是下一步將要研究的工作。