基于局部密度下降搜索的自適應(yīng)聚類方法

徐正國　鄭　輝　賀　亮　姚佳奇

(盲信號處理國家科技重點(diǎn)實(shí)驗(yàn)室　成都　610041)

?

基于局部密度下降搜索的自適應(yīng)聚類方法

徐正國鄭輝賀亮姚佳奇

(盲信號處理國家科技重點(diǎn)實(shí)驗(yàn)室成都610041)

(xuzhg08@163.com)

聚類分析是數(shù)據(jù)挖掘中一個(gè)重要的研究領(lǐng)域，用于在無監(jiān)督條件下，從混合類別的數(shù)據(jù)集中分離各樣本的自然分組.根據(jù)不同的先驗(yàn)條件，現(xiàn)已提出了多種不同的聚類算法.但復(fù)雜數(shù)據(jù)集中存在的聚類個(gè)數(shù)未知、聚類形態(tài)混雜、樣本分布不均勻以及類間樣本數(shù)不均衡等問題，仍然是當(dāng)前聚類分析研究中的重難點(diǎn)問題.針對這些問題，通過定義樣本分布的局部密度，提出了一種利用類內(nèi)密度有序性搜索聚類邊界的新的聚類方法，能夠?qū)崿F(xiàn)在未知聚類個(gè)數(shù)條件下，對任意分布形態(tài)的數(shù)據(jù)樣本集進(jìn)行聚類.同時(shí)，通過自適應(yīng)調(diào)節(jié)聚類參數(shù)來處理數(shù)據(jù)分布疏密度不一、類間樣本數(shù)不均衡以及局部密度異常等特殊情況，避免樣本類別被誤劃分和噪聲數(shù)據(jù)干擾.實(shí)驗(yàn)結(jié)果表明，在6類典型測試集上，提出的新聚類算法均有較好的適用性，而在與典型聚類算法和最近發(fā)表的一種聚類算法的性能指標(biāo)對比上，新算法也表現(xiàn)更優(yōu).

數(shù)據(jù)挖掘；聚類；局部密度；下降搜索；自適應(yīng)

聚類分析是數(shù)據(jù)挖掘領(lǐng)域中一項(xiàng)經(jīng)典的數(shù)據(jù)分析任務(wù)，也是無監(jiān)督學(xué)習(xí)中日久彌新的一個(gè)研究課題.聚類分析的目標(biāo)是要在無先驗(yàn)知識或有少量先驗(yàn)知識的條件下，將數(shù)據(jù)樣本集劃分成合理的組合，從而獲得關(guān)于數(shù)據(jù)樣本聚合形態(tài)的自然結(jié)構(gòu)[1-2].

幾十年來，國內(nèi)外學(xué)者基于不同分析視角定義的自然分組，提出了不同類型的聚類算法[3-4].這些聚類算法被廣泛應(yīng)用于文本處理[5]、圖像分析[6]、生物信息學(xué)[7]等諸多領(lǐng)域.隨著聚類方法的研究越來越深入，已有的算法不斷被改進(jìn)，新的聚類思想陸續(xù)被提出，以適應(yīng)更復(fù)雜的數(shù)據(jù)條件和更嚴(yán)苛的聚類需求，實(shí)現(xiàn)更理想的聚類劃分.從KMeans、層次聚類、模糊聚類(fuzzingc-means,FCM)等經(jīng)典算法[8-10]，到后續(xù)提出的網(wǎng)格聚類[11]、DBSCAN(density-basedspatialclusteringofapplicationswithnoise)[12]、譜聚類(spectralclustering)[13]等算法，完成了從線性劃分到非線性劃分，從給定聚類個(gè)數(shù)到尋優(yōu)搜索類別個(gè)數(shù)等不同數(shù)據(jù)條件和應(yīng)用場景下的聚類分析任務(wù).但時(shí)至今日，仍有2個(gè)問題沒有得到很好地解決:

1) 感知不同的數(shù)據(jù)條件，實(shí)現(xiàn)自適應(yīng)聚類，并能夠同時(shí)處理任意分布形態(tài)的數(shù)據(jù)樣本集，以及各類樣本數(shù)不均衡和樣本分布疏密度不一等情況.

2) 在聚類個(gè)數(shù)未知的情況下，使聚類結(jié)果接近最優(yōu)的自然分組.

解決以上2個(gè)問題，能夠使聚類分析的普適性和容噪性得到提升，實(shí)用范圍得到擴(kuò)展，因此也成為現(xiàn)今的研究熱點(diǎn).然而，近年國內(nèi)外的許多研究工作大多針對上述的部分問題提出了改進(jìn)方案，尚未有較為完整的解決方法[14-16].為此，本文提出了一種基于局部密度下降搜索的自適應(yīng)聚類分析算法，能夠?qū)崿F(xiàn)在未知聚類個(gè)數(shù)的條件下，對任意分布形態(tài)的數(shù)據(jù)樣本集進(jìn)行聚類，同時(shí)能夠根據(jù)數(shù)據(jù)分布疏密度自動調(diào)節(jié)聚類閾值，防止出現(xiàn)稀疏類別樣本被當(dāng)作噪聲點(diǎn)的情形，還可根據(jù)預(yù)先設(shè)定的樣本不均衡容忍度來實(shí)現(xiàn)不均衡類別的合理劃分，避免小樣本類別被誤分的情況.

