黃劍柔,王 茜,蔡星娟,李建偉

(太原科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,太原 030024)

1 引 言

作為數(shù)據(jù)挖掘的主要研究?jī)?nèi)容之一,離群點(diǎn)檢測(cè)是通過(guò)某種特定方法從給定數(shù)據(jù)集中找出少數(shù)和其他多數(shù)數(shù)據(jù)具有顯著差別的數(shù)據(jù)點(diǎn)的一個(gè)過(guò)程[1,2],這些異常數(shù)據(jù)可能是錯(cuò)誤的數(shù)據(jù)或者是數(shù)據(jù)處理過(guò)程中引起的誤差,也可能是來(lái)源于不同的類(lèi),它們與正常數(shù)據(jù)之間存在著顯著的差異.離群點(diǎn)檢測(cè)在很多領(lǐng)域有著非常廣泛的應(yīng)用前景,例如,惡意代碼檢測(cè)[3]、入侵檢測(cè)[4]、欺詐行為[5]等.傳統(tǒng)的離群點(diǎn)檢測(cè)方法分別是基于統(tǒng)計(jì),基于距離,基于密度和基于聚類(lèi)進(jìn)行的.

基于統(tǒng)計(jì)的離群點(diǎn)檢測(cè)方法[6]主要是基于模型進(jìn)行的,它的主要思想是先為數(shù)據(jù)創(chuàng)建一個(gè)模型,然后對(duì)對(duì)象進(jìn)行擬合,最后根據(jù)擬合程度來(lái)進(jìn)行評(píng)估.對(duì)于此方法,數(shù)據(jù)集的分布情況是十分重要的,需要事先了解,否則錯(cuò)誤的估計(jì)會(huì)導(dǎo)致重尾分布.但是多數(shù)情況下,我們都不知道數(shù)據(jù)的實(shí)際分布情況,而且它不適用于高維屬性的數(shù)據(jù)集,因此,在離群點(diǎn)檢測(cè)中基于統(tǒng)計(jì)的離群點(diǎn)檢測(cè)方法不經(jīng)常被使用.

基于距離的離群點(diǎn)檢測(cè)方法主要有效地解決了基于統(tǒng)計(jì)的方法不能處理的高維數(shù)據(jù)集和無(wú)法預(yù)知數(shù)據(jù)集分布情況的問(wèn)題,它主要是通過(guò)選取不同的距離度量方式作為離群點(diǎn)的判斷方式,其中的代表算法有K近鄰(KNN,K-Nearest Neighbor)算法[7],逆K近鄰(RKNN,Reverse K-Nearest Neighbor)算法[8]及其它們的改進(jìn)算法[9].但此方法是針對(duì)全局?jǐn)?shù)據(jù)集的,不適用于對(duì)局部離群數(shù)據(jù)的檢測(cè).

基于密度的離群點(diǎn)檢測(cè)方法主要適用于分布不均勻的數(shù)據(jù)集,同時(shí)也可以很好解決基于距離的不足.其最具有代表性的算法是由Breuing提出的局部離群因子(LOF,Local Outlier Factor)算法[10],在此基礎(chǔ)上,胡彩平提出了DLOF算法[11],將信息熵引入到LOF中用于確定數(shù)據(jù)的離群屬性,并在數(shù)據(jù)之間距離的求取過(guò)程中加入權(quán)值,但它在提升離群點(diǎn)檢測(cè)效率的同時(shí)增加了計(jì)算量.鄒云峰等人提出了LDBO算法[12],該算法在處理數(shù)據(jù)分布存在異常的離群點(diǎn)檢測(cè)問(wèn)題中同時(shí)應(yīng)用了強(qiáng)K近鄰點(diǎn)和弱K近鄰點(diǎn),以此對(duì)數(shù)據(jù)進(jìn)行了區(qū)分對(duì)待,提高了算法的效率.但是基于密度的離群點(diǎn)檢測(cè)中帶有求解距離的公式,時(shí)間復(fù)雜度較高,在高維數(shù)據(jù)中的效果并不是很好.

