基于局部估計(jì)密度的局部離群點(diǎn)檢測算法

謝 兄,唐 昱

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

1 引 言

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

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

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

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

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

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

2 局部離群點(diǎn)檢測算法

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

2.1 LOF算法

LOF算法的核心思想是計(jì)算數(shù)據(jù)對象的局部可達(dá)密度,并使用其鄰域范圍內(nèi)所有其它對象的局部可達(dá)密度的平均值與自身局部可達(dá)密度值的比值來表示該數(shù)據(jù)對象的離群程度,這個(gè)比值被稱為局部離群因子,反映數(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的可達(dá)距離,reach-distk(si,sj):給定自然數(shù)k,且si,sj∈S,對象si相對于對象sj的可達(dá)距離被定義為:

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

(2)

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

(3)

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

(4)

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

2.2 基于局部估計(jì)密度的局部離群點(diǎn)檢測算法

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

2.2.1 局部估計(jì)密度的計(jì)算

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

(5)

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

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

(7)

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

(8)

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

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

(9)

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

(10)

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

(11)

2.2.2 基于局部估計(jì)密度的局部離群因子計(jì)算

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

(12)

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

2.2.3 LOLED算法描述

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

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

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

1. for each s in S

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

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

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

5. ifLOLED(s)>o

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

7. end if

8. end for

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

3 實(shí)驗(yàn)驗(yàn)證

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

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

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

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

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

實(shí)驗(yàn)分別采取LOLED算法、SimplifiedLOF算法、LOF算法與KDEOS算法對6個(gè)處理后的數(shù)據(jù)集進(jìn)行局部離群點(diǎn)檢測.將正確檢測出的離群點(diǎn)的數(shù)量設(shè)為TP,正常點(diǎn)檢測為離群點(diǎn)的數(shù)量設(shè)為FP,離群點(diǎn)檢測為正常點(diǎn)的數(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作為算法的評價(jià)指標(biāo).查準(zhǔn)率,也稱精確率(precision),記為P,計(jì)算公式為:

(12)

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

(13)

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

(14)

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

(15)

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

由圖1可知,KDEOS算法、LOF算法與LOLED算法在閾值o=1.3時(shí),具有最高的平均F-Measure值,即算法的表現(xiàn)最好,因此后續(xù)實(shí)驗(yàn)設(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個(gè)數(shù)據(jù)集上都高于或等于其它算法的查全率.表5顯示,LOLED算法與其它算法的F-Measure在不同數(shù)據(jù)集上有不同的比較結(jié)果.

圖1 四種算法不同閾值時(shí)的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í)數(shù)據(jù)集

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

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

實(shí)驗(yàn)分別選取LOLED算法、SimplifiedLOF算法、LOF算法、KDEOS算法對兩組數(shù)據(jù)進(jìn)行處理,設(shè)置參數(shù)k=9,同時(shí)考慮實(shí)際業(yè)務(wù)需求,為了避免檢測出過多的離群點(diǎn),導(dǎo)致GPS數(shù)據(jù)集剔除掉檢測出的離群點(diǎn)后,剩余的點(diǎn)無法看出軌跡形狀或軌跡出現(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所示,其中較小的點(diǎn)表示檢測出的噪聲點(diǎn),較大的點(diǎn)表示檢測出的正常點(diǎn).圖4(b)(c)(d)與圖5(b)(c)(d)中方框內(nèi)較大點(diǎn)的數(shù)量明顯多于圖4(a)與圖5(a)中相應(yīng)位置上較大點(diǎn)的數(shù)量,這些點(diǎn)雖然被檢測為正常點(diǎn),但從圖中可以看出,方框內(nèi)的較大點(diǎn)應(yīng)屬于噪聲點(diǎn).

表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ù)集的實(shí)驗(yàn)結(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)過離群點(diǎn)檢測,并剔除離群點(diǎn)后,圖3(a)、圖4(a)中剩余的點(diǎn)依然可以看出道路骨架的形狀,偏離其它大部分?jǐn)?shù)據(jù)、游離在道路外的點(diǎn)已經(jīng)被識別并剔除.其它算法存在的漏判較多,處理后的數(shù)據(jù)中漏判的離群點(diǎn)對后續(xù)工作的影響仍然較大,LOLED算法的漏判情況則較少,基本消除后續(xù)工作中離群點(diǎn)的影響.LOLED算法具有較高的查全率,在模擬數(shù)據(jù)集中,也可以取得較好的效果.

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

4 結(jié) 論

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