孤立森林算法研究及并行化實(shí)現(xiàn)

王 誠，狄 萱

(南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210003)

0 引 言

異常檢測是近年來數(shù)據(jù)挖掘中熱門的研究課題之一，被廣泛應(yīng)用于醫(yī)保欺詐[1]、網(wǎng)絡(luò)入侵[2]、醫(yī)療診斷[3]等領(lǐng)域。隨著物聯(lián)網(wǎng)、云計(jì)算等技術(shù)的不斷發(fā)展，數(shù)據(jù)量日漸增長，傳統(tǒng)單機(jī)版異常檢測算法難以對大規(guī)模數(shù)據(jù)進(jìn)行高效檢測。因此，針對大規(guī)模數(shù)據(jù)設(shè)計(jì)相應(yīng)算法，具有重要的應(yīng)用價值。近年來，已有的異常檢測算法分為三類，分別是基于統(tǒng)計(jì)[4]、密度[5]和聚類[6]的算法。Liu等[7-8]提出的孤立森林算法，通過計(jì)算測試數(shù)據(jù)在已構(gòu)建的孤立森林模型下的平均路徑長度代入公式求其異常值，該算法大大減少了計(jì)算時間，適用于高維數(shù)據(jù)。Liao等[9]提出一種基于信息熵的改進(jìn)孤立森林算法，該算法通過計(jì)算數(shù)據(jù)集中各個特征下的信息熵，優(yōu)先選擇信息熵小的特征作為切割特征，并且改進(jìn)了路徑長度的計(jì)算公式，對噪聲特征具有較強(qiáng)的抵抗性。Yang等[10]提出了一種基于孤立的嵌入式無監(jiān)督特征選擇(IBFS)算法，該算法通過計(jì)算孤立森林在訓(xùn)練過程中每個特征的得分，選出表現(xiàn)優(yōu)異的特征集合進(jìn)行異常檢測，提高了異常檢測精度。Yong等[11]根據(jù)Hadoop平臺業(yè)調(diào)度機(jī)制和孤立森林算法的思想，將孤立森林算法的模型構(gòu)建和異常預(yù)測兩個過程進(jìn)行了并行化設(shè)計(jì)，但其運(yùn)算過程中需要多個MapReduce操作完成并行運(yùn)算，多次讀寫硬盤，耗費(fèi)大量時間。

孤立森林算法異常檢測不需要計(jì)算距離和密度，避免了大量的計(jì)算，因此能夠更好地支持高維數(shù)據(jù)的異常檢測，同時孤立森林的每棵孤立二叉樹的構(gòu)建過程都是獨(dú)立的，能夠利用分布式平臺對孤立森林算法進(jìn)行并行化設(shè)計(jì)。孤立森林算法存在一些不足之處：

(1)在深入研究孤立森林算法過程中發(fā)現(xiàn)，孤立森林算法在計(jì)算測試樣本的異常值時，計(jì)算的是測試樣本在孤立森林的平均路徑長度，而孤立森林算法的核心思想是：在一棵孤立二叉樹中，若某個葉子節(jié)點(diǎn)的路徑長度短，則認(rèn)為該節(jié)點(diǎn)是異常點(diǎn)。當(dāng)某棵孤立二叉樹沒有相對短的路徑的葉子節(jié)點(diǎn)時，則說明其難以區(qū)分異常點(diǎn)。

(2)Yong等[11]指出，孤立森林算法異常檢測的精度與孤立二叉樹的數(shù)量有關(guān)，隨著數(shù)據(jù)量的增多，所需構(gòu)建孤立二叉樹的數(shù)量也相應(yīng)增多，從而導(dǎo)致耗費(fèi)大量內(nèi)存和時間，影響算法效率。

針對第一點(diǎn)不足，對孤立森林中每棵孤立二叉樹的路徑長度的標(biāo)準(zhǔn)差進(jìn)行歸一化加權(quán)，計(jì)算異常值。若標(biāo)準(zhǔn)差大，則說明該棵孤立二叉樹中各葉子節(jié)點(diǎn)間的路徑長度差異大，具有較好的異常檢測能力，應(yīng)賦予較高的權(quán)值，否則賦予較低的權(quán)值。通過加權(quán)計(jì)算測試樣本在孤立森林的異常值，以提高異常檢測的精確度。針對第二點(diǎn)不足，利用Spark平臺實(shí)現(xiàn)改進(jìn)算法的并行化。Spark平臺是基于內(nèi)存設(shè)計(jì)的，避免了Hadoop平臺MapReduce操作需要頻繁讀寫磁盤，能夠加快整體的異常檢測速度。

