基于主動學習的離群點集成挖掘方法研究

趙曉永，王寧寧，王 磊

北京信息科技大學 信息管理學院，北京100129

1 引言

離群點是指與數據集中的其他數據有明顯偏離，使人懷疑這些數據點是由不同機制產生的[1]。離群點檢測（Outlier Detection），也稱為離群點挖掘（Outlier Mining），因其在金融欺詐、網絡入侵、故障檢測、生物信息等領域有著廣闊的應用前景，受到了廣泛關注和研究。

離群點檢測任務通常缺少可用的標注數據，且離群數據只占整個數據集的很小一部分，因此，相較于其他的數據挖掘任務，離群點檢測的難度較大。目前對于離群點檢測的研究主要可分為以下幾類：（1）基于概率統計的檢測方法，包括基于直方圖[2-3]和圖基測試（Tukey Test）[4]的檢測方法等；（2）基于相似性的檢測方法，包括基于聚類[5-6]、近鄰距離[7-8]和密度[9-10]的檢測方法；（3）基于分類的方法，包括基于淺層神經網絡、基于支持向量機的二元分類方法和深度自編碼器方法[11-12]；（4）對高維數據的子空間劃分方法，包括孤立森林等[13-14]；（5）基于信息論的檢測方法[15-17]。

由于離群點檢測任務的復雜性，尚沒有單一的算法適合于所有的場景，因此研究人員提出了基于模型集成的檢測方法[18]，以降低單一算法帶來的風險。其中，文獻[19]設計了在離群點檢測中使用不同的特征子集的方法，并將它們組合以提供更有效的結果。文獻[20-22]中展示了如何組合來自離群值檢測算法發現的不同子空間的分數，以便提供統一且更穩健的結果。文獻[23]借鑒隨機森林方法思想，提出了離群點檢測的孤立森林（Isolation Forest）概念，并在工業界中得到了廣泛的應用。

鑒于領域專家知識的應用對提高離群點的識別效果總是非常明顯[1]，研究人員嘗試將主動學習（Active Learning）應用于離群點檢測，使得人類專家可以將領域知識，進而將無監督的離群點檢測問題轉換為有監督的稀有類別檢測問題方面。文獻[24]中提出了基于主動學習的離群點檢測方法，從未標記的數據迭代主動地學習，在每次迭代中，算法確定有助于進一步分類的“重要的”示例，呈現給人類專家，由其為這些示例進行標注，然后使用這些標記后的數據對數據集進行分類。

結合多樣性模型集成和主動學習思想，本文提出了一種基于主動學習的離群點集成檢測方法OMAL（Outlier Mining based on Active Learning）。在主動學習框架指導下，首先根據各種基礎學習器的對比分析，選擇基于統計的HBOS、基于相似性的模型iORCA、基于軸平行子空間劃分的Isolation Forest共3個無監督模型作為基學習器；然后，將各基學習器評判的離群分數處于離群和正常邊界的數據合并后呈現給人類專家進行標注，這樣可以最大化人類專家反饋的信息量[24]；從標注的數據集和各基學習器投票產生的數據集中抽樣75%訓練基于GBM（Gradient Boosting Machine）[25]的有監督二元分類模型，將該模型應用于全數據集，得出最終的挖掘結果；最后，使用文獻[26]和[27]中的數據集進行實驗，結果表明本文提出方法的AUC（Area Under Curve）有了較為明顯的提升，且具有良好的運行效率，具備較好的實用價值。

2 方法設計

2.1 OMAL總體框架

在主動學習框架指導下，本文提出的離群點集成挖掘方法整體流程如圖1所示。

圖1 OMAL整體流程圖

首先使用分析對比后選擇的3個無監督基學習器對原始數據進行離群挖掘，根據各基學習器的輸出，采用算法1呈現出少量重要數據給專家進行標注，采用算法2的集成方式產生部分帶標注的訓練數據集，并與專家標注的數據集整合后，去訓練基于GBM的二元監督分類模型，然后將該模型應用到原始數據上，得到最終的離群挖掘結果。

2.2 基學習器的選擇

目前主要的無監督離群檢測算法如表1。

