孤立森林算法在智能監控中的應用

聞明 竇晨

(北京科技大學天津學院 天津 301830)

傳統的人工盯盤監控數據的方式效率不僅低下，還對應著巨大的人力成本。而現存的監控數據自動監控需要管理員去挨個配置各個環境數據的合理范圍，超出合理范圍的會觸發告警系統。但管理員對數據的合理波動范圍往往并不全都清楚，隨著監控設備的陡增，這項工作量也變得非常大，異常檢測平臺和告警容易被旁置。況且，由于傳感器質量問題，現場安裝問題的廣泛存在，這些監控數據存在著不準確、失真等多種問題，光是設定閾值很難將自動監控平臺派上用場，這就需要我們采用機器學習算法、深度學習算法等技術對數據進行清洗、分析和歸類。因為學習算法中涉及了大量的統計學理論，機器學習與推斷統計學聯系尤為密切，也被稱為統計學習理論[3]。

1 基于自動化算法的監控數據異常檢測

數據挖掘類的任務如異常檢測和信息檢索需要定義度量。最常見的度量是基于距離和密度的，大多數現有的工作都是基于這些度量對工程中的實例進行排序。但是這些方法有一個問題，就是它的計算成本很高，特別是在大數據情形下計算成本很高，隨著維度的上升計算要求的性能飆升。

孤立森林(Isolation Forest)是一種新穎的無監督學習算法，用于判斷數據集內是否存在異常點，由Fei Tony Liu及周志華等于2008年提出[4]。它使用的度量不依賴于距離和密度計算。它的基本思想是將給定的數據集中的每個對象與其他對象隔離開來。因為異常點具有兩個特征，一個是少，另一個是異常。所以他們比正常的數據更容易在數結構中被隔離。因此，異常點的平均路徑長度比孤立樹集合上的其他正常對象的平均路徑長度更短。

孤立森林在工程中的實踐經過時間的考驗已經被證明是一個良好的算法。但是，我們在開發的過程中發現它有一些缺陷。我們改進的一個缺陷是，當數據集包含多個正常點簇，用原始的孤立森林算法不易將異常數據分離出來。造成這種缺陷的原因是當數據集包含多個正常點簇時，局部的異常點容易被密度相似的正常點簇掩蓋，導致它不太容易被孤立森林算法隔離。

2 對算法的改進

考慮了孤立森林算法和它在探測局部異常點方面的缺陷以后，我們提出了以下的新算法，它可以通過計算相對質量克服孤立森林的缺點。

在傳統的孤立森林算法中，使用的是基于路徑長度的全局排名度量，我們改為使用基于數據點在本地鄰域的相對質量的本地排名度量來對數據點進行排名。在樹結構中，數據點的相對質量是通過數據點從根節點到葉節點的路徑上的兩個節點的質量比來計算的。計算相對質量時使用的兩個節點取決于任務的具體要求。

在異常檢測中，我們采用的新算法只考慮x相對于它的鄰域的相對質量。相對質量計算的方式為x所在的直接父節點和它的直接葉節點的質量比。

在每個孤立森林樹Ti中，一個數據點x相對于它的鄰域的異常分數si(x)可以被這個公式估計：

其中Ti(x)是x所在的樹Ti的葉子節點，是的直接節點，m(·)是樹節點的質量，是正則化參數，等于用于訓練Ti的數據集的大小。

圖1 新算法流程圖

表1 新舊算法基準測試結果

si(·)的值域為(0,1]。這個分數越高，x越有可能是一個異常點。與原本的孤立森林中的路徑長度分數相比，si(x)衡量了一個數據點在局部的異常程度。

最后的異常分數可以對局部異常分數取平均得到

給定數據集的所有數據點的異常分數被計算出來以后可以根據異常分數從高到低排列，這個排名表示了數據點在數據集中的異常分數排名。

3 服務器端的設計與實現

算法智能分析平臺的開發過程如下：

（1）搭建Hadoop分布式機器學習平臺，從數據庫中加載已有的監控數據，對監控數據進行數據預處理，數據存入HBase。

（2）使用Python 編寫異常檢測算法的實現，對HBase中的數據進行分析。該過程需要對算法具體實現的參數進行調優。分析完成的結果寫入數據庫。

（3）最后分析結果由監控數據展示平臺的前端拉取展示，告警平臺的程序定時拉取數據篩選出等級較為嚴重的日志發送到管理員的郵箱中。

由于Hadoop本身并沒有支持我們設計的新算法，所以我們設計了程序使這個算法支持Hadoop。新算法的大致流程如圖1。其中n是算法樹的數量，max是每棵算法樹的采樣數量。

Hadoop 分布式計算算法樹包括：對數據集隨機采樣不放回，并行構建算法樹和并行計算數據點相對于鄰域的異常分數，最后綜合異常分數計算異常分數平均值。對數據集進行隨機采樣且不放回的實現是：將數據集讀入內存構建為HBase要求的格式，用指標索引數據集中的樣本，加速下一步訪問。用Linux的/dev/urandom 取隨機數作為numpy 的隨機數生成器的種子，取出大小為n*max 的樣本集，然后調用numpy API廣播隨機樣本集，最后用孤立森林算法構建算法樹。

算法樹構建成功后，將樣本代入公式計算樣本相對于鄰域的相對質量。這里在編程上需要對每個樣本遍歷算法樹計算出樣本相對于所有算法樹的異常分。這里因為可以并行化可以充分發揮Hadoop自動并行化加速的特性，提高算法實現的性能。

4 實驗結果

在實驗和測試方面我們測試比對了孤立森林算法和新算法在探測異常點任務上的表現。實驗中我們統一采用無監督學習的配置。數據集上的標簽不會參與模型訓練過程。標簽僅用于評估模型的運行效果。異常點探測任務的效果評估我們用AUC這個指標衡量。ROC曲線是一個用來說明二進制分類器系統的區分能力的曲線，橫坐標為它的區分閾值。AUC 是ROC曲線下面積。最后我們會計算標準差來檢查孤立森林和新算法之間的差別是否顯著。

我們用了十個基準測量數據集[1]分別用孤立森林算法和我們改進的新算法進行了測試。我們將參數t默認值設置為100，最佳子樣本數量設置為在8，16，32，64，128到256之間搜索。新算法的MinPts 參數的默認值設置為5。孤立森林算法的MinPts參數設置為1，這是隨機森林算法的默認設定[1]。基準測試的結果見表格1，其中NA是我們的新算法。

以AUC為指標的話，新算法和孤立森林相比效果類似。大部分數據集都不包含局部異常點，因此這兩種算法的AUC都是類似的。我們也測試了MinPts=5時的孤立森林算法，并不會提高孤立森林算法的成績。

從運行時間來看，新算法要顯著好于孤立森林算法。這是因為新算法的更小，產生的樹比孤立森林要小很多，所以即使參數相同新算法也會比孤立森林快。