離群點檢測算法的評價指標(biāo)

寧 進(jìn)，陳雷霆，3，羅子娟，周 川*，曾慧茹

（1.電子科技大學(xué)計算機科學(xué)與工程學(xué)院，成都 611731；2.數(shù)字媒體技術(shù)四川省重點實驗室（電子科技大學(xué)），成都 611731；3.電子科技大學(xué)廣東電子信息工程研究院，廣東東莞 523808；4.中國電子科技集團公司第二十八研究所信息系統(tǒng)工程重點實驗室，南京 210007）

0 引言

離群點，也可稱為異常點，是數(shù)據(jù)集中與大多數(shù)點不一致，或是由不同機制產(chǎn)生的數(shù)據(jù)［1］。例如在海上安防系統(tǒng)［2］中，入侵船只被看作是異常點，需要攔截。雷達(dá)數(shù)據(jù)處理中［3］，噪聲被看作是離群點，需要過濾以防止干擾建模。

近年來，離群點檢測算法依然是數(shù)據(jù)挖掘的熱點方向。各種基于統(tǒng)計、基于鄰近性、基于分類、基于聚類、基于集成的方法等［4-5］層出不窮，以取得更好的離群點檢測效果。離群點檢測算法的輸出通常為離群得分，得分越高，越可能是離群點?；诮y(tǒng)計的方法對正常數(shù)據(jù)建模，用與正常模式的偏離程度來表示離群得分?；卩徑缘姆椒ㄓ门c鄰居差異程度來表示離群得分?；诜诸惖姆椒ㄓ门c分界線的偏離程度來衡量離群得分?；诰垲惖姆椒ㄒ曤x群點為聚類的副產(chǎn)物，用與正常簇的偏離程度來衡量離群得分。基于集成的方法通過集成多個結(jié)果得到最終的離群得分。

由于離群點本身的少量、多變，以及難以預(yù)知、難以建模的特點，離群點檢測算法常采用無監(jiān)督方法。再加上缺少離群點的標(biāo)簽，使得離群點檢測的評價變得困難。離群點檢測一般使用外部度量來進(jìn)行評價，這種度量需要已有的真實標(biāo)簽來進(jìn)行?，F(xiàn)有的離群點檢測算法評價指標(biāo)主要分為三類，如圖1。第一種是閾值法，在離群得分的基礎(chǔ)上，利用所設(shè)置的閾值來劃分預(yù)測的離群點集。將預(yù)測的離群點集與真實的離群點標(biāo)簽作對比，用檢測率、精確度等統(tǒng)計值來評價算法效果。第二種是曲線法，將閾值法的全參數(shù)下的指標(biāo)繪制連續(xù)的曲線，曲線越“凸”，表示算法效果越好。第三種是整合法，用曲線下的面積來衡量算法效果，值越大，表示算法的效果越好。

圖1 離群點檢測算法評價指標(biāo)Fig.1 Evaluation metrics of outlier detection algorithm

近年來，一些改進(jìn)的方法也被提出來了。例如Zhang等［6］提出了一種帶標(biāo)準(zhǔn)化的精確度的均值，以包含離群度排位信息；但是，這種方法在沒有調(diào)整的時候會產(chǎn)生錯誤［7］。Klement 等［8］針對受試者工作特征（Receiver Operating Characteristic，ROC）曲線丟失離群得分信息的問題，提出了一種平滑的ROC 曲線，通過對ROC 曲線加入平滑分量以保留離群得分信息，對評價算法的差異更具有一致性。此外，Marques 等［9］提出了一種不需要真實標(biāo)簽的內(nèi)部評價方式，這種方式基于離群得分的相對評價，但是計算復(fù)雜度太高。

