決策樹是一個預測模型种冬，也是一個分類器付燥，代表對象屬性和對象值的一種映射關系。決策樹適用于小數據的分類枝哄。
決策樹例子圖：公司招聘
決策樹通過不斷選取特征屬性作為根節(jié)點肄梨，通過判斷輸出結果分類，再根據下一個特征屬性再分類挠锥，直到某一個子節(jié)點中只有一種結果或者不再有特征屬性用來分類众羡，如果用于分類的特征屬性用完，還有某一子節(jié)點未得到單一結果蓖租，則根據少數服從多數原則來判別屬于哪一類結果粱侣。那么如何來選取特征屬性先作為根節(jié)點來進行分類，這就需要了解關于信息熵的概念蓖宦。
信息熵：用來度量信息的一個概念齐婴，可理解為離散隨機事件發(fā)生的概率。
信息熵（Entropy）的計算：
如何構建決策樹稠茂，這里討論兩種算法：ID3和C4.5
ID3算法：
ID3算法通過信息增益（Information Gain）來選取特征屬性進行分類柠偶，通過選取信息增益最大的特征屬性先作為根節(jié)點來分類。如何計算信息增益：
信息增益計算方法：
為了防止建立的決策樹出現過度擬合（Overfitting）現象睬关，需要對決策樹進行剪枝操作诱担，有先剪枝和后剪枝。
ID3算法存在一些缺陷：
(1) 信息增益的計算依賴于特征數目較多的特征电爹，而屬性取值最多的屬性并不一定最優(yōu)蔫仙。
(2) ID3是非遞增算法。
(3) ID3是單變量決策樹(在分枝節(jié)點上只考慮單個屬性)丐箩，許多復雜概念的表達困難摇邦，屬性相互關系強調不夠恤煞，容易導致決策樹中子樹的重復或有些屬性在決策樹的某一路徑上被檢驗多次。
(4) 抗噪性差涎嚼，訓練例子中正例和反例的比例較難控制阱州。
C4.5算法
基于上述ID3的缺陷，C4.5進行了一些優(yōu)化法梯。
C4.5算法通過計算信息增益率（Information Gain Ratio）來選取特征屬性進行分類，增益比率度量是用前面的增益度量Gain(S犀概，A)和分裂信息度量SplitInformation(S立哑，A)來共同定義的計算方法如下：
C4.5算法繼承了ID3算法的優(yōu)點，并在以下幾方面對ID3算法進行了改進：
(1) 用信息增益率來選擇屬性姻灶，克服了用信息增益選擇屬性時偏向選擇取值多的屬性的不足铛绰；
(2) 在樹構造過程中進行剪枝；
(3) 能夠完成對連續(xù)屬性的離散化處理产喉；
(4) 能夠對不完整數據進行處理捂掰。
C4.5算法優(yōu)點：產生的分類規(guī)則易于理解，準確率較高曾沈。
C4.5算法缺點：在構造樹的過程中这嚣，需要對數據集進行多次的順序掃描和排序，因而導致算法的低效塞俱。此外姐帚，C4.5只適合于能夠駐留于內存的數據集，當訓練集大得無法在內存容納時程序無法運行障涯。
為了便于新手理解罐旗，接下來對上面的公式進行例子計算：
假設以下是招聘的一些實例：
先使用ID3算法中的信息增益來計算，首先不加任何特征屬性的唯蝶，計算錄用的信息熵九秀，由圖5可知，一共有6個實例粘我，錄用為“是”的占5個鼓蜒，錄用為“否”的占一個，所以“是”概率為5/6涂滴，“否”的概率為1/6友酱，根據圖2中信息熵的計算公式可得錄用的信息熵為：
現在分別來計算加入特征屬性后“錄用”信息熵的值，計算加入“實習經歷”后柔纵，根據是否有實習經歷來計算的“錄用”的信息熵值缔杉，由圖5可知在6個實例中“實習經歷”中為“有”的占3個，為“無”的占3個搁料，所以在“實習經歷”中“有”和“無”所占的概率都為1/2或详，在“實習經歷”中為“有”中的“錄用結果”都為“是”系羞，所以“是”的概率為1，“否”為0霸琴，同理椒振，在“實習經歷”中為“無”中的“錄用結果”為“是”的有2個，為“否”的有1個梧乘，所以“是”的概率為2/3澎迎，“否”的概率為1/3。所以“實習經歷”為“有”的“錄用”的信息熵為：
“實習經歷”為“無”的“錄用”的信息熵為：
所以圖3式子中：
所以加入“實習經歷”后“錄用”的信息增益計算為：
其他的特征屬性信息增益計算與上面相同选调，計算出每個特征屬性的信息增益后夹供，取最大的信息增益的對應的特征屬性作為分類根節(jié)點。
C4.5算法中采用信息增益率來選取根節(jié)點仁堪，計算公式如圖4哮洽，其中需要說明的是分裂信息度量SplitInformation(S，A)的計算弦聂，還是以“實習經歷”屬性來計算鸟辅，在圖5中“實習經歷”中分“有”和“無”兩種，且分別占1/2莺葫，所以計算SplitInformation(S匪凉，A)結果為：
以上為個人理解，如有錯誤徙融，歡迎大家批評指正洒缀。
