基于網(wǎng)格和密度的聚類算法的分析與研究

摘 要：針對(duì)CLIQUE算法的特點(diǎn)以及所存在的問題進(jìn)行深入的研究。為了進(jìn)一步提高其處理高維海量數(shù)據(jù)的能力，在原算法的基礎(chǔ)上提出一種基于密度樣本分析和基于最優(yōu)區(qū)間分割進(jìn)行改進(jìn)的聚類算法，并通過使用仿真數(shù)據(jù)加以驗(yàn)證是可行的，理論分析與實(shí)驗(yàn)結(jié)果表明，與原算法相比，改進(jìn)算法不僅保留原算法的優(yōu)點(diǎn)，且對(duì)大規(guī)模數(shù)據(jù)集有著很好的聚類效果。

關(guān)鍵詞：聚類；最優(yōu)區(qū)間分割；密度；CLIQUE算法

中圖分類號(hào)：TP301文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1004373X(2008)2012503

Research and Analysis of Clustering Algorithm Based on Grid and Density

XU Yingjie，SUN Junyi

(Computer College，Hubei University of Technology，Wuhan，430068，China)

Abstract：The characters and existing problems of CLIQUE clustering algorithm are intensive researched.In order to improve the ability of solving the high dimention and mass data，based on the old algorithm，a modified one with the methods of density and the best space division is presented.Proving it with simulation data and it is feasible.Theory analysis and experimental results demonstrate the improved algorithm not only can keep its old advantages but also can get better clustering results.

Keywords：clustering;the best space division;density;CLIQUE algorithm

1 引 言

在早期，聚類分析作為統(tǒng)計(jì)學(xué)的一個(gè)分支，主要集中在基于距離的聚類分析。隨著機(jī)器學(xué)習(xí)研究領(lǐng)域的興起，聚類成為無指導(dǎo)學(xué)習(xí)的一個(gè)例子。聚類分析是依據(jù)樣本間關(guān)聯(lián)的量度標(biāo)準(zhǔn)將其自動(dòng)分成幾個(gè)群組，使同一群組內(nèi)的樣本相似，而屬于不同群組的樣本相異的一組方法^［1］。現(xiàn)在，聚類算法已成功地應(yīng)用在空間數(shù)據(jù)庫、模式識(shí)別、圖像處理、過程優(yōu)化、生物學(xué)以及市場營銷、配方設(shè)計(jì)等許多領(lǐng)域中，并取得了良好效果。根據(jù)對(duì)象數(shù)據(jù)間相似度和對(duì)聚類評(píng)價(jià)準(zhǔn)則的不同，常用的聚類方法可分為:劃分方法、層次的方法、基于密度的方法、基于網(wǎng)格的方法和基于模型的方法等。為了進(jìn)一步提高聚類算法在處理高維海量數(shù)據(jù)時(shí)的準(zhǔn)確性和有效性，本文重點(diǎn)研究與改進(jìn)CLIQUE算法，并通過實(shí)驗(yàn)加以仿真。

2 CLIQUE算法分析

CLIQUE聚類算法綜合了基于密度和網(wǎng)格的聚類算法的特點(diǎn)。它對(duì)于大型數(shù)據(jù)庫中高維數(shù)據(jù)的聚類非常有效。給定一個(gè)多維數(shù)據(jù)點(diǎn)的數(shù)據(jù)集合，數(shù)據(jù)點(diǎn)在數(shù)據(jù)空間中通常不是均勻分布的。CLIQUE將數(shù)據(jù)空間分割成網(wǎng)格單元，把落到某一個(gè)網(wǎng)格單元中點(diǎn)的個(gè)數(shù)當(dāng)成這個(gè)單元的密度。可以指定一個(gè)閡值，當(dāng)某一個(gè)網(wǎng)格單元中點(diǎn)的個(gè)數(shù)大于閡值時(shí)，就說這個(gè)單元格是稠密的。聚類就可定義為相連的密集單元的最大集合^［1］。

