劉云翔，吳 浩

(上海應(yīng)用技術(shù)大學(xué)計算機科學(xué)與信息工程學(xué)院，上海 201418)

0 引 言

隨著人口的快速增加，現(xiàn)代化工、農(nóng)業(yè)生產(chǎn)的快速發(fā)展，大量的工、農(nóng)業(yè)廢水和生活廢水進入海洋，湖泊和城市水庫中，形成的水華[1,2]造成嚴重的水污染。并且大多數(shù)都是未經(jīng)處理的廢水，這些未處理過的廢水就直接排放到海洋、湖泊和水庫中，這種現(xiàn)象加劇了水體的富營養(yǎng)化程度。水體嚴重的富營養(yǎng)化是誘導(dǎo)水華爆發(fā)的重要因素，水華的大面積爆發(fā)使得水環(huán)境越來越差，污染逐漸加重。為有效控制水環(huán)境，科學(xué)有效的預(yù)測至關(guān)重要。預(yù)測有利于事前準備有針對性的預(yù)防措施并進行預(yù)警。為了解決湖泊預(yù)報的問題，國內(nèi)外學(xué)者在開展預(yù)警研究方面取得了一些進展，不同學(xué)者從不同角度進行了不同的分析。多變量統(tǒng)計回歸方法，模糊數(shù)學(xué)，遺傳算法和神經(jīng)網(wǎng)絡(luò)方法[3]應(yīng)用于湖體水華預(yù)測中，在水環(huán)境防護和治理中發(fā)揮了較好的作用。不過這些方法還是存在一定的不足。例如，神經(jīng)網(wǎng)絡(luò)局部極值的問題，多元統(tǒng)計回歸方法模型一般得出的線性關(guān)系的方程，對水華預(yù)測的效果不明顯。

解決水華爆發(fā)預(yù)測問題的關(guān)鍵是根據(jù)監(jiān)測站采集到的水華影響因素數(shù)據(jù)來判斷水華是否會爆發(fā)，這屬于典型分類問題。因此應(yīng)用CART算法可以很好的生成預(yù)測模型。CART具有模型簡單和規(guī)則提取簡單的特點。CART算法是利用二元遞歸分裂方法把樣本集分為兩個不同的子樣本，使得生成的每個非葉子結(jié)點都擁有兩個左右分叉，所以利用CART算法形成的是一種具有二叉樹形式的簡單決策樹。但基于傳統(tǒng)的CART算法生成的水華預(yù)警模型，在進行判斷時，依然會存在運行時間長、準確率不高等缺點。為此，本文將結(jié)合Fayyad邊界判定定理和統(tǒng)計學(xué)中的相關(guān)系數(shù)，運用Fayyad邊界判定定理解決屬性分割點GINI指數(shù)運算時間長問題，優(yōu)化閾值選擇的方法，減少運行時間。利用相關(guān)系數(shù)選出與形成水華相關(guān)程度較大的屬性，利用這些屬性進行分裂得到改進決策樹。這種改進的決策樹為水華預(yù)警問題提供了一種可行的方法。

1 CART決策樹算法原理

決策樹算法[4,5]是分類算法中比較常用的經(jīng)典算法之一，決策樹算法得到的結(jié)果理解性強，容易看懂。建立決策樹首先是分析和處理樣本集中的數(shù)據(jù)，并且通過歸納算法生成一系列的規(guī)則和決策樹。然后，通過使用決策樹來分析新數(shù)據(jù)。決策樹就是利用一組規(guī)則把數(shù)據(jù)分到不同類別中的過程。 CART[6]是一種決策樹算法中一種二叉樹形式的算法，它的結(jié)構(gòu)比較簡單，其使用二元分割方法，其將當前樣本集合劃分為兩個樣本子集合，再對子集合使用二元分割，不斷遞歸重復(fù)這個動作使得最終生成的每個非葉子結(jié)點都有兩個左右分支。生成CART決策樹的步驟如下：

(1)計算數(shù)據(jù)集中每個屬性的GINI指數(shù)，GINI指數(shù)越小，雜質(zhì)越低，越“純凈”。選擇最小的GINI指數(shù)的屬性作為決策樹的根結(jié)點。對于離散屬性，我們檢查已知樣本集合(空集合和完整集合)的所有可能的子集，計算這些子集的GINI指數(shù)，從中選出最小GINI指數(shù)的子集作為屬性分裂方法，最小GINI指數(shù)作為該屬性的GINI指數(shù)。但對于連續(xù)的屬性，需要多做一步連續(xù)屬性的離散化工作，離散化需要計算每個屬性的最優(yōu)分割閾值，根據(jù)分割閾值對其進行離散化，并計算其GINI指數(shù)。

GINI指數(shù)是度量數(shù)據(jù)分區(qū)或者是樣本集E的不純程度，GINI指數(shù)越小代表樣本越“純凈”。定義如下：

(1)

