啥是決策樹：

決策樹是一種分類器，通過訓練數據構建決策樹可以對未知的類別的擁有相同屬性的數據進行分類。

決策樹的優點：

適用情況：

例子：新建酒吧的評估問題 （手動模擬決策樹建樹過程） 這個例子是關于某個啤酒廠的，它需要對在某些位置是否適合建新酒吧進行評估，也就是說，對于某個指定位置，是應該建新酒吧，還是應該將其劃為不適合? 為了對新位置進行評估，需要對有關該位置坐落區域的諸多屬性進行調查，這些屬性描述包括：該位置是一個城市呢還是一個較大的城鎮，該區域內是否有大學，居住區屬于什么類型。如果需要，還包括附近是否有工業區(公園)，以及該區域內公共交通的質量和學校的數量。每個屬性都有多個取值，例如，城市屬性取值為{Y－是，N－否}，居住區類型屬性取值為{M－中等，S－小型，N－無，L－大型}, 交通條件取值為{A－一般，P－差，G－好}。 這個啤酒廠擁有一個數據庫，其中包括現有酒吧及其相應屬性值。下表列出了該數據庫的一個子集。每個現有酒吧／飯館都有一個類別, 其中，+(正)表示該位置被認為是成功的，－(負)表示該位置尚可，但他們已不希望將來再進行類似的投資了。該啤酒廠希望利用這個數據庫找到一組規則，以便能夠幫助他們決定某個新位置的潛在可用性。