CLIQUE對(duì)元組的輸入順序不敏感，無需假設(shè)任何規(guī)范的數(shù)據(jù)分布。CLIQUE自動(dòng)發(fā)現(xiàn)最高維的子空間，高密度聚類存在于這些子空間中。它隨輸入數(shù)據(jù)的大小線性的擴(kuò)展，當(dāng)數(shù)據(jù)維數(shù)增加時(shí)具有良好的可伸縮性，但是它也存在著很多局限性，主要有以下幾點(diǎn)^［2］。

（1） 邊緣區(qū)域精度問題。由于算法采用硬劃分技術(shù)，在類的邊界區(qū)域。其包含的點(diǎn)數(shù)比較少，有可能被誤認(rèn)為非密集單元，這樣就容易破壞類的邊緣區(qū)域，降低結(jié)果的準(zhǔn)確性。

（2） 孤立點(diǎn)問題。CLIQUE算法不能自動(dòng)去除數(shù)據(jù)集中的孤立點(diǎn)，需要增加額外的步驟去除孤立點(diǎn)，這就增加了算法復(fù)雜性。

（3） 子空間的剪枝問題。CLIQUE算法應(yīng)用一種剪枝技術(shù)來減少密集單元候選集的數(shù)目。通過把在同一個(gè)子空間中的密集單元分組，并且找出每一個(gè)子空間中密集單元選出的數(shù)據(jù)覆蓋。覆蓋大的子空間將被選出其余的將被剪枝。這種技術(shù)可能遺失一些密集單元。

（4） 算法的精確性問題。算法中很多步驟都大大簡化，并且用的是近似算法，所以聚類結(jié)果的精確性會(huì)降低。

3 CLIQUE算法的改進(jìn)

在CLIQUE算法中采用最小描述長度來剪枝的方法，這樣可能會(huì)漏掉一些密集單元，就會(huì)使聚類的精確性大大降低。而改進(jìn)的新算法，將樣本數(shù)據(jù)向坐標(biāo)軸上投影，利用基于密度的算法將樣本進(jìn)行區(qū)域分割。根據(jù)樣本的分布特性進(jìn)行網(wǎng)格分割得到的區(qū)間會(huì)比等寬分割得到的區(qū)間更加精確，并且數(shù)目也更少；對(duì)獲得的最優(yōu)分割區(qū)間，再采用基于數(shù)據(jù)集劃分的聚類發(fā)現(xiàn)算法，得到基于子空間的聚類^［3］。

在已經(jīng)確定的區(qū)間分割中，為了保證每一個(gè)分割可以將不同的聚類分開，在考慮處理樣本向坐標(biāo)軸上投影時(shí)，采用一種基于密度相連的方法實(shí)現(xiàn)。為更好地描述改進(jìn)算法，在各個(gè)樣本所在的不同一維空間的投影坐標(biāo)中，提出以下概念:

概念1:(d近鄰)假設(shè)一數(shù)據(jù)點(diǎn)q與給定對(duì)象P在i維空間中的投影距離不超過d，那么這個(gè)數(shù)據(jù)點(diǎn)q就稱為該對(duì)象在i+1維空間關(guān)于d的近鄰，這些數(shù)據(jù)點(diǎn)的集合用ad（p）表示，設(shè)D是要進(jìn)行聚類的樣本在一維空間中的投影坐標(biāo)，那么ad(p)定義為:

ad(p) = {q ∈ D | dist (p，q) ≤ d}

概念2:(核對(duì)象)對(duì)于一個(gè)給定對(duì)象，如果在參數(shù)d半徑的大小內(nèi)包含等于MinPts或者超過MinPts的近鄰，那么則稱它為核對(duì)象。

概念3:(直接密度可達(dá))對(duì)于給定的MinPts，d和數(shù)據(jù)點(diǎn)P，若要從對(duì)象q可以直接密度可達(dá)，則p需要滿足的條件是:

(1)p ∈ ad(q)

