基于孤立森林采樣策略的企業(yè)異常用水模式檢測

林青軒，郭 強，鄧春燕，王雅靜，劉建國

(1.上海理工大學(xué)復(fù)雜系統(tǒng)科學(xué)研究中心,上海 200093; 2.上海財經(jīng)大學(xué)會計與財務(wù)研究院,上海 200433)

0 引言

企業(yè)異常用水模式檢測是指從企業(yè)用水量數(shù)據(jù)中找出異常的模式，企業(yè)用能數(shù)據(jù)如用水量和用電量是企業(yè)生產(chǎn)經(jīng)營狀況最直接的反映，分析企業(yè)用水量數(shù)據(jù)能夠一定程度上檢測出企業(yè)生產(chǎn)經(jīng)營上的異常行為。公共安全部門若能及時發(fā)現(xiàn)生產(chǎn)運作狀態(tài)異常的企業(yè)，并對其進行事前干預(yù)，對于保護公民的人身安全和維護社會安全有十分重要的意義。另外，以往公共安全部門多采用現(xiàn)場稽查的形式對企業(yè)是否正常運營進行判斷，十分耗費人力物力而且不能及時地進行監(jiān)管。因此，公共安全部門亟需一套行之有效的企業(yè)異常用水模式檢測方法。

機器學(xué)習(xí)方法已經(jīng)被應(yīng)用于此類發(fā)現(xiàn)異常模式的任務(wù)，已經(jīng)有效應(yīng)用于信用卡反欺詐[1-2]、垃圾網(wǎng)頁識別[3-4]和用戶異常用電識別[5]等領(lǐng)域。在解決此類問題的過程中，通常會遇到不平衡分類的問題，即真實數(shù)據(jù)集中兩類樣本數(shù)量差異巨大，且真實數(shù)據(jù)中含有大量噪聲樣本。傳統(tǒng)分類算法的預(yù)測目標是降低總體的分類錯誤率，為了提升整體的準確度，分類器更關(guān)注多數(shù)類，結(jié)果導(dǎo)致在測試集上的預(yù)測結(jié)果偏向為多數(shù)類，雖然整體準確度很高，但是沒有對少數(shù)類進行有效的預(yù)測。近年來，大量學(xué)者研究通過改變數(shù)據(jù)分布來解決不平衡分類問題，其中，過采樣(over-sampling)和欠采樣(under-sampling)是兩種最常用的技術(shù)[6]，典型的方法有隨機欠采樣技術(shù)、綜合小類過采樣技術(shù)(Synthetic Minority Over-sampling Technique,SMOTE)[7]和自適應(yīng)綜合過采樣(Adaptive Synthetic Sampling,ADASYN)[8]等。過采樣是一種對少數(shù)樣本進行擴充使得樣本數(shù)接近平衡的采樣方法，它雖然不會產(chǎn)生重復(fù)樣本，卻可能引入噪聲[9]，不適合用于含有較多噪聲的場景。盧曉勇等[3]提出用隨機欠采樣和隨機森林的方法檢測垃圾網(wǎng)頁，但隨機欠采樣方法僅僅通過抽樣的方式簡單平衡了類別并沒有考慮數(shù)據(jù)集中樣本“代表性”的問題，每個樣本以相同的概率被抽取。因此，本文先考慮樣本“代表性”的問題，基于孤立森林算法(Isolation Forest,iForest)計算多數(shù)類中每個樣本點的“孤立”程度，“孤立”程度一定程度上表示了樣本的“代表性”，越被“孤立”的樣本點“代表性”則越低；再通過優(yōu)先對“代表性”高的樣本進行采樣，然后將抽取的樣本和少數(shù)類合并構(gòu)建較平衡的訓(xùn)練數(shù)據(jù)集，以解決不平衡分類問題。

iForest算法[10]相比基于直方圖的異常得分算法(Histogram-based Outlier Score,HBOS)[11]和局部異常因子算法(Local Outlier Factor,LOF)[12]，iForest不要求特征間獨立且無需計算距離，速度較快，更適合企業(yè)異常用水模式檢測場景下特征之間存在相關(guān)性的低頻短時間序列數(shù)據(jù)。

