利用局部集聚特性的聚類(lèi)算法的研究

牛習(xí)現(xiàn)，趙立川

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

利用局部集聚特性的聚類(lèi)算法的研究

牛習(xí)現(xiàn)1，趙立川2

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

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

數(shù)據(jù)挖掘；聚類(lèi)分析；局部集聚特性；SNN密度

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

1 SNN相似性與SNN密度分析

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

在一些情況下，依賴(lài)于標(biāo)準(zhǔn)相似性和密度度量方法的聚類(lèi)分析技術(shù)不能夠產(chǎn)生合適的聚類(lèi)結(jié)果，因此應(yīng)該分析原因找到其他相似性的度量方法，通常可以認(rèn)為，如果2個(gè)數(shù)據(jù)對(duì)象同時(shí)與許多共同的數(shù)據(jù)對(duì)象具有較高相似性，即使是通過(guò)直接的度量方法不能體現(xiàn)出它們之間具有相似性，那么它們之間也會(huì)具有較高的相似性，是因?yàn)閷?duì)象之間的關(guān)系具有傳遞性。這正是SNN相似性度量的基礎(chǔ)依據(jù)。SNN度量方法可以解決低相似性數(shù)據(jù)對(duì)象（如文檔類(lèi)對(duì)象集合）和密度分布不均勻數(shù)據(jù)集合的聚類(lèi)分析問(wèn)題［3］。SNN相似性計(jì)算的描述算法如下。

1）發(fā)現(xiàn)所有數(shù)據(jù)對(duì)象的k個(gè)最近鄰居。

2）如果2個(gè)數(shù)據(jù)對(duì)象x和y不存在于對(duì)方的k個(gè)最近鄰居列表中，則有：

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

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

核心對(duì)象：如果1個(gè)數(shù)據(jù)對(duì)象的鄰居數(shù)在SNN相似性定義以及用戶(hù)提供的參數(shù)Eps的條件下超出了另一個(gè)提供參數(shù)MinPts閾值，則標(biāo)記該對(duì)象為核心對(duì)象。

邊界對(duì)象：如果1個(gè)數(shù)據(jù)對(duì)象周?chē)鷽](méi)有足夠的鄰居使它成為核心對(duì)象，但是卻是某一個(gè)核心對(duì)象的近鄰，這樣的對(duì)象稱(chēng)為邊界對(duì)象。

噪音對(duì)象：既不是核心對(duì)象也不是邊界對(duì)象的其他數(shù)據(jù)對(duì)象［3］。

2 現(xiàn)有相關(guān)算法分析

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

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

1）對(duì)聚類(lèi)分析的數(shù)據(jù)集合中的每一個(gè)對(duì)象確定它的J個(gè)最近的鄰居。

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

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

2.2 基于SNN密度的聚類(lèi)算法分析

因?yàn)镾NN相似性反映了數(shù)據(jù)對(duì)象在數(shù)據(jù)空間中的局部分布特征，它對(duì)數(shù)據(jù)空間中密度和維度的變化具有相對(duì)較好的適應(yīng)性，因此選擇它作為新的密度度量的方法是非常有意義的。SNN密度方法通過(guò)數(shù)據(jù)對(duì)象周?chē)南嗨茖?duì)象的個(gè)數(shù)來(lái)確定數(shù)據(jù)空間的密度，則一個(gè)局部對(duì)象空間的密度的高低可以通過(guò)它的SNN密度來(lái)反映，這樣的方法對(duì)于具有較大范圍密度變化的數(shù)據(jù)空間具有較好的適應(yīng)性，并且對(duì)低密度的簇仍然具有較好的反應(yīng)能力。將SNN密度方法和DBSCAN（density-based spatial clustering of application with noise）結(jié)合可以生成新的聚類(lèi)算法，新算法跟JP算法一樣以SNN相似圖開(kāi)始，通過(guò)閾值來(lái)完成SNN相似圖的疏化并且把相連接的對(duì)象分配到相同的簇?；赟NN密度的算法描述如下：

a）計(jì)算數(shù)據(jù)空間的SNN相似圖；

b）根據(jù)用戶(hù)選定的Eps和MinPts參數(shù)應(yīng)用DBSCAN算法進(jìn)行聚類(lèi)運(yùn)算。

