决策树实战：从数据到模型——详解cart决策树生成过程与实现

1次阅读

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

决策树是一种常用的机器学习算法，它通过树状结构对数据进行分类或回归。CART（Classification and Regression Trees）算法是决策树的一种实现方式，既可以用于分类问题，也可以用于回归问题。

CART 算法使用基尼系数（Gini Index）作为特征选择的准则。基尼系数表示从数据集中随机抽取两个样本，其类别不一致的概率。基尼系数越小，数据集的纯度越高。

基尼系数的计算公式为：

Gini(D) = 1 - Σ (p_i)^2

其中，p_i是第 i 类样本在数据集 D 中的比例。

对于特征 A，将数据集D 划分为 D1 和D2后的基尼系数为：

Gini_A(D) = |D1|/|D| * Gini(D1) + |D2|/|D| * Gini(D2)

CART 算法会选择使得 Gini_A(D) 最小的特征 A 作为当前节点的分裂特征。

假设我们有以下数据集：

年龄	收入	学生	信用	购买电脑
青年	高	否	一般	否
青年	高	否	好	否
中年	高	否	一般	是
老年	中	否	一般	是
老年	低	是	一般	是
老年	低	是	好	否
中年	低	是	好	是

计算整个数据集的基尼系数：
购买电脑为“是”的比例：4/7
购买电脑为“否”的比例：3/7
Gini(D) = 1 – (4/7)^2 – (3/7)^2 ≈ 0.4898
计算各个特征的基尼系数：
对于“年龄”：
- 青年：Gini = 1 – (0/2)^2 – (2/2)^2 = 0
- 中年和老年：Gini = 1 – (2/3)^2 – (1/3)^2 ≈ 0.4444
- Gini_age(D) = (2/7)0 + (5/7)0.4444 ≈ 0.3175
对于“收入”：
- 高：Gini = 1 – (1/3)^2 – (2/3)^2 ≈ 0.4444
- 中和低：Gini = 1 – (3/4)^2 – (1/4)^2 = 0.375
- Gini_income(D) = (3/7)0.4444 + (4/7)0.375 ≈ 0.4048
其他特征类似计算
选择基尼系数最小的特征作为根节点，这里是“年龄”。
对每个子节点重复上述过程，直到满足停止条件（如节点纯度达到阈值、达到最大深度等）。

import numpy as np
import pandas as pd

class Node:
    def __init__(self, feature=None, threshold=None, left=None, right=None, value=None):
        self.feature = feature  # 分裂特征
        self.threshold = threshold  # 分裂阈值
        self.left = left  # 左子树
        self.right = right  # 右子树
        self.value = value  # 叶节点的预测值

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

    def fit(self, X, y):
        self.root = self._grow_tree(X, y)

    def _grow_tree(self, X, y, depth=0):
        n_samples, n_features = X.shape
        n_classes = len(np.unique(y))

        # 停止条件
        if (self.max_depth is not None and depth >= self.max_depth) or n_classes == 1:
            return Node(value=self._most_common_label(y))

        # 寻找最佳分裂
        best_feature, best_threshold = self._best_split(X, y)
        if best_feature is None:
            return Node(value=self._most_common_label(y))

        # 分裂
        left_idxs = X[:, best_feature] <= best_threshold
        right_idxs = X[:, best_feature] > best_threshold
        left = self._grow_tree(X[left_idxs], y[left_idxs], depth+1)
        right = self._grow_tree(X[right_idxs], y[right_idxs], depth+1)

        return Node(best_feature, best_threshold, left, right)

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

        for feature in range(X.shape[1]):
            thresholds = np.unique(X[:, feature])
            for threshold in thresholds:
                left_idxs = X[:, feature] <= threshold
                gini = self._gini_impurity(y[left_idxs], y[~left_idxs])
                if gini < best_gini:
                    best_gini = gini
                    best_feature = feature
                    best_threshold = threshold

        return best_feature, best_threshold

    def _gini_impurity(self, left_y, right_y):
        n = len(left_y) + len(right_y)
        p_left = len(left_y) / n
        p_right = len(right_y) / n
        return p_left * self._gini(left_y) + p_right * self._gini(right_y)

    def _gini(self, y):
        if len(y) == 0:
            return 0
        counts = np.bincount(y)
        probabilities = counts / len(y)
        return 1 - np.sum(probabilities ** 2)

    def _most_common_label(self, y):
        counts = np.bincount(y)
        return np.argmax(counts)

    def predict(self, X):
        return np.array([self._traverse_tree(x, self.root) for x in X])

    def _traverse_tree(self, x, node):
        if node.value is not None:
            return node.value
        if x[node.feature] <= node.threshold:
            return self._traverse_tree(x, node.left)
        else:
            return self._traverse_tree(x, node.right)

# 示例数据
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split

iris = load_iris()
X = iris.data
y = iris.target
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# 训练模型
tree = DecisionTree(max_depth=3)
tree.fit(X_train, y_train)

# 预测
predictions = tree.predict(X_test)
print("Predictions:", predictions)
print("Actual:", y_test)