本文首先簡要描述當(dāng)前聚類分析研究的進(jìn)展，指出其中存在的一些問題，為與本文的方法對比提供參考.然后闡述本文算法所涉及的聚類原理，并詳細(xì)討論算法中的一些關(guān)鍵步驟，給出實(shí)驗(yàn)結(jié)果，最后總結(jié)全文.

1　聚類分析研究進(jìn)展

聚類算法根據(jù)對自然分組的不同定義，大體可被分為基于距離度量的方法、基于傳播的方法和基于局部統(tǒng)計(jì)量的方法.

基于距離度量的聚類方法，其聚類目標(biāo)是要使得類內(nèi)的距離盡可能小，而類間的距離盡可能大.KMeans作為最早提出的聚類算法，只能對凸分布數(shù)據(jù)集做線性劃分，并且類別樣本數(shù)不均衡的情況會降低聚類準(zhǔn)確性，這些問題為后續(xù)研究留下了許多改進(jìn)的空間.以KernelKMeans[17]為代表的方法，通過引入核函數(shù)，將歐氏距離進(jìn)行非線性映射，使之能夠?qū)Ψ峭狗植嫉臄?shù)據(jù)聚類也具有較好的適應(yīng)性.近年來，又提出了基于多核的聚類分析方法[18]，使得對類別的劃分性能比單核更優(yōu).同樣利用距離來度量樣本之間的相似性，層次聚類方法[19]通過自頂向下的分裂或自底向上的合并過程實(shí)現(xiàn)逐層聚合.譜聚類[20]利用樣本之間的距離構(gòu)造一個(gè)相似度矩陣，將樣本聚類問題轉(zhuǎn)換為子圖劃分問題，而聚類準(zhǔn)則轉(zhuǎn)換為使劃分后的子圖內(nèi)部相似性盡量大，子圖之間的相似性盡量小[13,21-22].譜聚類算法能夠在任意分布的樣本空間上聚類，且收斂于全局最優(yōu)解.

盡管聚類算法在適用性上不斷地被改進(jìn)，但從先驗(yàn)條件上看，其中一些方法需要顯式地指定聚類個(gè)數(shù).目前，有文獻(xiàn)[23-25]通過引入各種判據(jù)來識別最佳聚類數(shù)，通常的做法是遍歷搜索可能的聚類數(shù)取值區(qū)間，觀測以Gap統(tǒng)計(jì)量或特征值為依據(jù)設(shè)計(jì)的聚類指標(biāo)的變化[14,16]，發(fā)現(xiàn)指標(biāo)突變點(diǎn)，從而判斷其為最佳聚類數(shù).但這種遍歷搜索方法的弊端是搜索區(qū)間太大導(dǎo)致計(jì)算量過大，使得算法并不實(shí)用.

為了能夠自適應(yīng)地探測樣本集中可能存在的最優(yōu)聚類個(gè)數(shù)，基于傳播和基于局部統(tǒng)計(jì)量的聚類方法從原理上改變了以距離度量定義“自然分組”的聚類準(zhǔn)則.基于親密度傳播(affinitypropagation)的聚類方法[26-28]，將樣本之間的距離轉(zhuǎn)換為吸引度.某個(gè)樣本點(diǎn)對其他數(shù)據(jù)點(diǎn)的吸引力之和越大，越有可能成為聚類中心.而以DBSCAN為代表的基于密度的聚類方法，通過定義樣本在局部鄰域內(nèi)的密度，將一個(gè)自然分組看作是由低密度點(diǎn)圍繞高密度點(diǎn)形成的團(tuán)簇.最近，Rodriguez等人[29]在《Science》期刊上提出的快速聚類算法，同樣依據(jù)局部密度來確定聚類中心及其半徑，但該算法在聚類過程中需要人工輔助決策.為了解決其中存在的問題，一年來又產(chǎn)生了相應(yīng)的改進(jìn)工作[30-31].與基于局部密度類似的還有基于網(wǎng)格的方法[32-33]，把樣本空間以網(wǎng)格切分，計(jì)算各網(wǎng)格中的局部統(tǒng)計(jì)參數(shù)(均值、方差、分布等)，利用這些信息完成聚類.另外，Mean-Shift[34]綜合了基于核和密度的方法，采用核密度估計(jì)算法搜索出密度最高的點(diǎn)作為聚類中心來實(shí)現(xiàn)聚類.雖然這類算法避免了要求指定聚類數(shù)，但在抗噪性能上，類間樣本數(shù)不均衡、樣本分布疏密度不一等情況并沒有得到很好解決[31].

2　局部密度與聚類

在闡述本文算法之前，先給出局部密度的定義，并討論其與聚類之間關(guān)系和性質(zhì)，以便更好地說明本文算法的設(shè)計(jì)思路和實(shí)現(xiàn)原理.

定義1. 局部密度.對于任意數(shù)據(jù)樣本i，其局部密度ρi由樣本間距離di j和截?cái)嗑嚯xdc確定，即

其中，ψ(di j,dc)可以采用階躍函數(shù)形式：

也可采用高斯核函數(shù)形式：

實(shí)驗(yàn)表明，2種局部密度的定義對計(jì)算結(jié)果影響不大，因此為了減少計(jì)算量，在后續(xù)的分析中都采用階躍形式定義的局部密度.圖1給出了4種不同數(shù)據(jù)集的樣本局部密度分布情況.

Fig. 1　Local densities of sample data sets.圖1　數(shù)據(jù)樣本集局部密度圖

