（武漢科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 武漢 430081）

摘 要：

提出一種基于衰減窗口的實(shí)時(shí)數(shù)據(jù)流聚類算法PDStream。算法首先對(duì)數(shù)據(jù)空間進(jìn)行網(wǎng)格劃分，采用改進(jìn)的維度樹結(jié)構(gòu)維護(hù)和更新數(shù)據(jù)流的摘要信息，設(shè)計(jì)了一種周期性剪枝策略，周期性地剪去維度樹中的稀疏網(wǎng)格，最后采用深度優(yōu)先搜索算法在線處理聚類請(qǐng)求。基于人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)表明，PDStream算法可以有效地發(fā)現(xiàn)數(shù)據(jù)流中任意形狀的聚類，內(nèi)存消耗少，具有較好的計(jì)算精度。

關(guān)鍵詞：數(shù)據(jù)流； 網(wǎng)格聚類； 衰減窗口； 維度樹； 剪枝策略

中圖分類號(hào)：TP311文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2009)04-1331-04

Real-time data stream clusteringbased on damped window and pruning dimension tree

ZHANG Xiao-long， ZENG Wei

(School of Computer Science Technology， Wuhan University of Science Technology， Wuhan 430081， China)

Abstract:

This paper proposed a novel real-time data stream clustering algorithm PDStream， which was based on damped window. PDStream firstly divided data space into grids， then used an improved dimension tree structure to maintain and update the data stream summary statistics. Designed a pruning strategy to prune the sparse grids in dimension tree periodically. Finally used the depth first search (DSF) method to deal with online clustering request. The experimental results on synthetic dataset and real dataset demonstrate that PDStream has the advantages of discovering clusters of arbitrary shape effectively， low memory consumption， preferable precision.

Key words：data stream; grid clustering; damped window; dimension tree; pruning strategy

隨著計(jì)算機(jī)技術(shù)和傳感器網(wǎng)絡(luò)的飛速發(fā)展，在網(wǎng)絡(luò)監(jiān)控、工業(yè)控制、股票交易、互聯(lián)網(wǎng)通信等諸多領(lǐng)域中產(chǎn)生了連續(xù)到達(dá)、實(shí)時(shí)變化的海量數(shù)據(jù)序列。這種以實(shí)時(shí)方式快速到達(dá)的海量數(shù)據(jù)稱為數(shù)據(jù)流，它是實(shí)時(shí)、連續(xù)、有序的數(shù)據(jù)序列，每個(gè)數(shù)據(jù)出現(xiàn)的順序、速率與時(shí)刻均不可控制[1]。實(shí)際應(yīng)用中迫切需要從這種新的數(shù)據(jù)形態(tài)中獲取有價(jià)值的信息和知識(shí)。針對(duì)數(shù)據(jù)流模型的數(shù)據(jù)挖掘和知識(shí)發(fā)現(xiàn)由此而成為重要的研究課題[1~4]，數(shù)據(jù)流聚類作為知識(shí)發(fā)現(xiàn)的重要手段得到了深入的研究。與傳統(tǒng)聚類一樣，數(shù)據(jù)流聚類按照對(duì)象間的相似性，將數(shù)據(jù)流中的數(shù)據(jù)劃分成一個(gè)或多個(gè)類，使得類內(nèi)數(shù)據(jù)具有較高的相似度，類與類之間的數(shù)據(jù)具有較低的相似度。在數(shù)據(jù)流環(huán)境下進(jìn)行聚類分析對(duì)算法提出了新的要求：對(duì)數(shù)據(jù)流的掃描次數(shù)僅限于單遍；數(shù)據(jù)處理的速度不能低于數(shù)據(jù)流的流速；算法空間復(fù)雜度一般要求在O(poly(log N))范圍內(nèi)；挖掘結(jié)果隨數(shù)據(jù)流不斷流入而增量更新。由于以上要求，傳統(tǒng)的聚類算法不能直接應(yīng)用于數(shù)據(jù)流。

本文介紹了數(shù)據(jù)流聚類的相關(guān)研究及PDStream算法的思路，給出了本文算法所使用的基本概念、定義和基于衰減窗口模型的數(shù)據(jù)流聚類及剪枝策略，并對(duì)仿真數(shù)據(jù)集和真實(shí)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)比較分析。

1 相關(guān)研究

目前數(shù)據(jù)流的聚類分析都是基于某種特定時(shí)間窗口進(jìn)行的，常用的窗口模型有三種，即界標(biāo)窗口、滑動(dòng)窗口和衰減窗口。

