从零构建CART决策树：基于西瓜数据集的机器学习入门实战

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

背景介绍

决策树是机器学习中最直观的算法之一，特别适合分类问题。CART（Classification and Regression Trees）算法通过基尼系数选择特征，能够处理连续和离散数据。相比 ID3 和 C4.5，CART 生成的二叉树结构更简单，且支持回归任务。

数据预处理

加载西瓜数据集

西瓜数据集包含 17 个样本，特征包括色泽、根蒂、敲声等离散属性，以及密度、含糖率等连续值。

import pandas as pd
melon_data = pd.read_csv('watermelon.csv')
print(melon_data.head())

缺失值处理

• 连续特征用均值填充
• 离散特征用众数填充

# 连续特征处理
melon_data['密度'].fillna(melon_data['密度'].mean(), inplace=True)

# 离散特征处理
from sklearn.preprocessing import LabelEncoder
le = LabelEncoder()
for col in ['色泽', '根蒂', '敲声']:
    melon_data[col] = le.fit_transform(melon_data[col])

算法实现

基尼系数计算

基尼系数表示数据不纯度，值越小越好：
$$Gini(D) = 1 – \sum_{k=1}^{K}(\frac{|C_k|}{|D|})^2$$

def gini_index(groups, classes):
    n_instances = sum([len(group) for group in groups])
    gini = 0.0
    for group in groups:
        size = len(group)
        if size == 0:
            continue
        score = 0.0
        for class_val in classes:
            p = [row[-1] for row in group].count(class_val) / size
            score += p * p
        gini += (1.0 - score) * (size / n_instances)
    return gini

特征选择

遍历所有特征和分割点，选择基尼系数最小的组合：

1. 对每个特征进行排序
2. 检查相邻样本的中点作为候选分割点
3. 计算每个分割点的基尼系数

递归建树

终止条件：
– 节点样本数小于阈值
– 基尼系数为 0（纯节点）
– 没有更多特征可用

# 节点类定义
class Node:
    def __init__(self, feature_index=None, threshold=None, left=None, right=None, value=None):
        self.feature_index = feature_index  # 特征索引
        self.threshold = threshold          # 分割阈值
        self.left = left                    # 左子树
        self.right = right                  # 右子树
        self.value = value                  # 叶节点值 

可视化展示

安装 graphviz 后，可以导出决策树：

from sklearn.tree import export_graphviz
import graphviz

dot_data = export_graphviz(tree_model, out_file=None, 
                          feature_names=features,
                          class_names=['bad','good'],
                          filled=True)
graph = graphviz.Source(dot_data)
graph.render("melon_tree")

模型评估

使用混淆矩阵和准确率评估模型性能：

from sklearn.metrics import confusion_matrix, accuracy_score

preds = [predict(tree, row) for row in X_test]
print("Confusion Matrix:")
print(confusion_matrix(y_test, preds))
print("Accuracy:", accuracy_score(y_test, preds))

避坑指南

过拟合解决方案

• 预剪枝：限制树深度或最小样本数
• 后剪枝：CCP 代价复杂度剪枝

类别不平衡处理

• 样本重采样（过采样 / 欠采样）
• 使用类别权重参数

连续特征离散化

• 等宽分箱可能效果不佳
• 建议使用决策树自带的最优分割

扩展思考

算法对比实验

可以设计实验比较 CART、ID3、C4.5 在相同数据集上的表现：

1. 训练时间对比
2. 准确率对比
3. 树深度对比

sklearn 调用示例

from sklearn.tree import DecisionTreeClassifier

# CART 实现
dtc = DecisionTreeClassifier(criterion='gini')

# C4.5 实现（使用信息增益比）# 需自定义 criterion 参数 

结语

通过这个实战项目，我们完整实现了 CART 决策树算法。建议读者尝试调整参数观察模型变化，并扩展到其他数据集。决策树是理解更复杂模型（如随机森林、GBDT）的基础，掌握核心原理非常重要。