一種新的基于網格的聚類算法

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

關鍵詞：聚類； 網格； 數據挖掘

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

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

數據挖掘是指從大型數據庫或數據倉庫中提取隱含的、未知的、非平凡的及有潛在應用價值的信息或模式。它是數據庫研究中的一個很有應用價值的領域，融合了數據庫、人工智能、機器學習、統計學等多個領域的理論和技術。數據挖掘工具能夠對將來的趨勢和行為進行預測，從而很好地支持人們的決策。其常用方法有聚類分析、人工神經網絡、遺傳算法等。其中聚類分析是數據挖掘中廣為研究的課題之一[1]。

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

1相關研究

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

2本文工作

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

3一種新的基于網格的聚類算法

3．1相關概念

e）刪除最后聚類結果中聚類包含數據單元數目少于給定參數的聚類。

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

3．3時間復雜度

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

3．4算法實驗

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

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

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

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

4結束語

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

參考文獻：

[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－hong， 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.

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