決策樹(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個子集 （有工作）和 （沒有工作），觀察壹下 和 ：
：
由於 所有實例都屬於同壹類 ，所以它是壹個葉結點，結點的類標記為“是”。
：