基于改進CART決策樹建立水華預警模型

劉云翔，吳 浩

(上海應用技術大學計算機科學與信息工程學院，上海 201418)

0 引 言

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

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

1 CART決策樹算法原理

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

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

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

(1)

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

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

(2)

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

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

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

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

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

2 改進CART算法決策樹

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

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

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

3 基于改進CART的水華預警模型

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

3.1 條件屬性的確定

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

表1 相關系數表Tab.1 Correlation coefficient table

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

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

表2 屬性最優閾值表Tab.2 The optimal threshold for the attribute

3.2 建立CART決策樹模型

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

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

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

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

表4 預測結果對比Tab.4 Comparison of forecast results

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

4 結 語

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

□

[1] 王 立，高 崇，王小藝，等. 藍藻生長時變系統非線性動力學分析及水華預測方法 [J]. 化工學報，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]. 計算機學報，2016，39(8):1 697-1 716.

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

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

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

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

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

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

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