利用局部集聚特性的聚類算法的研究

牛習現，趙立川

（1.河北青年管理干部學院信息技術與傳播系，河北石家莊 050031；2.河北科技大學后勤集團，河北石家莊 050018）

利用局部集聚特性的聚類算法的研究

牛習現1，趙立川2

（1.河北青年管理干部學院信息技術與傳播系，河北石家莊 050031；2.河北科技大學后勤集團，河北石家莊 050018）

基于SNN相似性和密度的聚類算法是當前主要的無監督聚類方法之一，該類算法在發現不同大小形狀簇的聚類過程中都取得了較好的結果。但是該類算法也存在局限性，如Jarvis-Patrick算法通過單連結的方式發現簇，可能分割真正的簇或者合并應該保持分離的簇，而SNN密度類算法的Eps，MinPts參數的確定對用戶來說是比較困難的。針對該類問題，本文對聚類過程中的局部集聚特征進行了分析和定義，提出了利用數據的局部集聚特征來控制聚類過程的的聚類算法。通過驗證，該算法對發現不同密度以及任意形狀的數據集合的聚類分析問題是有效的，突出了數據分析的局部集聚特征，改進了數據聚類的質量。

數據挖掘；聚類分析；局部集聚特性；SNN密度

聚類分析是人類的基本概念性活動之一，而人類自發的聚類分析過程通常是基于相對較少的選擇屬性進行的，并且不能排除人的偏見。因此當分析的對象集合是由相當數量的定量屬性來修飾定義，并且想要獲得無人為偏見干擾的分析結果時，就不可避免地使用了數學工具。但是數學工具的使用也具有局限性，因為數學工具的選擇和解決方案都是由人選擇和決定的，有特定的傾向性［1］。聚類分析是數據挖掘的方法之一，用來在無標識的數據集合中發現其內在結構和聯系，將對象按照某方面的相似性進行組織分組的過程，因此每個聚類都是對象的集合，并且他們之間具有相對強的相似性，而不同聚類之間對象則具有相對較弱的相似性或者不具有相似性［2］。針對不同的數據類型、數據集合的大小、對象的屬性個數以及想要發現聚類的類型等，相關研究人員設計實現了很多卓有成效的分析算法，其主要算法如下：K均值法、Chameleon法、STING法、SOM 法、SNN Density Based Methods法、Jarvis-Patrick法等聚類分析的方法［2－3］。本文的研究以 SNN密度和SNN相似性分析方法過程中數據局部集聚特征為基礎，旨在通過對已有相關算法的研究分析，找出解決其局限性的途徑，設計新的聚類算法，增強算法的適應性以及改進聚類分析的質量。

1 SNN相似性與SNN密度分析

通常將聚類分析定義成應用技術手段將對象集合分割成不同的分組，在同一分組中的對象比不屬于同一分組中的對象具有更強的相似性，因此在這個意義上聚類是發現相互之間具有相似性的對象的分組過程。然而聚類的這種定義并不是通用的，在很多情況下讓屬于同一分組的對象相互之間具有較強的相似性并不是必須的，取而代之的是，這些對象之間表現出來較高的連接特性，它可以被認為是相互近鄰的對象之間的關聯屬性，以相互連接或序列模式體現。因此一些并不具備直接相似性的對象被不間斷的鄰近的對象連接起來形成完整的集聚簇。進而可以得到更為一般化的聚類分析的定義，即它是一種通過給定的模型或相似性度量方法對異構不統一的項目集合進行確認同質子集的數據分析的技術。而這樣的數據子集的特征定義可以通過SNN密度和SNN相似性來體現［1］。

在一些情況下，依賴于標準相似性和密度度量方法的聚類分析技術不能夠產生合適的聚類結果，因此應該分析原因找到其他相似性的度量方法，通常可以認為，如果2個數據對象同時與許多共同的數據對象具有較高相似性，即使是通過直接的度量方法不能體現出它們之間具有相似性，那么它們之間也會具有較高的相似性，是因為對象之間的關系具有傳遞性。這正是SNN相似性度量的基礎依據。SNN度量方法可以解決低相似性數據對象（如文檔類對象集合）和密度分布不均勻數據集合的聚類分析問題［3］。SNN相似性計算的描述算法如下。

1）發現所有數據對象的k個最近鄰居。

2）如果2個數據對象x和y不存在于對方的k個最近鄰居列表中，則有：

similarity（x，y）＝＝0；否則similarity（x，y）＝＝共享鄰居數。

