虽然二叉搜索树(Binary Search Trees)擅长根据固有顺序组织数据以进行高效查找,但机器学习中的树状结构通常服务于不同的目的:进行预测。决策树是一种主要的监督学习算法,它使用树状结构来模拟决策及其可能的结果。决策树不是像二叉搜索树那样直接存储数据点,而是表示一系列关于数据点特征的问题或检验,以得出预测。决策树的结构想象一个流程图,其中每个步骤都针对您的数据提出一个问题。这基本就是决策树所代表的。它包含:根节点: 树的起点,代表整个数据集。它根据第一次检验的结果分叉。内部节点(决策节点): 每个内部节点都代表对特定特征的检验。对于数值特征,该检验通常是阈值比较(例如,feature_X <= 5.0)。对于类别特征,它可能检查相等性或是否属于某组类别(例如,feature_Y == 'category_A')。分支(边): 从内部节点发出的每个分支对应检验的一个结果(例如,阈值分割的True或False,或类别分割的特定类别)。这些分支指向下一个节点。叶节点(终端节点): 这些节点代表最终的结果或预测。在分类任务中,叶节点通常包含到达该节点的所有训练样本的多数类别。在回归任务中,它通常包含样本的平均目标值。新的数据点通过从根节点开始,并根据数据点特征值在每个内部节点的检验结果沿着树向下遍历,直到到达叶节点,从而被分类或预测。digraph G { rankdir=TB; node [shape=box, style=filled, fontname="helvetica", fontsize=10]; edge [fontname="helvetica", fontsize=9]; 0 [label="天气展望 <= 0.5?\n(晴天=0, 阴天=1, 雨天=2)", fillcolor="#a5d8ff"]; 1 [label="湿度 <= 0.5?\n(高=0, 正常=1)", fillcolor="#a5d8ff"]; 2 [label="打球 = 是\n(样本: [0, 4])", fillcolor="#b2f2bb", shape=ellipse]; // 阴天 -> 打球=是 3 [label="刮风 <= 0.5?\n(否=0, 是=1)", fillcolor="#a5d8ff"]; 4 [label="打球 = 否\n(样本: [3, 0])", fillcolor="#ffc9c9", shape=ellipse]; // 晴天, 湿度=高 -> 打球=否 5 [label="打球 = 是\n(样本: [0, 2])", fillcolor="#b2f2bb", shape=ellipse]; // 晴天, 湿度=正常 -> 打球=是 6 [label="打球 = 是\n(样本: [0, 3])", fillcolor="#b2f2bb", shape=ellipse]; // 雨天, 刮风=否 -> 打球=是 7 [label="打球 = 否\n(样本: [2, 0])", fillcolor="#ffc9c9", shape=ellipse]; // 雨天, 刮风=是 -> 打球=否 0 -> 1 [label="是 (晴天)"]; 0 -> 2 [label="否 > 0.5 (阴天/雨天)"]; // 简化分割以作说明 // 根据常见的树构建(通常为简单起见采用二叉或多路)校正分割逻辑 // 让我们根据天气展望类别正确地改进 0 -> 分割 // 假设天气展望:晴天=0, 阴天=1, 雨天=2 // 让我们进行第一次分割:天气展望是否 == 阴天 (1)? // 让我们用更典型的分割策略重绘。例如:天气展望是否 == 晴天? // 使用典型的二叉分割方法重绘 graph [nodesep=0.3, ranksep=0.4]; node [shape=box, style=filled, fontname="helvetica", fontsize=10, width=1.5, height=0.6]; edge [fontname="helvetica", fontsize=9]; N0 [label="天气展望 = 晴天?", fillcolor="#a5d8ff"]; N1 [label="湿度 > 75?", fillcolor="#74c0fc"]; N2 [label="天气展望 = 雨天?", fillcolor="#a5d8ff"]; // 如果天气展望不是晴天,则为节点 N3 [label="打球 = 否\n(3 样本)", fillcolor="#ffc9c9", shape=ellipse, width=1, height=0.5]; // 晴天, 湿度 > 75 N4 [label="打球 = 是\n(2 样本)", fillcolor="#b2f2bb", shape=ellipse, width=1, height=0.5]; // 晴天, 湿度 <= 75 N5 [label="打球 = 是\n(4 样本)", fillcolor="#b2f2bb", shape=ellipse, width=1, height=0.5]; // 阴天 (如果不是晴天或雨天,则隐式处理) N6 [label="刮风 = 是?", fillcolor="#74c0fc"]; // 雨天 N7 [label="打球 = 否\n(2 样本)", fillcolor="#ffc9c9", shape=ellipse, width=1, height=0.5]; // 雨天, 刮风 = 是 N8 [label="打球 = 是\n(3 样本)", fillcolor="#b2f2bb", shape=ellipse, width=1, height=0.5]; // 雨天, 刮风 = 否 // 结构边 N0 -> N1 [label="是"]; N0 -> N2 [label="否"]; // 不是晴天 -> 可能是阴天或雨天 N1 -> N3 [label="是"]; N1 -> N4 [label="否"]; N2 -> N5 [label="否 (阴天)"]; // 如果不是晴天也不是雨天 -> 阴天 N2 -> N6 [label="是 (雨天)"]; N6 -> N7 [label="是"]; N6 -> N8 [label="否"]; }一个简单的决策树,用于根据天气情况预测是否打网球。内部节点检验特征,分支表示结果,叶节点给出预测。构建决策树:递归划分决策树通常使用递归算法构建,该算法旨在将数据划分成相对于目标变量尽可能“纯净”的子集。其主要思想是重复选择最佳特征和分割点(阈值或类别),以最大限度地分离类别或减少目标值的方差。CART(分类和回归树)和ID3(迭代二分器3)等常见算法实现了这种递归划分。该过程包含:开始时,根节点包含整个数据集。评估分割点: 对于每个特征,评估所有可能的分割点。对于数值特征,这通常涉及对唯一值进行排序并检验它们之间的阈值。对于类别特征,可以检验不同的类别分组。选择最佳分割点: 选择导致最大“信息增益”或最大“不纯度”降低的特征和分割点。不纯度度量量化了节点内目标值的混合程度。基尼不纯度: CART中常用。对于包含 $C$ 个类别的节点,其中 $p_i$ 是属于类别 $i$ 的样本比例,基尼不纯度为: $$ 基尼 = 1 - \sum_{i=1}^{C} p_i^2 $$ 基尼得分为0表示完美纯净(所有样本属于一个类别),而最高分(对于两个类别接近0.5,对于更多类别更高)表示最大不纯度(类别均匀混合)。熵: 常用在ID3和C4.5中。它衡量节点内的无序或不确定性程度: $$ 熵 = - \sum_{i=1}^{C} p_i \log_2(p_i) $$ 其中 $p_i$ 是类别 $i$ 的样本比例。对于纯节点,熵为0;当类别均匀分布时,熵达到最大值。根据约定,$0 \log_2 0 = 0$。信息增益 计算为父节点不纯度与分割后子节点加权平均不纯度之间的差值: $$ 信息增益 = 不纯度_{父节点} - \sum_{j \in children} \frac{N_j}{N} 不纯度_{子节点_j} $$ 其中 $N$ 是父节点处的样本总数,$N_j$ 是子节点 $j$ 中的样本数量。选择使此增益最大化的分割点。对于回归树,通常使用方差减少而不是不纯度度量。创建子节点: 根据选定的特征和阈值分割数据集,创建新的子节点。递归: 对每个新创建的子节点重复步骤2-4。停止条件: 当满足预设条件时,分支的递归停止:节点纯净(所有样本属于同一类别或具有非常相似的目标值)。达到最大树深度。节点中的样本数量低于最小阈值。找不到可以显著改善不纯度的分割点。 该节点随后成为叶节点。结构与预测的关联树状结构直接表示学到的决策逻辑。遍历树反映了根据特征值应用一系列条件检查的过程。这种分层划分使得决策树能够近似特征空间中复杂、非线性的决策边界。虽然简单且易于理解,但单个决策树很容易过拟合训练数据,捕获到噪声而非潜在信号。它们也可能不稳定,这意味着训练数据中的微小变化可能导致显著不同的树状结构。这些局限性通常通过使用集成方法来解决,例如随机森林和梯度提升树(在下一节讨论),这些方法结合了多个决策树以提高鲁棒性和预测性能。在研究这些更高级的集成技术之前,了解单个决策树的核心结构和构建算法是必要的。