宋金玉，郭一平，王 斌

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

0 引 言

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

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

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

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

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

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

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

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

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

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

(1)距離。

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

(1)

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

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

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

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

(2)

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

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

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

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

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

(4)簇。

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

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

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

圖1 DBSCAN算法流程

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

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

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

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

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

(3)

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

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

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

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

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

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

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

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

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

(4)

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

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