https://blog.csdn.net/baimafujinji/article/details/53269040

在2006年12月召開的 IEEE 數(shù)據(jù)挖掘國際會議上（ICDM， International Conference on Data Mining），與會的各位專家選出了當(dāng)時(shí)的十大數(shù)據(jù)挖掘算法（ top 10 data mining algorithms ），可以參見文獻(xiàn)【1】。本博客已經(jīng)介紹過的位列十大算法之中的算法包括：

• [1]?k-means算法（http://blog.csdn.net/baimafujinji/article/details/50570824）
• [2] 支持向量機(jī)SVM（http://blog.csdn.net/baimafujinji/article/details/49885481）
• [3] EM算法（http://blog.csdn.net/baimafujinji/article/details/50626088）
• [4] 樸素貝葉斯算法（http://blog.csdn.net/baimafujinji/article/details/50441927）
• [5]?kkNN算法（http://blog.csdn.net/baimafujinji/article/details/6496222）
• [6] C4.5決策樹算法（http://blog.csdn.net/baimafujinji/article/details/53239581）

決策樹模型是一類算法的集合，在數(shù)據(jù)挖掘十大算法中，具體的決策樹算法占有兩席位置，即C4.5和CART算法。本文主要介紹分類回歸樹（CART，Classification And Regression Tree）也屬于一種決策樹，希望你在閱讀本文之前已經(jīng)了解前文已經(jīng)介紹過之內(nèi)容：

• 《數(shù)據(jù)挖掘十大算法之決策樹詳解（1）》
• 《數(shù)據(jù)挖掘十大算法之決策樹詳解（2）》

歡迎關(guān)注白馬負(fù)金羈的博客?http://blog.csdn.net/baimafujinji，為保證公式、圖表得以正確顯示，強(qiáng)烈建議你從該地址上查看原版博文。本博客主要關(guān)注方向包括：數(shù)字圖像處理、算法設(shè)計(jì)與分析、數(shù)據(jù)結(jié)構(gòu)、機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、統(tǒng)計(jì)分析方法、自然語言處理。

---

CART生成

CART假設(shè)決策樹是二叉樹，內(nèi)部結(jié)點(diǎn)特征的取值為“是”和“否”，左分支是取值為“是”的分支，右分支是取值為“否”的分支。這樣的決策樹等價(jià)于遞歸地二分每個(gè)特征，將輸入空間即特征空間劃分為有限個(gè)單元，并在這些單元上確定預(yù)測的概率分布，也就是在輸入給定的條件下輸出的條件概率分布。

CART算法由以下兩步組成：

決策樹生成：基于訓(xùn)練數(shù)據(jù)集生成決策樹，生成的決策樹要盡量大；

決策樹剪枝：用驗(yàn)證數(shù)據(jù)集對已生成的樹進(jìn)行剪枝并選擇最優(yōu)子樹，這時(shí)損失函數(shù)最小作為剪枝的標(biāo)準(zhǔn)。

CART決策樹的生成就是遞歸地構(gòu)建二叉決策樹的過程。CART決策樹既可以用于分類也可以用于回歸。本文我們僅討論用于分類的CART。對分類樹而言，CART用Gini系數(shù)最小化準(zhǔn)則來進(jìn)行特征選擇，生成二叉樹。 CART生成算法如下：

輸入：訓(xùn)練數(shù)據(jù)集DD，停止計(jì)算的條件：?
輸出：CART決策樹。

根據(jù)訓(xùn)練數(shù)據(jù)集，從根結(jié)點(diǎn)開始，遞歸地對每個(gè)結(jié)點(diǎn)進(jìn)行以下操作，構(gòu)建二叉決策樹：

設(shè)結(jié)點(diǎn)的訓(xùn)練數(shù)據(jù)集為DD，計(jì)算現(xiàn)有特征對該數(shù)據(jù)集的Gini系數(shù)。此時(shí)，對每一個(gè)特征AA，對其可能取的每個(gè)值aa，根據(jù)樣本點(diǎn)對A=aA=a的測試為“是”或 “否”將DD分割成D1D1和D2D2兩部分，計(jì)算A=aA=a時(shí)的Gini系數(shù)。

