王向陽(yáng)

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

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

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

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

1　基于密度的離群點(diǎn)檢測(cè)

本文提出的方法主要由全局離群點(diǎn)提取、邊界“錯(cuò)聚”樣本點(diǎn)確定及局部離群點(diǎn)識(shí)別三部分組成。

1.1　全局離群點(diǎn)提取

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

1.2　邊界“錯(cuò)聚”樣本點(diǎn)確定

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

(1)

(2)

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

(3)

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

(1-LOFk(pj))×α

(4)

1.3　局部離群點(diǎn)識(shí)別

(5)

(6)

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

(7)

(8)

(9)

2　實(shí)驗(yàn)

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

(10)

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

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

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

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

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

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

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

3　結(jié)束語(yǔ)

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

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

[2]王敬華,趙新想,張國(guó)燕,等.NLOF:一種新的基于密度的局部離群點(diǎn)檢測(cè)算法[J].計(jì)算機(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]鄒云峰，張昕，宋世淵,等. 基于局部密度的快速離群點(diǎn)檢測(cè)算法[J].計(jì)算機(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ù)集的并行離群點(diǎn)檢測(cè)算法[J]. 計(jì)算機(jī)科學(xué),2016,43(7)：251-254,274.

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

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

[9]王茜,劉書志.基于密度的局部離群數(shù)據(jù)挖掘方法的改進(jìn)[J].計(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] 薛安榮,劉彬,聞丹丹.基于小波變換的分布式隱私保護(hù)聚類算法[J].計(jì)算機(jī)應(yīng)用,2014,34(4):1029-1033.