基于核密度估計的離群數(shù)據(jù)挖掘

馬 洋，趙旭俊，蘇建花，席婷婷

(太原科技大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，太原 030024)

離群是數(shù)據(jù)集中存在的、少量的、與大多數(shù)對象模式不一致的對象(觀察、事例或點)。識別數(shù)據(jù)中的離群非常重要，因為它們會扭曲常規(guī)的分析和決策，也可能是突發(fā)事情、異常活動等。異常檢測在實際情況下尤其有用，一方面數(shù)據(jù)集眾多，另一方面，它包含或承載了最重要信息的意外事件。但是，在異常檢測的通用技術(shù)方面存在著一些挑戰(zhàn)：離群數(shù)據(jù)挖掘的應(yīng)用領(lǐng)域(例如，網(wǎng)絡(luò)入侵檢測、監(jiān)測、欺詐、機器故障等)不斷增加，這為相應(yīng)的離群數(shù)據(jù)挖掘方法提出了新要求，同時也增加了難度。另外，現(xiàn)實世界中可用于構(gòu)建模型的數(shù)據(jù)通常是未標記的，因此，通過特定的分布或幾何形狀來確定該區(qū)域的先驗形狀，通常是一項困難的任務(wù)，這可能會產(chǎn)生偏差，導(dǎo)致生成的模型失去意義。

為了較好適應(yīng)不同的數(shù)據(jù)集和應(yīng)用領(lǐng)域，在分析密度估計和異常檢測的基礎(chǔ)上，本文給出了樣本點及其鄰域的核函數(shù)，并提出了一種基于核密度估計的離群數(shù)據(jù)挖掘算法OMDE.通過對象之間的距離得到每個樣本點的鄰域；然后計算數(shù)據(jù)集中每個樣本點的密度值，并對其鄰域密度進行估計；通過對各樣本點的離群因子比較，最終獲得偏離大多數(shù)對象的離群數(shù)據(jù)。最后，采用UCI數(shù)據(jù)集對本文提出的OMDE算法同已有的傳統(tǒng)算法進行比較，實驗結(jié)果顯示OMDE算法在效率和準確性兩個方面上，體現(xiàn)出較強的優(yōu)勢。

1 相關(guān)研究

離群數(shù)據(jù)挖掘在各種領(lǐng)域中有著廣泛的應(yīng)用。例如，它被廣泛用于網(wǎng)絡(luò)入侵和惡意事件的檢測；也被用于識別醫(yī)療事故或信用欺詐。研究者們提出了形形色色的離群檢測算法，大體可分為以下幾類：

1.1 基于聚類的方法

基于聚類的離群數(shù)據(jù)檢測，主要依賴于聚類、分類數(shù)據(jù)集，然后將稀疏區(qū)域的觀測值識別為離群數(shù)據(jù)。該類方法可分為兩種：其一是基于排名的離群點分析和檢測ROAD[1]；其二是基于Rough-ROAD[2]的方法。ROAD方法定義了兩種類型的離群值：基于頻率的離群值和基于聚類的離群值?；陬l率的離群值是那些具有不頻繁類別(小平均邊際頻率)的觀測值。相反地，基于聚類的異常值是那些具有頻繁類別的罕見組合的觀測值?；赗ough-ROAD的方法擴展了ROAD方法，它是在粗糙集理論的基礎(chǔ)上，將k-modes算法改進為粗糙k-modes算法，以捕捉不確定性，并處理關(guān)于某些聚類的異常值隸屬度的模糊性。

1.2 基于密度的方法

