基于動態網格的數據流聚類分析
2008-12-31 00:00:00何勇劉青寶
計算機應用研究 2008年11期
(國防科學技術大學 信息系統與管理學院， 長沙 410073)
摘要：提出的增量式數據流聚類算法DGCDS結合網格和密度技術，能夠得到任意形狀的聚類，通過改進網格密度的計算方式，解決了現有網格算法中丟失數據空間影響信息的問題，并且實現了關鍵參數的自適應設置，減小了人工參數對聚類結果的影響。
關鍵詞：動態網格； 網格密度； 數據流聚類； 聚類參數
中圖分類號：TP391文獻標志碼：A
文章編號：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引言
隨著硬件技術的飛速發展，人們獲取數據的能力越來越高，獲取數據的領域越來越廣，數據形態也從靜止的數據轉為海量、源源不斷的數據流數據。比如通信領域的通話記錄數據流、網絡監控中的數據包流，金融領域和零售企業的交易數據流，以及近幾年發展起來的傳感器網絡等產生的大量數據流。
數據流一經提出就引起了研究者的廣泛關注。目前，數據流研究大致可分為兩個方面：數據流管理系統(data stream management system，DSMS)和數據流挖掘[1]。數據流聚類由于在網絡監控、銀行交易數據分析等方面的重要應用價值而成為數據流挖掘的一個重要研究方向，已提出多種一次性掃描聚類算法，如STREAM算法[2]、CluStream算法[3]和HPStream算法[4]，以及基于它們的一些衍生算法。但總的來說，現有數據流算法基本上都是對靜態數據集算法的改進。
1相關研究
數據流的特性要求算法必須是內存限制下的實時增量更新算法。第一個增量更新聚類算法是用于數據倉庫的IncrementalDBSCAN算法[5]，然而該算法僅適用于處理數據倉庫這種相對穩定的數據流，不能處理變化很快的數據流。同時為了得到任意形狀的聚類，要求獲得整個數據流的信息，這在內存有限的情況下是無法做到的。L.O'Callaghan等人[2]提出的STREAM算法采取分而治之(divide and conquer)的思想，將數據流劃分為多個段，算法對每段分別聚類。該算法在整個數據流上進行計算，每次都要積累一定數目的數據后才進行處理，是一個數據流上的靜態算法，因此不能反映出數據流的變化情況。Aggarwal等人[3]提出的CluStream算法將數據流聚類分為在線聚集和離線分析兩部分。在線過程對數據流進行初級聚類；離線過程根據用戶需求對在線得到的初級聚類進行分析。在此基礎上，Aggarwal等人[4]在2004年又提出了HPStream算法。該算法采用投影的方式解決數據流的高維聚類問題，動態地選擇使聚類體積最小的那些維與聚類關聯，實現了一個子空間的聚類算法，并使用衰減因子隨時間推移不斷衰減歷史數據，并在聚類數目過多時，刪除最早加入的聚類。CluStream和HPStream算法都采用了K-means思想，得到的聚類結果通常都是球形的，不能得到任意形狀的聚類。朱蔚恒等人[6]提出基于密度與空間的ACluStream聚類算法，通過引入有嚴格空間意義的聚類塊，在對數據流進行初步聚類的同時，盡量保留數據的空間特性，有效克服了CluStream算法不能支持任意形狀聚類的缺陷。但是它在處理不屬于已有聚類塊的新數據點時，使用一種類似拋硬幣的方法來猜測是否為新數據點創建一個新的聚類塊，誤差較大；而且它以絕對密度作為參考，在聚類結果中無法區分密度等級不同的簇[7]。
對于聚類分析任務，基于網格的聚類算法有很多理想的特性，如發現任意形狀或任意大小的簇、計算結果與數據輸入順序無關、計算時間與數據量無關等[8]。由于基于密度的聚類方法和基于網格的聚類方法有很好的互補性，大部分基于網格的方法都是以網格單元的密度屬性作為聚類依據的。WaveCluster[9]和CLIQUE[10]是網格聚類中的兩個典型算法。WaveCluster是一種多分辨率的聚類算法，它首先在數據空間上強加一個多維網格結構來匯總數據，然后采用一種小波變換來變換原始的特征空間，在變換后的特征空間中找到密集區域。WaveCluster在低維數據空間上表現出了良好的性能。CLIQUE算法主要考慮高維子空間聚類，對大型高維數據聚類非常有效，但數據的維數增加時它表現出了良好的擴展性，但由于方法的大大簡化，降低了聚類結果的精確性。與大部分基于網格的聚類算法一樣，它們在計算網格密度時將網格中數據點的個數直接轉換為網格的密度值，忽略了周圍數據空間對網格的影響，容易導致聚類邊界點的丟失。2005年王生生等人[11]提出擴展相鄰空間聚類算法來克服這一缺陷；2006年單世民[12]提出貢獻度的概念，通過計算網格獲取的貢獻度多少來計算網格單元的密度。本文在已有算法基礎上提出的基于動態網格的數據流聚類算法(dynamicgrid-based clustering over data streams，DGCDS)，改進了已有算法在密度計算、網格劃分和密度聚類方面存在的問題，并實現了關鍵參數的自動設置。
2基于動態網格的數據流聚類算法
DGCDS算法基本思路：首先積累一段時間的數據流，得到數據流上的一個樣本集，在樣本集上對數據流進行自下而上的網格劃分，進而形成初始聚類；對數據流上新來的數據進行判斷，根據不斷到來的數據點對網格進行動態合并，t時間后，對過去的數據按照參數進行逐步遺忘。本章分三步對算法進行描述：a)闡述了相關概念和網格劃分、網格密度和密度閾值的計算方法；b)闡述了一個針對靜態數據集的GCDS(grid-based clustering over dataset)算法，以在數據流樣本集上形成初始網格和初始聚類；c)在前兩步的基礎上闡述了一個完整的DGCDS算法。
21網格劃分
211基本概念
定義1d維數據集(A1，A2，…，Ad)是一個有界并且有序的定義域，S=A1×A2×…×Ad就是一個d維數據空間。X={X1，X2，…，Xn}表示S上的數據流在時間t內的一個點集。其中：Xi={Xi1，Xi2，…，Xid}(i=1，2，…，n)。為不失一般性，假定任意維區間都是一個半開半閉的區間[lj，hj)(j=1，2，…，d)，那么點集X可以表示為X=[l1，h1)×[l2，h2)×…×[ld，hd)。
定義2將數據空間的每一維分成長度相等，互不相交的區間，向各維的正方向延伸區間長度所形成的超矩形區域就是一個網格單元，記為grid(o)。
為了下一步的高效計算，本文設定每維被均勻劃分為k個區間，整個數據空間被分為kd個網格。其中第j維上網格邊長δj可以通過式（1）計算得到：
δj=(hj-lj)/k(1)
由于均勻劃分，數據空間可能存在沒有數據對象的空網格。為了節省內存空間，只保留非空網格單元。
為避免網格單元出現負數編號的情況，本文以每維的取值下限lj作為絕對參考點來建立空間坐標。用gridi(Vi1，Vi2，…，Vid，Id)表示網格的空間位置。其中：vij(vij-，vij+)表示第i個網格在第j維上的坐標區間；kj表示網格單元在第j維上以坐標原點為始的網格索引編號；Id表示網格的編號。
vij-=lj+(kj-1)δjvij+=lj+kj×δj
(2)
用grid(count，den，cen，flag，W)描述網格特征。其中：count表示網格單元中數據點的個數；den表示網格單元的密度； cen表示網格單元的質心；flag表示網格的類別；W(0＜w＜1)是網格密度衰減因子。
212網格密度的計算
大部分基于密度的網格算法都是將網格所包含的數據點個數直接轉換為網格單元的密度值。這種方法簡單易行，且比較有效，但是運用于聚類時，會丟失數據點對周圍空間的影響信息，從而導致同屬一類的點被分在不同的類中，這種影響在網格單元邊界上體現尤為突出。圖1體現了密度計算方式對聚類結果的影響。其中，(a)是一個原始數據集，它主要包含一個橢圓形的類；(b)是執行傳統網格劃分后得到的類，聚類邊界點大部分落于其他三個相鄰網格中而丟失。因此，需要設計一種方法來計算數據對周圍網格的影響，結合這些影響值計算網格單元的密度。
DENCLUE方法[13]是較早考慮數據對周圍空間影響的密度算法。它認為，每個數據對周圍空間都會產生一定的影響，這種影響可以通過定義一個影響函數來度量，而空間中某一位置（如一個網格單元）的密度就是相關數據點對該位置的影響函數值的疊加。王生生等人[11]提出的擴展相鄰空間聚類算法中采用了類似于影響函數的思想，它利用對初始網格單元的擴展來計算網格周圍數據的影響。單世民在文獻[12]中提出貢獻度的概念，通過計算網格得到的貢獻度的大小來確定網格的密度。這種算法充分考慮了數據點對周圍空間的影響，但是在得到一個精確的貢獻度值時需要經過復雜的運算，運用于數據流上顯然是不合適的。因此，本文改進單世民和王生生的算法，利用一個擴展空間來計算網格的密度。
為了簡便起見，本文在二維空間中對下面幾個概念進行定義。
定義3初始網格單元。經過初始階段劃分得到的網格單元，如圖2(a)中編號為(2，2)的網格單元。
定義4擴展網格單元。對初始網格單元進行邊長擴展（經過反復實驗，本文將擴展長度定為δj/4）后得到的網格單元，如圖2(b)中的大網格單元。
定義5擴展區域。擴展網格單元中除去初始網格單元的區域，如圖2(c)中灰色區域。
定義6相似度。兩個對象之間的相似程度的數值度量，常在[0，1]上取值。
在進行網格密度計算時，將初始網格單元中每個數據點記為1，擴展區域內點對網格的影響度inf(0＜infi＜1)用數據點與網格質心的相似度（鄰近程度）來度量。相似度越大，inf值越大，該數據點對網格影響越大；相似度越小，inf值越小，該數據點對網格的影響也越小。如果出現擴展區域數據點與初始網格單元質心相似度為0或者為負數的情況，則認為數據點對網格單元的影響為0。這樣就充分考慮了網格周圍點的影響，而且計算簡便。
網格密度計算過程描述如下：
a)劃分網格，將數據映射到相應的網格單元中；
b)依次掃描每個網格單元，記錄下非空網格單元個數K和各非空網格單元中數據的個數count;
c)計算網格單元的質心cen
cen=∑Xij∈grid Xij/count(3)
d)擴展網格單元，按式(4)計算擴展區域內的數據對網格單元的影響值
inf=1-∑di=1(Xi-Ceni)2/δj(4)
e)計算網格單元密度
den=count+∑nj=1infi(5)
其中：n表示擴展區域中數據點的個數;infj表示擴展區域中第j個數據點對網格的影響值。
213網格密度閾值
根據數據分布特點，具有相似屬性的一類數據往往會形成一個密集的數據區域，而另一些數據形成稀疏的數據區域，并且彼此相隔。因此需要設定一個密度閾值參數MinPts來判斷網格的稠密性。MinPts的值對算法結果的好壞有很大影響，尤其是在數據流環境下，要求對后來數據要有預先判斷以此來設定MinPts。傳統的方法要求用戶在對聚類的性質有一定理解的基礎上來設置這個參數，很多情況下，對于用戶來說這樣的要求很苛刻。因此，本文借鑒平均密度的思路設計了一種簡單的方法自動計算MinPts。
a)依次掃描所有網格單元，找出最大密度值記為max(den);
b)計算所有非空網格單元的平均密度值ave(den)
ave(den)=∑Ki=1dengi/K(6)
其中：K是所有非空網格單元的個數；dengi表示第i個非空網格單元的密度值。
c)計算密度閾值
MinPts=(max(den)+ave(den))/2(7)
根據網格密度和MinPts值可以將網格劃分為三類：密度大于MinPts的網格單元是高密單元(dense cell)；密度小于MinPts且與高密網格單元相鄰的網格單元是稀疏單元(sparse cell)；密度小于MinPts且周圍都是稀疏單元的網格單元是孤立單元(outlier cell)。高密單元中的數據點是聚類的主要對象，稀疏單元中的數據點可能是聚類的邊界點也可能是孤立點，而孤立單元中的點可以認為是噪聲點。
22GCDS算法描述
通過上面的步驟，得到所有網格密度和類型，在此基礎上進行聚類分析。首先給出下列定義。
定義7網格相鄰。當且僅當兩個網格有一條公共邊或者一個公共頂點。用數學方式可描述為，若兩個網格單元編號中對應的維度索引號相減，結果不是1(-1)就是0，則說明這兩個網格單元相鄰。
定義8聚類核心單元。具有最大密度值的網格單元。數據的分布總是遵循一定的規律，即具有相似屬性的數據相對集中在一起。根據這個特性可以判斷，具有最大密度的網格單元就是聚類核心單元，本文中將聚類核心單元作為聚類的起始點。
GCDS算法具體過程描述如下：
a)網格劃分。按照2.1節中的方法在樣本數據空間上進行網格劃分，計算每個網格的密度，并根據密度閾值將網格標記為D-Grid（高密單元）或者S-Grid（稀疏單元）或者O-Grid（孤立單元），將相關信息記錄在網格中。
b)聚類。在a)生成的網格中，記錄了網格的所有相關信息，此時，所有的網格都已標志好類型。聚類時，首先搜索所有高密單元，找到聚類核心單元；然后從核心單元開始采用深度優先算法搜索所有相鄰的網格。若相鄰的兩個網格單元都是稠密的且距離（指兩個相鄰高密單元質心的距離）小于給定閾值τ，則連接成一個類，標記已聚類好的稠密網格單元；如果距離大于τ，說明這兩個單元分屬于不同的聚類，分別以這兩個單元為起點，按照先前的方法搜索相鄰網格單元；若是稠密單元和稀疏單元相鄰，則稀疏單元中的數據點可能是聚類的邊界點，利用邊界點處理技術對稀疏單元中的數據進行判斷。對未作標記的稠密網格單元重復以上步驟，直到找到所有的類。
閾值τ由網格單元內所有點到單元格質心的平均距離決定，可以通過式（8）計算得到
τ=∑counti=1(Xi-cen)2」1/2/count
(8)
23完整的DGCDS算法描述
數據流上的數據不斷到來，聚類結果也需要不斷更新。通常有兩種方法來維持一個不斷更新的聚類結果[14]：一種方法是在新的數據集上重新執行聚類過程，得到新的聚類結果，這種方法執行起來簡單，但是會增加時間復雜度，用在數據流上是不合適的；另一種方法是采用一種增量更新的算法，在原有聚類的基礎上進行更新，這種方法具有良好的收縮性和較高的執行效率。DGCDS就是在GCDS算法基礎上借鑒增量更新的思想，當有新數據到來時，只考慮新數據影響到的那部分網格和類。
具體過程形式化地描述如下：
a)劃分網格，形成初始聚類。先積累一定時間的數據流，然后運用GCDS算法，形成初始網格和初始聚類。
b)映射新加入的數據對象。
for新加入的數據對象Xi=(Xi1，Xi2，…，Xid)
if Xij[lj，hj)
if Xij屬于已存在的某個網格單元
then 直接定位其所在的網格，重新計算網格質心，相應網格的count=count+1，den=den+1；
if Xij不屬于已存在的某個網格單元
then 創建一個新網格以包含該數據；
if Xij[lj，hj)，
then 創建一個新網格以包含該數據。
如果數據落在相鄰網格的擴展區域內，用式(4)計算新數據對相鄰網格的影響值，通過式(5)更新網格的密度。
c)判斷數據對象的類型。新來的數據對象定位其所在的網格后，若其所在網格是稠密網格，則直接將其歸于網格所在的聚類中；若所在的網格是稀疏單元格，則計算它與最近一個聚類的相似度:
sim=1-∑di=1(Xi-Ci)2/δj(9)
如果sim大于相似度閾值ε，說明數據點是聚類的邊界點；否則認為數據點是一個孤立點或者噪聲點。
d)網格的合并。隨著數據的不斷流入，新增的網格會越來越多，在內存空間有限的條件下，必須按照一定的原則對網格單元進行合并，以節省空間消耗。合并的原則是：相鄰的兩個高密單元，若密度相近且距離（同GCDS算法中距離的意義一致）小于τ，則合并。設任意兩個相鄰的高密單元D-Gridi和D-Gridj，用Nij表示單元格D-Gridi和D-Gridj密度的近似程度
Nij=(min (dengi，dengj)/(max(dengi，dengj))(10)
若Nij接近1且距離小于τ，則合并這兩個相鄰的高密單元；否則，不合并。
e)網格的衰減。對于數據流數據而言，當前和最近的數據才是人們關心的，因此，每過一定時間就對所有單元格進行衰減。引入衰減因子w(0＜w＜1)對網格密度進行更新，den=den×w。若den＜ξ(ξ是網格消除閾值），則從內存中刪除相應的網格。
在計算網格密度的過程中，由于考慮了相鄰網格內數據的影響，在步驟c)的計算中也考慮了邊界點的問題，此時聚類結果已經比較精確，如無特別要求，不需要專門進行邊界點檢測。
3算法分析
31時間復雜度分析
假設樣本數據集中數據對象個數為N1，整個數據流數長度為N。算法第一步網格劃分階段，首先要找出每一維上的最大最小值，其時間復雜度為O(dN1)；然后將數據映射到網格中去，時間復雜度同樣為O(dN1)；在計算網格密度時，需要對所有網格進行掃描，時間復雜度為O(kd)；在執行GCDS算法過程中復雜度為O(K)。由于K≤kd≤N1，步驟a)時間復雜度實際上為O(2dN1)。步驟b)映射新加入的數據對象和步驟c)判斷數據點的類型時間復雜度都為O(dN)。步驟d)和步驟e)時間復雜度均為O(K)，即DGCDS算法的時間復雜度為O(2dN1+dN+dN+K+K)。對于整個數據流來說，N遠遠大于樣本數據個數N1和非空網格單元個數K，因此，DGCDS算法時間復雜度無限接近O(dN)并且隨維度的增加而呈線性增加。
32算法評價
與現有網格算法相比，DGCDS算法存在以下幾方面的優點：
a)優化了網格密度計算方式。通過擴展網格單元考慮了網格單元周圍空間數據對網格的影響，雖然比直接將網格單元包含的數據個數轉換為網格密度的計算方法復雜，但是得到的聚類結果更加接近數據真實分布情況；而且與整個算法執行時間比較起來，在網格密度計算上增加的時間是微不足道的。
b)本算法是一個增量式的數據流聚類方法。當新數據到來時，算法只考慮新數據影響到的那部分網格，而不用重新執行一次聚類算法。因此，該方法具有良好的伸縮性，能滿足數據流聚類的要求。
c)實現了關鍵參數的自適應設置。在很多經典的網格計算方法中，由于采取全局一致的密度閾值參數MinPts，經常會出現高密度簇完全被相連的低密度簇所包含的情況，從而導致聚類結果難以分析。本文雖然也是采取全局一致的密度參數，但是MinPts值是在考慮整個數據分布特點的基礎上自動設置而不用人工指定，并且在數據流環境下，隨著網格密度的改變，MinPts也會作出相應改變。
4結束語
基于動態網格的數據流聚類算法DGCDS使用網格和密度相結合的技術，能夠得到任意形狀的聚類，通過對網格密度計算方式的改進，解決了現有網格算法中丟失數據空間影響信息的問題，使得聚類邊界更平滑，并且實現了關鍵參數的自適應設置，減少了人工參數對聚類結果的影響。如何進一步提高算法執行效率和精度以及對高維數據流的適應性是筆者下一步的研究方向。
參考文獻：
［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]朱蔚恒，印鑒，謝益煌.基于數據流的任意形狀聚類算法[J].軟件學報，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]孫玉芬，盧炎生.一種基于網格方法的高維數據流子空間聚類算法[J].計算機科學，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]王生生，劉大有，曹斌.一種高維空間數據的子空間聚類算法[J].計算機應用，2005，25(11):2615-2617.
[12]單世民.基于網格和密度的數據流聚類方法研究[D].大連：大連理工大學，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].小型微型計算機系統，2004，25(10)：1847-1849.