諸多學者已經對上述算法進行了多種對比研究，Sugiyama等人對比了iForest、FastVOA、iORCA、One Class SVM、LOF和子采樣Sugiyama-Borgwardt方法在多種數據集上的表現，其中Sugiyama-Borgwardt、iORCA和iForest效果最佳，表明采樣能大幅提升處理性能，同時保證準確性[7]；Lazarevic等基于KDD Cup99數據集，對比了LOF、k-NN、PCA和One-Class SVM算法[19]；Campos等人對基于距離(k NN k NNW)、密度（LOF、SimplifiedLOF、LoOP、COF、LDF、INFLO、LDOF、ODIN、KDEOS）和角度（FastABOD）的方法進行了對比，結果表明k NN k NNW和LOF是這些方法中統計最優的，特別是在離群點數量較多的情況下更為突出，在離群點數量較少的情況下，SimplifiedLOF和LoOP效果與LOF相近；LDF在某些情況下有最好的效果，但非常不穩定，FastABOD非常穩定，但效果較差[26]。Goldstein等人的研究表明，局部離群檢測算法（LOF、COF、INFLO、LoOP、LOCI、LDCOF、CMGOS）只適合于僅包含局部離群點的數據集，在包含有全局離群點的數據集上，會產生許多誤檢；相反，全局離群檢測算法（HBOS、Robust PCA、K-NN、uCBLOF、One-Class SVM）不僅可檢測全局離群點，對于局部離群問題，可至少達到平均水平，在對數據集沒有先驗知識的情況下，建議優先選擇全局離群檢測算法[27]。Ding等人對比了SVDD、K-NN、K-Means和GMM在10個不同數據集上的離群檢測效果[28]；Liu等人對比了iForest、SciForest、ORCA、One Class SVM、Random Forest和LOF在多個數據集上的表現，指出iForest對全局離群點檢測問題最有效，SciForest對局部離群點檢測問題最有效[29-30]。Zimek等的研究表明，在無監督的離群點集成算法中，采取多樣性的基模型有助于提升最終的效果，且不同類型的模型集成優于不同參數的同類模型集成[31]。

表1 主要的無監督離群檢測算法

綜合上述文獻的研究成果，結合本文研究方法的特點，給出基學習器的選擇原則：

（1）近線性時間復雜度。主動學習框架中需要人類專家參與，時效性是保證閉環順利進行的核心要素，因此，各基學習器的時間復雜度是第一重要的選擇指標。

（2）模型的魯棒性。各基學習器需要在不同數據集上有穩定的表現。

（3）模型的多樣性。多樣性的模型集成可發現不同原因產生的離群點，提升最終檢測效果。

（4）模型可解釋性。模型可解釋性允許領域專家更好地理解基學習器發現的離群點，從而更好地進行標注。

因此，本文選擇了基于統計的HBOS、基于相似性的模型iORCA、基于軸平行子空間劃分的Isolation Forest共3種類別的、近線性時間復雜度的、無監督模型作為基學習器。

2.3 監督模型訓練集的構造

為了將離群點檢測轉換為有監督的過程，需要構造出用于訓練的有標注數據集，標注主要來源于兩個方面：人類專家的標注、基學習器的結果整合。

為了減少人類專家的標注工作量，同時最大化標注的價值，需要將能夠為系統帶來最多反饋信息的數據呈現給人類專家[32]，算法1描述了人類專家標注訓練集構建的具體過程。

算法1人類專家標注訓練集構建算法

輸入：各基學習器的輸出S1～S3

輸出：帶標注的數據集D