事實(shí)上，不論采用何種算法，聚類結(jié)果應(yīng)該符合人對自然分組的直觀判斷，即在幾何形態(tài)上，特征空間中數(shù)據(jù)樣本分布應(yīng)該在某一觀測尺度ε下具有顯著的團(tuán)簇聚合特性.同時(shí)，觀察圖1中各數(shù)據(jù)集的局部密度分布可以發(fā)現(xiàn)，一個(gè)團(tuán)簇中的局部密度呈現(xiàn)了不同程度的高低有序分布.利用拓?fù)浞治龅姆椒ǎ梢詫⑦@種直觀特性作更為嚴(yán)謹(jǐn)?shù)谋硎觯簿褪钦f，對于一個(gè)局部密度ρ均勻分布的理想聚類，在拓?fù)浣Y(jié)構(gòu)上應(yīng)該具有ε-連通性和ρ-有序性.

(4)

其中,|C|≤|X|，為樣本集中集合的個(gè)數(shù)，則稱集合X是ε-連通的.

由以上定義可知，ε-連通性是形成一個(gè)聚類的必要非充分條件，而為了說明聚類中的ρ-有序性，下面先給出聚類邊界和理想聚類的定義，再對ρ-有序性進(jìn)行證明.

定義4. 理想聚類.樣本集S中的理想聚類X為?xi,xj∈X,N(xi,ε)∩Xborder=?,N(xj,ε)∩Xborder=?，滿足|N(xi,ε)|=|N(xj,ε)|>1和ε-連通性的最大子集.

定理1. 對于由理想聚類混合而成的樣本集，各理想聚類中樣本點(diǎn)的局部密度從聚類內(nèi)部向邊緣呈現(xiàn)單調(diào)變化的趨勢.

證明. 設(shè)樣本集S中各聚類均為理想聚類，X?S,xb∈Xborder，令D=N(xb,ε)X，下面分2種情況討論:

1) D=?.

此時(shí)該邊界區(qū)段不與其他聚類交界.對于從聚類內(nèi)部到該邊界區(qū)段的各樣本點(diǎn)xi，其局部鄰域所包含的樣本點(diǎn)個(gè)數(shù)|N(xi,ε)|逐漸減少.

2) D≠?.

此時(shí)理想聚類X與樣本集S中另一理想聚類Y交界，則D?Y.設(shè)ρX,ρY分別表示X和Y內(nèi)部的局部密度.

① 當(dāng)ρX<ρY時(shí)，從聚類內(nèi)部到該邊界區(qū)段的各樣本點(diǎn)xi，其局部鄰域所包含的樣本點(diǎn)個(gè)數(shù)|N(xi,ε)|單調(diào)遞增；

② 當(dāng)ρX>ρY時(shí)，從聚類內(nèi)部到該邊界區(qū)段的各樣本點(diǎn)xi，其局部鄰域所包含的樣本點(diǎn)個(gè)數(shù)|N(xi,ε)|單調(diào)遞減；

③ 當(dāng)ρX=ρY時(shí)，從聚類內(nèi)部到該邊界區(qū)段的各樣本點(diǎn)xi，其局部鄰域所包含的樣本點(diǎn)個(gè)數(shù)|N(xi,ε)|無變化，又由于D≠?，即X′=X∪Y是ε-連通的.此時(shí)，X′是一個(gè)理想聚類，且|X′|>|X|，這與X是理想聚類的條件矛盾，因此，該情況不成立.

綜上所述，根據(jù)局部密度定義有，理想聚類中樣本點(diǎn)的局部密度從聚類內(nèi)部向邊緣總是呈現(xiàn)單調(diào)變化趨勢.

證畢.

這里需要注意的一個(gè)特殊情形是呈線狀分布的數(shù)據(jù)集，此時(shí)可認(rèn)為聚類中的每個(gè)樣本均處于聚類的邊界，即ρborder=ρinner，如圖1中pathbased數(shù)據(jù)集中環(huán)狀區(qū)域所示.這將作為一種特殊情況在聚類算法中進(jìn)行有針對性的處理.

而對于一般情形中的聚類Z，其樣本的局部密度ρz可以由n個(gè)超球面的理想聚類的局部密度ρ(ri,ci),i∈[1,n]逼近，其中ri和ci分別為各超球面聚類半徑和中心.同時(shí)考慮到噪聲數(shù)據(jù)ξ的影響，于是ρz可表示為

(5)

因此，可認(rèn)為是由密度散布均勻的理想聚類經(jīng)噪聲干擾、局部變形、類間混疊等因素變化而成.這也是在第3節(jié)設(shè)計(jì)基于局部密度下降搜索聚類算法時(shí)要重點(diǎn)解決的問題.

3　基于局部密度下降搜索的聚類算法

與以往基于局部密度的聚類算法不同的是，現(xiàn)有算法大多以尋找聚類中心和聚類半徑為聚類目標(biāo)，而本算法采用搜索聚類邊界為聚類依據(jù)，一旦聚類邊界圈定，聚類自然也就形成.

根據(jù)第2節(jié)中關(guān)于聚類連通性的定義和理想聚類中局部密度有序性的證明，本文提出了基于局部密度下降搜索的聚類算法(localdensitybasedclusteringbydescendingsearch,LDCDS).

首先給定一個(gè)較小的局部半徑，按照式(1)計(jì)算各樣本點(diǎn)的局部密度，然后以合適的搜索半徑，從局部密度最高的樣本沿著密度下降的方向進(jìn)行搜索，并將沿途的樣本點(diǎn)標(biāo)注為與最高密度點(diǎn)相同的類別，當(dāng)某方向再無鄰域樣本點(diǎn)，或鄰域樣本點(diǎn)的局部密度開始增大時(shí)，停止該方向的搜索，并確定聚類的邊界.循環(huán)迭代以上步驟，完成對所有樣本的類別標(biāo)注，聚類結(jié)束.

