葛朋,彭夢晶

1.重慶市中醫(yī)院信息科,重慶400010

2.重慶市中醫(yī)院設(shè)備處,重慶400010

決策樹算法在分類預(yù)測中的應(yīng)用與優(yōu)化

葛朋1,彭夢晶2

1.重慶市中醫(yī)院信息科,重慶400010

2.重慶市中醫(yī)院設(shè)備處,重慶400010

決策樹是一類常見的機器學(xué)習(xí)方法，具有屬性結(jié)構(gòu)和較好的分類預(yù)測能力，可以根據(jù)既定規(guī)則完成基本的決策任務(wù)。本文闡述了決策樹算法的基本思想，并以某銀行信貸問題為例，分析了決策樹算法在應(yīng)用中遇到的一些問題，最后給出了性能調(diào)優(yōu)方案。

機器學(xué)習(xí);決策樹算法;分類預(yù)測

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

1 決策樹基本流程

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

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

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

2 決策樹算法分析

2.1 ID3算法

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

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

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

2.2 C4.5

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

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

3 決策樹算法的應(yīng)用

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

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

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

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

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

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

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

4 決策樹分類算法的優(yōu)化

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

針對以上三大問題，對數(shù)據(jù)預(yù)處理、屬性的合理選擇和連續(xù)屬性的離散化等方面進行優(yōu)化。

4.1 預(yù)處理

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

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

4.2 屬性選擇

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

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

4.3 連續(xù)屬性離散化

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

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

經(jīng)測試，優(yōu)化后的算法在準(zhǔn)確率和最小均方誤差等參數(shù)均有所提升，正確率提高至96.71%，均方根誤差為0.1279。

5 總結(jié)

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

[1]王珊,薩師煊.數(shù)據(jù)庫系統(tǒng)概論[M].4版.北京:高等教育出版社,2006

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

[3]趙基.基于數(shù)據(jù)挖掘的銀行客戶分析管理關(guān)鍵技術(shù)研究[D].杭州:浙江大學(xué),2005

[4]石振華.銀行卡用戶數(shù)據(jù)挖掘系統(tǒng)的設(shè)計與實現(xiàn)[D].西安:西安電子科技大學(xué),2010

[5]鄭英姿.基于數(shù)據(jù)挖掘的商業(yè)銀行客戶關(guān)系管理研究[D].西安:西安科技大學(xué),2010

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

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

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

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

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

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

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

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

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

[15]李運.機器學(xué)習(xí)算法在數(shù)據(jù)挖掘中的應(yīng)用[D].北京:北京郵電大學(xué),2015

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

[17]孫亮.若干機器學(xué)習(xí)算法的研究與應(yīng)用[D].長春:吉林大學(xué),2012

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

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

[20]王靜.基于機器學(xué)習(xí)的文本分類算法研究與應(yīng)用[D].成都:電子科技大學(xué),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-),男,研究生,工程師,研究領(lǐng)域:數(shù)據(jù)庫技術(shù).E-mail:34170856@qq.com