界標(biāo)窗口模型下的聚類對(duì)象為從數(shù)據(jù)流開始到當(dāng)前時(shí)刻的所有數(shù)據(jù)，界標(biāo)窗口一般隨著數(shù)據(jù)流進(jìn)行而不斷增加。Guha等人[5]最早提出的LocalSearch算法采用分治策略，使用迭代的方法實(shí)現(xiàn)有限空間上數(shù)據(jù)流K平均聚類；Callaghan等人[6]隨后在此基礎(chǔ)上提出了stream算法，它們都是基于界標(biāo)窗口模型，不能反映數(shù)據(jù)流的動(dòng)態(tài)演化，界標(biāo)窗口下的數(shù)據(jù)流聚類實(shí)際上是單遍掃描約束下的傳統(tǒng)聚類。

數(shù)據(jù)流應(yīng)用中，用戶傾向于關(guān)注特定時(shí)間段內(nèi)數(shù)據(jù)流的聚類形態(tài)，而且隨著數(shù)據(jù)流的大量流入，對(duì)從數(shù)據(jù)流開始到當(dāng)前時(shí)刻的所有數(shù)據(jù)進(jìn)行聚類的結(jié)果往往沒有實(shí)際意義?；谶@一需求，學(xué)者提出滑動(dòng)窗口模型，即在任意時(shí)刻t，需要聚類的數(shù)據(jù)流片段是{Xmax(0，t-W+1)，…，Xt}，對(duì)于時(shí)間戳max(0，t-W+1)之后的數(shù)據(jù)全部忽略。CluStream算法[7]首次提出針對(duì)數(shù)據(jù)流的兩階段聚類框架，即在線微聚類和離線宏聚類，實(shí)現(xiàn)近期數(shù)據(jù)的聚類和用戶指定時(shí)間段的聚類，同時(shí)支持?jǐn)?shù)據(jù)流的動(dòng)態(tài)演化分析。但CluStream基于K-means聚類，聚類結(jié)果趨于球形，且需要用戶人為指定聚類簇的個(gè)數(shù)；CD-Stream[8]通過在每個(gè)非空的空間網(wǎng)格中維護(hù)一個(gè)滑動(dòng)窗口實(shí)現(xiàn)了指定時(shí)間段的數(shù)據(jù)流聚類。

衰減窗口模型的聚類對(duì)象與界標(biāo)窗口一樣，但每個(gè)數(shù)據(jù)點(diǎn)具有不同的權(quán)值，按照數(shù)據(jù)點(diǎn)到達(dá)的時(shí)刻，離當(dāng)前時(shí)刻越近的數(shù)據(jù)點(diǎn)被賦予越大的權(quán)值，逐步消除歷史數(shù)據(jù)對(duì)聚類的影響。HPStream算法[9]按照f(t)=2-λt(λ>0)給數(shù)據(jù)點(diǎn)賦予不同的權(quán)值，同時(shí)采用維度投影技術(shù)解決高維數(shù)據(jù)流聚類問題，算法需要用戶輸入衰退聚類結(jié)構(gòu)的個(gè)數(shù)以及平均聚類維數(shù)，用戶往往不具備這樣的知識(shí)。D-Stream算法[10]也是一種基于衰減窗口的流數(shù)據(jù)聚類算法，算法在內(nèi)存中維護(hù)一個(gè)代表非空網(wǎng)格的哈希表，對(duì)哈希表進(jìn)行周期性掃描，及時(shí)刪除代表噪聲的網(wǎng)格，在密集網(wǎng)格中尋找聚類。

本文設(shè)計(jì)了一個(gè)基于衰減窗口模型的數(shù)據(jù)流網(wǎng)格聚類算法，即PDStream。主要工作有：采用一種改進(jìn)的維度樹結(jié)構(gòu)作為數(shù)據(jù)流概要數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)方式，以適應(yīng)數(shù)據(jù)流對(duì)內(nèi)存空間的限制；提出一種剪枝策略，周期性地減去維度樹中大部分稀疏網(wǎng)格對(duì)應(yīng)的分支，確保算法性能不會(huì)因?yàn)閿?shù)據(jù)流的快速流入而性能急劇下降；有別于傳統(tǒng)的網(wǎng)格聚類算法采用全局絕對(duì)密度閾值，設(shè)計(jì)一種隨時(shí)間變化的密度閾值函數(shù)，以準(zhǔn)確地識(shí)別特定時(shí)刻數(shù)據(jù)流中的聚類。

2 基本概念和定義

A={A1，A2，…，Ad}是一個(gè)有界、全部有序域集合，則S= A1×A2×…×Ad表示一個(gè)d維數(shù)值空間，A1，A2，…，Ad為S的d個(gè)維度。數(shù)據(jù)流定義為S中一系列按時(shí)間順序到達(dá)的數(shù)據(jù)點(diǎn)集合DS={X1，X2，…，Xn，…}，對(duì)應(yīng)的時(shí)刻依次為t1，t2，…，tn，…。Xi=(xi1，xi2，…，xid)表示一個(gè)數(shù)據(jù)點(diǎn)(xi1∈A1，xi2∈A2，…，xid∈Ad)，對(duì)應(yīng)于數(shù)值空間S中的一個(gè)點(diǎn)。

