基于采樣的超球體聚類離群點檢測算法*

高榮芳，董振濤，夏海洋

(西安石油大學 計算機學院，陜西 西安 710065)

0 引 言

離群點檢測是數(shù)據(jù)檢測中的熱點研究方向之一，其目的主要是為了消除噪聲或發(fā)現(xiàn)潛在的且有價值的信息，是當今數(shù)據(jù)檢測領(lǐng)域一個重要的研究問題. 離群點檢測廣泛應用于金融交易、網(wǎng)絡(luò)安全、欺詐檢測和故障檢測等領(lǐng)域[1].

傳統(tǒng)的離群點檢測算法主要有基于分類的算法，如Liu B等人提出的基于SVDD的離群點檢測算法[2]，Yang J等人提出的自適應權(quán)重的One-class-svm的離群點檢測算法[3]，以及An W等人提出的改進SVDD的離群點檢測算法[4]等. 然而基于分類的離群點檢測算法只適合于低比例的離群點檢測任務，在處理高比例離群數(shù)據(jù)時算法精度較低. 由于聚類算法可以對相似點進行聚類的特點，使得聚類算法很容易被用到離群點檢測中，因此在近幾年，基于聚類的離群點檢測方法成為研究的熱點，如左進等人提出的基于K均值聚類的離群點檢測算法[5]，梅孝輝等人提出的基于DBSCAN聚類算法改進而來的LDBSCAN-CM離群點檢測算法[6]，Duan等人提出的基于OPTICS聚類的離群點檢測算法[7]，以及呂宗磊等人提出的快速超球體聚類離群點檢測算法[8]等. 基于聚類的離群點檢測算法對數(shù)據(jù)集的適用能力較強[9]，可以處理多分布數(shù)據(jù)集的離群點檢測問題[10]，使得其應用場景更加靈活. 然而，由于現(xiàn)有的基于聚類的離群點檢測算法不能給出數(shù)據(jù)點的離群程度，使其無法滿足特定領(lǐng)域的功能需求，例如故障檢測中對故障等級的確定，金融交易中一筆異常交易的可疑程度等，都需要對檢測對象做離群程度的等級劃分. 為了使快速超球體聚類算法能夠?qū)﹄x群點進行定量描述，提高離群點檢測的精度和召回率，本文提出了一種基于采樣的超球體聚類離群點檢測算法(Sampling-based Hyper-sphere Clustering Anomaly Detection Algorithm，簡稱SHCAD).

1 快速超球體聚類離群點檢測算法

快速超球體聚類離群點檢測算法(Fast Hyper-sphere Clustering Anomaly Detection Algorithm，簡稱FHCAD). FHCAD算法根據(jù)用戶自定義超球體密度閾值和連接度閾值來進行離群點檢測，其中超球體密度描述的是超球體內(nèi)的空間中數(shù)據(jù)點數(shù)量的多少，連接度描述的是兩個在空間中相交的超球體間的余弦距離. FHCAD算法的離群點檢測過程分為如下兩個步驟.

首先，F(xiàn)HCAD算法根據(jù)用戶自定義密度閾值，在數(shù)據(jù)集中隨機選擇一個數(shù)據(jù)點作為球心，不斷將周圍的數(shù)據(jù)點納入超球體中，并計算超球體的密度，當超球體的密度大于等于給定的密度閾值時，則完成一個超球體的聚類，并繼續(xù)對剩余的數(shù)據(jù)點進行超球體聚類，直到將滿足密度閾值的超球體全部聚類完成，不在任何一個超球體中的數(shù)據(jù)點被判定為離群點.

在聚類生成超球體后，F(xiàn)HCAD算法通過判斷兩個超球體之間的連接度，來進行超球體合并，如果其連接度大于給定的連接度閾值，說明兩個超球體的距離足夠接近，則這兩個超球體被合并為一類，最終未能被合并的超球體，其包含的數(shù)據(jù)點被判定為離群點.

FHCAD算法通過兩步計算，檢測數(shù)據(jù)中的離群點，具有較好的召回率，但其密度閾值和連接度閾值設(shè)置困難，應用受到限制，并且其在超球體聚類過程中容易將離群程度較低的數(shù)據(jù)點納入到超球體中，因此算法的精度較低.

2 SHCAD算法

2.1 相關(guān)概念和定義

假設(shè)原始數(shù)據(jù)集為X，其中的樣本個數(shù)為n，x(x∈X)表示數(shù)據(jù)集X中的一個數(shù)據(jù)點.

