蘇亞然，陳軍霞，牛習(xí)現(xiàn)

（1.河北科技大學(xué)經(jīng)濟管理學(xué)院，河北石家莊 050018；2.華北電力大學(xué)經(jīng)濟與管理學(xué)院，北京102206；3.河北青年管理干部學(xué)院信息技術(shù)與傳播系，河北石家莊 050031）

隨機種子最近鄰居搜索聚類算法研究

蘇亞然1，2，陳軍霞1，牛習(xí)現(xiàn)3

（1.河北科技大學(xué)經(jīng)濟管理學(xué)院，河北石家莊 050018；2.華北電力大學(xué)經(jīng)濟與管理學(xué)院，北京102206；3.河北青年管理干部學(xué)院信息技術(shù)與傳播系，河北石家莊 050031）

提出了隨機種子最近鄰居搜索（RS-NNS）聚類算法，該算法從隨機確定的種子開始沿著它最近鄰居的方向搜索具有最大相似特征的鄰居對象，形成局部最大聚類集合，并在搜索過程中動態(tài)調(diào)整數(shù)據(jù)對象的歸屬，以實現(xiàn)局部的最優(yōu)分配，直到所有的數(shù)據(jù)對象完成聚類標(biāo)識。經(jīng)過驗證，該算法可以適應(yīng)數(shù)據(jù)集合的密度、形狀、噪音、聚類個數(shù)等問題，并且相對于同類算法可以實現(xiàn)較快地優(yōu)化搜索。

最近鄰居搜索；隨機種子；聚類分析；數(shù)據(jù)挖掘

聚類作為一種重要的數(shù)據(jù)分析方法，已經(jīng)在模式識別、機器學(xué)習(xí)、數(shù)據(jù)挖掘、圖像處理、文檔分析、信息檢索、醫(yī)療圖像分析、市場研究、質(zhì)量控制和欺詐檢測等方面得到了廣泛應(yīng)用。數(shù)據(jù)聚類是一個探索和描述性數(shù)據(jù)分析的過程，并在這個過程中將相似的對象或數(shù)據(jù)進(jìn)行標(biāo)識和分組。聚類的任務(wù)是在沒有訓(xùn)練樣本的情況下，僅利用樣本間的相似性尋找樣本集針對某個評判準(zhǔn)則的最佳類別劃分［1－2］。聚類分析屬于無監(jiān)督學(xué)習(xí)問題，用來在無標(biāo)識的數(shù)據(jù)集合中發(fā)現(xiàn)其內(nèi)在結(jié)構(gòu)和聯(lián)系，將對象按照某方面的相似性進(jìn)行組織分組的過程，因此每個聚類都是對象的集合，并且具有很強的相似性，而不同聚類之間的對象則具有相對較弱的相似性或者不具有相似性［3］。在實現(xiàn)數(shù)據(jù)集合聚類分析的研究過程中，針對不同的數(shù)據(jù)類型和應(yīng)用目的，相關(guān)的研究人員對問題的關(guān)注方向也不盡相同，如對密度的適應(yīng)能力、形狀的適應(yīng)能力、噪音的檢測、邊界對象的識別、聚類個數(shù)的確定、聚類結(jié)果的準(zhǔn)確度、算法的優(yōu)化速度、高維數(shù)據(jù)的聚類問題，因此研究具有最大的適應(yīng)能力的聚類算法就成為聚類研究的重要方向之一。早期的聚類算法，如K-均值、K-中心點、FCM等，它們只對空間分布為球形或者超球體的數(shù)據(jù)具有較好的性能，而對空間分布復(fù)雜的數(shù)據(jù)聚類效果較差［1］，而且它們都需要預(yù)先設(shè)定聚類的個數(shù)?；诿芏鹊腄BSCAN算法，考慮到數(shù)據(jù)分布的密度特性，對具有不同形狀特征的數(shù)據(jù)集合有很好的適應(yīng)性，但是它的參數(shù)設(shè)置比較困難且無法適應(yīng)密度變化比較大的數(shù)據(jù)集合的數(shù)據(jù)分析任務(wù)。為了改進(jìn)聚類的結(jié)果和算法的適應(yīng)性，有些研究人員提出了基于SNN（shared nearest neighbours）相似性聚類分析算法如JP（jarvis-patrick）聚類算法，該類算法對數(shù)據(jù)對象集合的大密度變化以及任意形狀均具有較好的適應(yīng)性，但是該類算法需要完成較大量數(shù)據(jù)對象之間的相似性計算，算法的性能還有提高的空間，另外，對于計算對象相似性時的共享鄰居個數(shù)的設(shè)定需要相關(guān)領(lǐng)域的知識和經(jīng)驗。經(jīng)過對相關(guān)領(lǐng)域的聚類算法的綜合研究和驗證，筆者提出了隨機種子最近鄰居搜索（RS-NNS：random seed nearest neighbour search algorithm）聚類算法，該算法從隨機確定的種子開始沿徑向搜索具有最大相似特征的鄰居對象，并形成局部最大聚類集合，并在搜索過程中動態(tài)調(diào)整數(shù)據(jù)對象的歸屬，以實現(xiàn)局部的最優(yōu)分配，直到所有的數(shù)據(jù)對象完成聚類標(biāo)識。經(jīng)過驗證，該算法可以有效地適應(yīng)數(shù)據(jù)集合的密度、形狀、噪音、聚類個數(shù)等問題，并且相對于同類算法可以實現(xiàn)較快的優(yōu)化搜索。

