㈠ 決策樹的原理及演算法
決策樹基本上就是把我們以前的經驗總結出來。我給你准備了一個打籃球的訓練集。如果我們要出門打籃球，一般會根據「天氣」、「溫度」、「濕度」、「刮風」這幾個條件來判斷，最後得到結果：去打籃球？還是不去？
上面這個圖就是一棵典型的決策樹。我們在做決策樹的時候，會經歷兩個階段：構造和剪枝。
構造就是生成一棵完整的決策樹。簡單來說，構造的過程就是選擇什麼屬性作為節點的過程，那麼在構造過程中，會存在三種節點：
根節點：就是樹的最頂端，最開始的那個節點。在上圖中，「天氣」就是一個根節點；
內部節點：就是樹中間的那些節點，比如說「溫度」、「濕度」、「刮風」；
葉節點：就是樹最底部的節點，也就是決策結果。
剪枝就是給決策樹瘦身，防止過擬合。分為「預剪枝」（Pre-Pruning）和「後剪枝」（Post-Pruning）。
預剪枝是在決策樹構造時就進行剪枝。方法是在構造的過程中對節點進行評估，如果對某個節點進行劃分，在驗證集中不能帶來准確性的提升，那麼對這個節點進行劃分就沒有意義，這時就會把當前節點作為葉節點，不對其進行劃分。
後剪枝就是在生成決策樹之後再進行剪枝，通常會從決策樹的葉節點開始，逐層向上對每個節點進行評估。如果剪掉這個節點子樹，與保留該節點子樹在分類准確性上差別不大，或者剪掉該節點子樹，能在驗證集中帶來准確性的提升，那麼就可以把該節點子樹進行剪枝。
1是欠擬合，3是過擬合，都會導致分類錯誤。
造成過擬合的原因之一就是因為訓練集中樣本量較小。如果決策樹選擇的屬性過多，構造出來的決策樹一定能夠「完美」地把訓練集中的樣本分類，但是這樣就會把訓練集中一些數據的特點當成所有數據的特點，但這個特點不一定是全部數據的特點，這就使得這個決策樹在真實的數據分類中出現錯誤，也就是模型的「泛化能力」差。
p(i|t) 代表了節點 t 為分類 i 的概率，其中 log2 為取以 2 為底的對數。這里我們不是來介紹公式的，而是說存在一種度量，它能幫我們反映出來這個信息的不確定度。當不確定性越大時，它所包含的信息量也就越大，信息熵也就越高。
ID3 演算法計算的是信息增益，信息增益指的就是劃分可以帶來純度的提高，信息熵的下降。它的計算公式，是父親節點的信息熵減去所有子節點的信息熵。
公式中 D 是父親節點，Di 是子節點，Gain(D,a) 中的 a 作為 D 節點的屬性選擇。
因為 ID3 在計算的時候，傾向於選擇取值多的屬性。為了避免這個問題，C4.5 採用信息增益率的方式來選擇屬性。信息增益率 = 信息增益 / 屬性熵，具體的計算公式這里省略。
當屬性有很多值的時候，相當於被劃分成了許多份，雖然信息增益變大了，但是對於 C4.5 來說，屬性熵也會變大，所以整體的信息增益率並不大。
ID3 構造決策樹的時候，容易產生過擬合的情況。在 C4.5 中，會在決策樹構造之後採用悲觀剪枝（PEP），這樣可以提升決策樹的泛化能力。
悲觀剪枝是後剪枝技術中的一種，通過遞歸估算每個內部節點的分類錯誤率，比較剪枝前後這個節點的分類錯誤率來決定是否對其進行剪枝。這種剪枝方法不再需要一個單獨的測試數據集。
C4.5 可以處理連續屬性的情況，對連續的屬性進行離散化的處理。比如打籃球存在的「濕度」屬性，不按照「高、中」劃分，而是按照濕度值進行計算，那麼濕度取什麼值都有可能。該怎麼選擇這個閾值呢，C4.5 選擇具有最高信息增益的劃分所對應的閾值。
針對數據集不完整的情況，C4.5 也可以進行處理。
暫無
請你用下面的例子來模擬下決策樹的流程，假設好蘋果的數據如下，請用 ID3 演算法來給出好蘋果的決策樹。
「紅」的信息增益為：1「大」的信息增益為：0
因此選擇「紅」的作為根節點，「大」沒有用，剪枝。
數據分析實戰45講.17 丨決策樹（上）：要不要去打籃球？決策樹來告訴你
㈡ 決策樹分類演算法有哪些
問題一：決策樹演算法是按什麼來進行分類的 決策樹演算法是一種逼近離散函數值的方法。它是一種典型的分類方法，首先對數據進行處理，利用歸納演算法生成可讀的規則和決策樹，然後使用決策對新數據進行分析。本質上決策樹是通過一系列規則對數據進行分類的過程。
決策樹方法最早產生於上世紀60年代，到70年代末。由J Ross Quinlan提出了ID3演算法，此演算法的目的在於減少樹的深度。但是忽略了葉子數目的研究。C4.5演算法在ID3演算法的基礎上進行了改進，對於預測變數的缺值處理、剪枝技術、派生規則等方面作了較大改進，既適合於分類問題，又適合於回歸問題。
決策樹演算法構造決策樹來發現數據中蘊涵的分類規則．如何構造精度高、規模小的決策樹是決策樹演算法的核心內容。決策樹構造可以分兩步進行。第一步，決策樹的生成：由訓練樣本集生成決策樹的過程。一般情況下，訓練樣本數據集是根據實際需要有歷史的、有一定綜合程度的，用於數據分析處理的數據集。第二步，決策樹的剪枝：決策樹的剪枝是對上一階段生成的決策樹進行檢驗、校正和修下的過程，主要是用新的樣本數據集（稱為測試數據集）中的數據校驗決策樹生成過程中產生的初步規則，將那些影響預衡准確性的分枝剪除。
問題二：數據挖掘分類方法決策樹可以分多類么 數據挖掘,也稱之為資料庫中知識發現是一個可以從海量數據中智能地和自動地抽取一些有用的、可信的、有效的和可以理解的模式的過程.分類是數據挖掘的重要內容之一.目前,分類已廣泛應用於許多領域,如醫療診斷、天氣預測、信用證實、顧客區分、欺詐甄別. 現己有多種分類的方法,其中決策樹分類法在海量數據環境中應用最為廣泛.其原因如下：
1、決策樹分類的直觀的表示方法較容易轉化為標準的資料庫查詢
2、決策樹分類歸納的方法行之有效,尤其適合大型數據集.
3、決策樹在分類過程中,除了數據集中已包括的信息外,不再需要額外的信息.
4、決策樹分類模型的精確度較高. 該文首先研究了評估分類模型的方法.在此基礎上著重研究了決策樹分類方法,並對決策樹演算法的可伸縮性問題進行了具體分析,最後給出了基於OLE DB for DM開發決策樹分類預測應用程序.
問題三：基於規則的分類器（比如用RIPPER演算法）和決策樹的區別在哪，使用場景有什麼不同？ 決策樹實際上是規則分類器。基於轉換的錯誤驅動學習方法的提出者曾經在論文中論證過這個問題，他的學習方法是規則學習器，但和決策樹等價。
問題四：決策樹的優缺點是什麼啊 決策樹(Decision Tree)是在已知各種情況發生概率的基礎上，通過構成決策樹來求取凈現值的期望值大於等於零的概率，評價項目風險，判斷其可行性的決策分析方法，是直觀運用概率分析的一種圖解法。
決策樹的優缺點：
優點：
1) 可以生成可以理解的規則。
2) 計算量相對來說不是很大。
3) 可以處理連續和種類字穿。
4) 決策樹可以清晰的顯示哪些欄位比較重要
缺點：
1) 對連續性的欄位比較難預測。
2) 對有時間順序的數據，需要很多預處理的工作。
3) 當類別太多時，錯誤可能就會增加的比較快。
4) 一般的演算法分類的時候，只是根據一個欄位來分類。
問題五：c4.5決策樹演算法怎麼得到分類結果 決策樹主要有ID3，C4.5，CART等形式。ID3選取信息增益的屬性遞歸進行分類，C4.5改進為使用信息增益率來選取分類屬性。CART是Classfication and Regression Tree的縮寫。表明CART不僅可以進行分類，也可以進行回歸。
問題六：決策樹分類演算法的適用領域，不要概括成經濟、社會、醫療領域，具體到實際問題。且用什麼軟體實現較方便。 決策樹演算法主要用於數據挖掘和機器學習，數據挖掘就是從海量數據中找出規律。一個有名的例子就是啤酒和尿布的例子，這是數據挖掘的典型。決策樹演算法包括ID3，C4.5，CART等，各種演算法都是利用海量的數據來生成決策樹的，決策樹能幫助人或者機器做出決策。最簡單的一個例子就是你去看病，根據決策樹，醫生能夠判斷這是什麼病。軟體的話用VISUAL STUDIO就可以，C語言，C++,C#，java都可以。
問題七：貝葉斯網路和貝葉斯分類演算法的區別 貝葉斯分類演算法是統計學的一種分類方法，它是一類利用概率統計知識進行分類的演算法。在許多場合，樸素貝葉斯(Na?ve Bayes，NB)分類演算法可以與決策樹和神經網路分類演算法相媲美，該演算法能運用到大型資料庫中，而且方法簡單、分類准確率高、速度快。
由於貝葉斯定理假設一個屬性值對給定類的影響獨立於其它屬性的值，而此假設在實際情況中經常是不成立的，因此其分類准確率可能會下降。為此，就衍生出許多降低獨立性假設的貝葉斯分類演算法，如TAN(tree augmented Bayes network)演算法。
㈢ 機器學習故事匯-決策樹演算法
機器學習故事匯-決策樹演算法
【咱們的目標】系列演算法講解旨在用最簡單易懂的故事情節幫助大家掌握晦澀無趣的機器學習，適合對數學很頭疼的同學們，小板凳走起！
決策樹模型是機器學習中最經典的演算法之一啦，用途之廣泛我就不多吹啦，其實很多機器學習演算法都是以樹模型為基礎的，比如隨機森林,Xgboost等一聽起來就是很牛逼的演算法（其實用起來也很牛逼）。
首先我們來看一下在上面的例子中我想根據人的年齡和性別（兩個特徵）對5個人（樣本數據）進行決策，看看他們喜不喜歡玩電腦游戲。首先根據年齡（根節點）進行了一次分支決策，又對左節點根據性別進行了一次分支決策，這樣所有的樣本都落到了最終的葉子節點，可以把每一個葉子節點當成我們最終的決策結果（比如Y代表喜歡玩游戲，N代表不喜歡玩游戲）。這樣我們就通過決策樹完成了非常簡單的分類任務！
再來看一下樹的組成，主要結構有根節點（數據來了之後首先進行判斷的特徵），非葉子節點（中間的一系列過程），葉子節點（最終的結果），這些都是我們要建立的模塊！
在決策中樹中，我們剛才的喜歡玩電腦游戲的任務看起來很簡單嘛，從上往下去走不就OK了嗎！但是難點在於我們該如何構造這棵決策樹（節點的選擇以及切分），這個看起來就有些難了，因為當我們手裡的數據特徵比較多的時候就該猶豫了，到底拿誰當成是根節點呢？
這個就是我們最主要的問題啦，節點究竟該怎麼選呢？不同的位置又有什麼影響？怎麼對特徵進行切分呢？一些到這，我突然想起來一個段子，咱們來樂呵樂呵！
武林外傳中這個段子夠我笑一年的，其實咱們在推導機器學習演算法的時候，也需要這么去想想，只有每一步都是有意義的我們才會選擇去使用它。回歸正題，我們選擇的根節點其實意味著它的重要程度是最大的，相當於大當家了，因為它會對數據進行第一次切分，我們需要把最重要的用在最關鍵的位置，在決策樹演算法中，為了使得演算法能夠高效的進行，那麼一開始就應當使用最有價值的特徵。
接下來咱們就得嘮嘮如何選擇大當家了，我們提出了一個概念叫做熵（不是我提出的。。。穿山甲說的），這里並不打算說的那麼復雜，一句話解釋一下，熵代表你經過一次分支之後分類的效果的好壞，如果一次分支決策後都屬於一個類別（理想情況下，也是我們的目標）這時候我們認為效果很好嘛，那熵值就很低。如果分支決策後效果很差，什麼類別都有，那麼熵值就會很高，公式已經給出，log函數推薦大家自己畫一下，然後看看概率[0,1]上的時候log函數值的大小（你會豁然開朗的）。
不確定性什麼時候最大呢？模稜兩可的的時候（就是你猶豫不決的時候）這個時候熵是最大的，因為什麼類別出現的可能性都有。那麼我們該怎麼選大當家呢？（根節點的特徵）當然是希望經過大當家決策後，熵值能夠下降（意味著類別更純凈了，不那麼混亂了）。在這里我們提出了一個詞叫做信息增益（就當是我提出的吧。。。），信息增益表示經過一次決策後整個分類後的數據的熵值下降的大小，我們希望下降越多越好，理想情況下最純凈的熵是等於零的。
一個栗子：准備一天一個哥們打球的時候，包括了4個特徵（都是環境因素）以及他最終有木有去打球的數據。
第一個問題：大當家該怎麼選？也就是我們的根節點用哪個特徵呢？
一共有4個特徵，看起來好像用誰都可以呀，這個時候就該比試比試了，看看誰的能力強（使得熵值能夠下降的最多）
在歷史數據中，首先我們可以算出來當前的熵值，計算公式同上等於0.940，大當家的競選我們逐一來分析，先看outlook這個特徵，上圖給出了基於天氣的劃分之後的熵值，計算方式依舊同上，比如outlook=sunny時，yes有2個,no有三個這個時候熵就直接將2/5和3/5帶入公式就好啦。最終算出來了3種情況下的熵值。
再繼續來看！outlook取不同情況的概率也是不一樣的，這個是可以計算出來的相當於先驗概率了，直接可以統計出來的，這個也需要考慮進來的。然後outlook競選大當家的分值就出來啦（就是信息增益）等於0.247。同樣的方法其餘3個特徵的信息增益照樣都可以計算出來，誰的信息增益多我們就認為誰是我們的大當家，這樣就完成了根節點的選擇，接下來二當家以此類推就可以了！
我們剛才給大家講解的是經典的ID3演算法，基於熵值來構造決策樹，現在已經有很多改進，比如信息增益率和CART樹。簡單來說一下信息增益率吧，我們再來考慮另外一個因素，如果把數據的樣本編號當成一個特徵，那麼這個特徵必然會使得所有數據完全分的開，因為一個樣本只對應於一個ID，這樣的熵值都是等於零的，所以為了解決這類特徵引入了信息增益率，不光要考慮信息增益還要考慮特徵自身的熵值。說白了就是用 信息增益/自身的熵值 來當做信息增益率。
我們剛才討論的例子中使用的是離散型的數據，那連續值的數據咋辦呢？通常我們都用二分法來逐一遍歷來找到最合適的切分點！
下面再來嘮一嘮決策樹中的剪枝任務，為啥要剪枝呢？樹不是好好的嗎，剪個毛線啊！這個就是機器學習中老生常談的一個問題了，過擬合的風險，說白了就是如果一個樹足夠龐大，那麼所有葉子節點可能只是一個數據點（無限制的切分下去），這樣會使得我們的模型泛化能力很差，在測試集上沒辦法表現出應有的水平，所以我們要限制決策樹的大小，不能讓枝葉太龐大了。
最常用的剪枝策略有兩種：
（1）預剪枝：邊建立決策樹邊開始剪枝的操作
（2）後剪枝：建立完之後根據一定的策略來修建
這些就是我們的決策樹演算法啦，其實還蠻好的理解的，從上到下基於一種選擇標准（熵，GINI系數）來找到最合適的當家的就可以啦！
㈣ 決策樹之CART演算法
一、基本概念
1.cart使用基尼系數作為劃分標准。基尼系數越小，則不純度越低，區分的越徹底。
2.假設有k個類別，第k個類別的概率為 ,則基尼系數表達式為：
Gini(p)= (1- )=1-
3.對於樣本D，如果根據特徵A 的值把樣本分為D1,D2兩部分，則在特徵A條件下，D的基尼系數
Gini(D,A)= Gini(D1)+ Gini(D2)
4.CART建立起來的是二叉樹，如果特徵A有A1,A2，A3三個類別，CART會考慮把A分成{A1},{A2 ,A3}兩組，或者是其他兩種情況。由於這次A並沒有完全分開，所以下次還有機會在子節點把A2,A3分開.
5.對於連續值的切分.假如有1 2 3 4 5 那麼cart會有4個切分點 [1.5 2.5 3.5 4.5]
二.實例推導樹的建立過程
1.假設我有以下源數據
序號 天氣 周末 促銷 銷量
1 壞 是 是 高
2 壞 是 是 高
3 壞 是 是 高
4 壞 否 是 高
5 壞 是 是 高
6 壞 否 是 高
7 壞 是 否 高
8 好 是 是 高
9 好 是 否 高
10 好 是 是 高
11 好 是 是 高
12 好 是 是 高
13 好 是 是 高
14 壞 是 是 低
15 好 否 是 高
16 好 否 是 高
17 好 否 是 高
18 好 否 是 高
19 好 否 否 高
20 壞 否 否 低
21 壞 否 是 低
22 壞 否 是 低
23 壞 否 是 低
24 壞 否 否 低
25 壞 是 否 低
26 好 否 是 低
27 好 否 是 低
28 壞 否 否 低
29 壞 否 否 低
30 好 否 否 低
31 壞 是 否 低
32 好 否 是 低
33 好 否 否 低
34 好 否 否 低
該數據集有三個特徵 天氣 周末 促銷
2.為了簡化建立樹的過程,我將忽略基尼系數與樣本個數閥值
2.1 首先計算各個特徵值對數據集的基尼系數,公式見---- 基本概念.3
Gini(D|天氣)=17/34*(1-(11/17)^2-(6/17)^2)+17/34*(1-(7/17)^2-(10/17)^2)=0.4706
Gini(D|周末)=20/34*(1-(7/20)^2-(13/20)^2)+14/34*(1-(11/14)^2-(3/14)^2)=0.4063
Gini(D|促銷)=12/34*(1-(9/12)^2-(3/12)^2)+22/34*(1-(7/22)^2-(15/22)^2)=0.4131
周末的基尼系數最小，這也符合我們的一般認識
2.2 第一個分列特徵選擇周末。此時數據集按照是否周末分成兩個。
Gini(周末|天氣)=0.2679
Gini(周末|促銷)=0.2714
Gini(非周末|天氣)=0.3505
Gini(非周末|促銷)=0.3875
此時，周末應該以天氣作為劃分，非周末也是以天氣作為劃分，下面放個圖
三、CART樹對於連續特徵的處理
假如特徵A為連續型變數，則把特徵A按照從小到大進行排序，取相鄰兩點的平均值為切分點，計算基尼系數。則基尼系數最小的點為切分點，大於切分點的為一類，小於切分點的為另一類。舉例：特徵A的值為 1，2，3，4，5，6 目標變數是高、低、高、低、高、低。則1.5處的基尼系數為 (1/6)*(1-1^2)+(5/6)*(1-(2/5)^2-(3/5)^2)=0.4 2.5處的基尼系數為 (2/6)*(1-(1/2)^2-(1/2)^2)+(4/6)*(1-(2/4)^2-(2/4)^2)=0.5 3.5處的基尼系數為 (3/6)*(1-(1/3)^2-(2/3)^2)+(3/6)*(1-(1/3)^2-(2/3)^2)=0.44 4.5處的基尼系數為 (4/6)*(1-(2/4)^2-(2/4)^2)+(2/6)*(1-(1/2)^2-(1/2)^2)=0.5 5.5處的基尼系數為 (5/6)*(1-(2/5)^2-(3/5)^2)+(1/6)*(1-1^2)=0.4 結論： 1.5和5.5處的基尼系數最小，可以把1分為一類，2-6分為另一類。或者6分為一類，1-5另一類。
四、關於回歸樹
1.回歸樹和分類樹的區別在於輸出值類型不同。分類樹輸出的是離散值，回歸樹輸出的是連續值。
2.和分類樹使用基尼系數不同，回歸樹使用和均方差來度量最佳分隔點。假設有1 2 3 4 5 6 六個數。假設3.5處把數據分開最合適，那麼(1-2)^2+(2-2)^2+(3-2)^2+(4-5)^2+(5-5)^2+(6-5)^2在所有分割點中取得最小值。2，5為各自數據段的平均值。
3.回歸樹採用最後葉子的平均值或者中值作為輸出結果
㈤ 決策樹演算法-原理篇
關於決策樹演算法，我打算分兩篇來講，一篇講思想原理，另一篇直接擼碼來分析演算法。本篇為原理篇。
通過閱讀這篇文章，你可以學到：
1、決策樹的本質
2、決策樹的構造過程
3、決策樹的優化方向
決策樹根據使用目的分為：分類樹和回歸樹，其本質上是一樣的。本文只講分類樹。
決策樹，根據名字來解釋就是，使用樹型結構來模擬決策。
用圖形表示就是下面這樣。
其中橢圓形代表：特徵或屬性。長方形代表：類別結果。
面對一堆數據（含有特徵和類別），決策樹就是根據這些特徵（橢圓形）來給數據歸類（長方形）
例如，信用貸款問題，我根據《神奇動物在哪裡》的劇情給銀行造了個決策樹模型，如下圖：
然而，決定是否貸款可以根據很多特徵，然麻雞銀行選擇了：（1）是否房產價值>100w；（2）是否有其他值錢的抵押物；（3）月收入>10k；（4）是否結婚；這四個特徵，來決定是否給予貸款。
先不管是否合理，但可以肯定的是，決策樹做了特徵選擇工作，即選擇出類別區分度高的特徵。
由此可見， 決策樹其實是一種特徵選擇方法。 （特徵選擇有多種，決策樹屬於嵌入型特徵選擇，以後或許會講到，先給個圖）即選擇區分度高的特徵子集。
那麼， 從特徵選擇角度來看決策樹，決策樹就是嵌入型特徵選擇技術
同時，決策樹也是機器學習中經典分類器演算法，通過決策路徑，最終能確定實例屬於哪一類別。
那麼， 從分類器角度來看決策樹，決策樹就是樹型結構的分類模型
從人工智慧知識表示法角度來看，決策樹類似於if-then的產生式表示法。
那麼， 從知識表示角度來看決策樹，決策樹就是if-then規則的集合
由上面的例子可知，麻雞銀行通過決策樹模型來決定給哪些人貸款，這樣決定貸款的流程就是固定的，而不由人的主觀情感來決定。
那麼， 從使用者角度來看決策樹，決策樹就是規范流程的方法
最後我們再來看看決策樹的本質是什麼已經不重要了。
決策樹好像是一種思想，而通過應用在分類任務中從而成就了「決策樹演算法」。
下面內容還是繼續講解用於分類的「決策樹演算法」。
前面講了決策樹是一種 特徵選擇技術 。
既然決策樹就是一種特徵選擇的方法，那麼經典決策樹演算法其實就是使用了不同的特徵選擇方案。
如：
（1）ID3：使用信息增益作為特徵選擇
（2）C4.5：使用信息增益率作為特徵選擇
（3）CART：使用GINI系數作為特徵選擇
具體選擇的方法網上一大把，在這里我提供幾個鏈接，不細講。
但，不僅僅如此。
決策樹作為嵌入型特徵選擇技術結合了特徵選擇和分類演算法，根據特徵選擇如何生成分類模型也是決策樹的一部分。
其生成過程基本如下：
根據這三個步驟，可以確定決策樹由：（1）特徵選擇；（2）生成方法；（3）剪枝，組成。
決策樹中學習演算法與特徵選擇的關系如下圖所示：
原始特徵集合T：就是包含收集到的原始數據所有的特徵，例如：麻瓜銀行收集到與是否具有償還能力的所有特徵，如：是否結婚、是否擁有100w的房產、是否擁有汽車、是否有小孩、月收入是否>10k等等。
中間的虛線框就是特徵選擇過程，例如：ID3使用信息增益、C4.5使用信息增益率、CART使用GINI系數。
其中評價指標（如：信息增益）就是對特徵的要求，特徵需要滿足這種條件（一般是某個閾值），才能被選擇，而這一選擇過程嵌入在學習演算法中，最終被選擇的特徵子集也歸到學習演算法中去。
這就是抽象的決策樹生成過程，不論哪種演算法都是將這一抽象過程的具體化。
其具體演算法我將留在下一篇文章來講解。
而決策樹的剪枝，其實用得不是很多，因為很多情況下隨機森林能解決決策樹帶來的過擬合問題，因此在這里也不講了。
決策樹的優化主要也是圍繞決策樹生成過程的三個步驟來進行優化的。
樹型結構，可想而知，演算法效率決定於樹的深度，優化這方面主要從特徵選擇方向上優化。
提高分類性能是最重要的優化目標，其主要也是特徵選擇。
面對過擬合問題，一般使用剪枝來優化，如：李國和基於決策樹生成及剪枝的數據集優化及其應用。
同時，決策樹有很多不足，如：多值偏向、計算效率低下、對數據空缺較為敏感等，這方面的優化也有很多，大部分也是特徵選擇方向，如：陳沛玲使用粗糙集進行特徵降維。
由此，決策樹的優化方向大多都是特徵選擇方向，像ID3、C4.5、CART都是基於特徵選擇進行優化。
參考文獻
統計學習方法-李航
特徵選擇方法綜述-李郅琴
決策樹分類演算法優化研究_陳沛玲
基於決策樹生成及剪枝的數據集優化及其應用-李國和
㈥ 數據挖掘-決策樹演算法
決策樹演算法是一種比較簡易的監督學習分類演算法，既然叫做決策樹，那麼首先他是一個樹形結構，簡單寫一下樹形結構（數據結構的時候學過不少了）。
樹狀結構是一個或多個節點的有限集合，在決策樹里，構成比較簡單，有如下幾種元素：
在決策樹中，每個葉子節點都有一個類標簽，非葉子節點包含對屬性的測試條件，用此進行分類。
所以個人理解，決策樹就是 對一些樣本，用樹形結構對樣本的特徵進行分支，分到葉子節點就能得到樣本最終的分類，而其中的非葉子節點和分支就是分類的條件，測試和預測分類就可以照著這些條件來走相應的路徑進行分類。
根據這個邏輯，很明顯決策樹的關鍵就是如何找出決策條件和什麼時候算作葉子節點即決策樹終止。
決策樹的核心是為不同類型的特徵提供表示決策條件和對應輸出的方法，特徵類型和劃分方法包括以下幾個：
注意，這些圖中的第二層都是分支，不是葉子節點。
如何合理的對特徵進行劃分，從而找到最優的決策模型呢？在這里需要引入信息熵的概念。
先來看熵的概念：
在數據集中，參考熵的定義，把信息熵描述為樣本中的不純度，熵越高，不純度越高，數據越混亂（越難區分分類）。
例如：要給（0，1）分類，熵是0，因為能明顯分類，而均衡分布的（0.5，0.5）熵比較高，因為難以劃分。
信息熵的計算公式為：
其中 代表信息熵。 是類的個數， 代表在 類時 發生的概率。
另外有一種Gini系數，也可以用來衡量樣本的不純度：
其中 代表Gini系數，一般用於決策樹的 CART演算法 。
舉個例子：
如果有上述樣本，那麼樣本中可以知道，能被分為0類的有3個，分為1類的也有3個，那麼信息熵為：
Gini系數為：
總共有6個數據，那麼其中0類3個，佔比就是3/6，同理1類。
我們再來計算一個分布比較一下：
信息熵為：
Gini系數為：
很明顯，因為第二個分布中，很明顯這些數偏向了其中一類，所以 純度更高 ，相對的信息熵和Gini系數較低。
有了上述的概念，很明顯如果我們有一組數據要進行分類，最快的建立決策樹的途徑就是讓其在每一層都讓這個樣本純度最大化，那麼就要引入信息增益的概念。
所謂增益，就是做了一次決策之後，樣本的純度提升了多少（不純度降低了多少），也就是比較決策之前的樣本不純度和決策之後的樣本不純度，差越大，效果越好。
讓信息熵降低，每一層降低的越快越好。
度量這個信息熵差的方法如下：
其中 代表的就是信息熵（或者其他可以度量不純度的系數）的差， 是樣本(parent是決策之前， 是決策之後)的信息熵（或者其他可以度量不純度的系數）， 為特徵值的個數， 是原樣本的記錄總數， 是與決策後的樣本相關聯的記錄個數。
當選擇信息熵作為樣本的不純度度量時，Δ就叫做信息增益 。
我們可以遍歷每一個特徵，看就哪個特徵決策時，產生的信息增益最大，就把他作為當前決策節點，之後在下一層繼續這個過程。
舉個例子：
如果我們的目標是判斷什麼情況下，銷量會比較高（受天氣，周末，促銷三個因素影響），根據上述的信息增益求法，我們首先應該找到根據哪個特徵來決策，以信息熵為例：
首先肯定是要求 ，也就是銷量這個特徵的信息熵：
接下來，就分別看三個特徵關於銷量的信息熵，先看天氣，天氣分為好和壞兩種，其中天氣為好的條件下，銷量為高的有11條，低的有6條；天氣壞時，銷量為高的有7條，銷量為低的有10條，並且天氣好的總共17條，天氣壞的總共17條。
分別計算天氣好和天氣壞時的信息熵，天氣好時：
根據公式 ，可以知道，N是34，而天氣特徵有2個值，則k=2，第一個值有17條可以關聯到決策後的節點，第二個值也是17條，則能得出計算：
再計算周末這個特徵，也只有兩個特徵值，一個是，一個否，其中是有14條，否有20條；周末為是的中有11條銷量是高，3條銷量低，以此類推有：
信息增益為：
另外可以得到是否有促銷的信息增益為0.127268。
可以看出，以周末為決策，可以得到最大的信息增益，因此根節點就可以用周末這個特徵進行分支：
注意再接下來一層的原樣本集，不是34個而是周末為「是」和「否」分別計算，為是的是14個，否的是20個。
這樣一層一層往下遞歸，直到判斷節點中的樣本是否都屬於一類，或者都有同一個特徵值，此時就不繼續往下分了，也就生成了葉子節點。
上述模型的決策樹分配如下：
需要注意的是，特徵是否出現需要在分支當中看，並不是整體互斥的，周末生成的兩個分支，一個需要用促銷來決策，一個需要用天氣，並不代表再接下來就沒有特徵可以分了，而是在促銷決策層下面可以再分天氣，另外一遍天氣決策下面可以再分促銷。
決策樹的模型比較容易解釋，看這個樹形圖就能很容易的說出分類的條件。
我們知道屬性有二元屬性、標稱屬性、序數屬性和連續屬性，其中二元、標稱和序數都是類似的，因為是離散的屬性，按照上述方式進行信息增益計算即可，而連續屬性與這三個不同。
對於連續的屬性，為了降低其時間復雜度，我們可以先將屬性內部排序，之後取相鄰節點的均值作為決策值，依次取每兩個相鄰的屬性值的均值，之後比較他們的不純度度量。
需要注意的是，連續屬性可能在決策樹中出現多次，而不是像離散的屬性一樣在一個分支中出現一次就不會再出現了。
用信息熵或者Gini系數等不純度度量有一個缺點，就是會傾向於將多分支的屬性優先分類——而往往這種屬性並不是特徵。
例如上面例子中的第一行序號，有34個不同的值，那麼信息熵一定很高，但是實際上它並沒有任何意義，因此我們需要規避這種情況，如何規避呢，有兩種方式：
公式如下：
其中k為劃分的總數，如果每個屬性值具有相同的記錄數，則 ，劃分信息等於 ，那麼如果某個屬性產生了大量劃分，則劃分信息很大，信息增益率低，就能規避這種情況了。
為了防止過擬合現象，往往會對決策樹做優化，一般是通過剪枝的方式，剪枝又分為預剪枝和後剪枝。
在構建決策樹時，設定各種各樣的條件如葉子節點的樣本數不大於多少就停止分支，樹的最大深度等，讓決策樹的層級變少以防止過擬合。
也就是在生成決策樹之前，設定了決策樹的條件。
後剪枝就是在最大決策樹生成之後，進行剪枝，按照自底向上的方式進行修剪，修剪的規則是，評估葉子節點和其父節點的代價函數，如果父節點的代價函數比較小，則去掉這個葉子節點。
這里引入的代價函數公式是：
其中 代表的是葉子節點中樣本個數， 代表的是該葉子節點上的不純度度量，把每個葉子節點的 加起來，和父節點的 比較，之後進行剪枝即可。
㈦ 決策樹演算法之隨機森林
在 CART 分類回歸樹 的基礎之上，我們可以很容易的掌握隨機森林演算法，它們之間的區別在於，CART 決策樹較容易過擬合，而隨機森林可以在一定程度上解決該問題。
隨機森林的主要思想是：使用隨機性產生出一系列簡單的決策樹，並組合它們的預測結果為最終的結果，可謂三個臭皮匠賽過一個諸葛亮，下面我們就來具體了解一下。
產生隨機森林的步驟大致為三步
在第 1 步，它是一個可放回抽樣，即所產生的樣本是允許重復的，這種抽樣又被稱為 Bootstrap，例如我們有以下 mmy 數據
在做完 Bootstrap 之後，可能的樣本數據如下
可見，樣本數據中，第 3 條和第 4 條樣本是一樣的，都對應的是原始數據中的第 4 條。
接下來，就是要使用上面的樣本數據來產生決策樹了，產生決策樹的方法和 CART 基本一致，唯一的不同地方在於，節點的構建不是來自於全部的候選特徵，而是先從中隨機的選擇 n 個特徵，在這 n 個特徵中找出一個作為最佳節點。
舉個例子，假設 n = 2，且我們隨機選擇了「血液循環正常」和「血管堵塞」這兩個特徵來產生根節點，如下：
我們將在上述兩個特徵中選擇一個合適的特徵作為根節點，假設在計算完 Gini 不純度之後，「血液循環正常」這個特徵勝出，那麼我們的根節點便是「血液循環正常」，如下圖所示
接下來我們還需要構建根節點下面的節點，下一個節點將會在剩下的「胸口疼痛」、「血管堵塞」和「體重」三個特徵中產生，但我們依然不會計算所有這 3 個特徵的 Gini 不純度，而是從中隨機選擇 2 個特徵，取這 2 個特徵中的 Gini 不純度較低者作為節點。
例如我們隨機選到了「胸口疼痛」和「體重」這兩列，如下：
假設此時「體重」的 Gini 不純度更低，那麼第 2 個節點便是「體重」，如下圖：
繼續下去，我們便產生了一棵決策樹。
隨機森林是多棵決策樹，在產生完一棵決策樹後，接著會循環執行上述過程：Bootstrap 出訓練樣本，訓練決策樹，直到樹的數量達到設置值——通常為幾百棵樹。
現在我們產生了幾百棵樹的隨機森林，當我們要預測一條數據時，該怎麼做呢？我們會聚合這些樹的結果，選擇預測結果最多的那個分類作為最終的預測結果。
例如我們現在有一條數據：
該條數據被所有樹預測的結果如下：
上述結果聚合後為：
取最多的那項為最終的預測結果，即 Yes——該病人被診斷為患有心臟病。
以上，隨機森林的兩個過程： B ootstrap 和 Agg regate 又被稱為 Bagging 。
本文我們一起學習了隨機森林的演算法，和 CART 決策樹比起來，它主要被用來解決過擬合問題，其主要的思想為 Bagging，即隨機性有助於增強模型的泛化（Variance） 能力。
參考：
相關文章：
㈧ 決策樹(decisionTree)
決策樹(decisionTree)是一種基本的分類和回歸方法。此文僅討論用於分類方法的決策樹。
決策樹的學習通常分為3步：
決策樹的學習的思想主要源於
定義決策樹 ：
分類決策樹模型是一種描述對實例進行分類的樹形結構。決策樹由結點(node)和有向邊(directed edge)組成。結點又分為內部結點(internal node)和葉結點(leaf node)。內部結點表示一個特徵或屬性，葉結點表示一個類。
形如：
其中，圓表示內部結點，方框表示葉結點。
if-then規則，簡單來說就是 ：
舉例：對於一個蘋果，外表是紅色的是紅蘋果，外表是綠色的是青蘋果。可以表示為：
if-then規則集合具有一個重要的性質：
這就是說每一個實例都被一條路徑或規則覆蓋，並且只被一條路徑或規則覆蓋。這里所謂的覆蓋是指實例的特徵與路徑上的特徵一致，或實例滿足規則的條件。
給定數據集：
其中， 為輸入實例（特徵向量），含有 個特徵， 為類標記， , 為樣本容量。
目標 ：
根據給定的訓練數據集構建一個決策樹模型，使它能夠對實例進行正確分類。
特徵選擇在於選取對訓練數據具有分類能力的特徵，這樣可以提高決策樹學習的效率。
如果我們利用某一個特徵進行分類的結果與隨機分類的結果沒什麼很大的差別的話，則稱這個特徵沒有分類能力。
那麼問題來了，怎麼選擇特徵呢？
通常特徵選擇的准則是
下面通過例子來說明一下。
目標 ：
希望通過所給的訓練集數據，學習一個貸款申請的決策樹。當新的客戶提出貸款申請的時候，根據申請人的特徵利用決策樹決定是否批准貸款申請。
可見這里共有4個特徵可供選擇。用特徵選擇的准則是 。接下來介紹 。
：
熵是表示隨機變數不確定性的度量。
設 是一個取有限個值的隨機變數，其概率分布為
則隨機變數 的熵定義為
若 ，則定義 。通常對數取以2為底，或是以 為底，熵的單位分布為比特（bit）或是納特（nat）。
由上式可知，熵只依賴 的分布，而已 的值無關，則 的熵還可記作 ，即
則從定義可知
當隨機變數只取2個值的時候，例如 時， 的分布為
熵為
熵隨概率變化的曲線為
當 或 時 ，隨機變數完全沒有不確定性，當 時 ，熵取值最大，隨機變數不確定性最大。
設隨機變數 ，其聯合概率分布
條件熵 表示在已知隨機變數 的條件下隨機變數 的不確定性。隨機變數 給定條件下隨機變數 的條件熵(conditional entropy)，定義為 給定條件下 的條件概率分布的熵對 的數學期望
信息增益
特徵 對訓練集 的信息增益
根據信息增益准則的特徵選擇方法：對訓練集 ，計算其每個特徵的信息增益，並比較大小，選擇信息增益最大的特徵。
前期定義各個量：
信息增益的演算法
輸入：訓練集 和特徵 ；
輸出：特徵 對訓練集 的信息增益
回看剛才的例子，
解 ：
這一次我很無聊的想用一下.csv文件類型。
所以訓練數據集部分如下，我存在一個loan.csv文件里了。對.csv文件的各種處理一般由python的pandas模塊完成。
第一步，導入相關模塊
第二步，讀入數據
若是使用jupyter，可以即刻查看一下數據，和數據標簽。
可以看出，除了'ID'之外前4個標簽 'age', 'work', 'own house', 'Credit conditions'為我們一直在說的特徵 ，而最後一個標簽'label'是我們所說的類 ，所以要處理一下這些標簽，
第三步，計算訓練集 的熵 ：
這里會用到pandas的一個統計數據的功能， groupby(by = [列]).groups ，將數據統計成字典的形式，這么說比較抽象，看下圖，將我們用pandas讀入的data，分為2類， ， Index 表示索引，即第0，1，4，5，6，14（python計數從0開始）個數據的 ，第2，3，7，8，9，10，11，12，13個數據的 .
那麼計算訓練集 的熵
第四步，計算特徵 對數據集 的條件熵
第五步 ，計算信息增益
輸入：訓練集 和特徵 和閾值 ；
輸出：決策樹
(1) 中所有實例都屬於同一類 ，則 為單結點樹，並將類 作為該結點的類標記，返回 ；
(2) 若 ，則 為單結點樹，並將 中實例數最大的類 作為該結點的類標記，返回 ；
(3)否則，按照上述信息增益的演算法，計算 中各個特徵對 的信息增益，選擇信息增益最大的特徵 ；
(4)如果特徵 的信息增益小於閾值 ，將置 為單結點樹，並將 中實例數最大的類 作為該結點的類標記，返回 ；
(5)否則，對 的每一個可能值 ，依 將 分割為若干非空子集 ，將 中實例數最大的類 作為該結點的類標記，構建子結點，由結點及其子結點構成樹 ，返回 ；
(6)對第 個子結點，以 為訓練集，以 為特徵集，遞歸的調用步驟(1)~步驟(5)，得到子樹 ，返回 。
對上述表的訓練集數據，利用ID3演算法建立決策樹。
解 ：
第一次迭代 ：
【特徵：有自己的房子】將數據集 劃分為2個子集 （有自己的房子）和 （沒有自己的房子），觀察一下 和 ：
：
由於 所有實例都屬於同一類 ，所以它是一個葉結點，結點的類標記為「是」。
：
對於 則需從特徵 中選擇新的特徵。
第二次迭代 ：
將 看作新的數據集 。【特徵：有工作】有2個可能值，劃分為2個子集 （有工作）和 （沒有工作），觀察一下 和 ：
：
由於 所有實例都屬於同一類 ，所以它是一個葉結點，結點的類標記為「是」。
：