謝 兄,唐 昱

(大連海事大學(xué) 信息科學(xué)技術(shù)學(xué)院,遼寧 大連 116026)

1 引 言

離群點檢測技術(shù)在許多領(lǐng)域中都有所應(yīng)用,如網(wǎng)絡(luò)入侵檢測[1,2]、欺詐檢測[3]、工業(yè)損傷檢測[4]等,其目的是消除噪聲或發(fā)現(xiàn)數(shù)據(jù)中行為異常的“部分”數(shù)據(jù).離群點集合是數(shù)據(jù)集中的一個特殊子集,在不同的領(lǐng)域有不同的定義,通常又被稱為異常點、偏差點、噪聲點等.Hawkins將離群點定義為[5]:一個離群點是一個觀察點,它偏離其它觀察點如此大以至于懷疑是由不同機制產(chǎn)生的.在早期的聚類算法和一些離群點檢測算法研究中,研究對象通常是基于整體數(shù)據(jù)集,檢測算法可以檢測出一些全局離群點[6].然而在實際應(yīng)用中,所獲得的數(shù)據(jù)通常是不完整的,許多情況下只關(guān)心局部范圍內(nèi)數(shù)據(jù)所包含的信息,需要進行局部離群點檢測.Breuing最先提出局部離群點的定義[7]:局部離群點是指在數(shù)據(jù)集中與其鄰域表現(xiàn)不一致或偏離其鄰域的觀測點.已有的離群點檢測算法大致可以分為:基于統(tǒng)計的算法[8]、基于距離的算法[9,10]、基于密度的算法[7,11-16]等.

基于統(tǒng)計的離群點檢測算法,需要事先假設(shè)數(shù)據(jù)服從某種標(biāo)準(zhǔn)分布,如果某個數(shù)據(jù)與這個分布的偏差較大,則將其標(biāo)記為離群點.但是對于不遵循任何標(biāo)準(zhǔn)分布的數(shù)據(jù)集或無法預(yù)知數(shù)據(jù)集的分布類型時,無法使用基于統(tǒng)計的檢測算法對數(shù)據(jù)集進行離群點檢測.

基于距離的離群點檢測算法不需要預(yù)先知道數(shù)據(jù)的分布模型,如果數(shù)據(jù)集中某個對象與數(shù)據(jù)集中超過一定比例的其它對象的距離大于某個閾值,則將這個對象視為離群點.然而基于距離的離群點檢測方法檢測出的是全局離群點,沒有考慮局部離群點.

基于統(tǒng)計的離群點檢測方法與基于距離的離群點檢測方法都具有一定的局限性,對于分布復(fù)雜的數(shù)據(jù)集,無法準(zhǔn)確的檢測出數(shù)據(jù)集中的局部離群點,因此研究者提出了基于密度的局部離群點檢測方法[7,11-16].基于密度的離群點檢測算法在判斷一個對象是否屬于離群點時,除了將該點與其它點之間的距離作為依據(jù)外,還增加其一定范圍鄰域內(nèi)所包含的對象數(shù)量作為判別依據(jù),這兩個依據(jù)共同構(gòu)成該對象的“密度”屬性.

