李春生，于 澍，劉小剛

(東北石油大學(xué) 計算機(jī)與信息技術(shù)學(xué)院，黑龍江 大慶 163318)

0 引 言

隨著網(wǎng)絡(luò)和信息技術(shù)的廣泛普及，人們在日常活動中會產(chǎn)生大量的數(shù)據(jù)，而從這些數(shù)據(jù)中發(fā)現(xiàn)某種未知的規(guī)律，挖掘其中隱含的信息與知識，成為了研究者們的研究樂趣。在這個過程中，數(shù)據(jù)預(yù)處理占據(jù)了較大的一部分，其中很重要的一方面就是對于異常數(shù)據(jù)的識別，即異常點檢測技術(shù)，它會影響后續(xù)數(shù)據(jù)挖掘模型的預(yù)測效果和實用性。異常點又叫做噪聲、孤立點、離群點等。然而發(fā)現(xiàn)的異常數(shù)據(jù)并不能簡單地直接剔除掉，不僅會影響數(shù)據(jù)的連續(xù)性，而在某些領(lǐng)域中，這些被認(rèn)為是不正常的數(shù)據(jù)隱藏著更有價值的信息，例如把異常點檢測技術(shù)應(yīng)用到以下領(lǐng)域：保險理賠，銀行交易中的欺詐檢測及風(fēng)險分析；醫(yī)藥研究中藥品所產(chǎn)生的異常反應(yīng)[1]；網(wǎng)絡(luò)安全方面入侵行為的檢測。

目前，異常數(shù)據(jù)的挖掘算法大致有基于統(tǒng)計、基于距離、基于密度、基于聚類等。其中傳統(tǒng)的基于距離的異常數(shù)據(jù)挖掘算法原理較為簡單，使用方便，在數(shù)據(jù)集分布均勻的情況下，檢測效果較好，但存在以下缺陷：參數(shù)設(shè)置復(fù)雜，檢測效果對參數(shù)要求較高；異常數(shù)據(jù)并不是存在于所有屬性上，只存在于某些影響數(shù)據(jù)穩(wěn)定性的屬性上；當(dāng)數(shù)據(jù)集分布不均勻時，可能會出現(xiàn)偏差，不能有效地檢測出異常點。

為了解決上述問題，提出了一種基于改進(jìn)距離和的異常數(shù)據(jù)檢測算法；對于終端的不確定性選擇屬性困難的問題，引入了“屬性隸屬度”的概念；用改進(jìn)的距離進(jìn)行異常點的檢測，給出了異常點的異常程度。

1 基于距離的異常點檢測

1.1 異常點檢測方法

最先提出基于距離的異常點檢測方法的是Knorr和Ng[2]，他們認(rèn)為的異常點是這樣的：在數(shù)據(jù)集中至少有k部分?jǐn)?shù)據(jù)點之間的距離大于某一閾值d。其實質(zhì)是將異常點看作是在d范圍內(nèi)鄰居較少的點?；诰嚯x的異常點檢測算法一般分為以下三種：

(1)基于索引的算法(index-based)[3]。

該算法首先建立了一個多維索引結(jié)構(gòu)，然后根據(jù)該索引結(jié)構(gòu)查找出各個數(shù)據(jù)點在半徑為d的范圍內(nèi)的鄰居。需事先設(shè)定臨界個數(shù)k，在查找過程中當(dāng)某點的鄰居個數(shù)一旦大于k，則說明該點不是異常點，立即停止查找，并標(biāo)記該點為正常的數(shù)據(jù)點。直至將所有點都做好是否為異常點的標(biāo)記。在最不理想的情況下該算法的復(fù)雜度為O(s*n2)，其中s表示數(shù)據(jù)的維數(shù)，n表示數(shù)據(jù)點的個數(shù)。由于構(gòu)建索引結(jié)構(gòu)需要的時間較長，所以該算法是非常耗時的，因此應(yīng)用較少。

(2)基于循環(huán)嵌套的算法(nested-loop)[4]。

