一種基于目標函數的局部離群點檢測方法

周 玉, 朱文豪, 孫紅玉

(華北水利水電大學 電力學院，河南 鄭州 450011)

離群點是偏離大部分數據較遠的點，它常被懷疑由不同的機制產生[1].根據數據對象的數量可以分為單獨離群點和集體離群點；根據數據類型可以分為矢量離群點、序列離群點、軌跡離群點和圖形離群點等[2].離群點檢測在數據處理中占有重要地位，它旨在找出數據集中的偏遠數據，是當下研究的熱點.其在欺詐檢測[3]、入侵檢測[4]、公共安全[5]、圖像處理[6]和目標跟蹤[7]等方面已經有了廣泛應用，其檢測方法大致為基于統計、基于距離、基于密度和基于聚類等方法[8-9].

Breuing等提出了局部離群因子的概念LOF(local outlier factor)[10-11]，這種方法基于密度給離群點賦予了離群因子，定量地描述了離群點的離群程度，其不再將離群點看作一個二值屬性.在沒有明確數據分布的情況下依然能準確發現離群點，由于其需要逐個查找數據點的鄰域，計算數據點的離群因子，這就使得此方法的計算量巨大.隨后，在此基礎上出現了很多改進的方法，例如文獻[12]提出的NLOF(new LOF)算法,通過聚類算法DBSCAN(density-based spatial clustering of applications with noise)對數據集進行剪枝處理，得到初步的異常數據集，然后利用LOF算法計算初步異常數據集中對象的局部異常程度，提高了離群點檢測精度.但此算法中DBSCAN聚類需要人為輸入的參數過多且敏感度較大，面對未知數據集時，在參數設置方面存在較大問題.同樣，文獻[13]也提出了類似的用DBSCAN對數據集進行預處理的檢測方法，這種方法分為兩個階段.第一階段，為了減少參數輸入，用k近鄰的個數代替Minpts并通過k近鄰確定聚類半徑，通過改進的DBSCAN對混合數據進行初步篩選，一定程度減小了計算量；然后利用新構造的LAOF(LOF based on the area density)計算篩選后數據的離群程度，為了表征不同屬性的貢獻度，在距離度量中采用除一化信息熵差對屬性加權，并在第二階段進行二次權重確定，提高了檢測精度，但這種方法和NLOF存在同樣的問題.文獻[14]使用EWT(empirical wavelet transform)方法對原始熱工過程時間序列的運行趨勢進行去除后，使用LOF算法得到該序列中的異常值點，避免了判斷閾值不易直接給出的問題，在動態和穩態過程中均具有適用性，但是，k距離和箱型圖截斷點系數β的選擇對結果的敏感度較大，并且此方法只適用于一維數據的檢測.文獻[15]從定義出發，提出基于聚類的局部離群點的概念，解釋了局部的定義，即小聚類在宏觀上可以看作離它最近的大聚類的局部，給出倍數β作為大小聚類的判別.通過新的局部概念，提出了CBLOF(cluster-based local outlier factor)的計算公式，計算得到每一個數據點的局部離群因子來表征離群程度，但這種方法對數據集并未進行預處理，計算復雜度十分高，面對大規模數據集不具備處理能力且用參數β來判別大小聚類并不精確.

針對上述問題，本文提出了一種新的基于目標函數的局部離群點檢測方法.①在進行檢測之前，對數據集進行預處理，由于使用FCM(fuzzy C-means)，為了有較好的聚類效果，因此使用肘部法則確定最佳聚類個數；②FCM的目標函數是根據距離求和的，拿走一個點，它的值必然會減小，而拿走離聚類中心較遠的點，它的值減小幅度就會更大，通過減小的幅度來大概判斷一個點的離群可能性，將大部分正常數據去除，剪枝得到初步的離群點集，這是本文最大的貢獻，相比于其他剪枝方法更精確；③每一維特征對數據集的貢獻度不同，采用屬性熵來表征每一維特征的離散程度，熵越大，離散程度越大，此維特征所占的權值越大，用傳統的LOF方法得出每一維的異常值得分，加權得到每個數據最終的異常得分，將其順序排列，值越大的離群程度越大.經過實驗對比驗證，結果顯示該方法能提高檢測精度，改善聚類效果，實現有效的離群點檢測.

1 預備知識

1.1 FCM算法

FCM算法屬于劃分聚類算法，聚類之后相同簇對象之間相似度最大，不同簇對象之間相似度最小是FCM的主要思想[16].FCM已成為聚類分析的主流[17]，其在圖像處理[18]、海水深度預測[19]、故障診斷[20]等方面有廣泛應用.