LOF(Local Outlier Factor)算法[7]是一種基于密度的局部離群點檢測算法,這個算法不再將離群看作是一個二元屬性,用局部離群因子這一概念,量化對象的離群程度,LOF算法為數(shù)據(jù)集中的每個對象賦予一個局部離群因子來表示該對象的離群程度,再進一步從離群程度較高的數(shù)據(jù)集合中尋找離群點.對于數(shù)據(jù)集中的任意一個數(shù)據(jù)對象s,首先通過給定的參數(shù)k確定其k-距離與k-鄰域,并計算出數(shù)據(jù)對象s相對于k-鄰域內(nèi)其它數(shù)據(jù)對象的可達距離,進而計算出s的可達密度,最后用s的k-鄰域內(nèi)所有其它數(shù)據(jù)對象的平均可達密度與s的可達密度的比值作為數(shù)據(jù)對象s的局部離群因子.目前已經(jīng)有許多學(xué)者針對不同的數(shù)據(jù)集或應(yīng)用場景對LOF算法進行改進和擴展,在其基礎(chǔ)上提出多種局部離群點檢測算法.其中比較有代表性的算法有:朱利等人[11]提出基于k-近鄰的最小生成樹離群點檢測算法,該算法先在原始數(shù)據(jù)集上構(gòu)建平分樹,計算數(shù)據(jù)點的k-近鄰,最后計算數(shù)據(jù)的局部離群因子,進而檢測出局部離群點.涂曉敏等人[12]將鄰域改為方形鄰域,減少鄰域查詢次數(shù),降低了時間復(fù)雜度,并使用裁剪系數(shù)來代替LOF算法中的可達距離、可達密度的計算.SimplifiedLOF算法[13],該算法用k-距離代替可達距離進行局部離群因子計算,簡化局部離群因子的計算過程,但檢測結(jié)果的準(zhǔn)確性受到一定影響.Su等人[14]提出使用局部偏差系數(shù)LDC來重新定義局部離群因子,這種方法通過計算數(shù)據(jù)對象與其鄰域內(nèi)其它對象之間距離的期望和方差來判斷數(shù)據(jù)對象的離群程度.Schubert等人[16]將LOF算法與核密度估計[15]方法結(jié)合起來,提出KDEOS算法,該算法使用LOF算法中的可達距離來代替核密度估計公式中的傳統(tǒng)距離,之后使用求出的密度估計來表示數(shù)據(jù)對象的密度.核密度估計方法可以求解給定樣本點集合的分布密度函數(shù),屬于非參數(shù)估計方法.這種方法不利用數(shù)據(jù)分布的先驗知識,不需要事先對數(shù)據(jù)分布做出假設(shè).

離群點檢測算法運用在交通數(shù)據(jù)去噪問題時,需要盡可能的檢測出所有的離群點,以消除數(shù)據(jù)集中噪聲點對后續(xù)工作的影響,即需要提高算法的查全率.針對這種情況,提出一種新的基于局部估計密度的局部離群點檢測算法LOLED(Local Outlier Detection Based on Local Estimation Density),該算法利用核密度估計方法計算數(shù)據(jù)集中每個數(shù)據(jù)的局部估計密度,為了反映數(shù)據(jù)集中每個數(shù)據(jù)的局部范圍內(nèi)的稀疏密集程度對其密度計算結(jié)果的影響,對核密度估計方法進行優(yōu)化,使帶寬的值可以根據(jù)局部范圍內(nèi)稀疏密集程度的不同進行調(diào)整;然后用局部估計密度計算局部離群因子,利用每個數(shù)據(jù)的局部離群因子判斷這個數(shù)據(jù)是否是離群點.最后在UCI標(biāo)準(zhǔn)數(shù)據(jù)集與模擬公交軌跡數(shù)據(jù)集上進行實驗,驗證檢測算法的有效性,局部離群點檢測算法的查全率提高.

2 局部離群點檢測算法

LOLED算法是對LOF算法進行改進,先給出LOF算法的一些基本定義,再詳細(xì)介紹LOLED算法.給定一個樣本數(shù)據(jù)集S={s1,…,sn},n為樣本數(shù)量,每個樣本si={a1,…,am}是m維樣本數(shù)據(jù)對象,si∈S.

2.1 LOF算法

LOF算法的核心思想是計算數(shù)據(jù)對象的局部可達密度,并使用其鄰域范圍內(nèi)所有其它對象的局部可達密度的平均值與自身局部可達密度值的比值來表示該數(shù)據(jù)對象的離群程度,這個比值被稱為局部離群因子,反映數(shù)據(jù)對象是否分布在與其密度較為相近的局部區(qū)域內(nèi).LOF算法的一些基本定義如下[7]:

定義1.對象si的k-距離,k-distance(si):對于任意小于n的正整數(shù)k,si∈S,對象si的k-距離,記為k-distance(si),被定義為si與sj之間的距離d(si,sj),其中sj∈S,且sj滿足以下條件:

定義2.對象si的k-鄰域,Nk(si):si∈S,給定si的k-距離,si的k-鄰域包括數(shù)據(jù)集中所有與si的距離不大于k-距離的其它對象,即:

(1)