為了避免建立索引結(jié)構(gòu)，提出了一種基于循環(huán)嵌套的算法。首先將數(shù)據(jù)集均勻分成若干數(shù)據(jù)塊，同時將內(nèi)存緩沖區(qū)均分為A和B兩部分。然后將未在該區(qū)存儲過的數(shù)據(jù)塊讀入A部分，其他數(shù)據(jù)塊依次由B部分讀取(每次只讀取一個)。最后計算A和B兩部分的數(shù)據(jù)塊中每對數(shù)據(jù)對象之間的距離，并記錄A部分的每個數(shù)據(jù)對象的鄰居數(shù)。一旦大于k個，則停止計算，A部分繼續(xù)讀取下一個數(shù)據(jù)塊；若小于k個，則B部分繼續(xù)讀入下一數(shù)據(jù)塊。直至讀取完所有的數(shù)據(jù)塊，并累加鄰居數(shù)。該算法的時間復(fù)雜度與第一種算法的復(fù)雜度相同。

(3)基于單元的算法(cell-based)。

1.2 距離的度量及異常點的定義

常用的距離度量方法有曼氏距離、歐氏距離、切比雪夫距離等。

對于兩個m維空間中的數(shù)據(jù)點xi與xj，它們之間的歐幾里得距離和曼哈頓距離可以由明考斯基距離來概括，即：

(1)

其中，當(dāng)q=1時為曼哈頓距離，表示為：

(2)

當(dāng)q=2時，表示為最常用的歐幾里得距離：

(3)

其中，xik表示在第k維的第i個分量；xjk表示第k維的第j個分量。

切比雪夫距離表示為各坐標(biāo)數(shù)值差的最大值，即：

(4)

常用距離度量種類比較多，使用哪種距離度量要看算法應(yīng)用的具體領(lǐng)域。用不同的距離度量進(jìn)行計算，得到的結(jié)果也可能是不同的。

常見的基于距離的異常點定義有以下幾種：

(1)在數(shù)據(jù)集S中，若點O是異常點，那么至少有p部分對象到點O的距離大于d，也就是說，如果點O在以d為半徑的范圍內(nèi)，有不超過M個點的鄰居，那么點O就是一個帶有參數(shù)p和d的異常點，表示為DB(p,d)，這里M=n(1-p)，n是數(shù)據(jù)集S中的數(shù)據(jù)對象個數(shù)。

(2)異常點是指數(shù)據(jù)集S中的n個點，這n個點到其第k個最近鄰點的距離是其他所有點中最大的，其中n是異常點個數(shù)的估計值。

(3)在數(shù)據(jù)集S中，取前n個與其k個最近鄰點的距離之和最大的點，則這n個點就是異常點。其中n是異常點個數(shù)的估計值。

盡管以上幾種定義都各不相同，但都是基于距離的異常點的定義。文中將使用第三種定義來判斷數(shù)據(jù)集中的某個點是否為異常點。

2 基于改進(jìn)距離和的異常點檢測

公式中的參數(shù)及其意義如表1所示。

表1 參數(shù)及意義

2.1 檢測屬性的選取

在數(shù)據(jù)集中，異常點并不是存在于每個屬性上，它們只是在其中某一部分屬性上出現(xiàn)異常狀態(tài)。一般情況下，都是由該領(lǐng)域的專家來選取這些有研究價值的屬性，但是當(dāng)終端操作人員不具備相關(guān)的專業(yè)知識時，要從眾多數(shù)據(jù)中選取能夠影響數(shù)據(jù)穩(wěn)定性且具有研究價值的屬性比較困難，為此引入了“屬性隸屬度”的概念。它能夠反映每個屬性的檢測價值，即使無領(lǐng)域?qū)＜以趫龅那闆r下，終端操作人員也能夠通過計算每個屬性的“屬性隸屬度”，選取到最適合的檢測屬性。

屬性隸屬度μ：對于數(shù)據(jù)集中任意一條數(shù)據(jù)ω的任意屬性，都有一個數(shù)μ(ω)與之對應(yīng)，μ為該屬性的“屬性隸屬度”，μ(ω)為該屬性的隸屬度函數(shù)，表示為：

(5)

屬性的μ(ω)值越大，說明該屬性值的波動越大，檢測價值也越高，就越有可能成為被檢測的對象；μ(ω)值越小，該屬性值的波動也越小，檢測價值也越低，就越有可能被忽略。

2.2 改進(jìn)距離度量

為了解決由數(shù)據(jù)分布不均勻而導(dǎo)致的檢測準(zhǔn)確率低的問題，文中改進(jìn)了距離度量，以明考斯基距離為例，表示為：

(6)

其中λk定義為：

(7)

