張玉婷，馮 山

（1.四川師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院，成都 610068；2.四川師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，成都 610068）

引 言

離群點(diǎn)檢測(cè)多用于入侵檢測(cè)、信用卡詐騙和醫(yī)學(xué)診斷等領(lǐng)域［1-2］，有分布式［3］、深度［4］、距離［5-6］、密度［7］和聚類［8］等方法。分布式檢測(cè)要預(yù)設(shè)數(shù)據(jù)分布規(guī)律，不適合分布未知情形；深度法針對(duì)高維數(shù)據(jù)，效率低；距離和密度法由于利用歐式距離來設(shè)計(jì)，所以不是檢測(cè)標(biāo)稱或混合屬性離群點(diǎn)的最佳方法；聚類法開銷大。

粒計(jì)算作為一個(gè)重要的研究方向，它主要分為2類：（1）以處理不確定性為主要目標(biāo)，如以模糊處理和粗糙集為基礎(chǔ)的計(jì)算模型；（2）以多粒度計(jì)算為目標(biāo)，如商空間理論。其中，經(jīng)典粗糙集理論模型［9］已經(jīng)成功應(yīng)用于標(biāo)稱特征選擇和相關(guān)性分析等研究。近年來，針對(duì)距離和密度法不能有效處理包含標(biāo)稱屬性數(shù)據(jù)的不足，提出了多種基于粗糙集的方法。例如，基于經(jīng)典粗糙集，文獻(xiàn)［10］采用粒計(jì)算的思想構(gòu)建對(duì)象離群因子并做離群檢測(cè)。文獻(xiàn)［11］用粗糙邊界定義對(duì)象異常度以做離群檢測(cè)。文獻(xiàn)［12］用粗糙集隸屬度擴(kuò)展了一種新方法。文獻(xiàn)［13］提出了基于粗糙邊界和距離的離群檢測(cè)。文獻(xiàn)［14］提出了基于經(jīng)典近似精度的離群檢測(cè)。但它們采用等價(jià)關(guān)系的方式建立數(shù)學(xué)模型，其檢測(cè)模型均只適于處理標(biāo)稱屬性數(shù)據(jù)集。

基于鄰域粗糙集的特征選擇［15-16］能有效處理混合屬性數(shù)據(jù)集。例如，文獻(xiàn)［17］提出了基于鄰域模型的鄰域離群檢測(cè)。然而，其對(duì)參數(shù)選擇非常敏感。文獻(xiàn)［18-21］提出了面向混合屬性數(shù)據(jù)的離群檢測(cè)。但這些方法均未考慮鄰域粗糙度量的離群點(diǎn)檢測(cè)模型。鄰域粗糙度量主要包括鄰域近似精度和鄰域粗糙度量等［16］，它是度量混合屬性數(shù)據(jù)不確定性的有效方法，可以用于混合屬性數(shù)據(jù)集的離群點(diǎn)檢測(cè)建模。

針對(duì)混合屬性離群點(diǎn)檢測(cè)問題，本文構(gòu)造了一種基于鄰域近似精度的離群點(diǎn)檢測(cè)方法（Neighborhood approximation accuracy-based outlier detection，NAAOD）。該方法以優(yōu)選異構(gòu)鄰域關(guān)系度量和統(tǒng)計(jì)鄰域半徑構(gòu)建鄰域信息系統(tǒng)（Neighborhood information system，NIS），以鄰域近似精度離群因子表征對(duì)象離群度。對(duì)比實(shí)驗(yàn)表明，NAAOD算法能同時(shí)適于各種屬性組合的離群檢測(cè)。

1 預(yù)備知識(shí)

