国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

DBSCAN聚類算法的參數(shù)配置方法研究

2019-05-17 02:43宋金玉郭一平
計算機技術(shù)與發(fā)展 2019年5期
關(guān)鍵詞:聚類噪聲密度

宋金玉,郭一平,王 斌

(1.解放軍陸軍工程大學(xué) 指揮控制工程學(xué)院,江蘇 南京 210007;2.解放軍陸軍工程大學(xué) 教學(xué)考試中心,江蘇 鎮(zhèn)江 212000)

0 引 言

全球知名咨詢公司麥肯錫稱:“數(shù)據(jù),已經(jīng)滲透到當(dāng)今每一個行業(yè)和業(yè)務(wù)職能領(lǐng)域,成為重要的生產(chǎn)因素?!钡F(xiàn)實生活中,人們常常抱怨“數(shù)據(jù)豐富,信息貧乏”。這是因為在海量的數(shù)據(jù)中,存在大量無用甚至錯誤的“臟數(shù)據(jù)”,根據(jù)“垃圾進,垃圾出(garbage in,garbage out)”[1]原理,低質(zhì)量的數(shù)據(jù)難以提供有價值的信息,反而會帶來負(fù)面影響,會因各種數(shù)據(jù)/信息質(zhì)量(data/information quality,DQ/IQ)問題給用戶帶來麻煩甚至損失[2-4]。

數(shù)據(jù)質(zhì)量低的一個方面就是數(shù)據(jù)異常,即數(shù)據(jù)集中出現(xiàn)明顯區(qū)別于其他正常數(shù)據(jù)的數(shù)據(jù)。由于數(shù)據(jù)異常往往使數(shù)據(jù)表現(xiàn)為孤立點[5],也稱之為離群點或異常點。這些數(shù)據(jù)可能是需要消除的錯誤數(shù)據(jù),也可能是重要的報警點,預(yù)示出現(xiàn)問題或者發(fā)生了重要變化。

離群點檢測(又稱為異常檢測)是找出其行為不同于預(yù)期對象的過程,通過檢測并去除數(shù)據(jù)源中的這些孤立點可達到消除數(shù)據(jù)異常的目的,從而提高數(shù)據(jù)源的數(shù)據(jù)質(zhì)量。

數(shù)據(jù)挖掘技術(shù)中的聚類分析工具,可以用于離群點(噪聲)檢測。聚類分析采用某種算法將大的數(shù)據(jù)集合根據(jù)數(shù)據(jù)相似性把所有數(shù)據(jù)劃分成簇,即采用相似度進行歸類,相似度較高的歸為一類,明顯不屬于任何一類的單個(或少量)數(shù)據(jù)集可認(rèn)為是異常數(shù)據(jù)。聚類算法有很多種,其中基于密度的方法(density-based method)考慮數(shù)據(jù)集中的每個對象,根據(jù)一定距離內(nèi)數(shù)據(jù)密度來劃分簇數(shù),數(shù)據(jù)比較密集的可以被認(rèn)為一個簇,而比較稀疏的區(qū)域則被認(rèn)為是噪聲。

有代表性的基于密度的全局鄰域(density-based spatial clustering of applications with noise,DBSCAN)算法將數(shù)據(jù)空間中的數(shù)據(jù)抽象為數(shù)據(jù)點,通過計算點之間距離和點密度來進行聚類,可將噪聲或離群點從簇內(nèi)分離。在DBSCAN算法使用中,需設(shè)置鄰域閾值(Eps)和點數(shù)閾值(Minpts)兩個參數(shù),根據(jù)參數(shù)將有一定密度的區(qū)域劃分為簇,且聚類結(jié)果對參數(shù)值敏感。

目前已有許多文獻對Eps和Minpts參數(shù)值的設(shè)定方法進行了研究。對于密度均勻的數(shù)據(jù),文獻[6]通過分析數(shù)據(jù)的統(tǒng)計特性來自適應(yīng)確定Eps和Minpts。對于不同密度數(shù)據(jù)的聚類,文獻[7]采用自適應(yīng)的Eps參數(shù);文獻[8]根據(jù)基于網(wǎng)絡(luò)與基于密度的聚類算法間的等效規(guī)則來計算不同密度的密度閾值;文獻[9]提出基于數(shù)據(jù)分區(qū)的PDBSCAN算法;文獻[10]提出基于網(wǎng)格分區(qū)來確定Eps的方法。

文中根據(jù)數(shù)據(jù)的統(tǒng)計特性,利用圖表的可視化結(jié)果,提出了一種確定DBSCAN算法參數(shù)的方法。

