一種基于密度的離群點檢測方法

王向陽

(陜西學(xué)前師范學(xué)院　陜西西安　710160)

離群點可理解為遠離其他數(shù)據(jù)點或不服從基于多數(shù)樣本數(shù)據(jù)建立的統(tǒng)計模型的數(shù)據(jù)[1]。盡管離群點在樣本數(shù)據(jù)集中所占比例通常很小，但在某些領(lǐng)域內(nèi)離群點檢測工作卻發(fā)揮著重要作用。例如在網(wǎng)絡(luò)安全領(lǐng)域，異常的網(wǎng)絡(luò)行為數(shù)據(jù)可能意味著網(wǎng)絡(luò)入侵事件的發(fā)生。在電力行業(yè)，異常的用電行為數(shù)據(jù)可能意味著竊電現(xiàn)象或電力故障的發(fā)生。

目前基于密度的離群點檢測方法比較流行，該方法的基本思想是從樣本點所在空間的密度差異性來發(fā)現(xiàn)離群點。離群點從分布情況可分為全局和局部兩類離群點。局部離群點相對全局離群點而言，更容易被聚類到某個類簇中，因此識別難度較大。針對局部離群點，研究者們基于離群點局部密度會低于其鄰居點局部密度的假設(shè)，采用了諸如局部離群因子(local outlier factor, LOF)等評估策略來發(fā)現(xiàn)局部離群點[2-4]。例如Alex等在其提出的方法中假定離群點必須滿足局部密度小、與高局部密度數(shù)據(jù)點的距離很遠[5]。針對大規(guī)模的數(shù)據(jù)集而言，離群點檢測的工作量大，時間效率低。對此，茍杰等先將數(shù)據(jù)集分割為互有重疊的子集，在子集中尋找K近鄰并計算離群度，最后合并結(jié)果并遴選出離群點[6]。姜開元等通過R2-TREE的結(jié)構(gòu)來提高數(shù)據(jù)檢索效率，并借鑒LOF方法通過計算數(shù)據(jù)對象落在不同區(qū)域的概率來發(fā)現(xiàn)離群點[7]。針對高密度、多義性數(shù)據(jù)集，錢景輝將數(shù)據(jù)拆分成多示例包形式，運用退化策略及權(quán)重調(diào)整，計算離群點因子來判別離群點[8]。離群點的密度會受鄰域劃分程度及樣本數(shù)據(jù)集稀疏性的影響，對此，王茜等鑒于近鄰中不同的鄰近程度發(fā)揮的作用不同，采用了基于鏈接的離群因子來解決離群點的密度與鄰近點密度接近的情況[9]。Liu等[10]利用核K均值方法和核離群因子來計算每個樣本數(shù)據(jù)認(rèn)定為正例或負(fù)例樣本的可能性，并基于支持向量數(shù)據(jù)描述來構(gòu)建分類模型。Miao等[11]采用核局部離群因子來解決鄰居點分布不均勻的情況。

由上述研究工作可見，檢測局部離群點時需明確樣本點的鄰域，并考慮鄰域內(nèi)近鄰點的分布情況及近鄰點對目標(biāo)樣本點的影響。由于離群點并不一定是孤立的點，可能會與其同類的若干樣本點緊密地聚集在其他類別樣本的邊緣地帶，在該情況下將很難根據(jù)樣本點與其鄰近點的局部密度差異來發(fā)現(xiàn)離群點。在基于密度的聚類方法中，類簇間的邊界地帶是樣本容易發(fā)生錯誤聚類的區(qū)域，顯然從邊界樣本點出發(fā)尋找局部離群點會在一定程度上降低工作量。本文提出的方法首先利用有噪聲的基于密度的聚類算法(Density-Based Spatial Clustering of Applications with Noise, DBSCAN)[12]分離出明顯不能劃歸到大類簇中的全局性離群點，然后根據(jù)小類簇中樣本點的近鄰關(guān)系(不考慮樣本點所屬類簇)和對小類簇局部密度的影響程度，來確定大類簇中應(yīng)該劃回小類簇的邊界“錯聚”樣本點，最后以“錯聚”樣本點為參考對象篩選掉與其相距很遠且局部密度高的鄰居點，從而發(fā)現(xiàn)大類簇中“錯聚”樣本點鄰域內(nèi)的其他局部離群點。

1　基于密度的離群點檢測

本文提出的方法主要由全局離群點提取、邊界“錯聚”樣本點確定及局部離群點識別三部分組成。

1.1　全局離群點提取

