蘇亞然,陳軍霞,牛習(xí)現(xiàn)
(1.河北科技大學(xué)經(jīng)濟(jì)管理學(xué)院,河北石家莊 050018;2.華北電力大學(xué)經(jīng)濟(jì)與管理學(xué)院,北京102206;3.河北青年管理干部學(xué)院信息技術(shù)與傳播系,河北石家莊 050031)
隨機(jī)種子最近鄰居搜索聚類算法研究
蘇亞然1,2,陳軍霞1,牛習(xí)現(xiàn)3
(1.河北科技大學(xué)經(jīng)濟(jì)管理學(xué)院,河北石家莊 050018;2.華北電力大學(xué)經(jīng)濟(jì)與管理學(xué)院,北京102206;3.河北青年管理干部學(xué)院信息技術(shù)與傳播系,河北石家莊 050031)
提出了隨機(jī)種子最近鄰居搜索(RS-NNS)聚類算法,該算法從隨機(jī)確定的種子開始沿著它最近鄰居的方向搜索具有最大相似特征的鄰居對(duì)象,形成局部最大聚類集合,并在搜索過程中動(dòng)態(tài)調(diào)整數(shù)據(jù)對(duì)象的歸屬,以實(shí)現(xiàn)局部的最優(yōu)分配,直到所有的數(shù)據(jù)對(duì)象完成聚類標(biāo)識(shí)。經(jīng)過驗(yàn)證,該算法可以適應(yīng)數(shù)據(jù)集合的密度、形狀、噪音、聚類個(gè)數(shù)等問題,并且相對(duì)于同類算法可以實(shí)現(xiàn)較快地優(yōu)化搜索。
最近鄰居搜索;隨機(jī)種子;聚類分析;數(shù)據(jù)挖掘
聚類作為一種重要的數(shù)據(jù)分析方法,已經(jīng)在模式識(shí)別、機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、圖像處理、文檔分析、信息檢索、醫(yī)療圖像分析、市場研究、質(zhì)量控制和欺詐檢測(cè)等方面得到了廣泛應(yīng)用。數(shù)據(jù)聚類是一個(gè)探索和描述性數(shù)據(jù)分析的過程,并在這個(gè)過程中將相似的對(duì)象或數(shù)據(jù)進(jìn)行標(biāo)識(shí)和分組。聚類的任務(wù)是在沒有訓(xùn)練樣本的情況下,僅利用樣本間的相似性尋找樣本集針對(duì)某個(gè)評(píng)判準(zhǔn)則的最佳類別劃分[1-2]。聚類分析屬于無監(jiān)督學(xué)習(xí)問題,用來在無標(biāo)識(shí)的數(shù)據(jù)集合中發(fā)現(xiàn)其內(nèi)在結(jié)構(gòu)和聯(lián)系,將對(duì)象按照某方面的相似性進(jìn)行組織分組的過程,因此每個(gè)聚類都是對(duì)象的集合,并且具有很強(qiáng)的相似性,而不同聚類之間的對(duì)象則具有相對(duì)較弱的相似性或者不具有相似性[3]。在實(shí)現(xiàn)數(shù)據(jù)集合聚類分析的研究過程中,針對(duì)不同的數(shù)據(jù)類型和應(yīng)用目的,相關(guān)的研究人員對(duì)問題的關(guān)注方向也不盡相同,如對(duì)密度的適應(yīng)能力、形狀的適應(yīng)能力、噪音的檢測(cè)、邊界對(duì)象的識(shí)別、聚類個(gè)數(shù)的確定、聚類結(jié)果的準(zhǔn)確度、算法的優(yōu)化速度、高維數(shù)據(jù)的聚類問題,因此研究具有最大的適應(yīng)能力的聚類算法就成為聚類研究的重要方向之一。早期的聚類算法,如K-均值、K-中心點(diǎn)、FCM等,它們只對(duì)空間分布為球形或者超球體的數(shù)據(jù)具有較好的性能,而對(duì)空間分布復(fù)雜的數(shù)據(jù)聚類效果較差[1],而且它們都需要預(yù)先設(shè)定聚類的個(gè)數(shù)。基于密度的DBSCAN算法,考慮到數(shù)據(jù)分布的密度特性,對(duì)具有不同形狀特征的數(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)聚類算法,該類算法對(duì)數(shù)據(jù)對(duì)象集合的大密度變化以及任意形狀均具有較好的適應(yīng)性,但是該類算法需要完成較大量數(shù)據(jù)對(duì)象之間的相似性計(jì)算,算法的性能還有提高的空間,另外,對(duì)于計(jì)算對(duì)象相似性時(shí)的共享鄰居個(gè)數(shù)的設(shè)定需要相關(guān)領(lǐng)域的知識(shí)和經(jīng)驗(yàn)。經(jīng)過對(duì)相關(guān)領(lǐng)域的聚類算法的綜合研究和驗(yàn)證,筆者提出了隨機(jī)種子最近鄰居搜索(RS-NNS:random seed nearest neighbour search algorithm)聚類算法,該算法從隨機(jī)確定的種子開始沿徑向搜索具有最大相似特征的鄰居對(duì)象,并形成局部最大聚類集合,并在搜索過程中動(dòng)態(tài)調(diào)整數(shù)據(jù)對(duì)象的歸屬,以實(shí)現(xiàn)局部的最優(yōu)分配,直到所有的數(shù)據(jù)對(duì)象完成聚類標(biāo)識(shí)。經(jīng)過驗(yàn)證,該算法可以有效地適應(yīng)數(shù)據(jù)集合的密度、形狀、噪音、聚類個(gè)數(shù)等問題,并且相對(duì)于同類算法可以實(shí)現(xiàn)較快的優(yōu)化搜索。
DBSCAN(density-based spatial clustering of application with noise)是一種基于密度的聚類算法。該算法將具有足夠高的密度的區(qū)域劃分為簇,并在具有噪音的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的簇,它將簇定義成密度相連的點(diǎn)的最大集合[2]。在給定了核心點(diǎn)、邊界點(diǎn)和噪音點(diǎn)的定義以后,DBSCAN算法中Eps和MinPts 2個(gè)參數(shù)的設(shè)置對(duì)聚類結(jié)果的影響非常大,并且它們的選擇比較困難。DBSCAN算法的描述性定義如下:
1)把所有的數(shù)據(jù)對(duì)象標(biāo)記為核心點(diǎn)、邊界點(diǎn)或者噪音點(diǎn);
2)忽略所有的噪音點(diǎn)對(duì)象;
3)按照Eps為每個(gè)核心點(diǎn)對(duì)象建立邊界;
4)把所有相互連接的核心點(diǎn)對(duì)象標(biāo)記為同一簇;
5)把每個(gè)邊界點(diǎn)分配到與它相關(guān)聯(lián)的核心點(diǎn)對(duì)象相同的簇。
DBSCAN的基于密度的簇的定義方式,使得該算法具有較強(qiáng)的抗噪音能力,并且能夠分析處理具有任意形狀和大小的簇的數(shù)據(jù)對(duì)象集合,因此能夠發(fā)現(xiàn)很多K-means算法不能處理的簇。然而DBSCAN算法也存在相應(yīng)的缺陷和不足:
1)當(dāng)分析處理的數(shù)據(jù)對(duì)象集合的分布密度有較大變化時(shí),Eps和Min Pts參數(shù)的選擇將變得非常困難;
2)對(duì)高維數(shù)據(jù)對(duì)象集合分析時(shí),密度的定義很難實(shí)現(xiàn);
3)用于獲得近鄰對(duì)象的計(jì)算代價(jià)較大,跟高維數(shù)據(jù)集合的計(jì)算代價(jià)一樣[1]。
基于SNN相似性算法的基本思想是:如果2個(gè)數(shù)據(jù)對(duì)象與其他許多相同的數(shù)據(jù)對(duì)象具有相似性,盡管直接的相似性度量方法可能確定不了這種相似性,但是這2個(gè)數(shù)據(jù)對(duì)象之間的相似性是成立的。SNN相似性定義為具有低密度或者密度變化較大特征的數(shù)據(jù)集合的聚類分析提供了可行的思路。JP聚類算法通過最近共享鄰居方法進(jìn)行對(duì)象聚類,該算法的執(zhí)行需要確定數(shù)據(jù)對(duì)象之間距離的度量方法以及2個(gè)參數(shù)J和K,J是最近鄰居列表的大小,K是共享鄰居的個(gè)數(shù)。該算法的描述如下。
1)對(duì)聚類分析的數(shù)據(jù)集合中的每個(gè)對(duì)象確定它的J個(gè)最近的鄰居;
2)把符合條件的對(duì)象分配到同一個(gè)簇中,它們相互包含在對(duì)方的最近鄰居列表中,并且至少擁有K個(gè)共享的鄰居對(duì)象。
因?yàn)镴P聚類算法是基于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ì)象集合,通過對(duì)單連接的判定來決定是否對(duì)一個(gè)對(duì)象集合進(jìn)行分割或保留為一個(gè)簇,因此JP聚類算法在一定意義上是脆弱的,它可能分割真正的簇或者合并應(yīng)該保持分離的簇。另外,JP聚類算法不能實(shí)現(xiàn)對(duì)象的完全聚類并且最佳參數(shù)的選擇也比較困難[2-6]。
數(shù)據(jù)分布密度、SNN相似性等測(cè)度方法的引入,使得復(fù)雜分布數(shù)據(jù)的結(jié)構(gòu)特點(diǎn)得到了較好的體現(xiàn),對(duì)于大多數(shù)的數(shù)據(jù)聚類分析問題能達(dá)到較好的效果。但算法的性能,如自然密度變化的數(shù)據(jù)分布的識(shí)別、不規(guī)則形狀的數(shù)據(jù)分布的識(shí)別等仍然存在改進(jìn)和提升的空間,因此隨機(jī)徑向搜索算法試圖通過數(shù)據(jù)對(duì)象本身自然存在局部集聚特性以及數(shù)據(jù)對(duì)象的局部關(guān)聯(lián)特性,來實(shí)現(xiàn)對(duì)數(shù)據(jù)對(duì)象的最佳聚類和算法性能的提升。
數(shù)據(jù)對(duì)象的分布是有局部集聚特性的,否則就失去了聚類分析的意義。對(duì)于任意一個(gè)數(shù)據(jù)對(duì)象而言,不管它周圍的數(shù)據(jù)分布密度如何,總可以發(fā)現(xiàn)一些相對(duì)來說比較近的鄰居對(duì)象,基于數(shù)據(jù)分布局部集聚特性,可以認(rèn)為當(dāng)前數(shù)據(jù)對(duì)象以及它的最近的鄰居就可以構(gòu)成一個(gè)具有局部集聚特征的聚類。在現(xiàn)實(shí)世界中,各種對(duì)象之間的關(guān)系是可以傳遞的,所以可以認(rèn)為鄰居的鄰居之間也存在必然的關(guān)聯(lián)。基于以上基本思想,可以從一個(gè)任意的種子對(duì)象開始,沿著它的四周鄰居的徑向方向進(jìn)行關(guān)聯(lián)搜索,并在搜索過程中對(duì)參加擴(kuò)展搜索的鄰居對(duì)象加以限制來實(shí)現(xiàn)局部數(shù)據(jù)對(duì)象的聚類發(fā)現(xiàn),算法搜索的具體實(shí)現(xiàn)原理見圖1。在圖1中,從隨機(jī)選定的對(duì)象點(diǎn)A開始,沿著它的每個(gè)最近鄰居所在的方向開始搜索,符合條件的每個(gè)鄰居都會(huì)成為新的搜索種子,直到完成局部集合的最優(yōu)搜索過程,然后再隨機(jī)選取沒有標(biāo)識(shí)的數(shù)據(jù)對(duì)象,如數(shù)據(jù)對(duì)象B,展開另一個(gè)聚類的搜索過程,直到實(shí)現(xiàn)整個(gè)數(shù)據(jù)空間的搜索工作。這樣的搜索過程是通過鄰居對(duì)象逐漸展開的,并且包括了各種可能方向的搜索,因此它可以達(dá)到對(duì)任意形狀和密度變化的數(shù)據(jù)集合的有效適應(yīng)[7-8]。
為了提高算法的適應(yīng)能力和聚類結(jié)果的準(zhǔn)確性,針對(duì)一些關(guān)鍵的技術(shù)細(xì)節(jié)問題,提出了以下解決方法。
1)弱關(guān)聯(lián)數(shù)據(jù)對(duì)象間的歸屬評(píng)判問題在聚類搜索的過程中,對(duì)于任意分布的數(shù)據(jù)對(duì)象,可能存在一些數(shù)據(jù)對(duì)象雖然屬于當(dāng)前對(duì)象的最近鄰居集合,但是該對(duì)象并不一定適合作為進(jìn)一步搜索的種子對(duì)象,因此需要采取一定的方法避免讓該類數(shù)據(jù)對(duì)象參加進(jìn)一步的聚類搜索。由于每個(gè)對(duì)象在其局部范圍內(nèi)都會(huì)存在相對(duì)較近的鄰居,這就為人們進(jìn)行判定提供了依據(jù),可以認(rèn)為一個(gè)對(duì)象如果它的最近的鄰居多數(shù)都屬于當(dāng)前種子對(duì)象的鄰居集合或者不屬于當(dāng)前已經(jīng)標(biāo)識(shí)的數(shù)據(jù)集合,則可以認(rèn)為它不適合作為種子進(jìn)行進(jìn)一步的搜索。
2)已經(jīng)標(biāo)識(shí)的對(duì)象的最優(yōu)判定問題
在搜索過程中如果遇到已經(jīng)標(biāo)識(shí)的數(shù)據(jù)對(duì)象,應(yīng)該對(duì)它的歸屬做出最佳的判定。對(duì)于一個(gè)已經(jīng)被標(biāo)識(shí)的數(shù)據(jù)對(duì)象,如果在搜索過程中發(fā)現(xiàn)它的鄰居對(duì)象中歸屬于其他類型的聚類標(biāo)識(shí)占多數(shù),則認(rèn)為它應(yīng)該標(biāo)識(shí)為其他聚類類別,以實(shí)現(xiàn)數(shù)據(jù)集合的局部最優(yōu)搜索。
3)初始種子對(duì)象選擇問題
在整個(gè)聚類過程中總會(huì)存在多次初始種子對(duì)象的選擇問題,如果它的選擇正好落在數(shù)據(jù)對(duì)象比較集中的區(qū)域,則可以完成高質(zhì)量的局部搜索,得到一個(gè)較好集聚的數(shù)據(jù)聚類,但是如果初始種子的選擇落在了邊界或噪音點(diǎn)上,則有可能得不到所預(yù)期的聚類結(jié)果,因此必須對(duì)種子對(duì)象的選取和搜索加以控制。如果當(dāng)前種子數(shù)據(jù)對(duì)象到它最近的2個(gè)鄰居的距離遠(yuǎn)遠(yuǎn)超出它的最近2個(gè)鄰居的距離,則認(rèn)為該種子對(duì)象為噪音數(shù)據(jù)或者停止對(duì)該種子的繼續(xù)搜索。
圖1 RS-NNS算法實(shí)現(xiàn)原理圖Fig.1 Principle of RS-NNS clustering algorithm
通過對(duì)相關(guān)聚類算法的研究,總結(jié)和分析了不同類型的數(shù)據(jù)集合的分布特點(diǎn),在此基礎(chǔ)上設(shè)計(jì)了RSNNS聚類算法,算法的具體實(shí)現(xiàn)如下:
為了對(duì)RS-NNS進(jìn)行驗(yàn)證,用Java語言完成了相關(guān)的算法編程實(shí)現(xiàn),將RS-NNS,DBSCAN,JP算法在大量的不同特性的人工合成數(shù)據(jù)集合上進(jìn)行了驗(yàn)證工作,并對(duì)試驗(yàn)的結(jié)果進(jìn)行了比較分析,試驗(yàn)結(jié)果表明,筆者所提出的RS-NNS算法是有效的,能夠較好地適用各種類型的數(shù)據(jù)集合的聚類分析任務(wù)。該算法的設(shè)計(jì)、試驗(yàn)運(yùn)行的環(huán)境均為CPU Intel Pentium Dual Core 1.7 GHz、內(nèi)存2 GB的微型計(jì)算機(jī)。
為了能夠直觀地考察RS-NNS算法的性能,通過軟件方法生成了分別有100,250,500個(gè)數(shù)據(jù)對(duì)象的多組模擬數(shù)據(jù)集合,讓3個(gè)算法分別運(yùn)行在不同大小的數(shù)據(jù)集合上,并取得它們運(yùn)行的平均時(shí)間,它們對(duì)數(shù)據(jù)的處理性能如圖2所示,可以明顯看出RS-NNS算法相對(duì)于其他算法的優(yōu)越性。
為了更好地說明該算法對(duì)于具有不同分布密度特點(diǎn)的數(shù)據(jù)集合的適應(yīng)能力,筆者選取了在試驗(yàn)中具有代表性的數(shù)據(jù)集合進(jìn)行了測(cè)試。測(cè)試結(jié)果顯示,該算法對(duì)于不同密度分布的數(shù)據(jù)對(duì)象的適應(yīng)優(yōu)于DBSCAN,克服了DBSCAN必須由用戶指定靜態(tài)的密度參數(shù)的缺點(diǎn),能夠正確地識(shí)別有較大差別的不同密度的數(shù)據(jù)集合中的自然形狀的聚類,如圖3所示。試驗(yàn)結(jié)果表明該算法對(duì)于噪音數(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ù)集合分布密度的變化,不一定是絕對(duì)的高密度和低密度,有可能會(huì)存在逐漸過渡的密度變化情形,這樣的數(shù)據(jù)對(duì)象的局部集聚往往也是合理的,因此在進(jìn)行聚類算法的設(shè)計(jì)時(shí)應(yīng)考慮對(duì)此類聚類數(shù)據(jù)的處理和分析。另外,聚類數(shù)據(jù)的分布不一定是球形或者其他規(guī)則的形狀,任意形狀的數(shù)據(jù)聚類的存在也非常廣泛。RS-NNS算法的設(shè)計(jì)充分考慮了以上數(shù)據(jù)分析的情況,使得它能夠很好地適應(yīng)密度逐漸變化以及任意形狀的聚類的分析任務(wù),它的適應(yīng)性測(cè)試結(jié)果見圖4。另外通過大量的試驗(yàn)表明,該算法同樣可以準(zhǔn)確地自動(dòng)識(shí)別出數(shù)據(jù)集合中自然存在的聚類個(gè)數(shù)。
圖4 RS-NNS算法對(duì)逐漸變化密度、任意形狀、聚類個(gè)數(shù)適應(yīng)性分析圖Fig.4 RS-NNS adaptability of gradually changed density,arbitrary shape and cluster number
筆者對(duì)當(dāng)前流行的聚類算法(如DBSCAN和JP等)以及不同算法所針對(duì)的數(shù)據(jù)分布特點(diǎn)進(jìn)行了綜合分析,針對(duì)這些算法的局限性提出了RS-NNS算法。測(cè)試了不同算法在相同數(shù)據(jù)集合上的運(yùn)行,RS-NNS算法通過簡化數(shù)據(jù)處理過程,取得了明顯的運(yùn)算優(yōu)勢(shì)。另外,RS-NNS算法針對(duì)不同類型的數(shù)據(jù)集合也表現(xiàn)出了良好的適應(yīng)性,它可以準(zhǔn)確地識(shí)別不同密度、逐漸過渡的密度變化以及任意形狀的數(shù)據(jù)對(duì)象的聚類集合。
[1]公茂果,王 爽,馬 萌,等.復(fù)雜分布數(shù)據(jù)的二階段聚類算法[J].軟件學(xué)報(bào)(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é)報(bào)(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]儲(chǔ)岳中,徐 波.動(dòng)態(tài)最近鄰聚類算法的優(yōu)化研究[J].計(jì)算機(jī)工程與設(shè)計(jì)(Computer Engineering and Design),2011,32(5):1 687-1 690.
[8]王 茜,楊正寬.一種基于加權(quán)KNN的大數(shù)據(jù)集下離群檢測(cè)算法[J].計(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é)任編輯:李 穆
河北省社會(huì)科學(xué)基金資助項(xiàng)目(HB12YJ064)
蘇亞然(1972-),女,河北靈壽人,講師,主要從事技術(shù)經(jīng)濟(jì)方面的研究。