1 DBSCAN聚類算法的分析與實現(xiàn)

由于數(shù)據(jù)集中相似重復(fù)記錄的個數(shù)是不確定的,因此,要求聚類算法應(yīng)具有能夠發(fā)現(xiàn)任意形狀簇的能力。DBSCAN算法[11]可將具有足夠高密度的區(qū)域劃分為一個簇,簇數(shù)事先是不確定的,點的鄰域的形狀取決于兩點間的距離函數(shù)dist(p,q),對象間的距離是根據(jù)對象的屬性值計算得來的。因此,聚類結(jié)果取決于選擇哪些屬性變量、采用何種距離度量以及如何計算度量的屬性。

下面介紹用來描述算法的相關(guān)概念[12]。

(1)距離。

對象間的距離采用求數(shù)據(jù)相異度的方法。假設(shè)X1,X2代表數(shù)據(jù)集中的兩個數(shù)據(jù)對象,n是參與計算的數(shù)據(jù)對象的屬性個數(shù),每個數(shù)據(jù)對象用n維向量(Xi1,Xi2,…,Xin)表示,X1k,X2k分別為兩個數(shù)據(jù)點的第k維坐標(biāo)。d12是兩點間距離,有多種形式的距離度量可采用。如歐幾里德函數(shù),則d12可由如下公式計算:

(1)

其中,d12就表示這兩個數(shù)據(jù)對象的相異度。當(dāng)兩個對象越相似或接近時,d12值越接近0,而當(dāng)兩個對象越不相同或相距較遠(yuǎn)時,d12值越大。還可以根據(jù)每個屬性的重要性為其賦一個權(quán)重。

(2)鄰域、密度、核心點、邊界點。

數(shù)據(jù)集中任意一點的鄰域記為NEps(p),是數(shù)據(jù)集中與p點的距離小于給定Eps的點的集合。

NEps(p)={q∈D‖dist(p,q)≤Eps}

(2)

鄰域中點的個數(shù)稱為該點的密度,若其大于或等于給定的最小值MinPts,則稱點p為核心點,否則稱為邊界點。

(3)直接密度可達、密度可達、密度相連。

數(shù)據(jù)集中任意兩點p,q,如果q∈NEps(p),且|NEps(p)|≥MinPts,則稱點q是從點p關(guān)于Eps和MinPts直接密度可達的。

如果p,q兩點間存在一個點的序列p1,p2,…,pn,且p1=p,pn=q,pi+1是從pi直接密度可達的,則稱點q是從點p關(guān)于Eps和MinPts密度可達的。

如果存在一個點o,q和p都是從點o關(guān)于Eps和MinPts密度可達的,則稱點q是從點p關(guān)于Eps和MinPts密度相連的。

(4)簇。

數(shù)據(jù)集中基于密度的簇是基于密度可達的最大密度相連的點的集合。簇中的任意兩點是關(guān)于Eps和MinPts密度相連的。

給定參數(shù)Eps和MinPts,DBSCAN算法的實現(xiàn)就是生成相應(yīng)的簇。DBSCAN算法從任意點p開始,檢索所有從點p關(guān)于Eps和MinPts密度可達的點。如果p是核心點,就生成一個關(guān)于Eps和MinPts的簇;如果p是邊界點,且沒有從p密度可達的點,算法就去處理數(shù)據(jù)集中的下一個點。算法實現(xiàn)的流程參見圖1。

相比其他聚類算法,例如基于層次的算法等,DBSCAN算法的優(yōu)點是可以發(fā)現(xiàn)數(shù)據(jù)集中任意形狀的簇,它的聚類速度比較快,聚類能力也很強。但必須為每個簇指定恰當(dāng)?shù)腅ps和MinPts,及每個簇中的至少一個點。由于很難事先獲得數(shù)據(jù)集中所有簇的相關(guān)信息,DBSCAN算法實現(xiàn)時對所有簇采用相同的全局參數(shù)值Eps和MinPts,但把確定參數(shù)的任務(wù)留給用戶,而且算法生成的結(jié)果對參數(shù)是敏感的。如若根據(jù)數(shù)據(jù)集中存在的比較密集的區(qū)域,選取了一個較大的Minpts值,那么數(shù)據(jù)集中其他區(qū)域會因為密度不夠大而不能被劃分成簇,會造成噪聲點過多現(xiàn)象;若根據(jù)數(shù)據(jù)集中存在的比較稀疏的區(qū)域,選取了一個較小的Minpts值,那么整個數(shù)據(jù)集很容易直接被劃成一個大簇,參數(shù)值的微小變化往往會導(dǎo)致差異很大的聚類結(jié)果。

