網格聚類算法綜述

網格聚類算法綜述

（1）STING

STING（Statistical Information Grid）是一種基于網格的多分辨率聚類技術它將空間區域劃分為矩型單元。針對不同級別的分辨率，通常存在多個級別的矩形單元，這些單元形成了一個層次結構；高層的每個單元被劃分為多個低一層的單元。每個網格單元屬性的統計信息（例如平均值、最大值和最小值）被預先計算和存儲。這些統計信息對于下面描述的查詢處理是有用的。

STING有幾個優點：（1）由于存儲在每個單元中的統計信息提供了單元中的數據不依賴查詢的匯總信息，因此基于網格的計算是獨立于查詢的。（2）網格結構有利于并行處理和增量更新。（3）效率很高。STING掃描數據庫一次來計算單元的統計信息。因此產生聚類的時間復雜度是O(n)，n是對象的數目。n是對象的數目。在層次結構建立后，查詢處理時間是O(g)，這里g是最底層網格單元的數目，通常遠遠小于n。

（2）Wave Cluster

Wave Cluster是一種多分辨率的聚類算法，它首先通過在數據空間上強加一個多為網格結構來匯總數據，然后采用一種小波變換來變換原特征空間，在變換后的空間中找到密集區域。在該方法中，每個網格單元匯總了一組映射到該單元中的點的信息。這種匯總信息適合于在內存中進行多分辨率小波變換時以及隨后的聚類分析使用。

小波變換是一種信號處理技術，它將一個信號分解為不同頻率的子波段。通過應用一維小波變換n次，小波模型可以應用于n維信號。在進行小波變換時，數據被變換在不同的分辨率層次保留對象間的相對距離。這使得數據的自然聚類變得更加容易區別。通過在新的空間中尋找高密度區域，可以確定聚類。

小波變換對聚類有如下優點：

提供了無指導的聚類。它采用了帽形過濾，強調點密集的區域，而忽視了在密集區域外的較弱的信息。這樣，在原特征空間中的密集區域成為了附近點的吸引點，距離較遠的點成為抑制點。這意味著數據的聚類自動地顯示出來，并。清理。了周圍的區域。這樣，小波變換的另一個優點是能夠自動地排除孤立點。小波變換的多分辨率特性對不同精確性層次的聚類探測是有幫助的。

基于小波變換的聚類速度很快，計算復雜度為O(n)，這里n是數據庫中對象的數目。這個算法事先可以并行化。

（3）CLIQUE

CLIQUE聚類算法綜合了基于網格和基于密度的聚類方法。它對大規模數據庫中的高維數據的聚類非常有效。CLIQUE的中心思想如下：

給定一個多維數據點的大集合，數據點在數據空間中通常不是均衡分布的。CLIQUE區分空間中稀疏的和。擁擠的。區域（或單元），以發現數據集合的全局分布模式。

如果一個單元中的數據點的數目超過了某個輸入模型參數，則該單元是密集的。在CLIQUE中，簇定義為相連的密集單元的最大集合。

（4）SCI

SCI聚類算法綜合了基于密度和基于網格的聚類方法。網格的劃分方法和CLIQUE類似，通過對d維數據集D的每個屬性上等分得到，首先將各個屬性排序為[I_j,U_j]，j=1,2,3,4,...,d，然后通過k-regular劃分成彼鄰的舉行單元格。數據空間被劃分為k個相同體積的單元格。所以說網格是均勻劃分的。

在聚類子空間中，它通過連接稠密單元格的技術獲得簇的大體輪廓。落入每個單元格中的數據點的總數就看作該單元格的密度。把單元格分成3種類型，即稠密單元格、稀疏單元格和孤立單元格。先通過熵的定理去除某些對于聚類效果信息少的屬性，然后稠密單元格彼此相連，被稀疏單元格分離，形成簇的輪廓。而孤立單元格也被稀疏單元格分離，被看作孤立點集，而稀疏單元格中的點可能是簇的邊界點，也可能是噪音點，需要進一步處理。處理的方法是，對于每一個在稀疏單元格中的數據點，如果離其最近的單元格是是稠密單元格，則將其歸為簇中；否則就是噪音數據。最后形成簇。

（5）MAFIA

MAFIA聚類算法綜合了基于密度和基于網格的聚類算法。網格劃分方法是根據數據分布決定網格單元的大小，因此網格的劃分是不均勻的。