該算法可以自動(dòng)的確定數(shù)據(jù)集合中簇的個(gè)數(shù)，在聚類(lèi)過(guò)程中會(huì)拋棄掉噪音、邊界以及非強(qiáng)連接的數(shù)據(jù)對(duì)象，適合于處理與文檔相關(guān)的聚類(lèi)問(wèn)題，比如WEB數(shù)據(jù)挖掘問(wèn)題等。SNN密度和核心對(duì)象的定義增強(qiáng)了算法的適應(yīng)能力和靈活性。該算法的局限性與JP算法類(lèi)似，另外讓用戶(hù)選定合適的Eps以及MinPts參數(shù)是較困難的［2－3］。

3 基于局部集聚特征的聚類(lèi)算法

SNN相似性度量方法以及SNN密度度量方法，都是基于數(shù)據(jù)空間中對(duì)象的局部分布特性來(lái)考慮的，主要考慮算法對(duì)數(shù)據(jù)空間中簇的密度、形狀等問(wèn)題的適應(yīng)能力。而基于局部集聚特征的聚類(lèi)算法主要關(guān)注于數(shù)據(jù)空間中數(shù)據(jù)對(duì)象的局部集聚特征的分析和應(yīng)用，分析數(shù)據(jù)對(duì)象周?chē)墓蚕磬従拥男螤?、大小、密度等局部集聚特征，并以此重新定義數(shù)據(jù)對(duì)象的相似性和密度等度量方法，進(jìn)而提高算法的適應(yīng)能力和優(yōu)化的效率。數(shù)據(jù)對(duì)象之間的共享鄰居本身就是一個(gè)局部的數(shù)據(jù)對(duì)象簇，相對(duì)于周?chē)渌臄?shù)據(jù)對(duì)象而言具有較強(qiáng)的集聚特性，研究它的數(shù)據(jù)分布特征，對(duì)于確定數(shù)據(jù)對(duì)象的相似性和密度是非常有意義的工作。

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

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

為了更好的利用數(shù)據(jù)分布的局部特性實(shí)現(xiàn)對(duì)數(shù)據(jù)對(duì)象相似性度量，被SNN評(píng)估的兩個(gè)對(duì)象之間的相似性可以通過(guò)以下幾個(gè)方面來(lái)體現(xiàn)，比如被評(píng)估對(duì)象之間的局部共享鄰居是否擁有相對(duì)較高的密度、相對(duì)于共享鄰居的分布形狀來(lái)說(shuō)是否具有相對(duì)較近距離等，如果上述指標(biāo)達(dá)到了用戶(hù)預(yù)期，則可以認(rèn)為在局部范圍內(nèi)被評(píng)估對(duì)象之間具有較高的相似性。

圖1 數(shù)據(jù)對(duì)象局部分布特性Fig.1 Local characteristics of data object

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

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

其中：CSNN是共享鄰居的集合；n是CSNN中數(shù)據(jù)對(duì)象的個(gè)數(shù)；Line X定義為穿過(guò)具有最大距離的2個(gè)對(duì)象點(diǎn)的直線(xiàn)。

3.3 基于局部集聚特征的聚類(lèi)算法

通過(guò)對(duì)不同基于密度的聚類(lèi)算法的分析研究，為了更好地適應(yīng)不同類(lèi)型的數(shù)據(jù)對(duì)象集合，結(jié)合對(duì)數(shù)據(jù)對(duì)象局部集聚特征的定義，在JP算法和基于SNN密度算法的基礎(chǔ)上，提出了新的聚類(lèi)算法，即基于局部集聚特征的聚類(lèi)分析算法，該算法在主要步驟上與JP算法相似，但是把數(shù)據(jù)集合的局部分布特性作為參考，使用LMD和LAD作為動(dòng)態(tài)閾值去控制SNN相似性的計(jì)算?；诰植考厶匦缘木垲?lèi)算法的實(shí)現(xiàn)步驟描述如下。

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

部簇，然后計(jì)算K個(gè)數(shù)據(jù)對(duì)象的平均距離作為局部的動(dòng)態(tài)閾值去控制相似圖的生成。

第2步：應(yīng)用相似性閾值去發(fā)現(xiàn)相互連接的對(duì)象集合，并同時(shí)動(dòng)態(tài)的調(diào)整簇的成員對(duì)象的隸屬關(guān)系。應(yīng)用相似性閾值疏化簇連接關(guān)系圖能夠簡(jiǎn)化相似性計(jì)算和改進(jìn)算法發(fā)現(xiàn)簇的效率。在完成簇的疏化工作后，需要相應(yīng)的方法去發(fā)現(xiàn)和展示對(duì)象連接關(guān)系圖中存在的簇，連接對(duì)象集合的發(fā)現(xiàn)方法的描述性偽代碼如下：

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

