決策樹算法是應用最廣泛的分類方法之一^[51] 。其核心算法是ID3算法和后來的改進算法C4.5算法。與ID3相比，C4.5主要改進如下：

① 用信息增益率來選擇屬性，克服了用信息增益來選擇屬性時偏向選擇值多的屬性的不足。信息增益率定義為：

其中Gain(S,A)與ID3算法中的信息增益相同，而分裂信息SplitInfo(S,A)代表了按照屬性A分裂樣本集S的廣度和均勻性。

其中，S₁到Sc是c個不同值的屬性A分割S而形成的c個樣本子集。

② 可以處理連續數值型屬性。例如，假設A為一個連續的數值型屬性，首先檢查樣本集中該屬性的所有取值，然后將其按升序排列為A1，A2，…，Am。對于每一個Aj，j=1，2，…，m-1，將樣本集劃分為兩個樣本子集，一子集是各記錄屬性A的值均小于等于Aj，另一子集是其各記錄屬性A的值均大于Aj。對于每個劃分，計算相應的信息增益率，然后選擇增益率最大的劃分，作為屬性A的信息增益率。

③ 為了避免樹的高度無節制的增長，避免過度擬合數據，采用了一種后剪枝方法，該方法是從一種稱為”規則后修剪”（rule post-pruning）的方法演變而來。該方法使用訓練樣本集本身來估計剪枝前后的誤差，從而決定是否真正剪枝。方法中使用的公式如下：

其中N是實例的數量，f=E/N為觀察到的誤差率（其中E為N個實例中分類錯誤的個數），q為真實的誤差率，c為置信度（C4.5算法的一個輸入參數，默認值為0.25），z為對應于置信度c的標準差，其值可根據c的設定值通過查正態分布表得到。通過該公式即可計算出真實誤差率q的一個置信度上限，用此上限為該節點誤差率e做一個悲觀的估計：

通過判斷剪枝前后e的大小，從而決定是否需要剪枝。

④ 對于缺失值的處理。在某些情況下，可供使用的數據可能缺少某些屬性的值。假如〈x，c(x)〉是樣本集S中的一個訓練實例，但是其屬性A的值A(x)未知。處理缺少屬性值的一種策略是賦給它結點n所對應的訓練實例中該屬性的最常見值；另外一種更復雜的策略是為A的每個可能值賦予一個概率。例如，給定一個布爾屬性A，如果結點n包含6個已知A=1和4個A=0的實例，那么A(x)=1的概率是0.6，而A(x)=0的概率是0.4。于是，實例x的60%被分配到A=1的分支，40%被分配到另一個分支。這些片斷樣例（fractional examples）的目的是計算信息增益，另外，如果有第二個缺少值的屬性必須被測試，這些樣例可以在后繼的樹分支中被進一步細分。C4.5就是使用這種方法處理缺少的屬性值。