由于SNN相似性度量方法反應了數據空間中局部數據對象的分布特性，并且該方法相對于數據空間中密度的變化以及維度的變化不敏感，使得它成為基于密度的度量方法的新選擇。SNN密度方法給出了數據對象被相似對象包圍的程度，因此數據對象所處區域的密度的高低變化是和SNN密度一致的。該類方法可以很好地適應具有較大范圍密度變化的數據集合，同時仍然可以發現低密度的簇。依據SNN密度確定對象類別的方法描述如下。

核心對象：如果1個數據對象的鄰居數在SNN相似性定義以及用戶提供的參數Eps的條件下超出了另一個提供參數MinPts閾值，則標記該對象為核心對象。

邊界對象：如果1個數據對象周圍沒有足夠的鄰居使它成為核心對象，但是卻是某一個核心對象的近鄰，這樣的對象稱為邊界對象。

噪音對象：既不是核心對象也不是邊界對象的其他數據對象［3］。

2 現有相關算法分析

2.1 基于SNN相似性的Jarvis-Patrick算法

基于SNN相似性算法的基本思想是：如果2個數據對象與其他許多相同的數據對象具有相似性，盡管直接的相似性度量方法可能確定不了這種相似性，但是這2個數據對象之間的相似性是成立的。SNN相似性定義為具有低密度或者密度變化較大特征的數據集合的聚類分析提供了可行的思路。JP（Jarvis-Patrick）算法通過最近共享鄰居方法進行對象聚類，該算法的執行需要確定數據對象之間距離的度量方法以及2個參數J和K，J是最近鄰居列表的大小，K是共享鄰居的個數。該算法的描述如下：

1）對聚類分析的數據集合中的每一個對象確定它的J個最近的鄰居。

2）把符合條件的對象分配到同一個簇中，它們相互包含在對方的最近鄰居列表中，并且至少擁有K個共享的鄰居對象。

因為JP聚類算法是基于SNN相似性概念的，所以它能夠處理帶有噪聲、邊界的數據集合的數據分析任務并且能夠發現不同大小、形狀和密度的數據對象簇；該算法對于高維數據的分析處理、特別是對于具有強關聯性的結合緊密的簇的發現也是非常有效的。然而，JP算法把簇定義為在SNN相似圖中相連接的對象集合，通過對單連結的判定來決定是否對一個對象集合進行分割或保留為一個簇，因此JP聚類算法在一定意義上是脆弱的，它可能分割真正的簇或者合并應該保持分離的簇。另外，JP算法不能實現對象的完全聚類，最佳參數的選擇也較困難［2－3，5］。

2.2 基于SNN密度的聚類算法分析

因為SNN相似性反映了數據對象在數據空間中的局部分布特征，它對數據空間中密度和維度的變化具有相對較好的適應性，因此選擇它作為新的密度度量的方法是非常有意義的。SNN密度方法通過數據對象周圍的相似對象的個數來確定數據空間的密度，則一個局部對象空間的密度的高低可以通過它的SNN密度來反映，這樣的方法對于具有較大范圍密度變化的數據空間具有較好的適應性，并且對低密度的簇仍然具有較好的反應能力。將SNN密度方法和DBSCAN（density-based spatial clustering of application with noise）結合可以生成新的聚類算法，新算法跟JP算法一樣以SNN相似圖開始，通過閾值來完成SNN相似圖的疏化并且把相連接的對象分配到相同的簇。基于SNN密度的算法描述如下：

a）計算數據空間的SNN相似圖；

b）根據用戶選定的Eps和MinPts參數應用DBSCAN算法進行聚類運算。

該算法可以自動的確定數據集合中簇的個數，在聚類過程中會拋棄掉噪音、邊界以及非強連接的數據對象，適合于處理與文檔相關的聚類問題，比如WEB數據挖掘問題等。SNN密度和核心對象的定義增強了算法的適應能力和靈活性。該算法的局限性與JP算法類似，另外讓用戶選定合適的Eps以及MinPts參數是較困難的［2－3］。

3 基于局部集聚特征的聚類算法