在所有可能的特征AA以及它們所有可能的切分點(diǎn)aa中，選擇Gini系數(shù)最小的特征及其對應(yīng)的切分點(diǎn)作為最優(yōu)特征與最優(yōu)切分點(diǎn)。依最優(yōu)特征與最優(yōu)切分點(diǎn)，從現(xiàn)結(jié)點(diǎn)生成兩個(gè)子結(jié)點(diǎn)，將訓(xùn)練數(shù)據(jù)集依特征分配到兩個(gè)子結(jié)點(diǎn)中去。

對兩個(gè)子結(jié)點(diǎn)遞歸地調(diào)用步驟l~2，直至滿足停止條件。

生成CART決策樹。

算法停止計(jì)算的條件是結(jié)點(diǎn)中的樣本個(gè)數(shù)小于預(yù)定閾值，或樣本集的Gini系數(shù)小于預(yù)定閾值（樣本基本屬于同一類），或者沒有更多特征。

---

一個(gè)具體的例子

下面來看一個(gè)具體的例子。我們使用《數(shù)據(jù)挖掘十大算法之決策樹詳解（1）》中圖4-6所示的數(shù)據(jù)集來作為示例，為了便于后面的敘述，我們將其再列出如下：?

?

?

首先對數(shù)據(jù)集非類標(biāo)號屬性{是否有房，婚姻狀況，年收入}分別計(jì)算它們的Gini系數(shù)增益，取Gini系數(shù)增益值最大的屬性作為決策樹的根節(jié)點(diǎn)屬性。根節(jié)點(diǎn)的Gini系數(shù)?

Gini(是否拖欠貸款)=1?(310)2?(710)2=0.42Gini(是否拖欠貸款)=1?(310)2?(710)2=0.42

當(dāng)根據(jù)是否有房來進(jìn)行劃分時(shí)，Gini系數(shù)增益計(jì)算過程為?

?

?

?

Gini(左子節(jié)點(diǎn))=1?(03)2?(33)2=0Gini(右子節(jié)點(diǎn))=1?(37)2?(47)2=0.4898Gini(左子節(jié)點(diǎn))=1?(03)2?(33)2=0Gini(右子節(jié)點(diǎn))=1?(37)2?(47)2=0.4898

?

Δ{是否有房}=0.42?710×0.4898?310×0=0.077Δ{是否有房}=0.42?710×0.4898?310×0=0.077

?

若按婚姻狀況屬性來劃分，屬性婚姻狀況有三個(gè)可能的取值{married，single，divorced}，分別計(jì)算劃分后的

• {married} | {single,divorced}
• {single} | {married,divorced}
• {divorced} | {single,married}

的Gini系數(shù)增益。?
當(dāng)分組為{married} | {single,divorced}時(shí)，SlSl表示婚姻狀況取值為married的分組，SrSr表示婚姻狀況取值為single或者divorced的分組?

Δ{婚姻狀況}=0.42?410×0?610×[1?(36)2?(36)2]=0.12Δ{婚姻狀況}=0.42?410×0?610×[1?(36)2?(36)2]=0.12

當(dāng)分組為{single} | {married,divorced}時(shí)，?

Δ{婚姻狀況}=0.42?410×0.5?610×[1?(16)2?(56)2]=0.053Δ{婚姻狀況}=0.42?410×0.5?610×[1?(16)2?(56)2]=0.053

當(dāng)分組為{divorced} | {single,married}時(shí)，?

Δ{婚姻狀況}=0.42?210×0.5?810×[1?(28)2?(68)2]=0.02Δ{婚姻狀況}=0.42?210×0.5?810×[1?(28)2?(68)2]=0.02

對比計(jì)算結(jié)果，根據(jù)婚姻狀況屬性來劃分根節(jié)點(diǎn)時(shí)取Gini系數(shù)增益最大的分組作為劃分結(jié)果，也就是{married} | {single,divorced}。

?

