基于并行深度孤立森林算法的水質(zhì)異常數(shù)據(jù)檢測

王海龍，李東波，吳紹鋒

(南京理工大學(xué)機械工程學(xué)院，江蘇 南京 210094)

水作為人類賴以生存的資源，其質(zhì)量對人類本身和人類社會的良好發(fā)展有著很大的影響。隨著我國經(jīng)濟不斷發(fā)展，人民對于水資源的質(zhì)量要求也日益提高，如何嚴(yán)格把關(guān)水質(zhì)以保證人民良好的生活需要和基本利益是各級政府面臨的一個難題。

傳統(tǒng)水質(zhì)異常檢測算法經(jīng)常采用閾值，試圖發(fā)現(xiàn)那些不屬于正常區(qū)域的異常點，即根據(jù)經(jīng)驗或者數(shù)據(jù)內(nèi)容定義一個范圍[n,k]，取值不在該范圍的即是異常數(shù)據(jù)，這種基于閾值的方法看似簡單，但是往往是不準(zhǔn)確的，原因如下：1)一類事物往往是具有多特征的，類別的判定應(yīng)是基于各個特征的共同計算得到的，而不是簡單的基于某一特征；2)異常數(shù)據(jù)和正常數(shù)據(jù)間的界限往往不精確；3)閾值判斷不一定適用每一個水域，同時正常的數(shù)據(jù)根據(jù)時間和其他因素影響也是不斷發(fā)展的，目前的正常概念可能隨著時間推移將不再適用。

目前，國內(nèi)外很多學(xué)者已經(jīng)采用了大量的水質(zhì)異常數(shù)據(jù)檢測方法實現(xiàn)水質(zhì)異常數(shù)據(jù)的檢測：Byer[1]假設(shè)水質(zhì)指標(biāo)服從高斯分布，計算得到樣本數(shù)據(jù)的平均值與方差，將實際監(jiān)測到的每個時間點上水質(zhì)指標(biāo)數(shù)據(jù)測量值與樣本水質(zhì)指標(biāo)數(shù)據(jù)時間序列的平均值進行比較，如果差值的絕對值大于樣本數(shù)據(jù)的3倍方差，則當(dāng)前水質(zhì)被判定異常；Conde[2]利用人工神經(jīng)網(wǎng)絡(luò)等機器學(xué)習(xí)相關(guān)算法，結(jié)合監(jiān)測站點的水質(zhì)指標(biāo)數(shù)據(jù)信息進行建模，通過訓(xùn)練生成分類器來在線判別水質(zhì)是否正常。

在當(dāng)前的信息化時代，水質(zhì)數(shù)據(jù)通過物聯(lián)網(wǎng)傳輸至平臺，隨著數(shù)據(jù)不斷地產(chǎn)生，上述基于統(tǒng)計和神經(jīng)網(wǎng)絡(luò)的方法盡管可靠性較高，但是計算繁瑣、效率較低，不適用于對實時性要求較高的水質(zhì)異常數(shù)據(jù)檢測[3]。

為了解決上述問題，本文引入了孤立森林算法和深度孤立森林算法。孤立森林算法是一種高效的異常檢測算法，它利用異常點數(shù)量少、異常數(shù)據(jù)特征值和正常數(shù)據(jù)差別大兩個特點來孤立異常點，算法的效率和可靠性都比較高；而深度孤立森林算法是對孤立森林算法的優(yōu)化，基于多粒度掃描和級聯(lián)森林來改進孤立森林算法對局部異常點識別不準(zhǔn)確的情況。由于深度孤立森林相比孤立森林多了多粒度掃描階段和級聯(lián)森林階段，會增加一些時間開銷，因此本文通過并行化構(gòu)建孤立森林，從而抵消部分增加的時間開銷。

1 水質(zhì)異常數(shù)據(jù)分析

異常數(shù)據(jù)是某個數(shù)據(jù)集中存在但不合群的數(shù)據(jù)點，又稱離群數(shù)據(jù)。某一個數(shù)據(jù)集在多個特征集合上形成一定規(guī)律，而集合中有一數(shù)據(jù)點明顯不符合該規(guī)律，則該數(shù)據(jù)點為異常點。

本文數(shù)據(jù)來自于國家地表水水質(zhì)自動監(jiān)測實時數(shù)據(jù)發(fā)布系統(tǒng)的真實數(shù)據(jù)，見表1。

表1 原始水質(zhì)數(shù)據(jù)

為了得到可靠的實驗結(jié)果，現(xiàn)對水質(zhì)數(shù)據(jù)進行以下預(yù)處理：

1)水質(zhì)等級Ⅳ以下的數(shù)據(jù)使其標(biāo)簽為1.0，代表正常數(shù)據(jù)；水質(zhì)等級Ⅳ及以上的數(shù)據(jù)使其標(biāo)簽為0.0，代表異常數(shù)據(jù)。

