一種基于網格的增量聚類算法

摘 要：分析了現有基于網格的聚類算法，該算法具有高效且可以處理高維數據的特點，但傳統網格聚類算法的聚類質量受網格劃分的粒度影響較大。為此，提出了一種基于網格的增量聚類算法IGrid。IGrid算法具有傳統網格聚類算法的高效性，且通過維度半徑對網格空間進行了動態增量劃分以提高聚類的質量。在真實數據集與仿真數據集上的實驗結果表明，IGrid算法在聚類準確度以及效率上要高于傳統的網格聚類算法。

關鍵詞：增量;聚類;網格;數據挖掘

中圖分類號：TP311文獻標志碼：A

文章編號：1001-3695(2009)06-2038-03

doi:10.3969/j.issn.1001-3695.2009.06.011

Incremental clustering algorithm based on grid

YIN Gui-sheng，YU Xiang，NING Hui

(Dept. of Computer Science Technology， Harbin Engineering University， Harbin 150001， China)

Abstract:This paper analyzed the existing clustering algorithms based on grid，and the clustering algorithms based on grid had the advantages of dealing with high dimensional data and high efficiency. However， traditional algorithms based on grid were influenced greatly by the granularity of grid partition.It proposed an incremental clustering algorithm based on grid， which was called IGrid.IGrid had the advantage of high efficiency of traditional clustering algorithms based on grid， and it also partitioned the grid space by dimensional radius in a dynamic and incremental manner to improve the quality of clustering.The experiments on real datasets and synthetic datasets show that IGrid has better performance than traditional clustering algorithms based on grid in both speed and accuracy.

Key words:incremental; clustering; grid; data mining

0 引言

聚類分析是數據挖掘領域中的一項重要的研究課題。聚類分析可以作為一個獨立的工具來獲得數據分布的情況，此外，也可以將聚類分析作為其他算法的預處理步驟。傳統的基于網格的聚類算法的主要優點是處理速度快，其處理時間獨立于數據對象的數目， 僅依賴于量化空間中每一維上的單元數目

^[1，2]。

基于網格的聚類算法中，有代表性的包括：STING，它利用了存儲在網格單元中的統計信息；WaveCluster，它用一種小波轉換方法來聚類數據對象；CLIQUE，它是在高維數據空間中基于網格和密度的聚類方法。

STING是一種基于網格的多分辨率聚類技術，它將空間區域劃分為矩形單元。針對不同級別的分辨率，通常存在多個級別的矩形單元，這些單元形成了一個層次結構，并對每個網格單元屬性的統計信息預先進行了計算和存儲。STING的效率很高，對于n個數據對象，在層次結構建立后，形成m個最低層網格單元，其產生聚類的時間復雜度為O(n)。其查詢處理時間是O(m)。STING聚類的質量取決于網格結構最低層的粒度。如果網格結構最低層的粒度較細，則處理的代價會增加，在數據集的維度較高時尤為明顯；如果網格結構最低層的粒度太粗，則會降低聚類的質量。

WaveCluster是一種多分辨率的聚類算法，它首先通過在數據空間上強加一個多維網格結構來匯總數據；然后采用小波變換來變換原特征空間，在變換后的空間中找到密集區域。WaveCluster能有效處理大數據集合，成功地處理孤立點，對于輸入的順序不敏感，且不要求指定領域半徑等參數。

CLIQUE聚類算法綜合了基于密度和基于網格的聚類方法，可有效地對大型數據庫中的高維數據進行聚類。該算法首先給定一個多維數據點集，對空間中的稀疏和稠密的單元進行區分，以發現數據集合的全局分布模式。如果一個單元中的數據點數超過了某輸入參數，則該單元是密集的。CLIQUE對元組的輸入順序不敏感，當數據維數增加時具有良好的可伸縮性。在應用于全空間聚類時會生成過多單元，性能會相應降低；且由于方法的簡化，聚類結果的精度也會受到影響。