定義1 網(wǎng)格。將數(shù)值空間S的每一維平均分割成ξ個(gè)區(qū)間，每個(gè)區(qū)間是該維上的一個(gè)右開的間隔段[li，hi)，長度為len，依次編號(hào)為1，2，…， ξ。數(shù)值空間S被劃分成ξd個(gè)互不相交的網(wǎng)格，每個(gè)網(wǎng)格g是S中一個(gè)d維超立方體，可表示為(v1，v2，…，vd)，vi為網(wǎng)格g在第i(1≤i≤d)維上對(duì)應(yīng)的區(qū)間編號(hào)。

定義2 數(shù)據(jù)點(diǎn)的密度系數(shù)。假設(shè)數(shù)據(jù)點(diǎn)X到達(dá)的時(shí)刻為t，則該數(shù)據(jù)點(diǎn)在任意時(shí)刻T的密度系數(shù)為D(X，t)=λT-t，λ為衰減因子(0<λ<1)。

定義3 網(wǎng)格密度。對(duì)于數(shù)據(jù)點(diǎn)X=(x1，x2，…，xd)，如果存在這樣一個(gè)網(wǎng)格g=(v1，v2，…，vd)，使得X在每一維上的取值xi都在第i維編號(hào)為vi的區(qū)間中，則該數(shù)據(jù)點(diǎn)X屬于網(wǎng)格g，記做X∈g。g在時(shí)刻t的網(wǎng)格密度表示為density(g，t)，其值為t時(shí)刻屬于網(wǎng)格g的所有數(shù)據(jù)點(diǎn)的密度系數(shù)之和。

定義4 網(wǎng)格特征向量。該向量用一個(gè)四元組(P， density， class， tl)表示。其中：P是d維向量，表示該網(wǎng)格的坐標(biāo)，用網(wǎng)格在對(duì)應(yīng)維的區(qū)間編號(hào)表示；density表示網(wǎng)格在時(shí)刻tl的密度值；class表示網(wǎng)格所屬的聚類簇標(biāo)號(hào)；tl表示網(wǎng)格最后獲得數(shù)據(jù)點(diǎn)的時(shí)刻。

假設(shè)網(wǎng)格g最后更新其密度的時(shí)刻為tl，其密度值為dentity(g，tl)，網(wǎng)格g在tn時(shí)刻又收到一個(gè)新的數(shù)據(jù)點(diǎn)，則網(wǎng)格g的密度可以用如下的方式進(jìn)行增量更新[10]：

density(g，tn)=λtn-tldensity(g，tl)+1(1)

定義5 相連的網(wǎng)格。兩個(gè)網(wǎng)格g1、g2相連是指g1、g2有一個(gè)公共的超平面或者存在一個(gè)網(wǎng)格g3，使得g1與g3相連，g2與g3相連。

定義6 聚類。t時(shí)刻的一個(gè)聚類可以定義為d維數(shù)值空間中一組相連的密集網(wǎng)格的集合。

3 基于衰減窗口的數(shù)據(jù)流網(wǎng)格聚類

3.1 算法框架

PDStream算法是一個(gè)連續(xù)在線的過程，算法在連續(xù)地處理數(shù)據(jù)流的同時(shí)，在線響應(yīng)用戶的聚類請(qǐng)求?？蚣苋缦拢?/p>

while (!數(shù)據(jù)流結(jié)束)

{

讀取當(dāng)前時(shí)刻curTime到達(dá)的所有數(shù)據(jù)點(diǎn)到bucket；

for (bucket中的每一個(gè)數(shù)據(jù)點(diǎn)Xi)

 updateTree (Xi); //根據(jù)當(dāng)前數(shù)據(jù)點(diǎn)更新維度樹

computeDensityThreshold( );//根據(jù)當(dāng)前參數(shù)計(jì)算密度閾值

if (curTime mod period==0)

{

updateGridDensityToCurrentTime ( );

//更新網(wǎng)格節(jié)點(diǎn)的密度為當(dāng)前時(shí)刻的密度

registerNodeMaxDensity ( ); //登記中間節(jié)點(diǎn)的最大密度

pruningTree ( ); //對(duì)維度樹進(jìn)行剪枝

}//end of if

if (curTime時(shí)刻有聚類請(qǐng)求)

{

cluster ( ); //在維度樹中進(jìn)行聚類

輸出聚類結(jié)果；

}//end of if

curTime++；

}//end of while

首先，從數(shù)據(jù)流DS讀取當(dāng)前時(shí)刻curTime到達(dá)的所有數(shù)據(jù)點(diǎn)，根據(jù)數(shù)據(jù)點(diǎn)的屬性值登記其在維度樹中的信息。處理完畢當(dāng)前時(shí)刻到達(dá)的所有數(shù)據(jù)點(diǎn)后，計(jì)算出當(dāng)前時(shí)刻的密度閾值densityThreshold(curTime)，然后進(jìn)行兩項(xiàng)檢測(cè)：a)檢查該時(shí)刻是否需要進(jìn)行維度樹剪枝，是則調(diào)用剪枝模塊；b)檢查當(dāng)前時(shí)刻用戶是否提出聚類請(qǐng)求，是則調(diào)用聚類模塊，輸出聚類結(jié)果。循環(huán)處理下一時(shí)刻的所有數(shù)據(jù)點(diǎn)，直到數(shù)據(jù)流完畢。

