基于網(wǎng)格山脊點的異常點檢測?

戴 楠 嚴 悍 卓勤政 馬玲玲

（南京理工大學計算機科學與技術學院 南京 210094）

1 引言

隨著信息技術的快速發(fā)展，各個領域內已經(jīng)積累了大量的復雜數(shù)據(jù)，并且數(shù)據(jù)的規(guī)模也是成爆炸式的增長。收集和檢測出有價值的信息是目前數(shù)據(jù)處理的一個重要的模塊。數(shù)據(jù)集的異常點檢測是數(shù)據(jù)挖掘領域內一個舉足輕重的研究方向，它的目的在于消除數(shù)據(jù)內的噪音或者是挖掘出有價值的知識。Hawkins的定義［1］揭示了異常點的本質:“異常點的表現(xiàn)與其他點如此不同，不禁讓人懷疑它是由不同機制產(chǎn)生的”。目前，異常點檢測已經(jīng)在電子商務詐騙、信用卡欺詐、網(wǎng)絡入侵檢測分析等鄰域得到了廣泛應用。現(xiàn)有的離群點檢測方法大致包括:1）基于深度的方法［2］；2）基于分布的方法［3］；3）基于密度的方法［4］；4）基于距離的方法［5］。目前數(shù)據(jù)集的異常點檢測中比較常用的算法是基于密度的局部離群點檢測算法LOF［4］。

2 關于GridLOF算法的研究

由于LOF算法需要計算數(shù)據(jù)集中各個點之間的距離，所以其時間復雜度非常高，耗費的時間也非常大。為了解決上述問題，提出了將網(wǎng)格的聚類算法和LOF算法集合起來，提出了一個GridLOF算法。GridLOF算法首先利用網(wǎng)格方法將數(shù)據(jù)集中部分的聚類數(shù)據(jù)點去除。僅僅考慮處于邊界網(wǎng)格的數(shù)據(jù)點。計算它們的LOF值。這樣就可以減少算法運算時間。

GridLOF算法尋找邊界網(wǎng)格時，僅僅是粗略的對空間內數(shù)據(jù)集進行劃分，采用網(wǎng)格內部所包含的點作為該區(qū)域的密度，并沒有考慮到空間內一定鄰域內點間的相互間的影響。因此GridLOF算法選取的邊界網(wǎng)格的數(shù)據(jù)的往往包涵大量正常點并且受網(wǎng)格寬度的影響，增加了不必要的計算量。

本文借鑒了GridLOF算法中利用網(wǎng)格對數(shù)據(jù)點進行分類［6］的思想。提出一種基于網(wǎng)格山脊點的LOF算法。該方法能更準確、快速地找到邊界網(wǎng)格中的數(shù)據(jù)點，并且降低了網(wǎng)格寬度對邊界網(wǎng)格區(qū)域選取的影響，有效地降低了LOF算法的復雜度。

3 相關概念

定義1網(wǎng)格單元［7～9］:給定一個d維的數(shù)據(jù)集，其屬性（A1，A2，…，Ad）都是有界的，將數(shù)據(jù)第i維劃分成ni個小段，由第i維劃分的小段組成的集合記為Si，那么數(shù)據(jù)空間被笛卡爾集（s1*s2*s3…*sd）劃分為s1*s2*s3…*sd個網(wǎng)格單元。用每一小段在該維上的位置構成的d維向量來唯一標識這個網(wǎng)格單元。例如，網(wǎng)格單元u可記為（u1，u2，u3，…ud）。

定義2網(wǎng)格山脊點:指在空間內各個相鄰網(wǎng)格間的交點且網(wǎng)格山脊點高度大于0。如圖1在二維空間內點A就是網(wǎng)格P，N，Q，M四個網(wǎng)格的交點。即空間內一個網(wǎng)格山脊點。

定義3網(wǎng)格山脊點的高度:在一個i維空間內，一個單元網(wǎng)格的相鄰的網(wǎng)格山脊點有2i個，記作并且單元網(wǎng)格空間內一點a到該網(wǎng)格山脊點p的距離為dis[ap]，因此點a到所有網(wǎng)格山脊點的最后每個點映射到網(wǎng)格山脊點的高度為

如圖1所示在二維空間內，單元網(wǎng)格M的四個相 鄰 的 網(wǎng) 格 山 脊 點 A（xa，ya），B(xb，yb) ，C(xc，yc)，D(xd，yd)，且網(wǎng)格單元內一點 a(x，y)。該點映射網(wǎng)格相鄰點的高度為

定義4網(wǎng)格山脊相鄰點:指的是與該網(wǎng)格山脊點相聚只有一個網(wǎng)格單元長度的網(wǎng)格山脊點。圖1中網(wǎng)格山脊點A的相鄰點有網(wǎng)格山脊點B，C，E，F(xiàn)。

定義5山脊點鄰域:指的是與網(wǎng)格山脊點［10～12］相接壤的網(wǎng)格單元所構成的區(qū)域。在圖1中山脊點A的鄰域為網(wǎng)格單元P，N，Q，M組成的區(qū)域。

圖1 某區(qū)域網(wǎng)格劃分圖

4 基于網(wǎng)格山脊點的異常點檢測算法

4.1 算法思想