2)刪除屬性都缺失的數(shù)據(jù)。

3)因為原數(shù)據(jù)集合中有缺失的數(shù)據(jù)，能夠憑借著剩余屬性判別水質(zhì)等級，若在此填充中位數(shù)、均值或者插值，在不知原數(shù)據(jù)集合判別標(biāo)準(zhǔn)的情況下，數(shù)據(jù)集合將變得不可靠，故將缺失值填充為0。

4)刪除缺少水質(zhì)等級的數(shù)據(jù)。

處理后的水質(zhì)數(shù)據(jù)見表2。

表2 預(yù)處理后水質(zhì)數(shù)據(jù)

對水質(zhì)數(shù)據(jù)進行描述性分析，結(jié)果見表3，可以發(fā)現(xiàn)異常數(shù)據(jù)和正常數(shù)據(jù)在氨氮、高錳酸鹽、總有機碳幾個指標(biāo)上差異明顯，而pH值和溶解氧則差異較小。

表3 水質(zhì)數(shù)據(jù)描述性分析

根據(jù)表2生成各指標(biāo)數(shù)據(jù)分布圖，如圖1所示，發(fā)現(xiàn)異常數(shù)據(jù)的溶解氧、高錳酸鹽、氨氮等指標(biāo)相較正常數(shù)據(jù)波動較大，且存在少數(shù)局部異常值。圖中深色線代表異常數(shù)據(jù)，淺色線代表正常數(shù)據(jù)。

圖1 各指標(biāo)數(shù)據(jù)分布圖

通過分析和經(jīng)驗判斷，發(fā)現(xiàn)水質(zhì)數(shù)據(jù)往往具備以下特點：1)正常數(shù)據(jù)和異常數(shù)據(jù)在高錳酸鹽、氨氮等指標(biāo)上有明顯差異，而pH值和溶解氧差異較小；2)異常數(shù)據(jù)較正常數(shù)據(jù)各指標(biāo)通常有著較大波動，且有較多遠離正常標(biāo)準(zhǔn)的值，整體分布較為稀疏；3)存在少量異常值；4)指標(biāo)易受氣候、人工等因素影響；5)水質(zhì)數(shù)據(jù)維度較低，異常數(shù)據(jù)數(shù)量少。

2 基于多粒度掃描孤立森林的水質(zhì)異常檢測

2.1 孤立森林算法

孤立森林算法是一種基于規(guī)律，針對異常點是分布稀疏且離密度高的群體較遠的點，通過從數(shù)據(jù)集合隨機地獲取屬性，再隨機地獲取某條數(shù)據(jù)，該屬性所對應(yīng)的值作為劃分閾值從而將數(shù)據(jù)集劃分為兩個部分，不斷重復(fù)上述步驟，直至使得某部分?jǐn)?shù)據(jù)集的數(shù)據(jù)量小于等于1，即孤立某條數(shù)據(jù)的算法。實驗表明，正常數(shù)據(jù)被孤立的平均路徑長度即劃分次數(shù)，是異常數(shù)據(jù)的2～3倍，如圖2所示，也就意味著相比正常數(shù)據(jù)，異常數(shù)據(jù)往往在更少的劃分次數(shù)下就能使其孤立[4-5]。

圖2 數(shù)據(jù)平均路徑長度

孤立森林通過給定的數(shù)據(jù)集，每次從中抽取固定大小的子數(shù)據(jù)集構(gòu)成子樹，通過構(gòu)建大量的子樹形成森林，計算每條數(shù)據(jù)被孤立或者找到其在樹中的位置所花費的路徑長度，計算其異常得分，判斷當(dāng)前數(shù)據(jù)是否異常。

給定一個包含n個樣本的數(shù)據(jù)集，樹的平均路徑長度為：

(1)

式中：H(i)為調(diào)和數(shù)，該值可以被估計為ln(i)+0.577 215 664 9；c(n)為給定樣本數(shù)n時路徑長度的平均值，用于標(biāo)準(zhǔn)化樣本x的路徑長度h(x)。

樣本的異常得分s(x,n)定義為：

(2)

式中：E(h(x))為樣本x在一批孤立樹中找到自己應(yīng)該所處的位置所花費的平均路徑長度。

由式(2)可以得出以下結(jié)論：

1)當(dāng)E(h(x))→c(n)，s(x,n)→0.5,則不能區(qū)分樣本x是不是異常點。

2)當(dāng)E(h(x))→0，s(x,n)→1.0，則能夠判斷樣本x是異常點。

3)當(dāng)E(h(x))→n-1，s(x,n)→0，則能夠判斷樣本x是正常點。

2.2 深度孤立森林