基于密度的離群，又稱為局部離群[3]，旨在識別局部區(qū)域中具有離群行為的觀測，多數(shù)觀測通常具有相似的特征[4]。這類離群不同于全局離群，全局離群與大多數(shù)其他觀測結(jié)果的模式不一致，而不僅僅表現(xiàn)在局部區(qū)域內(nèi)[5]。分類數(shù)據(jù)的局部離群挖掘方法包括超邊緣異常檢驗(HOT)[6]，k-局部異常因子k-LOF，監(jiān)視方法[7]。HOT方法基于定義兩組變量：公共變量C和外圍變量A，它發(fā)展了一個超圖來捕捉類別觀測之間的相似性。k-LOF是分類和定量數(shù)據(jù)的局部異常檢測方法，將局部異常因子(LOF)擴展到范疇域。如果k-LOF與鄰居的關(guān)系弱于鄰居與鄰居之間的關(guān)系，則k-LOF將觀測值視為局部異常值。WATCH方法包括兩個階段：特征分組和異常點檢測。在特征分組階段，通過將相關(guān)變量聚集到同一組中，將q個分類變量集合劃分成不相交的特征組。

1.3 基于貝葉斯/條件頻率的方法

這類方法對分類中的離群數(shù)據(jù)定義比較模糊，它搜索具有高邊際頻率和小聯(lián)合頻率的觀測值。換言之，該類方法將異常視為類別組合不頻繁的觀測，而其類別是頻繁的。條件異常與其它異常檢測方法所識別的異常有很大區(qū)別，該類方法包括條件算法CA，異常模式檢測APD，屬性關(guān)聯(lián)算法。條件算法CA將異常值定義為具有頻繁類別的罕見組合的觀測值；異常模式檢測方法APD是將異常值百分比高于預(yù)期的相關(guān)觀測組視為離群數(shù)據(jù)[8]；屬性關(guān)聯(lián)算法是將條件異常定義為包含頻繁類別的觀測，但這些項目集很少一起觀測。該方法首先從數(shù)據(jù)中提取一組高度可信的關(guān)聯(lián)規(guī)則，然后計算一個叫做離群度的離群分數(shù)。

1.4 其他方法

除了上述的幾類方法之外，研究者還提出基于指標變量的方法、基于頻率的方法以及信息論方法[9]。

基于指標變量的方法[10]是用數(shù)值表示分類數(shù)據(jù)，然后對定量數(shù)據(jù)進行異常檢測。采用這種方法的例子有指標變量法和基于多重對應(yīng)分析方法。基于頻率的方法使用頻率(即類別的出現(xiàn)次數(shù))而不是距離來識別離群。有三種頻率可用于識別分類數(shù)據(jù)中的異常：邊際頻率、項目集頻率、以及分散頻率。信息論方法[11]背后的思想依賴于異常存在與數(shù)據(jù)中噪聲量之間的直接關(guān)系。因此，異常檢測問題[12]可以轉(zhuǎn)化為一個優(yōu)化問題，其目標是找出使內(nèi)部觀測的信息增益最大或不確定性最小化的異常集合。這些方法大多使用熵作為信息增益或不確定性度量，可分為香農(nóng)熵和全息熵。

2 核密度估計

基于密度估計的離群檢測方法通過比較每個樣本的密度與其鄰域密度來檢測異常，鄰域密度通常是其鄰域的局部密度的平均值。該類方法中，如何合理有效地估計密度，成為一個需重要關(guān)注的問題[13]。為解決這一問題，提出了一種新的局部密度估計核函數(shù)和加權(quán)鄰域密度來計算每個樣本的異常因子，并用于異常檢測?；诩訖?quán)鄰域密度的異常檢測方法對鄰域大小參數(shù)具有較強的魯棒性。

2.1 鄰域的定義

假設(shè)D是一個數(shù)據(jù)集，|D|是數(shù)據(jù)集D中的數(shù)據(jù)對象個數(shù)，其中x=[x1,x2…xd]是一個d維的數(shù)據(jù)對象，對于任一正整數(shù)k(k≤|D|)，x的k距離disk(x)=dis(x,o)，是節(jié)點x到數(shù)據(jù)集中節(jié)點o的距離，并且滿足如下的兩個條件：

