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

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