段 珣，楊志勇，江 峰

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

0 引 言

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

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

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

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

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

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

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

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下的距離度量及鄰域半徑的確定采用文獻[16-17]的方法。

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

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

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

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

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

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

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

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

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

3 基于鄰域粒度熵的離群點檢測算法OD_NGE

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

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

OD_NGE算法的偽代碼如下：

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

輸出：U中的離群點集合O。

Step1將離群點集合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加入離群點集合O中。

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

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

下面，通過實驗來驗證OD_NGE算法的離群點檢測性能。對比算法包括：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)的基于距離的離群點檢測方法；NED是一種鄰域半徑直接給定的鄰域離群點檢測方法；NVDMOD是一種基于鄰域值差異度量的離群點檢測方法；SMAOD是一種基于序列的離群點檢測方法。

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

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

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

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

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

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

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

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

接下來，本文在Lymphography數(shù)據(jù)集上進行實驗。該數(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類的樣本看作是離群點，因此，該數(shù)據(jù)集中總共有6個離群點。

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

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

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

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

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

5 結(jié)束語

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

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