當(dāng)然，實(shí)際情況中數(shù)據(jù)樣本的局部密度不會是理想的有序散布.為了處理聚類搜索過程中遇到的如類內(nèi)樣本點(diǎn)散布不均勻?qū)е碌木植棵芏确骞取㈩愰g疏密度不一、類別混疊時(shí)的邊界探測、線狀分布與球狀分布混合以及類別之間樣本數(shù)不均衡等各種情況，搜索過程中還需有針對性的判決篩查.下面將就這些關(guān)鍵步驟一一說明.

1) 類內(nèi)樣本散布不均導(dǎo)致的局部密度極值.

由于樣本點(diǎn)非均勻散布可能導(dǎo)致局部密度極值的出現(xiàn)，使得當(dāng)密度下降搜索到此處時(shí)誤將局部極小值點(diǎn)判為聚類邊界.而實(shí)際中，若出現(xiàn)局部極值點(diǎn)，其鄰域會成為類內(nèi)的一個(gè)“孤島”，在最后的聚類合并過程中，這些“孤島”將劃歸周邊的大類.合并“孤島”的尺度由類別樣本不均衡容忍系數(shù)α決定，即樣本數(shù)少于某一比例的小類將并入其周邊的大類.

2) 類間疏密度不一.

圖1中jain數(shù)據(jù)集顯示了2個(gè)類別疏密度不一的情況，DBSCAN這類基于密度的聚類算法，通過給定半徑距離尋找聚類中心，對類內(nèi)密度低于其他類別的樣本子集，容易誤判為噪聲.而本算法采用搜索半徑自適應(yīng)的方式，從類內(nèi)密度高的樣本子集向類內(nèi)密度低的樣本子集不斷擴(kuò)大搜索半徑，也就是不斷在自適應(yīng)不同類別的疏密度，降低分布稀疏的類別樣本的誤判概率.同時(shí)，為了防止搜索半徑在迭代過程中被快速擴(kuò)大，其被設(shè)計(jì)為

(6)

其中,r為初始搜索半徑，n為迭代搜索的次數(shù).

3) 類間樣本混疊.

當(dāng)2個(gè)聚類存在少量樣本交疊時(shí)，采用密度下降的方式對類別邊界進(jìn)行搜索，密度下降的趨勢可能會通過交疊連通的區(qū)域沿著另一個(gè)類別低密度的邊緣傳播出去，造成樣本誤分類的情況.一般來講，當(dāng)2類樣本可分時(shí)，其類間交疊區(qū)域的分布形態(tài)要顯著區(qū)別于各自類內(nèi)的分布形態(tài).這里采用對類別混疊區(qū)域進(jìn)行分布形態(tài)判斷的方法來識別當(dāng)前搜索位置是否處于類間交疊區(qū)，由此來停止對該方向的搜索.

判斷局部樣本分布形態(tài)變化可以采用主成分分析的方法.主成分分析是一種用于提取數(shù)據(jù)分布特征的經(jīng)典而有效的方法.通過矩陣特征值分解，得到數(shù)據(jù)散布的主成分方向及其正交投影空間.當(dāng)搜索半徑之內(nèi)局部樣本散布的主成分方向發(fā)生較大突變時(shí)，可認(rèn)為此時(shí)聚類形態(tài)發(fā)生了改變，搜索可能處于類別邊界或者類間混疊區(qū).這里，我們采用主成分分析中最大特征值和次大特征值的比值，來衡量第i步搜索時(shí)樣本點(diǎn)局部鄰域分布形態(tài)的變化，令γ(i)=λ1λ2，當(dāng)γ(i+1)>β γ(i)或γ(i+1)<γ(i)β時(shí)，判斷為局部散布形態(tài)發(fā)生突變.

由于聚類是一個(gè)無監(jiān)督的過程，對混疊區(qū)域的樣本做類別劃分，具有一定的主觀因素，為了選取一個(gè)合理的判決閾值β，我們根據(jù)2個(gè)正態(tài)分布混疊變化過程的仿真實(shí)驗(yàn)，得到一個(gè)符合觀測預(yù)期的經(jīng)驗(yàn)值，在算法中該值一般取值為3.

綜合以上3點(diǎn)，我們可以得到在局部密度下降搜索過程中，較為完整地解決任意分布形態(tài)聚類、類別樣本數(shù)不均衡、類間疏密度不一致等情況的聚類算法.算法1給出了這些關(guān)鍵步驟的處理流程.

算法1. 局部鄰域搜索與類別標(biāo)注Labeling.

輸入：中心點(diǎn)c、搜索半徑R、前序搜索狀態(tài)s(i-1)；前序鄰域分布形態(tài)γ(i-1)；

輸出：樣本類別標(biāo)簽Labels.

① 判斷前序搜索狀態(tài)是否為初始狀態(tài)0.若是，執(zhí)行步驟②；若否，執(zhí)行步驟⑥.

② 判斷該中心點(diǎn)c是否被標(biāo)記過.若是，則返回.

③ 依據(jù)搜索半徑R，搜索給定中心點(diǎn)c的局部鄰域樣本點(diǎn)N(c,R).若N(c,R)=?，執(zhí)行步驟④；否則，執(zhí)行步驟⑤.

④ 按式(6)擴(kuò)大搜索半徑R，并返回.

