決策樹算法在分類預測中的應用與優化

葛朋,彭夢晶

1.重慶市中醫院信息科,重慶400010

2.重慶市中醫院設備處,重慶400010

決策樹算法在分類預測中的應用與優化

葛朋1,彭夢晶2

1.重慶市中醫院信息科,重慶400010

2.重慶市中醫院設備處,重慶400010

決策樹是一類常見的機器學習方法，具有屬性結構和較好的分類預測能力，可以根據既定規則完成基本的決策任務。本文闡述了決策樹算法的基本思想，并以某銀行信貸問題為例，分析了決策樹算法在應用中遇到的一些問題，最后給出了性能調優方案。

機器學習;決策樹算法;分類預測

隨著云計算和大數據的迅速發展，數據挖掘技術得到了廣泛的應用。數據挖掘指的就是從大量數據中通過某種算法和工具，挖掘數據背后隱藏價值的過程。而在實際應用中，數據挖掘主要用于分類和預測。數據挖掘需要實現建立數據關系模型，對數據進行分析預測。預測是為了基于歷史數據通過機器學習算法分析數據的變化趨勢，達到預測的作用。決策樹算法是數據挖掘中最常用的方法，其作用于分類階段，可以直接體現數據特點，分析預測數據，并能方便提取決策規則，達到輔助決策的功效。

1 決策樹基本流程

決策樹是一種常見的樹形結構，一個典型的決策樹由一個根節點、若干個內部節點和若干個葉節點組成。葉節點與決策結果相對應。其它每個內部節點表示一個屬性測試，每個分支代表一個測試輸出，每個葉節點代表一種類別。在機器學習中，決策樹學習的目的是針對不同的未知數據產生一顆泛化能力強的決策樹。常用的決策樹算法是ID3和C4.5算法，其采用“自上而下、分類治之”的方法，通過一些無序、無規則的事例推測出決策樹的分類規則，可以實現對位置數據的分類、預測和數據預處理。決策樹一般分為構成和剪枝兩個步驟，其工作流程如圖1所示：

圖1 決策樹工作流程圖Fig.1 The running process of the decision tree

決策樹學習的關鍵是如何選擇最優劃分屬性。一般而言，隨著劃分過程不斷進行，我們希望決策樹的分支節點所包含的樣本盡可能屬于同一類別，即節點的純度（Purity）越來越高。因此引入了信息增益的概念。

2 決策樹算法分析

2.1 ID3算法

ID3算法是決策樹的一種，它是基于奧卡姆剃刀原理的，這個算法的基礎是越是小型的決策樹越優于大的決策樹，盡管如此，也不總是生成最小的樹型結構，而是一個啟發式算法。假定當前樣本集合D中第k類樣本所占的比例為pk(k=1,2,3...|y|)，那么D的信息熵定義為：

在信息論中，Ent(D)的值越小，那么D的純度就越高。根據上式可以計算屬性a對樣本集D進行劃分所獲得的信息增益（Information gain）。

ID3算法的實質是利用信息增益來度量屬性的選擇，在選擇分裂屬性時，往往偏向于選擇取值較多的屬性，但是現實應用中取值較多的屬性不一定是最重要的屬性，因此很有可能會使得生成的決策樹的預測結果與現實情況誤差較大，為了解決這個問題，引入分支信息熵和屬性優先的概念。

2.2 C4.5

C4.5決策樹算法是在ID3算法的基礎上發展起來的，通過信息熵方法遞歸形成決策樹，應用廣泛，效率更高。對比兩種算法的不同之處，一方面表現在C4.5將信息增益作為測試屬性，而ID3算法采用基于信息增益的方法選擇測試屬性。另一方面表現是C4.5算法不需要獨立測試樣本集，提高效率，可以直接處理連續屬性和屬性空缺的樣本，這樣的產生決策樹分枝減少，而ID3算法的連續屬性處理是離散化的。

C4.5算法用信息增益率來選擇屬性，解決了用信息增益選擇屬性時偏向選擇取值多的屬性的缺陷問題，此外，它還能處理非離散的數據和不完整的數據。但是C4.5的算法效率比較低。

