基于網格的聚類方法研究

摘要:已有的聚類算法對于發現任意形狀的聚類和處理離群點效果不理想，分析了現有基于網格的聚類算法。使用網格方法的數據分析方法將空間劃分為由(超)矩形網格單元組成的網格，然后在網格單元上進行聚類。最后，總結全文并提出基于網格的聚類需要進一步研究的方向。

關鍵詞:數據挖掘;網格;聚類

1 引言

數據挖掘是指從大型數據庫或數據倉庫中提取隱含的、未知的及有應用價值的信息或模式。它是數據庫研究中的一個很有應用價值的領域，融合了數據庫、機器學習、統計學等多個領域的理論和技術[1]。

聚類分析是數據挖掘中廣為研究的課題之一，是從數據中尋找數據間的相似性，并依此對數據進行分類，從而發現數據中隱含的有用信息或知識。目前已經提出了不少數據聚類算法，其中比較著名的有CLARANS[2]、BIRCH[3]、DBSCAN[4]和CLIQUE[5]等。但對于高維、大規模數據庫的高效聚類分析仍然是一個有待研究的開放問題。

網格方法是空間數據處理中常用的將空間數據離散化的方法。基于網格的聚類算法由于易于增量實現和進行高維數據處理而被廣泛應用于聚類算法中。研究人員已經提出了很多基于網格的聚類算法，包括STING[6]，它利用了存儲在網格單元中的統計信息;WaveCluster[7]它用一種小波轉換方法來聚類數據對象;CLIQUE在高維數據空間中基于網格和密度的聚類方法等。

本文對已有的基于網格的聚類算法進行了研究，從網格的表示，劃分網格單元的方法，到統計網格內信息，搜索近鄰網格單元，聚類超過指定闕值的網格單元的各個步驟進行了分析，最后對基于網格方法聚類的研究方向做了展望。

2 網格的定義與劃分

網格的基本概念，設A1， A2，…， Ar 是數據集O={O1， O2，…， On }中數據對象的r 個屬性的有界定義域，那W=A1 ×A2 ×…×Ar 就是一個r 維空間， 將A1，A2 ，…， Ar 看成是W 的維( 屬性、字段)，則對于一個包含n 個數據點的r 維空間中的數據集O={O1 ， O2 ，…， On }，其中Oi ={Oi1 ， Oi2 ，…， Oir }( i=1， 2，…， n) ， Oi 的第j 個分量Oij ∈Aj 。將W的每一維M等分，即把W分割成個網格單元。

基于網格聚類算法的第一步是劃分網格結構，按搜索子空間的策略不同， 主要有基于由底向上網格劃分方法的算法和基于自頂向下網格劃分方法的算法。

2.1 由底向上的劃分方法

由底向上的網格劃分方法按照用戶輸入的劃分參數(即每維段數ki，1 ≤i ≤d)，將數據空間均勻劃分為相等大小的網格單元，假設落入同一網格單元內的所有數據點都屬于同一個簇，每個網格單元保存落入其內數據的統計信息，比如數據點個數，數據點之和。包含一定數目數據點的網格單元被稱為高密度網格單元。

WaveCluster與CLIQUE是采用由底向上網格劃分方法的代表性算法。WaveCluster處理低維空間數據，它的性能超越了BIRCH、CLARANS，與DBSCAN等優秀的聚類算法[15]。CLIQUE考慮了高維子空間聚類，但它的時間復雜度較高，需要用戶指定全局密度閾值。算法MAFIA[8]對CLIQUE進行了改進，為了減少聚類算法需要處理的網格單元數目，MAFIA將均勻劃分網格中每一維上數據分布密度相似的相鄰段合并，由此得到一個不均勻劃分的網格。這個網格在數據分布較均勻的區域劃分粒度大，在數據分布不均勻的區域劃分粒度小，這種不均勻劃分網格的方法能夠提高聚類的質量，被后續的許多算法所采用。

采用由底向上的網格劃分方法的優點在于，它能通過對數據的一遍掃描，將數據壓縮到一個網格數據結構內，并基于這個網格數據結構，發現任意形狀的簇。此外，如果網格單元的粒度較小(即體積較小)，那么得到的聚簇的精度較高，但是算法的計算復雜度較大。此外，由底向上的網格方法存在不適合處理高維數據的問題。在高維空間，數據的分布是非常稀疏的，網格方法失去其壓縮作用，而且屬于同一個簇的高密度網格單元也可能不相連，這使聚類算法不能發現合理數目的簇。