定義3.對象si相對于對象sj的可達距離,reach-distk(si,sj):給定自然數(shù)k,且si,sj∈S,對象si相對于對象sj的可達距離被定義為:

reach-distk(si,sj)=max{k-distance(sj),d(si,sj)}

(2)

定義4.對象si的局部可達密度,lrd(si):si∈S,對象si的局部可達密度被定義為:

(3)

定義5.對象si的離群因子,LOF(si):si∈S,對象si的局部離群因子被定義為:

(4)

LOF算法在求出數(shù)據(jù)集中每個數(shù)據(jù)對象的局部離群因子后,對這些值進行排序,輸出排序后離群因子較大的z個數(shù)據(jù)對象作為數(shù)據(jù)集S的離群點集合,其中z值是根據(jù)不同數(shù)據(jù)集規(guī)模給定的參數(shù).

2.2 基于局部估計密度的局部離群點檢測算法

LOLED算法首先使用核密度估計方法求出每個數(shù)據(jù)的局部估計密度,并在計算過程中引入了每個數(shù)據(jù)的k-鄰域信息;再利用每個數(shù)據(jù)的局部估計密度與其k-鄰域內(nèi)其它數(shù)據(jù)的局部估計密度,計算出每個數(shù)據(jù)的局部離群因子;最后將每個數(shù)據(jù)的局部離群因子與某個固定的閾值進行比較,進而判斷出該數(shù)據(jù)是否屬于離群點.

2.2.1 局部估計密度的計算

核密度估計方法可以在未知數(shù)據(jù)集分布模型的情況下,利用數(shù)據(jù)自身的信息,估計未知的密度函數(shù),進而計算出每個數(shù)據(jù)的估計密度.首先給出標(biāo)準(zhǔn)核密度估計公式[15]:

(5)

其中‖si-sj‖表示兩個對象之間的距離,‖si-sj‖=d(si,sj).h(sj)是一個平滑函數(shù),也稱為帶寬.帶寬函數(shù)h(sj)的最簡單選取方式為h(sj)=h,即固定帶寬.但對于真實數(shù)據(jù)集來說,不同數(shù)據(jù)間的局部密度可能存在差異,固定帶寬不能很好的適應(yīng)這種情況,需要一種可以適應(yīng)不同數(shù)據(jù)密度的方法,因此在帶寬函數(shù)中引入尺度參數(shù).對于任意兩個數(shù)據(jù)對象si,sj,其距離為d(si,sj),設(shè)尺度參數(shù)為σ,可以通過比較d(si,sj)與σ來判斷兩個對象間的相似性,若d(si,sj)≤σ,則兩個對象間的相似度較高,若d(si,sj)>σ,則兩個對象間的相似度較低.當(dāng)數(shù)據(jù)集中存在多個密度不同的簇時,全局尺度參數(shù)無法很好的衡量兩個對象間的相似情況,因此引入局部尺度參數(shù),即在比較密集的簇內(nèi),尺度參數(shù)的設(shè)置偏小,而對于較為稀疏的簇,尺度參數(shù)的設(shè)置偏大,尺度參數(shù)的大小可以根據(jù)數(shù)據(jù)自身的分布情況進行調(diào)整.引入k-鄰域平均距離來衡量對象所處區(qū)域的稀疏或密集情況:

定義6.對象si的k-鄰域平均距離,Nk-adist(si):對象si的k-鄰域平均距離定義為:

(6)

期望值往往可以反映出特定屬性空間中數(shù)據(jù)的整體分布情況.Nk-adist(si)是數(shù)據(jù)對象si的k-鄰域內(nèi)的所有其它對象到si距離的平均值,可以很好的反映出對象si與其k-鄰域Nk(si)整體的偏離程度,根據(jù)密集區(qū)域的數(shù)據(jù)對象的k-鄰域平均距離較小、稀疏區(qū)域的數(shù)據(jù)對象的k-鄰域平均距離較大的特點,可以設(shè)置局部尺度參數(shù)為:

σi=Nk-adist(si),σj=Nk-adist(sj)

(7)

并進一步設(shè)置帶寬函數(shù)為:

(8)