1 相關(guān)領(lǐng)域問題的研究與分析

1.1 DBSCAN

DBSCAN（density-based spatial clustering of application with noise）是一種基于密度的聚類算法。該算法將具有足夠高的密度的區(qū)域劃分為簇，并在具有噪音的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的簇，它將簇定義成密度相連的點的最大集合［2］。在給定了核心點、邊界點和噪音點的定義以后，DBSCAN算法中Eps和MinPts 2個參數(shù)的設(shè)置對聚類結(jié)果的影響非常大，并且它們的選擇比較困難。DBSCAN算法的描述性定義如下：

1）把所有的數(shù)據(jù)對象標(biāo)記為核心點、邊界點或者噪音點；

2）忽略所有的噪音點對象；

3）按照Eps為每個核心點對象建立邊界；

4）把所有相互連接的核心點對象標(biāo)記為同一簇；

5）把每個邊界點分配到與它相關(guān)聯(lián)的核心點對象相同的簇。

DBSCAN的基于密度的簇的定義方式，使得該算法具有較強的抗噪音能力，并且能夠分析處理具有任意形狀和大小的簇的數(shù)據(jù)對象集合，因此能夠發(fā)現(xiàn)很多K-means算法不能處理的簇。然而DBSCAN算法也存在相應(yīng)的缺陷和不足：

1）當(dāng)分析處理的數(shù)據(jù)對象集合的分布密度有較大變化時，Eps和Min Pts參數(shù)的選擇將變得非常困難；

2）對高維數(shù)據(jù)對象集合分析時，密度的定義很難實現(xiàn)；

3）用于獲得近鄰對象的計算代價較大，跟高維數(shù)據(jù)集合的計算代價一樣［1］。

1.2 基于SNN相似性的JP聚類算法

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

1）對聚類分析的數(shù)據(jù)集合中的每個對象確定它的J個最近的鄰居；

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

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

2 隨機種子最近鄰居搜索聚類算法

數(shù)據(jù)分布密度、SNN相似性等測度方法的引入，使得復(fù)雜分布數(shù)據(jù)的結(jié)構(gòu)特點得到了較好的體現(xiàn)，對于大多數(shù)的數(shù)據(jù)聚類分析問題能達(dá)到較好的效果。但算法的性能，如自然密度變化的數(shù)據(jù)分布的識別、不規(guī)則形狀的數(shù)據(jù)分布的識別等仍然存在改進(jìn)和提升的空間，因此隨機徑向搜索算法試圖通過數(shù)據(jù)對象本身自然存在局部集聚特性以及數(shù)據(jù)對象的局部關(guān)聯(lián)特性，來實現(xiàn)對數(shù)據(jù)對象的最佳聚類和算法性能的提升。

