一牌借、決策樹
分類決策樹模型是一種描述對實例進行分類的樹形結(jié)構(gòu)。決策樹由結(jié)點(node)和有向邊(directed edge)組成狰右。結(jié)點有兩種類型：內(nèi)部結(jié)點(internal node )和葉結(jié)點(leaf node)错敢。內(nèi)部結(jié)點表示一個特征或?qū)傩匀簦~結(jié)點表示一個類踩萎。（簡單說就是用我們熟悉的樹結(jié)構(gòu)去做回歸和分類）
學習時停局， 利用訓練數(shù)據(jù)， 根據(jù)損失函數(shù)最小化的原則建立決策樹模型香府。 預測時董栽， 對新的數(shù)據(jù)， 利用決策樹模型進行分類企孩。 決策樹學習通常包括3個步驟： 特征選擇锭碳、決策樹的生成和決策樹的修剪。
與決策樹相關(guān)的重要算法包括：CLS勿璃，ID3擒抛、 C4.5與CART。
決策樹的基本組成部分：決策結(jié)點补疑、分支闻葵、葉子
決策樹中最上面的節(jié)點稱為根結(jié)點。是整個決策樹的開始癣丧，每個分支是一個新的決策節(jié)點，或者是樹的葉子栈妆。每個決策結(jié)點代表一個問題或者決策胁编。通常對應待分類對象的屬性厢钧。每個葉結(jié)點代表一種可能的分類結(jié)果。
在沿著決策樹從上到下遍歷過程中嬉橙，在每個節(jié)點都有一個測試早直。對每個結(jié)點上問題的不同測試輸出導致不同的分歧，最后會打到一個葉子結(jié)點市框。這一過程就是利用決策樹進行分類的過程霞扬，利用若干個變量來判斷屬性的類別
決策樹與條件概率分布
決策樹還表示給定特征條件下類的條件概率分布。
條件概率分布定義在特征空間的一個劃分上枫振，將特征空間劃分為互不相交的單元或區(qū)域喻圃，并在每個單元定義的一個類的概率分布就構(gòu)成了一個條件概率分布。
決策樹的一條路徑對應于劃分中的一個單元粪滤。
決策樹所表示的條件概率分布由各個單元給定條件下類的條件概率分布組成斧拍。這個條件概率分布可以表示為P(Y|X)。 X取值于給定劃分下單元的集合杖小， Y取值于類的集合肆汹。 各葉結(jié)點（單元） 上的條件概率往往偏向某一個類， 即屬于某一類的概率較大予权。 決策樹分類時將該結(jié)點的實例強行分到條件概率大的那一類去昂勉。
決策樹學習
- 決策樹學習本質(zhì)上是從訓練數(shù)據(jù)集中歸納出一組分類規(guī)則。與訓練數(shù)據(jù)集不相矛盾的決策樹
- 能對訓練數(shù)據(jù)進行正確分類的決策樹可能有多個扫腺，也可能一個也沒有岗照。我們需要的是一個與訓練數(shù)據(jù)矛盾較小的決策樹，同時具有很好的泛化能力斧账。
- 決策樹學習是由訓練數(shù)據(jù)集估計條件概率模型谴返。基于特征空間劃分的類的條件概率模型有無窮多個
- 我們選擇的條件概率模型應該不僅對訓練數(shù)據(jù)有很好的擬合咧织，而且對未知數(shù)據(jù)有很好的預測嗓袱。
決策樹學習的策略：以損失函數(shù)為目標函數(shù)的最小化
二、決策樹算法
決策樹的學習算法分為三步：首先遞歸的選擇特征习绢、用選擇的特征構(gòu)造一個決策樹渠抹、解決過擬合進行決策樹剪枝。
1闪萄、特征選擇
特征選擇問題：特征選擇在于選取對訓練數(shù)據(jù)具有分類能力的特征梧却。通常特征選擇的準則是信息增益或信息增益比。
（1）信息增益：
熵：信息量大小的獨立败去，即表示隨機變量不確定性的度量放航。
假設有n個互不相容的時間a1,a2,a3,...,an,他們中有且僅有一個發(fā)生，則其平均的信息量（熵）可以如下度量：
熵越大圆裕，隨機變量的不確定性越大广鳍，從定義可驗證荆几。
設有隨機變量(X,Y)， 其聯(lián)合概率分布為
條件熵H(Y|X)表示在已知隨機變量X的條件下隨機變量Y的不確定性赊时。 隨機變量X給定的條件下隨機變量Y的條件熵（conditionalentropy） H(Y|X)吨铸， 定義為X給定條件下Y的條件概率分布的熵對X的數(shù)學期望：
當熵和條件熵中的概率由數(shù)據(jù)估計（特別是極大似然估計）得到時，所對應的熵與條件熵分別稱為經(jīng)驗熵和經(jīng)驗條件熵
信息增益：
特征A對訓練數(shù)據(jù)集D的信息增益g(D,A)祖秒， 定義為集合D的經(jīng)驗熵H(D)與特征A給定條件下D的經(jīng)驗條件熵H(D|A)之差诞吱， 即
信息增益表示得知特征X的信息而使得類Y 的信息的不確定性減少的程度
一般地，熵H(Y)與條件熵H(Y|X)之差稱為互信息
決策樹學習中的信息增益等價于訓練數(shù)據(jù)集中類與特征的互信息房维。
信息增益的算法
（2）信息增益比
特征A對訓練數(shù)據(jù)集D的信息增益比gR(D,A)定義為其信息增益g(D,A)與訓練數(shù)據(jù)集D關(guān)于特征A的值的熵HA(D)之比：
以信息增益作為劃分訓練數(shù)據(jù)集的特征，存在偏向于選擇取值較多的特征的問題歌焦，使用信息增益比可以對這一問題進行校正
2独撇、決策樹的生成
（1）ID3算法
ID3算法的核心：是在決策樹各個結(jié)點上應用信息增益準則選擇特征， 遞歸地構(gòu)建決策樹纷铣。
** 具體方法是：** 從根結(jié)點（root node） 開始，對結(jié)點計算所有可能的特征的信息增益战转， 選擇信息增益最大的特征作為結(jié)點的特征搜立， 由該特征的不同取值建立子結(jié)點颠通； 再對子結(jié)點遞歸地調(diào)用以上方法撵儿， 構(gòu)建決策樹淀歇； 直到所有特征的信息增益均很小或沒有特征可以選擇為止。 最后得到一個決策樹。
基本思想：以信息熵為度量满钟，用于決策樹節(jié)點的屬性選擇，每次優(yōu)先選取信息量最多的屬性，亦即能使熵值變?yōu)樽钚〉膶傩裕詷?gòu)造一顆熵值下降最快的決策樹膀捷，到葉子節(jié)點處的熵值為0，此時每個葉子節(jié)點對應的實例集中的實例屬于同一類。
（2）C4.5的生成算法
用信息增益比來選擇特征氓英。
（3）決策樹的枝剪
決策樹生成算法遞歸地產(chǎn)生決策樹， 直到不能繼續(xù)下去為止。 但這種操作容易造成過擬合現(xiàn)象虚青。
過擬合的原因在于學習時過多地考慮如何提高對訓練數(shù)據(jù)的正確分類， 從而構(gòu)建出過于復雜的決策樹。 解決這個問題的辦法是考慮決策樹的復雜度宪赶， 對已生成的決策樹進行簡化 。
在決策樹學習中將已生成的樹進行簡化的過程稱為剪枝（pruning） 引几。 具體地叽掘， 剪枝從已生成的樹上裁掉一些子樹或葉結(jié)點， 并將其根結(jié)點或父結(jié)點作為新的葉結(jié)點， 從而簡化分類樹模型辽幌。
決策樹學習的剪枝算法：
（4）CART算法
CART算法由兩部分組成：
- 決策樹生成
- 決策樹剪枝
回歸樹(目標變量是連續(xù)的)：平方誤差最小化
分類樹(目標變量是類別的)：Gini Index
CART與ID3不同
二元劃分：二叉樹不易產(chǎn)生數(shù)據(jù)碎片，精度往往也會高于多叉樹
CART中選擇變量的不純性獨立：
分類目標：Gini指標腐缤，Towing绍在、orderTowing
連續(xù)目標：最小平方殘差、最小絕對殘差
剪枝：用預剪枝或后剪枝對訓練集生長的樹進行剪枝
樹的建立：
如果目標變量是標稱的留攒，并且是具有兩個以上類別杰标，則CART可能考慮將目標類別合并成兩個超類別（雙化）腔剂；
如果目標變量是連續(xù)的胜茧，則CART算法找出一組基于樹的回歸方程來預測目標變量
CART的生成：
1、回歸樹的生成
如何對輸入空間進行劃分下翎？
最小二乘回歸樹生成算法
2、分類樹的生成
基尼指數(shù)：
CART生成算法
CART剪枝
兩步組成：
- 從生成算法產(chǎn)生的決策樹T0底端開始不斷剪枝宝当，直到T0的根結(jié)點视事，形成一個子樹序列{T0,T1...Tn}
- 通過交叉驗證法在獨立的驗證數(shù)據(jù)集上對子樹序列進行測試，從中選擇最優(yōu)子樹
1庆揩、剪枝郑口，形成一個子樹序列
2、在剪枝得到的子樹序列{T0,T1...Tn}中通過交叉驗證選取最優(yōu)子樹Ta.
利用獨立的驗證數(shù)據(jù)集盾鳞，測試子樹序列中各子樹的平方誤差或基尼指數(shù)，最小的決策樹就是最優(yōu)決策樹瞻离。
CART剪枝算法：