其中，類別集為{C1，C2，…,Cn}，|Ci|為E中屬于Ci的樣本數(shù)量，pi=|Ci|/|E|為E中的樣本屬于類別Ci的概率。

當只把樣本集一分為二時，屬性A將訓(xùn)練樣本集E劃分成兩個子集E1和E2，則劃分后E的GINI指數(shù)為：

(2)

其中，|Ek|/|E|為樣本集中樣本屬于第k(k=1，2) 個子集的概率。

(2)針對連續(xù)屬性的分割，樣本集要選擇屬性分割點GINI指數(shù)最小值的點為分割閾值把S劃分為≤S和≥S的兩個部分。如果分裂屬性是離散的，通過計算訓(xùn)練樣本集所有子集的GINI指數(shù)，選出GINI指數(shù)最小的子集為它的分裂子集，將它分裂成為兩個部分。

對于連續(xù)的屬性，為了獲得該屬性的GINI指數(shù)則需要考慮每個可能的分裂點。需要將其中每對按升序(或降序)排序好后的相鄰值的中間值作為可能的分裂點，利用這個分裂點把屬性分為兩個部分，再利用公式(2)計算每個分裂點的GINI指數(shù)，再從中選出最小的GINI指數(shù)的分裂點作為這個屬性的分裂點。

(3)根據(jù)GINI指數(shù)最小的屬性將樣本集分裂成兩個子集E1和E2，采用(1)一樣的方法遞歸建立決策樹的子結(jié)點。循環(huán)到所有葉子結(jié)點中樣本的類別大致相同，或者下一個后續(xù)分裂屬性已經(jīng)沒有了為止。

(4)利用代價復(fù)雜度剪枝算法進行剪枝，形成簡潔的決策樹。

2 改進CART算法決策樹

由于傳統(tǒng)的CART算法存在運行時間較長和預(yù)測精度不夠等問題，本文就利用Fayyad邊界點判定定理改進CART算法，簡化屬性最優(yōu)閾值選擇的運算。利用相關(guān)系數(shù)理論求取決策屬性與條件屬性的相關(guān)系數(shù)，選出與決策屬性相關(guān)程度較大的屬性，以這些條件屬性為結(jié)點遞歸形成決策樹。

CART算法在進行連續(xù)屬性的離散化過程中，首先對屬性A的所有屬性數(shù)據(jù)值(n個)進行升序(或降序)排序，然后取相鄰值的中間數(shù)作為分割點，得到n-1個分割點，計算出每個分割點的GINI指數(shù)，選出其中最小的GINI指數(shù)作為屬性A的最佳分割閾值。但是如果樣本集的樣本數(shù)過大且具有的連續(xù)型屬性也很多，CART算法的計算量就會非常巨大，構(gòu)成決策樹的效率也降低了。

在進行屬性最優(yōu)分割閾值選擇時，結(jié)合Fayyad邊界判定定理[7,8]，檢查相鄰不同類別的邊界點，F(xiàn)ayyad邊表界判定定理明：最優(yōu)分裂點總是處在不同類別的邊界點處。所以只需要算出不同類邊界處的GINI指數(shù)值就可以，不需要計算所有分割點的GINI指數(shù)值。因此所屬類別越少，效率越高。在樣本集只有兩個類別的時候效率是最高。

3 基于改進CART的水華預(yù)警模型

水華的爆發(fā)是一個多因素綜合影響的結(jié)果，其影響因素非常多且復(fù)雜。本文研究所選取的水質(zhì)數(shù)據(jù)來自巢湖西半湖的藍藻水華在線監(jiān)測基站。引用的指標包括葉綠素a(Chl-a)，水溫(T)，pH，氮磷比(TN∶TP)，化學(xué)需氧量(COD)，總氮(TN)，總磷(TP)，溶解氧(DO)，光照(E)等水質(zhì)、氣象因子。

3.1 條件屬性的確定

以葉綠素a為決策屬性，其他影響因子為條件屬性，計算出決策屬性和其他各個條件屬性的相關(guān)系數(shù)，得到巢湖水體葉綠素a水平與不同影響因子的相關(guān)系數(shù)[9]表，見表1。

表1 相關(guān)系數(shù)表Tab.1 Correlation coefficient table

由表1可知，影響巢湖西半湖水體葉綠素a[10]濃度水平的主要因素有總磷(TP)，pH，溫度(T)，化學(xué)需氧量(COD)，氮磷比(TN∶TP)。

本文中葉綠素a濃度為決策屬性，根據(jù)國際上和國家文獻定義Chl-a濃度的閾值為0.003 mg/L，當Chl-a濃度超過0.003 mg/L時，就表示可能爆發(fā)水華，需要做出預(yù)防工作，小于0.003 mg/L時水環(huán)境狀況良好，水華爆發(fā)的可能性不大。利用改進的CART算法計算各個屬性的分割點的最小GINI指數(shù)，這些最小GINI指數(shù)點就是屬性最優(yōu)閾值，得到屬性的最優(yōu)閾值見表2。