1 相關(guān)工作

1.1 孤立森林算法

孤立森林是由多棵孤立二叉樹組成的，孤立二叉樹的構(gòu)建過程是算法的核心，孤立二叉樹的構(gòu)建過程如下：

(1)從數(shù)據(jù)集D中隨機(jī)選擇m個樣本點(diǎn)作為生成本棵孤立二叉樹的樣本集Ds。

(2)從樣本集Ds中隨機(jī)選擇一個特征f和一個切割值p。若節(jié)點(diǎn)N包含的所有樣本在特征f下的最大值和最小值分別為f_max和f_min，則有p∈[f_min,f_max]。

(3)若樣本的特征f的值小于切割值p，則將該樣本分到節(jié)點(diǎn)N的左孩子；否則，分到右孩子。

(4)重復(fù)(2)、(3)兩步，分別對節(jié)點(diǎn)N的左右孩子節(jié)點(diǎn)進(jìn)行切分，生成孤立二叉樹。當(dāng)孩子節(jié)點(diǎn)中有多條相同的數(shù)據(jù)或只有一條數(shù)據(jù)或孤立二叉樹已達(dá)到設(shè)置的最大高度時，停止生成孤立二叉樹。

(5)孤立森林最終由用戶指定數(shù)目的孤立二叉樹組成。根據(jù)樣本點(diǎn)d在每棵孤立二叉樹中的路徑長度h(d)，利用公式(1)計(jì)算d的異常值，從而評價其異常情況。

(1)

1.2 Spark大數(shù)據(jù)計(jì)算框架

Spark[12-13]是加州大學(xué)伯克利分校的AMP實(shí)驗(yàn)室開發(fā)的一款基于內(nèi)存的并行分布式計(jì)算框架。相較于Hadoop框架中的分布式計(jì)算模塊MapReduce需要頻繁讀寫磁盤I/O操作，Spark框架基于內(nèi)存的設(shè)計(jì)，將每一輪的輸出結(jié)果都緩存在內(nèi)存中，避免了從HDFS中讀取數(shù)據(jù)，更適合需要多次迭代的算法。Spark的運(yùn)行架構(gòu)模型如圖1所示，其基本運(yùn)行流程是：

圖1 Spark運(yùn)行架構(gòu)模型

(1)Spark在驅(qū)動節(jié)點(diǎn)Driver端運(yùn)行main()方法并創(chuàng)建SparkContext以構(gòu)建Spark Application的運(yùn)行環(huán)境，創(chuàng)建完成后的SparkContext向資源管理器Cluster Manager申請所需要的CPU、內(nèi)存等資源并申請運(yùn)行多個執(zhí)行節(jié)點(diǎn)Executor，Cluster Manager分配并啟動各個Executor。

(2)SparkContext構(gòu)建有向無環(huán)圖DAG以反映彈性分布式數(shù)據(jù)集RDD之間的依賴關(guān)系，并將其分解成任務(wù)集TaskSet發(fā)送給有向無環(huán)圖調(diào)度器TaskScheduler。

(3)各Executor向SparkContext申請Task，TaskScheduler將Task分發(fā)給各個Executor，同時SparkContext將打好的程序Jar包發(fā)送給各個Executor，各Executor執(zhí)行結(jié)束后將結(jié)果收集給Driver端[14]，最終釋放資源。

2 改進(jìn)孤立森林算法的并行化實(shí)現(xiàn)

2.1 加權(quán)孤立森林的構(gòu)建算法