聚集度c(x)是用來描述超球體類中包含的所有數(shù)據(jù)點的聚集程度，如果一個超球體內(nèi)包含的數(shù)據(jù)點個數(shù)越多，則表明球心數(shù)據(jù)點的聚集度越大.

離群度s(x)描述的是一個數(shù)據(jù)點的離群程度，離群度越大則其為離群點的概率就越大.

定義1 假設(shè)在第k次數(shù)據(jù)劃分中，一個超球體類中包含w(1≤w≤p)個數(shù)據(jù)點，則其球心數(shù)據(jù)點x的聚集度為

ck(x)=w/p.

(1)

SHCAD算法對原始數(shù)據(jù)集X進行L次數(shù)據(jù)劃分，數(shù)據(jù)點x會產(chǎn)生L個聚集度，取均值作為最終的聚集度值，增強聚集度的魯棒性，其計算公式為

(2)

定義2 假設(shè)對原始數(shù)據(jù)集共進行L次數(shù)據(jù)劃分，則數(shù)據(jù)點x的離群度可表示為

s(x)=1-c(x).

(3)

2.2 算法思想

SHCAD算法的核心思想，就是通過多次數(shù)據(jù)劃分，在每次數(shù)據(jù)劃分中，通過數(shù)據(jù)采樣，多次計算空間數(shù)據(jù)點的聚集度，取均值得到魯棒性的聚集度，進而得到具有魯棒性的離群度，從而描述每個數(shù)據(jù)點的離群程度，而不是定性地給出結(jié)論，一個數(shù)據(jù)點是否為離群點. 該算法實質(zhì)上是描述了一個數(shù)據(jù)點在整個數(shù)據(jù)集上的密度情況，也即密度稀疏的數(shù)據(jù)點的離群度較大，密度稠密的數(shù)據(jù)點離群度較小.

新的聚類形式得到所有數(shù)據(jù)點的離群度的取值范圍是在(0,1)區(qū)間，如圖 1 所示.

圖 1 數(shù)據(jù)點的離群度Fig.1 Outlier degree of data points

2.3 SHCAD算法設(shè)計

2.3.1 數(shù)據(jù)劃分

2.3.2超球體聚類

SHCAD算法在進行超球體聚類時，首先計算每個數(shù)據(jù)子集的超球體半徑r，然后對于每個數(shù)據(jù)子集以半徑r進行超球體聚類.

在原始數(shù)據(jù)集X中，將所有數(shù)據(jù)點表示為空間向量形式，設(shè)X表示原始數(shù)據(jù)集X中所有數(shù)據(jù)點的向量集合，故X=(X1，X2，…，Xn),Xi(1≤i≤n)表示一個向量，其中n為向量個數(shù).

在一個樣本子集中，取其中兩個向量Xi和Xj，Xi=(xi1,xi2,…,xim),Xj=(xj1,xj2,…,xjm)，其中m表示分量的個數(shù)，設(shè)Q=(q1,q2,…,qm)，qm表示向量Xi和Xj的第m個分量之間的距離，表達式為

qm=1+|xim-xjm|,

(4)

向量Xi和Xj間的乘法距離可表示為MD(Xi,X)，設(shè)E=(e1,e2,…,em)，其中em是第m個維度上對MD(Xi,Xj)乘法距離的影響因子，所以乘法距離公式為

(5)

超球體半徑r是由樣本子集中所有數(shù)據(jù)點的之間的平均距離所得，可表示為

(6)

然后依次選擇數(shù)據(jù)點為聚類中心，判斷其與周圍數(shù)據(jù)點之間的乘法距離，如果小于半徑r則聚為一類，稱每個類為一個超球體. 含有p條數(shù)據(jù)的數(shù)據(jù)子集中會聚類產(chǎn)生p個超球體.

2.3.3 離群度計算與離群點檢測

SHCAD算法通過多次計算得到穩(wěn)定的離群度，其可以定量描述數(shù)據(jù)點的離群程度，為離群點檢測提供了有力支持.

由式(1)～(3)可知，每個數(shù)據(jù)點的離群度實質(zhì)上描述的是這個點周圍數(shù)據(jù)在整個數(shù)據(jù)集中的相對密度，離群度越大，說明這個點周圍的數(shù)據(jù)點稀疏，則其為離群點的概率就越大，如果一個點的離群度越小，就說明這個點周圍的數(shù)據(jù)點稠密，則其為離群點的概率就越小.

離群點的檢測根據(jù)所有數(shù)據(jù)點的離群度大小來確定，首先，需要自定義一個離群度閾值δ(0<δ<1)，然后判斷數(shù)據(jù)點x的離群度s(x)與δ之間差值V(x)，其判別公式為