聚類(lèi)分析[13]和離群點(diǎn)檢測(cè)都是數(shù)據(jù)挖掘中很有研究前景的重要方向,且聚類(lèi)和離群點(diǎn)檢測(cè)密切相關(guān),因此,出現(xiàn)了基于聚類(lèi)的離群點(diǎn)檢測(cè)方法.其最具代表性的算法有K-means,層次聚類(lèi),STING和DBSCAN等.K-means聚類(lèi)算法[14]的關(guān)鍵在于參數(shù)K的選擇,首先確定合適的K值,再把每個(gè)數(shù)據(jù)點(diǎn)都劃分到離它最近的聚類(lèi)中心的簇中,最后不屬于任何簇的數(shù)據(jù)點(diǎn)則為離群點(diǎn).但是K值的不確定性會(huì)影響聚類(lèi)和離群點(diǎn)檢測(cè)的結(jié)果.Chameleon算法[15]是一種經(jīng)典的動(dòng)態(tài)層次聚類(lèi)算法,它的核心思想是通過(guò)合并來(lái)進(jìn)行聚類(lèi),但它和K-means類(lèi)似,需要預(yù)先確定聚類(lèi)數(shù)目K的大小,檢測(cè)精度不高.STING算法[16]是一種基于劃分多層次網(wǎng)格的聚類(lèi)方法,將數(shù)據(jù)空間劃分為矩形網(wǎng)格,再根據(jù)不同的分辨率把矩形網(wǎng)格劃分為不同的層次結(jié)構(gòu),但其網(wǎng)格空間最底層的粒度對(duì)聚類(lèi)和異常檢測(cè)的精度有很大影響.由于部分常用聚類(lèi)算法并沒(méi)有普適性,且算法和數(shù)據(jù)集之間具有不確定關(guān)系,只能針對(duì)于特定的數(shù)據(jù)集使用,如果用于不同的數(shù)據(jù)集則會(huì)導(dǎo)致聚類(lèi)的效果變差,隨之離群點(diǎn)檢測(cè)的精度也會(huì)下降.DBSCAN算法[17]是由Martin Ester等人提出的一種基于密度的聚類(lèi)算法,提出后在數(shù)據(jù)挖掘領(lǐng)域受到了廣泛關(guān)注,主要應(yīng)用于生物科學(xué)、商業(yè)營(yíng)銷(xiāo)、社交網(wǎng)絡(luò)分析和計(jì)算機(jī)科學(xué)等方面,展現(xiàn)出了強(qiáng)大的效果.基于上述DBSCAN的廣泛應(yīng)用和獨(dú)特優(yōu)勢(shì),本文著重研究了該算法在自適應(yīng)選擇參數(shù)配置上的優(yōu)化改進(jìn),解決了最優(yōu)參數(shù)靠經(jīng)驗(yàn)選擇的不足,并針對(duì)該算法無(wú)法在非均勻數(shù)據(jù)集上進(jìn)行有效的離群點(diǎn)檢測(cè)這一問(wèn)題進(jìn)行了深入的研究.

傳統(tǒng)基于DBSCAN算法的離群點(diǎn)檢測(cè)中,兩個(gè)參數(shù)Eps和minPts的設(shè)置比較復(fù)雜,需要不斷進(jìn)行測(cè)試,才能找出用戶(hù)需求的參數(shù),但這種情況下參數(shù)對(duì)結(jié)果的影響具有很大的敏感性;而且由于數(shù)據(jù)的密度分布不均勻,密度大的數(shù)據(jù)點(diǎn)需要一個(gè)較大的Eps,密度小的數(shù)據(jù)點(diǎn)需要一個(gè)較小的Eps,統(tǒng)一的全局Eps會(huì)淹沒(méi)部分離群點(diǎn).且近些年來(lái),多目標(biāo)優(yōu)化算法也是研究的重點(diǎn).因此,為了避免人為設(shè)置參數(shù)的困難和誤差,本文提出一種新的基于NSGA-II算法的自適應(yīng)DBSCAN離群點(diǎn)檢測(cè)方法.首先,使用DBSCAN來(lái)找出原始數(shù)據(jù)集中的有可能為離群點(diǎn)的數(shù)據(jù)子集,其中原始數(shù)據(jù)集中的每個(gè)數(shù)據(jù)點(diǎn)可以采用不同的Eps,而這個(gè)Eps是通過(guò)多目標(biāo)優(yōu)化算法NSGA-II求解得到的,不但可以避免人為設(shè)定參數(shù)問(wèn)題,而且可以反映出數(shù)據(jù)集本身的特征.其次,使用基于Eps的LOF算法計(jì)算篩選后數(shù)據(jù)子集中各數(shù)據(jù)的離群得分,減少了計(jì)算量.最后,使用UCI不同數(shù)據(jù)集來(lái)進(jìn)行實(shí)驗(yàn),驗(yàn)證了本文算法的正確性和有效性.