盡管已有很多適合的評價指標(biāo)，但很多離群點檢測文獻(xiàn)仍然存在評價方法選擇不當(dāng)、使用不當(dāng)?shù)膯栴}，使得所得出的結(jié)論站不住腳。例如，如果錯將正常點標(biāo)記1，異常點標(biāo)記0，得出的評價指標(biāo)虛高。再例如，使用閾值法時，閾值設(shè)置不合理，得出的指標(biāo)結(jié)果偏差也大。此外，離群點檢測算法的評價要求常常分為兩類：一類要求高真正率，例如在疾病檢測中，要求檢測到所有患病者，即使存在將正常人歸為患病類；二類要求低假正率。例如在垃圾郵件檢測中，要求不能把有用郵件誤歸為垃圾郵件，即使漏檢部分真正的垃圾郵件?？傊?，由于離群點檢測算法的特殊性，目前，仍然缺乏針對離群點檢測問題的專門的系統(tǒng)評價方法研究。

本文首先對離群點檢測算法的已有評價指標(biāo)做了一個詳細(xì)的整理，為研究者評價所提出的算法提供評價指標(biāo)的說明和參考；然后針對已有指標(biāo)不能區(qū)分一類和二類要求的問題，提出了一類高真正率評價指標(biāo)（High True positive rate-Area Under Curve，HT_AUC）和二類低假正率評價指標(biāo)（Low False positive rate-Area Under Curve，LF_AUC），通過計算證明和在真實數(shù)據(jù)集上與已有方法的對比實驗，說明了本方法的適用性。

1 常用的離群點檢測算法評價指標(biāo)

設(shè)N個點的離散數(shù)據(jù)集D中，O表示真實的離群點集（令集合大小|O|=n），NO表示正常點集（令集合大小|NO|=m）。離群點檢測算法大多返回離群得分（Outlier Score，OS）［1］，可以是距離、密度、概率等。離群得分越高，越可能是離群點。OS(p)表示點p的離群得分。rank(p)表示點p的離群得分在OS 中的排位，離群得分越高，rank值越小，位次越高。離群點的標(biāo)簽應(yīng)是正類（這里用“1”表示）；正常點的標(biāo)簽應(yīng)是負(fù)類（這里用“0”表示）。

1.1 閾值法

步驟1 設(shè)定閾值。

另一種是TOPr（1 ≤r≤N，評價的時候只要真實的標(biāo)簽可用，那么r就可以設(shè)為n），表示將離群得分排在前r的點判為離群點。

步驟2 計算評價指標(biāo)對。

離群點檢測算法所采用的評價指標(biāo)對主要有3 組，分別是精確度（Precision）和召回率（Recall）［11-13］，真正率（True Positive Rate，TPR）和假正率（False Positive Rate，F(xiàn)PR）［14-15］，檢測率（Detection Rate，DR）和排位力（Rank power，Rp）［16-17］。計算方法如表1。其中：TP表示將離群點標(biāo)記為離群點的量；FP表示將正常點標(biāo)記為離群點的量；FN表示將離群點標(biāo)記為正常點的量；TN表示將離群點標(biāo)記為離群點的量。

表1 閾值法的評價指標(biāo)計算方法Tab.1 Evaluation metrics calculation method of threshold method

Recall=TPR=DR，也稱為檢測準(zhǔn)確率，表示預(yù)測出的真實離群點數(shù)量占所有的真實離群點數(shù)量的比，值越高，表示算法效果越好。但這個單一的指標(biāo)存在著漏洞，即越大，檢測準(zhǔn)確率越高。當(dāng)算法預(yù)測所有數(shù)據(jù)為離群點，即時，檢測準(zhǔn)確率為1。所以，只有這一個指標(biāo)還不足以說明算法的效果。Precision表示預(yù)測出的真實離群點數(shù)量占預(yù)測的離群點數(shù)量的比，值越高，表示算法效果越好。FPR表示預(yù)測錯誤的離群點（真實的正常點預(yù)測為離群點）占正常點數(shù)量的比，值越低，表示算法效果越好。Rp反映了預(yù)測的真實離群點在rank中的排位情況，值越高，表示算法的效果越好。所有的離群點排位在rank前列時，Rp=1。Precision、FPR和Rp作為檢測準(zhǔn)確率的補充增強，可以彌補檢測準(zhǔn)確率的漏洞；此外Rp還利用了rank信息，對算法要求更高。

