王海龍，李東波，吳紹鋒

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

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

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

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

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

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

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

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

本文數(shù)據(jù)來(lái)自于國(guó)家地表水水質(zhì)自動(dòng)監(jiān)測(cè)實(shí)時(shí)數(shù)據(jù)發(fā)布系統(tǒng)的真實(shí)數(shù)據(jù)，見(jiàn)表1。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 孤立森林算法

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

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

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

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

(1)

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

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

(2)

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

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

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

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

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

2.2 深度孤立森林

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

2.2.1多粒度掃描

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

(3)

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

圖3 多粒度掃描示意圖

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

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

圖4 多粒度掃描示意圖

圖5 多粒度掃描階段

2.2.2級(jí)聯(lián)森林

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

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

2.3 算法構(gòu)建

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

孤立森林分為訓(xùn)練階段和評(píng)估階段。訓(xùn)練階段主要目標(biāo)是分配數(shù)據(jù)集中各數(shù)據(jù)點(diǎn)在樹中的位置，在本文中，對(duì)孤立森林進(jìn)行了并行優(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表達(dá)式進(jìn)行并行化計(jì)算得到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

詳細(xì)建樹偽代碼如下：

輸入：子水質(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′的特征集，隨機(jī)取某一特征q∈Q,隨機(jī)取p,其范圍是特征q的取值范圍

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

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

輸出：是否為異常值

1：計(jì)算尋找x在T中的位置所花費(fèi)的距離l

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

3：if s>S

4：return-1

5：else

6：return 1

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

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

輸入：水質(zhì)數(shù)據(jù)集X，維度u，步長(zhǎng)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′

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

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

輸出：結(jié)果類別c,層級(jí)數(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)境

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

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

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

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

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

圖8 各算法時(shí)間開銷

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

4 結(jié)束語(yǔ)

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