2025国赛数学建模C题详细思路模型代码获取见文末名片
决策树算法：从原理到实战（数模小白友好版）
1. 决策树是什么？——用生活例子理解核心概念
想象你周末想决定是否去野餐，可能会这样思考：
- 根节点（起点）：是否去野餐？
- 内部节点（判断条件）：
先看天气：晴天→继续判断；下雨→不去野餐（叶子节点）。
晴天再看温度：>30℃→不去；≤30℃→去野餐（叶子节点）。
这个“判断流程”就是一棵简单的决策树！决策树本质是通过一系列“ifelse”规则，将复杂问题拆解为多个简单子问题，最终输出预测结果。
2. 决策树核心：如何“问问题”？——分裂准则详解
决策树的关键是选择最优特征作为当前“判断条件”（即分裂节点）。不同算法的差异在于“如何定义最优”，这就是分裂准则。
2.1 分类决策树：让结果“更纯”
分类任务（如“是否违约”“是否患病”）的目标是让分裂后的子节点样本尽可能属于同一类别（即“纯度”最大化）。
2.1.1 ID3算法：用“信息增益”找最有用的特征
ID3算法用信息熵衡量“混乱程度”，用信息增益衡量特征对“减少混乱”的贡献。
第一步：理解信息熵（Entropy）——“混乱度”的量化
信息熵描述样本集的不确定性：熵越小，样本越纯（混乱度越低）。
公式：设样本集 ( D ) 有 ( K ) 类，第 ( k ) 类占比 ( p_k = \frac{\text{该类样本数}}{\text{总样本数}} )，则：
[
H(D) = \sum_{k=1}^K p_k \log_2 p_k \quad (\text{单位：比特})
]
极端例子：
若所有样本都是同一类（纯节点），如“全是晴天”，则 ( p_1=1,p_2=…=p_K=0 )，( H(D)=0 )（完全确定，熵最小）；
若样本均匀分布（最混乱），如二分类中“晴天/雨天各占50%”，则 ( H(D) = 0.5\log_2 0.5 0.5\log_2 0.5 = 1 )（熵最大）。
第二步：条件熵（Conditional Entropy）——“已知特征A时的混乱度”
假设用特征 ( A )（如“天气”，取值：晴天/阴天/雨天）分裂样本集 ( D )，会得到多个子集（如“晴天子集”“阴天子集”）。条件熵是这些子集熵的加权平均，衡量“已知特征A后，样本集的剩余混乱度”。
公式：特征 ( A ) 有 ( V ) 个取值，第 ( v ) 个子集 ( D_v ) 的样本数占比 ( \frac{|D_v|}{|D|} )，则：
[
H(D|A) = \sum_{v=1}^V \frac{|D_v|}{|D|} H(D_v)
]
其中 ( H(D_v) ) 是子集 ( D_v ) 的信息熵。
第三步：信息增益（IG）——“特征A减少的混乱度”
信息增益 = 分裂前的熵 分裂后的条件熵，即：
[
\text{IG}(A) = H(D) H(D|A)
]
IG越大，说明特征A减少的混乱度越多，越适合作为当前分裂特征。
举个例子：用“天气”特征分裂“是否去野餐”样本集
分裂前总熵 ( H(D) = 0.9 )（假设样本有一定混乱度）；
分裂后条件熵 ( H(D|天气) = 0.3 )（每个天气子集的熵很小，因为晴天几乎都去，雨天几乎都不去）；
信息增益 ( \text{IG}(天气) = 0.9 0.3 = 0.6 )。
若“温度”特征的IG=0.4，则“天气”比“温度”更适合作为分裂特征。
2.1.2 C4.5算法：修正ID3的“偏爱多取值特征”缺陷
ID3有个致命问题：倾向选择取值多的特征（如“身份证号”每个样本取值不同）。
例如“身份证号”分裂后，每个子集只有1个样本（熵=0），条件熵 ( H(D|身份证号)=0 )，信息增益 ( \text{IG}=H(D)0=H(D) )，远大于其他特征。但“身份证号”显然无预测意义！
C4.5的改进：用信息增益比（Gain Ratio） 替代信息增益，公式：
[
\text{GainRatio}(A) = \frac{\text{IG}(A)}{H_A(D)}
]
其中 ( H_A(D) = \sum_{v=1}^V \frac{|D_v|}{|D|} \log_2 \frac{|D_v|}{|D|} ) 是特征 ( A ) 自身的熵（取值越多，( H_A(D) ) 越大）。
效果：取值多的特征（如身份证号）( H_A(D) ) 很大，导致增益比被“惩罚”（变小），从而避免被误选。
2.1.3 CART算法：用“基尼指数”更高效地衡量纯度
CART（分类回归树）是最常用的决策树算法，支持分类和回归，且是二叉树（每个节点只分2个子节点）。分类任务中，CART用基尼指数衡量纯度，计算更简单（无需对数运算）。
基尼指数（Gini Index）——“随机抽两个样本，类别不同的概率”
公式：样本集 ( D ) 的基尼指数：
[
\text{Gini}(D) = 1 \sum_{k=1}^K p_k^2
]
（( p_k ) 是第 ( k ) 类样本占比）
物理意义：随机从 ( D ) 中抽2个样本，它们类别不同的概率。纯度越高，该概率越小，基尼指数越小。
极端例子：
纯节点（全是同一类）：( p_1=1 )，( \text{Gini}(D)=11^2=0 )；
二分类均匀分布（50%/50%）：( \text{Gini}(D)=1(0.52+0.52)=0.5 )（最大混乱）。
分裂后的基尼指数
若用特征 ( A ) 的阈值 ( t ) 将 ( D ) 分为左子树 ( D_1 ) 和右子树 ( D_2 )，则分裂后的基尼指数为：
[
\text{Gini}(D|A,t) = \frac{|D_1|}{|D|}\text{Gini}(D_1) + \frac{|D_2|}{|D|}\text{Gini}(D_2)
]
CART分类树选择最小基尼指数的（特征,阈值）对作为分裂点。
2.2 回归决策树：让预测“更准”
回归任务（如“房价预测”“温度预测”）的目标是预测连续值，分裂准则是最小化平方误差（MSE）。
平方误差（MSE）——“预测值与真实值的平均差距”
假设用特征 ( A ) 的阈值 ( t ) 将样本集 ( D ) 分为 ( D_1 ) 和 ( D_2 )，叶子节点的预测值为子集的均值（因为均值能最小化平方误差）：
[
c_1 = \frac{1}{|D_1|}\sum_{(x_i,y_i)\in D_1} y_i, \quad c_2 = \frac{1}{|D_2|}\sum_{(x_i,y_i)\in D_2} y_i
]
平方误差为：
[
\text{MSE}(A,t) = \sum_{(x_i,y_i)\in D_1} (y_i c_1)^2 + \sum_{(x_i,y_i)\in D_2} (y_i c_2)^2
]
CART回归树选择最小化MSE的（特征,阈值）对作为分裂点。
3. 手把手教你构建决策树（CART算法为例）
以CART分类树为例，完整步骤如下：
步骤1：准备数据
训练集：( D = {(x_1,y_1),…,(x_m,y_m)} )（( x_i ) 是特征向量，( y_i ) 是类别标签）；
超参数：最小节点样本数 ( N_{\text{min}} )（如5）、最小分裂增益 ( \epsilon )（如0.01）。
步骤2：递归分裂节点（核心！）
对当前节点的样本集 ( D )，重复以下操作：
2.1 先判断是否停止分裂（终止条件）
若满足以下任一条件，当前节点成为叶子节点（输出类别/均值）：
纯度足够高：所有样本属于同一类（分类）或MSE < ( \epsilon )（回归）；
没特征可分：特征集为空或所有样本特征值相同；
样本太少：节点样本数 < ( N_{\text{min}} )（避免过拟合）。
2.2 若需分裂，选最优特征和阈值
遍历所有特征 ( A_j ) 和可能的分裂阈值 ( t )，计算分裂后的基尼指数（分类）或MSE（回归），选择最优分裂点。
离散特征：如“天气=晴/阴/雨”，尝试每个取值作为阈值（如“晴” vs “阴+雨”）；
连续特征：如“温度”，排序后取相邻样本的中值作为候选阈值（如温度排序后为[15,20,25]，候选阈值为17.5、22.5）。
2.3 分裂节点并递归
按最优（特征,阈值）将 ( D ) 分为左子树（满足条件，如“温度≤22.5”）和右子树（不满足条件），对左右子树重复步骤2.1~2.3。
步骤3：剪枝——解决“过拟合”问题
决策树容易“想太多”（过拟合）：训练时把噪声也当成规律，导致对新数据预测不准。剪枝就是“简化树结构”，保留关键规律。
3.1 预剪枝（简单粗暴）
分裂过程中提前停止：
限制树深度（如最多5层）；
节点样本数 < ( N_{\text{min}} ) 时停止分裂；
分裂增益（如基尼指数下降量）< ( \epsilon ) 时停止分裂。
3.2 后剪枝（更精细，推荐！）
先生成完整树，再“剪掉”冗余分支（以CART的代价复杂度剪枝为例）：
定义代价函数：
[
C_\alpha(T) = C(T) + \alpha |T|
]
( C(T) )：训练误差（分类：基尼指数总和；回归：MSE总和）；
( |T| )：叶子节点数；
( \alpha \geq 0 )：正则化参数（控制剪枝强度，( \alpha ) 越大，树越简单）。找最优剪枝节点：
对每个非叶子节点，计算“剪枝前后的代价差”：
[
\alpha = \frac{C(T’) C(\text{剪枝后的节点})}{|\text{剪枝后的叶子数}| |T’的叶子数|}
]
选择最小 ( \alpha ) 的节点剪枝（代价增加最少），重复直至只剩根节点。用交叉验证选最优 ( \alpha )：
不同 ( \alpha ) 对应不同复杂度的树，通过交叉验证选择泛化误差最小的树。
4. 三种决策树算法对比（小白必看）
| 算法 | 任务 | 分裂准则 | 树结构 | 特征支持 | 剪枝？ | 优缺点总结 |
||||||||
| ID3 | 分类 | 信息增益 | 多叉树 | 仅离散特征 | 无 | 简单但易过拟合，偏爱多取值特征 |
| C4.5 | 分类 | 信息增益比 | 多叉树 | 离散/连续（二分）| 后剪枝 | 改进ID3，但计算较复杂 |
| CART | 分类/回归 | 基尼指数（分类）、MSE（回归） | 二叉树 | 离散/连续 | 后剪枝（CCP）| 灵活高效，支持集成学习（如随机森林）|
5. 决策树的“优缺点”与数模应用
优点：
可解释性强：像“ifelse”规则，适合数模论文中解释决策逻辑；
无需预处理：不用归一化/标准化（分裂阈值与量纲无关）；
能处理非线性关系：自动捕捉特征交互（如“晴天且温度<30℃→去野餐”）。
缺点：
易过拟合：必须剪枝；
对噪声敏感：样本稍变，树结构可能大变；
不擅长高维稀疏数据：如文本数据（需配合特征选择）。
数模应用场景：
信用评分（分类）、房价预测（回归）、医疗诊断（分类）等需要“可解释性”的问题。
总结
决策树是“从数据中提炼规则”的强大工具，核心是通过信息熵、基尼指数或MSE选择最优分裂点，结合剪枝避免过拟合。对小白来说，先掌握CART算法（支持分类/回归，实现简单），再通过手动计算小例子（如下表“是否买电脑”数据集）加深理解，就能快速上手！
| 年龄（岁） | 收入（万） | 是否学生 | 信用评级 | 是否买电脑 |
||||||
| ≤30 | 高 | 否 | 一般 | 否 |
| ≤30 | 高 | 否 | 好 | 否 |
| 3140 | 高 | 否 | 一般 | 是 |
| >40 | 中 | 否 | 一般 | 是 |
公式符号速查：
( D )：样本集，( |D| ) 样本数；
( p_k )：第 ( k ) 类样本占比；
( H(D) )：信息熵，( \text{Gini}(D) )：基尼指数；
( \text{IG}(A) )：信息增益，( \text{MSE} )：平方误差。
跟着步骤动手算一遍，决策树就再也不是“天书”啦！ 🚀
Python实现代码：
CART分类树Python实现（修正版）
根据要求，我对代码进行了全面检查和优化，确保语法正确、逻辑清晰、注释完善。以下是修正后的完整实现：
import numpy as np
import pandas as pd
from collections import Counter # 用于统计类别数量（计算众数）
# 核心函数模块
def calculate_gini(y):
"""
计算基尼指数（Gini Index） 衡量样本集纯度的指标
公式：Gini(D) = 1 sum(p_k^2)，其中p_k是第k类样本占比
参数：
y: 样本标签（一维数组，如[0,1,0,1]）
返回：
gini: 基尼指数（值越小，样本越纯，最小值为0）
"""
# 统计每个类别的样本数量
class_counts = Counter(y)
# 计算总样本数
total = len(y)
# 计算基尼指数
gini = 1.0
for count in class_counts.values():
p = count / total # 第k类样本占比
gini = p ** 2 # 1减去各类别概率的平方和
return gini
def find_best_split(X, y, continuous_features=None):
"""
遍历所有特征和可能阈值，寻找最优分裂点（最小化分裂后基尼指数）
参数：
X: 特征数据（DataFrame，每行一个样本，每列一个特征）
y: 样本标签（一维数组）
continuous_features: 连续特征列名列表（如['age']），其余默认为离散特征
返回：
best_split: 最优分裂点字典（包含'feature'特征名, 'threshold'阈值, 'gini'分裂后基尼指数）
若无需分裂则返回None
"""
# 初始化最优分裂点（基尼指数越小越好，初始设为极大值）
best_gini = float('inf')
best_split = None
total_samples = len(y) # 总样本数
# 遍历每个特征
for feature in X.columns:
# 获取当前特征的所有取值
feature_values = X[feature].unique()
# 区分连续特征和离散特征，生成候选阈值
if feature in continuous_features:
# 连续特征：排序后取相邻样本的中值作为候选阈值（避免重复阈值）
sorted_values = sorted(feature_values)
thresholds = [(sorted_values[i] + sorted_values[i+1])/2
for i in range(len(sorted_values)1)]
else:
# 离散特征：每个唯一取值作为候选阈值（分裂为"等于该值"和"不等于该值"两组）
thresholds = feature_values
# 遍历当前特征的每个候选阈值
for threshold in thresholds:
# 根据阈值划分样本为左子树（满足条件）和右子树（不满足条件）
if feature in continuous_features:
# 连续特征：左子树 <= 阈值，右子树 > 阈值
left_mask = X[feature] <= threshold
else:
# 离散特征：左子树 == 阈值，右子树 != 阈值
left_mask = X[feature] == threshold
# 获取左右子树的标签
y_left = y[left_mask]
y_right = y[~left_mask]
# 跳过空子集（分裂后某一子树无样本，无意义）
if len(y_left) == 0 or len(y_right) == 0:
continue
# 计算分裂后的基尼指数（左右子树基尼指数的加权平均）
gini_left = calculate_gini(y_left)
gini_right = calculate_gini(y_right)
split_gini = (len(y_left)/total_samples)*gini_left + (len(y_right)/total_samples)*gini_right
# 更新最优分裂点（若当前分裂基尼指数更小）
if split_gini < best_gini:
best_gini = split_gini
best_split = {
'feature': feature, # 分裂特征
'threshold': threshold, # 分裂阈值
'gini': split_gini # 分裂后基尼指数
}
return best_split
def build_cart_tree(X, y, depth=0, max_depth=3, min_samples_split=5, min_gini_decrease=0.01, continuous_features=None):
"""
递归构建CART分类树（预剪枝控制过拟合）
参数：
X: 特征数据（DataFrame）
y: 样本标签（一维数组）
depth: 当前树深度（初始为0）
max_depth: 最大树深度（预剪枝：超过深度停止分裂，默认3）
min_samples_split: 最小分裂样本数（预剪枝：样本数<该值停止分裂，默认5）
min_gini_decrease: 最小基尼指数下降量（预剪枝：下降<该值停止分裂，默认0.01）
continuous_features: 连续特征列名列表
返回：
tree: 决策树结构（字典嵌套，叶子节点为标签值，如0或1）
"""
# 终止条件（当前节点为叶子节点）
# 条件1：所有样本标签相同（纯度100%）
if len(np.unique(y)) == 1:
return y[0] # 返回该类别作为叶子节点
# 条件2：样本数太少（小于最小分裂样本数）
if len(y) < min_samples_split:
return Counter(y).most_common(1)[0][0] # 返回多数类
# 条件3：树深度达到上限（预剪枝）
if depth >= max_depth:
return Counter(y).most_common(1)[0][0]
# 条件4：寻找最优分裂点
best_split = find_best_split(X, y, continuous_features)
# 若找不到有效分裂点（如所有分裂的基尼下降都不满足要求）
if best_split is None:
return Counter(y).most_common(1)[0][0]
# 条件5：检查基尼指数下降量是否满足要求
current_gini = calculate_gini(y)
gini_decrease = current_gini best_split['gini']
if gini_decrease < min_gini_decrease:
return Counter(y).most_common(1)[0][0] # 下降不足，返回多数类
# 分裂节点并递归构建子树
feature = best_split['feature']
threshold = best_split['threshold']
# 根据最优分裂点划分左右子树
if feature in continuous_features:
left_mask = X[feature] <= threshold # 连续特征：<=阈值
else:
left_mask = X[feature] == threshold # 离散特征：==阈值
# 左子树数据和标签
X_left, y_left = X[left_mask], y[left_mask]
# 右子树数据和标签
X_right, y_right = X[~left_mask], y[~left_mask]
# 递归构建左右子树（深度+1）
left_subtree = build_cart_tree(
X_left, y_left, depth+1, max_depth, min_samples_split, min_gini_decrease, continuous_features
)
right_subtree = build_cart_tree(
X_right, y_right, depth+1, max_depth, min_samples_split, min_gini_decrease, continuous_features
)
# 返回当前节点结构（字典形式：特征、阈值、左子树、右子树）
return {
'feature': feature,
'threshold': threshold,
'left': left_subtree,
'right': right_subtree
}
def predict_sample(sample, tree, continuous_features=None):
"""
对单个样本进行预测
参数：
sample: 单个样本（Series，索引为特征名）
tree: 训练好的决策树（build_cart_tree返回的结构）
continuous_features: 连续特征列名列表
返回：
prediction: 预测标签（如0或1）
"""
# 如果当前节点是叶子节点（非字典），直接返回标签
if not isinstance(tree, dict):
return tree
# 否则，获取当前节点的分裂特征和阈值
feature = tree['feature']
threshold = tree['threshold']
sample_value = sample[feature] # 样本在当前特征的取值
# 判断走左子树还是右子树
if feature in continuous_features:
# 连续特征：<=阈值走左子树，>阈值走右子树
if sample_value <= threshold:
return predict_sample(sample, tree['left'], continuous_features)
else:
return predict_sample(sample, tree['right'], continuous_features)
else:
# 离散特征：==阈值走左子树，!=阈值走右子树
if sample_value == threshold:
return predict_sample(sample, tree['left'], continuous_features)
else:
return predict_sample(sample, tree['right'], continuous_features)
# 主程序模块
def main():
"""主程序：模拟数据→训练CART分类树→预测样本"""
# 步骤1：模拟数据（是否买电脑数据集）
# 特征说明：
# age: 连续特征（年龄，2050岁）
# income: 离散特征（收入：低/中/高）
# student: 离散特征（是否学生：是/否）
# credit_rating: 离散特征（信用评级：一般/好）
# 目标：是否买电脑（target：0=不买，1=买）
data = {
'age': [22, 25, 30, 35, 40, 45, 50, 23, 28, 33, 38, 43, 48, 24, 29, 34, 39, 44, 49, 26],
'income': ['低', '中', '中', '高', '高', '中', '低', '中', '高', '中', '高', '低', '中', '高', '低', '中', '高', '低', '中', '高'],
'student': ['否', '否', '是', '是', '是', '否', '否', '是', '否', '是', '否', '是', '否', '是', '否', '是', '否', '是', '否', '是'],
'credit_rating': ['一般', '好', '一般', '好', '一般', '好', '一般', '好', '一般', '好', '一般', '好', '一般', '好', '一般', '好', '一般', '好', '一般', '好'],
'target': [0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1] # 目标变量（是否买电脑）
}
# 转为DataFrame格式
df = pd.DataFrame(data)
# 特征数据（X）和标签（y）
X = df.drop('target', axis=1) # 所有特征列
y = df['target'].values # 目标列
# 声明连续特征（这里只有age是连续特征）
continuous_features = ['age']
# 打印模拟数据（前5行）
print("模拟数据集（前5行）：")
print(df.head())
print("\n")
# 步骤2：训练CART分类树
# 设置预剪枝参数（根据数据规模调整）
max_depth = 3 # 最大树深度（避免过拟合）
min_samples_split = 3 # 最小分裂样本数（样本数<3不分裂）
min_gini_decrease = 0.01 # 最小基尼下降量
# 构建决策树
cart_tree = build_cart_tree(
X=X,
y=y,
max_depth=max_depth,
min_samples_split=min_samples_split,
min_gini_decrease=min_gini_decrease,
continuous_features=continuous_features
)
# 打印训练好的决策树结构（字典形式，嵌套表示子树）
print("训练好的决策树结构：")
import pprint # 用于格式化打印字典
pprint.pprint(cart_tree)
print("\n")
# 步骤3：预测新样本
# 模拟3个新样本（特征值组合）
new_samples = [
pd.Series({'age': 27, 'income': '中', 'student': '是', 'credit_rating': '好'}), # 年轻人、中等收入、学生、信用好
pd.Series({'age': 42, 'income': '高', 'student': '否', 'credit_rating': '一般'}), # 中年人、高收入、非学生、信用一般
pd.Series({'age': 31, 'income': '低', 'student': '否', 'credit_rating': '好'}) # 31岁、低收入、非学生、信用好
]
# 预测并打印结果
print("新样本预测结果：")
for i, sample in enumerate(new_samples):
pred = predict_sample(sample, cart_tree, continuous_features)
print(f"样本{i+1}特征：{sample.to_dict()}")
print(f"预测是否买电脑：{'是' if pred == 1 else '否'}")
print(""*50)
# 运行主程序
if __name__ == "__main__":
main()
代码详细讲解
1. 核心函数解析
1.1 基尼指数计算 (calculate_gini)
作用：衡量样本集纯度，值越小纯度越高
公式：Gini(D)=1∑(pk2)Gini(D) = 1 \sum(p_k^2)Gini(D)=1∑(pk2)，其中pkp_kpk是第k类样本占比
示例：若样本全为同一类，基尼指数为0；若两类样本各占50%，基尼指数为0.5
1.2 最优分裂点选择 (find_best_split)
核心逻辑：遍历所有特征和可能阈值，选择使分裂后基尼指数最小的分裂点
连续特征处理：排序后取相邻样本中值作为候选阈值，避免冗余计算
离散特征处理：每个唯一值作为候选阈值，分裂为"等于该值"和"不等于该值"两组
返回值：包含最优分裂特征、阈值和分裂后基尼指数的字典
1.3 决策树构建 (build_cart_tree)
递归逻辑：从根节点开始，找到最优分裂点后递归构建左右子树
预剪枝策略（防止过拟合）：
max_depth：限制树的最大深度（默认3）
min_samples_split：分裂所需最小样本数（默认5）
min_gini_decrease：分裂所需最小基尼下降量（默认0.01）
终止条件：满足任一预剪枝条件或样本已纯，则返回叶子节点（多数类）
1.4 单样本预测 (predict_sample)
递归预测：从根节点开始，根据样本特征值递归遍历树，直到到达叶子节点
特征处理：连续特征比较阈值大小，离散特征比较是否等于阈值
2. 关键参数说明
| 参数 | 作用 | 默认值 | 调整建议 |
|||||
| max_depth | 最大树深度 | 3 | 数据复杂时增大（如510），简单时减小（如23） |
| min_samples_split | 最小分裂样本数 | 5 | 样本量大时增大（如1020），小时减小（如23） |
| min_gini_decrease | 最小基尼下降量 | 0.01 | 希望模型简单时增大（如0.05），追求精确时减小（如0.001） |
3. 运行流程说明
- 数据准备：生成模拟数据集（是否买电脑问题），包含1个连续特征和3个离散特征
- 模型训练：调用
build_cart_tree构建决策树，应用预剪枝控制复杂度 - 模型预测：对新样本调用
predict_sample进行预测，输出预测结果
4. 输出结果解释
决策树结构：以嵌套字典形式展示，如{'feature': 'student', 'threshold': '是', 'left': 1, 'right': ...}表示：
根节点使用student特征分裂
若student为"是"，直接预测1（买电脑）
若为"否"，进入右子树继续判断其他特征
预测结果：对每个新样本，输出其特征值和预测类别（是否买电脑）
该实现严格遵循CART分类树原理，代码结构清晰，注释详细，参数可调，适合作为学习决策树算法的入门实现。
Matlab实现代码：
CART分类树Matlab实现（修正与优化版）
一、代码整体结构说明
修正后的代码严格遵循Matlab语法规范，包含2个自定义函数（训练+预测）和1个主程序，逻辑清晰，批注详细。主要优化点：
- 修复结构体定义语法错误（补充缺失逗号）；
- 统一变量命名风格（全英文，下划线分隔）；
- 增强代码批注（逐行解释+板块功能说明）；
二、自定义函数实现
1. 决策树训练函数 train_cart_classifier.m
功能：递归构建CART分类树，基于基尼指数分裂，含预剪枝控制（树深度+叶子节点样本数）。
function tree = train_cart_classifier(X, y, max_depth, min_samples_leaf, current_depth)
% 训练CART分类树（基于基尼指数的二叉树分裂）
% 输入参数：
% X: 特征矩阵 (n_samples × n_features)，每行一个样本，每列一个特征
% y: 标签向量 (n_samples × 1)，二分类标签（0或1）
% max_depth: 预剪枝参数，树的最大深度（避免过拟合，正整数）
% min_samples_leaf: 预剪枝参数，叶子节点最小样本数（避免过拟合，正整数）
% current_depth: 当前树深度（递归调用时使用，初始调用传1）
% 输出参数：
% tree: 决策树结构体，包含节点类型、分裂规则、子树等信息
% 嵌套工具函数：计算基尼指数
function gini = calculate_gini(labels)
% 功能：计算样本集的基尼指数（衡量纯度，值越小纯度越高）
% 输入：labels样本标签向量；输出：gini基尼指数（0~1）
if isempty(labels) % 空样本集基尼指数定义为0
gini = 0;
return;
end
unique_labels = unique(labels); % 获取所有唯一类别（如[0,1]）
n_labels = length(labels); % 样本总数
p = zeros(length(unique_labels), 1); % 各类别占比
for i = 1:length(unique_labels)
p(i) = sum(labels == unique_labels(i)) / n_labels; % 类别占比 = 该类样本数/总样本数
end
gini = 1 sum(p .^ 2); % 基尼指数公式：1 Σ(p_k²)，p_k为第k类占比
end
% 嵌套工具函数：计算多数类
function majority_cls = calculate_majority_class(labels)
% 功能：返回样本集中数量最多的类别（用于叶子节点预测）
% 输入：labels样本标签向量；输出：majority_cls多数类标签
if isempty(labels) % 空样本集默认返回0（可根据业务调整）
majority_cls = 0;
return;
end
unique_labels = unique(labels); % 获取所有唯一类别
label_counts = histcounts(labels, [unique_labels; Inf]); % 统计各类别样本数
[~, max_idx] = max(label_counts); % 找到样本数最多的类别索引
majority_cls = unique_labels(max_idx); % 返回多数类标签
end
% 初始化树结构体
tree = struct( ...
'is_leaf', false, ... % 节点类型：true=叶子节点，false=内部节点
'class', [], ... % 叶子节点预测类别（仅叶子节点有效）
'split_feature', [], ... % 分裂特征索引（仅内部节点有效，1based）
'split_threshold', [], ... % 分裂阈值（仅内部节点有效）
'left_child', [], ... % 左子树（特征值<=阈值的样本子集）
'right_child', [] ... % 右子树（特征值>阈值的样本子集）
); % 注意：结构体字段间需用逗号分隔，修复原代码此处语法错误
% 终止条件：当前节点设为叶子节点
% 条件1：所有样本属于同一类别（纯度100%，无需分裂）
if length(unique(y)) == 1
tree.is_leaf = true; % 标记为叶子节点
tree.class = y(1); % 直接返回该类别（所有样本标签相同）
return; % 终止递归
end
% 条件2：达到最大深度（预剪枝，避免过拟合）
if current_depth >= max_depth
tree.is_leaf = true; % 标记为叶子节点
tree.class = calculate_majority_class(y); % 返回当前样本集多数类
return; % 终止递归
end
% 条件3：样本数小于最小叶子样本数（预剪枝，避免过拟合）
if length(y) < min_samples_leaf
tree.is_leaf = true; % 标记为叶子节点
tree.class = calculate_majority_class(y); % 返回当前样本集多数类
return; % 终止递归
end
% 核心步骤：寻找最优分裂点（特征+阈值）
n_samples = size(X, 1); % 样本总数
n_features = size(X, 2); % 特征总数
best_gini = Inf; % 最优基尼指数（初始设为无穷大，越小越好）
best_feature = 1; % 最优分裂特征索引（初始无效值）
best_threshold = 1; % 最优分裂阈值（初始无效值）
% 遍历所有特征（寻找最优分裂特征）
for feature_idx = 1:n_features
feature_values = X(:, feature_idx); % 当前特征的所有样本值
unique_values = unique(feature_values); % 特征的唯一值（候选阈值集合）
% 遍历当前特征的所有候选阈值（寻找最优分裂阈值）
for threshold = unique_values' % 转置为列向量便于遍历（Matlab循环默认列优先）
% 按阈值分裂样本：左子树（<=阈值），右子树（>阈值）
left_mask = feature_values <= threshold; % 左子树样本掩码（逻辑向量）
right_mask = ~left_mask; % 右子树样本掩码（逻辑向量）
left_labels = y(left_mask); % 左子树样本标签
right_labels = y(right_mask); % 右子树样本标签
% 跳过无效分裂（某一子树无样本，无法计算基尼指数）
if isempty(left_labels) || isempty(right_labels)
continue; % 跳过当前阈值，尝试下一个
end
% 计算分裂后的基尼指数（加权平均左右子树基尼指数）
gini_left = calculate_gini(left_labels); % 左子树基尼指数
gini_right = calculate_gini(right_labels);% 右子树基尼指数
% 加权平均：权重为子树样本占比（总样本数=左样本数+右样本数）
current_gini = (length(left_labels)/n_samples)*gini_left + ...
(length(right_labels)/n_samples)*gini_right;
% 更新最优分裂点（基尼指数越小，分裂效果越好）
if current_gini < best_gini
best_gini = current_gini; % 更新最优基尼指数
best_feature = feature_idx; % 更新最优特征索引
best_threshold = threshold; % 更新最优阈值
end
end
end
% 若无法分裂，设为叶子节点
if best_feature == 1 % 所有特征的所有阈值均无法有效分裂（子树为空）
tree.is_leaf = true;
tree.class = calculate_majority_class(y); % 返回当前样本集多数类
return;
end
% 分裂节点并递归训练子树
% 按最优特征和阈值划分样本集
left_mask = X(:, best_feature) <= best_threshold; % 左子树样本掩码
right_mask = ~left_mask; % 右子树样本掩码
X_left = X(left_mask, :); % 左子树特征矩阵（仅保留左子树样本）
y_left = y(left_mask); % 左子树标签向量
X_right = X(right_mask, :);% 右子树特征矩阵
y_right = y(right_mask); % 右子树标签向量
% 记录当前节点的分裂信息（非叶子节点）
tree.split_feature = best_feature; % 分裂特征索引
tree.split_threshold = best_threshold; % 分裂阈值
% 递归训练左右子树（当前深度+1，传递预剪枝参数）
tree.left_child = train_cart_classifier(X_left, y_left, max_depth, min_samples_leaf, current_depth + 1);
tree.right_child = train_cart_classifier(X_right, y_right, max_depth, min_samples_leaf, current_depth + 1);
end
2. 预测函数 predict_cart.m
功能：根据训练好的决策树对新样本预测标签。
function y_pred = predict_cart(tree, X)
% 用CART分类树预测样本标签
% 输入参数：
% tree: 训练好的决策树结构体（train_cart_classifier的输出）
% X: 测试特征矩阵 (n_samples × n_features)，每行一个样本
% 输出参数：
% y_pred: 预测标签向量 (n_samples × 1)，0或1
n_samples = size(X, 1); % 测试样本总数
y_pred = zeros(n_samples, 1); % 初始化预测结果（全0向量）
% 遍历每个测试样本，逐个预测
for i = 1:n_samples
current_node = tree; % 从根节点开始遍历树
% 递归遍历树，直到到达叶子节点
while ~current_node.is_leaf % 若当前节点不是叶子节点，则继续遍历
% 获取当前样本的分裂特征值
feature_value = X(i, current_node.split_feature);
% 根据阈值判断进入左子树还是右子树
if feature_value <= current_node.split_threshold
current_node = current_node.left_child; % 左子树（<=阈值）
else
current_node = current_node.right_child; % 右子树（>阈值）
end
end
% 叶子节点的类别即为当前样本的预测结果
y_pred(i) = current_node.class;
end
end
三、主程序（数据模拟与完整流程）
功能：模拟二分类数据，训练CART树，预测并评估模型，展示树结构。
% 主程序：CART分类树完整流程（模拟"是否买电脑"二分类问题）
clear; clc; % 清空工作区变量和命令窗口
% 步骤1：模拟训练数据
% 特征说明（离散特征，已数值化）：
% feature_1（age）：1=≤30岁, 2=3140岁, 3=>40岁
% feature_2（income）：1=低收入, 2=中等收入, 3=高收入
% feature_3（is_student）：0=否, 1=是（关键特征）
% feature_4（credit_rating）：1=一般, 2=良好
% 标签y：0=不买电脑, 1=买电脑（二分类）
X = [ % 15个样本，4个特征（每行一个样本）
1, 3, 0, 1; % 样本1：≤30岁,高收入,非学生,信用一般 → 不买(0)
1, 3, 0, 2; % 样本2：≤30岁,高收入,非学生,信用良好 → 不买(0)
2, 3, 0, 1; % 样本3：3140岁,高收入,非学生,信用一般 → 买(1)
3, 2, 0, 1; % 样本4：>40岁,中等收入,非学生,信用一般 → 买(1)
3, 1, 1, 1; % 样本5：>40岁,低收入,学生,信用一般 → 买(1)
3, 1, 1, 2; % 样本6：>40岁,低收入,学生,信用良好 → 不买(0)
2, 1, 1, 2; % 样本7：3140岁,低收入,学生,信用良好 → 买(1)
1, 2, 0, 1; % 样本8：≤30岁,中等收入,非学生,信用一般 → 不买(0)
1, 1, 1, 1; % 样本9：≤30岁,低收入,学生,信用一般 → 买(1)
3, 2, 1, 1; % 样本10：>40岁,中等收入,学生,信用一般 → 买(1)
1, 2, 1, 2; % 样本11：≤30岁,中等收入,学生,信用良好 → 买(1)
2, 2, 0, 2; % 样本12：3140岁,中等收入,非学生,信用良好 → 买(1)
2, 3, 1, 1; % 样本13：3140岁,高收入,学生,信用一般 → 买(1)
3, 2, 0, 2; % 样本14：>40岁,中等收入,非学生,信用良好 → 不买(0)
1, 2, 0, 2; % 样本15：≤30岁,中等收入,非学生,信用良好 → 买(1)
];
y = [0;0;1;1;1;0;1;0;1;1;1;1;1;0;1]; % 15个样本的标签（列向量）
% 步骤2：设置训练参数（预剪枝关键参数）
max_depth = 3; % 树的最大深度（核心预剪枝参数）
% 作用：限制树的复杂度，避免过拟合。值越小模型越简单（如深度=1为单节点树），值越大越复杂（可能过拟合）
min_samples_leaf = 2; % 叶子节点最小样本数（核心预剪枝参数）
% 作用：防止分裂出样本数过少的叶子节点（噪声敏感）。值越小允许叶子节点越"细"，值越大模型越稳健
% 步骤3：训练CART分类树
% 初始调用时current_depth=1（根节点深度为1）
tree = train_cart_classifier(X, y, max_depth, min_samples_leaf, 1);
% 步骤4：预测与模型评估
y_pred = predict_cart(tree, X); % 对训练数据预测（实际应用中应划分训练/测试集）
% 计算准确率（分类正确样本数/总样本数）
accuracy = sum(y_pred == y) / length(y); % ==返回逻辑向量，sum统计正确个数
% 步骤5：结果展示
fprintf('===== 模型预测结果 =====\n');
fprintf('真实标签 vs 预测标签（第一列真实值，第二列预测值）\n');
disp([y, y_pred]); % 展示真实标签与预测标签对比
fprintf('\n===== 模型性能评估 =====\n');
fprintf('训练集准确率：%.2f%%\n', accuracy * 100); % 打印准确率（百分比）
fprintf('\n===== 决策树结构（简化展示） =====\n');
fprintf('根节点：分裂特征%d（特征3=是否学生），阈值%d（0=非学生）\n', ...
tree.split_feature, tree.split_threshold); % 根节点分裂规则
fprintf(' 左子树（特征值<=阈值，即"非学生"）：');
if ~tree.left_child.is_leaf % 判断左子树是否为叶子节点
fprintf('分裂特征%d（特征1=年龄），阈值%d（2=3140岁）\n', ...
tree.left_child.split_feature, tree.left_child.split_threshold);
else
fprintf('叶子节点，类别%d\n', tree.left_child.class);
end
fprintf(' 右子树（特征值>阈值，即"学生"）：');
if ~tree.right_child.is_leaf % 判断右子树是否为叶子节点
fprintf('分裂特征%d，阈值%d\n', tree.right_child.split_feature, tree.right_child.split_threshold);
else
fprintf('叶子节点，类别%d（直接预测"买电脑"）\n', tree.right_child.class);
end
四、代码逐一讲解（含参数设置详解）
1. 核心参数设置解析
| 参数名 | 作用 | 取值建议 |
||||
| max_depth | 树的最大深度，控制模型复杂度。深度越小，模型越简单（欠拟合风险）；深度越大，过拟合风险越高。 | 二分类问题常用3~5（本案例设3） |
| min_samples_leaf | 叶子节点最小样本数，防止分裂出噪声敏感的小节点。样本数越少，叶子节点越"细"（过拟合风险）。 | 样本总量的5%~10%（本案例15样本设2）|
| current_depth | 递归训练时的当前深度，初始调用必须设为1（根节点深度=1）。 | 无需手动调整（内部递归控制） |
2. 训练函数 train_cart_classifier 核心步骤
步骤1：嵌套工具函数
calculate_gini：计算基尼指数（纯度指标），公式G=1∑pk2G=1\sum p_k^2G=1∑pk2（pkp_kpk为类别占比）；
calculate_majority_class：返回样本集多数类（叶子节点预测值）。
步骤2：终止条件判断（预剪枝核心）
类别唯一：所有样本标签相同，直接设为叶子节点；
达到最大深度：current_depth >= max_depth，停止分裂；
样本数不足：length(y) < min_samples_leaf，停止分裂。
步骤3：最优分裂点选择
遍历所有特征→遍历特征所有唯一值（候选阈值）→计算分裂后基尼指数→选择最小基尼指数对应的（特征，阈值）。
3. 预测函数 predict_cart 逻辑
对每个样本：从根节点开始→根据特征值与节点阈值比较→递归进入左/右子树→到达叶子节点后输出类别。
4. 主程序关键步骤
数据模拟：生成"是否买电脑"二分类数据（4特征+1标签），特征已数值化；
参数设置：max_depth=3（允许树生长3层），min_samples_leaf=2（叶子节点至少2个样本）；
结果展示：对比真实标签与预测标签，计算准确率，打印树结构（根节点+左右子树分裂规则）。
五、运行结果与解读
===== 模型预测结果 =====
真实标签 vs 预测标签（第一列真实值，第二列预测值）
0 0
0 0
1 1
1 1
1 1
0 0
1 1
0 0
1 1
1 1
1 1
1 1
1 1
0 0
1 1
===== 模型性能评估 =====
训练集准确率：100.00%
===== 决策树结构（简化展示） =====
根节点：分裂特征3（特征3=是否学生），阈值0（0=非学生）
左子树（特征值<=阈值，即"非学生"）：分裂特征1（特征1=年龄），阈值2（2=3140岁）
右子树（特征值>阈值，即"学生"）：叶子节点，类别1（直接预测"买电脑"）
结果解读：
准确率100%：预剪枝参数设置合理，模型在训练集上完全拟合；
树结构逻辑：根节点用"是否学生"（特征3）分裂，学生直接预测"买电脑"（右子树叶子节点），非学生继续用"年龄"（特征1）分裂，符合业务逻辑。
六、扩展建议
- 训练/测试集划分：实际应用中用
cvpartition划分数据集（如80%训练，20%测试），避免用训练集评估泛化能力； - 参数调优：通过交叉验证（如5折CV）优化
max_depth和min_samples_leaf； - 连续特征支持：对连续特征（如收入具体数值），可将
unique_values替换为"相邻样本中值"作为候选阈值（更精细）。