對于分布不均勻的數(shù)據(jù)集來說，基于常用距離的異常點檢測算法的檢測效果較差[5-7]，當(dāng)數(shù)據(jù)點分別分布在密集區(qū)域和稀疏區(qū)域時，由k個最近鄰點所組成的局部區(qū)域范圍是不同的，按照傳統(tǒng)基于距離的算法進(jìn)行異常點檢測時，就有可能會將原本正常的數(shù)據(jù)點標(biāo)記為異常點[8]。

圖1 不均勻分布的散點圖

圖1所示為非均勻分布的拋物線形數(shù)據(jù)集S，已知點A為數(shù)據(jù)集S中的一個異常點，點B為數(shù)據(jù)集S中正常的數(shù)據(jù)點，若點B到其k個最近鄰點的距離之和大于點A到其k個最近鄰點的距離之和，傳統(tǒng)基于距離的算法就可能會把B點當(dāng)作異常點來處理，而把點A認(rèn)為是正常的數(shù)據(jù)點[9-10]。

2.3 基于改進(jìn)距離和的異常點檢測算法

傳統(tǒng)基于距離的算法中，對DB(p,d)的參數(shù)設(shè)置比較復(fù)雜[13]，需要不斷進(jìn)行測試，找出符合用戶需求的參數(shù)，而所得結(jié)果對參數(shù)是敏感的。為了避免參數(shù)的設(shè)置，提出了一種基于改進(jìn)距離和的異常點檢測算法，并且給出了異常點的評價方法。步驟描述如下：

Step1:假設(shè)數(shù)據(jù)已經(jīng)過標(biāo)準(zhǔn)化，計算數(shù)據(jù)集中第一條數(shù)據(jù)與其他數(shù)據(jù)之間的距離dij。

Step2:由Step1得到該數(shù)據(jù)點與k個最近鄰點的距離之和Di(k)。

對此算法的說明如下：

(2)φi為評價異常點異常程度的關(guān)鍵，即矩陣P中第i行元素之和，φi的值越大，就說明數(shù)據(jù)點i離其他點越遠(yuǎn)。即該點比其他點異常。

3 實驗設(shè)計

實驗選取了100組股票交易數(shù)據(jù)進(jìn)行異常點檢測，每條記錄包含6個屬性。通過計算每個屬性的μ值，最終選擇了μ值最大的兩個屬性即交易量與交易金額。經(jīng)篩選后的數(shù)據(jù)集如表2所示。

表2 篩選后的部分?jǐn)?shù)據(jù)集

實驗中所用的距離度量是選取q=2時的明考斯基距離進(jìn)行計算，當(dāng)k=30時，距離和矩陣P為：

由矩陣P可計算出100個φ值，對φ值進(jìn)行降序排列，設(shè)用戶期望的異常值為4，則可得到四個異常點，如表3所示。

表3 異常點檢測結(jié)果

從輸出的結(jié)果來看，求得的數(shù)據(jù)點的距離之和按降序排列，則可取前四條記錄，即序號為6,35,100,61的數(shù)據(jù)與其他點距離之和最大，可判定為異常數(shù)據(jù)。

如圖2所示，實驗將數(shù)據(jù)量增加至200,500。并分別對兩種算法檢測出的異常點個數(shù)進(jìn)行了對比。傳統(tǒng)基于距離和算法的檢測效果不理想，準(zhǔn)確率約為70%；而基于改進(jìn)距離和的異常點檢測算法的準(zhǔn)確率可以達(dá)到90%以上，取得了較好的檢測效果。

圖2 算法檢測結(jié)果對比

4 結(jié)束語

介紹了幾種基于距離的異常點檢測算法和幾種常用的距離度量，給出了一種選擇檢測屬性的方法，提出了一種改進(jìn)的基于距離和的異常點檢測算法。該算法舍去了傳統(tǒng)算法中對DB(p,d)參數(shù)的設(shè)置，避免了因參數(shù)不合適而產(chǎn)生參差不齊的結(jié)果，并給出了數(shù)據(jù)的異常程度，能夠更直觀地呈現(xiàn)出來。與傳統(tǒng)基于距離和的檢測算法進(jìn)行了比較，證明了該算法在分布不均勻的數(shù)據(jù)集上有較好的檢測效果。現(xiàn)階段異常點檢測技術(shù)的難點在于對高維數(shù)據(jù)的處理方法，因此基于改進(jìn)距離和的異常點檢測算法在高維數(shù)據(jù)上的應(yīng)用還有待于進(jìn)一步研究。