(1)IF交通條件=差 AND有無工業區=無THEN不購買該位置(因為例子{2，4，10，13，18都是負的) 。 (2)IF交通條件=好 THEN購買該位置(因為例子{7，12，16，19，20}都是正的) 。 沿著從根結點到葉結點的每條路徑就會得到相應的規則。路徑上的每個結點都表示了一個屬性，而該屬性對應于路徑上的那個分支就給出了相應的屬性值。

得到的決策樹如下

ID3算法：

基本的ID3算法通過自頂向下構造決策樹來進行學習。那么構造一顆決策樹要先選擇根節點，怎么選呢？ 這里要用到信息增益的熵計算公式，比較啰嗦，后面記錄。 假如現在通過熵增益計算公式得到了一個根節點，然后為根結點屬性的每個可能值產生一個分支，并把訓練例排列到適當的分支(也就是，訓練例的該屬性值對應的分支)之下。然后重復整個過程，用每個分支結點關聯的訓練例來選取在該點被測試的最佳屬性。

例如，在上面的圖中，例子{1，3，6，8，11，15，17}的交通條件屬性都取值為A(一般)。 交通條件屬性有三個取值{一般－A，差－P，好－G}，所以在根結點下就有三個分支，相應地也創建了三個新結點。然后，按照該屬性的相應取值將這些例子分別賦給這三個新結點，如例子{2，4，5，9，10，13，14，18}的交通條件屬性都取值為P。

構造出決策樹后，可以直觀的看出。交通條件好的地方適合當酒吧（交通條件為G）

上面的說的熵增益和根節點的選擇方法如下：

熵(entropy)，用來描述一個系統的混亂程度

1.只有兩種信息的熵

假設一個系統S含有兩種信息, 其中p1表示第一種信息在S中的比例, p2表示第二種信息在S中的比例, 那么系統S相對于這兩種信息分類的熵為:

Entropy(S)=?p1log2p1?p2log2p2$Entropy(S)=-p_1/log_2p1-p_2/log_2p2$ (1) 在有關熵的所有計算中我們定義0log0為0。

假設S是一個有14個訓練例的集合，它包括9個正例和5個反例 ,我們采用記號[ 9+，5-]來概括這樣的訓練例集。那么S相對于這個正反例兩種信息分類的熵為：

Entropy ([9+，5-] )= - (9／14)log2(9／14) - (5／14)log2(5／14) =0．940 (2)

如果S的所有成員屬于同一類，那么S的熵為0。例如，如果所有的成員都是第一種, p1 =1，那么p2 就是0，Entropy (S)= -1?log2(1) - 0?log2 (0)= -1?0-0?log2(0)=0。當集合中兩種信息的數量相等時，熵為l。當集合中兩種信息的數量不等時，熵介于0和1之間。

2.具有多種信息的系統的熵

如果目標屬性具有n個不同的信息，那么S相對于n種信息的分類的熵定義為：

Entropy(S)=∑ni=1(?pilog2pi)$Entropy(S)=/sum_{i=1}^n(-p_i/log_2p_i)$（3）

其中，pi是S中屬于類別i的比例

3.系統分類后的熵

設原系統S的熵為Entropy(S),又系統S具有屬性A,我們用Values(A)表示屬性A所有可能值的集合，Sv是S中屬性A的值為v的集合

∑v∈Values(A)|Sv||S|Entropy(Sv)$/sum_{v∈Values(A)}/frac{|S_v|}{|S|}Entropy(S_v)$

計算熵的例子：

根據天氣判斷“是否適合打網球”。

設S是上表中訓練例的集合,包括14個訓練例,其中9個為正例,5個為反例,表示為[9+，5-], 相對于正反例, S的熵Entropy(S) =0．940(見(2)) 。現考慮S的屬性Wind,它有兩個值Weak和Strong, 14個訓練例中具有Weak 值的有6個正例, 2個反例, ,表示為[6+，2-];同時, 14個訓練例中具有Strong 值的有3個正例, 3個反例, ,表示為[3+，3-],按照屬性Wind分類14個訓練例得到的分類后的熵計算如下。 由此可見, 使用屬性Wind屬性分類后, S的熵大大降低。我們再考慮S的屬性Humidity,按其分類14個訓練例得到的分類后的熵計算如下。

信息增益最佳分類屬性：

一個屬性A相對訓練例集合S的信息增益Gain(S，A)被定義為：

等式(4)的第一項就是原集合S的熵，第二項是用A分類S后熵的期望值。這個第二項描述的期望熵就是每個子集的熵的加權和，權值為屬于Sv 的樣例占原始樣例S的比例，所以Gain(S，A)是由于知道屬性A的值而導致的期望熵減少

相對于目標分類(即是否適合打網球)，Humidity比Wind有更大的信息增益。這里，E代表熵，S代表原始樣例集合。已知初始集合S有9個正例和5個反例，即[9+，5－]。用Humidity分類這些樣例產生了子集[ 3+，4－ ] (Humidity=High)和[6+，1－] (Humidity=Normal)。這種分類的信息增益為0.151，而對于屬性Wind增益僅為0.048

使用ID3算法完整實現”是否適合打網球”

第一步，創建決策樹的最頂端結點

ID3算法計算每一個候選屬性(也就是Outlook、Temperature、Humidity和Wind)的信息增益，然后選擇信息增益最高的一個。

所有四個屬性的信息增益為： Gain(S，Outlook)=0．246 Gain(S，Humidity)=0．151 Gain(S，Wind)=0．048 Gain(S，Temperature)=0．029

第二步，創建分枝

Outlook被選作根結點的決策屬性，并為它的每一個可能值(也就是Sunny,Overcast和Rain)在根結點下創建分支。

注意到每一個Outlook =Overcast的樣例都是PlayTennis的正例，所以，樹的這個結點成為一個葉子結點，它對目標屬性的分類是PlayTennis=Yes。相反，對應Outlook =Sunny和Outlook=Rain的后繼結點還有非0的熵，所以決策樹會在這些結點下進一步展開。 如圖

Ssunny={D1,D2,D8,D9,D11} Gain(Ssunny,Humidity)=0.970－(3／5)0.0－(2／5)0.0=0.970 Gain(Ssunny,Temperature=0.970－(2／5)0.0－(2／5)1.0－(1／5)0.0=0.570 Gain(Ssunny,Wind)=0.970－(2／5)1.0－(3／5)0.918=0.019

對于非終端的后繼結點，再重復前面的過程選擇一個新的屬性來分割訓練樣例，這一次僅使用與這個結點關聯的訓練樣例。已經被樹的較高結點測試的屬性被排除在外，以便任何給定的屬性在樹的任意路徑上最多僅出現一次。對于每一個新的葉子結點繼續這個過程，直到滿足以下兩個條件中的任一個：(1)所有的屬性已經被這條路徑包括；(2)與這個結點關聯的所有訓練樣例都具有相同的目標屬性值(也就是它們的熵為0)。

最后的決策樹如下圖

決策樹算法的問題：

上面的例子描述的算法增長樹的每一個分支的深度，直到恰好能對訓練樣例完美地分類，但是當數據中有噪聲或訓練樣例的數量太少以至于不能產生目標函數的有代表性的采樣時，這個策略便會遇到困難。在以上任一種情況發生時，這個簡單的算法產生的樹會過度擬合訓練樣例。

過度擬合的通俗意思就是該算法非常完美的滿足了訓練例，最后使得該算法只對訓練例中的數據有非常精確的結果，由于訓練例的局限性，對未知數據預測造成了很大的偏差。

例如，在上面打網球的例子當中增加一條訓練正例，但卻被誤標示為反例 < Outlook=Sunny，Temperature=Hot，Humidity=Normal，Wind=Strong，PlayTennis=No>

增加這個不正確的樣例導致ID3建立一個更復雜的樹，當然，新的決策樹會完美地擬合訓練樣例集，然而，由于新的決策結點只是擬合訓練樣例中噪聲的結果。

有幾種途徑可被用來避免決策樹學習中的過度擬合

通常后剪枝比預剪枝更加常用 后剪枝的方法有

python代碼： （來自機器學習實戰那本書）