SNN相似性度量方法以及SNN密度度量方法，都是基于數據空間中對象的局部分布特性來考慮的，主要考慮算法對數據空間中簇的密度、形狀等問題的適應能力。而基于局部集聚特征的聚類算法主要關注于數據空間中數據對象的局部集聚特征的分析和應用，分析數據對象周圍的共享鄰居的形狀、大小、密度等局部集聚特征，并以此重新定義數據對象的相似性和密度等度量方法，進而提高算法的適應能力和優化的效率。數據對象之間的共享鄰居本身就是一個局部的數據對象簇，相對于周圍其他的數據對象而言具有較強的集聚特性，研究它的數據分布特征，對于確定數據對象的相似性和密度是非常有意義的工作。

3.1 基于局部集聚特性的相似性分析

由于JP算法采用輸入參數k作為數據對象相似性計算的閾值條件，對于具有較強集聚特性的局部小的數據集合的發現是不利的，如圖1a）所示，當參數k設定為6時，盡管它們之間局部分布是較為疏遠的，數據對象A和B將被分配到同一簇中。另外基于SNN密度的算法采用輸入參數Eps作為限定參數去度量數據對象的相似性，所以數據集合局部配置的形狀大小等特性的考慮對于發現具有較強集聚特性的局部簇也是非常有用的，如圖1b）所示，對象A和B在局部配置上是較為松散的，但是卻在Eps的限定范圍內，而數據對象C相較于對象A而言與對象B具有更強的連接性，盡管這種連接不是直接的。

為了更好的利用數據分布的局部特性實現對數據對象相似性度量，被SNN評估的兩個對象之間的相似性可以通過以下幾個方面來體現，比如被評估對象之間的局部共享鄰居是否擁有相對較高的密度、相對于共享鄰居的分布形狀來說是否具有相對較近距離等，如果上述指標達到了用戶預期，則可以認為在局部范圍內被評估對象之間具有較高的相似性。

圖1 數據對象局部分布特性Fig.1 Local characteristics of data object

3.2 局部集聚特征定義和度量方法

局部共享鄰居中所有的數據對象相對于其他數據對象而言可以看作一個具有較強集聚特性的完整的簇。因此可以把它的局部集聚特性作為衡量2個具有相同共享鄰居的數據對象是否具有較高相似性的依據。簡單的來考慮，在局部數據區域，如果2個數據對象具有相對近的距離，則可以認為它們具有較高的相似性。因為數據對象的分布可能存在較大的變化，為了動態確定什么是相對于局部區域比較近的距離，需要對局部數據的分布特性進行分析，如局部簇分布形狀、大小和密度等特征。共享鄰居簇的大小作為參數由用戶根據分析處理的數據類型設定，因此局部數據集聚特征可以簡化為局部形狀和局部密度的表示，其中密度可以由所有共享鄰居簇的成員的平均距離LAD（local average distance）來衡量。由于局部數據分布的任意性，其分布形狀的度量方法可以簡化為2個主要的方面，局部最大距離LMD（local maximum distance）和局部徑向距離LRD（local radial distance）（如圖2所示）。局部數據特征的定義如下：

其中：CSNN是共享鄰居的集合；n是CSNN中數據對象的個數；Line X定義為穿過具有最大距離的2個對象點的直線。

3.3 基于局部集聚特征的聚類算法

通過對不同基于密度的聚類算法的分析研究，為了更好地適應不同類型的數據對象集合，結合對數據對象局部集聚特征的定義，在JP算法和基于SNN密度算法的基礎上，提出了新的聚類算法，即基于局部集聚特征的聚類分析算法，該算法在主要步驟上與JP算法相似，但是把數據集合的局部分布特性作為參考，使用LMD和LAD作為動態閾值去控制SNN相似性的計算。基于局部集聚特性的聚類算法的實現步驟描述如下。

第1步：通過LAD閾值的控制計算數據對象的相似矩陣。對于每一對數據對象，掃描數據集合建立它們的共享鄰居集合，則可以把共享鄰居的K個對象看作是一個具有較強集聚特性的局

部簇，然后計算K個數據對象的平均距離作為局部的動態閾值去控制相似圖的生成。

第2步：應用相似性閾值去發現相互連接的對象集合，并同時動態的調整簇的成員對象的隸屬關系。應用相似性閾值疏化簇連接關系圖能夠簡化相似性計算和改進算法發現簇的效率。在完成簇的疏化工作后，需要相應的方法去發現和展示對象連接關系圖中存在的簇，連接對象集合的發現方法的描述性偽代碼如下：

圖2 共享鄰居簇局部特征分析圖Fig.2 Map of local characteristics analysis

3.4 算法的實驗結果與評估