最后考慮年收入屬性，我們發(fā)現(xiàn)它是一個(gè)連續(xù)的數(shù)值類型。我們在前面的文章里已經(jīng)專門介紹過如何應(yīng)對這種類型的數(shù)據(jù)劃分了。對此還不是很清楚的朋友可以參考之前的文章，這里不再贅述。

對于年收入屬性為數(shù)值型屬性，首先需要對數(shù)據(jù)按升序排序，然后從小到大依次用相鄰值的中間值作為分隔將樣本劃分為兩組。例如當(dāng)面對年收入為60和70這兩個(gè)值時(shí)，我們算得其中間值為65。倘若以中間值65作為分割點(diǎn)。SlSl作為年收入小于65的樣本，SrSr表示年收入大于等于65的樣本，于是則得Gini系數(shù)增益為?

Δ(年收入)=0.42?110×0?910×[1?(69)2?(39)2]=0.02Δ(年收入)=0.42?110×0?910×[1?(69)2?(39)2]=0.02

其他值的計(jì)算同理可得，我們不再逐一給出計(jì)算過程，僅列出結(jié)果如下（最終我們?nèi)∑渲惺沟迷鲆孀畲蠡哪莻€(gè)二分準(zhǔn)則來作為構(gòu)建二叉樹的準(zhǔn)則）：?

?

注意，這與我們之前在《數(shù)據(jù)挖掘十大算法之決策樹詳解（1）》中得到的結(jié)果是一致的。最大化增益等價(jià)于最小化子女結(jié)點(diǎn)的不純性度量（Gini系數(shù)）的加權(quán)平均值，之前的表里我們列出的是Gini系數(shù)的加權(quán)平均值，現(xiàn)在的表里給出的是Gini系數(shù)增益。現(xiàn)在我們希望最大化Gini系數(shù)的增益。根據(jù)計(jì)算知道，三個(gè)屬性劃分根節(jié)點(diǎn)的增益最大的有兩個(gè)：年收入屬性和婚姻狀況，他們的增益都為0.12。此時(shí)，選取首先出現(xiàn)的屬性作為第一次劃分。

?

接下來，采用同樣的方法，分別計(jì)算剩下屬性，其中根節(jié)點(diǎn)的Gini系數(shù)為（此時(shí)是否拖欠貸款的各有3個(gè)records）

Gini(是否拖欠貸款)=1?(36)2?(36)2=0.5Gini(是否拖欠貸款)=1?(36)2?(36)2=0.5

與前面的計(jì)算過程類似，對于是否有房屬性，可得?

Δ{是否有房}=0.5?46×[1?(34)2?(14)2]?26×0=0.25Δ{是否有房}=0.5?46×[1?(34)2?(14)2]?26×0=0.25

對于年收入屬性則有：

?

?

?

?

最后我們構(gòu)建的CART如下圖所示：

?

?

?

最后我們總結(jié)一下，CART和C4.5的主要區(qū)別：

• C4.5采用信息增益率來作為分支特征的選擇標(biāo)準(zhǔn)，而CART則采用Gini系數(shù)；
• C4.5不一定是二叉樹，但CART一定是二叉樹。

---

關(guān)于過擬合以及剪枝

決策樹很容易發(fā)生過擬合，也就是由于對train數(shù)據(jù)集適應(yīng)得太好，反而在test數(shù)據(jù)集上表現(xiàn)得不好。這個(gè)時(shí)候我們要么是通過閾值控制終止條件避免樹形結(jié)構(gòu)分支過細(xì)，要么就是通過對已經(jīng)形成的決策樹進(jìn)行剪枝來避免過擬合。另外一個(gè)克服過擬合的手段就是基于Bootstrap的思想建立隨機(jī)森林（Random Forest）。關(guān)于剪枝的內(nèi)容可以參考文獻(xiàn)【2】以了解更多，如果有機(jī)會我也可能在后續(xù)的文章里討論它。

?

轉(zhuǎn)載于:https://www.cnblogs.com/Rubick7/p/8810644.html

總結(jié)

以上是生活随笔為你收集整理的数据挖掘资料的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。