閾值法簡單有效，可以直接評價離群點檢測算法實驗結(jié)果的優(yōu)劣。但是有如下3個缺陷：

1）參數(shù)依賴。例如，α值太高（或者r太?。?，漏標(biāo)多，評價值會偏低；α值太低（或者r太大），錯標(biāo)多，評價值會偏高。

2）參數(shù)設(shè)置困難。大部分論文在使用這種方法評價算法時，會設(shè)置r=|O|，這需要提前知道數(shù)據(jù)集中有多少真實的離群點。然而在實際應(yīng)用中，很難提前獲取真實離群點的量。

3）丟失了rank 和score 信息。不能表示算法結(jié)果的整體好壞。此外，即使是Rp利用了部分rank 信息，仍然區(qū)分不了如下情況。例如表2：取r=4 的時候，檢測準(zhǔn)確率DR1=DR2=0.5，Rp1=Rp2=0.6，這種情況下，算法1 和算法2 的評價結(jié)果相同，無法區(qū)分好壞。

表2 Rank Power的例子Tab.2 Examples of Rank Power

4）對于Precision 和Recall，在參數(shù)相同的情況下，一些好的算法常常要么高Precision 低Recall，要么低Precision 高Recall。

1.2 曲線法

為了擺脫參數(shù)依賴，整合rank信息，以更精確地評價各個算法的優(yōu)劣。通過從1 到N變化參數(shù)r，得到對應(yīng)的N組Precision 和Recall。依次連接每對（Recall（r），Precision（r））點繪制Precision-Recall（PR）曲線［1，18］（如圖2（a））。同樣，通過從1 到N變化參數(shù)r，依次得到對應(yīng)的TPR（r）和FPR（r），F(xiàn)PR 作橫坐標(biāo)，TPR 作縱坐標(biāo)，繪制ROC 曲線［19-21］（如圖2（b））。由于ROC 曲線比PR 曲線更直觀，且具有單調(diào)性，所以一般情況下，多使用ROC 曲線。ROC 曲線越“凸”，表示算法的效果越好。smROC［8］在ROC曲線的基礎(chǔ)上增加了離群得分信息，使得修改的ROC曲線更加平滑（如圖2（c））。

圖2 PR curve、ROC curve和smROC curve的示例Fig.2 Examples of PR curve，ROC curve and smROC curve

ROC 曲線應(yīng)用在離群點檢測算法的結(jié)果評價上，具有直觀、簡便、精確的優(yōu)點，且不受離群點檢測數(shù)據(jù)集類別的有偏性的影響，在一定程度上是很成功的，具有廣泛的應(yīng)用；但仍然有如下缺陷：

1）不夠清楚。很多時候，一個算法不會完全地比另一個算法“凸”，例如圖2（b），或者更加錯綜復(fù)雜，算法的優(yōu)劣需要進(jìn)一步分情況討論。

2）不能擴展。大部分離群點檢測算法都有除閾值以外的其他參數(shù)依賴，例如，基于鄰近性的算法依賴參數(shù)k（鄰域的大?。?，基于一類支持向量機算法依賴核函數(shù)的選擇，用ROC 曲線只能展示特定參數(shù)下算法的差異。

1.3 整合法

為了驗證算法與非閾值參數(shù)的關(guān)系，通常需要整合曲線，直接用一個數(shù)值來體現(xiàn)算法綜合能力。使得該數(shù)值既有閾值法的簡單直觀性，并保留曲線法的精確性。已經(jīng)知道，曲線法評價好的算法比壞的算法更“凸”，于是可以用一種曲線的整合形式，即曲線下的面積（Area Under Curve，AUC）來評價算法。數(shù)值越高，表示算法效果越好。

PR_AUC［22-23］是PR 曲線下的面積，可以由離群點的平均精確度計算。