1)在數(shù)據(jù)集D中存在至少k個樣本點q，使得dis(x,q)≤dis(x,o);

2)在數(shù)據(jù)集D中最多存在k-1個樣本點Q，使得dis(x,q)

基于上述的假設(shè)，x的k-距離鄰域是由一些特殊的樣本點構(gòu)成，這些樣本點到節(jié)點x的距離不大于x的k距離，采用Domaink(x)來表示，可形式化描述為：

Domaink(x)={q∈D|dis(x,q)≤disk(x)}

(1)

k-距離鄰域中的任一樣本節(jié)點都是x的k-距離鄰居。圖1表示了k為3的前提下，節(jié)點p1和p2的3-距離鄰域，p1的3-距離鄰域為以p1為圓心，以p1的3-距離dis3(p1)為半徑的圓。同樣地，p2的3-距離鄰域為以p2為圓心，以p2的3-距離dis3(p2)為半徑的圓。顯然地，p2的3-距離鄰域要小于p1的鄰域，即p2的3距離小于p1的3距離。換言之，在單位區(qū)域內(nèi)p2的樣本點數(shù)量(即p2的局部密度)要大于p1的數(shù)量，所以，空間樣本中k距離鄰域的大小與樣本的局部密度成反比。即在以p1為圓心，以p2的3-距離dis3(p2)為半徑畫的圓中，點的個數(shù)一定小于3。因此，在k值不變得情況下，樣本點的局部密度越小，這些樣本點的k距離越大，該樣本點成為離群的可能性將越大。

圖1 3-距離鄰域Fig.1 3-distance neighbor

2.2 核密度估計

樣本點的密度大小同離群點特征密切相關(guān)，為有效監(jiān)測離群，需對各樣本點的密度進行計算。核密度估計是研究未知總體中隨機變量分布特性的重要工具，可用作樣本點鄰域度量的手段。尤其在可視化數(shù)據(jù)中，核密度估計比常用的概率密度圖(Probability Density Plot，PDP)方法具有更穩(wěn)定、強壯的性能。核密度估計通過對一組高斯分布求和來估計數(shù)據(jù)頻率，它與概率密度圖PDP相反，不需要考慮分析不確定性的影響。這一特點能較好地適用于計算樣本點的密度，下面給出核密度計算公式。

設(shè)x表示密度為f(x)的隨機變量，在本文中，x可看做數(shù)據(jù)集D中一個具有d維特征的數(shù)據(jù)對象，f(x)可以近似表示為：

f(x|h)=f(x)*Kh(x)

(2)

其中，Kh(x)=K(x/h)/h,K(x)是有關(guān)x的核函數(shù)。實際上，f(x|h)可被看做隨機變量x+δ的密度，δ是另一個隨機變量，其均值為0，密度為Kh(δ).當h是一個較小的值的時候，f(x|h)和f(x)之間的差別實際上可以忽略不計。

(3)

其中，ω(h)在實際中通常是未知的，將ω(h)當作參數(shù)向量組中的一個參數(shù)加以計算，能有效估計該值的大小。也就是說ω(h) 可用式(4)進行計算：

(4)

其中，θ是一個超參數(shù)向量，在這種情況下，h的先驗表示為ω(h|θ)，h的貝葉斯估計表示為h0(x|θ).因為f(x|h)是未知的，任何基于ω(h|θ)的推理或計算都不能直接進行。當從x觀察到一個隨機樣本，表示為{x1,x2,…,xd}時，可以用樣本均值來近似描述f(x|h)的值，形式化描述如下：

(5)

該值被稱為f(x)的核估計量，可以估計x點在數(shù)據(jù)集D中的密度。

2.3 鄰域密度度量