3.2 數(shù)據(jù)流摘要信息維護(hù)

由于數(shù)據(jù)流流速快、數(shù)據(jù)量大，系統(tǒng)內(nèi)存相對(duì)不足，數(shù)據(jù)流聚類算法不能將衰減窗口內(nèi)的所有數(shù)據(jù)點(diǎn)保存于內(nèi)存中。文獻(xiàn)[8]中提出了一種基于滑動(dòng)窗口的維度樹結(jié)構(gòu)，本文在其基礎(chǔ)上進(jìn)行了改進(jìn)，用來在衰減窗口下在線維護(hù)和更新數(shù)據(jù)流的摘要信息。

首先按照定義1將數(shù)值空間進(jìn)行網(wǎng)格劃分，得到ξd個(gè)網(wǎng)格，為了節(jié)省內(nèi)存，只需存儲(chǔ)其中包含有數(shù)據(jù)點(diǎn)的非空網(wǎng)格。本文所使用的維度樹結(jié)構(gòu)是一棵深度為d+1的多叉樹，d是數(shù)據(jù)流的維度，多叉樹前d層從上到下分別對(duì)應(yīng)于數(shù)值空間的d個(gè)維度，第d+1層對(duì)應(yīng)于非空網(wǎng)格，樹中的每一個(gè)節(jié)點(diǎn)存放該層對(duì)應(yīng)的維上有數(shù)據(jù)點(diǎn)落入的間段隔的編號(hào)，并且從小到大排序，從樹根到葉子節(jié)點(diǎn)的一條路徑可以惟一確定一個(gè)網(wǎng)格，每網(wǎng)格用定義4中的特征向量來表示。

如表1所示，有15個(gè)二維數(shù)據(jù)點(diǎn)按時(shí)間順序先后達(dá)到，t表示數(shù)據(jù)點(diǎn)到達(dá)的時(shí)刻。每一維被平均劃分成5個(gè)區(qū)間(len=0.2)。圖1顯示了對(duì)二維空間進(jìn)行網(wǎng)格劃分后數(shù)據(jù)點(diǎn)的分布狀態(tài)；圖2則是對(duì)應(yīng)的維度樹，第一層對(duì)應(yīng)于A1維，第二層對(duì)應(yīng)于A2維，葉子節(jié)點(diǎn)代表二維網(wǎng)格單元。例如，數(shù)據(jù)點(diǎn)(0.29，0.37)對(duì)應(yīng)的網(wǎng)格坐標(biāo)應(yīng)為(2，2)，根據(jù)網(wǎng)格坐標(biāo)(2，2)可以在維度樹中快速地找到其對(duì)應(yīng)的網(wǎng)格。

表1 一個(gè)二維數(shù)據(jù)流的例子

數(shù)據(jù)點(diǎn)t數(shù)據(jù)點(diǎn)t數(shù)據(jù)點(diǎn)t

(0.29，0.37)0(0.78， 0.90)5(0.93， 0.81)10

(0.21，0.59)1(0.36， 0.54)6(0.24， 0.43)11

(0.99， 0.67)2(0.97， 0.10)7(0.70， 0.84)12

(0.30， 0.47)3(0.82， 0.94)8(0.33， 0.23)13

(0.90， 0.73)4(0.22， 0.30)9(0.61， 0.95)14

維度樹隨著數(shù)據(jù)點(diǎn)的不斷流入而動(dòng)態(tài)地生長和更新，更新策略如下：

a）根據(jù)當(dāng)前接收到的數(shù)據(jù)點(diǎn)X=(x1，x2，…，xd)，計(jì)算出其對(duì)應(yīng)網(wǎng)格g的坐標(biāo)P=(v1，v2，…，vd)；

b）從維度樹樹根開始查找，如果編號(hào)vi在維度樹第i層對(duì)應(yīng)的節(jié)點(diǎn)中不存在，則將當(dāng)前編號(hào)vi按順序插入到對(duì)應(yīng)的節(jié)點(diǎn)中；如果存在，則繼續(xù)向下查找；

c）如果對(duì)應(yīng)的網(wǎng)格g在葉子節(jié)點(diǎn)中不存在，則在當(dāng)前節(jié)點(diǎn)下創(chuàng)建網(wǎng)格g，特征向量設(shè)置為P=(v1，v2，…，vd)， density=1， class=0， tl=curTime；

d）如果網(wǎng)格g在葉子節(jié)點(diǎn)層存在，則tl=curTime，根據(jù)式（1）更新g的密度。