設有樣本集X={x1，x2，…，xn}，c為聚類中心個數，m為模糊權重指數，隸屬度為uij(i=1，2，…，c；j=1，2,…，n).其中uij∈[0,1]，聚類中心為V={V1，V2，…,Vc}，算法目標函數為

(1)

步驟1 參數初始化，輸入聚類中心個數c(2≤c≤n)，停止閾值ε，模糊權重指數m，選取初始聚類中心.V(b)={V1，V2，…，Vc}，迭代計數器b=0.

步驟2 用式(2)計算并更新劃分矩陣U(b):

(2)

步驟3 用式(3)更新聚類中心矩陣V(b+1):

(3)

步驟4 如果‖V(b)-V(b+1)‖<ε，則聚類停止，輸出U和V，否則b=b+1，轉向步驟2.該算法迭代終止后，數據對象的模糊劃分由模糊隸屬度矩陣U體現.

1.2 局部離群點檢測算法LOF

LOF算法用離群因子定量地描述每一個數據對象的離群程度，其沒有全局計算數據點的密度，而是通過k鄰域計算得到數據點的局部可達密度，因此其中表征離群程度的量被稱為 “局部”異常因子[21].傳統LOF算法需要明確以下幾個定義.

1)d(p,o):點p與點o之間的距離.

2)第k距離(k-distance):p的第k距離為p到其周圍第k遠的點的距離，但不包括p.

3)第k距離鄰域(k-distance neighborhood ofp):與點p的距離不超過其第k距離的所有點，包括第k距離上的點所組成的點集為p的第k距離鄰域Nk(p).因此p的第k鄰域點的個數Nk(p)≥k.

4)可達距離(reach-distance):點o到點p的第k可達距離為

reach-distancek(p,o)=max{k-distance(o),d(p,o)}.

(4)

即點o到點p的第k可達距離為o的第k距離和op間真實距離的最大值.

5)局部可達密度(local reachability density):點p的局部可達密度表示為

(5)

6)局部離群因子(local outlier factor):點p的局部離群因子表示為

(6)

LOF檢測算法有較大的缺點，它需要計算每一個數據的離群因子，包括數據集中的正常數據，因此產生了很多無效計算，增加了計算量，并且其對未知數據集檢測效果一般，直接用其進行離群點檢測不可取.因此，本文提出了一種基于目標函數的局部離群點檢測方法，用于改進傳統LOF檢測算法的性能.

1.3 肘部法則

聚類算法對聚類個數c的選取將直接影響算法的聚類效果.肘部法則將不同c值的成本函數值刻畫出來，每個簇包含的樣本數會隨著c值的增大而減少，樣本會更靠近其聚類中心，代價函數(式(7))隨之減小.但隨著c繼續增大，代價函數的減小幅度不斷下降，直至代價函數曲線趨于平穩.在c值增大過程中，代價函數減小幅度最大的位置就是肘部，使用這個c值一般可以取得很好的效果.

定義代價函數：

(7)

其中:c是聚類個數;N(i)是第i簇中的數據個數;Ci為第i個聚類中心.

2 基于目標函數的局部離群點檢測方法

2.1 基于FCM目標函數的剪枝算法

在1.1和文獻[22]的基礎上，提出了一種新的剪枝方法，即基于FCM目標函數的剪枝算法.首先，執行FCM算法，生成一個目標函數和幾個簇；然后，將數據個數少于簇平均個數的小簇視為離群簇，將其加入離群候選集；由式(1)得知，從數據集中移除某個點，必然會導致目標函數的減小，若移除的點偏離正常數據較遠，也就是離群程度較高的話，目標函數值的減小程度會更大，由此判斷數據的離群程度.

基于FCM目標函數的剪枝算法推導過程：

令式(1)中的xj-Vi=dij，表示第j個點到第i個聚類中心的距離，n表示數據集D的樣本個數，若移除數據集D中的某個點，樣本個數變為n-1，且某個點的移除對整個數據集的聚類中心幾乎不產生影響，此時，FCM的目標函數變為

(8)

對比公式(1)，只要移除數據集中的點，J0(u,c)

假設:

(9)

(10)

由于:

Δ∑dij(outlier)?Δ∑dij(normal).

(11)

則

J1(u,c)?J2(u,c).

(12)

即

J-J1(u,c)?J-J2(u,c).

(13)

令:

(14)

則

ΔJ(outlier)?ΔJ(normal).

(15)

即移除的點如果離群程度較大，其目標函數減少量會比正常數據大得多，運用此規律對數據集進行初步離群點篩選.

算法1 基于目標函數值剪枝算法.

輸入：數據集D；

