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

聞明 竇晨

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

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

1 基于自動(dòng)化算法的監(jiān)控?cái)?shù)據(jù)異常檢測(cè)

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

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

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

2 對(duì)算法的改進(jìn)

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

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

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

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

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

圖1 新算法流程圖

表1 新舊算法基準(zhǔn)測(cè)試結(jié)果

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

最后的異常分?jǐn)?shù)可以對(duì)局部異常分?jǐn)?shù)取平均得到

給定數(shù)據(jù)集的所有數(shù)據(jù)點(diǎn)的異常分?jǐn)?shù)被計(jì)算出來(lái)以后可以根據(jù)異常分?jǐn)?shù)從高到低排列，這個(gè)排名表示了數(shù)據(jù)點(diǎn)在數(shù)據(jù)集中的異常分?jǐn)?shù)排名。

3 服務(wù)器端的設(shè)計(jì)與實(shí)現(xiàn)

算法智能分析平臺(tái)的開(kāi)發(fā)過(guò)程如下：

（1）搭建Hadoop分布式機(jī)器學(xué)習(xí)平臺(tái)，從數(shù)據(jù)庫(kù)中加載已有的監(jiān)控?cái)?shù)據(jù)，對(duì)監(jiān)控?cái)?shù)據(jù)進(jìn)行數(shù)據(jù)預(yù)處理，數(shù)據(jù)存入HBase。

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

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

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

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

算法樹(shù)構(gòu)建成功后，將樣本代入公式計(jì)算樣本相對(duì)于鄰域的相對(duì)質(zhì)量。這里在編程上需要對(duì)每個(gè)樣本遍歷算法樹(shù)計(jì)算出樣本相對(duì)于所有算法樹(shù)的異常分。這里因?yàn)榭梢圆⑿谢梢猿浞职l(fā)揮Hadoop自動(dòng)并行化加速的特性，提高算法實(shí)現(xiàn)的性能。

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

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

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

以AUC為指標(biāo)的話，新算法和孤立森林相比效果類(lèi)似。大部分?jǐn)?shù)據(jù)集都不包含局部異常點(diǎn)，因此這兩種算法的AUC都是類(lèi)似的。我們也測(cè)試了MinPts=5時(shí)的孤立森林算法，并不會(huì)提高孤立森林算法的成績(jī)。

從運(yùn)行時(shí)間來(lái)看，新算法要顯著好于孤立森林算法。這是因?yàn)樾滤惴ǖ母。a(chǎn)生的樹(shù)比孤立森林要小很多，所以即使參數(shù)相同新算法也會(huì)比孤立森林快。