基于局部密度的異常檢測，其性能在很大程度上取決于鄰域參數(shù)k值的選擇，只有當k值足夠大，使得鄰域中的大多數(shù)樣本保持正常，才能有效檢測到離群的數(shù)據(jù)。為了提高對參數(shù)k的魯棒性影響，特提出一種基于均值的鄰域密度。與傳統(tǒng)的鄰域密度相比，基于均值的鄰域密度是領(lǐng)域中所有樣本點的局部密度均值，它對鄰域中存在的離群數(shù)據(jù)非常敏感，其形式化定義如下所示：

(6)

公式(6)表示樣本點x的鄰域密度，其中q是樣本點x的任一鄰居，即它是x的k-距離鄰域中一個點。該公式可以看出，k距離越大，樣本點的局部密度越小，對于正態(tài)樣本，其鄰域樣本大多是正態(tài)的，其鄰域密度與平均鄰域密度相似。但對于一個異常，當參數(shù)k很小時，其鄰域中異常的比例是不確定的。當樣本中有很大一部分是異常鄰域中的異常時，鄰域密度可能急劇下降，從而影響異常的檢測。采用基于均值的局部密度估計，得到的k值范圍比傳統(tǒng)的鄰域密度估計的k值范圍寬得多，因此它對k值的變化具有更強的魯棒性。

3 離群挖掘與算法描述

3.1 離群因子估計

離群因子用于估計樣本的離群程度，是判斷離群數(shù)據(jù)的重要因素。通常情況下，正常的樣本位于稠密區(qū)域，比較密集，具有較高的局部密度和鄰域密度。相反地，離群數(shù)據(jù)一般分布在比較稀疏的區(qū)域，樣本點的局部密度較低，而且樣本點與其鄰居的距離較遠。因此，可以采用樣本點的局部密度以及其鄰域密度估計作為樣本點的離群因子，并用于度量樣本點是處于稠密區(qū)域還是稀疏區(qū)域，從而確定是否屬于離群對象。下面公式給出了離群因子Outlier(x)的形式化定義。

(7)

從公式(7)可以看出，樣本的局部核密度越小，其鄰域的均值密度越大，離群因子越大，樣本越可能是離群數(shù)據(jù)。對于大多數(shù)與正常對象分離的離群數(shù)據(jù)，它們的局部密度與鄰域密度相差很大，從而保證了它們的離群因子遠大于1.對于數(shù)據(jù)集中的大多數(shù)樣本點，它們的局部密度更接近其鄰域密度，從而確保其離群因子在1左右波動。這使得區(qū)分離群和正常樣本數(shù)據(jù)變得很容易。

考慮到所有樣本的離群因素，離群數(shù)據(jù)的檢測方法可有如下兩種：1)按離群因子的降序排列的前N個樣本視為異常；2)離群因子大于閾值的樣本被視為離群，在本文中，采用第一種方法實現(xiàn)離群數(shù)據(jù)的檢測。

3.2 算法描述

基于核密度估計的離群挖掘算法(Outlier Mining based on Dernel Density Estimation，OMDE)總體上分為三步，第一步是確定數(shù)據(jù)集D中每個對象的k-距離鄰域，這一步需要計算兩兩對象之間的距離，并返回每個對象的k個鄰居及其距離；第二步是根據(jù)公式(5)計算并估計每個對象的樣本點密度，然后根據(jù)公式(6)估算每個樣本點的鄰域密度；最后，根據(jù)公式(7)計算每個對象的離群因子，將所有離群因子排序，獲取最大的N個值，其對應(yīng)的數(shù)據(jù)對象為離群數(shù)據(jù)。其算法描述如下：

算法： OMDE

輸入：數(shù)據(jù)集D，離群數(shù)量N，鄰居數(shù)量k；

輸出：離群數(shù)據(jù)；

1)for each object x in dataset D

2) dis[]=dis(x,o);//o是除x之外的對象

3) disk(x)=sort(dis[],k);

4) Near[ ] = compute k-nearest neighbors of x

5)end for

6)for(i = 0; i < n; i++)

