趙曉永，王寧寧，王 磊

北京信息科技大學(xué) 信息管理學(xué)院，北京100129

1 引言

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

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

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

鑒于領(lǐng)域?qū)＜抑R的應(yīng)用對提高離群點(diǎn)的識別效果總是非常明顯[1]，研究人員嘗試將主動學(xué)習(xí)（Active Learning）應(yīng)用于離群點(diǎn)檢測，使得人類專家可以將領(lǐng)域知識，進(jìn)而將無監(jiān)督的離群點(diǎn)檢測問題轉(zhuǎn)換為有監(jiān)督的稀有類別檢測問題方面。文獻(xiàn)[24]中提出了基于主動學(xué)習(xí)的離群點(diǎn)檢測方法，從未標(biāo)記的數(shù)據(jù)迭代主動地學(xué)習(xí)，在每次迭代中，算法確定有助于進(jìn)一步分類的“重要的”示例，呈現(xiàn)給人類專家，由其為這些示例進(jìn)行標(biāo)注，然后使用這些標(biāo)記后的數(shù)據(jù)對數(shù)據(jù)集進(jìn)行分類。

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

2 方法設(shè)計(jì)

2.1 OMAL總體框架

在主動學(xué)習(xí)框架指導(dǎo)下，本文提出的離群點(diǎn)集成挖掘方法整體流程如圖1所示。

圖1 OMAL整體流程圖

首先使用分析對比后選擇的3個無監(jiān)督基學(xué)習(xí)器對原始數(shù)據(jù)進(jìn)行離群挖掘，根據(jù)各基學(xué)習(xí)器的輸出，采用算法1呈現(xiàn)出少量重要數(shù)據(jù)給專家進(jìn)行標(biāo)注，采用算法2的集成方式產(chǎn)生部分帶標(biāo)注的訓(xùn)練數(shù)據(jù)集，并與專家標(biāo)注的數(shù)據(jù)集整合后，去訓(xùn)練基于GBM的二元監(jiān)督分類模型，然后將該模型應(yīng)用到原始數(shù)據(jù)上，得到最終的離群挖掘結(jié)果。

2.2 基學(xué)習(xí)器的選擇

目前主要的無監(jiān)督離群檢測算法如表1。

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

表1 主要的無監(jiān)督離群檢測算法

綜合上述文獻(xiàn)的研究成果，結(jié)合本文研究方法的特點(diǎn)，給出基學(xué)習(xí)器的選擇原則：

（1）近線性時間復(fù)雜度。主動學(xué)習(xí)框架中需要人類專家參與，時效性是保證閉環(huán)順利進(jìn)行的核心要素，因此，各基學(xué)習(xí)器的時間復(fù)雜度是第一重要的選擇指標(biāo)。

（2）模型的魯棒性。各基學(xué)習(xí)器需要在不同數(shù)據(jù)集上有穩(wěn)定的表現(xiàn)。

（3）模型的多樣性。多樣性的模型集成可發(fā)現(xiàn)不同原因產(chǎn)生的離群點(diǎn)，提升最終檢測效果。

（4）模型可解釋性。模型可解釋性允許領(lǐng)域?qū)＜腋玫乩斫饣鶎W(xué)習(xí)器發(fā)現(xiàn)的離群點(diǎn)，從而更好地進(jìn)行標(biāo)注。

因此，本文選擇了基于統(tǒng)計(jì)的HBOS、基于相似性的模型iORCA、基于軸平行子空間劃分的Isolation Forest共3種類別的、近線性時間復(fù)雜度的、無監(jiān)督模型作為基學(xué)習(xí)器。

2.3 監(jiān)督模型訓(xùn)練集的構(gòu)造

為了將離群點(diǎn)檢測轉(zhuǎn)換為有監(jiān)督的過程，需要構(gòu)造出用于訓(xùn)練的有標(biāo)注數(shù)據(jù)集，標(biāo)注主要來源于兩個方面：人類專家的標(biāo)注、基學(xué)習(xí)器的結(jié)果整合。

