基于網格山脊點的異常點檢測?

戴 楠 嚴 悍 卓勤政 馬玲玲

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

1 引言

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

2 關于GridLOF算法的研究

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

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

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

3 相關概念

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

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

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

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

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

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

圖1 某區域網格劃分圖

4 基于網格山脊點的異常點檢測算法

4.1 算法思想

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

4.2 算法描述

輸入:數據集D，較小的網格單元長度m，閾值p；輸出:數據集D中測試點的異常程度值

基于網格山脊點的異常點檢測算法描述:

步驟1：對任意空間數據集按照網格單元長度m進行劃分。

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

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

5 實驗結果及分析

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

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

在現實數據集中，大部分數據是滿足正態分布，如圖2顯示的是在二維空間滿足某兩種不同正態分布的數據集且相互間存在關聯，數據集的規模是8000。

圖2 二維空間正態分布數據

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

圖3 LOF算法檢測出異常點

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

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

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

圖5 不同網格情況下兩種算法取得測試點數

圖6 不同網格情況下，最優解情況下的運行時間

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

6 結語

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