一種新的基于網(wǎng)格的聚類算法

摘要：新的基于網(wǎng)格的聚類算法（CABG）利用網(wǎng)格處理技術對數(shù)據(jù)進行了預處理，能根據(jù)數(shù)據(jù)分布情況動態(tài)計算每個單元格的半徑，并成功地將網(wǎng)格預處理后所得單元格數(shù)據(jù)運用于其后的聚類分析中，從而簡化了算法所需的初始參數(shù)。實驗表明，CABG算法不僅具有DBSCAN算法準確挖掘各種形狀的聚類和很好的噪聲處理能力的優(yōu)點，而且具有較高聚類速度以及對初始參數(shù)較低的敏感度。

關鍵詞：聚類； 網(wǎng)格； 數(shù)據(jù)挖掘

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

文章編號：1001-3695(2008)05-1337-03

數(shù)據(jù)挖掘是指從大型數(shù)據(jù)庫或數(shù)據(jù)倉庫中提取隱含的、未知的、非平凡的及有潛在應用價值的信息或模式。它是數(shù)據(jù)庫研究中的一個很有應用價值的領域，融合了數(shù)據(jù)庫、人工智能、機器學習、統(tǒng)計學等多個領域的理論和技術。數(shù)據(jù)挖掘工具能夠?qū)淼内厔莺托袨檫M行預測，從而很好地支持人們的決策。其常用方法有聚類分析、人工神經(jīng)網(wǎng)絡、遺傳算法等。其中聚類分析是數(shù)據(jù)挖掘中廣為研究的課題之一[1]。

聚類分析就是從數(shù)據(jù)中尋找數(shù)據(jù)間的相似性，并依此對數(shù)據(jù)進行分類，使得不同類中的數(shù)據(jù)盡可能相異，而同一類中的數(shù)據(jù)盡可能相似，從而優(yōu)化大規(guī)模數(shù)據(jù)庫的查詢和發(fā)現(xiàn)數(shù)據(jù)中隱含的有用信息或知識。數(shù)據(jù)聚類在很多領域有著廣泛的應用，如模式識別、圖像處理和數(shù)據(jù)壓縮等。迄今為止，僅僅數(shù)據(jù)庫界的研究人員就已經(jīng)提出了不少數(shù)據(jù)聚類算法，比較著名的有CLARANS[2]、BIRCH[3]、DBSCAN[4]和CLIQUE[5]等。這些算法都試圖從不同途徑實現(xiàn)對大規(guī)模數(shù)據(jù)庫的有效聚類，但總的來說，都沒有取得理想的效果。可以說，對于高維、大規(guī)模數(shù)據(jù)庫的高效聚類分析仍然是一個有待研究的開放問題。

1相關研究

基于網(wǎng)格的聚類算法由于易于增量實現(xiàn)和高維數(shù)據(jù)挖掘而被廣泛應用于聚類算法中。迄今為止，已經(jīng)有很多人提出了基于密度或網(wǎng)格的聚類算法，如CLIQUE、IGDCA[6]、CABDET[7]等。CLIQUE是一種基于網(wǎng)格和密度的聚類算法，它是一種更廣泛的子空間聚類方法，可以通過任意組合來產(chǎn)生子空間，再將數(shù)據(jù)投影到子空間中進行聚類，具有網(wǎng)格類算法效率高的優(yōu)點，并且可以處理高維數(shù)據(jù)。但是在劃分網(wǎng)格時沒有考慮數(shù)據(jù)的分布，從而導致了聚類質(zhì)量的降低。IGDCA是一種基于密度的增量式網(wǎng)格聚類算法。該算法通過將數(shù)據(jù)空間劃分成體積相等的若干單元，再對這些單元采用基于密度的聚類分析方法進行聚類，從而有效地提高聚類的效率，一定程度上減少了聚類所需的內(nèi)存和I/O開銷。但由于它是基于DBCSCAN算法的改進，用戶仍需輸入聚類初始參數(shù)。CABDET是一種基于構(gòu)建密度樹的聚類算法。該算法通過為每個聚類構(gòu)建一棵密度樹，采用動態(tài)參數(shù)，每次的拓展聚類都根據(jù)單元分布情況自動計算對應的半徑參數(shù)，減少了聚類對初始參數(shù)的敏感度，取得了較好的聚類效果。但是它不進行任何的預處理而直接對整個數(shù)據(jù)庫進行聚類操作，當數(shù)據(jù)量非常大時，就必須有大量內(nèi)存支持，I/O消耗也非常大。

2本文工作

本文受算法CLIQUE、IGDCA、CABDET、SDBSCAN[8]的啟發(fā)，提出了一種新的基于網(wǎng)格的聚類算法CABG（clustering algorithm based on grid）。算法首先對原始數(shù)據(jù)進行了網(wǎng)格預先處理，將初始數(shù)據(jù)集分割成等同的若干數(shù)據(jù)單元，再對這些數(shù)據(jù)單元采用基于密度的聚類分析方法進行聚類分析。算法充分利用了聚類分析中各階段之間的數(shù)據(jù)關系，將前階段數(shù)據(jù)預處理中所得的數(shù)據(jù)融入后階段的聚類分析中，從而減少了后階段的聚類分析算法對初始參數(shù)的要求，降低了算法對初始參數(shù)的敏感度。

3一種新的基于網(wǎng)格的聚類算法

3．1相關概念

e）刪除最后聚類結(jié)果中聚類包含數(shù)據(jù)單元數(shù)目少于給定參數(shù)的聚類。

