網格聚類算法研究

【摘 要】聚類分析是數據挖掘中非常重要的方法， 并且在很多領域發揮了巨大的作用。本文以研究網格聚類算法為目的，介紹了常見的基于網格的聚類算法，并比較分析了各類算法的基本思想和優缺點。

【關鍵詞】網格聚類算法;STING算法;WaveCluster算法;CLIQUE算法

0.引言

聚類就是將多個數據對象分成不同的類或者簇，每個類中的對象之間具有較高的相似度，而不同類的對象相似度低。聚類算法是數據挖掘中的重要算法，可以應用于機器學習、統計學、模式識別、圖像處理、考古學、市場營銷和生物學等多個領域。

聚類是數據挖掘的主要任務之一，目前常見的文獻中主要有以下幾類聚類算法：劃分方法、層次方法、基于密度的算法、基于網格的算法及基于模型的算法等。一些聚類算法集成了多種聚類方法的思想，所以有時不能將某個給定的算法劃分為屬于某一類特定的聚類方法。各類算法各有自己的特點，應用于不同的領域并且發揮了很大的作用，實現了數據的有效聚類。

1.基于網格的聚類方法(grid-based method)

基于網格的方法采用了網格的數據結構，首先將數據空間劃分成為有限個單元（cell），這些單元就形成了網格結構，所有的處理都是以單個的單元為對象的。這種方法的主要優點就是處理速度很快，處理時間與目標數據庫中記錄的個數無關的，但是又依賴于數據空間的單元數目。代表算法有：STING[1]、WaveCluster、CLIQUE。

1.1 STING（Statistical Information Grid，統計信息網格）算法

STING算法是一種基于網格的多分辨率聚類算法，其基本思想是：先將數據空間區域劃分成矩形單元。對于不同級別的分辨率，通常存在著不同級別的矩形單元，這些單元形成一個層次結構，高層的每一個單元被劃分為多個低一層的單元。每個網格單元屬性的統計信息如均值等都被預先計算和存儲起來，以方便下一步的查詢操作。

高層單元的統計參數可以通過計算低層單元獲得，這些參數包括：屬性無關的參數count（計數）；屬性相關的參數mean(平均值)，stdev(標準偏差)，min(最小值)，max(最大值)，以及該單元中屬性值遵循的分布(distribution)類型，例如一致分布、正態分布等。當數據被裝載進數據庫時，底層單元的一些參數(如min、max、stdev、mean)可以直接由數據進行計算。如果分布的類型已經確定，distribution的值可以由用戶指定，也可以通過假設檢驗來獲得。高層單元的分布類型的確定可以基于它對應的低層單元多數的分布類型，通過閾值過濾過程的合取計算來得到。如果低層單元的分布彼此不同，閾值檢驗失敗，那么此時高層單元的分布類型就為none。

當得到上述的統計參數后，就可以根據統計參數來進行查詢處理。統計參數的使用可以按照自頂向下的基于網格的方法來進行查詢。大體過程如下：首先，在層次結構中，選定一層（通常選定含少量單元的層）作為查詢答復過程的開始點。對選定的當前層次的每個單元，估算其概率范圍或者計算置信度區間，該概率用以反映該單元與給定查詢的相關程度。此時得到一些不相關的單元和相關單元，不相關單元在以后操作中不再考慮。相關單元用于下一層較低單元的處理。反復進行該處理過程，直到達到底層。最后，如果滿足查詢要求，則返回相關單元。否則，檢索和處理落在相關單元中的數據，直到它們滿足查詢要求。

與其他聚類算法相比，STING算法具有以下優點：（1）基于網格的計算是獨立于查詢的。這主要是因為存儲在每個單元中的統計信息提供了單元中的數據不依賴于查詢的匯總信息，所以網格的計算獨立于查詢。（2）STING算法通過掃描數據庫一次來計算單元的統計參數，時間復雜度是O(n)，n是對象的數目。在生成層次結構后，一個查詢響應時間是O(g)，這里g是最低層網格單元的數目，通常遠遠小于n，這些使該算法的效率非常高。（3）網格結構利于并行處理和增量更新。

1.2 WaveCluster（利用小波變換聚類）算法

WaveCluster的基本思想是：首先通過在數據空間上強加一個多維網格結構，這個結構用來匯總數據，然后采用小波變換變換原特征空間，在變換后的空間中找到密集區域，該算法是一種多分辨率的聚類算法。這種方法中每個網格單元匯總了一組映射到該單元點的信息，它提供給多分辨率小波變換使用以及隨后的聚類分析，可以存放在內存中。

該算法的優點是：（1）速度快，并且可以是并行的。（2）小波變換具有多分辨率的特性，該特性有助于發現不同精度的聚類。（3）提供了無指導聚類，并且能夠自動排除離群點。

1.3 CLIQUE（Clustering In Quest，維增長子空間聚類算法）算法

CLIQUE算法是典型的高維空間的子空間聚類算法，綜合了基于密度和網格的聚類算法，該算法的基本思想是：給定一個多維數據點的數據空間，數據點在數據空間中通常是分布不平衡的。該算法區分空間中稀疏的和“擁擠的”區域(空間或單元)，找出數據集合的全局分布模式。在CLIQUE算法中，把相連的密集單元的最大集合成為簇。如果一個單元中包含的數據點數超過了某個輸入參數，則該單元是密集的。

CLIQUE通過以下兩個步驟進行多維聚類：

第一步，CLIQUE將多維數據空間劃分為互不相交的長方形單元，識別每一維中的密集單元。代表密集單元的子空間取交集形成了一個候選搜索空間。

第二步，CLIQUE為每個簇生成最小的描述。對每個簇，它確定覆蓋相連的密集單元的最大區域，然后再為每一個簇確定最小的覆蓋[2]。

該算法的優點：（1）對數據高維有良好的伸縮性，對數據輸入順序不敏感，具有處理噪聲的能力。（2）方法簡化，但是聚類結果的精確可能降低。

1.4改進的網格聚類算法

基于上述分析，各類算法有各自的優缺點，為了更好的完善聚類算法，國內外出現了很多改進的網格聚類算法，這類算法大多都和其他的聚類算法相結合，如：基于密度和網格的聚類算法：SCI算法、DCLUST算法、MAFIA聚類算法等；基于數據流的網格密度算法（RTCS）；基于網格的層次聚類算法；自動化網格聚類算法（GCA）等算法。

2.結束語

本文對常見的聚類算法進行了闡述和分析，每一種網格聚類算法都有其自身的優缺點，如何將網格聚類算法與實際問題相結合，如何將網格聚類算法更加有效地應用于實踐成為本文作者下一步將要研究的問題。 [科]

【參考文獻】

［１］W.Wang，J.Yang，R.Muntz.A statistical information grid approach to spatial data mining[C].In Proc.1997 Int.Conf.Very Large Databases， Athens，reecs ，Aug.1997:186～195.

［２］韓家煒.數據挖掘—概念與技術[M].

［３］范明，孟小峰，譯.北京:機械工業出版社，2001數據挖掘概念與技術.