（1）從各基學習器的輸出S1～S3中，根據學習器的評分，獲取處于離群和正常邊界的離群數據各m(m=min（10，可用數據））條、正常數據各n(n=min（5，可用數據））條，則從S1～S3中可得到待標注離群數據集A1～A3（不超過30行）和待標注的正常數據集N1～N3（不超過15行）；

（2）將A1～A3 N1～N3分別合并去重后可得待標注離群數據集A、待標注的正常數據集N；

（3）在A和N中重復的數據，將其從N中刪除；

（4）將A和N按照離群程度降序排列后呈現給人類專家進行標注；

（5）A和N合并為D并輸出，算法結束。

基學習器的結果整合是集成學習的關鍵點，但由于各學習器輸出結果的含義和尺度的差異，結果整合仍然是集成學習中的難點[31]。由于本文的方法并不需要將基學習器的模型進行整合，因此無需對輸出結果在含義和尺度上進行融合；另一方面，依據沒有免費午餐定理NFL[33-34]，在分布未知的多種數據集上，各基學習器的平均表現是相當的，因此采用了未加權的簡單投票（Major Vote）方法，算法2描述了基學習器投票標注訓練集的具體過程。

算法2基學習器投票標注訓練集算法

輸入：各基學習器的輸出S1～S3

輸出：帶標注的數據集E

（1）將各基學習器的輸出S1～S3拆分為離群數據集Sa1～Sa3和正常數據集Sn1～Sn3；

（2）對Sa1～Sa3進行簡單投票，將在一半以上數據集中出現的，作為訓練用的離群數據集A；

（3）從Sn1～Sn3的交集中抽樣75%，作為訓練用的正常數據集N；

（4）A和N合并為E并輸出，算法結束。

將算法1和算法2的輸出結果D和E合并形成最終的訓練數據集，當遇到標注沖突的數據時，以D中的標注為準。

2.4 有監督分類算法的選擇

首先，由于離群數據的稀有特性，2.3節構造出的訓練數據集仍然是不平衡的，而常用的過采樣、欠采樣方法均不適于離群挖掘場景[35]，因此，需要能夠支持不平衡數據集的二元分類算法；其次，人類專家標注訓練集后，會希望能盡快獲得最終的離群挖掘結果，這也就要求有監督模型必須有較高的訓練和預測性能。

Friedman等人提出的GBM（Gradient Boosting Machine）是一種Boosting集成學習模型，支持不平衡數據集的二元分類，具有可高度定制的靈活性、訓練速度快且可并行化、易于調參和可解釋性強等優點[36]，在各大數據挖掘競賽和工業界均有廣泛的應用并取得了良好的效果[37]，因此，本文選擇基于GBM的有監督二元分類算法。

3 實驗

3.1 實驗環境

本文的實驗環境為1臺8核32 GB內存，500 GB硬盤容量的Dell R620服務器，操作系統為Ubuntu 16.04。

測試數據為文獻[26]和[27]使用的30個公開數據集，這些數據集也被許多離群點挖掘的文獻使用，其中kdd99、shuttle和annthyroid數據集在兩篇文獻中分別做了不同的處理，數據集的情況如表2。

OMAL算法中各基學習器HBOS、iORCA和iForest參數設定分別使用各算法提出者文獻中的推薦設定；并基于lightgbm實現有監督二元分類監督模型，設置unbalanced參數后可支持不平衡數據集二分類。將OMAL算法與各基學習器HBOS、iORCA和iForest獨立運行時的結果進行對比，各基學習器也采用各算法提出者文獻中的推薦設定。采用無監督離群挖掘算法評價的事實標準AUC其作為評價指標[1]。

3.2 實驗結果

圖2顯示了本文使用的基學習器在各數據集上的運行時長情況。得益于此三種基學習器的近似線性時間復雜度（參見2.2節），對于6萬行以內的數據集，人類專家需要等待的時間均在3 s以內，由于大腦的短時記憶效應，此時間間隔內人們不會感覺到明顯的等待[38]。

圖3顯示了本文提出的OMAL算法與三種典型的基學習器方法的對比結果，可以看出，得益于人類專家反饋的信息，本文的OMAL方法在這些數據集上的AUC值都有了較為顯著的提升。

表2 數據集情況

圖2 基學習器運行時長

4 結論

針對目前的離群點挖掘方法尚未有效解決專家知識應用、擴展性和準確率三者之間的平衡問題，本文結合主動學習和模型集成，提出一種基于主動學習的離群點集成挖掘方法OMAL，結合多個無監督基學習器的學習結果與人類專家知識，訓練出有監督的二元分類模型，在減少工作量、提升擴展性的同時，達到了較高的準確率。實驗表明，OMAL方法在提供更好的離群點挖掘效果的同時，具有良好的運行效率，具備較好的實用價值。不過，在主動學習過程中，如果能經過人類專家的多輪指導，可獲得更多的反饋信息，有助于提升系統效果，但如何呈現每輪次的待標注數據以優化信息反饋效率，如何處理每輪次標注后的樣本集以優化下輪無監督學習器的輸出，如何根據每輪次的反饋調整各基學習器的權重，是需要進一步研究的問題。

圖3 算法AUC結果對比