一種多參數(shù)自動(dòng)控制的dbscan聚類算法

一種多參數(shù)自動(dòng)控制的dbscan聚類算法

1基于密度的聚類算法像概括數(shù)據(jù)這樣的數(shù)據(jù)捕獲技術(shù)已經(jīng)廣泛使用。聚類是一種重要的挖掘挖掘技術(shù)。這項(xiàng)任務(wù)是將數(shù)據(jù)集分為幾個(gè)部分。同一集群中的數(shù)據(jù)具有很高的相似性，不同簇中的數(shù)據(jù)幾乎沒有相似性。目前已經(jīng)存在的聚類算法大致可以分為4種類型:(1)基于劃分的聚類算法,如k-means、k-medoids等.這種算法需要設(shè)定簇的數(shù)量,根據(jù)對(duì)象間的相似性將每個(gè)對(duì)象劃歸最近的簇.這種算法能夠發(fā)現(xiàn)超球狀的簇.(2)層次聚類算法.層次聚類可以從2個(gè)方向產(chǎn)生,第一是凝聚,首先將所有對(duì)象標(biāo)記為簇,然后逐次合并距離最小的簇;第二是分裂,先將整個(gè)數(shù)據(jù)集視為一個(gè)簇,然后逐次分裂樣本較多的簇.層次聚類需要人為設(shè)定終止條件,即凝聚或分裂到何種程度為止.根據(jù)簇相似性的不同定義,層次聚類算法有單鏈(single-link)、全鏈(complete-link)、組平均(groupaverage)、Ward方法、BIRCH和CURE等.(3)基于統(tǒng)計(jì)模型的算法,如期望最大化(EM)算法.這類算法基于數(shù)理統(tǒng)計(jì)理論,假定數(shù)據(jù)集是由一個(gè)統(tǒng)計(jì)過程產(chǎn)生的,并通過找出最佳擬合模型來描述數(shù)據(jù)集.(4)基于密度的算法,其中心思想是尋找數(shù)據(jù)集中被低密度區(qū)域隔開的高密度區(qū)域,并將每個(gè)獨(dú)立的高密度區(qū)域作為一個(gè)簇.根據(jù)對(duì)密度的不同定義,典型算法有DBSCAN、OPTICS、DENCLULDE等.基于密度的聚類方法以數(shù)據(jù)集在空間分布上的稠密程度為依據(jù)進(jìn)行聚類,無需預(yù)先設(shè)定簇的數(shù)量,因此特別適合于對(duì)未知內(nèi)容的數(shù)據(jù)集進(jìn)行聚類.DBSCAN是一種經(jīng)典的基于密度聚類算法,它以超球狀區(qū)域內(nèi)數(shù)據(jù)對(duì)象的數(shù)量來衡量此區(qū)域密度的高低.DBSCAN算法能夠發(fā)現(xiàn)任意形狀的簇,并有效識(shí)別離群點(diǎn),但聚類之前需要人工選擇Eps和minPts2個(gè)參數(shù).已有文獻(xiàn)提出了若干方法用于判定Eps參數(shù),但并不能適應(yīng)不同統(tǒng)計(jì)特性的數(shù)據(jù)集,對(duì)于minPts參數(shù)的使用也缺乏討論.本文在DBSCAN的基礎(chǔ)上,提出一種通過分析數(shù)據(jù)集的統(tǒng)計(jì)特性來自適應(yīng)確定Eps和minPts的新方法,從而做到聚類過程的全自動(dòng)化.我們將這種方法稱為自適應(yīng)DBSCAN(self-adaptivedensity-basedspatialclusteringofapplicationswithnoise,簡稱SA-DBSAN).本文中定義的主要符號(hào)如表1:本文第2節(jié)介紹DBSCAN算法及其相關(guān)研究工作,第3節(jié)描述SA-DBSCAN的算法細(xì)節(jié),第4節(jié)給出了SA-DBSCAN算法的實(shí)驗(yàn)結(jié)果,第5節(jié)就存在的一些問題做進(jìn)一步討論,最后總結(jié)全文.2相關(guān)工作2.1dap矩陣算法DBSCAN是一種經(jīng)典的基于密度聚類算法,可以自動(dòng)確定簇的數(shù)量,并能夠發(fā)現(xiàn)任意形狀的簇.DBSCAN的主要定義如下.(1)epsp、非臺(tái)度p、非定位問題p(Eps鄰域)給定一個(gè)數(shù)據(jù)對(duì)象p,p的Eps鄰域NEps(p)定義為以p為核心,以Eps為半徑的d維超球體區(qū)域,即ΝEps(p)={q∈D|dist(p,q)≤Eps},(1)NEps(p)={q∈D|dist(p,q)≤Eps},(1)其中,D?Rd為d維實(shí)空間上的數(shù)據(jù)集,dist(p,q)表示D中的2個(gè)對(duì)象p和q之間的距離.(2)相關(guān)條件下的核心點(diǎn)(核心點(diǎn)與邊界點(diǎn))對(duì)于數(shù)據(jù)對(duì)象p∈D,給定一個(gè)整數(shù)minPts,如果p的Eps鄰域內(nèi)的對(duì)象數(shù)滿足|NEps(p)|≥minPts,則稱p為(Eps,minPts)條件下的核心點(diǎn);不是核心點(diǎn),但落在某個(gè)核心點(diǎn)的Eps鄰域內(nèi)的對(duì)象稱為邊界點(diǎn).(3)對(duì)象pnpsq的ndfp(直接密度可達(dá))給定(Eps,minPts),如果對(duì)象p和q滿足:(a)p∈NEps(q);(b)|NEps(q)|≥minPts(即q是核心點(diǎn)),則稱對(duì)象p是從對(duì)象q出發(fā),直接密度可達(dá)的.(4)從pi密度可達(dá)(密度可達(dá))給定數(shù)據(jù)集D,當(dāng)存在一個(gè)對(duì)象鏈p1,p2,p3,…,pn,其中,p1=q,pn=p,對(duì)于pi∈D,如果在條件(Eps,minPts)下pi+1從pi直接密度可達(dá),則稱對(duì)象p從對(duì)象q在條件(Eps,minPts)下密度可達(dá).密度可達(dá)是非對(duì)稱的,即p從q密度可達(dá)不能推出q也從p密度可達(dá).(5)密度相同的情況(密度相連)如果數(shù)據(jù)集D中存在一個(gè)對(duì)象o,使得對(duì)象p和q是從o在(Eps,minPts)條件下密度可達(dá)的,那么稱對(duì)象p和q在(Eps,minPts)條件下密度相連.密度相連是對(duì)稱的.(6)標(biāo)準(zhǔn)6(簇和噪聲)由任意一個(gè)核心點(diǎn)對(duì)象開始,從該對(duì)象密度可達(dá)的所有對(duì)象構(gòu)成一個(gè)簇.不屬于任何簇的對(duì)象為噪聲.2.2基于distminpts的精度分析DBSCAN聚類的準(zhǔn)確性與Eps和minPts2個(gè)參數(shù)的選擇有關(guān).給定minPts,選擇的Eps越小,發(fā)現(xiàn)的簇的密度越高.如果選擇過小的Eps,則會(huì)導(dǎo)致大量對(duì)象被錯(cuò)誤地標(biāo)記為噪聲,而一個(gè)自然簇也被錯(cuò)誤地拆分成多個(gè)簇;如果選擇了過大的Eps,則很多噪聲被錯(cuò)誤地歸入簇,而分離的若干個(gè)自然簇也被錯(cuò)誤地合并為一個(gè)簇.給定Eps,選擇的minPts越大,發(fā)現(xiàn)簇的密度越高.過小的minPts會(huì)導(dǎo)致大量對(duì)象被標(biāo)記為核心點(diǎn),從而將噪聲歸入簇;過大的minPts會(huì)導(dǎo)致核心點(diǎn)數(shù)量減少,使得一些包含對(duì)象數(shù)較少的自然簇被丟棄.DBSCAN算法描述中給出的參數(shù)選擇方法是設(shè)定minPts=4,通過觀察法來判斷Eps.對(duì)于p∈D查找與p最近的第minPts個(gè)對(duì)象的距離distminPts(p),p遍歷D得到集合DistminPts={distminPts(p)|p∈D},對(duì)DistminPts排序并繪圖.對(duì)于簇密度差異不明顯的數(shù)據(jù)集,DistminPts的排序圖一般為圖1的形狀.觀察圖中曲線的平緩部分,將處在A位置的值設(shè)定為Eps.顯然,這種方法需要用戶的參與.FengP.J.等人將HalkidiM.提出的方法采用到DBSCAN上.仍假定minPts,而使用多個(gè)不同的Eps參數(shù)值進(jìn)行試聚類,然后評(píng)估各次聚類的有效性(clusteringvalidity),從中選取最優(yōu)的.這種方法解決了自動(dòng)選取Eps參數(shù)的問題,但時(shí)間復(fù)雜度增大,相當(dāng)于做了多次DBSCAN運(yùn)算.而且,試聚類時(shí)Eps在多大范圍內(nèi)取多少個(gè)值也難以界定.YueS.H.的研究中引入了距離分布的概念.仍假定minPts=4,計(jì)算數(shù)據(jù)集中每2個(gè)對(duì)象之間的距離并排序,并取Eps為排序后第δ2/(4c)C2n2n個(gè)點(diǎn)對(duì)應(yīng)的值.這種方法仍需設(shè)定簇個(gè)數(shù)c的值,或者使用HalkidiM的方法來判斷c值.XuX.等人則引入了密度分布的概念.假定每個(gè)自然簇中的對(duì)象都服從平均分布,通過網(wǎng)格取高密度區(qū)域,并以原分布模型是否仍有效來衡量一個(gè)對(duì)象是否屬于某個(gè)簇.這種方法無需使用Eps和minPts,事實(shí)上是有別于DBSCAN的一種新聚類算法.但是這種方法需要選擇網(wǎng)格的大小,過大或過小的網(wǎng)格都會(huì)造成結(jié)果失真.在其他相關(guān)工作中,AnkerstM.提出的OPTICS方法對(duì)所有對(duì)象按照密度可達(dá)距離排序,使得同一個(gè)簇的對(duì)象相鄰,從而在分布圖中可以看到明顯的簇特征,但未給出確定簇的算法;LinC.Y.采用了遺傳算法來估算Eps,但時(shí)間復(fù)雜度較大,且仍假定minPts參數(shù);蔡穎琨等人通過增加簇連接信息使得DBSCAN對(duì)輸入?yún)?shù)的敏感性降低,但未能解決自動(dòng)確定參數(shù)的問題;蘇中等人則提出了逐級(jí)細(xì)化聚類的方法,每次聚類動(dòng)態(tài)調(diào)整參數(shù),但初始參數(shù)仍需使用觀察法確定.基于以上描述,現(xiàn)有改進(jìn)工作的局限在于無法真正自適應(yīng)地確定合適的minPts和Eps參數(shù).本文在DBSCAN的基礎(chǔ)上,提出一種通過分析數(shù)據(jù)集的統(tǒng)計(jì)特征來自適應(yīng)確定Eps和minPts的新方法,從而做到聚類過程的全自動(dòng)化.我們將這種方法稱為SA-DBSCAN算法.3距離分布矩陣本節(jié)所有的繪圖都基于一個(gè)包含240個(gè)對(duì)象的二維示例數(shù)據(jù)集SampleD,見圖5.SA-DBSCAN根據(jù)數(shù)據(jù)集本身的統(tǒng)計(jì)特性來判斷Eps和minPts的取值.首先需要計(jì)算距離分布矩陣DISTn×n:DΙSΤn×n={dist(i,j)|1≤i≤n,1≤j≤n},(2)DISTn×n={dist(i,j)|1≤i≤n,1≤j≤n},(2)其中,n=|D|,表示數(shù)據(jù)集中的對(duì)象個(gè)數(shù).DISTn×n是n行n列的實(shí)對(duì)稱陣,每個(gè)元素表示D中第i個(gè)對(duì)象到第j個(gè)對(duì)象的距離.3.1在k-gaus蝦n擬合中k-1.2.2對(duì)DISTn×n的每一列排序并轉(zhuǎn)置得到矩陣KNN0n×n=sort(DISTn×n)′.KNN0n×n的每一列向量代表數(shù)據(jù)集中所有對(duì)象到最近的第k-1(k是列下標(biāo),k=1,2,…,n)個(gè)對(duì)象的距離集合.其中第1列為全零集合,因?yàn)槊總€(gè)對(duì)象到第0個(gè)最近對(duì)象的距離是到它自身的距離.為了計(jì)算和繪圖的方便,刪除KNN0n×n的第1列并對(duì)列向量排序,得到KNNn×(n-1):ΚΝΝn×(n-1)=sort(ΚΝΝ0n×n(1:end;2:end)),(3)KNNn×(n?1)=sort(KNN0n×n(1:end;2:end)),(3)這樣,KNNn×(n-1)的第k(k=1,2,…,n-1)列即數(shù)據(jù)集中所有對(duì)象的k-最近鄰距離集合Distk.對(duì)SampleD數(shù)據(jù)集的KNNn×(n-1)矩陣的每一列(排序后的Distk)繪圖,得到圖2.圖2中可以看到,隨著k的增加,排序后的Distk曲線大致沿縱軸向上平移.直觀上理解,對(duì)于數(shù)據(jù)集中的每個(gè)點(diǎn),到第k+1個(gè)最近鄰的距離總是不小于到第k個(gè)最近鄰的距離.可以看到,任何一條曲線都基本符合圖1的形狀.事實(shí)上,圖1就是圖2中k=4的曲線.使用數(shù)學(xué)方法無法直接對(duì)Distk曲線尋找圖1的A點(diǎn).但觀察圖1和圖2,可以發(fā)現(xiàn)任何一條曲線都是在平緩變化后急劇上升,因此可以判斷Distk中大部分值應(yīng)落在一個(gè)比較密集的區(qū)域內(nèi)(曲線平緩段).仍取k=4,繪制Distk的概率分布圖如圖3中的柱狀圖所示.由圖3可以看到Distk的概率分布情況.假如能夠通過數(shù)學(xué)方法找到分布曲線的峰值,則可以以峰值點(diǎn)所對(duì)應(yīng)的k-最近鄰距離值(橫坐標(biāo)刻度)為Eps.對(duì)于概率分布,可以用統(tǒng)計(jì)模型進(jìn)行擬合.經(jīng)過多次實(shí)驗(yàn)發(fā)現(xiàn)使用InverseGaussian擬合的效果最好,如圖3中的擬合曲線所示.InverseGaussian分布的概率密度公式為Ρ(x)=√λ2πx3e-λ(x-μ)2/(2xμ2)P(x)=λ2πx3????√e?λ(x?μ)2/(2xμ2),其中λ和μ可以用最大似然估計(jì)獲得.為了獲得峰值點(diǎn),解微分方程dP(x)/dx=0得到一個(gè)正數(shù)解:x=μ√9μ2+4λ2-3μ22λx=μ9μ2+4λ2√?3μ22λ.因此,當(dāng)取minPts=k時(shí),對(duì)Distk進(jìn)行InverseGaussian擬合,從而得到Epsk=μk√9μ2k+4λ2k-3μ2k2λk.(4)Epsk=μk9μ2k+4λ2k√?3μ2k2λk.(4)3.2noisak/k-n-1噪聲需要注意的是,使用上述的InverseGaussian擬合方法得到的Epsk并非處在圖1的A處,而是大致處在曲線平緩部分的中段,這個(gè)值要小于A處的取值.如果仍假定minPts=4進(jìn)行聚類,很可能因?yàn)镋ps取值過小而造成偏差.因此,聚類時(shí)不宜再設(shè)置minPts為固定值.為了確定minPts的合理取值,參考Distk和Epsk(k=1,2,…,n-1),計(jì)算當(dāng)minPts=k時(shí)的噪聲數(shù)量,記為noisek.噪聲可以根據(jù)定義判斷:對(duì)于數(shù)據(jù)集D中的對(duì)象p,當(dāng)minPts=k,Eps=Epsk,如果p滿足(1)|NEps(p)|<minPts,即p不是核心點(diǎn);(2)NEps(p)內(nèi)不存在核心點(diǎn),則p為噪聲.由此得到分別對(duì)應(yīng)于k=1,2,…,n-1的噪聲數(shù)量noisek.將其按照k由小到大排列得到向量Noise.對(duì)Noise繪圖如圖4(a)所示:可以看到,Noise曲線是一條由急劇下降變化到平緩的曲線,k取值越大越貼近0,也可能等于0.當(dāng)k=1時(shí),因Epsk過小而導(dǎo)致大量對(duì)象被標(biāo)記為噪聲;隨著k的增大,Epsk逐漸增大至合理值,噪聲數(shù)量急劇減少;而隨著k的變大,特別是超過了最小自然簇中對(duì)象個(gè)數(shù)以后,Epsk將增大到幾乎可以將所有點(diǎn)合并到同一個(gè)簇中,噪聲數(shù)量將逐漸趨于0.因此對(duì)于Noise曲線來說,并非噪聲數(shù)量最少的就是合理的,而應(yīng)該取急劇下降部分到平緩部分的拐點(diǎn),即圖4(a)中C點(diǎn).與圖1中的A點(diǎn)類似,很難有數(shù)學(xué)方法精確定位C點(diǎn).觀察圖4(a)可以發(fā)現(xiàn),Noise曲線大致沿45°直線對(duì)稱,而橫、縱坐標(biāo)軸物理含義均是“對(duì)象個(gè)數(shù)”,且取值范圍相差不大.構(gòu)造等差數(shù)列:K*=k*1,k*2,…,k*n-1,其中k*1=min(noisek),k*n-1=max(noisek).以K*為橫坐標(biāo),Noise為縱坐標(biāo)重新繪圖,得到圖4(b).根據(jù)圖4(b),有2種方法可以大致確定C點(diǎn):(1)Noise對(duì)K*數(shù)值求導(dǎo),得到每個(gè)noisei處的導(dǎo)數(shù)(實(shí)際上是曲線在橫軸第i個(gè)點(diǎn)上的斜率):(noisei)′=noisei+1-noiseik*i+1-k*i.尋找i0使得(noisei0)′最接近-1,取minPts=i0.圖4(b)中的LineA顯示了在i0點(diǎn)處的切線.(2)尋找i0點(diǎn)使得noisei0和k*i0近似相等,即圖4(b)中45°直線LineB與Noise曲線的交點(diǎn).取minPts=i0.經(jīng)過多次實(shí)驗(yàn)發(fā)現(xiàn)方法(1)受到曲線不規(guī)則變化的影響比較大,而方法(2)雖然簡單,但在多數(shù)情況下都能取到合適的值.因此在SA-DBSCAN中使用方法(2)確定minPts.4已選中4.1基于sa-dbscan的數(shù)據(jù)集實(shí)驗(yàn)使用SA-DBSCAN算法對(duì)SampleD進(jìn)行聚類的結(jié)果如圖5所示.為了驗(yàn)證SA-DBSCAN的效果,實(shí)驗(yàn)中我們使用了另外2個(gè)數(shù)據(jù)集.DS1是一個(gè)520個(gè)對(duì)象的二維數(shù)據(jù)集,DS2是一個(gè)300個(gè)對(duì)象的二維數(shù)據(jù)集,二者以及他們的聚類結(jié)果如圖6、圖7所示.由圖5、圖6、圖7可以看到,SA-DBSCAN能夠發(fā)現(xiàn)數(shù)據(jù)集中的高密度區(qū)域并做出適當(dāng)?shù)拇貏澐?這表明第3節(jié)所描述的算法能夠有效選擇合適的Eps和minPts參數(shù).為了測試SA-DBSCAN應(yīng)用在二維以上數(shù)據(jù)集的效果,我們還使用了美國加州大學(xué)信息與計(jì)算機(jī)科學(xué)系的Iris數(shù)據(jù)集1進(jìn)行實(shí)驗(yàn).因多維空間繪圖不便,本文不給出圖形結(jié)果.Iris數(shù)據(jù)集的SA-DBSCAN聚類結(jié)果見表2.4.2聚類計(jì)算的準(zhǔn)確性DBSCAN算法使用R*樹伸展算法進(jìn)行搜索,時(shí)間復(fù)雜度為O(nlogn).R*樹伸展算法的時(shí)間復(fù)雜度主要體現(xiàn)在對(duì)象間距離和k-最近鄰距離的計(jì)算上.在SA-DBSCAN中DIST矩陣和KNN矩陣已經(jīng)包含了這些計(jì)算結(jié)果,因此在聚類過程中不必重復(fù)計(jì)算.相比于DBSCAN,SA-DBSCAN需要額外的時(shí)間開銷用于計(jì)算Eps和minPts參數(shù)的取值,這主要由InverseGaussian擬合引起.我們采用有監(jiān)督的F度量(FMeasure)方法檢測聚類的準(zhǔn)確性.SampleD、DS1、DS2和Iris數(shù)據(jù)集的各項(xiàng)聚類結(jié)果和準(zhǔn)確度指標(biāo)在表1給出,為了比較,對(duì)以上數(shù)據(jù)集同時(shí)進(jìn)行k-means和傳統(tǒng)DBSCAN算法聚類.其中k-means聚類的k參數(shù)取數(shù)據(jù)集中自然簇的個(gè)數(shù),DBSCAN取minPts=4,Eps=Eps4.所有的實(shí)驗(yàn)數(shù)據(jù)都是在PentiumIV3.0+512MDDRmemory+WindowsXP平臺(tái)上,使用Matlab2006b計(jì)算并測得.從表2可以看到,在時(shí)間性能方面SA-DBSCAN確實(shí)慢于DBSCAN和k-means,這是由于增加了InverseGaussian擬合的計(jì)算量而引起的.但也可以看出,SA-DBSCAN與DBSCAN的運(yùn)算時(shí)間并不存在數(shù)量級(jí)的差別;另外由于聚類過程仍與DBSCAN相同,所以任何對(duì)DBSCAN算法的優(yōu)化也能用于改善SA-DBSCAN的性能.從表2還可以看出,直接取minPts=4,Eps=Eps4進(jìn)行DBSCAN聚類的準(zhǔn)確度不高,因此對(duì)minPts參數(shù)進(jìn)行判斷而不是取固定值是必要的.另外從準(zhǔn)確度指標(biāo)來看,在處理包含超球狀簇的數(shù)據(jù)集(DS2、Iris)的時(shí)候,SA-DBSCAN提供了不遜于k-means的能力;而對(duì)于k-means不能有效處理的包含任意形狀簇的數(shù)據(jù)集(SampleD、DS1),SA-DBSCAN同樣具有很高的準(zhǔn)確度.5高密度自然簇被廢棄SA-DBSCAN算法對(duì)于簇密度差別很大的數(shù)據(jù)集聚類效果不理想.這是DB