DBSCAN算法可以將局部密度大且相連的區(qū)域內(nèi)的樣本點聚集到一起形成類簇，其對噪音點和異常點具有很強的免疫能力。其核心思想是找到滿足半徑Eps內(nèi)鄰居樣本數(shù)不少于minPts的核心點，并以每個核心點代表一個區(qū)域，將相距不超過Eps的核心點所代表的區(qū)域進行合并。其缺點是由于密度連通關(guān)系的傳遞性會使大多數(shù)樣本點聚集到非常少的類簇中[11]。本文提出的方法將DBSCAN算法聚類出的小類簇和噪音點作為全局離群點。

1.2　邊界“錯聚”樣本點確定

在不考慮樣本點歸屬的情況，本文提出的方法先依據(jù)歐式距離確定每個小類簇中樣本點在一定半徑內(nèi)的k個近鄰，然后標(biāo)記k個近鄰中位于大類簇中的樣本點，從而確定邊界區(qū)域“錯聚點”候選集合。若候選樣本點屬于“錯聚點”，則將其劃歸回相應(yīng)的類簇后，類簇的局部密度應(yīng)該變得緊密，至少不會變得稀疏。LOF是比較流行的度量樣本點與其鄰居點局部密度差異的方法。樣本點q的LOF評估公式如下[2]：

(1)

(2)

reach-distk(q,p)=max{d(q,p),k(p)}

(3)

式中，Nk(q)為樣本點q的k個近鄰，Lrdk(q)為樣本點q的局部可達密度，reach-distk(q,p)為樣本點q相對其近鄰點p的可達距離，d(q,p)為樣本點q和p間的距離，k(p)為樣本點p到距離其最近的第k個近鄰點的距離。若樣本點不是離群點，則其LOF值應(yīng)在0至1之間?；贚OF的度量方法，本文度量候選樣本點q對類簇Ci的貢獻程度公式為：

(1-LOFk(pj))×α

(4)

1.3　局部離群點識別

(5)

(6)

式中，distc為檢索半徑。樣本點xi到高密度樣本點的距離計算公式為[3]：

(7)

(8)

(9)

2　實驗

實驗采用UCI提供的shuttle數(shù)據(jù)集[13]來驗證離群點檢測方法的檢測效果。shuttle數(shù)據(jù)集由7個類別樣本組成，包含了43 500個訓(xùn)練樣本和14 500個測試樣本，其中每個樣本由7個數(shù)值型屬性組成。實驗去掉shuttle數(shù)據(jù)集中第4類樣本，選取第1類作為正例樣本，其余類別作為負(fù)例樣本(離群點)。處理后正例樣本數(shù)為45 586，離群點數(shù)為3 511。實驗首先采用z-score公式對樣本數(shù)據(jù)進行標(biāo)準(zhǔn)化處理[14]：

(10)

式中，μ為屬性值的均值，σ為屬性值的標(biāo)準(zhǔn)差。為檢測全局離群點，DBSCAN方法的半徑Eps取值為0.1，最小樣本數(shù)minPts取值為100，聚類結(jié)果如表1所示。

表1　DBSCAN聚類結(jié)果Table 1 DBSCAN clustering results

針對類簇2和類簇3，實驗采用公式(4)確定各自在類簇1中的邊界“錯聚”樣本點，其中公式(4)的調(diào)整因子α取值為10。確定邊界“錯聚”樣本點后，實驗將每個“錯聚”樣本的鄰域半徑設(shè)定為0.5，并采用公式(8)來確定類簇1中的局部離群點，公式(8)中調(diào)整因子β取值為10。公式(4)中樣本點近鄰數(shù)k的取值和依據(jù)公式(8)計算樣本點偏離度的閾值TH都會對局部離群點檢測造成影響。圖1和圖2為近鄰數(shù)k和偏離度閾值TH調(diào)整時，類簇1中局部離群點檢測方法的查全率和查準(zhǔn)率。圖1中參數(shù)TH調(diào)整時局部離群點的查全率變化不大，但對應(yīng)的查準(zhǔn)率變化卻非常大，可見k取值為15和偏離度閾值TH取值為5時方法的局部離群點檢測效果較好。

圖1　參數(shù)調(diào)整時大類簇中局部離群點的查全率Fig.1　The recall rate of local outliers in thelarge group clusters when the parameters are adjusted

圖2　參數(shù)調(diào)整時大類簇中局部離群點的查準(zhǔn)率Fig.2　The precision rate of local outliers in thelarge group clusters when the parameters are adjusted