2.2 自頂向下的劃分方法

自頂向下的網格劃分方法采取分治的策略(divide and conquer principle)，對數據空間進行遞歸劃分，使問題的規模不斷減小。首先將原數據空間劃分為幾個較大的區域。對于每個得到的區域，劃分過程反復執行，直到每個區域包含屬于同一個簇的數據點，那么這些區域就是最終的網格單元。基于自頂向下網格方法的聚類算法直接將高密度網格單元識別為一個簇，或是將相連的高密度網格單元識別為簇。

OptiGrid[9]與CLTree[10]是兩個典型的基于自頂向下網格劃分方法的聚類算法。其中， OptiGrid則是用空間數據分布的密度信息來選擇最優劃分。通過一個密度函數來決定切割平面，可以將數據空間劃分為規則的或不規則單元，與傳統的等間距的劃分相比，可以用此來解決高維聚類的問題。而CLTree用劃分后的信息增益來選取最優劃分。

自頂向下劃分方法的主要優點在于不需要用戶指定劃分參數，而是根據數據的分布對空間進行劃分，因此這種劃分更為合理。數據空間維度對自頂向下網格方法的影響較小，可以快速將大型高維數據集中的簇分隔開。這一類方法的計算復雜度與數據集大小和維度都呈線性關系適合于處理高維數據。由于劃分是基于數據分布的，而通常認為噪音是在整個空間均勻分布的，所以自頂向下劃分方法對噪音不敏感。但是，由于這種方法得到的網格單元的體積遠大于由底向上網格方法中的網格單元體積，因此方法產生的簇的描述精度比由底向上的網格方法得到的簇的描述精度要低。而且在自頂向下的劃分過程中，同一個簇可能被劃分到不同的區域中，最終得到的同一區域也可能包含不同的簇，這樣就進一步降低了算法的正確度。這類劃分方法的另一個缺點是它在劃分過程中，需要對數據集進行多次掃描。

而由底向上劃分方法在于只需對數據集進行一次線性掃描以及較高的簇的描述精度。因此，兩類方法適用于不同的問題。前者適于處理高維數據集，后者能有效處理存取代價較大的超大型數據集與動態數據。

3 基于網格的聚類過程

基于網格的聚類算法的基本過程是，首先將數據空間W劃分為網格單元，將數據對象集O 映射到網格單元中，并計算每個單元的密度。根據用戶輸入的密度閾值MinPts 判斷每個網格單元是否為高密度單元，由鄰近的稠密單元組形成簇[11]，如表1。

算法1中的步驟1已經在上文詳細說明，下面具體介紹步驟2-4的內容。

3.1 網格單元的密度

簇就是一個區域，該區域中的點的密度大于與之相鄰的區域。在網格數據結構中，由于每個網格單元都有相同的體積，因此網格單元中數據點的密度即是落到單元中的點的個數。據此可以得到稠密網格單元的密度是，設在某一時刻t一個網格單元的密度為density，定義density=單元內的數據點數/數據空間中總的數據點數，設密度閾值為， 為用戶輸入的密度闕值，當density> 時，該網格單元是—個密集網格單元。

相對于稠密網格單元來說，大多數的網格單元包含非常少甚至空的的數據，這一類網格單元被稱為稀疏網格單元。大量的稀疏網格單元的存在會極大的降低聚類的速度，需要在聚類之前對稀疏網格單元進行處理，定義稀疏密度閾值為，當density>時，該網格單元是—個稀疏單元。對于稀疏網格單元的處理方法一般采用壓縮的方法或者直接刪除的方法，如果需要保留稀疏網格單元用于后續處理，可以使用壓縮的方法;如果在現有數據的基礎之上直接聚類，可以刪除稀疏網格單元，理論分析和實驗證明刪除稀疏網格單元并不影響聚類的質量[12]。

3.2 由稠密網格單元形成簇

在基于網格的聚類算法中，根據以上分析，由鄰接的稠密單元形成簇是相對直截了當的，這也是基于網格的方法的優點之一。但是需要首先定義鄰接單元的含義。設n維空問中的存在任意兩個網格單元U1和U2，當這兩個網格單元在—個維上有交集或是具有一個公共面時，稱它們為鄰接網格單元。

