一種基于鄰域粒度熵的離群點(diǎn)檢測算法

段 珣，楊志勇，江 峰

(青島科技大學(xué)信息科學(xué)與技術(shù)學(xué)院，山東 青島 266061)

0 引 言

離群點(diǎn)是數(shù)據(jù)集中顯著區(qū)別于其他數(shù)據(jù)對象的一小部分?jǐn)?shù)據(jù)對象，這部分對象不符合數(shù)據(jù)集的一般模型。在信用卡欺詐檢測、網(wǎng)絡(luò)入侵檢測、故障診斷、醫(yī)療診斷等諸多領(lǐng)域中，離群點(diǎn)檢測技術(shù)都可以發(fā)揮重要作用。離群數(shù)據(jù)并不等同于錯誤數(shù)據(jù)，其出現(xiàn)往往隱含或預(yù)示著某種具有特殊意義的事件或現(xiàn)象。與分類、聚類等數(shù)據(jù)挖掘技術(shù)相比，離群點(diǎn)檢測可能更加有用，因為1萬條正常的記錄可能只覆蓋一條分類規(guī)則，而10個離群點(diǎn)可能就蘊(yùn)含著10條有用的規(guī)則。例如，如果將離群點(diǎn)檢測應(yīng)用于入侵檢測，那么10個離群點(diǎn)可能就代表10個入侵，而將其應(yīng)用于信用卡欺詐檢測，那么10個離群點(diǎn)可能就代表10起信用卡盜用事件。

離群點(diǎn)檢測最早出現(xiàn)在統(tǒng)計學(xué)領(lǐng)域，現(xiàn)有的離群點(diǎn)檢測方法主要分為：基于統(tǒng)計的檢測方法[1]、基于距離的方法[2]、基于密度的方法[3]、基于聚類的方法[4]、基于粗糙集的方法[5]。

已有的離群點(diǎn)檢測方法大多假設(shè)所處理的數(shù)據(jù)是確定和完備的，而現(xiàn)實(shí)生活中又存在著很多的不確定與不完備數(shù)據(jù)。為了處理這類數(shù)據(jù)，研究者提出了一系列基于粗糙集的離群點(diǎn)檢測方法[2,5-7]。自1982年P(guān)awlak[8]提出粗糙集理論以來，粗糙集已經(jīng)成為處理不確定性、不完備性的重要工具?；诖植诩碾x群點(diǎn)檢測方法獲得了廣泛關(guān)注。然而經(jīng)典的粗糙集模型不適合于直接處理數(shù)值型數(shù)據(jù)。為了從數(shù)值型數(shù)據(jù)中檢測離群點(diǎn)，已有的基于粗糙集的離群點(diǎn)檢測方法通常需要對數(shù)值型數(shù)據(jù)進(jìn)行離散化處理。離散化過程很容易導(dǎo)致信息的丟失，從而影響到后續(xù)的離群點(diǎn)檢測的整體性能。

針對經(jīng)典的粗糙集模型在處理數(shù)值型數(shù)據(jù)上所存在的困難，有必要考慮采用擴(kuò)展的粗糙集模型來進(jìn)行離群點(diǎn)檢測，例如，采用鄰域粗糙集模型來檢測離群點(diǎn)。鄰域粗糙集模型最早由Hu等[9-11]所提出。作為經(jīng)典粗糙集模型的一種有效擴(kuò)展，鄰域粗糙集能夠直接處理數(shù)值型數(shù)據(jù)，從而避免了離散化過程所帶來的信息丟失問題。

基于上述考慮，本文利用鄰域粗糙集模型來檢測離群點(diǎn)。具體而言，在鄰域粗糙集中引入一種新的信息熵模型——鄰域粒度熵。通過使用鄰域粒度熵，可以有效度量論域U中各個對象之間的差別，從而檢測出其中所存在的離群點(diǎn)。

為了解決信息的量化度量問題，Shannon[12]在1948年首次提出信息熵的概念。近年來，信息熵已被擴(kuò)展到鄰域粗糙集中，并由此出現(xiàn)了一些新的信息熵模型。Hu等人[13]將信息熵概念拓展到鄰域粗糙集中，提出了鄰域信息熵的概念。在文獻(xiàn)[14]中，Chen等人進(jìn)一步發(fā)展了鄰域信息熵理論，提出了一種基于鄰域信息熵的不確定性度量方法。目前，鄰域信息熵已被用于解決屬性約簡、規(guī)則獲取等實(shí)際問題[15]。但是，利用鄰域信息熵來進(jìn)行離群點(diǎn)檢測的研究尚不多見。因此，開展基于鄰域信息熵的離群點(diǎn)檢測研究是非常有必要的，不僅可以解決經(jīng)典的粗糙集模型在處理數(shù)值型數(shù)據(jù)上所存在的困難，而且還可以進(jìn)一步拓展鄰域信息熵的應(yīng)用范圍。