該算法的基本思想主要是:對任意空間分布的數(shù)據(jù)集［13］，每一維度上取較小的且相同的網(wǎng)格單元長度，將空間劃分為網(wǎng)格單元空間。遍歷所有數(shù)據(jù)集中的點，將點劃分到所有的網(wǎng)格單元中，計算出所有網(wǎng)格山脊點的高度，和每個網(wǎng)格山脊點對應的鄰域。根據(jù)網(wǎng)格山脊點的高度對網(wǎng)格山脊點進行升序排序。取前某閾值的網(wǎng)格山脊點鄰域中所包涵的所有數(shù)據(jù)集點作為LOF算法要檢測數(shù)據(jù)測試點。最后采用LOF計算出數(shù)據(jù)測試點的異常程度值。

4.2 算法描述

輸入:數(shù)據(jù)集D，較小的網(wǎng)格單元長度m，閾值p；輸出:數(shù)據(jù)集D中測試點的異常程度值

基于網(wǎng)格山脊點的異常點檢測算法描述:

步驟1：對任意空間數(shù)據(jù)集按照網(wǎng)格單元長度m進行劃分。

步驟2：依據(jù)網(wǎng)格山脊點高度定義，計算出每個網(wǎng)格山脊點的高度和每一個網(wǎng)格山脊點所對應的鄰域。然后基于網(wǎng)格山脊點高度，對網(wǎng)格山脊點進行升序排序，小于閾值p所對應的網(wǎng)格山脊點鄰域所包涵的數(shù)據(jù)點為測試點。

步驟3：對選取出的測試點采用基于密度LOF算法來計算其異常程度值。

5 實驗結果及分析

實驗環(huán)境:Window 10，處理器:Intel（R）Core（TM）i7-6500U CPU@2.5GHz 2.59GHz

為了驗證算法的可行性和精確度，筆者做了大量的實驗，在此僅僅舉一個具有代表性的給予具體說明。并與常用的LOF算法和GridLOF算法進行比較。

在現(xiàn)實數(shù)據(jù)集中，大部分數(shù)據(jù)是滿足正態(tài)分布，如圖2顯示的是在二維空間滿足某兩種不同正態(tài)分布的數(shù)據(jù)集且相互間存在關聯(lián)，數(shù)據(jù)集的規(guī)模是8000。

圖2 二維空間正態(tài)分布數(shù)據(jù)

采用常用的LOF算法［14］對圖2中二維正態(tài)分布的數(shù)據(jù)集進行檢測?，F(xiàn)實數(shù)據(jù)集中異常點的數(shù)量占非常小的一部分，所以本實驗中取異常程度排在前150的數(shù)據(jù)集點作為異常點處理。如圖3為異常點的分布圖。圖4所示異常點和正常點顯示，其中星型代表異常點，圓形為正常點。

圖3 LOF算法檢測出異常點

采用GridLOF和基于網(wǎng)格山脊點的異常值檢測算法對圖2二維正態(tài)分布數(shù)據(jù)集進行檢測。為了保證GridLOF算法和基于網(wǎng)格山脊點的異常點檢測算法的有效性，要求該兩種算法計算出的數(shù)據(jù)集的異常點與LOF算法計算的數(shù)據(jù)集異常點相同的數(shù)量要在140（總數(shù)150個異常點）以上才能算該算法有效。

圖4 LOF算法檢測異常和正常點結果

采用GridLoF算法和基于網(wǎng)格山脊點的異常點檢測算法對圖2所示數(shù)據(jù)集進行異常點檢測，在保證算法的有效。如圖5所示其在不同網(wǎng)格寬度情況下，所需取最少的數(shù)據(jù)測試點。圖6對應是下不同網(wǎng)格寬度情況下檢測相關數(shù)據(jù)點所需要的時間。在上方框型點構成的折線圖為GridLOF算法檢測結果。星型點構成的折線圖為采用基于網(wǎng)格山脊點異常點檢測算法檢測的結果。

圖5 不同網(wǎng)格情況下兩種算法取得測試點數(shù)

圖6 不同網(wǎng)格情況下，最優(yōu)解情況下的運行時間

根據(jù)實驗的情況可以了解到，在同等數(shù)據(jù)規(guī)模的情況下，采用基于網(wǎng)格山脊點的異常點檢測算法的效率明顯高于采用GridLOF算法，時間上的縮減也非常明顯。并且采用基于網(wǎng)格山脊點的異常點檢測算法對網(wǎng)格寬度變化的抗干擾性明顯強于GridLOF算法。所以在實際使用時，基于網(wǎng)格山脊點算法異常點檢測算法要優(yōu)于GridLOF算法。

6 結語

采用基于網(wǎng)格的異常點檢測方法［15］是數(shù)據(jù)檢測主要方法之一，具有效率高，檢測結果與輸入數(shù)據(jù)順序無關，可拓展性好的優(yōu)點。本文提出的基于網(wǎng)格山脊點的異常點檢測算法極大的降低了檢測算法的時間。能快速高效地定位數(shù)據(jù)集的邊緣區(qū)域，給LOF算法提供較精確的檢測區(qū)域來檢測異常點，從而極大減少了算法檢測的時間?；诰W(wǎng)格的異常點檢測方法是一種對GridLOF算法有效改進的方法。