輸出：離群候選集D0.

步驟1 對完整的數據集執行FCM算法，得到OF，并將小簇放入離群候選集；

步驟2 逐次移除剩余的點，得到所有的OFi，計算得到每一個DOFi和平均減少量AvgDOF；

步驟3 比較DOFi和T(AvgDOF)，若DOF>T(AvgDOF)，則將第i個點放入離群候選集.

2.2 加權LOF算法

信息熵常被用于表征數據的離散程度，熵值越大代表變量的離散程度越大，其提供的信息越少；熵值越小代表變量的離散程度越小，其提供的信息越多.因此數據不同維的特征提供的信息量不同，需要相應賦予不同的權值.對于熵大的屬性，所占權重應該較高，這樣可以將其離散程度更明顯地體現出來.

算法2 加權LOF算法.

輸入:數據集D；

輸出:權值集合W={ω1，ω2，…，ωm}，每個數據的異常值得分LOFi.

步驟1 對數據集D執行Z-score標準化得到D′，通過式(16)計算得到數據集D′中第i個數據的第j維屬性的比重Pij：

(16)

步驟2 用式(17)計算數據集D′中第j維屬性的信息熵Ej：

(17)

其中，p=1/lnn；

步驟3 用式(18)計算第j維屬性的權值ωj：

(18)

步驟4 利用熵權法對每一維屬性賦權之后，再對每一維屬性單獨執行傳統LOF算法，根據式(19)對其加權，獲取最終的LOF值作為整體數據的異常得分.

(19)

式中，LOFij表示第i個數據的第j維度LOF值.

2.3 基于目標函數的局部離群點檢測算法描述

算法3 基于目標函數的局部離群點檢測算法.

輸入:數據集D，鄰域查詢個數k，剪枝閾值T，離群點個數p；

輸出:Topp個離群點.

步驟1 運用肘部法則確定數據集D的最佳聚類個數c；

步驟2 輸入參數c，使用FCM算法對數據集D聚類，列出每一個數據移除后的目標函數值變化量并進行對比，依據剪枝閾值T(AvgDOFi)，對數據集D剪枝得到離群候選集D0；

步驟3 在離群候選集D0中，利用式(16)～式(18)對每一維屬性進行加權，之后用式(19)計算得到每一個數據的異常值得分LOF；

步驟4 將每個數據的LOF值按從大到小的順序排列，輸出前p個數據對象，組成數據集D的離群點集合.

傳統的LOF算法在面對未知數據集，即不知道其數據分布，聚類個數等特征時檢測效果十分不理想，并且由于其必須計算每一個數據點的離群程度，這又導致算法的計算量大大增加，FOLOF算法在這兩方面做出了一定的改進.

3 實驗對比

在人工數據集和UCI數據庫中選取Iris，Wine，Yeast和User Knowledge Modeling四個數據集，從聚類效果(CH指數，Dunn指數，I指數，S指數)[23]、準確度、誤檢率[24]等方面來驗證所提出算法的可行性.前面部分提到的所有參數在下面實驗中統一設置，剪枝時用到的閾值T取1，LOF算法和FOLOF算法中的鄰域個數k取5.

3.1 人工數據集

為了可視化離群點檢測的整個過程，首先利用人工數據集Dataset1來進行實驗.該數據集共有70個數據點，包含10個離群點，分別是第6，7，19，30，40，45，52，58，69，70等點，如圖1所示.先使用肘部法則確定最佳聚類個數，再剪枝得到離群候選集，運行加權LOF算法，將得出的離群值順序排列.

圖1 Dataset1數據集

如圖2所示，當聚類個數從3變到4時，代價函數逐漸趨于平緩，所以最佳聚類個數c為3，運行剪枝算法，得到OF的值為568.317，Avg(DOFi)的值為8.431，將每一個DOFi都列于表1中，圖3為移除第i個點后的目標函數值圖，圖4為移除第i個點后的目標函數值變化量針狀圖，與Avg(DOFi)進行對比，最終剪枝剩下第6，7，8，19，30，40，45，52，58，60，69，70等12個點將其放入離群候選集，候選集中包含所有離群點，剪枝精度為100%，運行加權LOF算法，將各點離群因子列于表2中，輸出離群值最大的前10個點，分別為第8，58，69，60，6，7，52，30，19，40等10個點，其中有8個為真實離群點，移除所檢測出來的離群點后，重新對數據集進行聚類，聚類效果提升，如表3所示.

表2 Dataset1離群候選集中各點離群因子(降序排列)

表3 Dataset1聚類指標對比

圖4 移除第i個點后的目標函數值變化量