3.4 算法的實(shí)驗(yàn)結(jié)果與評(píng)估

在聚類(lèi)分析中，幾乎所有的聚類(lèi)算法都會(huì)在數(shù)據(jù)對(duì)象集合中發(fā)現(xiàn)簇，不管相關(guān)數(shù)據(jù)集合中的對(duì)象是否存在自然的簇結(jié)構(gòu)，因此對(duì)聚類(lèi)結(jié)果的評(píng)估是一項(xiàng)非常重要的工作。每一種聚類(lèi)算法都會(huì)定義它自己的適合目標(biāo)數(shù)據(jù)集合的發(fā)現(xiàn)簇的類(lèi)型，所以對(duì)于不同的聚類(lèi)分析算法需要定義相應(yīng)合適的發(fā)現(xiàn)簇的評(píng)價(jià)的方法。基于距離的相似定義的優(yōu)勢(shì)是容易理解和計(jì)算，對(duì)于基礎(chǔ)類(lèi)聚類(lèi)算法的研究評(píng)價(jià)，采用該類(lèi)相似性定義是很好的選擇，兩個(gè)簇相似性定義方式可以有以下方式［6］：

本文設(shè)計(jì)的聚類(lèi)算法由于采取了與JP方法以及SNN密度算法相似的數(shù)據(jù)處理步驟和數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，因此它的實(shí)現(xiàn)在時(shí)間和空間復(fù)雜度上與它們相同，不會(huì)額外增加系統(tǒng)開(kāi)銷(xiāo)。為了測(cè)試該算法的聚類(lèi)效果以及準(zhǔn)確性，采用隨機(jī)分布和合成的數(shù)據(jù)對(duì)象集合作為測(cè)試數(shù)據(jù)集合，部分?jǐn)?shù)據(jù)對(duì)象如表1所示。設(shè)定相同的初始條件，對(duì)同一組數(shù)據(jù)對(duì)象分別應(yīng)用JP，SNN密度以及基于局部特征的聚類(lèi)算法，其實(shí)驗(yàn)結(jié)果如表2所示，通過(guò)對(duì)不同聚類(lèi)算法的在同一數(shù)據(jù)對(duì)象集合上的聚類(lèi)結(jié)果進(jìn)行比較，發(fā)現(xiàn)該算法在分析處理具有自然分布的數(shù)據(jù)對(duì)象集合時(shí)能夠得到更好集聚的簇，因此改善了聚類(lèi)的質(zhì)量。

表1 部分實(shí)驗(yàn)數(shù)據(jù)Tab.1 Part of experimental data set

表2 實(shí)驗(yàn)結(jié)果Tab.2 Experimental result

4 結(jié) 論

在對(duì)相關(guān)領(lǐng)域已有的算法進(jìn)行綜合研究的基礎(chǔ)上，為了能夠更好地提取和表達(dá)數(shù)據(jù)對(duì)象的局部集聚特征，筆者對(duì)聚類(lèi)分析中數(shù)據(jù)的局部集聚特征進(jìn)行了詳盡的分析和定義，分析了其應(yīng)用依據(jù)，并提出了基于局部集聚特征的改進(jìn)的聚類(lèi)分析算法，該算法對(duì)于不同密度以及形狀的目標(biāo)數(shù)據(jù)集合均有很好的適應(yīng)性。將該算法應(yīng)用到隨機(jī)分布和合成的數(shù)據(jù)對(duì)象集合上進(jìn)行聚類(lèi)分析，能夠準(zhǔn)確地發(fā)現(xiàn)自然分布的簇以及在局部有較強(qiáng)集聚特性的較小的簇。相較于其他相關(guān)算法而言，該算法的實(shí)現(xiàn)沒(méi)有提高時(shí)間和空間復(fù)雜度，由于強(qiáng)化了數(shù)據(jù)對(duì)象局部分布特征的應(yīng)用，進(jìn)而改善了聚類(lèi)的質(zhì)量。

［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.數(shù)據(jù)挖掘概念與技術(shù)［M］.第2版.北京：機(jī)械工業(yè)出版社，2007.251-299.

［3］ TAN Pang-ning，STEINBACH M，KUMAR V.數(shù)據(jù)挖掘?qū)д摚跰］.北京：人民郵電出版社，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；責(zé)任編輯:張 軍

牛習(xí)現(xiàn)（1972-），男，河北贊皇人，講師，碩士，主要從事數(shù)據(jù)挖掘、網(wǎng)絡(luò)管理方面的研究。