(2)| ad(q) | > MinPts

概念4:(密度可達(dá))對(duì)于給定的MinPts，d和數(shù)據(jù)點(diǎn)P，從對(duì)象R可以密度可達(dá)，P需要滿足的條件是:存在一串對(duì)象P₁，P₂，…，P_n；P₁=P，P_n=Q，其中從P_i+1可以直接密度可達(dá)P_i。

然后通過檢查數(shù)據(jù)庫中的數(shù)據(jù)在i維空間投影的每個(gè)點(diǎn)的參數(shù)半徑d近鄰來尋找在次維空間的網(wǎng)格劃分區(qū)域。如果包含在一個(gè)點(diǎn)P，并且參數(shù)半徑d中的點(diǎn)數(shù)目大于MinPts的區(qū)域內(nèi)，則創(chuàng)建一個(gè)以P作為核心對(duì)象的網(wǎng)格區(qū)域。然后，反復(fù)的尋找從這些核心對(duì)象直接密度可達(dá)的對(duì)象，這個(gè)過程可能會(huì)涉及一些密度可達(dá)區(qū)域的合并。執(zhí)行這個(gè)過程，一直到?jīng)]有新的點(diǎn)可以添加到任何網(wǎng)格區(qū)域時(shí)，該過程結(jié)束。

通過前面可知，算法用基于密度的方法來優(yōu)化網(wǎng)格，使得分割區(qū)間數(shù)目大大減少，并且不需要生成最小覆蓋的過程，結(jié)果直接就是DNF范式。相比較而言，CLIQUE原算法中采用的平均分割區(qū)間方法將會(huì)出現(xiàn)在聚類發(fā)現(xiàn)的每一步過程中，比最優(yōu)分割區(qū)間方法來會(huì)產(chǎn)生更多的候選聚類項(xiàng)集；另外，在CLIQUE中，采用貪心算法生成相連密集算法的最小覆蓋，產(chǎn)生DNF范式，也使得復(fù)雜度比用最優(yōu)分割區(qū)間方法有所增加。

根據(jù)基于優(yōu)化分割區(qū)間的算法，可以得到在每一維上的一維聚類的區(qū)間，然后通過優(yōu)化分割區(qū)間的方法進(jìn)行Clique聚類^［4］。

4 CLIQUE聚類過程流程圖

通過對(duì)原算法的研究，可知如果一個(gè)n維單元是密集的，那么它在n-1維空間上的投影也是密集的。也就是說，給定一個(gè)n維的候選密集單元，檢查它的n-1維投影單元，發(fā)現(xiàn)任何一個(gè)不是密集的，則知道第n維的單元也不可能是密集的。因此可以從n-1維空間中發(fā)現(xiàn)的密集單元來推測n維空間中潛在的或候選的密集單元。并且CLIQUE算法是按照以下步驟進(jìn)行的^［5］:識(shí)別含有聚類的密集子空間；識(shí)別聚類；生成聚類的最小描述。

結(jié)合所要改進(jìn)之處，可得圖1。

5 改進(jìn)算法的分析

改進(jìn)算法不僅具有CLIQUE本來的特點(diǎn)，如：良好的可擴(kuò)展性、較強(qiáng)的噪聲處理能力、對(duì)輸入數(shù)據(jù)樣本的順序不敏感、可以發(fā)現(xiàn)任意形狀的聚類、聚類結(jié)果易于控制等特點(diǎn)，而且它還有著原算法所不具有的優(yōu)點(diǎn)^［6，7］：

（1）有較低的時(shí)間復(fù)雜度。因?yàn)閷?shù)據(jù)樣本向坐標(biāo)軸上投影，所以也就減少了坐標(biāo)軸上的聚類區(qū)域，使得聚類子空間的數(shù)目顯著減少，也省去了覆蓋相鄰密度單元的步驟；

（2）較好的可擴(kuò)展性。當(dāng)數(shù)據(jù)增多時(shí)數(shù)據(jù)分布特性更加明顯，數(shù)據(jù)量越多，效率就越高；

