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

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

中圖分類號：TP301文獻標識碼：A文章編號：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)計學的一個分支，主要集中在基于距離的聚類分析。隨著機器學習研究領域的興起，聚類成為無指導學習的一個例子。聚類分析是依據樣本間關聯的量度標準將其自動分成幾個群組，使同一群組內的樣本相似，而屬于不同群組的樣本相異的一組方法^［1］?，F在，聚類算法已成功地應用在空間數據庫、模式識別、圖像處理、過程優(yōu)化、生物學以及市場營銷、配方設計等許多領域中，并取得了良好效果。根據對象數據間相似度和對聚類評價準則的不同，常用的聚類方法可分為:劃分方法、層次的方法、基于密度的方法、基于網格的方法和基于模型的方法等。為了進一步提高聚類算法在處理高維海量數據時的準確性和有效性，本文重點研究與改進CLIQUE算法，并通過實驗加以仿真。

2 CLIQUE算法分析

CLIQUE聚類算法綜合了基于密度和網格的聚類算法的特點。它對于大型數據庫中高維數據的聚類非常有效。給定一個多維數據點的數據集合，數據點在數據空間中通常不是均勻分布的。CLIQUE將數據空間分割成網格單元，把落到某一個網格單元中點的個數當成這個單元的密度?？梢灾付ㄒ粋€閡值，當某一個網格單元中點的個數大于閡值時，就說這個單元格是稠密的。聚類就可定義為相連的密集單元的最大集合^［1］。

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

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

（2） 孤立點問題。CLIQUE算法不能自動去除數據集中的孤立點，需要增加額外的步驟去除孤立點，這就增加了算法復雜性。

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

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

3 CLIQUE算法的改進

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

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

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

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

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

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

(1)p ∈ ad(q)

(2)| ad(q) | > MinPts

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

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

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

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

4 CLIQUE聚類過程流程圖

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

結合所要改進之處，可得圖1。

5 改進算法的分析

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

（1）有較低的時間復雜度。因為將數據樣本向坐標軸上投影，所以也就減少了坐標軸上的聚類區(qū)域，使得聚類子空間的數目顯著減少，也省去了覆蓋相鄰密度單元的步驟；

（2）較好的可擴展性。當數據增多時數據分布特性更加明顯，數據量越多，效率就越高；

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

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

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

6 結 語

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

參考文獻

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

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

［3］王建會，申展，胡運發(fā).一種實用高效的聚類算法\\.軟件學報，2004，15(5):697-705.

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

［5］邵峰晶，于忠清.數據挖掘原理與算法［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年出生，碩士研究生。主要研究方向為數據挖掘、網絡安全。

孫俊逸 男，1947年出生，教授。主要研究方向為計算機控制、虛擬現實。