⑤ 找出N(c,R)中占比最多的類別.若多數(shù)樣本未被標(biāo)注，則為中心點(diǎn)c生成新的類別標(biāo)簽；否則，將c標(biāo)注為與鄰域主要類別相同的標(biāo)簽.繼續(xù)執(zhí)行步驟⑦.

⑥ 計(jì)算N(c,R)的分布形態(tài)γ(i).若γ(i)較前序形態(tài)γ(i-1)發(fā)生較大變化，則返回.

⑦ 搜索N(c,R)中密度小于ρ(c)的樣本點(diǎn)集.若樣本點(diǎn)集為空，則返回；若非空，則將集合中的所有樣本標(biāo)注為與c相同的類別，并將其中每個(gè)樣本點(diǎn)賦為中心點(diǎn)c，重復(fù)步驟①.

值得指出的一點(diǎn)是，從定義1可以看出，樣本局部密度的計(jì)算過程隱式地完成了將數(shù)據(jù)集從原始m維空間向1維空間的映射，在后續(xù)的聚類過程中，樣本的類別標(biāo)注只與其搜索半徑內(nèi)各樣本點(diǎn)的局部密度有關(guān)，與原始數(shù)據(jù)的維數(shù)無關(guān).因此本算法的適用范圍不受限于數(shù)據(jù)集的維數(shù)，但為了更好地顯示本算法的性能和結(jié)果，也便于讀者理解，第4節(jié)均采用2維數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)驗(yàn)證和對比測試.

當(dāng)然，高維和稀疏數(shù)據(jù)空間可能造成最近鄰失效的情況[35]，但該問題是采用距離來度量樣本間相似性的聚類方法所面臨的共同問題.因此，面對高維數(shù)據(jù)，需要先將其相似性度量進(jìn)行有效處理[36]，在此基礎(chǔ)上使用本方法完成聚類.

4　實(shí)驗(yàn)結(jié)果

4.1LDCDS算法聚類測試結(jié)果

為了測試本文提出的LDCDS算法的聚類性能，我們選取了在聚類分析研究中廣為采用的6類測試數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，測試數(shù)據(jù)集的基本信息如表1所示:

Table 1　Attributes of Experiment Data Sets表1　實(shí)驗(yàn)數(shù)據(jù)集基本屬性

圖2顯示了采用LDCDS算法對表1中各數(shù)據(jù)集的聚類結(jié)果.作為對比，圖3顯示了一種新近提出的，同樣基于局部密度的聚類算法[29]的測試結(jié)果.

從圖2可以看出，LDCDS算法均能給出符合直觀判斷和真實(shí)聚類情況的結(jié)果，并能有效處理這6類測試數(shù)據(jù)集中包含的非凸分布、疏密度不一、類間混疊、類別樣本數(shù)不均衡以及有噪聲干擾等特殊情況.其中，有2個(gè)值得注意的地方是，在pathbased數(shù)據(jù)集中聚類結(jié)果將屬于1個(gè)類的外環(huán)樣本劃分為2個(gè)類.原因是按照LDCDS算法對類別邊界的搜索，在某一局部區(qū)域出現(xiàn)了大于搜索半徑的間隙，使得該區(qū)域被誤判為1個(gè)聚類的邊界，同時(shí)由于該間隙處于環(huán)狀分布的中部，使得被分為2個(gè)聚類的樣本數(shù)相當(dāng)，在最后的聚類合并階段，也無法實(shí)現(xiàn)2個(gè)類別的融合.另外，對于compound數(shù)據(jù)集而言，測試樣本集雖然被標(biāo)注為6類，但在無類別標(biāo)簽的情況下，將圖中右上區(qū)域稀疏分布的樣本點(diǎn)視為密集分布的樣本點(diǎn)的邊界噪聲，也符合直觀判斷，因此，從基于密度下降搜索的聚類準(zhǔn)則和人對聚類的直觀判斷來講，該聚類結(jié)果的準(zhǔn)確性是可以接受的.而在文獻(xiàn)[29]所提算法的測試結(jié)果中，則存在著一些明顯的類別誤判.

Fig. 2　Clustering results of LDCDS.圖2　LDCDS聚類算法的測試結(jié)果

Fig. 3　Results of clustering by fast search and find of density peaks in ref

同時(shí)，我們還基于文獻(xiàn)[29]中使用的實(shí)驗(yàn)數(shù)據(jù)集對算法性能進(jìn)行了測試，結(jié)果如圖4所示.由于該文獻(xiàn)提出的快速聚類算法，有對噪聲數(shù)據(jù)的判斷，而本文算法在對局部分布密致的區(qū)域完成搜索后，同樣達(dá)到了其論文中顯示的聚類效果，如圖4(a)所示.同時(shí)，如果數(shù)據(jù)集中含有大量被認(rèn)為是噪聲的未分類樣本點(diǎn)的話，其聚類結(jié)果也不盡合理，因此，本文算法除了在設(shè)定局部密度閾值實(shí)現(xiàn)噪聲數(shù)據(jù)發(fā)現(xiàn)之外，還能夠?qū)υ肼晹?shù)據(jù)實(shí)現(xiàn)合理地類別劃分，如圖4(b)所示.

Fig. 4　Results of LDCDS with noise and toleration of noise.圖4　LDCDS去噪和容噪聚類結(jié)果

Fig. 5　Performances of LDCDS comparing with typical and latest clustering methods.圖5　LDCDS算法與典型的和最新的聚類算法的性能對比

4.2LDCDS算法與典型算法的性能對比