（3）聚類結(jié)果有著較高的精確度。用基于最優(yōu)分割區(qū)間的算法能夠更加精確地刻畫聚類的邊界，并且不采用剪枝算法，這樣就可以得到更加精確的聚類結(jié)果。

實(shí)驗(yàn)的目的是驗(yàn)證改進(jìn)CLIQUE算法的可行性和有效性，顯示出算法的優(yōu)勢(shì)。同時(shí)對(duì)算法出現(xiàn)的若干問題進(jìn)行分析，為算法的下一步改善提供實(shí)驗(yàn)依據(jù)^［8］。用戶可以通過輸入?yún)?shù)來控制產(chǎn)生數(shù)據(jù)集的結(jié)構(gòu)和大小。參數(shù)包括數(shù)據(jù)集的大小、維數(shù)和各維上的取值范圍^［9-10］。

由圖2可以看出，隨著數(shù)據(jù)集維數(shù)的增加，改進(jìn)后算法的效率比原算法有較大提高，性能也有了進(jìn)一步的改善。通過比較可知新算法有更好的聚類效果。

6 結(jié) 語

CLIQUE算法是聚類分析中的一種常用方法，由于算法在區(qū)域邊界精度和子空間剪枝等方面存在問題，限制了該算法的性能，本文在原算法的基礎(chǔ)上進(jìn)行了嘗試性的改進(jìn)并提出一種改進(jìn)方案，可以有效地提高算法的準(zhǔn)確性和處理數(shù)據(jù)的能力。在理論和實(shí)驗(yàn)方面證明改進(jìn)后的算法與原算法相比是可行而有效的。為了提高處理超大型復(fù)雜數(shù)據(jù)的性能，今后有待于在并行處理方面多做研究。

參考文獻(xiàn)

［1］Han J，Kamber M.Data Mining Concepts and Techniques［M］.Morgan Kaufmann Publishers，2001.

［2］馮永，吳開貴，熊忠陽，等．一種有效的并行高維聚類算法\\．計(jì)算機(jī)科學(xué)，2005，32(3)：216-218．

［3］王建會(huì)，申展，胡運(yùn)發(fā).一種實(shí)用高效的聚類算法\\.軟件學(xué)報(bào)，2004，15(5):697-705.

［4］業(yè)寧，李威，梁作鵬.一種Web用戶行為聚類算法\\.小型微型計(jì)算機(jī)系統(tǒng)，2004，25(7):1 364-1 367.

［5］邵峰晶，于忠清.數(shù)據(jù)挖掘原理與算法［M］.北京：中國水利水電出版社，2003.

［6］Wang W，Yang J，Muntz R.A Statistical Inf_ormation Grid Approach to Spatial Data Mining［C］.In Proc.1997 Int.Conf.Very Large Databases，Athens，Greece，1997:186-195.

［7］Hinneburg A，Keim D.An Efficient Approach to Clustering in Large Multimedia Databases with Noise［C］.In：Proc.1998 Int.Conf Knowledge Discovery and Data Mining，New York:AAAI Press，1998:58-65.

［8］Alexander Hinneburg，Daniel A Keim.An EfficientApproach to Clustering in Large Multimedia Databases with Noise［C］.KDD，1998:58-65.

［9］Ci Song，Guizani Mohsen，Sharif Hamid.Adaptive Clustering in Wireless Sensor Networks by Mining Sensor Energy Data\\.Computer Communications，2007:2 968-2 975.

［10］Abascal E，Garcia Lautre I，Mallor F.Data Mining in a Bicriteria Clustering Problem，2006.705-716.

作者簡介 許英杰 男，1983年出生，碩士研究生。主要研究方向?yàn)閿?shù)據(jù)挖掘、網(wǎng)絡(luò)安全。

孫俊逸 男，1947年出生，教授。主要研究方向?yàn)橛?jì)算機(jī)控制、虛擬現(xiàn)實(shí)。