基于改進(jìn)距離和的異常點(diǎn)檢測(cè)算法研究

李春生，于 澍，劉小剛

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

0 引 言

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

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

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

1 基于距離的異常點(diǎn)檢測(cè)

1.1 異常點(diǎn)檢測(cè)方法

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

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

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

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

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

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

1.2 距離的度量及異常點(diǎn)的定義

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

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

(1)

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

(2)

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

(3)

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

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

(4)

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

常見(jiàn)的基于距離的異常點(diǎn)定義有以下幾種：

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

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

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

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

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

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

表1 參數(shù)及意義

2.1 檢測(cè)屬性的選取

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

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

(5)

屬性的μ(ω)值越大，說(shuō)明該屬性值的波動(dòng)越大，檢測(cè)價(jià)值也越高，就越有可能成為被檢測(cè)的對(duì)象；μ(ω)值越小，該屬性值的波動(dòng)也越小，檢測(cè)價(jià)值也越低，就越有可能被忽略。

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

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

(6)

其中λk定義為：

(7)

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

圖1 不均勻分布的散點(diǎn)圖

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

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

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

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

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

對(duì)此算法的說(shuō)明如下：

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

3 實(shí)驗(yàn)設(shè)計(jì)

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

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

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

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

表3 異常點(diǎn)檢測(cè)結(jié)果

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

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

圖2 算法檢測(cè)結(jié)果對(duì)比

4 結(jié)束語(yǔ)

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