基于動(dòng)態(tài)網(wǎng)格的數(shù)據(jù)流聚類分析
2008-12-31 00:00:00何勇劉青寶
計(jì)算機(jī)應(yīng)用研究 2008年11期
(國(guó)防科學(xué)技術(shù)大學(xué) 信息系統(tǒng)與管理學(xué)院， 長(zhǎng)沙 410073)
摘要：提出的增量式數(shù)據(jù)流聚類算法DGCDS結(jié)合網(wǎng)格和密度技術(shù)，能夠得到任意形狀的聚類，通過(guò)改進(jìn)網(wǎng)格密度的計(jì)算方式，解決了現(xiàn)有網(wǎng)格算法中丟失數(shù)據(jù)空間影響信息的問(wèn)題，并且實(shí)現(xiàn)了關(guān)鍵參數(shù)的自適應(yīng)設(shè)置，減小了人工參數(shù)對(duì)聚類結(jié)果的影響。
關(guān)鍵詞：動(dòng)態(tài)網(wǎng)格； 網(wǎng)格密度； 數(shù)據(jù)流聚類； 聚類參數(shù)
中圖分類號(hào)：TP391文獻(xiàn)標(biāo)志碼：A
文章編號(hào)：1001-3695(2008)11-3281-04
Dynamic grid-based clustering over data stream
HE Yong， LIU Qing-bao
(College of Information System Management， National University of Defense Technology， Changsha 410073， China)
Abstract:This paper presented an incremental data stream clustering algorithm(DGCDS) based on grid and density，which discovered clusters with arbitrary shape. It solved a problem that losing space influence of data in some of grid-based algorithms with improving the method of density calculation， and this algorithm also set key parameter automatically to reduce the influence of factitious parameter.
Key words：dynamic grid; grid density; datastream clustering; clustering parameter
0引言
隨著硬件技術(shù)的飛速發(fā)展，人們獲取數(shù)據(jù)的能力越來(lái)越高，獲取數(shù)據(jù)的領(lǐng)域越來(lái)越廣，數(shù)據(jù)形態(tài)也從靜止的數(shù)據(jù)轉(zhuǎn)為海量、源源不斷的數(shù)據(jù)流數(shù)據(jù)。比如通信領(lǐng)域的通話記錄數(shù)據(jù)流、網(wǎng)絡(luò)監(jiān)控中的數(shù)據(jù)包流，金融領(lǐng)域和零售企業(yè)的交易數(shù)據(jù)流，以及近幾年發(fā)展起來(lái)的傳感器網(wǎng)絡(luò)等產(chǎn)生的大量數(shù)據(jù)流。
數(shù)據(jù)流一經(jīng)提出就引起了研究者的廣泛關(guān)注。目前，數(shù)據(jù)流研究大致可分為兩個(gè)方面：數(shù)據(jù)流管理系統(tǒng)(data stream management system，DSMS)和數(shù)據(jù)流挖掘[1]。數(shù)據(jù)流聚類由于在網(wǎng)絡(luò)監(jiān)控、銀行交易數(shù)據(jù)分析等方面的重要應(yīng)用價(jià)值而成為數(shù)據(jù)流挖掘的一個(gè)重要研究方向，已提出多種一次性掃描聚類算法，如STREAM算法[2]、CluStream算法[3]和HPStream算法[4]，以及基于它們的一些衍生算法。但總的來(lái)說(shuō)，現(xiàn)有數(shù)據(jù)流算法基本上都是對(duì)靜態(tài)數(shù)據(jù)集算法的改進(jìn)。
1相關(guān)研究
數(shù)據(jù)流的特性要求算法必須是內(nèi)存限制下的實(shí)時(shí)增量更新算法。第一個(gè)增量更新聚類算法是用于數(shù)據(jù)倉(cāng)庫(kù)的IncrementalDBSCAN算法[5]，然而該算法僅適用于處理數(shù)據(jù)倉(cāng)庫(kù)這種相對(duì)穩(wěn)定的數(shù)據(jù)流，不能處理變化很快的數(shù)據(jù)流。同時(shí)為了得到任意形狀的聚類，要求獲得整個(gè)數(shù)據(jù)流的信息，這在內(nèi)存有限的情況下是無(wú)法做到的。L.O'Callaghan等人[2]提出的STREAM算法采取分而治之(divide and conquer)的思想，將數(shù)據(jù)流劃分為多個(gè)段，算法對(duì)每段分別聚類。該算法在整個(gè)數(shù)據(jù)流上進(jìn)行計(jì)算，每次都要積累一定數(shù)目的數(shù)據(jù)后才進(jìn)行處理，是一個(gè)數(shù)據(jù)流上的靜態(tài)算法，因此不能反映出數(shù)據(jù)流的變化情況。Aggarwal等人[3]提出的CluStream算法將數(shù)據(jù)流聚類分為在線聚集和離線分析兩部分。在線過(guò)程對(duì)數(shù)據(jù)流進(jìn)行初級(jí)聚類；離線過(guò)程根據(jù)用戶需求對(duì)在線得到的初級(jí)聚類進(jìn)行分析。在此基礎(chǔ)上，Aggarwal等人[4]在2004年又提出了HPStream算法。該算法采用投影的方式解決數(shù)據(jù)流的高維聚類問(wèn)題，動(dòng)態(tài)地選擇使聚類體積最小的那些維與聚類關(guān)聯(lián)，實(shí)現(xiàn)了一個(gè)子空間的聚類算法，并使用衰減因子隨時(shí)間推移不斷衰減歷史數(shù)據(jù)，并在聚類數(shù)目過(guò)多時(shí)，刪除最早加入的聚類。CluStream和HPStream算法都采用了K-means思想，得到的聚類結(jié)果通常都是球形的，不能得到任意形狀的聚類。朱蔚恒等人[6]提出基于密度與空間的ACluStream聚類算法，通過(guò)引入有嚴(yán)格空間意義的聚類塊，在對(duì)數(shù)據(jù)流進(jìn)行初步聚類的同時(shí)，盡量保留數(shù)據(jù)的空間特性，有效克服了CluStream算法不能支持任意形狀聚類的缺陷。但是它在處理不屬于已有聚類塊的新數(shù)據(jù)點(diǎn)時(shí)，使用一種類似拋硬幣的方法來(lái)猜測(cè)是否為新數(shù)據(jù)點(diǎn)創(chuàng)建一個(gè)新的聚類塊，誤差較大；而且它以絕對(duì)密度作為參考，在聚類結(jié)果中無(wú)法區(qū)分密度等級(jí)不同的簇[7]。
對(duì)于聚類分析任務(wù)，基于網(wǎng)格的聚類算法有很多理想的特性，如發(fā)現(xiàn)任意形狀或任意大小的簇、計(jì)算結(jié)果與數(shù)據(jù)輸入順序無(wú)關(guān)、計(jì)算時(shí)間與數(shù)據(jù)量無(wú)關(guān)等[8]。由于基于密度的聚類方法和基于網(wǎng)格的聚類方法有很好的互補(bǔ)性，大部分基于網(wǎng)格的方法都是以網(wǎng)格單元的密度屬性作為聚類依據(jù)的。WaveCluster[9]和CLIQUE[10]是網(wǎng)格聚類中的兩個(gè)典型算法。WaveCluster是一種多分辨率的聚類算法，它首先在數(shù)據(jù)空間上強(qiáng)加一個(gè)多維網(wǎng)格結(jié)構(gòu)來(lái)匯總數(shù)據(jù)，然后采用一種小波變換來(lái)變換原始的特征空間，在變換后的特征空間中找到密集區(qū)域。WaveCluster在低維數(shù)據(jù)空間上表現(xiàn)出了良好的性能。CLIQUE算法主要考慮高維子空間聚類，對(duì)大型高維數(shù)據(jù)聚類非常有效，但數(shù)據(jù)的維數(shù)增加時(shí)它表現(xiàn)出了良好的擴(kuò)展性，但由于方法的大大簡(jiǎn)化，降低了聚類結(jié)果的精確性。與大部分基于網(wǎng)格的聚類算法一樣，它們?cè)谟?jì)算網(wǎng)格密度時(shí)將網(wǎng)格中數(shù)據(jù)點(diǎn)的個(gè)數(shù)直接轉(zhuǎn)換為網(wǎng)格的密度值，忽略了周?chē)鷶?shù)據(jù)空間對(duì)網(wǎng)格的影響，容易導(dǎo)致聚類邊界點(diǎn)的丟失。2005年王生生等人[11]提出擴(kuò)展相鄰空間聚類算法來(lái)克服這一缺陷；2006年單世民[12]提出貢獻(xiàn)度的概念，通過(guò)計(jì)算網(wǎng)格獲取的貢獻(xiàn)度多少來(lái)計(jì)算網(wǎng)格單元的密度。本文在已有算法基礎(chǔ)上提出的基于動(dòng)態(tài)網(wǎng)格的數(shù)據(jù)流聚類算法(dynamicgrid-based clustering over data streams，DGCDS)，改進(jìn)了已有算法在密度計(jì)算、網(wǎng)格劃分和密度聚類方面存在的問(wèn)題，并實(shí)現(xiàn)了關(guān)鍵參數(shù)的自動(dòng)設(shè)置。
2基于動(dòng)態(tài)網(wǎng)格的數(shù)據(jù)流聚類算法
DGCDS算法基本思路：首先積累一段時(shí)間的數(shù)據(jù)流，得到數(shù)據(jù)流上的一個(gè)樣本集，在樣本集上對(duì)數(shù)據(jù)流進(jìn)行自下而上的網(wǎng)格劃分，進(jìn)而形成初始聚類；對(duì)數(shù)據(jù)流上新來(lái)的數(shù)據(jù)進(jìn)行判斷，根據(jù)不斷到來(lái)的數(shù)據(jù)點(diǎn)對(duì)網(wǎng)格進(jìn)行動(dòng)態(tài)合并，t時(shí)間后，對(duì)過(guò)去的數(shù)據(jù)按照參數(shù)進(jìn)行逐步遺忘。本章分三步對(duì)算法進(jìn)行描述：a)闡述了相關(guān)概念和網(wǎng)格劃分、網(wǎng)格密度和密度閾值的計(jì)算方法；b)闡述了一個(gè)針對(duì)靜態(tài)數(shù)據(jù)集的GCDS(grid-based clustering over dataset)算法，以在數(shù)據(jù)流樣本集上形成初始網(wǎng)格和初始聚類；c)在前兩步的基礎(chǔ)上闡述了一個(gè)完整的DGCDS算法。
21網(wǎng)格劃分
211基本概念
定義1d維數(shù)據(jù)集(A1，A2，…，Ad)是一個(gè)有界并且有序的定義域，S=A1×A2×…×Ad就是一個(gè)d維數(shù)據(jù)空間。X={X1，X2，…，Xn}表示S上的數(shù)據(jù)流在時(shí)間t內(nèi)的一個(gè)點(diǎn)集。其中：Xi={Xi1，Xi2，…，Xid}(i=1，2，…，n)。為不失一般性，假定任意維區(qū)間都是一個(gè)半開(kāi)半閉的區(qū)間[lj，hj)(j=1，2，…，d)，那么點(diǎn)集X可以表示為X=[l1，h1)×[l2，h2)×…×[ld，hd)。
定義2將數(shù)據(jù)空間的每一維分成長(zhǎng)度相等，互不相交的區(qū)間，向各維的正方向延伸區(qū)間長(zhǎng)度所形成的超矩形區(qū)域就是一個(gè)網(wǎng)格單元，記為grid(o)。
為了下一步的高效計(jì)算，本文設(shè)定每維被均勻劃分為k個(gè)區(qū)間，整個(gè)數(shù)據(jù)空間被分為kd個(gè)網(wǎng)格。其中第j維上網(wǎng)格邊長(zhǎng)δj可以通過(guò)式（1）計(jì)算得到：
δj=(hj-lj)/k(1)
由于均勻劃分，數(shù)據(jù)空間可能存在沒(méi)有數(shù)據(jù)對(duì)象的空網(wǎng)格。為了節(jié)省內(nèi)存空間，只保留非空網(wǎng)格單元。
為避免網(wǎng)格單元出現(xiàn)負(fù)數(shù)編號(hào)的情況，本文以每維的取值下限lj作為絕對(duì)參考點(diǎn)來(lái)建立空間坐標(biāo)。用gridi(Vi1，Vi2，…，Vid，Id)表示網(wǎng)格的空間位置。其中：vij(vij-，vij+)表示第i個(gè)網(wǎng)格在第j維上的坐標(biāo)區(qū)間；kj表示網(wǎng)格單元在第j維上以坐標(biāo)原點(diǎn)為始的網(wǎng)格索引編號(hào)；Id表示網(wǎng)格的編號(hào)。
vij-=lj+(kj-1)δjvij+=lj+kj×δj
(2)
用grid(count，den，cen，flag，W)描述網(wǎng)格特征。其中：count表示網(wǎng)格單元中數(shù)據(jù)點(diǎn)的個(gè)數(shù)；den表示網(wǎng)格單元的密度； cen表示網(wǎng)格單元的質(zhì)心；flag表示網(wǎng)格的類別；W(0＜w＜1)是網(wǎng)格密度衰減因子。
212網(wǎng)格密度的計(jì)算
大部分基于密度的網(wǎng)格算法都是將網(wǎng)格所包含的數(shù)據(jù)點(diǎn)個(gè)數(shù)直接轉(zhuǎn)換為網(wǎng)格單元的密度值。這種方法簡(jiǎn)單易行，且比較有效，但是運(yùn)用于聚類時(shí)，會(huì)丟失數(shù)據(jù)點(diǎn)對(duì)周?chē)臻g的影響信息，從而導(dǎo)致同屬一類的點(diǎn)被分在不同的類中，這種影響在網(wǎng)格單元邊界上體現(xiàn)尤為突出。圖1體現(xiàn)了密度計(jì)算方式對(duì)聚類結(jié)果的影響。其中，(a)是一個(gè)原始數(shù)據(jù)集，它主要包含一個(gè)橢圓形的類；(b)是執(zhí)行傳統(tǒng)網(wǎng)格劃分后得到的類，聚類邊界點(diǎn)大部分落于其他三個(gè)相鄰網(wǎng)格中而丟失。因此，需要設(shè)計(jì)一種方法來(lái)計(jì)算數(shù)據(jù)對(duì)周?chē)W(wǎng)格的影響，結(jié)合這些影響值計(jì)算網(wǎng)格單元的密度。
DENCLUE方法[13]是較早考慮數(shù)據(jù)對(duì)周?chē)臻g影響的密度算法。它認(rèn)為，每個(gè)數(shù)據(jù)對(duì)周?chē)臻g都會(huì)產(chǎn)生一定的影響，這種影響可以通過(guò)定義一個(gè)影響函數(shù)來(lái)度量，而空間中某一位置（如一個(gè)網(wǎng)格單元）的密度就是相關(guān)數(shù)據(jù)點(diǎn)對(duì)該位置的影響函數(shù)值的疊加。王生生等人[11]提出的擴(kuò)展相鄰空間聚類算法中采用了類似于影響函數(shù)的思想，它利用對(duì)初始網(wǎng)格單元的擴(kuò)展來(lái)計(jì)算網(wǎng)格周?chē)鷶?shù)據(jù)的影響。單世民在文獻(xiàn)[12]中提出貢獻(xiàn)度的概念，通過(guò)計(jì)算網(wǎng)格得到的貢獻(xiàn)度的大小來(lái)確定網(wǎng)格的密度。這種算法充分考慮了數(shù)據(jù)點(diǎn)對(duì)周?chē)臻g的影響，但是在得到一個(gè)精確的貢獻(xiàn)度值時(shí)需要經(jīng)過(guò)復(fù)雜的運(yùn)算，運(yùn)用于數(shù)據(jù)流上顯然是不合適的。因此，本文改進(jìn)單世民和王生生的算法，利用一個(gè)擴(kuò)展空間來(lái)計(jì)算網(wǎng)格的密度。
為了簡(jiǎn)便起見(jiàn)，本文在二維空間中對(duì)下面幾個(gè)概念進(jìn)行定義。
定義3初始網(wǎng)格單元。經(jīng)過(guò)初始階段劃分得到的網(wǎng)格單元，如圖2(a)中編號(hào)為(2，2)的網(wǎng)格單元。
定義4擴(kuò)展網(wǎng)格單元。對(duì)初始網(wǎng)格單元進(jìn)行邊長(zhǎng)擴(kuò)展（經(jīng)過(guò)反復(fù)實(shí)驗(yàn)，本文將擴(kuò)展長(zhǎng)度定為δj/4）后得到的網(wǎng)格單元，如圖2(b)中的大網(wǎng)格單元。
定義5擴(kuò)展區(qū)域。擴(kuò)展網(wǎng)格單元中除去初始網(wǎng)格單元的區(qū)域，如圖2(c)中灰色區(qū)域。
定義6相似度。兩個(gè)對(duì)象之間的相似程度的數(shù)值度量，常在[0，1]上取值。
在進(jìn)行網(wǎng)格密度計(jì)算時(shí)，將初始網(wǎng)格單元中每個(gè)數(shù)據(jù)點(diǎn)記為1，擴(kuò)展區(qū)域內(nèi)點(diǎn)對(duì)網(wǎng)格的影響度inf(0＜infi＜1)用數(shù)據(jù)點(diǎn)與網(wǎng)格質(zhì)心的相似度（鄰近程度）來(lái)度量。相似度越大，inf值越大，該數(shù)據(jù)點(diǎn)對(duì)網(wǎng)格影響越大；相似度越小，inf值越小，該數(shù)據(jù)點(diǎn)對(duì)網(wǎng)格的影響也越小。如果出現(xiàn)擴(kuò)展區(qū)域數(shù)據(jù)點(diǎn)與初始網(wǎng)格單元質(zhì)心相似度為0或者為負(fù)數(shù)的情況，則認(rèn)為數(shù)據(jù)點(diǎn)對(duì)網(wǎng)格單元的影響為0。這樣就充分考慮了網(wǎng)格周?chē)c(diǎn)的影響，而且計(jì)算簡(jiǎn)便。
網(wǎng)格密度計(jì)算過(guò)程描述如下：
a)劃分網(wǎng)格，將數(shù)據(jù)映射到相應(yīng)的網(wǎng)格單元中；
b)依次掃描每個(gè)網(wǎng)格單元，記錄下非空網(wǎng)格單元個(gè)數(shù)K和各非空網(wǎng)格單元中數(shù)據(jù)的個(gè)數(shù)count;
c)計(jì)算網(wǎng)格單元的質(zhì)心cen
cen=∑Xij∈grid Xij/count(3)
d)擴(kuò)展網(wǎng)格單元，按式(4)計(jì)算擴(kuò)展區(qū)域內(nèi)的數(shù)據(jù)對(duì)網(wǎng)格單元的影響值
inf=1-∑di=1(Xi-Ceni)2/δj(4)
e)計(jì)算網(wǎng)格單元密度
den=count+∑nj=1infi(5)
其中：n表示擴(kuò)展區(qū)域中數(shù)據(jù)點(diǎn)的個(gè)數(shù);infj表示擴(kuò)展區(qū)域中第j個(gè)數(shù)據(jù)點(diǎn)對(duì)網(wǎng)格的影響值。
213網(wǎng)格密度閾值
根據(jù)數(shù)據(jù)分布特點(diǎn)，具有相似屬性的一類數(shù)據(jù)往往會(huì)形成一個(gè)密集的數(shù)據(jù)區(qū)域，而另一些數(shù)據(jù)形成稀疏的數(shù)據(jù)區(qū)域，并且彼此相隔。因此需要設(shè)定一個(gè)密度閾值參數(shù)MinPts來(lái)判斷網(wǎng)格的稠密性。MinPts的值對(duì)算法結(jié)果的好壞有很大影響，尤其是在數(shù)據(jù)流環(huán)境下，要求對(duì)后來(lái)數(shù)據(jù)要有預(yù)先判斷以此來(lái)設(shè)定MinPts。傳統(tǒng)的方法要求用戶在對(duì)聚類的性質(zhì)有一定理解的基礎(chǔ)上來(lái)設(shè)置這個(gè)參數(shù)，很多情況下，對(duì)于用戶來(lái)說(shuō)這樣的要求很苛刻。因此，本文借鑒平均密度的思路設(shè)計(jì)了一種簡(jiǎn)單的方法自動(dòng)計(jì)算MinPts。
a)依次掃描所有網(wǎng)格單元，找出最大密度值記為max(den);
b)計(jì)算所有非空網(wǎng)格單元的平均密度值ave(den)
ave(den)=∑Ki=1dengi/K(6)
其中：K是所有非空網(wǎng)格單元的個(gè)數(shù)；dengi表示第i個(gè)非空網(wǎng)格單元的密度值。
c)計(jì)算密度閾值
MinPts=(max(den)+ave(den))/2(7)
根據(jù)網(wǎng)格密度和MinPts值可以將網(wǎng)格劃分為三類：密度大于MinPts的網(wǎng)格單元是高密單元(dense cell)；密度小于MinPts且與高密網(wǎng)格單元相鄰的網(wǎng)格單元是稀疏單元(sparse cell)；密度小于MinPts且周?chē)际窍∈鑶卧木W(wǎng)格單元是孤立單元(outlier cell)。高密單元中的數(shù)據(jù)點(diǎn)是聚類的主要對(duì)象，稀疏單元中的數(shù)據(jù)點(diǎn)可能是聚類的邊界點(diǎn)也可能是孤立點(diǎn)，而孤立單元中的點(diǎn)可以認(rèn)為是噪聲點(diǎn)。
22GCDS算法描述
通過(guò)上面的步驟，得到所有網(wǎng)格密度和類型，在此基礎(chǔ)上進(jìn)行聚類分析。首先給出下列定義。
定義7網(wǎng)格相鄰。當(dāng)且僅當(dāng)兩個(gè)網(wǎng)格有一條公共邊或者一個(gè)公共頂點(diǎn)。用數(shù)學(xué)方式可描述為，若兩個(gè)網(wǎng)格單元編號(hào)中對(duì)應(yīng)的維度索引號(hào)相減，結(jié)果不是1(-1)就是0，則說(shuō)明這兩個(gè)網(wǎng)格單元相鄰。
定義8聚類核心單元。具有最大密度值的網(wǎng)格單元。數(shù)據(jù)的分布總是遵循一定的規(guī)律，即具有相似屬性的數(shù)據(jù)相對(duì)集中在一起。根據(jù)這個(gè)特性可以判斷，具有最大密度的網(wǎng)格單元就是聚類核心單元，本文中將聚類核心單元作為聚類的起始點(diǎn)。
GCDS算法具體過(guò)程描述如下：
a)網(wǎng)格劃分。按照2.1節(jié)中的方法在樣本數(shù)據(jù)空間上進(jìn)行網(wǎng)格劃分，計(jì)算每個(gè)網(wǎng)格的密度，并根據(jù)密度閾值將網(wǎng)格標(biāo)記為D-Grid（高密單元）或者S-Grid（稀疏單元）或者O-Grid（孤立單元），將相關(guān)信息記錄在網(wǎng)格中。
b)聚類。在a)生成的網(wǎng)格中，記錄了網(wǎng)格的所有相關(guān)信息，此時(shí)，所有的網(wǎng)格都已標(biāo)志好類型。聚類時(shí)，首先搜索所有高密單元，找到聚類核心單元；然后從核心單元開(kāi)始采用深度優(yōu)先算法搜索所有相鄰的網(wǎng)格。若相鄰的兩個(gè)網(wǎng)格單元都是稠密的且距離（指兩個(gè)相鄰高密單元質(zhì)心的距離）小于給定閾值τ，則連接成一個(gè)類，標(biāo)記已聚類好的稠密網(wǎng)格單元；如果距離大于τ，說(shuō)明這兩個(gè)單元分屬于不同的聚類，分別以這兩個(gè)單元為起點(diǎn)，按照先前的方法搜索相鄰網(wǎng)格單元；若是稠密單元和稀疏單元相鄰，則稀疏單元中的數(shù)據(jù)點(diǎn)可能是聚類的邊界點(diǎn)，利用邊界點(diǎn)處理技術(shù)對(duì)稀疏單元中的數(shù)據(jù)進(jìn)行判斷。對(duì)未作標(biāo)記的稠密網(wǎng)格單元重復(fù)以上步驟，直到找到所有的類。
閾值τ由網(wǎng)格單元內(nèi)所有點(diǎn)到單元格質(zhì)心的平均距離決定，可以通過(guò)式（8）計(jì)算得到
τ=∑counti=1(Xi-cen)2」1/2/count
(8)
23完整的DGCDS算法描述
數(shù)據(jù)流上的數(shù)據(jù)不斷到來(lái)，聚類結(jié)果也需要不斷更新。通常有兩種方法來(lái)維持一個(gè)不斷更新的聚類結(jié)果[14]：一種方法是在新的數(shù)據(jù)集上重新執(zhí)行聚類過(guò)程，得到新的聚類結(jié)果，這種方法執(zhí)行起來(lái)簡(jiǎn)單，但是會(huì)增加時(shí)間復(fù)雜度，用在數(shù)據(jù)流上是不合適的；另一種方法是采用一種增量更新的算法，在原有聚類的基礎(chǔ)上進(jìn)行更新，這種方法具有良好的收縮性和較高的執(zhí)行效率。DGCDS就是在GCDS算法基礎(chǔ)上借鑒增量更新的思想，當(dāng)有新數(shù)據(jù)到來(lái)時(shí)，只考慮新數(shù)據(jù)影響到的那部分網(wǎng)格和類。
具體過(guò)程形式化地描述如下：
a)劃分網(wǎng)格，形成初始聚類。先積累一定時(shí)間的數(shù)據(jù)流，然后運(yùn)用GCDS算法，形成初始網(wǎng)格和初始聚類。
b)映射新加入的數(shù)據(jù)對(duì)象。
for新加入的數(shù)據(jù)對(duì)象Xi=(Xi1，Xi2，…，Xid)
if Xij[lj，hj)
if Xij屬于已存在的某個(gè)網(wǎng)格單元
then 直接定位其所在的網(wǎng)格，重新計(jì)算網(wǎng)格質(zhì)心，相應(yīng)網(wǎng)格的count=count+1，den=den+1；
if Xij不屬于已存在的某個(gè)網(wǎng)格單元
then 創(chuàng)建一個(gè)新網(wǎng)格以包含該數(shù)據(jù)；
if Xij[lj，hj)，
then 創(chuàng)建一個(gè)新網(wǎng)格以包含該數(shù)據(jù)。
如果數(shù)據(jù)落在相鄰網(wǎng)格的擴(kuò)展區(qū)域內(nèi)，用式(4)計(jì)算新數(shù)據(jù)對(duì)相鄰網(wǎng)格的影響值，通過(guò)式(5)更新網(wǎng)格的密度。
c)判斷數(shù)據(jù)對(duì)象的類型。新來(lái)的數(shù)據(jù)對(duì)象定位其所在的網(wǎng)格后，若其所在網(wǎng)格是稠密網(wǎng)格，則直接將其歸于網(wǎng)格所在的聚類中；若所在的網(wǎng)格是稀疏單元格，則計(jì)算它與最近一個(gè)聚類的相似度:
sim=1-∑di=1(Xi-Ci)2/δj(9)
如果sim大于相似度閾值ε，說(shuō)明數(shù)據(jù)點(diǎn)是聚類的邊界點(diǎn)；否則認(rèn)為數(shù)據(jù)點(diǎn)是一個(gè)孤立點(diǎn)或者噪聲點(diǎn)。
d)網(wǎng)格的合并。隨著數(shù)據(jù)的不斷流入，新增的網(wǎng)格會(huì)越來(lái)越多，在內(nèi)存空間有限的條件下，必須按照一定的原則對(duì)網(wǎng)格單元進(jìn)行合并，以節(jié)省空間消耗。合并的原則是：相鄰的兩個(gè)高密單元，若密度相近且距離（同GCDS算法中距離的意義一致）小于τ，則合并。設(shè)任意兩個(gè)相鄰的高密單元D-Gridi和D-Gridj，用Nij表示單元格D-Gridi和D-Gridj密度的近似程度
Nij=(min (dengi，dengj)/(max(dengi，dengj))(10)
若Nij接近1且距離小于τ，則合并這兩個(gè)相鄰的高密單元；否則，不合并。
e)網(wǎng)格的衰減。對(duì)于數(shù)據(jù)流數(shù)據(jù)而言，當(dāng)前和最近的數(shù)據(jù)才是人們關(guān)心的，因此，每過(guò)一定時(shí)間就對(duì)所有單元格進(jìn)行衰減。引入衰減因子w(0＜w＜1)對(duì)網(wǎng)格密度進(jìn)行更新，den=den×w。若den＜ξ(ξ是網(wǎng)格消除閾值），則從內(nèi)存中刪除相應(yīng)的網(wǎng)格。
在計(jì)算網(wǎng)格密度的過(guò)程中，由于考慮了相鄰網(wǎng)格內(nèi)數(shù)據(jù)的影響，在步驟c)的計(jì)算中也考慮了邊界點(diǎn)的問(wèn)題，此時(shí)聚類結(jié)果已經(jīng)比較精確，如無(wú)特別要求，不需要專門(mén)進(jìn)行邊界點(diǎn)檢測(cè)。
3算法分析
31時(shí)間復(fù)雜度分析
假設(shè)樣本數(shù)據(jù)集中數(shù)據(jù)對(duì)象個(gè)數(shù)為N1，整個(gè)數(shù)據(jù)流數(shù)長(zhǎng)度為N。算法第一步網(wǎng)格劃分階段，首先要找出每一維上的最大最小值，其時(shí)間復(fù)雜度為O(dN1)；然后將數(shù)據(jù)映射到網(wǎng)格中去，時(shí)間復(fù)雜度同樣為O(dN1)；在計(jì)算網(wǎng)格密度時(shí)，需要對(duì)所有網(wǎng)格進(jìn)行掃描，時(shí)間復(fù)雜度為O(kd)；在執(zhí)行GCDS算法過(guò)程中復(fù)雜度為O(K)。由于K≤kd≤N1，步驟a)時(shí)間復(fù)雜度實(shí)際上為O(2dN1)。步驟b)映射新加入的數(shù)據(jù)對(duì)象和步驟c)判斷數(shù)據(jù)點(diǎn)的類型時(shí)間復(fù)雜度都為O(dN)。步驟d)和步驟e)時(shí)間復(fù)雜度均為O(K)，即DGCDS算法的時(shí)間復(fù)雜度為O(2dN1+dN+dN+K+K)。對(duì)于整個(gè)數(shù)據(jù)流來(lái)說(shuō)，N遠(yuǎn)遠(yuǎn)大于樣本數(shù)據(jù)個(gè)數(shù)N1和非空網(wǎng)格單元個(gè)數(shù)K，因此，DGCDS算法時(shí)間復(fù)雜度無(wú)限接近O(dN)并且隨維度的增加而呈線性增加。
32算法評(píng)價(jià)
與現(xiàn)有網(wǎng)格算法相比，DGCDS算法存在以下幾方面的優(yōu)點(diǎn)：
a)優(yōu)化了網(wǎng)格密度計(jì)算方式。通過(guò)擴(kuò)展網(wǎng)格單元考慮了網(wǎng)格單元周?chē)臻g數(shù)據(jù)對(duì)網(wǎng)格的影響，雖然比直接將網(wǎng)格單元包含的數(shù)據(jù)個(gè)數(shù)轉(zhuǎn)換為網(wǎng)格密度的計(jì)算方法復(fù)雜，但是得到的聚類結(jié)果更加接近數(shù)據(jù)真實(shí)分布情況；而且與整個(gè)算法執(zhí)行時(shí)間比較起來(lái)，在網(wǎng)格密度計(jì)算上增加的時(shí)間是微不足道的。
b)本算法是一個(gè)增量式的數(shù)據(jù)流聚類方法。當(dāng)新數(shù)據(jù)到來(lái)時(shí)，算法只考慮新數(shù)據(jù)影響到的那部分網(wǎng)格，而不用重新執(zhí)行一次聚類算法。因此，該方法具有良好的伸縮性，能滿足數(shù)據(jù)流聚類的要求。
c)實(shí)現(xiàn)了關(guān)鍵參數(shù)的自適應(yīng)設(shè)置。在很多經(jīng)典的網(wǎng)格計(jì)算方法中，由于采取全局一致的密度閾值參數(shù)MinPts，經(jīng)常會(huì)出現(xiàn)高密度簇完全被相連的低密度簇所包含的情況，從而導(dǎo)致聚類結(jié)果難以分析。本文雖然也是采取全局一致的密度參數(shù)，但是MinPts值是在考慮整個(gè)數(shù)據(jù)分布特點(diǎn)的基礎(chǔ)上自動(dòng)設(shè)置而不用人工指定，并且在數(shù)據(jù)流環(huán)境下，隨著網(wǎng)格密度的改變，MinPts也會(huì)作出相應(yīng)改變。
4結(jié)束語(yǔ)
基于動(dòng)態(tài)網(wǎng)格的數(shù)據(jù)流聚類算法DGCDS使用網(wǎng)格和密度相結(jié)合的技術(shù)，能夠得到任意形狀的聚類，通過(guò)對(duì)網(wǎng)格密度計(jì)算方式的改進(jìn)，解決了現(xiàn)有網(wǎng)格算法中丟失數(shù)據(jù)空間影響信息的問(wèn)題，使得聚類邊界更平滑，并且實(shí)現(xiàn)了關(guān)鍵參數(shù)的自適應(yīng)設(shè)置，減少了人工參數(shù)對(duì)聚類結(jié)果的影響。如何進(jìn)一步提高算法執(zhí)行效率和精度以及對(duì)高維數(shù)據(jù)流的適應(yīng)性是筆者下一步的研究方向。
參考文獻(xiàn)：
［1］PAPADINITRIOU S， SUN J， FALOUTSOS C. Streaming pattern discovery in multiple time-series[C]//Proc of the 31st VLDB Conf. 2005:697-708.
[2]O’CALLAGHAN L， MISHRA N， MEYERSON A， et al. Streaming-data algorithm for high-quality clustering[C]//Proc of IEEE International Conference on Data Engineering. 2002:685-696.
[3]AGGARWAL C C， HAN J， WANG J，et al. A framework for clustering evolving data streams[C]//Proc of the 29th VLDB Conf. 2003.
[4]AGGARWAL C C， HAN J， WANG J， et al. A framework for projected clustering of high dimensional data streams[C]//Proc of the 30th VLDB Conf. 2004:852-863.
[5]ESTER M， KRIEGEL P， SANDER J，et al. Incremental clustering for mining in a data warehousing environment[C]//Proc of the 24th International Conference on VLDB Conf. New York: Morgan Kaufmann Publisher，1998:323-333.
[6]朱蔚恒，印鑒，謝益煌.基于數(shù)據(jù)流的任意形狀聚類算法[J].軟件學(xué)報(bào)，2006，17(3):379-387.
[7]LIU Qing-bao， DENG Su， LU Chang-hui， et al. Relative density based k-nearest neighbors clustering algorithm[C]//Proc ofInternational Conference on Machine Learning and Cybernetics. 2003.
[8]孫玉芬，盧炎生.一種基于網(wǎng)格方法的高維數(shù)據(jù)流子空間聚類算法[J].計(jì)算機(jī)科學(xué)，2007，34(4):199-203.
[9]SHEKHOLESLAMI G， CHATTERJEE S A.WaveCluster:multi-resolution clustering approach for very large spatial databases[C]//Proc of the 24th Conference on VLDB. New York:[s.n.]， 1998:428-439.
[10]AGRAWAL R， GEHRKE J，GUNOPULOS D，et al. Automatic subspace clustering of high dimensional data for data mining applications[C]//Proc of ACM SIGMOD Conf.Seattle: [s.n.]，1998:94-105.
[11]王生生，劉大有，曹斌.一種高維空間數(shù)據(jù)的子空間聚類算法[J].計(jì)算機(jī)應(yīng)用，2005，25(11):2615-2617.
[12]單世民.基于網(wǎng)格和密度的數(shù)據(jù)流聚類方法研究[D].大連：大連理工大學(xué)，2006.
[13]HINNEBURG A， KEIM D A. An efficient approach to clustering in large multimedia databases with noise[C]//Proc of 1998 Internatio-nal Conference on Knowledge Discovery and Data Mining. New York:[s.n.]，1998:58-65.
[14]馮興杰，黃亞樓.增量式CURE聚類算法研究[J].小型微型計(jì)算機(jī)系統(tǒng)，2004，25(10)：1847-1849.