表2 屬性最優(yōu)閾值表Tab.2 The optimal threshold for the attribute

3.2 建立CART決策樹模型

根據(jù)表1的屬性相關(guān)系數(shù)和表2的屬性最優(yōu)閾值建立CART決策樹模型，以總磷(TP)，溫度(T), 氮磷比(TN∶TP)，化學(xué)需氧量(COD)，pH為條件屬性，Chl-a濃度為決策屬性，建立決策樹模型；同時根據(jù)代價復(fù)雜度剪枝算法對生成的CART算法進行剪枝，減去一些子樹，簡化決策樹，防止過度擬合。根據(jù)得到的決策樹可以提取部分有效規(guī)則，利用“If A Then B”來表示這些規(guī)則，結(jié)果如表3。

表3 巢湖西半湖水華預(yù)警部分規(guī)則Tab.3 Chaohu West half of the lake water blooms part of the rules

結(jié)合表3的分類規(guī)則，建立巢湖西半湖水發(fā)生預(yù)警決策模型。根據(jù)得出的決策樹模型表明該湖泊區(qū)域水華爆發(fā)的重要因素是總磷(TP)濃度，化學(xué)需氧量(COD)和氮磷比(TN∶TP)，而水溫(T)和pH也是它的影響因素但不是最重要。研究表明當TP<0.032 mg/L；COD<5.5 mg/L和TP>0.032 mg/L這兩種情況時該湖泊區(qū)域水華爆發(fā)的可能性比較大這個模型的建立對于水華爆發(fā)的短期預(yù)測能提供幫助，這對水環(huán)境防護和治理起到非常重要的作用。

利用實驗得出模型運行時長和預(yù)測正確率，將最后的結(jié)果與傳統(tǒng)的CART決策樹算法對比，結(jié)果見表4。

表4 預(yù)測結(jié)果對比Tab.4 Comparison of forecast results

由表4可知，采用結(jié)合相關(guān)系數(shù)和Fayyad邊界點判定定理的改進CART算法進行水華發(fā)生預(yù)測時，模型的預(yù)測正確率由83.54%變?yōu)榈?2.99%，預(yù)測模型的運行時長由1.018 s減少到0.795 s。運行時長減少，但準確度變化不大。由此可得到基于這種改進的CART決策樹模型對水華發(fā)生預(yù)警有非常良好的適用性。

4 結(jié) 語

科學(xué)正確的預(yù)測水華發(fā)生情況可以保證水環(huán)境安全，對于水環(huán)境治理起到重要的預(yù)防作用。最終的測試結(jié)果表明，改進的CART算法建立的預(yù)測模型能降低運行時長，還能保證預(yù)測正確率并且還可以發(fā)現(xiàn)影響水華爆發(fā)的重要因素，為水華爆發(fā)預(yù)測問題提出一種行之有效的方法，為水文監(jiān)測部門預(yù)防水華爆發(fā)提供了有效的科學(xué)依據(jù)。

□

[1] 王 立，高 崇，王小藝，等. 藍藻生長時變系統(tǒng)非線性動力學(xué)分析及水華預(yù)測方法 [J]. 化工學(xué)報，2017，68(3):1 065-1 072.

[2] QIN B. The changing environment of Lake Taihu and itsecosystem responses[J]. Journal of Freshwater Ecology, 2015,30(1): 1-3.

[3] 焦李成，楊淑媛，劉 芳，等. 神經(jīng)網(wǎng)絡(luò)七十年：回顧與展望[J]. 計算機學(xué)報，2016，39(8):1 697-1 716.

[4] 潘大勝，屈遲文. 一種改進ID3型決策樹挖掘算法[J].華僑大學(xué)學(xué)報(自然科學(xué)版)，2016，37(1):71-73.

[5] 謝妞妞. 決策樹算法綜述[J]. 軟件導(dǎo)刊，2015，14(11)：63-65.

[6] 張 亮，寧 芊. CART決策樹的兩種改進及應(yīng)用[J]. 計算機工程與應(yīng)用，2015，36(5):1 209-1 213.

[7] 苗煜飛，張霄宏. 決策樹C4.5算法的優(yōu)化與應(yīng)用[J]. 計算機工程與應(yīng)用，2015,51(13):255-258.

[8] 胡美春，田大鋼. 一種改進的C4.5決策樹算法[J]. 軟件導(dǎo)刊，2015，14(7):54-56.

[9] 董躍華，劉 力. 基于相關(guān)系數(shù)的決策樹優(yōu)化算法 [J]. 計算機工程與科學(xué)，2015，37(9):1 783-1 792.

[10] 齊凌艷，黃佳聰. 洪澤湖葉綠素 a 濃度的時空變化特征[J]. 湖泊科學(xué)，2016，28(3) :583-591.