C4.5是壹系列用在機器學習和數據挖掘的分類問題中的算法。它的目標是監督學習：給定壹個數據集，其中的每壹個元組都能用壹組屬性值來描述，每壹個元組屬於壹個互斥的類別中的某壹類。C4.5的目標是通過學習，找到壹個從屬性值到類別的映射關系，並且這個映射能用於對新的類別未知的實體進行分類。
C4.5由J.Ross Quinlan在ID3的基礎上提出的。ID3算法用來構造決策樹。決策樹是壹種類似流程圖的樹結構，其中每個內部節點（非樹葉節點）表示在壹個屬性上的測試，每個分枝代表壹個測試輸出，而每個樹葉節點存放壹個類標號。壹旦建立好了決策樹，對於壹個未給定類標號的元組，跟蹤壹條有根節點到葉節點的路徑，該葉節點就存放著該元組的預測。決策樹的優勢在於不需要任何領域知識或參數設置，適合於探測性的知識發現。
決策樹呈樹形結構，在分類問題中，表示基於特征對實例進行分類的過程。學習時，利用訓練數據，根據損失函數最小化的原則建立決策樹模型；預測時，對新的數據，利用決策模型進行分類。
決策樹是壹種通過對特征屬性的分類對樣本進行分類的樹形結構，包括有向邊以及三類節點：
上圖給出了（二叉）決策樹的示例。決策樹具有以下特點：
決策樹學習的本質是從訓練集中歸納出壹組分類規則。但隨著分裂屬性次序的不同，所得到的決策樹也會不同。如何得到壹棵決策樹既對訓練數據有較好的擬合，又對未知數據有很好的預測呢？
首先，我們要解決兩個問題：
壹般的，壹顆決策樹包含壹個根節點、若幹個內部結點和若幹個葉結點；葉結點則對應於壹個屬性冊書；每個葉結點包含的樣本集合根據屬性測試的結果被劃分到子結點中；根結點包含樣本全集，從根結點到每個葉結點的路徑對飲過了壹個判定測試序列。決策樹學習的目的是為了產生壹顆泛化能力強的決策樹，其基本流程遵循簡單且只管的“分而治之”（divide-and-conquer）策略，如下圖所示：
顯然，決策樹的生成是壹個遞歸的過程。在決策樹基本算法中，有三種情形會導致遞歸返回：
在第二種情形下，我們把當前結點標記為葉結點，並且將其類別設定為該結點所含樣本最多的類別；在第三種情形下，同樣把當前結點標記為葉結點，但將其類別設定為其父結點所含樣本最多類別。註意這兩種情形的處理實質不同：情形二是在利用當前結點的後驗分布，而情形三則是把父結點的樣本分布當做當前結點的先驗分布。
決策樹學習的關鍵在於如何選擇最優劃分屬性。壹般而言，隨著劃分過程的不斷進行，我們希望決策樹的分支結點所包含的樣本盡可能屬於同壹類別，即結點的“純度”越來越高。
“信息熵”（information entropy）是度量樣本集合純度最常用的壹種指標。假定當前樣本集合 中第k類樣本所占比例為 ，則 的信息熵定義為
的值越小，則 的純度越高。
假定離散屬性 有 個可能的取值 ,若使用 來對樣本集合 進行劃分，則會產生 個分支結點，其中第v個分支結點包含了 中所有在屬性 上取值為 的樣本，記為 ，我們根據上述公式計算出 的信息熵，再考慮到不同的分支結點所包含的樣本數不同，給分支結點賦予權重 ，即樣本越多的分支結點影響越大，於是可以計算出用屬性 對樣本集合 進行劃分所獲得的"信息增益"（information gain）
壹般而言，信息增益越大，則意味著使用屬性a來進行劃分所獲得的“純度提升越大”。因此，我們可用信息增益來進行決策樹的劃分屬性選擇。
實際上，信息增益準則對可取值數目較多的屬性有所偏好（如何以序號作為劃分屬性，每壹個事物作為壹個單獨存在的類別的時候，信息增益往往會很高，但是這樣進行劃分並沒有什麽意義），為了減少這種偏好可能帶來的不利影響，著名的C4.5算法並不是直接使用信息增益，而是使用增益率（gain ratio）來選擇最優的劃分屬性。增益率的定義為：
值得註意的是： 增益率準則對可取值數目較少的屬性有所偏好，因此C4.5算法並不是直接選擇增益率最大的候選劃分屬性，而是使用了壹個啟發式： 先從候選劃分屬性中找出信息增益高於平均水平的屬性，再從中選擇增益率最高的
CART決策樹使用“基尼指數”來選擇劃分屬性。數據集 的純度可用基尼值來度量：
直觀來說， 反映了從數據集 中隨機抽取兩個樣本，其類別標記不壹致的概率，因此 值越小，則數據集 的純度就越高。屬性 的基尼指數定義為：
於是，我們在候選屬性集合 中，選擇那個使得劃分後基尼指數最小的屬性作為最優劃分屬性，即
銀行希望能夠通過壹個人的信息（包括職業、年齡、收入、學歷）去判斷他是否有貸款的意向，從而更有針對性地完成工作。下表是銀行現在能夠掌握的信息，我們的目標是通過對下面的數據進行分析建立壹個預測用戶貸款壹下的模型。
上表中有4個客戶的屬性，如何綜合利用這些屬性去判斷用戶的貸款意向？決策樹的做法是每次選擇壹個屬性進行判斷，如果不能得出結論，繼續選擇其他屬性進行判斷，直到能夠“肯定地”判斷出用戶的類型或者是上述屬性都已經使用完畢。比如說我們要判斷壹個客戶的貸款意向，我們可以先根據客戶的職業進行判斷，如果不能得出結論，再根據年齡作判斷，這樣以此類推，直到可以得出結論為止。決策樹用樹結構實現上述的判斷流程，如圖所示：
以熵作為節點復雜度的統計量，分別求出下面例子的信息增益，圖3.1表示節點選擇屬性1進行分裂的結果，圖3.2表示節點選擇屬性2進行分裂的結果，通過計算兩個屬性分裂後的信息增益，選擇最優的分裂屬性。
屬性壹
屬性二
由於 ，所以屬性1是比屬性2更優的分裂屬性，故而選擇屬性1作為分裂屬性。
由於 ，故而選擇屬性2作為分裂屬性。
剪枝（pruning）是決策樹學習算法對付“過擬合”的主要手段。在決策樹學習中，為了盡可能正確分類訓練樣本，結點劃分過程將不斷重復，有事會造成決策樹分支過多，這是就可能因為訓練樣本學得太好了，以致把訓練集自身的壹些特點黨組喲所有數據都具有的壹般性質而導致過擬合。因此，可通過主動去掉壹些分支來降低過擬合的風險。
其中{1,2,3,6,7,10,14,15,16,17}為測試集，{4,5,8,9,11,12,13}為訓練集。
預剪枝是要對劃分前後泛化性能進行評估。對比決策樹某節點生成前與生成後的泛化性能。
2.計算訓練集的信息增益，得知臍部的信息增益最大，因此按照臍部進行劃分。又因為在訓練集中，凹陷特征好瓜的占比多，因此凹陷劃分為好瓜，稍凹特征好過占比多，因此將其標記為好瓜，因此按照臍部劃分的子樹結果如下：
劃分後，對比結果如下：
由圖可知，預剪枝使得很多分支沒有展開，這不僅降低了過擬合的風險，還顯著減少了決策樹的訓練時間開銷和測試時間。但是，有些分支雖當前不能提升泛化性。甚至可能導致泛化性暫時降低，但在其基礎上進行後續劃分卻有可能導致顯著提高，因此預剪枝的這種貪心本質，給決策樹帶來了欠擬合的風險。
後剪枝表示先從訓練集中生成壹顆完整決策樹。
對比標記節點的劃分類與各數據的真實分類，計算準確率，如下表所示：
生成的決策樹，在驗證集上的準確度為3/7*100%=42.9%.
對比預剪枝與後剪枝生成的決策樹，可以看出，後剪枝通常比預剪枝保留更多的分支，其欠擬合風險很小，因此後剪枝的泛化性能往往由於預剪枝決策樹。但後剪枝過程是從底往上裁剪，因此其訓練時間開銷比前剪枝要大。