這種計算方式將樣本點的鄰域信息,即數(shù)據(jù)對象的k-鄰域平均距離引入到帶寬函數(shù)計算中,使得帶寬可以根據(jù)不同樣本點鄰域的稀疏密集情況進行自動調(diào)整.

公式(5)中的K是滿足積分為1,期望為0,帶寬為h(sj)的m維函數(shù),選擇高斯核函數(shù)作為核密度估計的內(nèi)核函數(shù),其公式為:

(9)

由于所要檢測的離群點為局部離群點,只需考慮樣本點周圍一定范圍內(nèi)的數(shù)據(jù)分布情況,因此將公式(5)中的求和范圍限制在樣本的k-鄰域范圍即可,將公式(8)、公式(9)代入到公式(5)中,可以獲得數(shù)據(jù)樣本si的局部估計密度led(si),計算公式為:

(10)

公式(10)可以進一步優(yōu)化為:

(11)

2.2.2 基于局部估計密度的局部離群因子計算

求出給定數(shù)據(jù)點的密度估計后,不能僅使用估計值來判斷該點是否為離群點.交通數(shù)據(jù)分布往往是多密度的,同一數(shù)據(jù)集中可能存在多個簇,屬于不同簇的數(shù)據(jù)可以具有不同的密度.當(dāng)數(shù)據(jù)集中的某個簇較為稀疏時,屬于這個簇的數(shù)據(jù)會具有較低的密度,但這些點不應(yīng)被判定為離群點.參考定義5,利用某個數(shù)據(jù)點si的局部密度估計與其k-鄰域范圍內(nèi)所有其它點sj(i≠j)的局部密度估計的平均值,可以計算出si的局部離群因子LOLED(si),計算公式為:

(12)

理想情況下,LOLED(si)的值越接近于1,表示數(shù)據(jù)對象si與其k-鄰域的平均局部密度越接近,si與其鄰域?qū)儆谕淮氐目赡苄栽酱?如果這個值小于1,說明數(shù)據(jù)對象si的局部密度大于周圍的密度,si為密集點,si為離群點的可能性較小;如果這個值大于1,說明數(shù)據(jù)對象si的局部密度小于周圍的密度,si是離群點的可能性較大.實際情況中,閾值的確定與數(shù)據(jù)規(guī)模和實際待解決的問題有關(guān),通常閾值o取值大于1.

2.2.3 LOLED算法描述

可以通過設(shè)置局部離群因子閾值o,來判斷數(shù)據(jù)集中的數(shù)據(jù)點是否為離群點,如果數(shù)據(jù)對象的局部離群因子大于閾值,則判定為離群點;如果數(shù)據(jù)對象的局部離群因子小于閾值,則判定為正常點.詳細(xì)的LOLED算法描述如下:

輸入:具有n個m維數(shù)據(jù)對象的數(shù)據(jù)集S;鄰域范圍k;局部離群因子閾值o

輸出:數(shù)據(jù)集S的離群點集合O

1. for each s in S

2. 構(gòu)建數(shù)據(jù)對象s的k-鄰域集合Nk(s);

3. 根據(jù)公式(11)計算數(shù)據(jù)對象s的局部估計密度led(s);

4. 根據(jù)公式(12)計算數(shù)據(jù)對象s的局部離群因子LOLED(s);

5. ifLOLED(s)>o

6. 將數(shù)據(jù)對象s添加到離群點集合O中;

7. end if

8. end for

9. 輸出離群點集合O

3 實驗驗證

3.1 UCI數(shù)據(jù)集實驗結(jié)果與分析

UCI數(shù)據(jù)庫是一個常用的標(biāo)準(zhǔn)測試數(shù)據(jù)集,經(jīng)常用來驗證算法的有效性.由于數(shù)據(jù)集中的離群點是未知的,參照文獻[17]中的方法,對UCI數(shù)據(jù)庫中的3個數(shù)據(jù)集進行處理,刪除數(shù)據(jù)集中某一類的大部分?jǐn)?shù)據(jù),只保留小部分?jǐn)?shù)據(jù),保留下來的這些數(shù)據(jù)偏離其它的數(shù)據(jù)點較遠(yuǎn),可以作為待檢測的離群點,其它類的數(shù)據(jù)則當(dāng)作正常點.處理后最終得到6個測試數(shù)據(jù)集如表 1 所示, 其中離群點數(shù)量為刪除類在刪除大部分