圖1 DBSCAN算法流程

2 DBSCAN聚類算法的參數(shù)配置

傳統(tǒng)DBSCAN算法中Eps和Minpts兩個參數(shù)是根據(jù)經(jīng)驗設(shè)置的,并根據(jù)聚類結(jié)果進行調(diào)整。這樣做顯然盲目性大,工作量也大,而且效果也不一定好。因此,文中提出了一種參數(shù)的判斷方法,該方法的主要思想是根據(jù)數(shù)據(jù)集本身的統(tǒng)計特性以及圖表的可視化結(jié)果由人工來選擇參數(shù)。

2.1 Eps參數(shù)的確定方法

首先按式1計算數(shù)據(jù)對象間的距離,得到距離矩陣Distn×n。

Distn×n={dist(i,j),1≤i≤n,1≤j≤n}

(3)

其中,n是數(shù)據(jù)集D中的數(shù)據(jù)對象個數(shù),每個元素表示對象i到對象j的距離。

求出矩陣后,將行向量按升序排序。這樣,每行就是相應(yīng)數(shù)據(jù)點到其他所有點距離的一個排序。則矩陣Distn×i中第i列的數(shù)據(jù)的意義是距每個數(shù)據(jù)點最近的第i個距離值的集合。為觀察取不同i值(如1,2,…,7)時數(shù)值集合的統(tǒng)計特點,繪制圖形,其中圖2是距離值的概率密度分布曲線,圖3是對第i列數(shù)據(jù)進行升序排序后的曲線。數(shù)據(jù)采用的是隨機生成的含有150個數(shù)據(jù)點的二維數(shù)據(jù)集Dataset1。

圖2 距離值的概率密度分布曲線

圖3 距每個數(shù)據(jù)點最近的第i個距離值的升序曲線

圖2中,曲線均值越大的是對應(yīng)i值越大的曲線??梢钥吹?,無論i取多少,曲線的分布都大概成泊松分布。曲線右側(cè),距離比較大的地方(圖中接近0.4)密度已變得非常小,這些比例很小卻和其他點相比距離明顯偏大很多的點,噪聲的可能性較大。因此,可以考慮以此來確定Eps參數(shù)。

圖3中,曲線由下至上依次是i值增大對應(yīng)的曲線。曲線的趨勢大致相同,前期和中間都比較平緩,末端陡峭。可以發(fā)現(xiàn),當(dāng)i大于4以后,曲線的陡峭點都大概集中在一個區(qū)域,即圖中圓形標(biāo)注內(nèi)。在Martin Ester等的研究[13]中,對此問題也有描述。若取陡峭點對應(yīng)的距離作為鄰域閾值,可以估計,當(dāng)i大于4以后,對噪聲的劃分情況是近似一樣的,也就是聚類和噪聲檢測結(jié)果趨于穩(wěn)定。

所以,取i等于4時,曲線的陡峭點對應(yīng)的距離值作為DBSCAN算法中的Eps參數(shù),即圖3中圓圈標(biāo)注的縱坐標(biāo),大概在0.3~0.4之間,與圖2的分析一致。

2.2 Minpts參數(shù)的確定方法

前面Eps的取值是取距每個數(shù)據(jù)點最近的第4個距離值集合升序排序后曲線的陡峭點對應(yīng)的距離值,即假定Minpts為4。但由于第一步需人工參與判斷,很可能出現(xiàn)誤差,而且固定的Minpts值設(shè)定不能保證對任意的數(shù)據(jù)集檢測都有比較好的效果。為了能夠更匹配已經(jīng)確定的Eps值,可根據(jù)人們實際中對噪聲判斷的標(biāo)準(zhǔn),再重新確定Minpts值。該思想融合了Alex Rodriguez等[14]提出的新型聚類算法的思想,即對于一般數(shù)據(jù)集,簇中心被局部密度較高的鄰居點所包圍,而高局部密度的點之間距離比較大。首先,根據(jù)2.1中確定Eps的方法得到Eps的值,然后計算每個數(shù)據(jù)點i的局部密度值ρi,即數(shù)據(jù)點鄰域半徑(Eps)內(nèi)包含的鄰居點數(shù),再利用式4計算每個數(shù)據(jù)點i距更高密度點的距離δi,對于具有最高密度的點,δi的取值為其到數(shù)據(jù)集中最遠(yuǎn)點的距離。

(4)