2 問(wèn)題描述與模型介紹

對(duì)于離群點(diǎn)檢測(cè)這一重要問(wèn)題,本文主要是通過(guò)使用NSGA-II優(yōu)化的自適應(yīng)DBSCAN算法從原始數(shù)據(jù)集中篩選出最有可能為離群點(diǎn)的部分?jǐn)?shù)據(jù),再使用基于Eps的LOF算法對(duì)篩選出的數(shù)據(jù)進(jìn)行計(jì)算,以此找到最終的離群點(diǎn).

2.1 改進(jìn)的DBSCAN

DBSCAN通過(guò)參數(shù)(Eps,minPts)分析數(shù)據(jù)樣本分布程度的大小.其中Eps表示的是距離閾值,也就是以某一數(shù)據(jù)樣本為中心,以Eps大小為半徑的鄰域.minPts是以某一數(shù)據(jù)樣本為中心,Eps鄰域范圍內(nèi)數(shù)據(jù)點(diǎn)的個(gè)數(shù),DBSCAN中通常將其作為密度閥值來(lái)計(jì)算.傳統(tǒng)的基于DBSCAN檢測(cè)離群點(diǎn)方法的主要思想是將數(shù)據(jù)集聚類(lèi)之后,沒(méi)有被劃分到任何簇的數(shù)據(jù)點(diǎn)為離群點(diǎn).但是傳統(tǒng)DBSCAN算法通常采用人為經(jīng)驗(yàn)設(shè)定的參數(shù)作為全局統(tǒng)一參數(shù),這就會(huì)導(dǎo)致在非均勻密度數(shù)據(jù)集中的一些離群點(diǎn)的聚類(lèi)簇歸屬出現(xiàn)錯(cuò)誤,且通過(guò)該方法檢測(cè)的離群點(diǎn)會(huì)隨著參數(shù)Eps和minPts的變化而發(fā)生改變,這無(wú)法反應(yīng)真實(shí)有效的離群點(diǎn)分布情況.因此,我們通過(guò)改進(jìn)DBSCAN算法人為手動(dòng)設(shè)置參數(shù)和全局設(shè)置統(tǒng)一參數(shù)來(lái)有效避免部分?jǐn)?shù)據(jù)被錯(cuò)誤劃分的情況,從而能夠提高離群點(diǎn)檢測(cè)的準(zhǔn)確度.改進(jìn)的DBSCAN和傳統(tǒng)的DBSCAN算法示意圖如圖1(a)、圖1(b)所示.

圖1 DBSCAN與改進(jìn)的DBSCAN原理示意圖Fig.1 Principle diagrams of DBSCAN and the improved DBSCAN

圖1(a)為傳統(tǒng)的DBSCAN給每個(gè)數(shù)據(jù)點(diǎn)設(shè)置相同的半徑,對(duì)于密度分布不均勻的數(shù)據(jù)會(huì)降低檢測(cè)效率;圖1(b)圖是本文改進(jìn)的DBSCAN,它會(huì)根據(jù)數(shù)據(jù)的分布情況自適應(yīng)調(diào)節(jié)半徑Eps的大小,更能體現(xiàn)出數(shù)據(jù)本身的分布.

改進(jìn)的自適應(yīng)調(diào)節(jié)Eps參數(shù)的DBSCAN算法的偽代碼如算法1所示.

算法1.改進(jìn)的DBSCAN

