基于方形鄰域和裁剪因子的離群點檢測方法

涂曉敏，石鴻雁

(沈陽工業大學，沈陽110870)

1 引 言

離群點檢測是數據挖掘領域中的一項重要挖掘技術，主要目的是消除數據中存在的噪音或者挖掘出潛在的、有意義的知識[1-3].目前，離群點檢測廣泛地運用于諸多領域，如醫療處理、公共安全、圖像處理、視頻網絡監視和入侵檢測[4-6]等，具有良好的應用前景.

迄今為止，在離群點檢測研究方面已經取得了一些成果，其中基于密度的離群點檢測算法是最為著名和實用的方法.Breuing等[7]提出了局部離群因子算法(LOF)，借助于可達距離、可達密度和局部離群因子來判斷離群點，使得對離群點的檢測不再是二元結果.在數據分布異常情況下，計算數據對象與其鄰域內數據對象的距離時，導致時間開銷很大，且檢測精度通常受給定參數的影響.Malik[8，9]提出了局部稀疏系數算法(LSC)和改進的局部稀疏系數算法(ELSC)，省去了LOF算法中可達距離、可達密度的計算，并引入裁剪系數的概念，并用局部稀疏系數代替局部離群因子表示對象的離群度，降低了計算的復雜度，但在剪枝過程中易導致部分正常點的誤判.賈晨科等人[10]提出了局部孤立系數算法(LOC)，改進了LSC算法中局部稀疏率和局部稀疏系數的計算，并從數據集中選出具有最大局部孤立系數值的前n個對象作為孤立點，提高了檢測效率.周云峰[11]提出了一種新的高維空間中離群點檢測算法(NELSC)，在ELSC算法的基礎上采用DBSCAN[12-14]聚類的方法對數據集進行預處理，去除屬性權值低于閾值的對象，在預處理時算法對參數的敏感度較大.黃添強等[15]提出了基于方形鄰域的離群點查找新方法(ODBSN)，吸收DBSCAN算法和基于網格[16]算法的優點，將鄰域改為方形鄰域并只對有數據分布的空間進行劃分，克服了“維災”問題，但在計算局部偏離指數時容易導致正常點的丟失.

由于基于密度的算法計算時間復雜度較高，并只適用于一定規模的數據集，在遇到大規模數據集時通常查準率較低.因此，本文在ELSC算法的基礎上，提出了方形鄰域和裁剪因子相結合的方法，采用方形鄰域，減少鄰域查詢次數，可以快速找到候選離群點，降低了時間復雜度.引入新定義的裁剪因子進行候選離群點的精選，發現更多有意義的離群點，提高了算法的準確度.

2 ELSC算法

ELSC算法通常用來減少數據集的規模，不再計算所有數據點的離群程度，主要分為初選和精選兩階段進行，其思想是：

1)吸取基于密度算法的思想，根據鄰域內數據對象的稠密程度，得到作為候選集的前提條件.

2)采用裁剪系數將不可能是異常點的數據對象進行修剪，剩余的對象構成候選集合.

3)對候選集中每個數據對象依次計算局部稀疏系數，并與閾值進行比較，確定最終的異常點.

ELSC算法中，在縮小了待測數據個數的同時，也存在不足之處：

1)有效性.對大規模數據集而言，異常點僅占數據集的很小部分，即便采用裁剪系數的方法，也只能排除一小部分數據對象，導致算法的精確度低.

2)執行效率.由于每個點在鄰域查詢時，都需掃描整個數據庫，限制其在海量數據集中的應用.在計算鄰域距離的過程中，數據對象之間需互相比較，對有n個數據的對象，則比較次數為(n/2)·(n-1)，對于一個K維的數據集，時間復雜度為O(Kn2)，離群點排序的時間復雜度為O(nlogn)，計算裁剪系數的時間復雜度為O(n)，因此算法的整體時間復雜度為：O(Kn2)+O(n)+O(nlogn).盡管采用R樹等索引技術來提高查詢效率，并不能從根本上解決問題；另一方面，當數據集維數較高時，R樹等索引結構比順序遍歷的效果更差，無法提高算法的效率.

3 改進算法概念及主要思想

為了便于描述、直觀理解，下文以二維空間為例進行介紹，這里一個點表示一個數據對象，故點與數據對象不再加以區分.

3.1 算法相關概念

給定一個二維數據庫D，實參數e(方形鄰域的邊長).

定義1. 以p(x,y)為中心，e為邊長的方形區域內的對象集合，稱為p的方形鄰域[17]，記作SSNeps(p)，即

{p′(x′，y′)∈D‖x′-x|≤e/2，|y′-y|≤e/2}

定義2. 與方形鄰域S相鄰的其他8個方形鄰域的集合，稱為鄰近方形鄰域[18]，記作Ne(S).如圖1所示.

Ne(S)={S1，S2，S3，S4，S5，S6，S7，S8}

圖1 鄰近方形鄰域示意圖Fig.1 Adjacent square neighborhood diagram

定義3. 對象p的局部稀疏率lsr(p)

(1)

該式表示了數據對象鄰域內大致的稠密程度，此處的距離為兩個點之間的歐氏距離.

定義4. 對象p的裁剪因子PF

(2)