表1 UCI數(shù)據(jù)集處理結(jié)果
Table 1 UCI datasets process result

數(shù)據(jù)集編號數(shù)據(jù)集刪除類離群點數(shù)量剩余總數(shù)據(jù)點數(shù)量1IrisIris-setosa51052IrisIris-versicolor51053Glass5651924Glass6751865Ionosphereg151406Ionosphereb15240

數(shù)據(jù)后剩余的數(shù)據(jù)點個數(shù),剩余總數(shù)據(jù)點數(shù)量是離群點數(shù)量與正常點數(shù)量之和.

實驗分別采取LOLED算法、SimplifiedLOF算法、LOF算法與KDEOS算法對6個處理后的數(shù)據(jù)集進行局部離群點檢測.將正確檢測出的離群點的數(shù)量設(shè)為TP,正常點檢測為離群點的數(shù)量設(shè)為FP,離群點檢測為正常點的數(shù)量設(shè)為FN,4種算法的檢測結(jié)果如表2所示.

表2 4種算法在UCI數(shù)據(jù)集上的檢測結(jié)果
Table 2 Detection results of the four algorithms
on UCI datasets

數(shù)據(jù)集編號LOLEDSimplifiedLOFLOFKDEOSTPFPFNTPFPFNTPFPFNTPFPFN159021635704912510038221133723521033248151804417136236341515923651610931662396112647198102459276

選擇查準(zhǔn)率、查全率與F-Measure作為算法的評價指標(biāo).查準(zhǔn)率,也稱精確率(precision),記為P,計算公式為:

(12)

查全率,也稱召回率(recall),記為R,計算公式為:

(13)

查準(zhǔn)率和查全率呈負(fù)相關(guān),一般來說,查準(zhǔn)率高時,查全率通常偏低,而查全率高時,查準(zhǔn)率通常偏低.F-Measure,記為Fβ,是查準(zhǔn)率和查全率的加權(quán)調(diào)和平均,是一個常用的評價標(biāo)準(zhǔn),計算公式為:

(14)

其中β為參數(shù),不同的應(yīng)用中對查全率和查準(zhǔn)率的要求有所不同,可以通過對β設(shè)置不同的值來調(diào)整對查準(zhǔn)率或查全率的偏好,當(dāng)β>1時查全率有更大影響,β<1時查準(zhǔn)率有更大影響.實驗中取β=1,即:

(15)

文獻[18]指出,k值的選取與數(shù)據(jù)規(guī)模無關(guān),實驗過程中,當(dāng)參數(shù)k=9時,四種算法都可以在各個數(shù)據(jù)集上取得較好的效果,包括維數(shù)較高的數(shù)據(jù)集.閾值o的選取與實際的需求有關(guān),閾值o越大,算法檢測出的離群點個數(shù)越少,即TP+FP的值越小,o的取值通常應(yīng)大于等于1.圖1列出在k=9的情況下,閾值o分別取值為1.0、1.3、1.5、1.7時,四種算法在不同數(shù)據(jù)集上的F-Measure值的平均值.

由圖1可知,KDEOS算法、LOF算法與LOLED算法在閾值o=1.3時,具有最高的平均F-Measure值,即算法的表現(xiàn)最好,因此后續(xù)實驗設(shè)置參數(shù)為k=9,o=1.3.表3、表4、表5分別列出四種算法在UCI數(shù)據(jù)集上的查準(zhǔn)率、查全率與F-Measure的比較結(jié)果.表3顯示,LOLED算法的查準(zhǔn)率與其它算法的查準(zhǔn)率在不同數(shù)據(jù)集上比較結(jié)果有所不同.表4中,LOLED算法的查全率在6個數(shù)據(jù)集上都高于或等于其它算法的查全率.表5顯示,LOLED算法與其它算法的F-Measure在不同數(shù)據(jù)集上有不同的比較結(jié)果.

圖1 四種算法不同閾值時的F-Measure比較Fig.1 F-Measure comparison of four algorithms with different thresholds