為了更加全面客觀地比較本文提出的LDCDS算法與已有典型聚類算法的性能差異，我們選取了BatchKMeans，AffinityPropagation，MeanShift，SpetralClustering，AgglomerativeClustering，DBSCAN六類典型算法，其中BatchKMeans是KMeans算法的一個(gè)變種，通過批量式處理來減少聚類時(shí)間，而AgglomerativeClustering是層次聚類算法中采用合并方式進(jìn)行聚類的一種.同時(shí)，我們也將文獻(xiàn)[29]中提出的基于局部密度的聚類算法一同納入比較范圍.

這里采用2個(gè)不同的指標(biāo)分別衡量各算法聚類結(jié)果的準(zhǔn)確性.由于已知測試數(shù)據(jù)集中各樣本的真實(shí)類別標(biāo)簽，我們選用校正Rand系數(shù)(adjustedrandindex,ARI)和校正互信息系數(shù)(adjustedmutualinformationscore,AMI)兩個(gè)指標(biāo)[37-38]來共同衡量聚類結(jié)果的性能.

ARI的取值范圍是[-1,1]，AMI的取值范圍為[0,1]，2個(gè)指標(biāo)越接近1，表示聚類的結(jié)果與真實(shí)的類別分組越相近.各算法在圖2所示的6類測試數(shù)據(jù)集上聚類的性能指標(biāo)如圖5所示.從圖5中的2個(gè)指標(biāo)的測試結(jié)果都可以看出，本文所提出的LDCDS算法的聚類性能多數(shù)情況都要優(yōu)于其他算法，并且對于jain，aggregation，spiral三類數(shù)據(jù)集的聚類結(jié)果與真實(shí)情況基本吻合.綜合2個(gè)聚類性能指標(biāo)，本算法與文獻(xiàn)[29]中所提出的算法性能相當(dāng)，但對于不同類型的測試集，本算法的性能表現(xiàn)更為平穩(wěn).考慮到文獻(xiàn)[29]的算法需要人工參與選定聚類中心，而本算法在參數(shù)設(shè)定的條件下，可完成自動聚類，無需人工干預(yù)，因此，本算法的適用性要更優(yōu)于現(xiàn)有的一些聚類算法.

5　結(jié)　　論

本文在總結(jié)現(xiàn)有聚類算法原理及其適用性的基礎(chǔ)上，提出了一種新的基于局部密度下降搜索的聚類方法.相比于現(xiàn)有的各類典型聚類方法，本文所提出的算法，具有3個(gè)特點(diǎn)：

1) 不同于以往許多聚類算法尋找合適聚類中心的思想，本算法采用局部密度下降的方式來搜索聚類的邊界，以此來完成對樣本類別屬性的標(biāo)注過程.從數(shù)據(jù)樣本空間的聚類拓?fù)浣Y(jié)構(gòu)來看，搜索聚類邊界比確定聚類中心，具有更高準(zhǔn)確性.

2) 能夠在未知聚類個(gè)數(shù)的條件下完成自適應(yīng)的聚類.并且，與之前采用搜索聚類數(shù)可能取值區(qū)間的方法不同，本算法在完成對所有樣本的聚類標(biāo)注之后，即可獲得合理的聚類數(shù)，節(jié)省了在可能取值區(qū)間內(nèi)反復(fù)搜索帶來的計(jì)算開銷和判別誤差.

3) 能夠同時(shí)處理含有類間數(shù)據(jù)分布疏密度不一、類間樣本數(shù)不均衡和任意分布形態(tài)等情況的數(shù)據(jù)聚類問題.本算法采用了局部密度自適應(yīng)因子，在搜索過程中通過調(diào)節(jié)搜索半徑來感知數(shù)據(jù)分布密度的變化，并在類間樣本不均衡容忍度參數(shù)的指導(dǎo)下，對少量局部密度異常區(qū)域進(jìn)行重新類別歸并，避免樣本類別的誤劃分.

在算法性能的實(shí)驗(yàn)驗(yàn)證中，本文選取了6類常用的測試數(shù)據(jù)集，對本算法進(jìn)行了測試，結(jié)果表明本文算法能夠較好地對上述各種特殊的數(shù)據(jù)聚合情況進(jìn)行處理.同時(shí)，本算法也與現(xiàn)有的典型聚類算法以及新近提出的一種聚類算法進(jìn)行了聚類性能對比，綜合2種聚類性能評價(jià)指標(biāo)，本算法的聚類性能總體優(yōu)于其他算法.但是，從算法的復(fù)雜性來講，本算法由于存在迭代搜索的過程，其聚類過程的耗時(shí)要大于現(xiàn)有的一些算法，如何降低算法的復(fù)雜性是今后研究的重要工作.

[1]DudaRO,HartPE,StorkDG.PatternClassification[M]. 2nded.NewYork:JohnWiley&Sons, 2001

[2]JainAK.Dataclustering: 50yearsbeyondK-means[J].PatternRecognitionLetters, 2010, 31(8): 651-666

[3]GuanTao.Overviewofstatisticalclusteringmodels[J].ComputerScience, 2012, 39(7): 18-24 (inChinese)

(管濤. 統(tǒng)計(jì)聚類模型研究綜述[J]. 計(jì)算機(jī)科學(xué), 2012, 39(7): 18-24)

[4]JinJianguo.Reviewofclusteringmethod[J].ComputerScience, 2014, 41(11): 288-293 (inChinese)

(金建國. 聚類方法綜述[J]. 計(jì)算機(jī)科學(xué), 2014, 41(11): 288-293)

