網(wǎng)格聚類算法綜述

網(wǎng)格聚類算法綜述

（1）STING

STING（Statistical Information Grid）是一種基于網(wǎng)格的多分辨率聚類技術(shù)它將空間區(qū)域劃分為矩型單元。針對(duì)不同級(jí)別的分辨率，通常存在多個(gè)級(jí)別的矩形單元，這些單元形成了一個(gè)層次結(jié)構(gòu)；高層的每個(gè)單元被劃分為多個(gè)低一層的單元。每個(gè)網(wǎng)格單元屬性的統(tǒng)計(jì)信息（例如平均值、最大值和最小值）被預(yù)先計(jì)算和存儲(chǔ)。這些統(tǒng)計(jì)信息對(duì)于下面描述的查詢處理是有用的。

STING有幾個(gè)優(yōu)點(diǎn)：（1）由于存儲(chǔ)在每個(gè)單元中的統(tǒng)計(jì)信息提供了單元中的數(shù)據(jù)不依賴查詢的匯總信息，因此基于網(wǎng)格的計(jì)算是獨(dú)立于查詢的。（2）網(wǎng)格結(jié)構(gòu)有利于并行處理和增量更新。（3）效率很高。STING掃描數(shù)據(jù)庫(kù)一次來(lái)計(jì)算單元的統(tǒng)計(jì)信息。因此產(chǎn)生聚類的時(shí)間復(fù)雜度是O(n)，n是對(duì)象的數(shù)目。n是對(duì)象的數(shù)目。在層次結(jié)構(gòu)建立后，查詢處理時(shí)間是O(g)，這里g是最底層網(wǎng)格單元的數(shù)目，通常遠(yuǎn)遠(yuǎn)小于n。

（2）Wave Cluster

Wave Cluster是一種多分辨率的聚類算法，它首先通過(guò)在數(shù)據(jù)空間上強(qiáng)加一個(gè)多為網(wǎng)格結(jié)構(gòu)來(lái)匯總數(shù)據(jù)，然后采用一種小波變換來(lái)變換原特征空間，在變換后的空間中找到密集區(qū)域。在該方法中，每個(gè)網(wǎng)格單元匯總了一組映射到該單元中的點(diǎn)的信息。這種匯總信息適合于在內(nèi)存中進(jìn)行多分辨率小波變換時(shí)以及隨后的聚類分析使用。

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

小波變換對(duì)聚類有如下優(yōu)點(diǎn)：

提供了無(wú)指導(dǎo)的聚類。它采用了帽形過(guò)濾，強(qiáng)調(diào)點(diǎn)密集的區(qū)域，而忽視了在密集區(qū)域外的較弱的信息。這樣，在原特征空間中的密集區(qū)域成為了附近點(diǎn)的吸引點(diǎn)，距離較遠(yuǎn)的點(diǎn)成為抑制點(diǎn)。這意味著數(shù)據(jù)的聚類自動(dòng)地顯示出來(lái)，并。清理。了周?chē)膮^(qū)域。這樣，小波變換的另一個(gè)優(yōu)點(diǎn)是能夠自動(dòng)地排除孤立點(diǎn)。小波變換的多分辨率特性對(duì)不同精確性層次的聚類探測(cè)是有幫助的。

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

（3）CLIQUE

CLIQUE聚類算法綜合了基于網(wǎng)格和基于密度的聚類方法。它對(duì)大規(guī)模數(shù)據(jù)庫(kù)中的高維數(shù)據(jù)的聚類非常有效。CLIQUE的中心思想如下：

給定一個(gè)多維數(shù)據(jù)點(diǎn)的大集合，數(shù)據(jù)點(diǎn)在數(shù)據(jù)空間中通常不是均衡分布的。CLIQUE區(qū)分空間中稀疏的和。擁擠的。區(qū)域（或單元），以發(fā)現(xiàn)數(shù)據(jù)集合的全局分布模式。

如果一個(gè)單元中的數(shù)據(jù)點(diǎn)的數(shù)目超過(guò)了某個(gè)輸入模型參數(shù)，則該單元是密集的。在CLIQUE中，簇定義為相連的密集單元的最大集合。

（4）SCI

SCI聚類算法綜合了基于密度和基于網(wǎng)格的聚類方法。網(wǎng)格的劃分方法和CLIQUE類似，通過(guò)對(duì)d維數(shù)據(jù)集D的每個(gè)屬性上等分得到，首先將各個(gè)屬性排序?yàn)?/span>[I_j,U_j]，j=1,2,3,4,...,d，然后通過(guò)k-regular劃分成彼鄰的舉行單元格。數(shù)據(jù)空間被劃分為k個(gè)相同體積的單元格。所以說(shuō)網(wǎng)格是均勻劃分的。

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

（5）MAFIA

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

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

該算法適合高維和大數(shù)據(jù)集，其時(shí)間復(fù)雜度是隨維數(shù)呈指數(shù)增長(zhǎng)。該算法的優(yōu)點(diǎn)是不需要用戶去輸入一般的網(wǎng)格參數(shù)；缺點(diǎn)是對(duì)參數(shù)相當(dāng)敏感，運(yùn)行時(shí)間隨維數(shù)呈指數(shù)增長(zhǎng)。通過(guò)與CLIQUE進(jìn)行比較，得出MAFIA性能較好并且有較好的聚類質(zhì)量，是CLIQUE聚類的一種提高。