如公式(1)所示，孤立森林在計(jì)算測試樣本異常值時，計(jì)算的是測試樣本在孤立森林的平均路徑長度，忽略了各孤立二叉樹的異常檢測能力的差異性，即每個葉子節(jié)點(diǎn)的路徑都很長的孤立二叉樹難以區(qū)分異常點(diǎn)，而具有短路徑的葉子節(jié)點(diǎn)的孤立二叉樹能夠更好地區(qū)分異常點(diǎn)。如圖2和圖3所示，圖2的孤立二叉樹比圖3的孤立二叉樹具有更強(qiáng)的區(qū)分異常點(diǎn)的能力。因此該文通過計(jì)算每棵孤立二叉樹的路徑長度標(biāo)準(zhǔn)差對具有更強(qiáng)區(qū)分異常點(diǎn)能力的樹進(jìn)行加權(quán)，同時減小區(qū)分異常點(diǎn)能力較差的樹的權(quán)值。

圖2 區(qū)分異常能力強(qiáng)的孤立二叉樹

圖3 區(qū)分異常能力差的孤立二叉樹

若一棵孤立二叉樹的葉子節(jié)點(diǎn)集合為Node={node1,node2,…,noden}，葉子節(jié)點(diǎn)的路徑長度集合為Hnode={h1,h2,…,hn}，則該棵樹的路徑長度標(biāo)準(zhǔn)差σ的計(jì)算公式為：

(2)

其中，n為葉子節(jié)點(diǎn)的總個數(shù)，μ為該棵樹所有葉子節(jié)點(diǎn)路徑長度的均值。

若孤立森林中所有孤立二叉樹的路徑長度標(biāo)準(zhǔn)差集合為σ={σ1,σ2,…,σn}，其中最大值為σmax，最小值為σmin，對路徑長度標(biāo)準(zhǔn)差集合進(jìn)行歸一化，公式為：

(3)

若數(shù)據(jù)集D中每個樣本點(diǎn)d在每棵孤立二叉樹中的路徑長度為集合Hd={h1,h2,…,hn}，孤立二叉樹的權(quán)重集W={w1,w2,…,wn}，則樣本點(diǎn)d的異常值計(jì)算公式為：

(4)

具體算法實(shí)現(xiàn)如下：

算法1：加權(quán)孤立森林的構(gòu)建算法。

輸出：孤立森林，權(quán)重集W。

(1)對數(shù)據(jù)集D進(jìn)行隨機(jī)采樣，抽取m個數(shù)據(jù)放入集合Ds中。

(2)調(diào)用孤立二叉樹生成算法，并傳入相關(guān)參數(shù)，生成單棵孤立二叉樹。

(3)利用公式(2)計(jì)算當(dāng)前生成的孤立二叉樹的路徑長度標(biāo)準(zhǔn)差。

(4)重復(fù)1、2兩步，直到生成n棵孤立二叉樹及路徑長度標(biāo)準(zhǔn)差集合。

(5)利用公式(3)對路徑長度標(biāo)準(zhǔn)差集合進(jìn)行歸一化，生成權(quán)重集W。

(6)返回由n棵孤立二叉樹組成的孤立森林及權(quán)重集W。

算法2：樣本點(diǎn)異常值計(jì)算流程。

輸入：數(shù)據(jù)集D，權(quán)重集W；

輸出：數(shù)據(jù)集D的異常值集N。

(1)計(jì)算數(shù)據(jù)集D中每個樣本點(diǎn)在每棵孤立二叉樹中的路徑長度集合Hd。

(2)利用公式(4)，加權(quán)計(jì)算每個樣本點(diǎn)的異常值，并合為異常值集N。

(3)返回?cái)?shù)據(jù)集D的異常值集N。

2.2 改進(jìn)孤立森林算法的并行化設(shè)計(jì)

該文利用Spark平臺實(shí)現(xiàn)改進(jìn)孤立森林算法的并行化。主要步驟包括：數(shù)據(jù)抽樣、模型構(gòu)建和異常預(yù)測。整體框架如圖4所示。

圖4 改進(jìn)孤立森林算法并行化框架

(1)數(shù)據(jù)抽樣。