表3 四種算法在UCI數(shù)據(jù)集上的查準(zhǔn)率結(jié)果
Table 3 Precision of the four algorithms on UCI datasets

數(shù)據(jù)集編號LOLEDSimplifiedLOFLOFKDEOS135.71%11.11%41.67%30.77%233.33%27.27%15.38%30.00%319.23%50.00%33.33%21.74%419.05%33.33%33.33%21.05%528.13%23.81%22.50%20.69%629.73%26.92%29.41%25.00%

3.2 真實數(shù)據(jù)集

為了驗證LOLED算法在真實數(shù)據(jù)集中的有效性,實驗?zāi)M某市公交車軌跡數(shù)據(jù)進行模擬測試.公交車配備的GPS設(shè)備在記錄移動對象的位置信息時,由于GPS設(shè)備的精度問題、GPS系統(tǒng)的自身誤差、司機休息時沒有關(guān)閉GPS設(shè)備等原因,會產(chǎn)生一些離群數(shù)據(jù).這些數(shù)據(jù)所包含的位置信息明顯不同于其它的數(shù)據(jù)對象,被視為噪聲點,這些噪聲點對基于公交軌跡數(shù)據(jù)的城市路網(wǎng)提取、交通流量預(yù)測等后續(xù)工作產(chǎn)生較大影響,在數(shù)據(jù)預(yù)處理階段需要進行去噪,即對原始數(shù)據(jù)集進行離群點檢測并剔除離群點.實驗?zāi)M兩組單向行駛的軌跡數(shù)據(jù)進行實驗,并計算出數(shù)據(jù)集中每個數(shù)據(jù)點與已有路網(wǎng)信息的道路中心線的距離,將與道路中心線距離大于7米的數(shù)據(jù)點看作是離群點.第一組為直線路段的數(shù)據(jù),原始GPS數(shù)據(jù)點數(shù)量為500個,計算后得到第一組數(shù)據(jù)的離群點個數(shù)為68個,數(shù)據(jù)的原始GPS點分布如圖3(a)所示.第二組為交叉路口區(qū)域的數(shù)據(jù),原始GPS數(shù)據(jù)點數(shù)量為1100個,計算后得到第二組數(shù)據(jù)的離群點個數(shù)為136個, 數(shù)據(jù)的原始GPS點分布如圖3(b)所示. 軌跡數(shù)據(jù)的數(shù)據(jù)量較大,正常點的分布極為密集,在進行離群點檢測時,注重去除離群點,以削弱離群點對后續(xù)工作產(chǎn)生的影響,需要較高的查全率.

表4 四種算法在UCI數(shù)據(jù)集上的查全率結(jié)果
Table 4 Recall of the four algorithms on UCI datasets

數(shù)據(jù)集編號LOLEDSimplifiedLOFLOFKDEOS1100.00%40.00%100.00%80.00%2100.00%60.00%40.00%60.00%3100.00%60.00%80.00%100.00%480.00%60.00%50.00%80.00%560.00%33.33%60.00%40.00%673.33%46.67%66.67%60.00%

表5 四種算法在UCI數(shù)據(jù)集上的F-Measure結(jié)果
Table 5 F-Measure of the four algorithms on UCI datasets

數(shù)據(jù)集編號LOLEDSimplifiedLOFLOFKDEOS152.63%17.39%58.82%44.44%250.00%37.50%22.22%40.00%332.26%54.55%47.06%35.71%430.77%42.86%40.00%33.33%538.30%27.78%32.73%27.27%642.31%34.15%40.82%35.29%

圖2 四種離群點檢測算法的表現(xiàn)對比圖Fig.2 Performance comparison of the four algorithms

圖3 某市公交車模擬軌跡數(shù)據(jù)點Fig.3 Synthetic bus trajectory data of a city