深度孤立森林由多粒度掃描和級聯(lián)森林兩部分組成，多粒度掃描負(fù)責(zé)以不同特征維度生成新的數(shù)據(jù)集合，級聯(lián)森林負(fù)責(zé)接收和訓(xùn)練多粒度掃描所產(chǎn)生的新數(shù)據(jù)集合，

2.2.1多粒度掃描

定義特征集合為F，掃描窗口大小為p，根據(jù)窗口p構(gòu)建新的特征集合，定義步長為step，在特征集上進行滑動，得到式(3)所示的數(shù)量子特征集合S，其中每個子特征集的標(biāo)簽仍使用原標(biāo)簽，而多粒度則意味著基于不同的窗口大小和步長能獲取不同數(shù)量和維度的子特征集合。

(3)

多粒度掃描的滑動窗口過程如圖3所示，在圖中窗口大小為100，步長為1，隨著窗口不斷滑動，根據(jù)式(3)，最終能夠得到301個維度為100的子數(shù)據(jù)集合，同時步長step越大，損失的特征信息越多；步長step越小，產(chǎn)生的子特征集越多，窗口滑動和子特征產(chǎn)生的時間開銷越大。

圖3 多粒度掃描示意圖

在圖4中，窗口大小為200，步長為1，根據(jù)式(3)，最終得到201個維度為200的子數(shù)據(jù)集合。

將圖3中生成的特征集合分別輸入到普通隨機森林和完全隨機森林中，其中完全隨機森林和普通隨機森林的不同點在于完全森林中每一棵樹都可以通過隨機地選擇一個特征來分裂樹的每個節(jié)點，而普通隨機森林通過最佳的gini值作為分裂特征。假設(shè)圖3中所得到的301個100維特征向量每一個對應(yīng)一個三分類的類向量，即三分類的概率分布，經(jīng)過普通隨機森林和完全隨機森林的計算，分別得到了301個3維的類向量，再將該向量進行聚合，得到了一個903維的特征向量，最終再將完全隨機森林和普通隨機森林的特征向量聚合，生成一個1 806維的向量，同理，圖4中生成的特征集合按照上述計算會得一個1 206維的向量，再和上面生成的1 806維向量進行拼接生成一個3 012維的向量作為級聯(lián)森林階段的輸入，如圖5所示。

圖4 多粒度掃描示意圖

圖5 多粒度掃描階段

2.2.2級聯(lián)森林

級聯(lián)森林階段如圖6所示，將多粒度掃描階段根據(jù)不同窗口大小和不同步長所得到的特征拼接，作為級聯(lián)森林的輸入，每一層的輸出作為下一層的輸入，將最后的輸出取平均再取其中最大的值，得到最大值所對應(yīng)的類別作為最終的結(jié)果。級聯(lián)森林的層數(shù)通常有著自適應(yīng)調(diào)節(jié)的能力，即在級聯(lián)森林的構(gòu)造階段，在構(gòu)造當(dāng)前層時，如果經(jīng)過交叉驗證的準(zhǔn)確率相較上一層沒有提升或者提升小于閾值，則停止級聯(lián)森林的構(gòu)造，因此也會節(jié)省算法訓(xùn)練的時間開銷。

圖6 級聯(lián)森林示意圖

2.3 算法構(gòu)建

2.3.1并行孤立森林構(gòu)建

孤立森林分為訓(xùn)練階段和評估階段。訓(xùn)練階段主要目標(biāo)是分配數(shù)據(jù)集中各數(shù)據(jù)點在樹中的位置，在本文中，對孤立森林進行了并行優(yōu)化，即根據(jù) 的數(shù)量創(chuàng)建n條線程，每條線程各自建樹，互不影響，其中建立森林的偽代碼如下：

輸入：水質(zhì)數(shù)據(jù)集X，異常得分閾值S，iTrees數(shù)量n，子樣本數(shù)量s

輸出：IForest(iTrees,s,S)

1：最大深度max_length=ceiling(log2n)

2：子樣本subsample_size=min(s,X.size)

3：獲取特征數(shù)num_features=X.cols

4：初始化當(dāng)前深度current_length=0

5：創(chuàng)建線程池

6：創(chuàng)建存放線程集合list

7：for i=1 to t do

8：創(chuàng)建線程tThread

9：存放線程list.add(tThread)

10：end for

11：利用java8的stream和lambda表達式進行并行化計算得到ListIForest

12：return IForest

線程內(nèi)部偽代碼如下：

輸入：水質(zhì)數(shù)據(jù)集X，子樣本數(shù)量s，最大深度max_length，特征數(shù)num_features，當(dāng)前深度current_length

輸出：tThread

1：創(chuàng)建線程tThread

2：初始化tThread

3：X′=sample(X,s)

4：iTree=growTree(X′,max_length,num_features,current_length)

5：return iTree