單機(jī)版的孤立森林算法需要對原始數(shù)據(jù)集進(jìn)行隨機(jī)抽樣，利用抽樣后的數(shù)據(jù)集生成孤立二叉樹。而Spark平臺數(shù)據(jù)存儲核心RDD是分布式數(shù)據(jù)集，如果直接對各個分區(qū)的數(shù)據(jù)進(jìn)行定量隨機(jī)抽樣，不能保證抽樣后得到的數(shù)據(jù)集是全局隨機(jī)的。雖然Spark提供了sample抽樣算子，但會導(dǎo)致非確定性大小的采樣樣本集。因此，該文設(shè)計(jì)從HDFS中讀取數(shù)據(jù)文件，轉(zhuǎn)化成RDD記為RDD_data，在Driver端首先利用count算子計(jì)算RDD_data數(shù)據(jù)總量，創(chuàng)建RandomData-Generator類，根據(jù)RDD_data數(shù)據(jù)總量、孤立二叉樹數(shù)量、隨機(jī)采樣樣本數(shù)量，隨機(jī)生成包含行號索引值的二維數(shù)組，并將其映射為(rowId(行號),treeIdArray(該行數(shù)據(jù)對應(yīng)的孤立二叉樹ID集合))的格式，最后將該形式的變量廣播到各個Executor端，以減少Shuffle成本。利用zipWithIndex算子，為RDD_data添加全局索引號，在各個Executor端利用廣播來的變量中的行號對RDD_data數(shù)據(jù)內(nèi)容篩選過濾，并通過flatMap、reduceByKey算子生成(treeId(孤立二叉樹ID),ContentArray(構(gòu)建此ID孤立二叉樹所需的數(shù)據(jù)集))格式的數(shù)據(jù)集：RDD_sample。

(2)模型構(gòu)建。

將RDD_sample數(shù)據(jù)集map到各個Executor端進(jìn)行孤立二叉樹的并行同步構(gòu)建并計(jì)算各個孤立二叉樹的路徑長度標(biāo)準(zhǔn)差，數(shù)據(jù)格式分別為：(treeId(孤立二叉樹ID)，tree(孤立二叉樹))、(treeId(孤立二叉樹ID)，stdPath(路徑長度標(biāo)準(zhǔn)差))。利用collect算子將多棵孤立二叉樹及各自的路徑長度標(biāo)準(zhǔn)差收集到Driver端，并將多棵樹的路徑長度標(biāo)準(zhǔn)差合并歸一化成一個數(shù)據(jù)格式為(treeId(孤立二叉樹ID),weight(權(quán)重))的權(quán)重集。最后將構(gòu)建好的模型及權(quán)重集分別存入RDD_model和RDD_weight中。

(3)異常預(yù)測。

將構(gòu)建好的模型RDD_model廣播給各個Executor，測試數(shù)據(jù)集并行遍歷每一棵孤立二叉樹，得到每一個測試數(shù)據(jù)樣本在模型下的路徑長度集合，集合中元素的數(shù)據(jù)格式為(treeId(孤立二叉樹ID)，pathLength(路徑長度))，利用權(quán)重集RDD_weight對每一個測試數(shù)據(jù)樣本的路徑長度集合進(jìn)行加權(quán)計(jì)算，得到每一個測試數(shù)據(jù)樣本的異常值，從而評價其異常情況。

3 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

3.1 實(shí)驗(yàn)數(shù)據(jù)集

實(shí)驗(yàn)數(shù)據(jù)集選取自威斯康星州數(shù)據(jù)集Breastw、UCI數(shù)據(jù)集Shuttle和KDD CUP 99數(shù)據(jù)集Http[15]，數(shù)據(jù)集的具體信息如表1所示。

表1 數(shù)據(jù)集具體信息

3.2 異常檢測精確度

該文使用表1中的三個數(shù)據(jù)集對三種算法進(jìn)行實(shí)驗(yàn)對比分析。其中，三個算法的參數(shù)均為：孤立二叉樹數(shù)量n=100，隨機(jī)采樣樣本數(shù)量m=256，樹的高度限制l=8。采用ROC曲線下的面積AUC指標(biāo)來評價算法異常檢測精確度。AUC值的范圍為[0,1]，其值越接近1則說明算法的檢測效果越好。具體的實(shí)驗(yàn)結(jié)果如表2所示。

表2 三種算法的AUC值