基于鄰域粒度熵，本文提出一種新的離群點(diǎn)檢測算法OD_NGE。通過在多個公共數(shù)據(jù)集上的實(shí)驗表明，OD_NGE算法的性能要優(yōu)于已有的離群點(diǎn)檢測方法。

1 基本理論

鄰域粗糙集中NS=(U,A,V,f,δ)為一個鄰域信息系統(tǒng)，其中，U={x1,x2,…,xn}是論域，表示對象的集合；A是屬性集；V=∪a∈AVa是值域，Va是單個屬性a的值域；δ表示鄰域半徑參數(shù)；f:U×A→V表示映射函數(shù)，即對任意x∈U以及a∈A，有f(x,a)∈Va。對任意x∈U和屬性子集B?A，對象x在屬性子集B上的鄰域類為[9-11]：

B在論域上的鄰域關(guān)系被定義為[9-11]：

對任意x,y∈U和屬性子集B?A，對象x、y在屬性子集B下的距離度量及鄰域半徑的確定采用文獻(xiàn)[16-17]的方法。

2 鄰域粒度熵與鄰域粒度熵離群因子

從定義3可以看出，鄰域粒度熵提供了一種更加全面的不確定性度量機(jī)制，它將鄰域信息熵和鄰域知識粒度這2個概念融合在一起，其中前者可以刻畫鄰域知識的完備性，而后者則可以刻畫鄰域知識的粒度大小。

接下來，利用鄰域粒度熵來計算論域U中每個對象的相對重要性，對象的相對重要性將被用于后續(xù)的離群點(diǎn)檢測任務(wù)。

除了對象的相對重要性，本文在檢測離群點(diǎn)時還考慮到“相對比重”和“基于相對勢的異常度”這2個因素。

其中，min和max分別表示|N1|、|N2|、…、|Nq|中的最小值和最大值。

相對比重刻畫了對象x所在的鄰域類(即群體)的規(guī)模。由于離群點(diǎn)屬于數(shù)據(jù)集中的一小部分對象，因此，對象所在的鄰域類的規(guī)模在一定程度上可以反映其離群的程度，即x所在的鄰域類的規(guī)模越大，則表明數(shù)據(jù)相對集中，x成為離群點(diǎn)的可能性就越低。

通過引入基于相對勢的異常度，進(jìn)一步放大了不同鄰域類的規(guī)模對離群點(diǎn)檢測結(jié)果的影響。

定義8 鄰域粒度熵離群因子。給定鄰域信息系統(tǒng)NS=(U,A,V,f,δ)，其中，A={a1,a2,…,ap}，對任意對象x∈U，對象x的鄰域粒度熵離群因子NGEOF(x)被定義為：

定義9 基于鄰域粒度熵的離群點(diǎn)。給定鄰域信息系統(tǒng)NS=(U,A,V,f,δ)，令μ為一個給定的閾值，對任意x∈U，如果NGEOF(x)>μ，則對象x被稱為NS中的一個基于鄰域粒度熵的離群點(diǎn)，其中NGEOF(x)為對象x的鄰域粒度熵離群因子。

3 基于鄰域粒度熵的離群點(diǎn)檢測算法OD_NGE

OD_NGE算法的流程如圖1所示。

如圖1所示，OD_NGE算法首先讀取數(shù)據(jù)集并將離群點(diǎn)集合置為空集；其次，針對數(shù)據(jù)集中每個屬性計算鄰域覆蓋；第3，針對每個屬性，計算其鄰域粒度熵；第4，計算論域U中每個對象x的重要性、相對比重、相對勢及異常度；第5，將第4步所得數(shù)值進(jìn)行集成計算，得到對象x的離群因子；第6，如果對象x的離群因子大于給定閾值，則將x放入離群點(diǎn)集合；最后，將離群點(diǎn)集合輸出。

OD_NGE算法的偽代碼如下：

輸入：NS=(U,A,V,f,δ)，其中U={x1,x2,…,xn},A={a1,a2,…,ap}；參數(shù)θ，閾值μ。

輸出：U中的離群點(diǎn)集合O。

Step1將離群點(diǎn)集合O初始置為空集。

Step2對任意屬性aj∈A, 1≤j≤p，循環(huán)執(zhí)行下列語句：

Step3對任意對象xi∈U, 1≤i≤n，循環(huán)執(zhí)行下列語句：

Step3.1對任意屬性aj∈A, 1≤j≤p，循環(huán)執(zhí)行下列語句：

Step3.2根據(jù)定義8與Step3.1所得數(shù)據(jù)計算對象xi的鄰域粒度熵離群因子NGEOF(xi)。