證明 在PR 曲線中，隨著r的增加，當(dāng)?shù)趓個數(shù)據(jù)點真實標(biāo)簽為1 時，Precision 變?yōu)镻recision（r），Recall 增加1/n，對應(yīng)變化面積為。當(dāng)?shù)趓個數(shù)據(jù)點真實標(biāo)簽為0 時，Recall 不變，Precision 減少，曲線垂直下降，變化面積為0，所以PR_AUC可以計算如下：

ROC_AUC［24-25］是ROC 曲線下的面積，也可由數(shù)據(jù)集中離群點-正常點對的均值來計算。

證明 離散情況下，在ROC 曲線中隨著r增加，當(dāng)?shù)趓個數(shù)據(jù)點真實標(biāo)簽為1 時，TPR 增加1/n，F(xiàn)PR 不變，對應(yīng)ROC 曲線垂直上升，變化面積為0。當(dāng)?shù)趓個數(shù)據(jù)點真實標(biāo)簽為0時，TPR 不變，F(xiàn)PR 增加1/m，對應(yīng)變化面積為TPR(rank(i))，所以ROC_AUC可以計算如下：

用曲線法評價離群點檢測算法效果時，不受數(shù)據(jù)集中離群點比例的影響。但整合為ROC_AUC 后，只要求曲線像左上角“凸”，很難保證算法同時有高真正率和低假正率，丟失了曲線的細(xì)節(jié)信息，不能同時滿足一類和二類要求。例如表3中，算 法1 的ROC_AUC1==0.8，算 法2 的=0.8。算法1 和算法2 的ROC_AUC值相同，但實際差別很大。算法1 在r=4 時，就能檢測出所有離群點，而算法2 在r=6 的時候才能檢測出所有離群點；算法r=2時，能檢測出2個離群點，且未將正常點誤判為離群點，而算法1無論r等于多少，都存在將正常點誤判為離群點。

在實際應(yīng)用中，對于算法1 和算法2 有著不同的適用場景。算法1 適合要求高檢測準(zhǔn)確率的場景，即要求所有離群點的rank 靠前，例如疾病檢測；算法2 適合要求低錯誤率的場景，即要求所有正常點的rank靠后，例如垃圾郵件檢測。

代價敏感（Meta Cost）方法［1］通過引入代價因子，作為TPR和FPR的權(quán)衡。代價因子c（Y，n）表示將正常點預(yù)測為離群點的代價，c(N，y)表示將離群點預(yù)測為正常點的代價。通過修改I函數(shù)，每項不等式右乘，為不同類型的錯誤分類設(shè)置不同的代價。當(dāng)設(shè)置c(Y，n) ＞c(N，y)時，表示正常點預(yù)測為離群點的代價更高，最終的meta_AUC 比ROC_AUC 更??；當(dāng)設(shè)置c(Y，n) ＜c(N，y)時，表示離群點預(yù)測為正常點的代價更高，最終的meta_AUC 比ROC_AUC 更大。這種方法通過設(shè)置兩個代價因子來權(quán)衡參數(shù)依賴，需要依靠經(jīng)驗設(shè)置。代價因子的可解釋性較弱，不便于使用。

表3 ROC_AUC的例子Tab.3 Examples of ROC_AUC

綜上述，閾值法適合在應(yīng)用決策時使用，曲線法適合算法效果的精確展示，整合法適合在參數(shù)控制時使用。已有的離群點檢測評價方式常常采用以上指標(biāo)的綜合方案［8］，以便優(yōu)勢互補，充分驗證算法的效果。

2 方法

2.1 高真正率和低假正率指標(biāo)

定義1一類高真正率要求：要求TPR 接近1，對應(yīng)ROC曲線向頂部“凸”。

定義2二類低假正率要求：要求FPR 接近0，對應(yīng)ROC曲線向左部“凸”。