從表2中可以看出,對于Breastw、Shuttle和Http三個數(shù)據(jù)集，改進(jìn)孤立森林算法相對于原始孤立森林算法的AUC值分別提高了2.22%、2.51%、1.65%，這是因?yàn)楦倪M(jìn)孤立森林算法改進(jìn)了異常值計(jì)算公式，為高異常檢測能力的孤立二叉樹賦予更高的權(quán)值，從而讓異常點(diǎn)更為突出。并行化改進(jìn)孤立森林算法與改進(jìn)孤立森林算法的AUC值沒有明顯差異，因此并行化改進(jìn)孤立森林算法在異常檢測精度上能與改進(jìn)孤立森林算法保持一致。同時，改進(jìn)孤立森林算法由于需要計(jì)算路徑長度標(biāo)準(zhǔn)差并歸一化為權(quán)重集，相對于原始孤立森林算法增加了些許時間開銷，但在小規(guī)模數(shù)據(jù)集上可以忽略不計(jì)。并行化改進(jìn)孤立森林算法相較于單機(jī)的改進(jìn)孤立森林算法耗費(fèi)了更多的時間，這是由于數(shù)據(jù)規(guī)模小時，集群初始化、任務(wù)調(diào)度及節(jié)點(diǎn)間的數(shù)據(jù)通信時間遠(yuǎn)大于算法本身的運(yùn)算時間。

3.3 并行性能實(shí)驗(yàn)

實(shí)驗(yàn)環(huán)境是基于Spark平臺的計(jì)算集群，該集群共有4個節(jié)點(diǎn)，每個節(jié)點(diǎn)的CPU核數(shù)為1核，內(nèi)存為2 G，硬盤為30 G，Java版本為1.8.0，Scala版本為2.11.0，Hadoop版本為2.7.6，Spark版本為2.4.0。實(shí)驗(yàn)數(shù)據(jù)集是由Breastw數(shù)據(jù)集構(gòu)造的行數(shù)為100萬行、300萬行、500萬行、800萬行的大規(guī)模數(shù)據(jù)集。分別對這四個大規(guī)模數(shù)據(jù)集進(jìn)行對比實(shí)驗(yàn)，其中自變量為孤立二叉樹數(shù)目，分別為100棵、200棵、300棵、400棵、500棵。同時計(jì)算當(dāng)孤立二叉樹數(shù)量為100時，改進(jìn)孤立森林算法在Spark集群下的加速比，評價其并行性能。實(shí)驗(yàn)結(jié)果如圖5～圖6所示。

從圖5中可以看出，在不同數(shù)據(jù)規(guī)模下，隨著孤立二叉樹數(shù)目的不斷增加，單機(jī)和并行化的孤立森林算法的運(yùn)行時間都呈線性增加，單機(jī)算法的增幅更陡峭，并行算法的增幅平緩。當(dāng)數(shù)據(jù)量達(dá)到800萬行、孤立二叉樹數(shù)目為500棵時，單機(jī)運(yùn)行時間是并行化后的運(yùn)行時間的4.34倍。從圖6中可以看出并行化改進(jìn)孤立森林算法總體上有很好的加速比。隨著數(shù)據(jù)量的不斷增大，加速比隨著節(jié)點(diǎn)數(shù)的增加而明顯增大，當(dāng)數(shù)據(jù)量達(dá)到800萬行、節(jié)點(diǎn)數(shù)為4時，加速比提升到了2.88。因此，并行化改進(jìn)孤立森林算法能夠更高效地處理需要構(gòu)建大量孤立二叉樹的大規(guī)模數(shù)據(jù)集。

圖5 不同規(guī)模數(shù)據(jù)集下運(yùn)行時間對比

圖6 100棵孤立二叉樹下的加速比

4 結(jié)束語

該文針對孤立森林算法在計(jì)算測試樣本的異常值時，忽略了孤立二叉樹間檢測異常能力差異性以及大規(guī)模數(shù)據(jù)下構(gòu)建大量孤立二叉樹需要耗費(fèi)大量內(nèi)存時間這兩點(diǎn)不足進(jìn)行改進(jìn)，加權(quán)計(jì)算測試樣本在孤立森林中的異常值并基于Spark平臺設(shè)計(jì)實(shí)現(xiàn)并行化改進(jìn)孤立森林算法。通過多個對比實(shí)驗(yàn)結(jié)果表明，并行化改進(jìn)孤立森林算法能夠加快大規(guī)模數(shù)據(jù)集下的異常檢測速度，同時提高了異常檢測精度。下一步將把該算法與實(shí)際應(yīng)用場景相結(jié)合，檢驗(yàn)其實(shí)際應(yīng)用價值。