實驗分別選取LOLED算法、SimplifiedLOF算法、LOF算法、KDEOS算法對兩組數(shù)據(jù)進行處理,設(shè)置參數(shù)k=9,同時考慮實際業(yè)務(wù)需求,為了避免檢測出過多的離群點,導(dǎo)致GPS數(shù)據(jù)集剔除掉檢測出的離群點后,剩余的點無法看出軌跡形狀或軌跡出現(xiàn)缺口等現(xiàn)象,將閾值o設(shè)為較大的值,設(shè)o=1.5,四種算法在兩組數(shù)據(jù)集上的檢測結(jié)果如表6所示,表7、表8、表9分別列出四種算法在模擬數(shù)據(jù)集上的查準(zhǔn)率、 查全率與F-Measure的比較結(jié)果.兩組GPS數(shù)據(jù)檢測結(jié)果可視化后分別如圖4、圖5所示,其中較小的點表示檢測出的噪聲點,較大的點表示檢測出的正常點.圖4(b)(c)(d)與圖5(b)(c)(d)中方框內(nèi)較大點的數(shù)量明顯多于圖4(a)與圖5(a)中相應(yīng)位置上較大點的數(shù)量,這些點雖然被檢測為正常點,但從圖中可以看出,方框內(nèi)的較大點應(yīng)屬于噪聲點.

表6 四種算法在模擬數(shù)據(jù)集上的檢測結(jié)果
Table 6 Detection results of the four algorithms
on synthetic datasets

數(shù)據(jù)集LOLEDSimplifiedLOFLOFKDEOSTPFPFNTPFPFNTPFPFNTPFPFN直線路段598893247364360254910419交叉路口119196177212764961524010421232

表7 四種算法在模擬數(shù)據(jù)集上的查準(zhǔn)率結(jié)果
Table 7 Precision of the four algorithms on synthetic datasets

數(shù)據(jù)集LOLEDSimplifiedLOFLOFKDEOS直線路段40.41%40.51%41.75%32.03%交叉路口36.84%36.18%38.71%32.91%

表8 四種算法在模擬數(shù)據(jù)集上的查全率結(jié)果
Table 8 Recall of the four algorithms on synthetic datasets

數(shù)據(jù)集LOLEDSimplifiedLOFLOFKDEOS直線路段86.76%47.06%63.24%72.06%交叉路口87.50%52.94%70.59%76.47%

表9 四種算法在模擬數(shù)據(jù)集上的F-Measure比較結(jié)果
Table 9 F-Measure of the four algorithms on synthetic datasets

數(shù)據(jù)集LOLEDSimplifiedLOFLOFKDEOS直線路段55.14%43.54%50.29%44.34%交叉路口51.85%42.99%50.00%46.02%

圖4 四種算法在第一組數(shù)據(jù)集的實驗結(jié)果Fig.4 Experimental results of the four algorithms on the first data set

綜合表7、表8、表9的內(nèi)容可以看出,LOLED算法的查全率較高,雖然算法的查準(zhǔn)率較低,但原始的GPS數(shù)據(jù)經(jīng)過離群點檢測,并剔除離群點后,圖3(a)、圖4(a)中剩余的點依然可以看出道路骨架的形狀,偏離其它大部分?jǐn)?shù)據(jù)、游離在道路外的點已經(jīng)被識別并剔除.其它算法存在的漏判較多,處理后的數(shù)據(jù)中漏判的離群點對后續(xù)工作的影響仍然較大,LOLED算法的漏判情況則較少,基本消除后續(xù)工作中離群點的影響.LOLED算法具有較高的查全率,在模擬數(shù)據(jù)集中,也可以取得較好的效果.

圖5 四種算法在第二組數(shù)據(jù)集的實驗結(jié)果Fig.5 Experimental results of the four algorithms on the second data set

4 結(jié) 論

LOLED算法將核密度估計方法引入到局部離群點檢測算法中,用核密度估計方法計算出的密度估計,來代替?zhèn)鹘y(tǒng)LOF算法中的局部可達密度,并使用局部尺度參數(shù)來代替?zhèn)鹘y(tǒng)高斯核函數(shù)的固定帶寬,可以更好的適應(yīng)密度不均勻、形狀不規(guī)則的數(shù)據(jù)集.在實驗方面,利用UCI標(biāo)準(zhǔn)數(shù)據(jù)集與模擬數(shù)據(jù)集,驗證算法的有效性,其中查全率有明顯改善.在實際應(yīng)用中也可以取得較好的效果.下一步將重點研究算法的最優(yōu)參數(shù)選擇方法以及進一步提高算法的查準(zhǔn)率.