該式表明了整個數據集的平均密度.根據裁剪因子的值，將局部稀疏率明顯小于裁剪因子的數據對象加入到候選集中.

定義5. 對象p的局部稀疏指數LSI(p)

(3)

從局部稀疏指數計算公式可知，若點p的鄰域內數據對象的局部稀疏率平均值越大，而p的局部稀疏率越小，則LSI(p)取值將越大，若其值大于某個閾值T(T為大于1的值)，那么將點p記為離群點.

3.2 算法思想

為了降低時間復雜度和提高檢測精度，本文將方形鄰域和裁剪因子結合在一起，算法分為粗選和精選兩個階段，其主要思想如下：

1)粗選階段：算法首先任選一個點，計算其方形鄰域.若方形鄰域內的點數大于鄰域中鄰居個數的閾值，則此方形鄰域內的所有點為聚類點；否則方形鄰域內的所有點為候選離群點.然后在該方形鄰域周圍任選一個方形鄰域進行類似的操作，直到該方形鄰域及其鄰近的八個方形鄰域中的所有數據點全部處理完畢.接著再任意選取一個尚未訪問的數據點開始，重復上述操作，直至把所有的點劃分為聚類點和候選離群點為止.

2)精選階段：采用改進的裁剪因子對候選集中的對象進行篩選，再通過新定義的局部稀疏指數計算得到最終的離群點.

3.3 算法實施步驟

輸入：數據集D，方形鄰域邊長e，鄰居個數閾值MinP，鄰域k，閾值T

輸出：數據集D的離群點

I粗選階段：

a)采用方形鄰域的方法將數據集分為了聚類點和候選離群點并分別標記.

II 精選階段：

b)根據公式(1)，計算候選離群點集中每個數據對象的局部稀疏率.

c)根據公式(2)，計算候選離群點集中每個數據對象的裁剪因子，并與局部稀疏率進行比較，得到最終的離群數據集.

d)根據公式(3)，計算最終離群數據集中數據對象的局部稀疏指數.

e)將局部稀疏指數大于離群因子閾值T的點判斷為離群點.

3.4 時間復雜度

算法在鄰域查詢時最為消耗時間，一般情況下，鄰域查詢操作的時間復雜度為O(n)，若采用空間索引技術，可以將復雜度降為O(logn).本文算法在粗選階段用方形鄰域對空間進行分割，精選階段對候選異常點進行k近鄰查詢，以求得裁剪因子PF.當數據集有n個對象，密集的方形鄰域有m個，候選離群點個數為h(h<

4 實驗分析

為了檢驗算法的性能，將本文算法與LOF算法、ELSC算法進行比較.其中實驗選取了聚類基準數據集中的兩個數據集并向其添加一定量的離群點(如表1)和隨機生成服從正態分布的數據集，所有算法均在Matlab R2016a中實現，操作系統為Win7 Inter?CoreCPU 3.40GHz.

表1 數據集信息描述Table 1 Information description of dataset

4.1 實驗有效性

為了檢驗算法的有效性，對R15數據集進行實驗，它包含15個簇與20個離群點，圖2為在參數k取不同值時，LOF算法、ELSC算法、本文算法的對比圖.算法的準確率是采用幾組數據的均值，從圖中可以看出，本文的算法一直高于LOF算法、ELSC算法.因此，算法具有可行性.

圖2 不同算法的精度對比Fig.2 Accuracy comparison of different algorithms

如圖3為算法對R15數據集在粗選階段劃分的方形鄰域.

圖3 算法粗選階段的方形鄰域劃分Fig.3 Square neighborhood partitioning in rough selection stage of algorithm

4.2 算法執行效率

為了驗證算法的執行效率，實驗采用隨機數發生器產生服從正態分布的具有不同密度的聚類數據集，數據集大小從3000到30000不等.本文算法參數e=20，MinP=8，T=1.1，LOF算法中MinP=10，ELSC算法中k=80.由圖4可知，本文算法的執行效率明顯高于LOF算法、ELSC算法，雖然對象個數有所增加，但是算法的執行時間增幅不明顯，故具有很好的可伸縮性.

圖4 不同算法的執行時間對比Fig.4 Execution times of different algorithms

用Aggregation數據集進行鄰域查詢次數與邊長e之間關系的實驗，如圖5所示，LOF算法、ELSC算法需對每個數據對象進行鄰域查詢，所以呈直線形.而本算法因為采用了方形鄰域的方法，所以查詢次數隨著方形鄰域邊長e的增加而逐漸減少，并且比LOF算法、ELSC算法成倍地減少了鄰域查詢次數.

圖5 鄰域查詢次數與邊長e之間的關系Fig.5 Relationship between the number of neighborhood queries and side length e

5 結束語

本文研究了基于密度的離群點檢測算法的不足，提出了一種基于方形鄰域和裁剪因子的離群點檢測算法.該算法不再對所有的點進行離群度檢測，而是通過采用方形鄰域的方法，快速排除密集鄰域部分，再利用裁剪因子對候選離群點集中的對象進一步篩選，排除被誤判的點，最后通過局部稀疏指數確定對象是否為離群點.實驗結果表明，算法能有效的識別離群點，并在執行效率上有明顯的優勢.但是本文的研究工作仍需繼續進行，未來將該算法推廣到動態數據集中.