假設(shè)信息系統(tǒng)IS=(U，A，V，f)，其中U={x1，x2，…，xn}，屬性集A非空為屬性a的值域；f：U×A→V，?a∈A和?x∈U，f(x，a)∈Va。當(dāng)A=C∪D時(shí)，信息系統(tǒng)變?yōu)闆Q策系統(tǒng)，簡(jiǎn)記為DS=(U，C∪D，V，f)，其 中C={c1，c2，…，cm}且D=syggg00。為 討 論方 便，設(shè)B?C且|·|為集 合的勢(shì)。

定義1［15］論域?qū)ο髕i的B鄰域?xi∈U和?B?C，δB(xi)={xj|xj∈U，ΔB(xi，xj)≤ε}是xi的B鄰域，ε是鄰域半徑，ΔB(xi，xj)是距離函數(shù)。對(duì)?xi，xj，xk∈U，有：

（1）ΔB(xi，xj)≥0?xi=xj，ΔB(xi，xj)=0；

（2）ΔB(xi，xj)=ΔB(xj，xi)；

（3）ΔB(xi，xk)≤ΔB(xi，xj)+ΔB(xj，xk)。

例如，關(guān)于條件屬性子集C的混合歐式重疊度量（Heterogeneous euclidean overlap metric，HEOM）［22］為其中

式中ω{cj}為cj的權(quán)重。顯然，式（1）可同時(shí)處理數(shù)值、標(biāo)稱屬性及屬性值未知情形。δB(xi)為關(guān)于屬性子集B的以xi為中心的鄰域粒，ε=0時(shí)退化為等價(jià)類。

?xi∈U，δ(xi)??且稱{δB(xi)|xi∈U}覆蓋論域U。U上鄰域關(guān)系N B可寫成關(guān)系矩陣易知N B是相似關(guān)系，鄰域內(nèi)樣本彼此相似，δB(xi)是0-1向量，即

2 基于鄰域近似精度的混合離群點(diǎn)檢測(cè)

2.1 檢測(cè)方法

可用最小-最大歸一化［18］對(duì)數(shù)據(jù)集屬性和維數(shù)差異作量綱統(tǒng)一。同HEOM，異構(gòu)鄰域關(guān)系度量（Heterogeneous neighborhood relation metric，HNRM）可定義如下：

定義4對(duì)給定，?xi，xj∈U，B={cj1，cj2，…，cjl}(1≤l≤m)?C，xi與xj的混合或HNRM值，其中

易知，式（2）可同時(shí)度量不同屬性組合的對(duì)象差異度，但ε一般由專家確定［17，19，21］，其主觀隨意性會(huì)導(dǎo)致算法對(duì)參數(shù)敏感。為此，文獻(xiàn)［18］提出了具有自適應(yīng)特性的ε取值法，即

式中：std(cj)為屬性標(biāo)準(zhǔn)差；λ為調(diào)整參數(shù)。顯然，式（3）的鄰域半徑ε取值方式更為合理，它用于調(diào)整鄰域半徑。

性質(zhì)1條件屬性子集并的鄰域關(guān)系等價(jià)于其鄰域關(guān)系的交，即對(duì)

假設(shè)C1，C2?C分別為數(shù)值型和標(biāo)稱型條件屬性子集。由性質(zhì)1易知，對(duì)象x的鄰域有如下等式成立：

對(duì)x∈U和U上鄰域關(guān)系，可得x的一組鄰域粒。利用x的鄰域粒差異或距離等信息可以進(jìn)行離群檢測(cè)。一般而言，為計(jì)算x的離群度，可先算鄰域粒離群度，再確定離群因子。鄰域粒離群度可用鄰域粒的鄰域近似精度度量。

定義5特定鄰域近似精度關(guān)于NE的鄰域近似精度可定義為

鄰域近似精度常用來度量決策類的論域近似度。一般來說，δB(xi)對(duì)一組鄰域關(guān)系近似精度很低時(shí)表明δB(xi)行為異常或離群程度高。而經(jīng)典近似精度離群因子［14］僅適于度量標(biāo)稱屬性。對(duì)混合屬性，可用鄰域粒離群度（Neighborhood granule outlier degree，NGOD）和鄰域近似精度離群因子（Neighborhood approximation accuracy-based outlier factor，NAAOF）有效度量。前者度量給定鄰域粒的離群程度，后者度量給定對(duì)象的離群程度。

