葛朋,彭夢(mèng)晶

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

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

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

葛朋1,彭夢(mèng)晶2

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

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

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

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

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

1 決策樹基本流程

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

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

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

2 決策樹算法分析

2.1 ID3算法

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

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

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

2.2 C4.5

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

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

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

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

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

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

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

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

在Weka平臺(tái)中分別選擇ID3算法和C4.5算法對(duì)模型進(jìn)行訓(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é)出來決策樹算法的三大問題，即計(jì)算效率低，多值偏向和對(duì)空缺值敏感。計(jì)算信息熵是一個(gè)高度復(fù)雜的過程，導(dǎo)致其計(jì)算開銷比較大。除此之外原始數(shù)據(jù)集由于缺乏屬性約減導(dǎo)致額外的計(jì)算開銷?；谛畔㈧氐膶傩赃x擇都會(huì)偏向于選擇取值較多的屬性，但是有時(shí)候下取值較多的屬性不一定就是最重要的屬性。決策樹算法在遇到缺失的數(shù)據(jù)時(shí)產(chǎn)生錯(cuò)誤的概率比較大，這樣會(huì)對(duì)后續(xù)的預(yù)測和決策產(chǎn)生較大的影響。

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

4.1 預(yù)處理

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

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

4.2 屬性選擇

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

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

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

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

全部離散要比局部離散的計(jì)算開銷更大。

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

5 總結(jié)

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

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

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

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

[4]石振華.銀行卡用戶數(shù)據(jù)挖掘系統(tǒng)的設(shè)計(jì)與實(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)計(jì)與信息論壇,2002,17(2):4-10

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

[9]欒麗華,吉根林.決策樹分類技術(shù)研究[J].計(jì)算機(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é)報(bào):社會(huì)科學(xué)版,2008,10(2):26-28,32

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

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

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

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

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

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

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

[20]王靜.基于機(jī)器學(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