一、經典決策樹算法原理
（一）ID3 算法
核心思想：以 “信息增益” 作為劃分屬性的選擇標準，通過最大化信息增益來提升數據集的 “純度”。
關鍵概念 —— 信息增益：指某個屬性帶來的 “熵減”（即純度提升量）。具體來說，當用屬性 a 對數據集 D 進行劃分后，數據集的整體熵值會降低，降低的數值就是屬性 a 的信息增益。信息增益越大，說明使用該屬性劃分后，數據集的類別分布越集中（純度越高），因此更適合作為當前節點的劃分屬性。
局限性：信息增益準則對 “可取值數目較多的屬性” 存在天然偏好。例如，若數據集中存在 “編號” 這類屬性（每個樣本的編號唯一），用編號劃分時每個子集都只包含單個樣本，信息增益會非常大，但這種劃分對分類任務毫無意義，因為它完全過擬合了訓練數據，無法推廣到新樣本。
（二）C4.5 算法
改進目標：解決 ID3 算法對取值多的屬性偏好問題，通過引入 “信息增益率” 實現更合理的屬性選擇。
核心指標 —— 信息增益率：計算公式為 “信息增益 ÷ 屬性自身的熵”。其中，屬性自身的熵反映了該屬性取值的分散程度：取值越多且分布越均勻，自身熵越大。通過除以自身熵，信息增益率可以平衡屬性取值數量對結果的影響，避免優先選擇取值過多的屬性。例如，對于 “編號” 這類屬性，雖然信息增益大，但自身熵也極大，因此信息增益率會降低，從而避免被誤選為最優劃分屬性。
（三）CART 算法
核心指標 —— 基尼指數：用于衡量數據集的純度，其物理意義是 “從數據集 D 中隨機抽取兩個樣本，它們的類別標記不一致的概率”。

?
是數據集 D 中第 k 類樣本的占比。當某個類別在數據集中占比極高（
P?k
接近 1）時，基尼指數會很小，說明數據集純度很高；反之，若各類別占比接近，基尼指數會增大，純度降低。
特點：CART 樹是 “二叉樹”，每次劃分都將數據集分為兩個子集，因此無論是離散屬性還是連續屬性，都采用二分法處理，這與 ID3、C4.5 的多叉劃分不同。
二、連續值屬性的處理方法
在實際數據中，很多屬性是連續值（如收入、年齡等），無法直接像離散屬性那樣按取值劃分，需要通過 “離散化” 轉化為離散屬性，具體步驟如下：

排序：將連續屬性的所有取值按從小到大的順序排列。例如，某數據集中 “應稅收入（Taxable Income）” 的取值為 60K、70K、75K、85K、90K、95K、100K、120K、125K、220K，排序后保持原順序。
確定候選分界點：采用 “二分法” 時，候選分界點為相鄰兩個取值的中間值。對于有 n 個不同取值的連續屬性，候選分界點有 n-1 個。例如上述收入數據有 10 個取值，因此有 9 個候選分界點（如 65K、72.5K 等）。
選擇最優分界點：使用 “貪婪算法”，分別計算每個候選分界點對應的信息增益（或基尼指數），選擇能使劃分后純度提升最大的分界點作為最終分割點。例如，可將收入分割為 “TaxIn≤80K” 和 “TaxIn>80K”，或 “TaxIn≤97.5K” 和 “TaxIn>97.5K”，具體取決于哪種劃分的指標更優。
三、決策樹剪枝策略（解決過擬合問題）
（一）剪枝的必要性
決策樹具有很強的擬合能力，理論上可以通過不斷劃分，將訓練集中的每個樣本都分到單獨的葉子節點，實現 “零錯誤率”。但這種過度復雜的樹會 “記住” 訓練數據中的噪聲和細節，導致在新數據（測試集）上表現很差，即發生 “過擬合”。剪枝的目的就是通過簡化樹的結構，降低過擬合風險，提高模型的泛化能力。
（二）預剪枝
操作時機：在決策樹構建過程中同步進行剪枝，即邊建邊剪。
核心邏輯：通過設置 “停止條件”，提前終止某些分支的生長。例如：
限制樹的最大深度：當樹的深度達到預設閾值時，不再繼續劃分。
限制葉子節點的最小樣本數：若當前節點的樣本數小于閾值，即使信息增益仍為正，也停止劃分，將當前節點設為葉子節點。
限制信息增益閾值：若某屬性的信息增益小于預設閾值，不采用該屬性劃分，直接將當前節點設為葉子節點。
優點：計算效率高，能避免構建不必要的復雜分支；實用性強，在實際工程中應用廣泛。
（三）后剪枝
操作時機：先完整構建決策樹，再從葉子節點向上逐層剪枝。
核心邏輯：通過 “損失函數” 衡量剪枝前后的模型性能，保留性能更優的結構。損失函數公式為：最終損失 = 葉子節點的基尼系數（或熵）之和 + α× 葉子節點數量。其中：
第一項 “葉子節點的基尼系數之和” 反映模型對訓練數據的擬合程度，值越小擬合越好。
第二項 “α× 葉子節點數量” 是正則化項，α 為超參數，控制對樹復雜度的懲罰力度。α 越大，懲罰越強，越傾向于選擇簡單的樹（葉子節點少）；α 越小，懲罰越弱，更注重擬合效果。
剪枝決策：對每個非葉子節點，計算 “剪枝后將其變為葉子節點” 的損失，與 “保留原分支” 的損失對比，若剪枝后損失更小，則進行剪枝。
實例效果：在 “好瓜 / 壞瓜” 分類案例中，原分支 “色澤 =?” 剪枝前驗證集精度為 57.1%，剪枝后提升至 71.4%；分支 “紋理 =?” 剪枝前精度 42.9%，剪枝后提升至 57.1%，均通過后剪枝顯著提升了泛化能力。
四、決策樹代碼實現關鍵參數（以 sklearn 為例）
在 Python 的 scikit-learn 庫中，使用DecisionTreeClassifier()類創建決策樹分類模型，以下是核心參數的詳細說明：

criterion：指定劃分屬性的評價指標，可選值為 “gini”（基尼指數）或 “entropy”（信息熵）。默認值為 “gini”，計算效率略高于熵，實際應用中兩者效果差異不大。
splitter：指定劃分點的選擇策略，可選值為 “best” 或 “random”。“best” 表示在所有特征中尋找最優劃分點，適合數據量較小的場景；“random” 表示在部分特征中隨機選擇劃分點，能減少過擬合風險，適合高維數據或需要加快訓練速度的場景。
整數 N：固定使用 N 個特征。該參數用于降低模型復雜度，避免過擬合。
max_depth：指定樹的最大深度，默認值為 None（不限制深度）。深度越大，樹越復雜，越容易過擬合。實際應用中推薦設置為 5-20 之間，需根據數據規模和復雜度調整。