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

王向陽

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

離群點可理解為遠離其他數據點或不服從基于多數樣本數據建立的統計模型的數據[1]。盡管離群點在樣本數據集中所占比例通常很小，但在某些領域內離群點檢測工作卻發揮著重要作用。例如在網絡安全領域，異常的網絡行為數據可能意味著網絡入侵事件的發生。在電力行業，異常的用電行為數據可能意味著竊電現象或電力故障的發生。

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

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

1　基于密度的離群點檢測

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

1.1　全局離群點提取

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

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

在不考慮樣本點歸屬的情況，本文提出的方法先依據歐式距離確定每個小類簇中樣本點在一定半徑內的k個近鄰，然后標記k個近鄰中位于大類簇中的樣本點，從而確定邊界區域“錯聚點”候選集合。若候選樣本點屬于“錯聚點”，則將其劃歸回相應的類簇后，類簇的局部密度應該變得緊密，至少不會變得稀疏。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值應在0至1之間。基于LOF的度量方法，本文度量候選樣本點q對類簇Ci的貢獻程度公式為：

(1-LOFk(pj))×α

(4)

1.3　局部離群點識別

(5)

(6)

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

(7)

(8)

(9)

2　實驗

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

(10)

式中，μ為屬性值的均值，σ為屬性值的標準差。為檢測全局離群點，DBSCAN方法的半徑Eps取值為0.1，最小樣本數minPts取值為100，聚類結果如表1所示。

表1　DBSCAN聚類結果Table 1 DBSCAN clustering results

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

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

圖2　參數調整時大類簇中局部離群點的查準率Fig.2　The precision rate of local outliers in thelarge group clusters when the parameters are adjusted

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

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

3　結束語

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

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

[2]王敬華,趙新想,張國燕,等.NLOF:一種新的基于密度的局部離群點檢測算法[J].計算機科學,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].計算機應用，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:面向大數據集的并行離群點檢測算法[J]. 計算機科學,2016,43(7)：251-254,274.

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

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

[9]王茜,劉書志.基于密度的局部離群數據挖掘方法的改進[J].計算機應用研究,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].計算機應用,2014,34(4):1029-1033.