為了減少人類專家的標(biāo)注工作量，同時最大化標(biāo)注的價值，需要將能夠?yàn)橄到y(tǒng)帶來最多反饋信息的數(shù)據(jù)呈現(xiàn)給人類專家[32]，算法1描述了人類專家標(biāo)注訓(xùn)練集構(gòu)建的具體過程。

算法1人類專家標(biāo)注訓(xùn)練集構(gòu)建算法

輸入：各基學(xué)習(xí)器的輸出S1～S3

輸出：帶標(biāo)注的數(shù)據(jù)集D

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

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

（3）在A和N中重復(fù)的數(shù)據(jù)，將其從N中刪除；

（4）將A和N按照離群程度降序排列后呈現(xiàn)給人類專家進(jìn)行標(biāo)注；

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

基學(xué)習(xí)器的結(jié)果整合是集成學(xué)習(xí)的關(guān)鍵點(diǎn)，但由于各學(xué)習(xí)器輸出結(jié)果的含義和尺度的差異，結(jié)果整合仍然是集成學(xué)習(xí)中的難點(diǎn)[31]。由于本文的方法并不需要將基學(xué)習(xí)器的模型進(jìn)行整合，因此無需對輸出結(jié)果在含義和尺度上進(jìn)行融合；另一方面，依據(jù)沒有免費(fèi)午餐定理NFL[33-34]，在分布未知的多種數(shù)據(jù)集上，各基學(xué)習(xí)器的平均表現(xiàn)是相當(dāng)?shù)模虼瞬捎昧宋醇訖?quán)的簡單投票（Major Vote）方法，算法2描述了基學(xué)習(xí)器投票標(biāo)注訓(xùn)練集的具體過程。

算法2基學(xué)習(xí)器投票標(biāo)注訓(xùn)練集算法

輸入：各基學(xué)習(xí)器的輸出S1～S3

輸出：帶標(biāo)注的數(shù)據(jù)集E

（1）將各基學(xué)習(xí)器的輸出S1～S3拆分為離群數(shù)據(jù)集Sa1～Sa3和正常數(shù)據(jù)集Sn1～Sn3；

（2）對Sa1～Sa3進(jìn)行簡單投票，將在一半以上數(shù)據(jù)集中出現(xiàn)的，作為訓(xùn)練用的離群數(shù)據(jù)集A；

（3）從Sn1～Sn3的交集中抽樣75%，作為訓(xùn)練用的正常數(shù)據(jù)集N；

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

將算法1和算法2的輸出結(jié)果D和E合并形成最終的訓(xùn)練數(shù)據(jù)集，當(dāng)遇到標(biāo)注沖突的數(shù)據(jù)時，以D中的標(biāo)注為準(zhǔn)。

2.4 有監(jiān)督分類算法的選擇

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

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

3 實(shí)驗(yàn)

3.1 實(shí)驗(yàn)環(huán)境

本文的實(shí)驗(yàn)環(huán)境為1臺8核32 GB內(nèi)存，500 GB硬盤容量的Dell R620服務(wù)器，操作系統(tǒng)為Ubuntu 16.04。

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

OMAL算法中各基學(xué)習(xí)器HBOS、iORCA和iForest參數(shù)設(shè)定分別使用各算法提出者文獻(xiàn)中的推薦設(shè)定；并基于lightgbm實(shí)現(xiàn)有監(jiān)督二元分類監(jiān)督模型，設(shè)置unbalanced參數(shù)后可支持不平衡數(shù)據(jù)集二分類。將OMAL算法與各基學(xué)習(xí)器HBOS、iORCA和iForest獨(dú)立運(yùn)行時的結(jié)果進(jìn)行對比，各基學(xué)習(xí)器也采用各算法提出者文獻(xiàn)中的推薦設(shè)定。采用無監(jiān)督離群挖掘算法評價的事實(shí)標(biāo)準(zhǔn)AUC其作為評價指標(biāo)[1]。

3.2 實(shí)驗(yàn)結(jié)果

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

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

表2 數(shù)據(jù)集情況

圖2 基學(xué)習(xí)器運(yùn)行時長

4 結(jié)論

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

圖3 算法AUC結(jié)果對比