獲得較平衡的訓(xùn)練數(shù)據(jù)集后，有監(jiān)督的機器學(xué)習(xí)方法可以更好地執(zhí)行預(yù)測的任務(wù)。本文利用XGBoost這一有監(jiān)督的機器學(xué)習(xí)方法對企業(yè)異常用水模式進行預(yù)測，XBGoost[13]是2016年由Chen提出的對梯度提升樹(Gradient Boosting Decision Tree,GBDT)算法的改進和實現(xiàn)，相比于傳統(tǒng)的GBDT只考慮了損失函一階的導(dǎo)數(shù)信息，XBGoost對損失函數(shù)進行了二階泰勒展開，還在目標函數(shù)中加入了正則項，有效地防止過擬合，具有效果好、速度快的優(yōu)點。在某市企業(yè)用水量數(shù)據(jù)集上的實驗表明，基于iForest采樣策略訓(xùn)練的XGBoost分類器可以提升企業(yè)異常用水模式的檢測效果。

1 孤立森林算法

iForest算法是一種無監(jiān)督的方法，該算法主要通過從訓(xùn)練數(shù)據(jù)集中隨機選取一個特征，在該特征的最大值最小值之間隨機選取一個分裂點，小于分裂點的進入左側(cè)分支，大于或等于分裂點的進入右側(cè)分支；不斷重復(fù)上述過程直到只剩一個樣本或相同樣本或達到樹的深度限制，然后通過路徑長度來表示一個樣本點被“孤立”的程度。路徑長度h(x)指樣本點x從根節(jié)點到外部節(jié)點所經(jīng)過的二叉樹的邊數(shù)，通常路徑長度較小的樣本被“孤立”的程度高。路徑長度h(x)的計算公式為

h(x)=e+C(T.size)

(1)

其中，e表示數(shù)據(jù)x從子樹(iTree)的根節(jié)點到葉節(jié)點過程中經(jīng)過的邊的數(shù)目，C(T.size)表示在一棵用T.size條樣本數(shù)據(jù)構(gòu)建的二叉樹的平均路徑長度。C(n)的計算公式為

(2)

其中，n為樣本個數(shù)，H(n-1)可用ln(i)+0.577 215 664 9(歐拉常數(shù))估算，以同樣的方式構(gòu)建包含多棵iTree，則樣本的“孤立”程度即可基于路徑長度被檢測出來，可以通過S(x,n)分值判斷。定義如下：

(3)

其中，E(h(x))是樣本點x在iForest中所有孤立樹的路徑長度的平均值，n表示單棵iTree的訓(xùn)練樣本數(shù)。

2 基于孤立森林采樣策略的企業(yè)異常用水模式檢測方法

基于iForest算法計算不平衡數(shù)據(jù)集中多數(shù)類樣本“代表性”得分，本文改進了對多數(shù)類樣本的采樣策略，優(yōu)先對多數(shù)類中樣本“代表性”得分高的樣本進行采樣，然后和少數(shù)類樣本構(gòu)建更加平衡的訓(xùn)練數(shù)據(jù)集。

假設(shè)將訓(xùn)練數(shù)據(jù)集U{(xi,yi)|(x1,y1),…,(xu,yu)}中樣本數(shù)較多的一類稱為多數(shù)類N{(xi,yi)|(x1,y1),…,(xu,yu)}，樣本數(shù)較少的一類稱為少數(shù)類S{(xi,yi)|(xl+1,yl+1),…,(xu,yu)}?；趇Forest的欠采樣方法首先計算多數(shù)類N中樣本的“孤立”程度得分scl，即樣本的“代表性”；再將多數(shù)類N中的樣本按照得分scl排序，以采樣比例k%從多數(shù)類N中按照排序抽取組成較平衡的訓(xùn)練數(shù)據(jù)集N′；最后將新的訓(xùn)練數(shù)據(jù)集N′和少數(shù)類S合并構(gòu)成較平衡的訓(xùn)練數(shù)據(jù)集U′；然后用XGBoost對較平衡的訓(xùn)練數(shù)據(jù)集U′分類訓(xùn)練，獲得分類器C；最后用分類器C對測試數(shù)據(jù)集T{xj|x1,…,xt}進行分類，得到測試數(shù)據(jù)集的分類結(jié)果L{yj|y1,…,yt}。

方法：基于iForest采樣策略的二分類預(yù)測方法。

輸入：

不平衡訓(xùn)練數(shù)據(jù)集及其分類U{(xi,yi)|(x1,y1),…,(xu,yu)}；

測試數(shù)據(jù)集T{xj|x1,…,xt}。

輸出：

測試數(shù)據(jù)集的分類L{yj|y1,…,yt}。

步驟：