Step3.3如果NGEOF(xi)>μ，則將對象xi加入離群點(diǎn)集合O中。

Step4返回離群點(diǎn)集合O，算法結(jié)束。

4 實(shí)驗結(jié)果與分析

下面，通過實(shí)驗來驗證OD_NGE算法的離群點(diǎn)檢測性能。對比算法包括：KNN (K-Nearest Neighbor)[19]、NED (Neighborhood Outlier Detection)[20]、NVDMOD (Neighborhood Value Difference Metric-based Outlier Detection)[6]和SMAOD (Sequence-based Mixed Attribute Outlier Detection)[7]算法。在上述4個對比算法中，KNN屬于傳統(tǒng)的基于距離的離群點(diǎn)檢測方法；NED是一種鄰域半徑直接給定的鄰域離群點(diǎn)檢測方法；NVDMOD是一種基于鄰域值差異度量的離群點(diǎn)檢測方法；SMAOD是一種基于序列的離群點(diǎn)檢測方法。

不同算法的參數(shù)設(shè)置情況如下：首先，關(guān)于OD_NGE算法的參數(shù)設(shè)置，通過多次實(shí)驗來逐步調(diào)節(jié)參數(shù)θ的值，并選擇能夠獲得最優(yōu)實(shí)驗結(jié)果的參數(shù)值，最終，將參數(shù)θ的值設(shè)置為0.55。其次，對于4個對比算法，它們也包括一些需要提前設(shè)置的參數(shù)。這4個對比算法的每個參數(shù)均根據(jù)相關(guān)文獻(xiàn)中所提供的參數(shù)值來進(jìn)行設(shè)置[6-7,19-20]。

為了對比不同算法的離群點(diǎn)檢測性能，本文使用目前最常用的一類評價標(biāo)準(zhǔn)。該評價標(biāo)準(zhǔn)的主要思路如下：為了判斷一個離群點(diǎn)檢測算法的性能好壞，在多個數(shù)據(jù)集上運(yùn)行該算法，并計算該算法找到的離群點(diǎn)中屬于真正離群點(diǎn)的比例。這個比例越高，則說明該算法的離群點(diǎn)檢測性能越好。

實(shí)驗數(shù)據(jù)集包括：Breast Cancer和Lymphography，其中，Breast Cancer是一個數(shù)值型數(shù)據(jù)集，而Lymphography則是一個符號型數(shù)據(jù)集[21]。

首先在Breast Cancer數(shù)據(jù)集上進(jìn)行實(shí)驗。該數(shù)據(jù)集包括699個樣本和9個數(shù)值型屬性。所有樣本被分為2大類：begin(占比65.5%)和malignant(占比34.5%)。為了便于實(shí)驗，本文隨機(jī)選擇一部分malignant類別的樣本，并將其刪除。最終的Breast Cancer數(shù)據(jù)集包含483個樣本，其中，有39個樣本屬于malignant類，另外444個樣本則屬于begin類[22]。

不同算法在Breast Cancer數(shù)據(jù)集上的離群點(diǎn)檢測結(jié)果如表1所示。

實(shí)驗中，對于每個離群點(diǎn)檢測算法，根據(jù)由該算法所求出的所有樣本的離群程度值，將所有樣本進(jìn)行降序排序。所以，在表1中，“離群程度值前k%的樣本(樣本個數(shù))”是指在采用某個算法求出所有樣本的離群程度值之后，離群程度值排在前k%的樣本以及這些樣本的個數(shù)。另外，“屬于離群點(diǎn)的樣本個數(shù)”是指離群程度值排在前k%的樣本中，真正屬于離群點(diǎn)的樣本個數(shù)，“覆蓋率”是指真正屬于離群點(diǎn)的樣本個數(shù)占離群點(diǎn)總數(shù)的比例[23]。

表1 Breast Cancer上離群點(diǎn)檢測結(jié)果

從表1可以看出，在Breast Cancer數(shù)據(jù)集上，OD_NGE與NVDMOD這2個算法的離群點(diǎn)檢測性能比較接近，它們的性能要顯著優(yōu)于另外3個算法(即SMAOD、NED和KNN)，此外，OD_NGE算法的性能要略優(yōu)于NVDMOD算法。當(dāng)分析離群程度值前k%的樣本時，OD_NGE算法所檢測出的真正的離群點(diǎn)個數(shù)以及覆蓋率總是最高的。例如，分析離群程度值前5%的樣本時(合計有24個樣本)，OD_NGE算法和NVDMOD算法所檢測出的真正的離群點(diǎn)有24個，即由OD_NGE和NVDMOD所找出的24個離群點(diǎn)都是真正的離群點(diǎn)，沒有出現(xiàn)任何誤判，而SMAOD、NED和KNN算法分別只找到了22、19和20個真正的離群點(diǎn)，即這些算法分別出現(xiàn)了2、5和4次誤判。另外，分析離群程度值前8.3%的樣本時(合計有40個樣本)，OD_NGE算法所檢測出的真正的離群點(diǎn)有35個，即由OD_NGE算法所找出的40個離群點(diǎn)中有35個是真正的離群點(diǎn)，即只出現(xiàn)了5次誤判，而NVDMOD、SMAOD、NED和KNN算法分別只找到了33、33、31和32個真正的離群點(diǎn)，即這些算法分別出現(xiàn)了7、7、9和8次誤判。