傳統網格聚類算法的聚類質量受網格劃分的粒度影響較大，網格劃分粒度較大，則會降低聚類的質量；網格劃分粒度較小，則會降低聚類的效率。本文提出了一種基于網格的增量聚類算法IGrid。IGrid算法具有傳統網格聚類算法的高效性，且通過維度半徑向量對網格空間進行動態增量劃分以提高聚類的質量。在此基礎上，設計了一種剪枝優化策略，以進一步提高IGrid算法的效率。

1 問題定義

1.1 基本概念

對于d維數據空間S上的數據集D={x1，x2，…，xn}，下標n表示集合中數據點的個數，任一數據點xi={xi1，xi2，…，xij，…，xid}。其中：j=1，2，…，d；xij表示第i個數據點的第j維的值。定義1 δ鄰域。數據集D中的數據點xi的第j維值為xij，xi的第j維的δ鄰域就是以數據點xi為中心在第j維上的一個劃分[xij-δ，xij+δ]。其中：δ為該維的維度半徑。

定義2 δ鄰域向量。由d維數據空間中各維的維度半徑δi組成的向量δ={δ1，δ2，…，δd}稱為δ鄰域向量。其中：δi為第i維的維度半徑。

定義3 網格體積。V=dj=1spanj，即網格在所有d維空間的區間長度spanj的乘積。

定義4 網格相對密度。網格中所包含的數據點的個數n與網格體積V的比值，即n/V為網格的相對密度。

定義5 網格公共面。兩個d維網格g1和g2，當存在g1與g2有d-1維是相同的，且在不相同的第d維上，g1和g2的劃分區間互相鄰接，則稱網格g1和g2有一個網格公共面。

定義6 網格相連。當兩個網格g1和g2有一個網格公共面或存在另一個網格g3，使得g1與g3之間有一個網格公共面，g2與g3之間有一個網格公共面，則網格g1與g2是相連的。借鑒CLIQUE算法對于類的定義^[3]，一個微聚類就是相連的網格相對密度大于某一閾值ρ0的網格組成的最大集。

1.2 網格的動態劃分及增量調整

數據集D={x1，x2，…，xn}中的每個數據點xi={xi1，xi2，…，xid}在其對應的每一維上進行網格空間劃分。對數據點xi在第j維上的值ij，如果xij不屬于第j維上任何已存在的δ鄰域劃分，那么由第j維的維度半徑δj可得到劃分[xij-δj，xij+δj]，稱xij-δj為該劃分的前部，xij+δj為該劃分的后部。若前部xij-δj與該維上某已存在的劃分(設為[xkj-δj，

xkj+δj])有交集，則將劃分[xij-δj，xij+δj]調整為(xkj+δj，xij+δj]。同理，若后部xij+δj與該維上某已存在的劃分(設為[xlj-δj，xlj+δj])有交集，則將劃分[xij-δj，xij+δj]調整為[xij-δj，xij-δj)。

2 IGrid算法

IGrid算法分為兩步：a)對數據集中的數據點進行訪問，并通過維度半徑動態增量式地逐步形成網格結構；b)利用網格聚類法進行聚類。IGrid算法還可對現有數據集進行增量調整。對于新增的數據集，只需順序訪問其中的數據點，動態更新網格結構后進行聚類即可。

IGrid算法對于每一網格，使用一個六元組(CF  1，CF  2，T2，T，n，V)作為網格特征值來表示該網格的統計信息，可以根據需要對該網格特征值進行調整。其中：CF 1和CF 2分別對應一個d維向量，對于每一維，CF 1與CF 2分別對應網格中數據點在各維上的算術和與平方和組成的向量；T與T2表示網格中數據點到達時間的和與平方和；n表示網格中數據點的個數；V表示網格體積。由此六元組可以方便地表示網格的統計信息，例如網格的均值為一個d維向量，定義為CF 1/n；網格的相對密度為n/V。

2.1 網格結構形成

對數據集D={x1，x2，…，xn}中的每個數據點xi={xi1，xi2，…，xid}進行依次訪問，按照給定的δ鄰域向量，建立網格結構。其中δ鄰域向量可以由經驗獲得，也可以通過取樣法來確定。具體如下：

算法1