(7)

V(x)值越大，表明數(shù)據(jù)點離群程度越大，越偏向離群點.V(x)值越小，表明數(shù)據(jù)點離群程度越小，越偏向正常點，而V(x)取值取決于離群度閾值δ，所以離群度閾值δ取值是否準確將直接影響算法的精度和召回率，所以在實驗中將會對δ的取值給出建議.

3 實驗及結(jié)果分析

3.1 數(shù)據(jù)來源

實驗采用了分別采用了Beijing，Ecoli[11]，KDDCUP-99Finger[12]和KDDCUP-99Other[13]四組公開數(shù)據(jù)集. 其中Beijing為從2013年12月到2017年4月期間的北京空氣質(zhì)量數(shù)據(jù)集，來自中國空氣質(zhì)量在線監(jiān)測分析平臺(http:∥www.aqistudy.cn)，Ecoli是不同亞種的大腸桿菌類別數(shù)據(jù)集，KDDCUP-99Finger和KDDCUP-99Other數(shù)據(jù)集為1998年美國國防部高級規(guī)劃署在MIT林肯實驗室收集的網(wǎng)絡(luò)入侵數(shù)據(jù). Ecoli、KDDCUP-99Finger和KDDCUP-99Other三個數(shù)據(jù)集都來自UCI(http:∥archive.ics.uci.edu/ml/datasets.html)公開數(shù)據(jù).

實驗中為了訓練采樣率v，數(shù)據(jù)劃分次數(shù)L和離群度密度閾值δ，將每一個數(shù)據(jù)集通過隨機采樣均分為兩個等量的數(shù)據(jù)集，分別為訓練集和測試集，并分別命名為Ecoli_train, Ecoli_test, Beijing_train, Beijing_test, Finger_train, Finger_test, Other_train和Other_test. 實驗設(shè)置乘法距離中的維度影響因子et=1(1≤t≤m)，在每個數(shù)據(jù)集中，每個維度對數(shù)據(jù)點間的距離的影響能力是相同的.

每個數(shù)據(jù)集包含的數(shù)據(jù)條數(shù)、維度、離群點的標記和離群點比例如表 1 所示.

表 1 實驗數(shù)據(jù)集的基本信息Tab.1 Essential information of the experimental dataset

3.2 參數(shù)L和v的訓練與分析

為了提高SHCAD算法對離群點檢測的精度和召回率，應選擇出適當?shù)臄?shù)據(jù)劃分次數(shù)L和合適的采樣率v. 用F1作為衡量L和v取值好壞的指標，F(xiàn)1是精度P和召回率R調(diào)和精度值，公式形式為F1=(2×P×R)/(P+R). 根據(jù)文獻[11]和文獻[14]中的數(shù)據(jù)采樣建議，分別取采樣率v為0.04, 0.08, 0.12, 0.16和0.20，并設(shè)置L初始值為10，步長為10，累加到500停止，觀察在不同采樣率下隨著L值的增加F1值的變化情況. 取訓練集中數(shù)據(jù)量差異較小的兩個數(shù)據(jù)集Beijing_train和Other_train訓練參數(shù)L和v，使訓練結(jié)果具有代表性，防止因數(shù)據(jù)集過大或過小而導致的參數(shù)訓練不準. 訓練結(jié)果如圖 2 和圖 3 所示，從圖 2 和圖 3 中可以看出，當采樣率v為0.04到0.12之間時F1值已基本達到最大值. 數(shù)據(jù)劃分次數(shù)為100時，不同采樣率下的F1值都已收斂. 所以根據(jù)實驗結(jié)果，數(shù)據(jù)劃分次數(shù)L取值100次，采樣率v取值0.08較為合理.

圖 2 Beijing_train數(shù)據(jù)集在不同的L和v下的F1值變化情況Fig.2 Different L and v, the F1 value of Beijing_train

圖 3 Finger_train數(shù)據(jù)集在不同的L和v對F1值的影響Fig.3 Different L and v influence F1 value of Finger_train

3.3 離群度閾值δ的訓練與驗證

δ值作為一個需要自定義的離群度閾值，在離群點判別過程中，有至關(guān)重要的作用. 這里使用Ecoli_train，Beijing_train，F(xiàn)inger_train和 Other_train四個數(shù)據(jù)集作為訓練集，利用3.2節(jié)的訓練參數(shù)L=100和v=0.08，訓練出每種數(shù)據(jù)集對應的δ值，并用Ecoli_test，Beijing_test，F(xiàn)inger_test和 Other_test四個測試集對δ值進行驗證.

