孤立森林算法在智能監(jiān)控中的應用

聞明 竇晨

(北京科技大學天津?qū)W院 天津 301830)

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

1 基于自動化算法的監(jiān)控數(shù)據(jù)異常檢測

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

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

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

2 對算法的改進

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

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

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

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

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

圖1 新算法流程圖

表1 新舊算法基準測試結(jié)果

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

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

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

3 服務器端的設計與實現(xiàn)

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

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

（2）使用Python 編寫異常檢測算法的實現(xiàn)，對HBase中的數(shù)據(jù)進行分析。該過程需要對算法具體實現(xiàn)的參數(shù)進行調(diào)優(yōu)。分析完成的結(jié)果寫入數(shù)據(jù)庫。

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

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

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

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

4 實驗結(jié)果

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

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

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

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