式中δB(xi)對(duì)一組鄰域關(guān)系的近似精度很低時(shí)δB(xi)對(duì)鄰域關(guān)系影響小，可認(rèn)為δB(xi)行為異常且離群度高。此時(shí)，NGOD(δB(xi))大，可以度量δB(xi)的異常性，進(jìn)而度量xi的離群性?；贜GOD的鄰域近似精度離群因子，即論域?qū)ο髕i的NAAOF定義如下：

定義7xi∈U的鄰域近似精度離群因子可定義為

2.2 檢測(cè)算法步驟及復(fù)雜度

算法步驟如下：

輸入：IS=(U，C，V，f)，鄰域離群閾值μ，調(diào)整參數(shù)λ

輸出：離群點(diǎn)集OS

算法復(fù)雜度：第（2）步的頻度為(n×n)，對(duì)第（3～12）步的頻度為m×(m+1+(m-1)×n)，第（13～18）步的頻度為n。故整體的頻度為(n2+m2×n+m2+m+n-m×n)。因此，算法的時(shí)間復(fù)雜度為O(m2n)，空間復(fù)雜度為O(mn)。

3 數(shù)據(jù)實(shí)驗(yàn)及結(jié)果

實(shí)驗(yàn)以文獻(xiàn)［14，18］預(yù)處理方法為基礎(chǔ)，并與適于標(biāo)稱的基于粒計(jì)算和粗糙集的離群檢測(cè)（Outlier detection based on granular computing and rough set theory，ODGrCR）［14］、基于粒計(jì)算（Granular computing，GrC）的方法［10］、基于粗糙隸屬度函數(shù)（Rough membership function，RMF）的方法［12］、適于數(shù)值屬性的基于距離（Distance，DIS）的方法［5］以及適于混合屬性的基于鄰域信息熵的離群檢測(cè)（Neighborhood information entropy-based outlier detection，NIEOD）［19］和基于鄰域值差異度量的離群檢測(cè)（Neighborhood value different metric-based outlier detection，NVDMOD）［20］算法進(jìn)行對(duì)比，以驗(yàn)證NAAOD算法的有效性。最后，從文獻(xiàn)［18］中選擇了6個(gè)離群點(diǎn)檢測(cè)數(shù)據(jù)集（含標(biāo)稱、數(shù)值和混合屬性）。這些數(shù)據(jù)集分別為Cred、Germ、Heart、Lymp、Wbc和Yeast。進(jìn)一步，它們被分別導(dǎo)入信息系統(tǒng)ISC、ISG、ISH、ISL、ISW和ISY。為便于比較，同文獻(xiàn)［14］的策略，分別從離群點(diǎn)數(shù)據(jù)集中選取2個(gè)子集，最終實(shí)驗(yàn)數(shù)據(jù)子集的基本特征信息描述如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)集描述Table 1 Description of experimental data set

以離群點(diǎn)覆蓋率（Coverage ratio，CR）［19，23］來評(píng)價(jià)所提算法。設(shè)OStopk(X)是X中離群值排前k的對(duì)象，OStrue(X)是真實(shí)離群點(diǎn)，則|OStopk(X)∩OStrue(X)|即檢測(cè)出的真實(shí)離群點(diǎn)數(shù)。易知，CR(k)=|OStopk(X)∩OStrue(X)|/|OStrue(X)|為離群點(diǎn)覆蓋率。顯然，TR(k)不變時(shí)，CR(k)越大算法性能越好。在實(shí)驗(yàn)中，取k=|OStrue(X)|時(shí)的離群點(diǎn)覆蓋率作為最終對(duì)比結(jié)果。