例如在疾病檢測中，將患?。?biāo)簽為“1”）錯標(biāo)記為正常（“0”），會導(dǎo)致該患者得不到治療。如果是傳染病，漏檢還會發(fā)生進(jìn)一步傳染，產(chǎn)生嚴(yán)重的后果。因此，疾病檢測系統(tǒng)要求一類高真正率，檢測到所有患病者，即使存在將正常人歸為患病類，可以進(jìn)一步檢測排除“疑似類”。在垃圾郵件檢測中，將重要郵件（標(biāo)簽為“0”）誤判為垃圾郵件（標(biāo)簽為“1”），會給收件人帶來難以估量的影響。因此垃圾郵件檢測系統(tǒng)要求二類要求低假正率，要求不能把重要郵件誤判為垃圾郵件，即使漏檢部分真正的垃圾郵件。

為了同時解決已有整合法的信息丟失和參數(shù)依賴的問題，適應(yīng)一類高真正率和二類低假正率要求，本文提出了HT_AUC和LF_AUC。

其中：α∈[0，1]是控制變量，表示求算法的ROC曲線在FPR＞α?xí)r具有高TPR，H表示NO中rank 值在后的點的集合。式（1）中第一個加項表示ROC 曲線后1-α部分曲線的面積，第二個加項表示忽略ROC曲線前α部分曲線的面積，適應(yīng)一類要求。

其中：α∈[0，1]是控制變量，表示求算法的ROC曲線在TPR＜α?xí)r具有低FPR，L表示O中rank 值在前α*n的點的集合。式（2）中第一個加項表示ROC曲線下面α部分曲線的面積，第二個加項表示忽略ROC 曲線后1-α部分曲線的面積，適應(yīng)二類要求。

例如，表3中算法1和算法2，取α=0.2，可以計算出：

HT_AUC1＞HT_AUC2，說明算法1 更能適應(yīng)一類要求，LF_AUC2＞LF_AUC1，說明算法2更能適應(yīng)二類要求。

2.2 證明

本方法通過調(diào)整參數(shù)α控制一類高真正率或者二類低假正率要求的程度。對于HT_AUC，表示在容忍FPR=α的情況下整合TPR 越高越好，α越小越接近ROC_AUC；對于LF_AUC，表示在滿足TPR=α的情況下整合FPR 越低越好，α越大越接近ROC_AUC。相較于Meta Cost 中的代價因子，本文方法的參數(shù)可解釋性更強，更容易設(shè)置，參數(shù)依賴性更低。

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

3.1 實驗準(zhǔn)備

數(shù)據(jù)集取自UCI 的30 個真實數(shù)據(jù)集［26］，表4 展示了這些真實數(shù)據(jù)集的特征。將數(shù)量稀少的類或者特選類中的數(shù)據(jù)點作為離群點，剩余的數(shù)據(jù)點作為正常點。

1）一類和二類要求。為了驗證本文評價方法的有效性，本文首先細(xì)化一類要求：要求在FPR=40%時，離群點檢測算法的TPR越高，算法效果越好。這種要求表示在同等容錯下，檢測準(zhǔn)確率越高的算法越能滿足高真正率要求。然后細(xì)化二類要求：要求在TPR=80%時，離群點檢測算法的FPR越低，算法效果越好。這種要求表示在同等檢測率下，檢測錯誤率越低的算法越能滿足低假正率要求。實驗平臺為3.4 GHz CPU，8 GB RAM，Windows10 系統(tǒng)，PyCharm 社區(qū)版，采用Python編程。

2）離群點檢測方法。使用下列4 種經(jīng)典的離群點檢測算法［18，27］作為評價指標(biāo)的對比算法：局部異常因子（Local Outlier Factor，LOF）、K最近鄰（KNearest Neighbor，KNN）、孤立森林（Isolation Forest，IF）、不穩(wěn)定因子（INStability factor，INS）。這4 種不同類型的算法在每個數(shù)據(jù)集上的檢測結(jié)果有不同程度的差異，本實驗的目的即比較出更能區(qū)分這些算法在不同要求下效果優(yōu)劣的評價指標(biāo)。