接下來，本文在Lymphography數(shù)據(jù)集上進(jìn)行實(shí)驗。該數(shù)據(jù)集包括148個樣本，這些樣本由18個條件屬性和1個決策屬性來描述。所有樣本被分為4類：normal find (占比1.35%)、metastases (占比54.73%)、malign lymph (占比41.22%)、fibrosis (占比2.7%)。將Lymphography數(shù)據(jù)集中屬于normal find和fibrosis類的樣本看作是離群點(diǎn)，因此，該數(shù)據(jù)集中總共有6個離群點(diǎn)。

不同算法在Lymphography數(shù)據(jù)集上的離群點(diǎn)檢測結(jié)果如表2所示。

需要指出的是，Lymphography數(shù)據(jù)集所包含的離群點(diǎn)數(shù)量較少，而且大部分算法都能在離群點(diǎn)比例較低時就能夠檢測出所有的離群點(diǎn)。例如，當(dāng)離群點(diǎn)比例在10.1%時，大部分算法都已經(jīng)檢測出所有的離群點(diǎn)。為了展示出不同算法在檢測出每一個新的離群點(diǎn)時所對應(yīng)的離群點(diǎn)比例，因此，在表2中，離群點(diǎn)比例的等級劃分設(shè)置較密。

表2 Lymphography上的離群點(diǎn)檢測結(jié)果

從表2可以看出，在Lymphography數(shù)據(jù)集上，OD_NGE與SMAOD這2個算法的離群點(diǎn)檢測性能相同，它們的性能要顯著優(yōu)于另外3個算法(即NVDMOD、NED和KNN)。分析離群程度值前k%的樣本時，OD_NGE算法所檢測出的真正的離群點(diǎn)個數(shù)以及覆蓋率總是最高的。例如，分析離群程度值前4.7%的樣本時(合計有7個樣本)，OD_NGE算法和SMAOD算法所檢測出的真正的離群點(diǎn)有5個，即由OD_NGE和SMAOD所找出的7個離群點(diǎn)中有5個是真正的離群點(diǎn)，只出現(xiàn)了2次誤判，而NVDMOD、NED和KNN算法都只找到了4個真正的離群點(diǎn)，這些算法都出現(xiàn)了3次誤判。

綜合Breast Cancer和Lymphography這2個數(shù)據(jù)集上的實(shí)驗結(jié)果來看，OD_NGE算法的離群點(diǎn)檢測性能要優(yōu)于NVDMOD、SMAOD、NED和KNN這4個現(xiàn)有的算法。

5 結(jié)束語

近年來，基于粗糙集的離群點(diǎn)檢測方法得到了廣泛應(yīng)用，很多基于粗糙集的離群點(diǎn)檢測方法被提出[24-26]，且在入侵檢測[27]、信用卡欺詐檢測等方面有著實(shí)際的應(yīng)用，被很多商業(yè)公司提上了議事日程[28]。但是，由于經(jīng)典的粗糙集模型不適合于直接處理數(shù)值型數(shù)據(jù)，因此需要對數(shù)值型數(shù)據(jù)進(jìn)行離散化處理，而離散化過程又會導(dǎo)致信息的丟失。因此，如何利用粗糙集的方法從數(shù)值型數(shù)據(jù)中檢測離群點(diǎn)就成為該領(lǐng)域的一個關(guān)鍵問題。針對上述問題，本文基于鄰域粗糙集來檢測離群點(diǎn)，在鄰域粗糙集中提出了一種新的信息熵模型——鄰域粒度熵，并基于該模型設(shè)計了一種新的離群點(diǎn)檢測算法OD_NGE。實(shí)驗結(jié)果表明，OD_NGE算法能夠從數(shù)值型數(shù)據(jù)中有效地檢測出離群點(diǎn)。

在下一步的工作中，計劃將本文所提出的離群點(diǎn)檢測算法應(yīng)用于網(wǎng)絡(luò)入侵檢測中，即通過將入侵行為看作是偏離于正常行為的離群點(diǎn)，從而把離群點(diǎn)檢測作為一種無監(jiān)督的入侵檢測方法而應(yīng)用于入侵檢測。