[5]BanerjeeS,RamanathanK,GuptaA.ClusteringshorttextsusingWikipedia[C] //Procofthe30thAnnualIntACMSIGIRConfonResearchandDevelopmentinInformationRetrieval.NewYork:ACM, 2007: 787-788

[6]HoreP,HallLO,GoldgofDB,etal.Ascalableframeworkforsegmentingmagneticresonanceimages[J].SignalProcessingSystems, 2009, 54(1//2//3): 183-203

[7]MadeiraSC,OliveiraAL.Biclusteringalgorithmsforbiologicaldataanalysis:Asurvey[J].IEEETransonComputatinalBiologyandBioinformatics, 2004, 1(1): 24-45

[8]BezdekJC,EhrlichR,FullW.FCM:Thefuzzyc-meansclusteringalgorithm[J].Computers&Geosciences, 1984, 10(2): 191-203

[9]FilipponeM,CamastraF,MasulliF,etal.Asurveyofkernelandspectralmethodsforclustering[J].PatternRecognition, 2008, 41(1): 176-190

[10]HuangChengquan,WangShitong,JiangYizhang.Anewfuzzyclusteringalgorithmwithentropyindexconstraint[J].JournalofComputerResearchandDevelopment, 2014, 51(9): 2117-2129 (inChinese)

(黃成泉,王士同, 蔣亦樟. 熵指數(shù)約束的模糊聚類新算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2014, 51(9): 2117-2129)

[11]WangWei,YangJiong,MuntzR.STING:Astatisticalinformationgridapproachtospatialdatamining[C] //ProcofVLDB.SanFrancisco:MorganKaufmann, 1997: 186-195

[12]KhanK,RehmanSU,AzizK,etal.DBSCAN:past,presentandfuture[C] //Procofthe5thIntConfontheApplicationsofDigitalInformationandWebTechnologies.Piscataway,NJ:IEEE, 2014: 43-47

[13]ShiJ,MalikJ.Normalizedcutsandimagesegmentation[J].IEEETransonPatternAnalysisandMachineIntelligence, 2000, 22(8): 888-905

[14]WangJun,WangShitong,DengZhaohong.Surveyonchallengesinclusteringanalysisresearch[J].ControlandDecision, 2012, 27(3): 321-328 (inChinese)

(王駿, 王士同, 鄧趙紅. 聚類分析研究中的若干問題[J]. 控制與決策, 2012, 27(3): 321-328)

[15]CaiXiaoyan,DaiGuanzhong,YangLibin.Surveyonspectralclusteringalgorithms[J].ComputerScience, 2008, 35(7): 14-19 (inChinese)

(蔡曉妍, 戴冠中, 楊黎斌. 譜聚類算法綜述[J]. 計(jì)算機(jī)科學(xué), 2008, 35(7): 14-19)

[16]XiaoYu,YuJian.Gapstatisticandk-meansalgorithm[J].JournalofComputerResearchandDevelopment, 2007, 44(Suppl): 176-180 (inChinese)

(肖宇, 于劍.Gapstatistic與K-Means算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2007, 44(增刊): 176-180)

[17]DhillonIS,GuanYuqiang,KulisB.Kernelk-means,spectralclusteringandnormalizedcuts[C] //Procofthe10thACMSIGKDDIntConfonKnowledgeDiscoveryandDataMining.NewYork:ACM, 2004: 551-556

[18]ZhaoB,KwokJT,ZhangCS.Multiplekernelclustering[C] //Procofthe9thSIAMIntConfonDataMining.Philadelphia:SIAM, 2009: 638-649

[19]GrabmeierJ,RudolphA.Techniquesofclusteringalgorithmsindatamining[J].DataMiningandKnowledgeDiscovery, 2002, 6(4): 303-360

[20]NgAY,JordanMI,WeissY.Onspectralclustering:Analysisandanalgorithm[J].AdvancedNeuralInformationProcessingSystems, 2001, 14: 849-856

[21]DingC,HeX,ZhaH.Spectalmin-maxcutforgraphpartitioninganddataclustering, 47848[R].Berkeley:NationalEnergyResearchScientificComputingDivision, 2001

[22]MeilaM,XuL.Multiwaycutsandspectralclustering, 442[R].Washington:UniversityofWashington, 2004

[23]TibshiraniR,WaltherG,HastieT.Estimatingthenumberofclustersinadatasetviathegapstatistic[J].RoyalStatisticalSociety, 2001, 63(2): 411-423

[24]MercerGM.Kernel-basedclusteringinfeaturespace[J].IEEETransonNeuralNetworks, 2002, 13(3): 780-784

[25]KongWanzeng,SunZhihai,YangCan.Automaticspectralclusteringbasedoneigengapandorthogonaleigenvector[J].ActaElectronicaSinica, 2010, 38(8): 1880-1886 (inChinese)

(孔萬增, 孫志海, 楊燦. 基于本征間隙與正交特征向量的自動譜聚類[J]. 電子學(xué)報(bào), 2010, 38(8): 1880-1886)

[26]FreyBJ,DueckD.Clusteringbypassingmessagesbetweendatapoints[J].Science, 2007, 315(5814): 972-976

[27]BruscoMJ,KohnHF.Commenton“clusteringbypassingmessagesbetweendatapoints”[J].Science, 2008, 319(5864): 726

[28]LuWeiming,DuChenyang,WeiBaogang,etal.Distributedaffinitypropagationclusteringbasedonmapreduce[J].JournalofComputerResearchandDevelopment, 2012, 49(8): 1762-1772 (inChinese)

(魯偉明，杜晨陽，魏寶剛，等.基于MapReduce的分布式近鄰傳播聚類算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2012, 49(8): 1762-1772)

[29]RodriguezA,LaioA,Clusteringbyfastsearchandfindofdensitypeaks[J].Science, 2014, 344(6191): 1492-1497

[30]ChenJinyin,HeHuihao.Researchondensity-basedclusteringalgorithmformixeddatawithdetermineclustercentersautomatically[J].ActaAutomaticaSinica, 2015, 41(10): 1798-1813 (inChinese)

(陳晉音, 何輝豪. 基于密度的聚類中心自動確定的混合屬性數(shù)據(jù)聚類算法研究[J]. 自動化學(xué)報(bào), 2015, 41(10): 1798-1813)

[31]ZhangWenkai,LiJing.Extendedfastsearchclusteringalgorithm:Widelydensityclusters,nodensitypeaks[EB//OL]. 2015[2015-05-21].http://arxiv.org//abs//1505.05610

[32]YangShanhong,LiangJinming,LiJingwen.Impactfactorofgriddensitybasedclusteringalgorithmformulti-density[J].ApplicationResearchofComputers, 2015, 32(3): 743-747 (inChinese)

(楊善紅, 梁金明, 李靜雯. 基于網(wǎng)格密度影響因子的多密度聚類算法[J]. 計(jì)算機(jī)應(yīng)用研究, 2015, 32(3): 743-747)

[33]HuangHongwei,HuangTianmin.Extensionclusteringalgorithmbasedonrelativegriddensitydifference[J].ApplicationResearchofComputers, 2014, 31(6): 1702-1705 (inChinese)

(黃紅偉, 黃天民. 基于網(wǎng)格相對密度差的擴(kuò)展聚類算法[J]. 計(jì)算機(jī)應(yīng)用研究, 2014, 31(6): 1702-1705)

[34]ComaniciuD,MeerP.Meanshift:Arobustapproachtowardfeaturespaceanalysis[J].IEEETransonPatternAnalysisandMachineIntelligence, 2002, 24(5): 603-619

[35]BeyerK,GoldsteinJ,RamakrishnanR,etal.WhenIs“NearestNeighbor”meaningful, 1377[R].Madison:UniversityofWisconsinMadison, 1998

[36]CaiTT,ShenXT.High-DimensionalDataAnalysis[M].Beijing:HigherEducationPress, 2010

[37]VinhNX,EppsJ,BaileyJ.Informationtheoreticmeasuresforclusteringscomparison:isacorrelationforchancenecessary[C] //Procofthe26thAnnualIntConfonMachineLearning.NewYork:ACM, 2009: 1073-1080

[38]VinhNX,EppsJ,BaileyJ.Informationtheoreticmeasuresforclusteringscomparison:variants,properties,normalizationandcorrectionforchance[J].JournalofMachineLearningResearch, 2010, 11: 2837-2854

XuZhengguo,bornin1985.PhDcandidateattheStateKeyLaboratoryofBlindSignalsProcessing,Chengdu.StudentmemberofChinaComputerFederation.Hismainresearchinterestsincludedatamining,machinelearning,networkanalysis,andbigdataprocessing.

ZhengHui,bornin1957.Seniorengineer.PhDsupervisor.Hismainresearchinterestsincludeblindsignalprocessingandintelligentinformationanalysis.

HeLiang,bornin1990.MastercandidateattheStateKeyLaboratoryofBlindSignalsProcessing,Chengdu.Hismainresearchinterestsincludeanomalydetectinandnetworkdetection.

YaoJiaqi,bornin1992.MastercandidateattheStateKeyLaboratoryofBlindSignalsProcessing,Chengdu.Hismainresearchinterestsincludedatabaseresearchandnetworkdataprocessing.

Self-AdaptiveClusteringBasedonLocalDensitybyDescendingSearch

XuZhengguo,ZhengHui,HeLiang,andYaoJiaqi

(National Key Laboratory of Science and Technology on Blind Signals Processing, Chengdu 610041)

Clusteranalysisisanimportantresearchdomainofdatamining.Ontheunsupervisedcondition,itisaimedatfiguringouttheclassattributesofsamplesinamixeddatasetautomatically.Fordecadesacertainamountofclusteringalgorithmshavebeenproposedassociatedwithdifferentkindsofprioriknowledge.However,therearestillsomeknottyproblemsunsolvedinclusteringcomplexdatasets,suchastheunknownnumberandmiscellaneouspatternsofclusters,theunbalancednumbersofsamplesbetweenclusters,andvarieddensitieswithinclusters.Theseproblemshavebecomethedifficultandemphaticpointsintheresearchnowadays.Facingthesechallenges,anovelclusteringmethodisintroduced.Basedonthedefinitionoflocaldensityandtheintuitionofordereddensityinclusters,thenewclusteringmethodcanfindoutnaturalpartitionsbyself-adaptedsearchingtheboundariesofclusters.Furthermore,intheclusteringprocess,itcanovercomethestraitenedcircumstancesmentionedabove,withavoidingnoisedisturbanceandfalseclassification.Theclusteringmethodistestifiedon6typicalandmarkedlydifferentdatasets,andtheresultsshowthatithasgoodfeasibilityandperformanceintheexperiments.Comparedwithotherclassicclusteringmethodsandanalgorithmpresentedrecently,inaddition,thenewclusteringmethodoutperformsthemon2differentevaluationindexes.

datamining;clustering;localdensity;descendingsearch;self-adaption

2016-03-10；

2016-06-01

TP391