（6）ENCLUS

ENCLUS聚類算法是一種基于網(wǎng)格的聚類方法。網(wǎng)格的劃分方法是等分?jǐn)?shù)據(jù)空間的每一維，所以網(wǎng)格的劃分是均勻的。

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

該算法的時(shí)間和空間復(fù)雜度都是線性的，類似于CLIQUE算法。ENCLUS算法的優(yōu)點(diǎn)是提出了一種有效的基于熵的搜索子空間的標(biāo)準(zhǔn)，效率高；缺點(diǎn)是對(duì)參數(shù)非常敏感。

（7）DCLUST

DCLUST聚類算法綜合了基于密度和基于網(wǎng)格的聚類方法。網(wǎng)格的劃分是等分?jǐn)?shù)據(jù)空間的每一維，所以網(wǎng)格的劃分是均勻的。

DCLUST算法的基本思想可概括如下：首先劃分網(wǎng)絡(luò)，根據(jù)密度閾值獲得高密度單元，將每個(gè)高密度單元的中心作為其代表點(diǎn)，根據(jù)這些代表點(diǎn)構(gòu)造帶標(biāo)點(diǎn)的最小生成樹(shù)（R-MST）和概要結(jié)構(gòu)，利用R-MST進(jìn)行Multi-resolution聚類和增量聚類。

該算法的時(shí)間和空間復(fù)雜度均為O(n)，其優(yōu)點(diǎn)是能處理含噪聲的任意形狀的簇，并且對(duì)數(shù)據(jù)的順序不敏感，可以處理增量聚類。DCLUST算法主要解決傳統(tǒng)的空間聚類算法不能有效地處理增量聚類的問(wèn)題。

（8）MMNG

MMNG聚類算法是一種基于網(wǎng)格的聚類方法。網(wǎng)格的劃分方法是利用一種P-樹(shù)的數(shù)據(jù)結(jié)構(gòu)進(jìn)行劃分，網(wǎng)格的劃分是均勻的。

MMNG算法的基本思想可概括如下：使用了一個(gè)P-樹(shù)的數(shù)據(jù)結(jié)構(gòu)來(lái)劃分?jǐn)?shù)據(jù)集，并計(jì)算每一個(gè)劃分單元的中心點(diǎn)，以此進(jìn)行聚類，從而達(dá)到對(duì)MM算法的一種改進(jìn)。

算法的優(yōu)點(diǎn)是當(dāng)數(shù)據(jù)維數(shù)增加時(shí)，MMNG需評(píng)估的簇中心的數(shù)目相比MM算法呈指數(shù)下降。該算法主要是對(duì)MM算法的一種改進(jìn)。

（9）GDILC

GDILC聚類算法是一種基于網(wǎng)格的聚類方法。網(wǎng)格的劃分方法是等分?jǐn)?shù)據(jù)空間的每一維，所以網(wǎng)格的劃分是均勻的。

GDILC算法的基本思想可概括如下：描述了一個(gè)基于網(wǎng)格的等高線聚類，即同一類中的點(diǎn)在同一個(gè)等高線上，相鄰等高線的距離若小于一個(gè)閾值，則合并這兩個(gè)等高線對(duì)應(yīng)的類。GDILC算法的時(shí)間復(fù)雜度是線性的，該算法的優(yōu)點(diǎn)是能快速、無(wú)指導(dǎo)地聚類，并能很好地識(shí)別出孤立點(diǎn)和各種形狀的簇；缺點(diǎn)是不能很好地分離出各個(gè)類。

（10）網(wǎng)格化聚類算法的均值近似方法

網(wǎng)格化聚類算法^[是一種基于網(wǎng)格的聚類方法。該方法的基本思想可概括為：采用數(shù)據(jù)空間網(wǎng)格劃分的基于密度的聚類算法的均值近似方法，對(duì)密集單元，通過(guò)一個(gè)重心點(diǎn)取代原有的保存網(wǎng)格中所有點(diǎn)，有效減少了內(nèi)存需求；采用一個(gè)近似的密度計(jì)算來(lái)減小密度計(jì)算的復(fù)雜度。這種算法的優(yōu)點(diǎn)是通過(guò)采用均值計(jì)算方法可減少內(nèi)存需求，大幅度降低計(jì)算復(fù)雜度。該算法是對(duì)目前基于網(wǎng)格和密度的聚類方法的一種改進(jìn)。

（11）移動(dòng)網(wǎng)格聚類算法

移動(dòng)網(wǎng)格聚類算法^[11]是一種綜合了基于密度和基于網(wǎng)格的聚類方法。在移動(dòng)網(wǎng)格聚類算法中，網(wǎng)格的劃分方法是等分?jǐn)?shù)據(jù)空間的每一維，所以網(wǎng)格的劃分是均勻的。該算法的基本思想可概括為：在傳統(tǒng)的網(wǎng)格聚類的基礎(chǔ)上，使用滑動(dòng)窗口技術(shù)即把每一個(gè)網(wǎng)格向外擴(kuò)展半個(gè)網(wǎng)格單元，以提高聚類的精度。該算法的優(yōu)點(diǎn)是不需要用戶輸入?yún)?shù)，有較高的精度；缺點(diǎn)是時(shí)間復(fù)雜度很大。