7) for (j = 0; j < d; j++)

9) end for

11)end for

12)for each object x in dataset D

14) All Outlier(x)are saved to the array fac[];

15)end for

16)sort(fac[]);

17)return the largest N values in fac[];

18)end

4 實驗與分析

本節(jié)描述了一系列實驗并給出了相應(yīng)的實驗分析，主要從準確性和時間的角度將本文提出的算法OMDE與其他最先進的方法進行比較，并分析了參數(shù)k和N對OMDE算法性能的影響。

4.1 人工合成數(shù)據(jù)集

為了有效評價參數(shù)對算法OMDE的性能影響，數(shù)據(jù)集的選擇是一個較難解決的問題，為此，我們采用人工合成數(shù)據(jù)集。具體而言，是采用文獻[14]給出的基于分割模型的數(shù)據(jù)生成方法，生成了不同簇數(shù)的合成圖，這些合成圖聚焦于屬性空間的不同子集，包含多個聚簇，并且具有不同的大小范圍?？傮w而言，該數(shù)據(jù)集和任務(wù)是基于密度的離群點檢測的經(jīng)典設(shè)置：與聚集圖像的成員相比，稀有對象應(yīng)該位于密度較低的區(qū)域。

4.1.1 參數(shù)k對算法的影響

在基于k近鄰的數(shù)據(jù)分類以及離群數(shù)據(jù)挖掘中，參數(shù)k對算法有較大的影響，主要體現(xiàn)在對算法效率和準確性的影響。

圖2顯示了不同的k值對OMDE算法效率的影響，從該圖中可以看出，OMDE算法無論采用那種核函數(shù)，都會隨著k值的增加，其效率降低，即算法執(zhí)行的時間隨著k值的增加而增加。其原因是，當k值增加時，每個樣本點計算其k近鄰的個數(shù)會增加，毫無疑問，這會需要更多的時間代價。另外，在相同的k值下，采用本文提出的核函數(shù)比Gaussian和Epanechnikov核函數(shù)具有更少的執(zhí)行時間，這能充分體現(xiàn)本文核函數(shù)在離群挖掘中具有更好的性能。

圖2 參數(shù)k對OMDE算法的效率影響Fig.2 The effect of parameter k on the efficiency

圖3顯示了不同的k值對OMDE準確性的影響，從該圖中能看出，隨著k值的增加，算法的準確性明顯增加，其原因是當k是一個較大的值的時候，樣本點的k近鄰的計算更加準確，這更能體現(xiàn)節(jié)點之間的不同，從而提高離群數(shù)據(jù)挖掘的準確性。

圖3 參數(shù)k對OMDE算法的準確性影響Fig.3 The effect of parameter k on the accuracy of OMDE algorithm

4.1.2 參數(shù)N對算法的影響

在OMDE算法中，離群數(shù)據(jù)的檢測是按離群因子的降序排列的前N個樣本，因此參數(shù)N對算法的性能具有較大的影響。

圖4顯示了不同的N值對算法OMDE執(zhí)行時間的影響，從該圖可以看出，當N值增加時，無論采用那種核函數(shù)，算法的執(zhí)行時間都將增加，特別地，Epanechnikov核函數(shù)同其它兩個核函數(shù)相比，具有最低的效率。其原因是，當N值增大時，說明需要找出更多的離群點進行輸出，這會增加離群檢測的開銷，導(dǎo)致算法效率降低。

圖4 參數(shù)N對OMDE算法的效率影響Fig.4 The effect of parameter N on the efficiency of OMDE algorithm

圖5是參數(shù)N對算法準確性的影響，隨著N值的增大，算法的準確性明顯增高，這是因為當N是一個大值的時候，離群數(shù)據(jù)的范圍將擴大，真正的離群將更有機會被檢測。從圖5還能看出，本文提出的核函數(shù)的準確性比其它兩個核函數(shù)的準確性略低，但在N為300時，三個核函數(shù)的準確性基本相同，結(jié)合圖4的算法效率能夠得出，本文提出的核函數(shù)以微不足道的準確性的降低換取了較高的效率。