由式（1）可知，在對(duì)當(dāng)前接收到數(shù)據(jù)點(diǎn)的網(wǎng)格的特征向量進(jìn)行更新時(shí)，無須重新計(jì)算屬于該網(wǎng)格的所有數(shù)據(jù)點(diǎn)的密度系數(shù)之和，只需按式（1）進(jìn)行增量更新即可。



定理1 設(shè)網(wǎng)格g最后更新其密度的時(shí)刻為tl，其密度值為dentity(g， tl)，從tl時(shí)刻一直到時(shí)刻curTime（curTime＞tl），該網(wǎng)格沒有接收到任何數(shù)據(jù)點(diǎn)，則網(wǎng)格在當(dāng)前時(shí)刻curTime的密度為

density(g，curTime)=λcurTime-tldensity(g，tl)(2)

證明 假設(shè)在tl時(shí)刻網(wǎng)格g已經(jīng)接收到了m個(gè)數(shù)據(jù)點(diǎn)，分別是X1，X2，…，Xm，其到達(dá)的時(shí)刻分別為t1，t2，…，tm(tm≤tl)，根據(jù)定義2與3則有density(g，tl)=∑mi=1D(Xi，tl)=∑mi=1λtl-ti ，所以

density(g，curTime)=∑mi=1D(Xi，curTime)=∑mi=1λcurTime-ti=

∑mi=1λcurTime-tl×λtl-ti=λcurTime-tl∑mi=1λtl-ti=λcurTime-tldensity(g，tl)

由于網(wǎng)格特征向量中存放了網(wǎng)格最近一次獲得數(shù)據(jù)點(diǎn)的時(shí)刻及該時(shí)刻的密度值，如果該網(wǎng)格隨后一直沒有接收到數(shù)據(jù)點(diǎn)，在時(shí)刻curTime其密度值可按式(2)進(jìn)行累計(jì)更新。

3.3 數(shù)據(jù)流在線聚類過程

假設(shè)數(shù)據(jù)流的流速為speed，即在同一個(gè)單位時(shí)間到達(dá)的數(shù)據(jù)點(diǎn)個(gè)數(shù)為speed。為了識(shí)別不同時(shí)刻維度樹中的密集網(wǎng)格，定義一個(gè)密度閾值函數(shù)：

densityThereshold(t)=β(1-λt+1)speed/[N(1-λ)](3)

其中:λ為衰減因子(0<λ<1)，N=ξd為數(shù)值空間劃分后的網(wǎng)格總數(shù)，speed為數(shù)據(jù)流的流速，β為閾值調(diào)節(jié)系數(shù)(β>1)。規(guī)定若在t時(shí)刻維度樹中一個(gè)網(wǎng)格的密度density(g，t)≥densityThreshold(t)，表示網(wǎng)格g在t時(shí)刻是密集網(wǎng)格。

根據(jù)定義6，當(dāng)用戶提出聚類請(qǐng)求時(shí)，只需在當(dāng)前維度樹的所有葉子節(jié)點(diǎn)中進(jìn)行搜尋，一組相連的密集網(wǎng)格的集合就代表一個(gè)聚類簇。由圖2可以看出，在當(dāng)前時(shí)刻curTime，維度樹中的網(wǎng)格單元最后更新的時(shí)刻tl不一致，無法進(jìn)行密度比較。因此，需要首先將所有的網(wǎng)格按照定理1更新為當(dāng)前時(shí)刻curTime所對(duì)應(yīng)的密度值。

在線聚類過程反復(fù)地在維度樹中找到一個(gè)未被聚類(class=0)并且具有最大密度值的網(wǎng)格，然后以此網(wǎng)格為起點(diǎn)按照深度優(yōu)先策略尋找聚類，直到找到的最大密度值小于densityThreshold(t)為止。

由于維度樹結(jié)構(gòu)很好地保持了S空間中非空網(wǎng)格之間的位置關(guān)系信息，可以高效地查找某個(gè)網(wǎng)格的所有鄰居，從而在線聚類過程可以高效地進(jìn)行。根據(jù)定義5，對(duì)于兩個(gè)d維網(wǎng)格g和g′，網(wǎng)格坐標(biāo)分別為(v1，v2，…，vd)，(v1′，v2′，…，vd′ )，若存在一個(gè)k(1≤k≤d)，使得vi= vi′ (i=1，2，…，k-1，k+1，…，d)，而且| vk- vk′ |=1，則g′與g互為鄰居。因此只需將網(wǎng)格g的每一維坐標(biāo)加減1就可以得到其所有2d個(gè)鄰居的位置坐標(biāo)。基于該坐標(biāo)從維度樹樹根開始搜尋，對(duì)應(yīng)的葉子節(jié)點(diǎn)就是要找的鄰居網(wǎng)格。