算法步驟a)對數(shù)據(jù)進行了網(wǎng)格預處理，從而在很大程度上減少了后期聚類的計算量，提高了算法中總體的效率，同時也減少了計算機的內(nèi)存和I/O開銷。b)c)充分利用了網(wǎng)格預處理操作后所得的信息，計算出單元格的平均密度和各個單元格的半徑，從而避免了基于密度的聚類算法中要求用戶輸入的參數(shù)，而僅需用戶輸入相對較為容易確定的網(wǎng)格半徑，減少了算法對輸入?yún)?shù)的敏感度。d)采用了基于密度的聚類分析方法，保證了算法能夠有效地挖掘出準確的各種形狀的聚類，所得聚類結(jié)果難免存在一些不滿足要求的，但e)解決了此問題。

3．3時間復雜度

算法通過一次掃描所有數(shù)據(jù)，采用了網(wǎng)格技術進行預處理操作，利用數(shù)據(jù)單元格代替數(shù)據(jù)點，在很大程度上減少了對數(shù)據(jù)查詢統(tǒng)計的次數(shù)。算法對數(shù)據(jù)單元格進行聚類，采用了基于密度的聚類算法的思想，并且算法對數(shù)據(jù)索引采用了SR－TREE方法，有效地減少了時間復雜度。假設具有n個數(shù)據(jù)的數(shù)據(jù)集經(jīng)過網(wǎng)格化預處理后，存在數(shù)據(jù)單元格數(shù)目為m，則算法時間復雜為O(n)+O(m)+O(m×log m)，可簡化為O(m×log m)。可以看出，算法總體時間復雜度只與預處理后的數(shù)據(jù)單元格的個數(shù)有關。

3．4算法實驗

這里選用國際上通用的數(shù)據(jù)集banana[9]對算法進行實驗操作。Banana數(shù)據(jù)集總共有數(shù)據(jù)4 900條。首先對數(shù)據(jù)集進行預處理，對所有數(shù)據(jù)增加5擴大50倍，即（x+5）×50（其中x表示數(shù)據(jù)集中任意一個數(shù)據(jù)）；然后對所得數(shù)據(jù)集進行實驗。本實驗在Windows 2000操作系統(tǒng)下進行，計算機配置為CPU P4 2．93 GHz、內(nèi)存512 MB。計算得到如圖1~4所示的結(jié)果。

同時筆者做上述實驗中也采用了DBSCAN算法和蟻群算法對等同的數(shù)據(jù)集進行聚類分析。實驗結(jié)果表明，在對大規(guī)模的數(shù)據(jù)進行處理上，CABG算法在內(nèi)存和I/O花銷上明顯比DBSCAN算法和蟻群算法少。

為了驗證本算法的準確性，筆者分別采用CABG和DBSCAN算法對數(shù)據(jù)集DB1和DB2進行聚類分析，然后比較最終結(jié)果。其中圖5、6為CABG算法的聚類結(jié)果；圖7、8為DBSCAN算法的聚類效果。

上述實驗表明，對于等同的數(shù)據(jù)集， CABG具有與DBSCAN算法一樣的準確率，能夠有效準確地挖掘出各種形狀的聚類結(jié)果，并且在噪聲處理上也同樣具有很好的處理能力。

4結(jié)束語

本文提出了采用動態(tài)的方法對聚類半徑進行賦值，并提出了基于密度的網(wǎng)格聚類算法CABG。該算法不僅保持了基于密度的聚類算法可以發(fā)現(xiàn)任意形狀的聚類和對噪聲數(shù)據(jù)不敏感的優(yōu)點，而且具有基于網(wǎng)格的聚類算法效率高的優(yōu)點，可以有效地處理高維的、增量式的數(shù)據(jù)集。上述的理論分析和實驗結(jié)果也證明了這點。筆者將會進一步地探討如何將CABG算法應用到增量式的數(shù)據(jù)空間中，以獲取更好的研究成果。

參考文獻：

[1]CHEN M S， HAN Jia－wei， YU P S. Data mining: an overview from a database perspective[J]. IEEE Trans on Knwledge and Data Eng， 1996，8(6):866-883.

[2]NG R T， HAN J. Efficient and effective clustering methods for spatial data mining[C]//Proc of the 20th VLDB Conference. Chile， Santiago:[s.n.]， 1994:144－155.

[3]ZHANG T， RAMAKRISHNAN R， LIVNY M. An efficient data clustering method for very large databases[C]//Proc of ACM SIGMOD International Conference on Management of Data. New York: ACM Press， 1996:103－114.

[4]ESTER M， KRIEGEL H P， SANDER J. A density－based algorithm for discovering clusters in large spatial databases with noise[C]//Proc of the 2nd International Conference on Knowledge Discovering in Databases and Data Mining. Oregon:[s.n.]， 1996:122－128.

[5]AGRAWAL R， GEHRKE J， GUNOPOLOS D. Automatic subspace clustering of high dimensional data for data mining applications[C]//Proc of ACM SIGMOD International Conference on Management of Data. New York: ACM Press， 1998:94－105.

[6]CHEN Ning， CHEN An－zhou， LONG Xiang. An incremental grid density－basedclustering algorithm[J].Journal of Software， 2002，13(1):1-7.

[7]DAI Wei－di， HOU Yue－xian， HE Pi－lian. A clustering algorithm based on building a density－tree[C]//Proc of the 4th International Conferenceon Machine Learning and Cybernetics. Guangzhou:[s.n.]， 2005:18-21.

[8]GUAN Ji－h(huán)ong， ZHOU Shui－geng， BIAN Fu－ling. Scaling up the DBSCAN algorithm for clustering large spatial databases basedon sampling technique[J].Wuhan University Journal of Natural Sciences， 2001，6(1-2):467-473.

[9]KEERTHI S S. Benchmark， datasets[EB/OL].http://guppy.mpe.nus.edu.sg/－mpessk.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”