輸入：數據集D={x1，x2，…，xn}，δ鄰域向量{δ1，δ2，…，δd}

輸出：網格結構G={G1，G2，…，Gd}

if xij不屬于第j維的某已存在的劃分

{計算出劃分P=[xij-δj，xij+δj];

if劃分P與某已存在的劃分相交

if劃分P與Q的后部相交//設劃分Q為[xkj-δj，xkj+δj]

調整P為P=[xkj+δj，xij+δj];

else if劃分P與Q的前部相交

調整P為P=[xij-δj，xkj-δj];

else//即P與劃分Q和L均相交，設劃分L為[xlj-δj，xlj+δj]

調整P為P=[xkj+δj，xlj-δj]或P=[xlj+δj，xkj-δj];

Gj=Gj∪P;

更新網格特征值;}

M=M-xi;

end while

end

算法1中通過δ鄰域向量對數據空間S進行動態劃分，在一定程度上限制了網格數量。但是由于網格體積大小存在差異，引入網格相對密度來判斷一個網格是否大于閾值ρ0，進而對網格結構進行剪枝。

2.2 網格聚類過程

對算法1中所生成的網格結構進行聚類，一個聚類就是相連的網格相對密度大于閾值ρ0的網格組成的最大集。聚類結果表示為k個生成的聚類集合C={C1，C2，…，Ck}。具體如下：

輸入：網格結構G={G1，G2，…，Gd}，相對密度閾值ρ0

輸出：聚類結果C={C1，C2，…，Ck}

G′=G；

cno=0;//cno為聚類數目

while G′≠

{Temp_G=;

從G′中取g;//g表示一個網格

if(g.n/g.V)＞ρ0

{cno++;

Temp_G=Temp_G∪g;

G′=G′-g;

for each g′ in G′

if (g′.n/g′.V)＞ρ0 and g′與Temp_G中某網格相連

{Temp_G=Temp_G∪g′;

G′=G′-g′;

更新Temp_G的統計信息;}

}

Ccno=Temp_G;//Ccno為第cno個聚類

}

end while

end

在進行聚類過程開始，可以對網格按其相對密度由大到小進行排序，當某網格相對密度小于閾值ρ0時，則無須考慮剩余的網格。當ρ0=0時，則表示對所有網格進行聚類。

2.3 復雜性分析

基于網格的增量聚類算法IGrid的計算花費主要由兩部分組成：a)在各維度上進行劃分，并確定每個數據點所屬的網格，以形成網格結構。這部分的計算量不大于O(n)，其中n為數據點的個數。b)判斷網格之間是否相連，對網格結構進行聚類。這部分的計算量不會大于通常的網格聚類算法的O(n)。所以，基于網格的增量聚類算法總的計算復雜度不會超過O(n+n)，即O(n)。不同于傳統的網格聚類算法，IGrid算法在網格結構形成后，可以增量地更新，引入了新的動態數據空間劃分方法，在一定程度上降低了網格劃分粒度對聚類質量的影響。在增量聚類時，無須對網格空間進行重新劃分，有效減少了計算量。

3 實驗分析

實驗中的算法采用C++語言編寫，硬件環境為Pentium 4 2.0 GHz CPU、主存為512 MB、硬盤為80 GB，操作系統為Windows XP。

實驗中的測試數據集來自UCI的wine recognition數據集。該數據集通過對化學屬性分析來對葡萄酒進行鑒別。該數據集中的每個數據點共13個連續屬性，不存在值缺失的情況。仿真數據集中每個數據點有8個連續屬性，不存在值缺失的情況。在實驗中，IGrid算法中各維的維度半徑通過取樣法來確定。對STING算法，每一維的等分劃分間隔以各相鄰數據點之間的平均距離為依據來確定。

3.1 聚類質量

實驗1中，使用IGrid算法對wine recognition數據集進行聚類。如圖1所示，wine recognition數據集中178個實例分為三類，即C1:59、C2:71和C3:48。IGrid算法對wine recognition數據集的聚類結果為C1:52、C2:66和C3:42。