在MAFIA算法中使用了一種自底向上的子空間聚類技術。該算法基本思想可以概況如下：根據數據分布劃分網格到單元，k維候選的高密度單元是通過合并任意兩個（k-1）維的高密度單元得到的，并且這兩個（k-1）維的單元有一個共同的（k-2）維的子單元，再根據高密度單元進行聚類。

該算法適合高維和大數據集，其時間復雜度是隨維數呈指數增長。該算法的優點是不需要用戶去輸入一般的網格參數；缺點是對參數相當敏感，運行時間隨維數呈指數增長。通過與CLIQUE進行比較，得出MAFIA性能較好并且有較好的聚類質量，是CLIQUE聚類的一種提高。

（6）ENCLUS

ENCLUS聚類算法是一種基于網格的聚類方法。網格的劃分方法是等分數據空間的每一維，所以網格的劃分是均勻的。

在ENCLUS中采用了一種尋找聚類子空間的技術：根據指定熵的值，由底向上（從一維開始）尋找有效子空間。該算法的基本思想可以概括如下：在CLIQUE算法提出的搜索有效的子空間技術的基礎上，提出一種基于熵的搜索有效子空間的方法，對每一個子空間計算其熵值，若值低于指定的熵值，就認為此單元是有效的，在找出的有效的子空間中，使用現有的聚類算法都可以進行聚類。

該算法的時間和空間復雜度都是線性的，類似于CLIQUE算法。ENCLUS算法的優點是提出了一種有效的基于熵的搜索子空間的標準，效率高；缺點是對參數非常敏感。

（7）DCLUST

DCLUST聚類算法綜合了基于密度和基于網格的聚類方法。網格的劃分是等分數據空間的每一維，所以網格的劃分是均勻的。

DCLUST算法的基本思想可概括如下：首先劃分網絡，根據密度閾值獲得高密度單元，將每個高密度單元的中心作為其代表點，根據這些代表點構造帶標點的最小生成樹（R-MST）和概要結構，利用R-MST進行Multi-resolution聚類和增量聚類。

該算法的時間和空間復雜度均為O(n)，其優點是能處理含噪聲的任意形狀的簇，并且對數據的順序不敏感，可以處理增量聚類。DCLUST算法主要解決傳統的空間聚類算法不能有效地處理增量聚類的問題。

（8）MMNG

MMNG聚類算法是一種基于網格的聚類方法。網格的劃分方法是利用一種P-樹的數據結構進行劃分，網格的劃分是均勻的。

MMNG算法的基本思想可概括如下：使用了一個P-樹的數據結構來劃分數據集，并計算每一個劃分單元的中心點，以此進行聚類，從而達到對MM算法的一種改進。

算法的優點是當數據維數增加時，MMNG需評估的簇中心的數目相比MM算法呈指數下降。該算法主要是對MM算法的一種改進。

（9）GDILC

GDILC聚類算法是一種基于網格的聚類方法。網格的劃分方法是等分數據空間的每一維，所以網格的劃分是均勻的。

GDILC算法的基本思想可概括如下：描述了一個基于網格的等高線聚類，即同一類中的點在同一個等高線上，相鄰等高線的距離若小于一個閾值，則合并這兩個等高線對應的類。GDILC算法的時間復雜度是線性的，該算法的優點是能快速、無指導地聚類，并能很好地識別出孤立點和各種形狀的簇；缺點是不能很好地分離出各個類。

（10）網格化聚類算法的均值近似方法

網格化聚類算法^[是一種基于網格的聚類方法。該方法的基本思想可概括為：采用數據空間網格劃分的基于密度的聚類算法的均值近似方法，對密集單元，通過一個重心點取代原有的保存網格中所有點，有效減少了內存需求；采用一個近似的密度計算來減小密度計算的復雜度。這種算法的優點是通過采用均值計算方法可減少內存需求，大幅度降低計算復雜度。該算法是對目前基于網格和密度的聚類方法的一種改進。

（11）移動網格聚類算法

移動網格聚類算法^[11]是一種綜合了基于密度和基于網格的聚類方法。在移動網格聚類算法中，網格的劃分方法是等分數據空間的每一維，所以網格的劃分是均勻的。該算法的基本思想可概括為：在傳統的網格聚類的基礎上，使用滑動窗口技術即把每一個網格向外擴展半個網格單元，以提高聚類的精度。該算法的優點是不需要用戶輸入參數，有較高的精度；缺點是時間復雜度很大。