輸入:數(shù)據(jù)集D,minPts,Eps(不同的數(shù)據(jù)設(shè)置不一樣的Eps,本文數(shù)據(jù)集中各數(shù)據(jù)的Eps由優(yōu)化算法NSGA-II求解)

輸出:離群點(diǎn)數(shù)據(jù)集

過(guò)程:標(biāo)記所有對(duì)象為未訪(fǎng)問(wèn);

創(chuàng)建新的簇C,創(chuàng)建離群點(diǎn)集合Q;

從任意一點(diǎn)p開(kāi)始,并進(jìn)行標(biāo)記;

If p的領(lǐng)域內(nèi)至少有minPts 個(gè)數(shù)據(jù)點(diǎn)

P加入到簇C;

令N為p的鄰域內(nèi)的對(duì)象集合;

For N中的各個(gè)數(shù)據(jù)

If q未標(biāo)記

對(duì)q進(jìn)行標(biāo)記;

判斷其Eps鄰域內(nèi)的數(shù)據(jù)個(gè)數(shù)是否大于minPts;

If q的領(lǐng)域內(nèi)至少有minPts 個(gè)數(shù)據(jù)點(diǎn)

q加入到簇C;

q的鄰域加入N;

else

q為離群點(diǎn),加入離群集Q;

End

End

else

標(biāo)記P為離群點(diǎn),并加入離群集Q;

End

2.2 基于NSGA-II算法的多目標(biāo)模型

在本文中,我們使用NSGA-II多目標(biāo)優(yōu)化算法為數(shù)據(jù)集中的每個(gè)數(shù)據(jù)點(diǎn)求解一個(gè)最優(yōu)的Eps,在該模型中,算法為數(shù)據(jù)集中的各個(gè)點(diǎn)隨機(jī)初始化一組Eps解,隨后的迭代過(guò)程中經(jīng)過(guò)選擇交叉變異進(jìn)行更新,以此尋找最優(yōu)解,我們具體的多目標(biāo)Eps優(yōu)化模型如下所示:

目標(biāo)1.我們定義DBSCAN算法中minPts與Eps的比值來(lái)測(cè)量離群度,minPts與Eps的比值越小,表示數(shù)據(jù)的離群度越高,因?yàn)樵陔x群數(shù)據(jù)的周?chē)?數(shù)據(jù)分布是比較稀疏的.

(1)

目標(biāo)2.在利用DBSCAN算法檢測(cè)離群點(diǎn)時(shí),半徑Eps內(nèi)的點(diǎn)到簇類(lèi)中心的距離越遠(yuǎn)則越可能是離群點(diǎn).

(2)

(3)

在這里,distance(Pi,Ci)表示Pi到簇類(lèi)中心Ci的距離,距離越大表示數(shù)據(jù)Pi離Ci越遠(yuǎn),屬于Ci的程度越低,越可能是離群點(diǎn).

因此,本文綜合考慮以上兩個(gè)目標(biāo),將該問(wèn)題形象描述為:

min[F1,F2]

(4)

約束條件如下:

Eps(i)

(5)

在這里,r是指包含所有數(shù)據(jù)點(diǎn)的最大半徑,如果Eps過(guò)大則失去了聚類(lèi)和離群檢測(cè)的意義.公式(5)表明Eps最大不能大于包含所有的數(shù)據(jù)點(diǎn)的半徑.

2.3 LOF

LOF是一種基于密度的離群點(diǎn)檢測(cè)方法,其主要是通過(guò)比較每個(gè)數(shù)據(jù)點(diǎn)和其鄰域數(shù)據(jù)點(diǎn)的密度大小來(lái)判斷該數(shù)據(jù)點(diǎn)是否為異常點(diǎn),密度低的數(shù)據(jù)點(diǎn)則可能被識(shí)別為異常點(diǎn).由于LOF主要是通過(guò)數(shù)據(jù)的K距離來(lái)計(jì)算距離,因此本文算法的K距離使用DBSCAN優(yōu)化出的Eps來(lái)代替,減少了算法的時(shí)間復(fù)雜度.

3 算法介紹

3.1 算法基本思想