2.1 算法的實現(xiàn)原理

數(shù)據(jù)對象的分布是有局部集聚特性的，否則就失去了聚類分析的意義。對于任意一個數(shù)據(jù)對象而言，不管它周圍的數(shù)據(jù)分布密度如何，總可以發(fā)現(xiàn)一些相對來說比較近的鄰居對象，基于數(shù)據(jù)分布局部集聚特性，可以認(rèn)為當(dāng)前數(shù)據(jù)對象以及它的最近的鄰居就可以構(gòu)成一個具有局部集聚特征的聚類。在現(xiàn)實世界中，各種對象之間的關(guān)系是可以傳遞的，所以可以認(rèn)為鄰居的鄰居之間也存在必然的關(guān)聯(lián)。基于以上基本思想，可以從一個任意的種子對象開始，沿著它的四周鄰居的徑向方向進(jìn)行關(guān)聯(lián)搜索，并在搜索過程中對參加擴展搜索的鄰居對象加以限制來實現(xiàn)局部數(shù)據(jù)對象的聚類發(fā)現(xiàn)，算法搜索的具體實現(xiàn)原理見圖1。在圖1中，從隨機選定的對象點A開始，沿著它的每個最近鄰居所在的方向開始搜索，符合條件的每個鄰居都會成為新的搜索種子，直到完成局部集合的最優(yōu)搜索過程，然后再隨機選取沒有標(biāo)識的數(shù)據(jù)對象，如數(shù)據(jù)對象B，展開另一個聚類的搜索過程，直到實現(xiàn)整個數(shù)據(jù)空間的搜索工作。這樣的搜索過程是通過鄰居對象逐漸展開的，并且包括了各種可能方向的搜索，因此它可以達(dá)到對任意形狀和密度變化的數(shù)據(jù)集合的有效適應(yīng)［7－8］。

2.2 算法的實現(xiàn)步驟

為了提高算法的適應(yīng)能力和聚類結(jié)果的準(zhǔn)確性，針對一些關(guān)鍵的技術(shù)細(xì)節(jié)問題，提出了以下解決方法。

1）弱關(guān)聯(lián)數(shù)據(jù)對象間的歸屬評判問題在聚類搜索的過程中，對于任意分布的數(shù)據(jù)對象，可能存在一些數(shù)據(jù)對象雖然屬于當(dāng)前對象的最近鄰居集合，但是該對象并不一定適合作為進(jìn)一步搜索的種子對象，因此需要采取一定的方法避免讓該類數(shù)據(jù)對象參加進(jìn)一步的聚類搜索。由于每個對象在其局部范圍內(nèi)都會存在相對較近的鄰居，這就為人們進(jìn)行判定提供了依據(jù)，可以認(rèn)為一個對象如果它的最近的鄰居多數(shù)都屬于當(dāng)前種子對象的鄰居集合或者不屬于當(dāng)前已經(jīng)標(biāo)識的數(shù)據(jù)集合，則可以認(rèn)為它不適合作為種子進(jìn)行進(jìn)一步的搜索。

2）已經(jīng)標(biāo)識的對象的最優(yōu)判定問題

在搜索過程中如果遇到已經(jīng)標(biāo)識的數(shù)據(jù)對象，應(yīng)該對它的歸屬做出最佳的判定。對于一個已經(jīng)被標(biāo)識的數(shù)據(jù)對象，如果在搜索過程中發(fā)現(xiàn)它的鄰居對象中歸屬于其他類型的聚類標(biāo)識占多數(shù)，則認(rèn)為它應(yīng)該標(biāo)識為其他聚類類別，以實現(xiàn)數(shù)據(jù)集合的局部最優(yōu)搜索。

3）初始種子對象選擇問題