如何確定樣本點的局部鄰域及如何度量樣本點的離群程度是每個離群點檢測模型都要解決的問題，因此當(dāng)大量的參數(shù)需要進行調(diào)整時檢測模型的性能將受到極大的影響。Alex等[5]提出的離群點檢測方法(簡記為快速法)僅需考慮樣本點的局部密度及到高密度點的距離，因此執(zhí)行速度非?？?。實驗觀察了該方法在shuttle數(shù)據(jù)集上的檢測效果。實驗過程如下：(1)利用公式(5)計算每個樣本點的局部密度，公式(5)中的檢索半徑設(shè)定為0.5；(2)按密度值降序排列得到高密度的100個樣本點和低密度的5 000個樣本點；(3)利用公式(7)計算每個低密度的樣本點到高密度樣本點的距離，按距離值降序排列后輸出前3 500個樣本點。實驗發(fā)現(xiàn)當(dāng)快速法保持低密度樣本點總數(shù)不變，高密度點總數(shù)取200，500及1 000時離群點的檢測結(jié)果無變化，可見快速法適合檢測全局離群點。兩種離群點檢測方法的檢測結(jié)果對比如表2所示。從表2可以看出，雖然本文提出的方法比較復(fù)雜，但能在保障查準(zhǔn)率的前提下檢測出更多的離群點。

表2　離群點檢測結(jié)果比較Table 2 Comparison of outlier detection results

3　結(jié)束語

本文提出了一種基于密度的離群點檢測方法，該方法首先從全局角度分割樣本特征空間中密度不一致且不連通的樣本區(qū)域，以便識別出全局離群點，然后從局部角度識別出邊界區(qū)域內(nèi)被錯誤聚類的離群點，進而發(fā)現(xiàn)更大范圍內(nèi)的局部離群點。實驗結(jié)果證明了提出的方法的可行性和有效性。但本文方法并未考慮高維特征時模型的優(yōu)化問題，同時也未考慮樣本點聚類后離群點遠離類簇間邊界的情況，需要進一步研究。

[1]范小剛.基于k近鄰樹的離群檢測算法研究[D].重慶:重慶大學(xué),2014.

[2]王敬華,趙新想,張國燕,等.NLOF:一種新的基于密度的局部離群點檢測算法[J].計算機科學(xué),2013,40(8):181-185.

[3]LIU J, DENG H F. Outlier detection on uncertain data based on local information[J]. Knowledge-Based Systems, 2013, 51(1):60-71.

[4]鄒云峰，張昕，宋世淵,等. 基于局部密度的快速離群點檢測算法[J].計算機應(yīng)用，2017,37(10)：2932- 2937.

[5]ALEX R, ALESSANDRO L. Clustering by fast search and find of density peaks[J]. Science, 2014, 344(6191):1492-1496.

[6]茍杰，馬自堂，張喆程. PODKNN:面向大數(shù)據(jù)集的并行離群點檢測算法[J]. 計算機科學(xué),2016,43(7)：251-254,274.

[7]姜元凱,鄭洪源,丁秋林.一種基于密度的不確定數(shù)據(jù)離群點檢測算法[J].計算機科學(xué),2015,42(4):172-176.

[8]錢景輝,梁棟.一種基于多標(biāo)記的局部離群點檢測算法[J]. 微電子學(xué)與計算機,2017, 34(10):110-114.

[9]王茜,劉書志.基于密度的局部離群數(shù)據(jù)挖掘方法的改進[J].計算機應(yīng)用研究,2014, 31(6):1693-1696.

[10] LIU B, XIAO Y, YU P S, et al. An efficient approach for outlier detection with imperfect data labels[J]. IEEE Transactions on Knowledge & Data Engineer,2014, 26(7):1602-1616.

[11] MIAO D, QIN X, WANG W. Anomalous cell detection with kernel density-based local outlier factor[J]. Communications China, 2015, 12(9):64-75.

[12] KALIFA M B, REDONDO R P D, VILAS A F, et al. Is there a crowd? experiences in using density-based clustering and outlier detection[C]. Proceedings of the 2nd International Conference on Mining Intelligence and Knowledge Exploration,2014,8891:155-163.

[13] UCI shuttle data[DB/OL]. http://archive.ics.uci.edu/ml/datasets/Statlog+(Shuttle).

[14] 薛安榮,劉彬,聞丹丹.基于小波變換的分布式隱私保護聚類算法[J].計算機應(yīng)用,2014,34(4):1029-1033.