IGrid算法的聚類準確度如表1所示。在算法執行過程中，網格結構逐漸形成，IGrid算法逐漸趨于穩定，保持較高的聚類準確度，且對于孤立點也不敏感。

3.2 聚類速度

實驗2中，分別用IGrid與STING算法對仿真數據集進行聚類，如圖2所示。隨著仿真數據集中數據點數目的增多，算法所需要的聚類時間逐漸增加。在數據集中數據點數目相等的情況下，IGrid算法的運行時間要少于STING算法。

3.3 算法伸縮性

實驗3對仿真數據集取不同數目的維度進行聚類。隨著數據集中數據點維數的增加，IGrid算法所需要的運行時間呈線性增長。如圖3所示，IGrid算法對于數據空間維度具有良好的伸縮性。

4 結束語

本文提出了一種基于網格的增量聚類算法IGrid。該算法保持了傳統網格聚類算法高效的優點，動態地對數據空間進行劃分，具有線性的時間復雜性。在真實數據集與仿真數據集上的實驗結果也表明IGrid算法在聚類準確度以及效率上要高于傳統的網格聚類算法。

IGrid算法可以根據數據集中數據點不斷增加的情況，在已形成的網格結構基礎上，增量地對其進行調整，以實現增量聚類。在IGrid算法中，若維度半徑選取過小，會對算法效率有一定的影響；若維度半徑選取過大，容易出現一些極小的空間劃分，使得歸入其中的數據點數量很小，不滿足閾值要求，而在聚類過程中被忽略。如何有效地選取維度半徑，完善網格結構的動態形成，以提高聚類質量，是需要進一步研究的課題。

參考文獻：

［1］WANG Wei，YANG Jiong，MUNTZ R.STING:a statistical information grid approach to spatial data mining[C]//Proc of the 23rd Confe-rence on VLDB.Athens:[s.n.]，1997：186-195.

[2]SHEIKHOLESLAMI G，CHATTERJEE S，ZHANG Ai-dong.WaveCluster:a multi-resolution clustering approach for very large spatial databases[C]//Proc of the 24th Conference on VLDB.New York:[s.n.]，1998：428-439.

[3]AGRAWAL R，GEHRKE J，GUNOPULOS D，et al.Automatic subspace clustering of high dimensional data for data mining applications[C]//Proc of ACM SIGMOD Conference. Seattle，WA:[s.n.]，1998:94-105.

[4]CHEN Ning，CHEN An，ZHOU Long-xiang.An incremental grid density-based clustering algorithm[J].Journal of Software，2002，13(1): 1-7.

[5]ERTZ L，STEINBACH M，KUMAR V.Finding clusters of different sizes， shapes， and densities in noisy， high dimensional data[C]//Proc of the 3rd SIAM International Conference on Data Mining.San Francisco:[s.n.]，2003.

[6]SUN Huan-liang，BAO Yu-bin，ZHAO Fa-xin，et al.CD-Trees: an efficient index structure for outlier detection[C]//Proc of WAM’04.Dalian:[s.n.]，2004:600-609.

[7]YANG Dong-hua，LI Jian-zhong，ZHANG Wen-ping.Join operation based on data grid[J].Journal of Computer Research and Deve-lopment，2004，41(10):1848-1855.

[8]PILEVAR A H，SUKUMAR M.GCHL:a grid-clustering algorithm for high-dimensional very large spatial data bases[J].Pattern Recognition Letters，2005，26(7):999-1010.

[9]AGRAWAL R，GEHRKE J，GUNOPULOS D，et al.Automatic subspace clustering of high dimensional data[J].Data Mining and Knowledge Discovery Journal，2005，11(1)：5-33.

[10]FIOLET V，TOURSEL B.Distributed data mining[J].Scalable Computing: Practice and Experiences，2005，6(1):99-109.

[11]劉俊嶺，孫煥良，王大玲，等.一種優化的基于網格的聚類算法 [J].小型微型計算機系統，2006，27(10):1927-1930.

[12]PEREZ M S，SANCHEZ A，ROBLES V，et al.Design and implementation of a data mining grid-aware architecture[J].Future Generation Computing Systems，2007，23(1):42-47.