基於網格的聚類方法研究
行業科技
作者：胡宇
【摘要】由於已有的聚類算法對於發現任意形狀的聚類和處理離群點效果不理想，分析了現有基於網格的聚類算法。使用網格方法的數據分析方法將空間劃分為由（超）矩形網格單元組成的網格，然後在網格單元上進行聚類，最後提出基於網格的聚類需要進一步研究的方向。
【關鍵詞】數據挖掘；網格；聚類
1 引言
數據挖掘指從大型數據庫或數據倉庫中提取隱含的、未知的及有應用價值的信息或模式。它是數據庫研究中的一個很有應用價值的領域，融合了數據庫、機器學習、統計學等多個領域的理論和技術。
數據挖掘中廣為研究的課題之一是聚類分析，從數據中尋找數據間的相似性，並依此對數據進行分類，從而發現數據中隱含的有用信息或知識。目前已經提出了不少著名的數據聚類算法，有CLARANS、BIRCH、DBSCAN和CLIQUE等。但對於高維、大規模數據庫的高效聚類分析仍然是一個有待研究的開放問題。
空間數據處理中常用的將空間數據離散化的方法是網格方法。由於易於增量實現和進行高維數據處理而廣泛應用聚類算法。研究人員已經提出了很多基於網格的聚類算法，包括利用了存儲在網格單元中的統計信息的STING；用一種小波轉換方法來聚類數據對象的WaveCluster；在高維數據空間中基於網格和密度的聚類方的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），將數據空間均勻劃分為相等大小的網格單元，假設落入同一網格單元內的所有數據點都屬於同一個簇，落入其內數據的統計信息由每個網格單元保存，比如數據點個數與數據點之和，包含一定數目數據點的網格單元被稱為高密度網格單元。
2.2自頂向下的劃分方法
自頂向下的網格劃分方法采取分治的策略（divideand conquer principle），對數據空間進行遞歸劃分，使問題的規模不斷減小。首先將原數據空間劃分為幾個較大的區域。對於每個得到的區域，劃分過程反複執行，直到每個區域包含屬於同一個簇的數據點，那麼這些區域就是最終的網格單元。基於自頂向下網格方法的聚類算法直接將高密度網格單元識別為一個簇，或是將相連的高密度網格單元識別為簇。
3 基於網格的聚類過程
3.1網格單元的密度
簇就是一個區域，該區域中的點的密度大於與之相鄰的區域。在網格數據結構中，由於每個網格單元都有相同的體積，因此網格單元中數據點的密度即是落到單元中的點的個數。據此可以得到稠密網格單元的密度是，設在某一時刻t一個網格單元的密度為density，定義density=單元內的數據點數/數據空間中總的數據點數，設密度閾值為，為用戶輸入的密度闕值，當density>時，該網格單元是—個密集網格單元。
相對於稠密網格單元來說，大多數的網格單元包含非常少甚至空的的數據，這一類網格單元被稱為稀疏網格單元。對於稀疏網格單元的處理方法一般采用壓縮的方法或者直接刪除的方法，如果需要保留稀疏網格單元用於後續處理，可以使用壓縮的方法；如果在現有數據的基礎之上直接聚類，可以刪除稀疏網格單元，理論分析和實驗證明刪除稀疏網格單元並不影響聚類的質量。