3 決策樹算法的應用

為了驗證并測試決策樹算法在分類預測中的性能以及調優效果，以某銀行客戶信貸風險預測為例，詳細闡述決策樹在算法在分類預測中的應用。現在擁有一個某公司近2年內的申辦信用卡客戶數據集，包含40700個客戶，每個客戶有40個屬性域。其中有700個客戶申請了貸款項目（target_flag=1），而另外的40000個則是沒有申請的（target_flag=0）。同時還提供了一個預測數據集（8000個樣本），其中的TARGET_FLAG【是否貸款】屬性是本次實驗重點關注的屬性，利用訓練集建立模型，然后利用此模型對此屬性進行預測，最終得出每個客戶申請貸款項目的可能性。

在數據預處理階段主要完成的是數據清洗工作，主要包括數據格式轉換，空缺值處理，離散化和不相關屬性的清理等工作，目的是提高數據的質量。為了提高模型的可信度，我們手動從原始數據集中隨機選出4000個實例作為訓練集，21343個實例作為測試集，用來測試分類預測模型的性能。

在這個數據集中，顯然|y|=2，在決策樹學習開始時，根節點包含D中所有的樣例，其中正例占p1=700/21343，p2=700/21343,因此根節點的信息熵為：

然后我們計算出當前屬性集合中每個屬性的信息增益，最后選擇信息增益最大的屬性作為劃分屬性，選擇部分決策樹如圖2所示。

圖2 部分決策樹模型Fig.2 The model of some decision trees

在Weka平臺中分別選擇ID3算法和C4.5算法對模型進行訓練，并將模型應用到集中，分別得到模型的性能結果，如表1所示。

表1 ID3和C4.5性能比較Table 1 Comparison of ID3 and C4.5 performances

4 決策樹分類算法的優化

通過分析決策樹的兩種算法ID3算法與C4.5算法的不同，總結出來決策樹算法的三大問題，即計算效率低，多值偏向和對空缺值敏感。計算信息熵是一個高度復雜的過程，導致其計算開銷比較大。除此之外原始數據集由于缺乏屬性約減導致額外的計算開銷。基于信息熵的屬性選擇都會偏向于選擇取值較多的屬性，但是有時候下取值較多的屬性不一定就是最重要的屬性。決策樹算法在遇到缺失的數據時產生錯誤的概率比較大，這樣會對后續的預測和決策產生較大的影響。

針對以上三大問題，對數據預處理、屬性的合理選擇和連續屬性的離散化等方面進行優化。

4.1 預處理

預處理主要是解決決策樹空缺值敏感問題。現實任務中經常遇到不完整的樣本，即樣本缺失，例如由于診測成本隱私保護等因素，患者的醫療數據在某些屬性上的取值未知，尤其是屬性較多的數據集上，往往會有大量樣本出現缺失值。假如給定數據集D和屬性a，～D表示D中在屬性a上的缺失值的樣本集，那么信息增益公式可以拓展為

還可以用一個全局常量，屬性的均值來填補缺失值或根據不同元祖分類數據，選擇同一個屬性的平均值替換空缺值。

4.2 屬性選擇

雖然從理論角度來講，選擇的屬性越多，信息量越大，然而當數據量達到某種水平時，性能便會急劇下滑。由于在實際的應用場景中，樣本不可能是無限的，因此，在設計分類器時進行屬性消減是很重要的。

削減屬性可以通過屬性提取和屬性選擇。屬性提取其實就是一種映射。若X是原始的測量空間，X′是屬性空間，則X→X′的映射就叫作屬性提取器。屬性選擇是通過選擇有效屬性來達到空間降維目的的過程。屬性選擇是屬性提取的一種特殊情況。提取變量往往會降低結果的可解釋性。尤其對于離散變量而言，進行屬性提取是沒有意義的。所以主要研究屬性選擇方法。刪除與目標屬性無關的屬性例如ID編號等可以提高模型的應用效率。

4.3 連續屬性離散化