設(shè)r指向當(dāng)前維度樹中class=0且具有最大密度值的網(wǎng)格，clusterNum為聚類編號(hào)，從1開始，聚類完畢后維度樹中具有同一編號(hào)的網(wǎng)格集合就是一個(gè)聚類。以r所指網(wǎng)格為起點(diǎn)尋找一個(gè)聚類的過程可以表示如下：

findACluster (r， clusterNum)

{

r->class=clusterNum;//對(duì)當(dāng)前網(wǎng)格進(jìn)行聚類標(biāo)號(hào)

for (i=0; i<2d; i++)

{

s=findGrid(r的一個(gè)鄰居g′)

//返回維度樹中指向該鄰居的指針

if (s==NULL) continue; //該鄰居在維度樹中不存在

if (s->class==0 s->density>=densityThreshold(t))

findACluster (s， clusterNum);

}//end of for

}//end of findACluster

3.4 剪枝策略

隨著新數(shù)據(jù)點(diǎn)不斷流入和衰減因子作用下歷史數(shù)據(jù)的不斷衰減，維度樹在動(dòng)態(tài)地生長，相關(guān)葉子節(jié)點(diǎn)的特征向量也在實(shí)時(shí)更新。隨著時(shí)間推移，維度樹中會(huì)生成許多密度值較小的稀疏網(wǎng)格。這些稀疏網(wǎng)格主要來源于兩個(gè)方面：a)網(wǎng)格在以前某些時(shí)刻接收到了少量數(shù)據(jù)點(diǎn)，此后一直未接收到數(shù)據(jù)點(diǎn)；b)網(wǎng)格最近收到較少的數(shù)據(jù)點(diǎn)，密度值較小，但是隨后一段時(shí)間可能接收到較多數(shù)據(jù)點(diǎn)而形成一個(gè)密集網(wǎng)格。對(duì)于前一種網(wǎng)格一般對(duì)應(yīng)于傳統(tǒng)聚類中的孤立點(diǎn)，而對(duì)于后一種網(wǎng)格則是有可能轉(zhuǎn)變?yōu)槊芗W(wǎng)格的孤立點(diǎn)。

本文設(shè)計(jì)了一個(gè)周期性剪枝策略，通過設(shè)定周期值剪去當(dāng)前維度樹中大部分離群點(diǎn)所對(duì)應(yīng)的稀疏網(wǎng)格，被剪掉的潛在密集網(wǎng)格由于在隨后一段時(shí)間會(huì)接收新的數(shù)據(jù)點(diǎn)，而在維度樹中被再次重建。基于這一事實(shí)，通過設(shè)定周期值給予潛在密集網(wǎng)格一定的成長時(shí)間，該剪枝策略在犧牲小部分“潛在密集網(wǎng)格”的情況下，及時(shí)消除數(shù)據(jù)流中大部分真實(shí)離群點(diǎn)。而且，隨著數(shù)據(jù)點(diǎn)流入，若不對(duì)維度樹加以控制，會(huì)使得維度樹趨于一棵完全樹，算法聚類性能急劇下降，內(nèi)存消耗大幅增長，這一現(xiàn)象對(duì)于高維數(shù)據(jù)流尤為明顯。

為了實(shí)現(xiàn)周期性剪枝策略，需要對(duì)第2章設(shè)計(jì)的維度樹結(jié)構(gòu)進(jìn)行修改，為每個(gè)非葉子節(jié)點(diǎn)開辟一個(gè)存儲(chǔ)空間，存放該節(jié)點(diǎn)的所有孩子節(jié)點(diǎn)中最大的密度值maxDensity。設(shè)在時(shí)刻t一棵二維的維度樹如圖3所示，各個(gè)非葉節(jié)點(diǎn)中保存了其所有孩子中的最大密度值。假設(shè)當(dāng)前密度閾值函數(shù)的值densityThreshold(t)=5.0，則圖中虛線框內(nèi)的兩個(gè)分支符合被剪枝的條件，可以全部剪去。



剪枝前維度樹中網(wǎng)格密度不是同一時(shí)刻的，需要進(jìn)行如下預(yù)操作：a)根據(jù)定理1將維度樹中所有網(wǎng)格更新到當(dāng)前時(shí)刻；b)登記非葉節(jié)點(diǎn)中的最大密度值，該過程采用一個(gè)自底向上的層次遍歷算法實(shí)現(xiàn)。遞歸的剪枝算法描述如下：

pruningTree (H， level)

//H為指向樹當(dāng)前節(jié)點(diǎn)的指針，level表示樹的當(dāng)前層數(shù)