NSGA-II是一種改進(jìn)經(jīng)典N(xiāo)SGA的多目標(biāo)優(yōu)化算法,它適合應(yīng)用于復(fù)雜的、多目標(biāo)優(yōu)化問(wèn)題,其主要通過(guò)改進(jìn)NSGA的不足,增加了選擇壓力,提高了搜索速度.NSGA具有較高的算法時(shí)間復(fù)雜度,特別是在種群規(guī)模較大時(shí),非支配排序速度會(huì)變得很慢,NSGA-II采用了帶有精英選擇策略的快速非支配排序,在減小排序時(shí)間復(fù)雜度的同時(shí)還保證了算法的收斂性.精英選擇策略保留上一代種群中的最優(yōu)個(gè)體,加強(qiáng)了搜索能力.在種群多樣性方面,NSGA使用共享函數(shù)來(lái)保證解的均勻分布,但是共享函數(shù)的方法在保證種群多樣性的方面常常依賴(lài)于共享參數(shù)的選擇;種群中的個(gè)體之間需要相互比較,共享函數(shù)的復(fù)雜度較高,而NSGA-II重新定義了擁擠距離來(lái)代替共享參數(shù).

基于NSGA-II的DBSCAN離群點(diǎn)檢測(cè)偽代碼如算法2所示.

算法2.基于NSGA-II的DBSCAN離群點(diǎn)檢測(cè)

開(kāi)始

輸入:數(shù)據(jù)集D,交叉算子(Pc),變異算子(Pm),最大迭代次數(shù)(Gmax),minPts.

初始化:根據(jù)公式(1)和公式(2)計(jì)算目標(biāo)值;

快速非支配排序;

選擇,交叉,變異;

迭代次數(shù)(Gen)= 1;

While Gen < Gmax do

結(jié)合子代和父代種群;

根據(jù)公式(1)和公式(2)計(jì)算目標(biāo)函數(shù)值;

快速非支配排序;

選擇操作;

If rand()

交叉操作;

End

If rand()

變異操作;

End

Gen = Gen +1;

End

求解得到數(shù)據(jù)集中各個(gè)數(shù)據(jù)點(diǎn)對(duì)應(yīng)的Eps;

根據(jù)算法1改進(jìn)的DBSCAN,篩選出離群點(diǎn)集合;

對(duì)于DBSCAN篩選出的離群點(diǎn)集,使用LOF計(jì)算每個(gè)數(shù)據(jù)點(diǎn)的離群得分,在LOF中,我們要求K距離和相應(yīng)數(shù)據(jù)的Eps保持一致;

輸出:離群點(diǎn)集合.

結(jié)束

3.2 算法具體實(shí)現(xiàn)

利用NSGA-II改進(jìn)DBSCAN算法的具體介紹如下:

1)對(duì)于DBSCAN中每個(gè)數(shù)據(jù)點(diǎn)的Eps的求解,我們采用實(shí)數(shù)編碼方法,假設(shè)輸入數(shù)據(jù)集中數(shù)據(jù)點(diǎn)的個(gè)數(shù)為N,則隨機(jī)產(chǎn)生規(guī)模為N的初始種群POP,本文的種群是:{x1,x2,x3,…,xN},分別對(duì)應(yīng)使用DBSCAN檢測(cè)離群點(diǎn)時(shí)輸入數(shù)據(jù)集中每個(gè)數(shù)據(jù)對(duì)應(yīng)的半徑參數(shù)Eps.這里選擇方式使用二元錦標(biāo)賽方法,即對(duì)POP中個(gè)體進(jìn)行快速非支配排序和擁擠距離比較產(chǎn)生父代種群P.

快速非支配排序結(jié)果中的排序值越小,說(shuō)明它被剩下其他個(gè)體支配的次數(shù)就越小,有著越大的概率被選擇.擁擠距離的計(jì)算方法為該個(gè)體與其相鄰的兩個(gè)個(gè)體形成的矩形的長(zhǎng)寬和.在排序值相同的情況下,要保留擁擠距離更大的個(gè)體.

2)通過(guò)交叉、變異操作得到子代種群Q,并將父代種群P與子代種群Q合并為一個(gè)新的種群R.