在整個聚類過程中總會存在多次初始種子對象的選擇問題，如果它的選擇正好落在數(shù)據(jù)對象比較集中的區(qū)域，則可以完成高質(zhì)量的局部搜索，得到一個較好集聚的數(shù)據(jù)聚類，但是如果初始種子的選擇落在了邊界或噪音點上，則有可能得不到所預(yù)期的聚類結(jié)果，因此必須對種子對象的選取和搜索加以控制。如果當(dāng)前種子數(shù)據(jù)對象到它最近的2個鄰居的距離遠(yuǎn)遠(yuǎn)超出它的最近2個鄰居的距離，則認(rèn)為該種子對象為噪音數(shù)據(jù)或者停止對該種子的繼續(xù)搜索。

圖1 RS-NNS算法實現(xiàn)原理圖Fig.1 Principle of RS-NNS clustering algorithm

2.3 隨機種子最近鄰居搜索算法一般性描述

通過對相關(guān)聚類算法的研究，總結(jié)和分析了不同類型的數(shù)據(jù)集合的分布特點，在此基礎(chǔ)上設(shè)計了RSNNS聚類算法，算法的具體實現(xiàn)如下：

3 試驗與結(jié)果分析

為了對RS-NNS進(jìn)行驗證，用Java語言完成了相關(guān)的算法編程實現(xiàn)，將RS-NNS，DBSCAN，JP算法在大量的不同特性的人工合成數(shù)據(jù)集合上進(jìn)行了驗證工作，并對試驗的結(jié)果進(jìn)行了比較分析，試驗結(jié)果表明，筆者所提出的RS-NNS算法是有效的，能夠較好地適用各種類型的數(shù)據(jù)集合的聚類分析任務(wù)。該算法的設(shè)計、試驗運行的環(huán)境均為CPU Intel Pentium Dual Core 1.7 GHz、內(nèi)存2 GB的微型計算機。

3.1 算法性能的驗證與分析

為了能夠直觀地考察RS-NNS算法的性能，通過軟件方法生成了分別有100，250，500個數(shù)據(jù)對象的多組模擬數(shù)據(jù)集合，讓3個算法分別運行在不同大小的數(shù)據(jù)集合上，并取得它們運行的平均時間，它們對數(shù)據(jù)的處理性能如圖2所示，可以明顯看出RS-NNS算法相對于其他算法的優(yōu)越性。

3.2 算法對數(shù)據(jù)集合的適應(yīng)能力的驗證與分析

為了更好地說明該算法對于具有不同分布密度特點的數(shù)據(jù)集合的適應(yīng)能力，筆者選取了在試驗中具有代表性的數(shù)據(jù)集合進(jìn)行了測試。測試結(jié)果顯示，該算法對于不同密度分布的數(shù)據(jù)對象的適應(yīng)優(yōu)于DBSCAN，克服了DBSCAN必須由用戶指定靜態(tài)的密度參數(shù)的缺點，能夠正確地識別有較大差別的不同密度的數(shù)據(jù)集合中的自然形狀的聚類，如圖3所示。試驗結(jié)果表明該算法對于噪音數(shù)據(jù)的處理非常有效。

圖2 3種算法性能比較Fig.2 Performance comparison of three algorithms

圖3 RS-NNS算法的密度噪音適應(yīng)性分析圖Fig.3 RS-NNS adaptability of different density and noise

在聚類分析中，數(shù)據(jù)集合分布密度的變化，不一定是絕對的高密度和低密度，有可能會存在逐漸過渡的密度變化情形，這樣的數(shù)據(jù)對象的局部集聚往往也是合理的，因此在進(jìn)行聚類算法的設(shè)計時應(yīng)考慮對此類聚類數(shù)據(jù)的處理和分析。另外，聚類數(shù)據(jù)的分布不一定是球形或者其他規(guī)則的形狀，任意形狀的數(shù)據(jù)聚類的存在也非常廣泛。RS-NNS算法的設(shè)計充分考慮了以上數(shù)據(jù)分析的情況，使得它能夠很好地適應(yīng)密度逐漸變化以及任意形狀的聚類的分析任務(wù)，它的適應(yīng)性測試結(jié)果見圖4。另外通過大量的試驗表明，該算法同樣可以準(zhǔn)確地自動識別出數(shù)據(jù)集合中自然存在的聚類個數(shù)。

