這是繼hello world之后的第一次更新，主要是因?yàn)樵谙乱淮紊险n的時(shí)候我就要鼓起勇氣去講課了，所以要在這里記錄下來(lái)，好了，現(xiàn)在開始吧......
1 決策樹是什么呢？
我的理解是：比如一個(gè)人要決定一件事，就拿買一件東西來(lái)說(shuō)，這個(gè)東西有很多衡量指標(biāo)，比如價(jià)錢，質(zhì)量，以后的用途等等。這個(gè)人要做的就是在這些衡量指標(biāo)中衡量最后得出一個(gè)結(jié)果：買或者不買。
現(xiàn)在是官方解釋：根據(jù)數(shù)據(jù)的屬性采用樹狀結(jié)構(gòu)建立決策模型。決策樹模型常常用來(lái)解決分類和回歸問題。常見的算法包括 CART (Classification And Regression Tree)、ID3、C4.5、隨機(jī)森林 (Random Forest) 等。
決策樹是附加概率結(jié)果的一個(gè)樹狀的決策圖，是直觀的運(yùn)用統(tǒng)計(jì)概率分析的圖法。機(jī)器學(xué)習(xí)中決策樹是一個(gè)預(yù)測(cè)模型，它表示對(duì)象屬性和對(duì)象值之間的一種映射，樹中的每一個(gè)節(jié)點(diǎn)表示對(duì)象屬性的判斷條件，其分支表示符合節(jié)點(diǎn)條件的對(duì)象。樹的葉子節(jié)點(diǎn)表示對(duì)象所屬的預(yù)測(cè)結(jié)果。
2 決策樹的實(shí)例
下面是來(lái)自老師發(fā)的課件上的數(shù)據(jù)表
然后是根據(jù)ID3算法得出的決策樹
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?天氣
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?晴? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 多云? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?雨
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 濕度? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? P? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?風(fēng)
? ? ? ? ? ? ?高? ? ? ? ? ? ? ? ? ? ? ? ? 正常? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 有風(fēng)? ? ? ? ? ? ? ? ? ? ? ? 無(wú)風(fēng)
? ? ? ? ? ? N? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?P? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?N? ? ? ? ? ? ? ? ? ? ? ? ? ? ? P
我也不知道為什么從課件上復(fù)制下來(lái)的圖為什么粘貼不上來(lái)，這樣應(yīng)該也能看懂。
3 應(yīng)用ID3畫出決策樹
先明確幾個(gè)需要算的值：
1.信息熵
2.條件熵
3.互信息
一，現(xiàn)在開始算信息熵：
類別出現(xiàn)概率：
|S|表示例子集S的總數(shù)，|ui|表示類別ui的例子數(shù)。
??? 對(duì)9個(gè)正例和5個(gè)反例有：
P（u1）=9/14 ? P（u2）=5/14
H（U）=（9/14）log（14/9）+（5/14）log（14/5）=0.94bit
二，接下來(lái)是條件熵：
屬性A1取值vj時(shí)，類別ui的條件概率：
A1=天氣取值? v1=晴，v2=多云，v3=雨
在A1處取值晴的例子5個(gè)，取值多云的例子4 個(gè)，取值雨的例子5 個(gè)，故：
?????? P（v1）=5/14? P（v2）=4/14? P（v3）=5/14
取值為晴的5 個(gè)例子中有2 個(gè)正例、3個(gè)反例，故：
?????? P（u1/v1）=2/5， P（u2/v1）=3/5
同理有：P（u1/v2）=4/4， P（u2/v2）=0
?????? P（u1/v3）=2/5， P（u2/v3）=3/5
H(U/V)=(5/14)((2/5)log(5/2)+(3/5)log(5/3))+(4/14)((4/4)log(4/4)????????+0)+(5/14)((2/5)log(5/2)+(3/5)log(5/3)) = 0.694bit
三， 然后是互信息：
對(duì) A1=天氣處有：
???????? I（天氣）=H（U）- H（U|V）= 0.94 - 0.694 = 0.246 bit
???????? 類似可得：
???????? I（氣溫）=0.029 bit
???????? I（濕度）=0.151 bit
???????? I（風(fēng)）=0.048 bit
四，最后就可以畫樹了
ID3算法將選擇互信息最大的特征天氣作為樹根，在14個(gè)例子中對(duì)天氣的3個(gè)取值進(jìn)行分枝，3
個(gè)分枝對(duì)應(yīng)3
個(gè)子集，分別是:
??? F1={1，2，8，9，11}，F(xiàn)2={3，7，12，13}，F(xiàn)3={4，5，6，10，14}
???????? 其中F2中的例子全屬于P類，因此對(duì)應(yīng)分枝標(biāo)記為P，其余兩個(gè)子集既含有正例又含有反例，將遞歸調(diào)用建樹算法。
附：遞歸建樹
（1）F1中的天氣全取晴值，則H（U）=H（U|V），有I（U|V）=0，在余下三個(gè)特征中求出濕度互信息最大，以它為該分枝的根結(jié)點(diǎn)，再向下分枝。濕度取高的例子全為N類，該分枝標(biāo)記N。取值正常的例子全為P類，該分枝標(biāo)記P。
????? （2）在F3中，對(duì)四個(gè)特征求互信息，得到風(fēng)特征互信息最大，則以它為該分枝根結(jié)點(diǎn)。再向下分枝，風(fēng)取有風(fēng)時(shí)全為N類，該分枝標(biāo)記N。取無(wú)風(fēng)時(shí)全為P類，該分枝標(biāo)記P。
4 介紹一下剪枝操作
在分類模型建立的過(guò)程中，很容易出現(xiàn)過(guò)擬合的現(xiàn)象。過(guò)擬合是指在模型學(xué)習(xí)訓(xùn)練中，訓(xùn)練樣本達(dá)到非常高的逼近精度，但對(duì)檢驗(yàn)樣本的逼近誤差隨著訓(xùn)練次數(shù)而呈現(xiàn)出先下降后上升的現(xiàn)象。過(guò)擬合時(shí)訓(xùn)練誤差很小，但是檢驗(yàn)誤差很大，不利于實(shí)際應(yīng)用。
決策樹的過(guò)擬合現(xiàn)象可以通過(guò)剪枝進(jìn)行一定的修復(fù)。剪枝分為預(yù)先剪枝和后剪枝兩種。
預(yù)先剪枝指在決策樹生長(zhǎng)過(guò)程中，使用一定條件加以限制，使得產(chǎn)生完全擬合的決策樹之前就停止生長(zhǎng)。預(yù)先剪枝的判斷方法也有很多，比如信息增益小于一定閥值的時(shí)候通過(guò)剪枝使決策樹停止生長(zhǎng)。但如何確定一個(gè)合適的閥值也需要一定的依據(jù)，閥值太高導(dǎo)致模型擬合不足，閥值太低又導(dǎo)致模型過(guò)擬合。
后剪枝是在決策樹生長(zhǎng)完成之后，按照自底向上的方式修剪決策樹。后剪枝有兩種方式，一種用新的葉子節(jié)點(diǎn)替換子樹，該節(jié)點(diǎn)的預(yù)測(cè)類由子樹數(shù)據(jù)集中的多數(shù)類決定。
另一種用子樹中最常使用的分支代替子樹。預(yù)先剪枝可能過(guò)早的終止決策樹的生長(zhǎng)，后剪枝一般能夠產(chǎn)生更好的效果。但后剪枝在子樹被剪掉后，決策樹生長(zhǎng)的一部分計(jì)算就被浪費(fèi)了。
5 一些代碼（Matlab）和應(yīng)用論文
https://blog.csdn.net/lfdanding/article/details/50753239
基于決策樹的乳腺癌病歷文本的挖掘與決策_(dá)龔樂君