詳細建樹偽代碼如下：

輸入：子水質(zhì)數(shù)據(jù)集X′，最大深度max_length，特征數(shù)num_features，當(dāng)前深度current_length

輸出：ITree

1：if current_length >= max_length or X′.size <=1

2：return LeafNode(X′.size)

3：Q是數(shù)據(jù)集X′的特征集，隨機取某一特征q∈Q,隨機取p,其范圍是特征q的取值范圍

評估階段根據(jù)訓(xùn)練階段所構(gòu)建好的森林，計算找到某數(shù)據(jù)點所花費的路徑長度，并根據(jù)式(2)得到其異常得分和判斷其是否為異常數(shù)據(jù)點，其偽代碼如下：

輸入：水質(zhì)數(shù)據(jù)集創(chuàng)建的孤立森林T，某條水質(zhì)數(shù)據(jù)x，異常得分閾值S

輸出：是否為異常值

1：計算尋找x在T中的位置所花費的距離l

2：根據(jù)公式(2)計算異常得分s

3：if s>S

4：return-1

5：else

6：return 1

2.3.2并行深度孤立森林構(gòu)建

由2.2可知，深度孤立森林劃分為多粒度掃描階段與級聯(lián)森林階段，其中多粒度掃描階段的偽碼如下：

輸入：水質(zhì)數(shù)據(jù)集X，維度u，步長step，窗口p

輸出：新數(shù)據(jù)集X′

1：if p>u

2：return X

3：start=0

4：X′= {}

5：while start+step

6：Xj=GenerateDate(X,start,p)

7：X′+=Xj

8：start+= step

9：end while

10: return X′

級聯(lián)森林階段的偽碼如下：

輸入：多粒度數(shù)據(jù)集X′

輸出：結(jié)果類別c,層級數(shù)depth

1：X = concatenate(X′)

2：for i=1 to depth do

3：tmp1 = NormalForest(X)

4：tmp2 = IsolateForest(X)

5：X = concatenate(tmp1,tmp2)

6：end for

7：X = Avg(X)

8：c = argmax(X)

9：return c

3 仿真結(jié)果及分析

3.1 仿真環(huán)境

用于仿真的計算機CPU為Intel(R)Core(TM)i5-7300HQ@2.50 GHz，內(nèi)存為12 GB，操作系統(tǒng)為64位Windows10。

3.2 仿真結(jié)果及分析

對孤立森林算法和深度孤立森林算法進行測試，取子樹的數(shù)量區(qū)間為[1,1 000]，基于不同子樹數(shù)量運行兩種算法10次求和取平均值，結(jié)果如圖7所示，可以看到，深度孤立森林算法的準(zhǔn)確率始終大于孤立森林算法，尤其在子樹數(shù)量較少的情況下，深度孤立森林算法有很好的性能，但是相比較孤立森林算法波動性較大。

圖7 準(zhǔn)確率變化圖

選取子樹數(shù)量為500棵，對4種算法訓(xùn)練不同次數(shù)，結(jié)果如圖8所示，并行版的算法相較于普通版本的算法都有著一定的訓(xùn)練效率提升，但是由于并行深度孤立森林算法僅僅優(yōu)化了級聯(lián)森林階段，故并行深度孤立森林的時間開銷還是大于普通孤立森林。

圖8 各算法時間開銷

選取多種異常檢測算法，對數(shù)據(jù)進行測試，結(jié)果如表4和圖9所示，其中F1代表著精確率和召回率的調(diào)和平均值，其綜合考慮了精確率和召回率，能夠更加準(zhǔn)確描述算法的性能。one-class SVM和LOF盡管在整體數(shù)據(jù)上表現(xiàn)尚可，但是在異常數(shù)據(jù)上表現(xiàn)非常差，其中one-class SVM僅預(yù)測出54.1%的異常數(shù)據(jù)，LOF僅預(yù)測出42.0%的異常數(shù)據(jù)，而孤立森林和深度孤立森林無論在整體數(shù)據(jù)，還是在異常數(shù)據(jù)上，都遠遠優(yōu)于one-class SVM和LOF，且深度孤立森林在異常數(shù)據(jù)的預(yù)測準(zhǔn)確率上要優(yōu)于孤立森林。

4 結(jié)束語

本文所應(yīng)用的深度孤立森林算法，相較于其他異常檢測算法，在水質(zhì)異常數(shù)據(jù)異常檢測上準(zhǔn)確率非常高，但所花費的代價是增加了算法訓(xùn)練的時間開銷。由于森林是一種天然支持并行化的結(jié)構(gòu)，故提出并行孤立森林和并行深度孤立森林以減少算法訓(xùn)練時間，異常檢測的兩個重要點在于實時和準(zhǔn)確，通過文中分析可知，并行深度孤立森林能夠很好地滿足這兩點。