在二維空間中，比較常使用的是4-connection相鄰定義和8-connection相鄰定義(如圖1)，4-connection更適合在聚類算法中使用。因為當尋找某個網格單元的鄰居時，在4-connection定義下，一個網格單元只有2d個鄰居，而在8-connection定義下，有3d-1個鄰居，當數據維度d較大時，這個數目非常大。使用4-connection不僅參與計算的單元數目大為減少，而且單元增加與維數的關系由指數增長變為線性增長，所以能進一步減少算法運行所需的時間，具有較低的計算復雜度[13]。其外，只有在非常特殊的情況下，使用4-connection定義得到的聚類結果才會與使用8-connection定義得到的聚類結果不同[14]，這是因為，當4-connection的網格單元是高密度網格單元時，四個對角線上的網格單元不論是否是高密度網格單元，都能被正確的聚類;只有當與對角線上的網格單元相鄰的2個網格單元同時為空且該單元本身是高密度網格單元時，不能正確聚類，在劃分網格時，通常都要求網格單元的大小遠小于簇的大小，因此可以認為這種情況出現的可能很小。

4 結論及展望

基于網格聚類方法的優點是它的處理速度快，因為其速度與數據對象的個數無關，而只依賴于數據空間中每個維上單元的個數，發現任意形狀、任意大小的簇、計算結果與數據輸入順序無關、計算時間與數據量無關，同時不要求像k均值一樣預先指定簇個數等。但是，基于網格方法的聚類算法的輸入參數對聚類結果影響較大，而且這些參數較難設置。當數據中有噪音時，如果不加特殊處理，算法的聚類質量會很差。而且，算法對于數據維度的可伸縮性較差。

基于網格的聚類方法目前還存在一些急需解決的問題，主要有以下幾點:(1)當簇具有不同的密度時，全局的密度參數不能有效發現這樣的簇，需要開發具有可變密度參數的算法。(2)對于不同類型數據的聚類問題，比如對于高維數據，網格的數據將急劇增加，需要有效地技術發現近鄰單元。(3)當數據集的規模巨大以及數據具有地理分布特性時，需要開發有效的并行算法來提高處理的速度。(4)對現有網格算法的優化，從不同方面提高網格算法的有效性。比如開發稀疏網格的壓縮算法、密度相似網格的合并算法等。

本文對基于網格的聚類方法的已有研究進行了分析和總結，包括網格的定義與劃分方法、網格單元密度的確定、由鄰接網格單元形成聚簇的聚類過程;最后對網格聚類方法優點與局限性進行總結，在已有研究分析的基礎上，提出后續需要重點解決的問題。

參考文獻

[1] CHENM S，HAN Jiawei，YUP S.Datamining:an overviewfrom 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，Santia.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，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]Wang W，Yang J，Muntz R.STING:A Statistical Information Grid Approach to Spatial Data Mining[C].In:Proceedings of the 23rd VLDB Conference.Athens，Greece，1997.186-195.

[7]Sheikholeslami G，Chatterjee S，Zhang A.WaveCluster:A Multi-Resolution Clustering Approach for Very Large Spatial Databases[C].In:Proceedings of the 24th VLDB Conference.New York，USA，1998.428-439.

[8]Goil S，Nagesh H，Choudhary A.MAFIA:Efficient and Scalable Subspace Clustering for Very Large Data Sets[C].Technical Report No.CPDC-TR-9906-010，Center for Parallel and Distributed Computing，1999.

[9]Hinneburg A，Keim D A.Optimal Grid-Clustring:Towards Breaking the Curse of Dimensionality in High-Dimensional Clustering[C].In:Proceedings of the 25th VLDB Conference.1999.506-517.

[10]Liu B，Xia Y，Yu P S.Clustering Through Decision Tree Construction[C].In: Proceedings of the Ninth International Conference on Information and Knowledge Management.2000.20-29.

[11]Pang-Ning Tan，Michael Steinbach.Introduction to Data Mining[J].2005，372-373.

[12] Chen Y，Tu L.Density-Based Clustering for Real-Time Stream Data[J].ACMKDD’07，August 12—15，2007，San Jose，California，USA.133—142.

[13] 曹洪其，余嵐，孫志揮.基于網格聚類技術的離群點挖掘算法[J].計算機工程.2006(6).

[14] 孫玉芬.基于網格方法的聚類算法研究[J].華中科技大學.2006.

[15]Han J，Kamber M.Data Mining:Concepts and Techniques[J].Morgan Kaufmann Publishers，2001.