交叉:交叉是為了使父代的優(yōu)良基因可以遺傳給子代,本文采用模擬二進(jìn)制交叉方法(SBX),交叉分布指數(shù)設(shè)置為1,其原理圖如圖2所示:P1和P2為父代,Q1和Q2為子代,在交叉點(diǎn)處進(jìn)行標(biāo)記,交換兩個(gè)父代交叉點(diǎn)之后的基因片段,得到新的兩個(gè)子代.

圖2 交叉原理圖Fig.2 Cross instance

變異:變異是為了改善算法的局部搜索能力,維持種群的多樣性.它是以一定的概率進(jìn)行的,此處設(shè)置為0.1.本文變異原理圖如圖3所示:在子代中以變異概率找出兩處基因變異位,然后交換其基因,以此生成新的子代.

圖3 變異原理圖Fig.3 Variation instance

3)利用精英策略產(chǎn)生下一代群體.其主要是采用快速非支配排序策略對(duì)R中的個(gè)體進(jìn)行排序,且在每個(gè)非支配層中,對(duì)個(gè)體進(jìn)行擁擠度的計(jì)算,根據(jù)計(jì)算得出的非支配關(guān)系和個(gè)體擁擠度聯(lián)合選取最優(yōu)的個(gè)體構(gòu)成下一代種群.

4 仿真實(shí)驗(yàn)及結(jié)果分析

4.1 參數(shù)與環(huán)境

本文所有實(shí)驗(yàn)均是在Matlab R2018a版本上實(shí)驗(yàn)的,且為了驗(yàn)證本文模型和算法的有效性,我們?cè)O(shè)置了兩組實(shí)驗(yàn):一是本文所提模型在不同數(shù)據(jù)集之間的對(duì)比;二是不同離群點(diǎn)檢測(cè)算法的對(duì)比,對(duì)比算法包括:LOF,K近鄰,DBSCAN.此外,本文涉及到的參數(shù)設(shè)置如表1所示.

表1 參數(shù)設(shè)置Table 1 Parameter setting

4.2 數(shù)據(jù)集

為了驗(yàn)證本文算法對(duì)于多種形態(tài)數(shù)據(jù)集的普適性,本文使用了UCI數(shù)據(jù)集中的不同數(shù)據(jù)集.

對(duì)于UCI數(shù)據(jù)集,由于預(yù)先知道測(cè)試數(shù)據(jù)集中的每個(gè)對(duì)象所屬于的真正類(lèi),所以將數(shù)據(jù)集中小類(lèi)中的對(duì)象定義為異常數(shù)據(jù)對(duì)象.對(duì)于小類(lèi)對(duì)象中數(shù)據(jù)較多的,本文從小類(lèi)中隨機(jī)選取出少數(shù)點(diǎn)作為離群數(shù)據(jù).本文實(shí)驗(yàn)中使用的UCI數(shù)據(jù)集如表2所示.

表2 UCI數(shù)據(jù)集Table 2 UCI data set

采用以下的準(zhǔn)確率對(duì)算法的離群精度進(jìn)行評(píng)價(jià):

(6)

在這里,precision表示檢測(cè)出的離群點(diǎn)和原始數(shù)據(jù)中離群點(diǎn)個(gè)數(shù)的比值,N2為檢測(cè)出的離群點(diǎn)總數(shù),N1為檢測(cè)出的正確的離群點(diǎn)個(gè)數(shù).準(zhǔn)確度越高,表示所提算法越有效.

4.3 實(shí)驗(yàn)分析

4.3.1 算法結(jié)果分析

本文的離群點(diǎn)檢測(cè)方法主要分為兩個(gè)步驟,先選取一個(gè)離群子集,再進(jìn)行離群點(diǎn)確定.經(jīng)過(guò)大量的仿真實(shí)驗(yàn),不同數(shù)據(jù)集下的實(shí)驗(yàn)結(jié)果如表3所示.

表3 本文方法檢測(cè)離群點(diǎn)結(jié)果Table 3 Outlier detection results