3）對比方法。將本文提出的HT_AUC 和LF_AUC 方法與已有的PR_AUC，ROC_AUC 以及meta_AUC（代價比分別設(shè)為1.25 和0.8）作對比。一類要求的評價方法對比策略：以每個算法在FPR=40%時的TPR 值作為基準(zhǔn)指標(biāo)，按從大到小對算法排序，再對比HT_AUC 與其他3 個方法的評價排序，與基準(zhǔn)指標(biāo)越接近（排序的歐式距離越小）的評價方法越好；同理，二類要求的評價方法對比策略：以每個算法在TPR=80%時的FPR 值作為基準(zhǔn)指標(biāo)，按從小到大對算法排序，再對比HT_AUC 與其他3 個算法的評價排序，與基準(zhǔn)指標(biāo)越接近（排序的歐式距離越?。┑脑u價方法越好。

表4 真實數(shù)據(jù)集的描述Tab.4 Description of real-world datasets

3.2 結(jié)果及分析

圖3記錄了HT_AUC與對比方法在30個真實數(shù)據(jù)集上的實驗結(jié)果。可以看出，meta_AUC 在大部分?jǐn)?shù)據(jù)集上具有最高的差異度，也就是與基準(zhǔn)指標(biāo)的差異最大，這是由于代價因子的影響。PR_AUC 和ROC_AUC 的方法大部分時候與基準(zhǔn)指標(biāo)差異不大，能基本滿足一類高真正率要求。HT_AUC 在大部分情況下結(jié)果和ROC_AUC 一致，部分?jǐn)?shù)據(jù)集上能展示出更好的效果。因此，可以得出結(jié)論，HT_AUC 比其他指標(biāo)更能滿足一類高真正率要求。

圖4 記錄了LF_AUC 與對比方法在30 個真實數(shù)據(jù)集上的實驗結(jié)果。同樣的，meta_AUC 在大部分?jǐn)?shù)據(jù)集上與基準(zhǔn)指標(biāo)的差異較大。PR_AUC 和ROC_AUC 的方法大部分時候與基準(zhǔn)指標(biāo)差異不大，能基本滿足二類低假正率要求。LF_AUC在大部分情況下結(jié)果和ROC_AUC 一致，其余數(shù)據(jù)集上能展示出更好的效果。因此，也可以得出結(jié)論，LF_AUC 比其他指標(biāo)更能滿足二類低真正率要求。

圖3 HT_AUC與傳統(tǒng)評價方法的結(jié)果對比Fig.3 Result comparison of the proposed HT_AUC and traditional methods

圖4 LF_AUC與傳統(tǒng)評價方法的結(jié)果對比Fig.4 Result comparison of the proposed LF_AUC and traditional methods

整體來看，所提出HT_AUC 和LF_AUC 指標(biāo)相較于其他方法，與基準(zhǔn)指標(biāo)的差異最小，更能滿足一類高真正率要求和二類低真正率要求。該方法可作為具有特別要求系統(tǒng)的評價指標(biāo)，例如要求一類高真正率的疾病檢測可使用HT_AUC 指標(biāo)，要求二類低假正率的垃圾郵件檢測可使用LF_AUC指標(biāo)。

4 結(jié)語

本文對離群點檢測領(lǐng)域內(nèi)常見的評價方法作了歸納整理，并提出了滿足一類高真正率要求的HT_AUC 指標(biāo)和滿足二類低假正率要求的LF_AUC 指標(biāo)。已有離群點檢測評價方式建議采用兩類以上的評價指標(biāo)，以便優(yōu)勢互補，充分驗證算法的效果。其中，閾值法適合工業(yè)選擇時使用，曲線法適合算法效果的精確展示，整合法適合在參數(shù)控制時使用。實驗結(jié)果表明，如果應(yīng)用對算法的真正率和假正率有特殊要求，采用所提出的HT_AUC 和LF_AUC 指標(biāo)，能更好地評價所使用的算法。本文所涉及的數(shù)據(jù)對象主要是離群數(shù)據(jù)集，未來將繼續(xù)對序列離群點檢測算法的評價方法進(jìn)行研究。