對(duì)于NAAOD、NIEOD和NVDMOD算法，其參數(shù)調(diào)節(jié)范圍均為［0.1，2］且步長(zhǎng)為0.1。最終，最優(yōu)覆蓋率作為實(shí)驗(yàn)結(jié)果。GrC算法的粒距離采用重疊距離法度量［10］。在粗糙集方法中，Lymphography和Wisconsin Breast Cancer對(duì)象的屬性值均被當(dāng)作標(biāo)稱類型［8］。除Yeast數(shù)據(jù)集，用MDL［24］離散化數(shù)值屬性外，其他數(shù)值屬性均使用Weka中等寬的離散化方法，其中離散化區(qū)間數(shù)為3。DIS算法采用歐氏距離度量和最小-最大歸一化預(yù)處理。

NAAOD算法與對(duì)比算法在代表子集上的實(shí)驗(yàn)對(duì)比結(jié)果如表2所示。從表2中可以看出，NAAOD算法在6個(gè)混合屬性數(shù)據(jù)子集上實(shí)現(xiàn)了較優(yōu)的結(jié)果。例如，在C1上，NAAOD算法的覆蓋率為88.00%，與NIEOD和NVDMOD算法相等。而對(duì)于ODGrCR、GrC、RMF和DIS算法，其覆蓋率分別為60.00%、28.00%、64.00%、68.00%，均小于NAAOD算法的覆蓋率。因此，本文所提方法適用于混合屬性數(shù)據(jù)的離群點(diǎn)檢測(cè)。

此外，NAAOD算法在兩個(gè)標(biāo)稱屬性數(shù)據(jù)上均取得了最高的覆蓋率。表2顯示，NAAOD算法在兩個(gè)標(biāo)稱屬性數(shù)據(jù)上的覆蓋率為100%，即它能檢測(cè)出全部離群點(diǎn)。然而，對(duì)于其他方法的覆蓋率均小于或等于100%。同理，通過表2可以看出NAAOD算法在大部分?jǐn)?shù)值屬性數(shù)據(jù)的覆蓋率均大于或等于其他對(duì)比算法。通過上述分析表明NAAOD算法也能有效處理標(biāo)稱和數(shù)值屬性數(shù)據(jù)集。

表2 對(duì)比實(shí)驗(yàn)結(jié)果Table 2 Results of comparative experiments %

閾值λ在NAAOD算法中起著重要的作用。C1和W2數(shù)據(jù)集被選取來探索參數(shù)對(duì)實(shí)驗(yàn)結(jié)果的敏感性。在C1和W2數(shù)據(jù)集上，其覆蓋率隨參數(shù)λ的變化曲線如圖1所示。從圖1可以看出在大部分?jǐn)?shù)據(jù)集上隨λ增加，其覆蓋率先增加，然后呈現(xiàn)出趨于平衡的趨勢(shì)。同時(shí)，也可以看到對(duì)于不同的數(shù)據(jù)集可以在多個(gè)參數(shù)λ值下取得最優(yōu)值。

圖1 在C1和W2數(shù)據(jù)集上覆蓋率隨參數(shù)λ的變化曲線Fig.1 Variation curves of coverage rates with parameters λ on C1 and W2 datasets

4 結(jié)束語

基于鄰域粗糙集框架，圍繞混合屬性離群檢測(cè)問題，提出了基于鄰域近似精度的具有自適應(yīng)特性的離群檢測(cè)方法。其離群因子融入了具有自適應(yīng)特性的HNRM度量，且數(shù)值型屬性無需離散化，能處理混合型數(shù)據(jù)集。數(shù)據(jù)實(shí)驗(yàn)結(jié)果表明，NAAOD算法能有效處理數(shù)值、標(biāo)稱和混合型屬性數(shù)據(jù)集。接下來將從三支決策角度進(jìn)一步研究基于粗糙集模型的其他相關(guān)離群點(diǎn)檢測(cè)方法。