在聚類分析中，幾乎所有的聚類算法都會在數據對象集合中發現簇，不管相關數據集合中的對象是否存在自然的簇結構，因此對聚類結果的評估是一項非常重要的工作。每一種聚類算法都會定義它自己的適合目標數據集合的發現簇的類型，所以對于不同的聚類分析算法需要定義相應合適的發現簇的評價的方法。基于距離的相似定義的優勢是容易理解和計算，對于基礎類聚類算法的研究評價，采用該類相似性定義是很好的選擇，兩個簇相似性定義方式可以有以下方式［6］：

本文設計的聚類算法由于采取了與JP方法以及SNN密度算法相似的數據處理步驟和數據存儲結構，因此它的實現在時間和空間復雜度上與它們相同，不會額外增加系統開銷。為了測試該算法的聚類效果以及準確性，采用隨機分布和合成的數據對象集合作為測試數據集合，部分數據對象如表1所示。設定相同的初始條件，對同一組數據對象分別應用JP，SNN密度以及基于局部特征的聚類算法，其實驗結果如表2所示，通過對不同聚類算法的在同一數據對象集合上的聚類結果進行比較，發現該算法在分析處理具有自然分布的數據對象集合時能夠得到更好集聚的簇，因此改善了聚類的質量。

表1 部分實驗數據Tab.1 Part of experimental data set

表2 實驗結果Tab.2 Experimental result

4 結 論

在對相關領域已有的算法進行綜合研究的基礎上，為了能夠更好地提取和表達數據對象的局部集聚特征，筆者對聚類分析中數據的局部集聚特征進行了詳盡的分析和定義，分析了其應用依據，并提出了基于局部集聚特征的改進的聚類分析算法，該算法對于不同密度以及形狀的目標數據集合均有很好的適應性。將該算法應用到隨機分布和合成的數據對象集合上進行聚類分析，能夠準確地發現自然分布的簇以及在局部有較強集聚特性的較小的簇。相較于其他相關算法而言，該算法的實現沒有提高時間和空間復雜度，由于強化了數據對象局部分布特征的應用，進而改善了聚類的質量。

［1］ ALMEIDA J A S，BARBOSA L M S，PAIS A A C C，et al.Improving hierarchical cluster analysis：A new method with outlier detection and automatic clustering［J］.Chemometrics and Intelligent Laboratory Systems，2007，87：208-217.

［2］ HAN Jia-wei，KAMBER M.數據挖掘概念與技術［M］.第2版.北京：機械工業出版社，2007.251-299.

［3］ TAN Pang-ning，STEINBACH M，KUMAR V.數據挖掘導論［M］.北京：人民郵電出版社，2006.

［4］ TONNY J O.A new-fangled FES-k-means clustering algorithm for disease discovery and visual analytics［J］.Eurasip Journal on Bioinformatics and Systems Biology，2010（4）：1-14.

［5］ FERNANDO C，RICHARD W.A methodology for dynamic data mining based on fuzzy dustering［J］.Fuzzy sets and System，2005，150：267-284.

［6］ QIAN Wei-ning，ZHUO Ao-ying.Analyzing popular clustering algorithms from different viewpoints［J］.Journal of Software，2002，13（8）：1 382-1 394.

Research in clustering algorithm based on local agglomerative characteristics

NIU Xi-xian1，ZHAO Li-chuan2
（1.Faculty of Information Technology and Propagation，Hebei Youth Administrative Cadres College，Shijiazhuang Hebei 050031，China；2.Logistics Group，Hebei University of Science and Technology，Shijiazhuang Hebei 050018，China）

The SNN similarity and density based clustering，as one of the most important unsupervised clustering method，has been proved to produce good results in finding clusters of various sizes and shapes.But these algorithms still have some limitations.For example，Jarvis-Patrick scheme of finding clusters by single link，may separate real clusters or merge clusters which should be kept separated in certain situations，and the determination of Eps and MinPts，the parameters of SNN density method，is hard for users.To deal with these problems，the paper gives analysis and definition of local agglomerative characteristics presented in clustering procedure；then proposes a new clustering algorithm which use local gathering features to control clustering progress.The algorithm can work well in finding different size and density clusters，highlighting the local features of data analysis and improving the quality of data clusters.

data mining；clustering；local agglomerative characteristics；SNN density

TP301

A

1008-1542（2011）05-0466-05

2011-04-02；

2011-08-28；責任編輯:張 軍

牛習現（1972-），男，河北贊皇人，講師，碩士，主要從事數據挖掘、網絡管理方面的研究。