從表3可以看出:對(duì)于iris和zoo數(shù)據(jù)集,在第1步得到的離群點(diǎn)子集中便包括了全部離群點(diǎn),第2步的計(jì)算可以精確的選擇出所有離群點(diǎn);對(duì)于yeast數(shù)據(jù)集中,在第1步得到的離群點(diǎn)子集中,缺失了一個(gè)離群點(diǎn),第2步檢測(cè)出了離群點(diǎn)子集中的全部離群點(diǎn);對(duì)于wine數(shù)據(jù)集,算法的第1步可以得到所有離群點(diǎn),在第2步缺失了一個(gè);但是整體來(lái)看,本文算法在第1步篩選出的離群點(diǎn)子集幾乎會(huì)包含所有的離群點(diǎn),再通過(guò)第2步的基于Eps參數(shù)的LOF算法進(jìn)行檢測(cè),具有很高的離群點(diǎn)檢測(cè)效率.

4.3.2 離群點(diǎn)檢測(cè)算法對(duì)比

為了對(duì)離群檢測(cè)算法的準(zhǔn)確率進(jìn)行評(píng)估,在UCI數(shù)據(jù)集上采用不同離群點(diǎn)算法(LOF,K近鄰,DBSCAN)進(jìn)行了實(shí)驗(yàn)對(duì)比.為了減少人為設(shè)置參數(shù)帶來(lái)的實(shí)驗(yàn)誤差,本文取了不同參數(shù)下30次實(shí)驗(yàn)的平均值,具體實(shí)驗(yàn)結(jié)果如表4和圖3所示.

表4 不同算法準(zhǔn)確率對(duì)比Table 4 Comparison of accuracy of different algorithms

由表4可以得出,對(duì)于不同的數(shù)據(jù)集,不同的離群點(diǎn)檢測(cè)方法具有不同的精確率.對(duì)于iris數(shù)據(jù)集,本文算法的準(zhǔn)確率達(dá)到了0.9943,LOF次之,DBSCAN效果最差;對(duì)于yeast數(shù)據(jù)集,LOF略高于本文算法,K近鄰算法最差;對(duì)于wine和zoo數(shù)據(jù)集,可以得出相同的結(jié)論.整體來(lái)說(shuō),相對(duì)于其他3種算法,本文算法具有較優(yōu)的性能.

為了更直觀的分析實(shí)驗(yàn)結(jié)果,對(duì)不同算法的離群點(diǎn)檢測(cè)結(jié)果做了柱狀圖.從圖4依舊可看出,本文算法具有最高的離群點(diǎn)檢測(cè)準(zhǔn)確率,LOF的準(zhǔn)確率較低,而K近鄰和DBSCAN的準(zhǔn)確率最低.

圖4 準(zhǔn)確率變化趨勢(shì)柱狀圖Fig.4 Histogram of variation trend of accuracy

5 結(jié) 論

本文針對(duì)DBSCAN離群點(diǎn)檢測(cè)算法中全局參數(shù)Eps的不確定問(wèn)題,通過(guò)構(gòu)建多目標(biāo)模型,使用多目標(biāo)優(yōu)化算法NSGA-II對(duì)數(shù)據(jù)集中每個(gè)數(shù)據(jù)對(duì)應(yīng)的Eps進(jìn)行優(yōu)化求解,以此選取出離群點(diǎn)子集;其次,再對(duì)由上一步選取出的離群點(diǎn)子集進(jìn)行LOF計(jì)算,在LOF中,我們使用相應(yīng)數(shù)據(jù)的Eps代替其k距離,也避免了k距離的選擇問(wèn)題.最后,通過(guò)仿真實(shí)驗(yàn)證明了多目標(biāo)模型的合理性和算法在不同數(shù)據(jù)集下的有效性.

在未來(lái)的工作中,我們將考慮DBSCAN算法中的另一個(gè)參數(shù)minPts的自適應(yīng)選擇問(wèn)題,通過(guò)自適應(yīng)的確定DBSCAN算法中的兩個(gè)參數(shù),提高高維數(shù)據(jù)的聚類(lèi)效果和離群點(diǎn)檢測(cè)效率.另外,我們還可以考慮建設(shè)高維多目標(biāo)模型,對(duì)參數(shù)進(jìn)行優(yōu)化求解.