數(shù)據(jù)集仍采用隨機生成的含有150個數(shù)據(jù)點的二維數(shù)據(jù)集Dataset1,對每個數(shù)據(jù)點計算上述兩個值,并以點圖(如圖4)的形式表現(xiàn),圖中的點就是數(shù)據(jù)集的每個對象。

圖4 Dataset1中每個點δi與ρi的函數(shù)關(guān)系

為了進一步說明該圖的意義,又采用隨機生成的含有51個數(shù)據(jù)點的二維數(shù)據(jù)集Dataset2,計算得到每個點δi與ρi的函數(shù)關(guān)系,如圖5所示。

在圖5中,右上角的點δi比較大并且ρi也比較高,應(yīng)該是一個簇的中心,而圖中左邊的點ρi非常小、δi又相對比較大的點更多是噪聲。根據(jù)δi與ρi的函數(shù)關(guān)系點圖,在聚類前,就可以得到數(shù)據(jù)聚類后的一個大概情況。對于數(shù)據(jù)集Dataset2,由圖5可知數(shù)據(jù)集大概集中在一個區(qū)域,并且有少量噪聲點,其中,數(shù)據(jù)對象點1(圖中箭頭標(biāo)注),其ρ為0,并且δ非常大,可以肯定是一個噪聲點;數(shù)據(jù)對象點2和3雖然ρ也比較小,但δ相對不是很大,所以只是有可能是噪聲點,因為DBSCAN聚類的簇是密度相連接的點集。若選取Minpts為7(ρ=7),可以預(yù)測聚類檢測結(jié)果,橫軸坐標(biāo)為7右側(cè)的點肯定是核心點,不會是噪聲,而左邊那些比較稀疏的點則有可能存在要尋找的噪聲點。在圖4中,可以判斷數(shù)據(jù)集大概集中在兩個區(qū)域,也有可能存在噪聲。若選取Minpts為2(ρ=2),橫坐標(biāo)為2左側(cè)的三個點有可能是要檢測的異常噪聲點;若選取Minpts為5,橫坐標(biāo)為5左側(cè)的六個點都有可能是要檢測的異常噪聲點。

圖5 Dataset2中每個點δi與ρi的函數(shù)關(guān)系

因此,利用δi與ρi的函數(shù)關(guān)系點圖,Minpts值的設(shè)置就轉(zhuǎn)換成了ρ閾值的選取問題,可選取圖中左邊稀疏點和密集點分界處的橫坐標(biāo)(ρ值)。在實際應(yīng)用中,若對噪聲的要求不是很嚴(yán)格,即偏差度不是很大就可以認(rèn)為是噪聲的話,可選取比較大的ρ閾值(Min-pts值);否則,可選取比較小的ρ閾值(Minpts值)。

3 數(shù)據(jù)異常檢測分析

下面在美國加州大學(xué)信息與計算機科學(xué)系的Iris(鳶尾花)數(shù)據(jù)集上,應(yīng)用DBSCAN聚類算法對數(shù)據(jù)進行異常檢測分析,檢驗所提出的參數(shù)配置方法的有效性。

首先對數(shù)據(jù)集進行改造,添加了兩個異常點,即補充了第151個數(shù)據(jù)點(第152行),該數(shù)據(jù)點因花瓣的長度(12)錄入有誤,造成異常;修改第70個數(shù)據(jù)點(第71行),使其class屬性值由原數(shù)據(jù)集中的Iris-versicolor改為Iris-virginica。處理后的Iris(鳶尾花)數(shù)據(jù)集的部分?jǐn)?shù)據(jù)如表1所示,數(shù)據(jù)集有4個數(shù)值型屬性,1個字符型屬性。

DBSCAN算法通過計算各個數(shù)據(jù)點的歐氏距離來聚類,要求參與計算的是數(shù)值型的屬性。但是,在實際中,通常會有字符型屬性,若將其舍棄,必然會喪失數(shù)據(jù)信息的完整性。文中將這類屬性分為兩類。一類是序數(shù)類型屬性,比如軍銜(少尉,中尉,上尉……)。這類屬性的特點是不同屬性之間有聯(lián)系,而且是等距離的。所以,可將其替換為數(shù)值1,2,3……。另一類是標(biāo)稱分類屬性的,比如國別(中國,美國,俄羅斯……)。若數(shù)據(jù)中有多個此類型的屬性,通常只選取一個有代表性的參與運算。文中是在數(shù)據(jù)處理中按標(biāo)稱屬性產(chǎn)生概念分層的方法。在聚類前,自動按標(biāo)稱屬性分區(qū)聚類,不同的分區(qū)選取不同的參數(shù)設(shè)定。這樣的處理雖然增加了工作量,但是不僅保證了信息的完整性,而且解決了數(shù)據(jù)密度不均勻卻只有一個全局參數(shù)設(shè)定的缺陷。