δ值的訓練過程：L=100和v=0.08作為四個訓練集的輸入?yún)?shù)，得到四個訓練集的中數(shù)據(jù)點的離群度. 設(shè)置δ的初始值為0.01，步長為0.01，累加到0.99停止，根據(jù)式(7)，計算出使得F1值最大的δ值.

訓練結(jié)果如圖 4 所示，四個訓練集Ecoli_train，Beijing_train，F(xiàn)inger_train和 Other_train的最優(yōu)δ值取值或者取值范圍分別為[0.82,0.83], 0.81, 0.64, [0.65,0.84].

δ值的驗證過程： 在四個訓練數(shù)據(jù)集訓練結(jié)果存在多個值的情況，取中值作測試，所以四個訓練集的δ分別取值為0.82, 0.81, 0.64, 0.75. 在這四個δ取值下，通過式(7)得到的四個測試集的F1值，稱為測試F1值，與其對比的值為測試集的最大F1值. 最大F1值是測試集參照訓練集的訓練方式而得到的F1值，稱為最大F1值.

圖 4 四個訓練集δ取值 對F1值的影響Fig.4 Different δ influence F1 value of four train dataset

對比結(jié)果如圖 5 所示，在Beijing_test，F(xiàn)inger_test和Other_test數(shù)據(jù)集上，測試F1值和最大F1十分接近. 在Ecoli_test數(shù)據(jù)集上兩者相差較大，主要原因是Ecoli數(shù)據(jù)集的數(shù)據(jù)量較少，均分為兩個數(shù)據(jù)集Ecoli_train和Ecoli_test時存在離群點分配不均的現(xiàn)象，導致測試F1值較低. 綜合圖 5 中的四個測試集，訓練得出的離群度閾值δ分別取值為0.82，0.81，0.64，0.75是較為合理的.

圖 5 四個測試集上對比測試F1值和最大F1值Fig.5 Comparison of test F1 value and maximum F1 value in four test dataset

3.4 實驗對比分析

實驗采用精度P和召回率R作為算法性能的衡量指標. 設(shè)置L=100，v=0.08，離群度閾值δ分別取值為0.82，0.81，0.64，0.75，在四個測試數(shù)據(jù)集Ecoli_test，Beijing_test，F(xiàn)inger_test和 Other_test中進行對比實驗，分別對比了SHCAD、基于分類的離群點檢測算法One-class-svm和基于快速超球體聚類的FHCAD離群點檢測算法的性能.

圖 6 為不同算法在各個數(shù)據(jù)集上的精度對比. 從圖中可以看出，在所有實驗數(shù)據(jù)集上，SHCAD算法的離群點檢測精度都要優(yōu)于傳統(tǒng)的離群點檢測算法，尤其在Ecoli_test，F(xiàn)inger_test和Other_test三個數(shù)據(jù)集上，SHCAD算法精度明顯高于其余兩個算法. 在四個測試數(shù)據(jù)集上，F(xiàn)HCAD算法的精度要優(yōu)于基于分類的One-class-svm算法.

圖 6 SHCAD算法與FHCAD算法、One-class-svm 算法精度對比Fig.6 Comparison of accuracy among SHCAD, FHCAD and One-class-svm

圖 7 為三種算法在四個測試數(shù)據(jù)集上的召回率對比，從圖中可以看出，在Beijng_test和Finger_test數(shù)據(jù)集上，SHCAD算法的召回率明顯優(yōu)于FHCAD算法和One-class-svm算法. 在Ecoli_test和Other_test數(shù)據(jù)集上，SHCAD算法的召回率也略高于其他兩個算法.

圖 7 SHCAD算法與FHCAD算法、One-class-svm 算法召回率對比Fig.7 Comparison of recall rate among SHCAD, FHCAD and One-class-svm

由實驗結(jié)果可知，改進后的SHCAD算法與FHCAD算法相比，在精度和召回率上有了很大的提升，同時對比了基于分類的One-class-svm算法，其性能指標遠遠優(yōu)于基于分類的One-class-svm算法，實驗證明了SHCAD算法的有效性.

4 結(jié)束語

針對快速超球體聚類離群點檢測算法存在的問題，提出一種基于采樣的超球體聚類的離群點檢測算法，通過數(shù)據(jù)采樣達到對數(shù)據(jù)點的定量描述的目的，采用自適應計算超球體半徑方式，避免了人工設(shè)定超球體半徑的盲目性，同時避免了原算法密度閾值和連接度閾值的設(shè)置問題，最后通過對離群度閾值的訓練和測試，證明了算法的有效性.