圖4 RS-NNS算法對逐漸變化密度、任意形狀、聚類個數(shù)適應(yīng)性分析圖Fig.4 RS-NNS adaptability of gradually changed density，arbitrary shape and cluster number

4 結(jié) 語

筆者對當(dāng)前流行的聚類算法（如DBSCAN和JP等）以及不同算法所針對的數(shù)據(jù)分布特點進(jìn)行了綜合分析，針對這些算法的局限性提出了RS-NNS算法。測試了不同算法在相同數(shù)據(jù)集合上的運行，RS-NNS算法通過簡化數(shù)據(jù)處理過程，取得了明顯的運算優(yōu)勢。另外，RS-NNS算法針對不同類型的數(shù)據(jù)集合也表現(xiàn)出了良好的適應(yīng)性，它可以準(zhǔn)確地識別不同密度、逐漸過渡的密度變化以及任意形狀的數(shù)據(jù)對象的聚類集合。

［1］公茂果，王 爽，馬 萌，等.復(fù)雜分布數(shù)據(jù)的二階段聚類算法［J］.軟件學(xué)報（Journal of Software），2011，22（11）：2 760-2 771.

［2］LEE J S.Sigurdur olafsson data clustering by minimizing disconnectivity［J］.Information Sciences，2011，181：732-746.

［3］牛習(xí)現(xiàn)，趙立川.利用局部集聚特性的聚類算法的研究［J］.河北科技大學(xué)學(xué)報（Journal of Hebei University of Science and Technology），2011，32（5）：466-470.

［4］JIM Z C，LAI A，HUANG T J.An agglomerative clustering algorithm using a dynamick-nearest-neighbor list［J］.Information Sciences，2011，181：1 722-1 734.

［5］GONZALEZ-BARRIOS J M，QUIROZ A J.A clustering procedure based on the comparison between theknearest neighbors graph and the minimal spanning tree［J］.Statistics ＆ Probability Letters，2003，62（1）：23-34.

［6］NOHA A Y，MOHAMED S K，MOHAMED A I.A distance-relatedness dynamic model for clustering high dimensional data of arbitrary shapes and densities［J］.Pattern Recognition，2009，42：1 193-1 209.

［7］儲岳中，徐 波.動態(tài)最近鄰聚類算法的優(yōu)化研究［J］.計算機工程與設(shè)計（Computer Engineering and Design），2011，32（5）：1 687-1 690.

［8］王 茜，楊正寬.一種基于加權(quán)KNN的大數(shù)據(jù)集下離群檢測算法［J］.計算機科學(xué)（Journal of Computer Science ＆Technology），2011，38（10）：177-180.

Study on random seed nearest neighbour search clustering algorithm

SU Ya-ran1，2，CHEN Jun-xia1，NIU Xi-xian3
（1.College of Economics and Management，Hebei University of Science and Technology，Shijiazhuang Hebei 050018，China；2.College of Economics and Management，North China Electric Power University，Beijing 102206，China；3.Faculty of Information Technology and Propagation，Hebei Youth Administrative Cadres College，Shijiazhuang Hebei 050031，China）

This paper presents a random seed nearest neighbour search clustering algorithm （RS-NNS）.The method is to follow the nearest neighbours＇direction of a random selected seed，search and find its neighbours which have the greatest similar features，form the local maximum cluster，adjust dynamically the data objects＇belongingness to realize the local optimization，and end the clustering procedure until all the data objects are identified.Experiments verify that the new algorithm fits the problems such as different density，shape，noise，cluster number and so on，and can realize fast optimization searching.

nearest neighbour search；random seed；clustering analysis；data mining

TP301

A

1008-1542（2012）04-0338-05

2011-12-30；責(zé)任編輯：李 穆

河北省社會科學(xué)基金資助項目（HB12YJ064）

蘇亞然（1972-），女，河北靈壽人，講師，主要從事技術(shù)經(jīng)濟方面的研究。