表1 待檢測的Iris數(shù)據(jù)集的部分?jǐn)?shù)據(jù)

對Iris(鳶尾花)數(shù)據(jù)集的檢測按class屬性值Iris-setosa,Iris-versicolor,Iris-virginica進行分區(qū),即分為3個區(qū),對每個分區(qū)分別進行算法的參數(shù)設(shè)置。采用前述的參數(shù)配置方法,通過可視化的判定,設(shè)置Eps分別取值1.5、0.9、1,Minpts分別取值12、2、2,從程序輸出檢測結(jié)果可以看到,除了檢測出之前添加的兩個異常點外,還檢測出兩個異常點,分別是第42個數(shù)據(jù)點和第61個數(shù)據(jù)點。在原數(shù)據(jù)集中找到這兩個點并進行人工檢查,可以發(fā)現(xiàn)第42個數(shù)據(jù)點的sepal width屬性值和其他Iris-setosa類鳶尾花相比是最小的,而且偏差比較大,而第61個數(shù)據(jù)點的四個數(shù)值屬性值和其他Iris-versicolor類鳶尾花相比都是比較小的,這也就解釋了這兩個點被認(rèn)為是離群噪聲點的原因。因此,從數(shù)據(jù)集的檢測結(jié)果來看,該方法的參數(shù)設(shè)置是比較準(zhǔn)確的,異常檢測的結(jié)果也是非常有效的。

為了進一步說明參數(shù)設(shè)置的準(zhǔn)確性,將參數(shù)Eps統(tǒng)一取值為1,Minpts統(tǒng)一取值為4,得到的異常檢測結(jié)果輸出了7個異常點,其中一些異常點并不符合對異常點的判斷標(biāo)準(zhǔn)。這說明DBSCAN算法對參數(shù)是敏感的,當(dāng)參數(shù)設(shè)置不合適時,其檢測結(jié)果也將不準(zhǔn)確,也驗證了文中算法是有效的。

4 結(jié)束語

對數(shù)據(jù)異常檢測問題進行了研究,將基于密度的DBSCAN聚類算法用于數(shù)據(jù)的異常檢測,并針對該算法在應(yīng)用過程中對參數(shù)設(shè)置敏感的問題,提出了一種配置算法鄰域閾值(Eps)和點數(shù)閾值(Minpts)的方法。該方法可根據(jù)數(shù)據(jù)集本身的統(tǒng)計特性以及圖表的可視化展示,為算法確定合適的參數(shù)。編程實現(xiàn)了DBSCAN聚類算法及輔助參數(shù)確定的計算,并利用MATLAB工具進行可視化展現(xiàn)。并在Iris數(shù)據(jù)集上進行檢測,通過對比測試,驗證了用該方法進行DBSCAN聚類算法參數(shù)的設(shè)置是可行的,彌補了DBSCAN聚類算法參數(shù)設(shè)置單靠經(jīng)驗的傳統(tǒng)做法,使得檢測結(jié)果的準(zhǔn)確性和可伸縮性更好。

目前,該DBSCAN聚類算法參數(shù)配置方法需要人工參與判定,仍存在一定的人為因素,同時參數(shù)判定的過程還比較麻煩耗時,這些都有待進一步的改進提高。

猜你喜歡
聚類噪聲密度
艦船通信中的噪聲消除研究
一種傅里葉域海量數(shù)據(jù)高速譜聚類方法
大尺寸高相對密度鎢管的制備
汽車制造企業(yè)噪聲綜合治理實踐
面向WSN的聚類頭選舉與維護協(xié)議的研究綜述
改進K均值聚類算法
基于Spark平臺的K-means聚類算法改進及并行化實現(xiàn)
“密度”練習(xí)
密度的不變性與可變性
汽車變速器嘯叫噪聲處治
涡阳县| 辽阳县| 南丹县| 福鼎市| 故城县| 广元市| 南和县| 镇远县| 丰宁| 永安市| 安乡县| 桐梓县| 和顺县| 嘉定区| 芜湖县| 梁山县| 蕉岭县| 吉安市| 桦川县| 吉林省| 宣城市| 阿巴嘎旗| 桐乡市| 平谷区| 民权县| 疏附县| 永善县| 禹城市| 贵南县| 岢岚县| 宜春市| 汕头市| 琼结县| 太仆寺旗| 桂平市| 安仁县| 咸阳市| 玉龙| 旬阳县| 蒙山县| 长沙市|