1) 將不平衡訓(xùn)練數(shù)據(jù)集U按類別分為多數(shù)類N和少數(shù)類S；

2)n=多數(shù)類N的樣本數(shù)；

3)s=少數(shù)類S的樣本數(shù)；

4)k%=采樣比例；

5) 建立i棵子樹iTree，構(gòu)建iForest：

(1) 從訓(xùn)練數(shù)據(jù)集中隨機選擇n個樣本點，作為子樹的根節(jié)點；

(2) 如果當前樹的高度e超過設(shè)置高度h，則返回子樹；

(3) 否則，隨機選擇一個特征q；

(4) 隨機在特征q的最大值和最小值之間選擇切分點p；

(5) 將小于p的樣本放入左子節(jié)點，將大于p的樣本放入右子節(jié)點；

(6) 在子節(jié)點中遞歸步驟b-e；

6) 利用構(gòu)建好的iForest計算多數(shù)類中的樣本得分scl；

7) 對多數(shù)類N中每個樣本按照得分scl升序排序；

8) 抽取前k%的樣本組成新的樣本集合N′；

9) 將集合N′和小類S合并為平衡的數(shù)據(jù)集U′；

10) 使用XGBoost算法對數(shù)據(jù)集U′進行分類訓(xùn)練，得到分類器C；

11) 使用分類器C對測試數(shù)據(jù)集T進行預(yù)測，最終得到測試集的分類L。

3 實驗和實驗結(jié)果

3.1 數(shù)據(jù)集及評價指標

本文采用的數(shù)據(jù)集為某市7 604家企業(yè)13個月的用水量數(shù)據(jù)，數(shù)據(jù)采集間隔為1個月，其中正常企業(yè)為7 051家，標記為異常的樣本為553家，異常樣本占比約為7.3%。

通過以月和季度為周期構(gòu)造統(tǒng)計性特征，計算均值、方差、極差、偏度和峰度，并且通過對數(shù)差分的方式提取每兩個月之間企業(yè)用水量的波動特征，最終得到29維的特征。

本研究采用機器學(xué)習(xí)中常用的標準指標作為評價指標，主要有召回率(Recall)和AUC(Area Under ROC Curve)等。AUC值用來評價預(yù)測異常模式效果的好壞，召回率則用來評價分類器是否將異常模式“全面”的預(yù)測出來。

3.1.1 AUC

AUC[14]是指ROC(Receiver Operating Characteristic)曲線下方面積，AUC用一個數(shù)值來表示分類器效果的好壞，較大的AUC值表示較好的預(yù)測性能。AUC的范圍屬于(0.5,1.0)，0.5表示隨機預(yù)測的情況，1.0表示最理想的分類情況。

ROC曲線[15]所在平面的橫坐標是假正例率(False Positive Rate,FPR)，縱坐標是真正例率(True Positive Rate,TPR)。對某個分類器而言，根據(jù)其在測試樣本上的表現(xiàn)得到一個TPR和FPR點對。這樣，此分類器就可以映射成ROC平面上的一個點。調(diào)整這個分類器分類時候使用的閾值，我們就可以得到一個經(jīng)過(0,0)，(1,1)的曲線，這就是此分類器的ROC曲線。

TRP和FPR的計算公式為

(4)

(5)

其中，真正例(True Positive,TP)為被模型預(yù)測為正的正樣本；假負例(False Negative,FN)為被模型預(yù)測為負的正樣本；假正例(False Positive,FP)為被模型預(yù)測為正的負樣本；真負例(True Negative,TN)為被模型預(yù)測為負的負樣本。

3.1.2 查全率

上節(jié)計算TRP和FPR中提到，對于二分類問題，可以將樣本根據(jù)預(yù)測結(jié)果和真實類別組合劃分為TP、FN、FP和TN，查全率[14](Recall)表示在被預(yù)測為正例的樣本中有多少是真實的正例，計算公式為

(6)

3.2 實驗結(jié)果

計算樣本“代表性”的方法有多種，常用的無監(jiān)督方法有iForest、HBOS和LOF，LOF的特點是根據(jù)樣本局部的密度來計算樣本的得分，但是忽略樣本領(lǐng)域外的樣本對其產(chǎn)生的影響，HBOS假設(shè)每個特征獨立，將每個特征以直方圖的形式離散化，然后計算特征在離散區(qū)間上頻率的乘積作為樣本的得分，該方法簡單、快速，但是前提假設(shè)較強，當特征之間相關(guān)性較強時效果會受到影響，iForest通過樣本被“孤立”的程度作為樣本的得分，并且建立多顆相互獨立的子樹，綜合考慮多顆子樹的得分。本文分別測試該3種方法在該數(shù)據(jù)集的表現(xiàn)，如表1所示，綜合比較3種方法預(yù)測的AUC和查全率，選擇效果較好的iForest作為計算樣本“代表性”的方法。