表1 目標函數值減少量對比

圖2 代價函數衰減

圖3 移除第i個點后的目標函數值

為了評估離群點檢測的性能，采用準確度(precision，Pr)和誤檢率(noise factor，Nf)兩個指標，分別用Pr和Nf表示.用TP表示算法檢測到的真實離群點數量，用FP表示算法錯將真實數據檢測為離群點的數量，則

(20)

其中，Pr和Nf的最大值取1，最小值取0，Pr的取值越大，Nf的取值越小，算法性能越好.對于Dataset1的檢測結果來說，TP=8，FP=2，計算得到，Pr=0.8，Nf=0.2，效果很好.

3.2 UCI數據集

通過對比本文算法和LOF離群點檢測算法在實際數據集中的運行結果來驗證本文算法的性能，實驗數據集如表4所示.

表4 實驗數據統計

對每個數據集運行肘部法則確定最佳聚類個數，分別是3，3，10，4，最佳聚類個數與實際分類個數基本一致，提出的方法對未知數據集具有可行性.

Iris數據集選取前兩類數據作為正常數據，第三類中取10個數據作為離群數據.選取Wine數據集的前兩類共130個數據點作為正常數據，第三類中隨機選取8個數據作為離群數據.對于Yeast數據集，沒有必要用到全部數據，選取CYT，NUC和MIT三個大類共1 136個數據作為正常數據，選取POX類共20個數據作為離群數據，另外，由于其第6維屬性含有0值，在運行屬性賦權算法計算比重時，不允許有0值的存在，則刪除第6維屬性，剩下其余7維屬性進行離群點檢測.對于UKM數據集，由于very_low中含有0值，則選取High，Middle兩類共224個數據做為正常數據，Low中隨機選取5個數據作為離群數據.

由剪枝精度，即剪枝后得到的離群候選集中真實離群點數量與整個數據集中的離群點數量的比值與剪枝后剩余數據量對比，結果證明FCM剪枝方法相比于DBSCAN剪枝方法、PMLDOF剪枝[25]方法具有比較明顯的優勢，如表5和表6所示.

表5 剪枝精度對比

表6 剪枝后剩余數據量對比

通過對比檢測結果和移除所檢測出的離群點之后的聚類效果，證明所提出的方法相比于LOF算法具有優勢，實驗結果如表7和表8所示，運行時間為t，單位s.算法采用MatlabR2016a編寫，實驗環境為：酷睿i5 2.90 GHz CPU，8.00 GB內存，Windows7操作系統.

表7 四種數據集檢測結果對比

表8 四種數據集去除離群點前后聚類效果對比

經過仿真實驗驗證，本文提出的算法對未知數據集具有一定的處理能力，與傳統的LOF算法相比在檢測結果方面有明顯提升.去除所檢測出來的離群點后，重新對數據集聚類，聚類效果有明顯改善，在進行檢測之前先通過FCM進行了數據剪枝，減少了很大一部分計算量，相比于LOF算法，運行時間明顯減少.

3.3 分析討論

1)FOLOF算法通過肘部法則確定數據集的最佳聚類個數以達到最好的聚類效果，這使得其在面對未知數據集時具備更好的處理能力，而LOF算法在面對所有數據集時的處理方法全部一致即逐個計算離群因子，對不同的數據集缺乏針對性.

2)FOLOF算法通過FCM的目標函數變化量對數據集進行剪枝，得到初步的離群點集，這就在數據量方面大大降低了計算復雜度，而LOF算法并未對數據集進行預處理，會導致較大的計算量和較長的運行時間.

3)在輸入參數方面，FOLOF算法只需要人為輸入鄰域查詢個數k，剪枝閾值T和需要輸出的離群點個數p，并且這些參數的設定不需要經過繁瑣的實驗過程，一般都采用經驗值就能得到不錯的檢測效果.

4)在檢測精度方面，FOLOF算法的檢測精度高于LOF算法，其綜合檢測性能得到了提高.

4 結 語

本文提出一種基于目標函數的離群點檢測方法FOLOF，首先，根據肘部法則確定最佳聚類個數；然后，利用目標函數對數據集進行剪枝；最后，采用加權LOF算法確定數據點的離群程度.相比于傳統的LOF離群點檢測算法，本文所提的方法在檢測精度、檢測效果以及檢測速度等方面的性能均有明顯提升.然而，該方法還需要在以下2個方面進行深入研究：閾值T的敏感度分析以及基于閾值T的離群點分類的研究，即研究出相應的方法實現強弱離群點的辨別；在FCM算法之外，其他聚類算法的目標函數是否可以用于剪枝及對剪枝結果有何種影響.