圖5 參數(shù)N對OMDE算法準確性的影響Fig.5 The effect of parameter N on the accuracy of OMDE algorithm

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

本組實驗主要實現(xiàn)相關(guān)算法之間的性能比較，為了體現(xiàn)實驗的多樣性，我們采用下面幾組真實數(shù)據(jù)作為實驗的數(shù)據(jù)集。

The KDD Cup 1999：這是一個用于網(wǎng)絡(luò)入侵檢測研究的通用數(shù)據(jù)集。在這個數(shù)據(jù)集中，選取60 593個正常對象和228個標記為離群的對象，每個對象由41個特征屬性，這些數(shù)據(jù)共同構(gòu)成了KDD數(shù)據(jù)集，成為算法性能比較的第一組實驗數(shù)據(jù)。

The Mam dataset：該數(shù)據(jù)集是從乳腺攝影圖像數(shù)據(jù)集中提取的。包括9 923個正常對象和200個離群對象，每個對象具有6個特征屬性，Mam數(shù)據(jù)集，成為算法性能比較的第二組實驗數(shù)據(jù)。

The Ann dataset:這是甲狀腺病變的數(shù)據(jù)集，由3 000個標準對象和50個離群對象構(gòu)成，每個對象包含21個屬性，這是本節(jié)的第三組實驗數(shù)據(jù)。

4.2.1 效率比較

在算法效率比較的實驗中，將我們算法的OMDE與ADMNC和KEDOS算法進行了比較。ADMNC[14]是一種用于處理具有分類和數(shù)值輸入變量混合的大規(guī)模問題的異常檢測算法；而KEDOS[15]是一種基于核密度估計的基于密度的孤立點檢測方法，它允許集成領(lǐng)域知識和特定需求，能嵌入在更廣泛的離群點檢測框架中。圖6給出了不同數(shù)據(jù)集下各個算法的運行時間，該圖顯示，本文提出的方法OMDE，無論在那個數(shù)據(jù)集上，其運行時間都最短，充分說明，OMDE算法同ADMNC和KEDOS相比，具有更高的效率。

圖6 不同算法效率比較Fig.6 Efficiency comparison of different algorithms

4.2.2 準確性比較

圖7是在不同數(shù)據(jù)集上，算法OMDE與ADMNC和KEDOS的準確性比較。圖7顯示，在KDD Cup數(shù)據(jù)集上，我們的方法OMDE同其他兩個算法相比，準確性具有非常顯著的提高，而在Mam和Ann數(shù)據(jù)集上，準確性改善的幅度不大。結(jié)合圖6算法效率的比較，可充分說明，OMDE算法不僅在效率上，而且在精度上，同先進算法ADMNC和KEDOS相比，都有顯著改善。

圖7 不同算法準確性比較Fig.7 Accuracy comparison of different algorithms

5 總結(jié)

數(shù)據(jù)集的形態(tài)復(fù)雜多變，導(dǎo)致不同數(shù)據(jù)集的密度難以計算，針對這一問題，本文提出了一種基于核密度估計的離群數(shù)據(jù)挖掘算法OMDE。在定義樣本鄰域的基礎(chǔ)上，結(jié)合核密度估計，給出了樣本點及其鄰域的核函數(shù)，并推導(dǎo)了核密度估計的公式及方法，為樣本點密度的度量提供了一種有效方法。在此基礎(chǔ)上，通過計算離群因子來檢測離群數(shù)據(jù)，從而為離群數(shù)據(jù)挖掘提供了一種新算法。為了有效適應(yīng)數(shù)據(jù)集在量上的急劇膨脹，下一步將重點研究基于核密度估計的并行離群檢測算法。