{

if (level==d)

return;

if (H->maxDensity

{ 刪除當(dāng)前節(jié)點(diǎn)H對(duì)應(yīng)的分支；

 釋放其占用的內(nèi)存空間；

}

for (H的每一個(gè)孩子child)

pruningTree (child， level+1);

}//end of pruningTree

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

為了驗(yàn)證本文算法的有效性和計(jì)算精度，在VC 6.0環(huán)境下用C語言實(shí)現(xiàn)了PDStream算法和聚類結(jié)果的統(tǒng)計(jì)程序，同時(shí)針對(duì)人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集進(jìn)行了相關(guān)的實(shí)驗(yàn)。實(shí)驗(yàn)平臺(tái)為一臺(tái)CPU 3.0 GHz、內(nèi)存512 MB、操作系統(tǒng)為Windows XP的PC機(jī)。

首先生成一個(gè)大小為100 KB的二維人工數(shù)據(jù)集，如圖4所示。其中有四個(gè)均勻分布的聚類，包含球形及非凸形狀的聚類，5 KB個(gè)噪聲點(diǎn)均勻分布在二維空間中。為了將其模擬成二維實(shí)時(shí)數(shù)據(jù)流，每讀入一個(gè)數(shù)據(jù)點(diǎn)為其加上一個(gè)時(shí)間標(biāo)簽，每一個(gè)未被讀取的數(shù)據(jù)點(diǎn)都以等可能的概率成為當(dāng)前被讀取到的數(shù)據(jù)點(diǎn)。

算法參數(shù)設(shè)置如下：len=0.01表示每一維被等分為100個(gè)片段，衰減因子λ=0.98， speed=1 000表示每個(gè)時(shí)間單位流入1 000個(gè)數(shù)據(jù)點(diǎn)， β=2， 剪枝周期period=10，在數(shù)據(jù)流結(jié)束時(shí)(t=99)提出聚類請(qǐng)求。由于算法沒有保存原始數(shù)據(jù)點(diǎn)的信息，將被聚類的密集網(wǎng)格作為結(jié)果顯示出來，如圖5所示?？梢钥闯霰疚乃惴梢院芎玫刈R(shí)別出實(shí)時(shí)數(shù)據(jù)流中具有任意形狀的聚類簇。



實(shí)驗(yàn)采用的真實(shí)數(shù)據(jù)集為ForestCoverType數(shù)據(jù)集，該數(shù)據(jù)集為美國森林服務(wù)信息系統(tǒng)提供的數(shù)據(jù)，共包含581 012條記錄，每一條記錄是一塊大小為30×30平方英尺土地上的地理數(shù)據(jù)，每條記錄包含54條屬性。其中連續(xù)屬性10維，標(biāo)稱屬性44維，數(shù)據(jù)集中總共包含7類森林覆蓋類型。本文算法選用其中的10維連續(xù)屬性。為了便于網(wǎng)格映射，先將所有數(shù)據(jù)規(guī)格化到[0，1]區(qū)間，以數(shù)據(jù)集中數(shù)據(jù)點(diǎn)的先后順序作為數(shù)據(jù)流的流入順序，依次加上時(shí)間標(biāo)簽，以模擬實(shí)時(shí)數(shù)據(jù)流的特性。

采用文獻(xiàn)[11]中的聚類純度作為衡量算法性能的標(biāo)準(zhǔn)， 聚類純度定義為滑動(dòng)窗口內(nèi)聚類簇的平均純度：

purity=∑Ki=1（|Cdi|/|Ci|）/K×100%(4)

其中：K表示聚類簇的個(gè)數(shù)；|Cdi|表示第i個(gè)聚類簇中主體類別的數(shù)據(jù)點(diǎn)個(gè)數(shù)；|Ci|為第i個(gè)聚類簇中所有數(shù)據(jù)點(diǎn)的個(gè)數(shù)，純度的計(jì)算使用了數(shù)據(jù)點(diǎn)的類別信息。為了計(jì)算聚類純度，本文算法在內(nèi)存中維護(hù)一個(gè)長度為h的滑動(dòng)窗口，即[curTime-h+1，curTime]時(shí)間段內(nèi)的數(shù)據(jù)點(diǎn)。參數(shù)設(shè)置為len=0.25，λ=0.9，β=10 000，period=100。為了便于比較，CluStream算法相關(guān)參數(shù)的設(shè)置均采用文獻(xiàn)[9]中的默認(rèn)設(shè)置，PDStream算法在文獻(xiàn)[9]所使用的代表性時(shí)刻提出聚類請(qǐng)求。

首先將數(shù)據(jù)流速率設(shè)定為每個(gè)時(shí)間單位200個(gè)數(shù)據(jù)點(diǎn)，滑動(dòng)窗口長度h=1，聚類結(jié)果如圖6所示。在160、320、2 560單位時(shí)間，PDStream算法聚類純度均明顯好于CluStream算法；在640、1 280單位時(shí)間PDStream算法性能比CluStream算法略差。

在圖7顯示的結(jié)果中，數(shù)據(jù)流速率設(shè)置為每個(gè)時(shí)間單位100個(gè)數(shù)據(jù)點(diǎn)，滑動(dòng)窗口長度h=10。在200、400、800、1 600、3 200單位時(shí)間，PDStream算法性能均好于CluStream算法。



由于PDStream算法的主要操作(數(shù)據(jù)點(diǎn)的處理、網(wǎng)格特征向量更新、聚類、剪枝等)都是在維度樹上進(jìn)行的，衡量算法時(shí)空復(fù)雜度的一個(gè)重要指標(biāo)就是維度樹中的網(wǎng)格的個(gè)數(shù)，網(wǎng)格數(shù)越少，算法運(yùn)行耗時(shí)越少，占用的內(nèi)存空間也越小。為了測(cè)試本文提出的周期性剪枝策略對(duì)算法執(zhí)行效率的影響，筆者進(jìn)行了相關(guān)實(shí)驗(yàn)。

首先在二維人工數(shù)據(jù)集的不同時(shí)刻提出聚類請(qǐng)求，參數(shù)設(shè)置與本文第一個(gè)實(shí)驗(yàn)相同。圖8顯示了剪枝前后維度樹中的網(wǎng)格個(gè)數(shù)，然后在ForestCoverType數(shù)據(jù)集的不同時(shí)刻進(jìn)行聚類。參數(shù)設(shè)置為speed=100， len=0.25， λ=0.9， β=10 000， period=100，剪枝前后維度樹中的網(wǎng)格數(shù)的變化如圖9所示。



實(shí)驗(yàn)表明，本文提出的周期性剪枝策略可以在幾乎不影響聚類結(jié)果的前提下，除去維度樹中離群點(diǎn)所對(duì)應(yīng)的大部分稀疏網(wǎng)格，從而為數(shù)據(jù)流系統(tǒng)節(jié)省了寶貴的運(yùn)行時(shí)間以及內(nèi)存空間。通過圖8與9的對(duì)比還可以發(fā)現(xiàn)，數(shù)據(jù)流維度越高，該剪枝策略的效果越明顯，說明本文算法適用于高維度、高流速的實(shí)時(shí)數(shù)據(jù)流。

5 結(jié)束語

本文研究實(shí)時(shí)數(shù)據(jù)流的在線聚類問題，在衰減窗口模型的基礎(chǔ)上提出了PDStream算法。該算法能實(shí)時(shí)地響應(yīng)用戶的在線聚類請(qǐng)求，并能發(fā)現(xiàn)任意形狀分布的聚類。實(shí)驗(yàn)結(jié)果表明，本文的算法是可行有效的，能夠滿足實(shí)時(shí)數(shù)據(jù)流環(huán)境對(duì)聚類算法的處理速度、內(nèi)存空間的要求。周期性剪枝策略有可能將一部分潛在密集網(wǎng)格識(shí)別為孤立點(diǎn)，尋找精確的識(shí)別真實(shí)離群點(diǎn)和潛在密集網(wǎng)格的方法以及提高剪枝周期參數(shù)的自適應(yīng)能力是進(jìn)一步深入研究的方向。

參考文獻(xiàn):

[1]GOLAB L. Issues in data stream management[J]. ACM SIGMOD Record， 2003， 32(2): 5-14.

[2]BABCOCK B， BABU S， DATAR M， et al. Models and issues in data stream systems[C]//Proc of the 21st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems.New York: ACM Press， 2002: 1-16.

[3]GABER M M， ZASLAVSKY A， KRISHNASWAMY S. Mining data streams: a review[J]. ACM SIGMOD Record， 2005， 34 (2): 18-26.

[4]MUTHUKRISHNAN S. Data streams: algorithms and applications [M]. Hanover: Now Publishers Inc， 2005.

[5]GUHA S， MEYERSON A， MISHRA N， et al. Clustering data streams[C]//Proc of the 41st Annual Symposium on Foundations of Computer Science. Washington DC: IEEE Computer Society， 2000: 359-366.

[6]OCALLAGHAN L. Streaming data algorithms for high quality clustering[C]//Proc of the 18th International Conference on Data Enginee-ring. Massachusetts: IEEE Computer Society， 2002: 685-694.

[7]AGGARWAL C C， HAN Jia-wei， WANG Jian-yong， et al. A framework for clustering evolving data streams[C]//Proc of the 29th VLDB Conference.Berlin: [s.n.]， 2003: 81-92.

[8]孫煥良.流數(shù)據(jù)聚類分析與孤立點(diǎn)檢測(cè)算法的研究[D].沈陽：東北大學(xué)，2005.

[9]AGGARWAL C C， HAN Jia-wei， WANG Jian-yong， et al. A framework for projected clustering of high dimensional data streams[C]//Proc of the 30th VLDB Conference. Toronto: [s.n.]， 2004:852-863.

[10]CHEN Yi-xi， TU Li. Density-based clustering for real-time stream data[C]//Proc of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. California: [s.n.]， 2007: 133-142.

[11]CAO Feng， ESTER M， QIAN Wei-ning， et al. Density-based clustering over an evolving data stream with noise[C]//Proc of SIAM Conference on Data Mining. 2006.