表1 3種無監(jiān)督方法的預(yù)測效果Tab.1 Comparison of three unsupervised methods

為了構(gòu)造較平衡的訓(xùn)練集，需要確定從大類樣本中進行欠采樣的比例，本文分別對欠采樣比例從0到1進行實驗，作為對比，本文分別用XGBoost、基于隨機欠采樣的XGBoost和基于iForest的XGBoost方法對異常用水模式進行預(yù)測，得到的結(jié)果為十折交叉驗證后的AUC的平均值。

由圖1和表2可知，基于iForest的欠采樣的預(yù)測在采樣比例為0.2時效果最佳，AUC值達到0.927，基于隨機欠采樣的預(yù)測在采樣比例為0.7時最佳，AUC值為0.885，當不進行欠采樣處理時，預(yù)測結(jié)果的AUC值為0.877。由此可知，在該不平衡數(shù)據(jù)集下，若對訓(xùn)練集做隨機欠采樣可以提升預(yù)測效果，但是采樣過程為隨機抽取，若數(shù)據(jù)集中含有較多“噪音”或是潛在未被標注的異常樣本，會被等概率抽取進入訓(xùn)練數(shù)據(jù)集，從而影響分類器的訓(xùn)練，因此提升效果并不顯著，而基于iForest采樣策略針對“代表性”高的樣本進行優(yōu)先抽取，一定程度上優(yōu)先避開了“噪音”樣本，故預(yù)測結(jié)果比基于隨機欠采樣的AUC提升了約4.7%，查全率提升了21.6%。結(jié)果說明，本文提出的企業(yè)異常用水模式檢測方法在考慮樣本“代表性”后進行欠采樣可以提升預(yù)測效果。

圖1 不同采樣比例下XGBoost的預(yù)測效果對比Fig.1 Comparison of XGBoost in different sampling proportion

表2 不同采樣方式下XGBoost的預(yù)測效果Tab.2 Result of XGBoost in different sampling methods

為進一步驗證在類似場景下該方法的有效性，本文還在社交網(wǎng)絡(luò)的場景下利用該方法進行了實驗，該數(shù)據(jù)集為某社交網(wǎng)絡(luò)上用戶的活躍度數(shù)據(jù)，數(shù)據(jù)采集間隔為周，連續(xù)采集了14周的用戶活躍度數(shù)據(jù)，該數(shù)據(jù)集共有3 099位用戶，其中普通用戶數(shù)為2 790位，非普通用戶數(shù)為309位，約占總樣本的10%?；陔S機欠采樣方法的預(yù)測結(jié)果的AUC值為0.669，查全率為0.805；基于iForest采樣策略的預(yù)測結(jié)果的AUC值為0.901，查全率為0.850，相較于基于隨機欠采樣的方法，AUC值提升了34.7%，召回率提了5.6%。結(jié)果說明，該方法在社交網(wǎng)絡(luò)場景下也具有一定的有效性。

4 總結(jié)

本文提出的基于iForest采樣策略的方法在企業(yè)異常用水模式檢測場景中，面對不平衡分類問題取得了較好的效果。首先基于iForest算法計算多數(shù)類中樣本點的“孤立”程度，通過“孤立”程度衡量樣本“代表性”，然后按樣本“代表性”得分進行排序，從“代表性”高的樣本中優(yōu)先進行欠采樣，然后與少數(shù)類樣本構(gòu)成較平衡的訓(xùn)練數(shù)據(jù)集，訓(xùn)練XGBoost分類器，最后對企業(yè)異常用水模式進行預(yù)測。在某市的企業(yè)用水量數(shù)據(jù)集上，該方法對企業(yè)異常用水模式的預(yù)測結(jié)果AUC值和查全率可達到0.927和0.891，較基于隨機欠采樣的方法的0.884和0.733分別提升了4.7%和21.6%。另外，本文還在社交網(wǎng)絡(luò)場景下利用該方法進行實驗，同樣也具有一定的有效性。未來的研究可以進一步探索在其他類似不平衡分類的場景下該方法的預(yù)測效果。