離群點檢測算法的評價指標

寧 進，陳雷霆，3，羅子娟，周 川*，曾慧茹

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

0 引言

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

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

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

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

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

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

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

1 常用的離群點檢測算法評價指標

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

1.1 閾值法

步驟1 設定閾值。

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

步驟2 計算評價指標對。

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

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

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

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

1）參數依賴。例如，α值太高（或者r太小），漏標多，評價值會偏低；α值太低（或者r太大），錯標多，評價值會偏高。

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

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

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

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

1.2 曲線法

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

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

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

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

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

1.3 整合法

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

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

證明 在PR 曲線中，隨著r的增加，當第r個數據點真實標簽為1 時，Precision 變為Precision（r），Recall 增加1/n，對應變化面積為。當第r個數據點真實標簽為0 時，Recall 不變，Precision 減少，曲線垂直下降，變化面積為0，所以PR_AUC可以計算如下：

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

證明 離散情況下，在ROC 曲線中隨著r增加，當第r個數據點真實標簽為1 時，TPR 增加1/n，FPR 不變，對應ROC 曲線垂直上升，變化面積為0。當第r個數據點真實標簽為0時，TPR 不變，FPR 增加1/m，對應變化面積為TPR(rank(i))，所以ROC_AUC可以計算如下：

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

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

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

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

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

2 方法

2.1 高真正率和低假正率指標

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

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

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

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

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

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

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

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

2.2 證明

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

3 實驗結果與分析

3.1 實驗準備

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

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

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

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

表4 真實數據集的描述Tab.4 Description of real-world datasets

3.2 結果及分析

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

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

圖3 HT_AUC與傳統評價方法的結果對比Fig.3 Result comparison of the proposed HT_AUC and traditional methods

圖4 LF_AUC與傳統評價方法的結果對比Fig.4 Result comparison of the proposed LF_AUC and traditional methods

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

4 結語

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