在本次數據集中，客戶的收入是連續屬性，但是在建模過程中需要將其離散化，便于分類處理。離散化是在面對分類問題時處理連續數據常用的方法，像ID3算法只能夠處理離散屬性，而C4.5不僅能夠處理連續數據，同時還能有效處理離散數據。離散化方法可以分為兩類：全局離散和局部離散。全局離散需要考慮到屬性之間的相互作用，局部離散方法限制一次只能對一個屬性進行離散。局部離散相對于全部離散要簡單。

全部離散要比局部離散的計算開銷更大。

經測試，優化后的算法在準確率和最小均方誤差等參數均有所提升，正確率提高至96.71%，均方根誤差為0.1279。

5 總結

隨著大數據和云計算時代的到來，數據挖掘分類問題和算法研究成為熱點，本文對數據挖掘中決策樹算法的應用進行了優化研究。通過分析決策樹常見的兩種算法以及決策樹算法中存在的問題，針對實際問題，主要提出數據預處理、從屬性選擇、連續屬性離散化等幾方面改進決策樹分類算法，提高決策樹算法的效率和性能。

[1]王珊,薩師煊.數據庫系統概論[M].4版.北京:高等教育出版社,2006

[2]張云濤,龔玲.數據挖掘原理與技術[M].北京:電子工業出版社,2004

[3]趙基.基于數據挖掘的銀行客戶分析管理關鍵技術研究[D].杭州:浙江大學,2005

[4]石振華.銀行卡用戶數據挖掘系統的設計與實現[D].西安:西安電子科技大學,2010

[5]鄭英姿.基于數據挖掘的商業銀行客戶關系管理研究[D].西安:西安科技大學,2010

[6]李明江,唐穎,周力軍.數據挖掘技術及應用[J].中國新通信,2012(22):66-67

[7]薛薇.數據挖掘中的決策樹技術及其應用[J].統計與信息論壇,2002,17(2):4-10

[8]楊學兵,張俊.決策樹算法及其核心技術[J].計算機技術與發展,2007,17(1):43-45

[9]欒麗華,吉根林.決策樹分類技術研究[J].計算機工程,2004,30(9):94-96,105

[10]陳文,史金成.決策樹分類技術研究[J].福建電腦,2005(8):5-6

[11]郭彥偉.電信行業客戶流失分析的決策樹技術[J].科技和產業,2005,5(11):7-9

[12]李曉卉.決策樹技術在客戶信用分析中的應用[J].武漢科技大學學報:社會科學版,2008,10(2):26-28,32

[13]陳沛玲.決策樹分類算法優化研究[D].長沙:中南大學,2007

[14]何清,李寧,羅文娟,等.大數據下的機器學習算法綜述[J].模式識別與人工智能,2014,27(4):327-336

[15]李運.機器學習算法在數據挖掘中的應用[D].北京:北京郵電大學,2015

[16]姜百寧.機器學習中的特征選擇算法研究[D].青島:中國海洋大學,2009

[17]孫亮.若干機器學習算法的研究與應用[D].長春:吉林大學,2012

[18]胡蓉.增量機器學習算法研究[D].南京:南京理工大學,2013

[19]王淑珍.機器學習算法的Weka嵌入[D].廣州:華南理工大學,2013

[20]王靜.基于機器學習的文本分類算法研究與應用[D].成都:電子科技大學,2015

The Optimization and Application of the Decision Tree Algorithm in the Classification Prediction

GE Peng1,PENG Meng-jing2
1.Information Center of Chongqing Chinese Medicine Hospital,Chongqing 400011,China
2.Equipment Department of Chongqing Chinese Medicine Hospital,Chongqing 400011,China

Decision tree is a kind of common method in machine learning,it is with an attribute structure and better ability to classify and predict and it can complete basic decision tasks according to the given rules.The paper firstly expounded the basic thoughts and then analyzed some problems in the application of the decision tree algorithm taking a bank credit as case to obtain the performance tuning scheme in the end.

Machine learning;decision tree algorithm;classification prediction

TP181

A

1000-2324(2016)06-0936-04

2016-03-20

2016-03-26

葛朋(1975-),男,研究生,工程師,研究領域:數據庫技術.E-mail:34170856@qq.com