本篇文章是由《計算機輔助工程》發表的一篇電子論文，本刊主要刊登計算機技術及其應用和相關領域的學術論文，如計算機輔助設計與圖形學技術及應用、專家系統、知識工程、計算機網絡與通信、分布式系統、計算機軟件與理論、程序設計語言、操作系統、數據庫、計算機輔助教學、制造業信息化、物流工程信息化、交通運輸工程信息化、信息管理技術及應用、人工智能技術及應用、電氣自動化等領域的文章，以及有價值的研究報告和研究簡介。

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

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

　　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]。