决策树算法精讲：从CART理论到Python实战

1次阅读

共计 2763 个字符，预计需要花费 7 分钟才能阅读完成。

决策树是一种直观且强大的机器学习算法，广泛应用于分类和回归任务。它的优势在于模型可解释性强，能够处理数值型和类别型数据，并且不需要复杂的特征缩放。本文将从 CART 决策树的核心理论出发，带你逐步实现一个完整的决策树模型，并分享实际应用中的调优技巧。

基尼系数（Gini Index）是 CART 算法用于分类问题的划分标准，衡量数据集的不纯度。计算公式为：

$$ Gini(D) = 1 – \sum_{k=1}^{K} (p_k)^2 $$

其中 $p_k$ 是第 $k$ 类样本在数据集 $D$ 中的比例。基尼系数越小，数据集的纯度越高。

信息增益（Information Gain）基于信息熵的概念，计算公式为：

$$ Gain(D, a) = Ent(D) – \sum_{v=1}^{V} \frac{|D^v|}{|D|} Ent(D^v) $$

其中 $Ent(D)$ 是数据集 $D$ 的信息熵：

$$ Ent(D) = -\sum_{k=1}^{K} p_k \log_2 p_k $$

基尼系数计算更快，因为没有对数运算
信息增益对类别分布更敏感
实际应用中两者效果通常相近

决策树的构建是一个递归过程，伪代码如下：

如果当前节点所有样本属于同一类别，则标记为叶节点
如果特征集为空或样本数量小于阈值，则标记为叶节点（多数类）
否则，选择最优划分特征和划分点
根据划分点将数据集分为左右子集
对左右子集递归调用上述过程

import numpy as np
from collections import Counter

class DecisionTree:
    def __init__(self, max_depth=None, min_samples_split=2):
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split

    def _gini(self, y):
        counter = Counter(y)
        return 1 - sum((count / len(y)) ** 2 for count in counter.values())

    def _best_split(self, X, y):
        best_gini = float('inf')
        best_feature, best_value = None, None

        for feature in range(X.shape[1]):
            values = np.unique(X[:, feature])
            for value in values:
                left_indices = X[:, feature] <= value
                gini = (len(y[left_indices]) * self._gini(y[left_indices]) + 
                        len(y[~left_indices]) * self._gini(y[~left_indices])) / len(y)
                if gini < best_gini:
                    best_gini = gini
                    best_feature = feature
                    best_value = value
        return best_feature, best_value

    def fit(self, X, y, depth=0):
        # 终止条件
        if len(np.unique(y)) == 1 or len(y) < self.min_samples_split or \
           (self.max_depth is not None and depth >= self.max_depth):
            self.label = Counter(y).most_common(1)[0][0]
            self.is_leaf = True
            return

        # 寻找最佳划分
        self.feature, self.value = self._best_split(X, y)
        left_indices = X[:, self.feature] <= self.value

        # 递归构建子树
        self.left = DecisionTree(self.max_depth, self.min_samples_split)
        self.left.fit(X[left_indices], y[left_indices], depth+1)

        self.right = DecisionTree(self.max_depth, self.min_samples_split)
        self.right.fit(X[~left_indices], y[~left_indices], depth+1)

        self.is_leaf = False

    def predict(self, X):
        if self.is_leaf:
            return np.array([self.label] * len(X))

        left_indices = X[:, self.feature] <= self.value
        y_pred = np.empty(len(X), dtype=object)

        y_pred[left_indices] = self.left.predict(X[left_indices])
        y_pred[~left_indices] = self.right.predict(X[~left_indices])

        return y_pred

设置最大树深度（max_depth）
设置叶节点最小样本数（min_samples_leaf）
设置分裂最小样本数（min_samples_split）

先让决策树完全生长
自底向上考察非叶节点
计算剪枝前后的验证集精度
如果精度不降则剪枝

避免选择高基数类别特征
注意处理缺失值
连续特征需要离散化处理

决策树不需要标准化
但对类别特征需要编码
注意处理样本不平衡

from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import GridSearchCV

# 参数网格
param_grid = {'max_depth': [3, 5, 7],
    'min_samples_split': [2, 5, 10],
    'criterion': ['gini', 'entropy']
}

# 网格搜索
tree = DecisionTreeClassifier()
grid_search = GridSearchCV(tree, param_grid, cv=5)
grid_search.fit(X_train, y_train)

# 最佳模型
best_tree = grid_search.best_estimator_

CART 决策树是一个强大而直观的机器学习算法，特别适合作为入门学习的第一个算法。通过本文的理论讲解和代码实现，你应该已经掌握了决策树的核心原理和实现方法。在实际应用中，记得使用交叉验证和剪枝技术来防止过拟合，同时注意特征工程的重要性。

正文完