半监督决策树
- 提出者
- Various (Levin & Shapiro; Zhu & Goldberg lineage)
- 年份
- 2000s
- 类型
- Semi-supervised classifier / regressor
- 类别
- Machine learning
本文为机器翻译,尚未经过审校。 阅读英文原文
它有什么作用?
半监督决策树是对标准决策树归纳(如 CART 或 C4.5)的扩展,它利用未标记的观测数据以及标记的训练集。通过迭代地为未标记数据分配暂定标签并将其纳入生长或分裂过程,该算法可以实现比仅在标记子集上训练的全监督树更高的准确性,这在标记成本高昂或耗时时尤其有价值。
方法背后的直觉
标记每个观测值成本高昂,但未标记数据仍然包含有关特征空间的有用结构信息。半监督决策树通过首先从少量标记样本构建一棵树,然后使用该树暂定标记未标记数据,最后在扩展集上重新训练来利用这一点。重复迭代同时精炼暂定标签和树结构,因此即使真实标签稀缺,模型也能从整体数据分布中学习。
历史学
半监督学习于 20 世纪 90 年代末出现,研究人员试图利用网络分类和计算生物学等领域中丰富的未标记数据。决策树的自训练变体,其中一棵树迭代地标记自己的未标记数据,是最早的实例之一。Zhu & Goldberg (2009) 的调查论文对该方法进行了正式处理,该论文将基于树的自训练置于更广泛的半监督学习分类法中。此后,该方法已扩展到集成设置,产生了半监督随机森林和梯度提升树。
何时使用
当标记数据稀缺且获取成本高昂,但有大量未标记观测数据可用时,半监督决策树是合适的——这在医学影像标注、文本分类和基于传感器的监控中很常见。当整体特征分布能被未标记数据池很好地捕捉,并且需要一个人类可解释的模型(一棵树)时,它们特别有用。当标记样本太少以至于初始树非常不可靠,当未标记数据不能代表测试分布,或者当伪标记过程预计会传播系统性错误(确认偏差)时,应避免使用此方法。在这些情况下,在干净标记数据上使用纯监督方法,或使用标签传播或协同训练等替代半监督方法可能更安全。
局限与注意事项
- 来自不可靠初始树的伪标签错误可能在迭代过程中被放大,导致性能相对于全监督基线下降。
- 该方法假设未标记数据与标记数据具有相同的底层分布;分布偏移会破坏此假设。
- 计算成本随着每次迭代而增加,因为树在越来越大的有效数据集上重新训练。
- 选择伪标签包含的置信度阈值需要仔细调整和交叉验证。
来源中的条件不能替代独立的科学审查或分析引擎的验证。
优势
- 在标记样本很少的情况下,利用未标记数据提高准确性,降低标注成本。
- 保留决策树的可解释性:生成的模型是一组人类可读的 if-then 规则。
- 自然处理混合特征类型——连续、分类、二元——而无需预处理归一化。
- 迭代自训练可以轻松地在任何现有树学习器之上实现。
- 可以捕捉线性半监督模型所遗漏的非线性边界和特征交互。
应用
- 医学影像和记录分类,其中专家标注成本高昂且存在大量未标注档案。
- 文本和文档分类,其中标记语料库很小而未标记集合很大。
- 传感器和物联网数据分析,其中只有一小部分时间序列段被手动标记。
- 生物信息学任务,例如基因功能预测,其中实验验证的标签很少。
- 欺诈检测,其中标记的欺诈案例与大量未标记交易相比很少。
使用方式
使用方式
使用仅标记部分数据集的拟合标准决策树(例如 CART 或 C4.5)。此初始模型提供了决策边界的初步近似,并作为后续半监督迭代的种子。
将每个未标记的观测值通过当前树进行传递,并将预测的类别(分类)或预测值(回归)分配为暂定标签。叶节点的置信度或概率估计可用于仅选择最可靠的伪标签,过滤掉低置信度分配。
使用原始标记样本和新伪标记的未标记观测值从头开始重新训练树。高置信度伪标签与真实标签一起有助于分裂决策,从而有效地扩大了有效训练集。
修改后的分裂标准——例如在标记和未标记观测值上计算的熵或 Gini,或平衡监督纯度和无监督聚类一致性的双标准目标——指导节点分裂,以尊重未标记点揭示的底层数据分布。
迭代继续,直到暂定标签在连续轮次中稳定或达到最大迭代次数限制。然后将标准后剪枝策略(成本复杂度剪枝、最小叶节点大小)应用于最终树,以控制对伪标记数据的过拟合。
常见陷阱
- 使用所有伪标签而不考虑置信度,这会导致低质量的分配主导后续迭代。
- 在训练之前未能验证未标记数据是否来自与标记数据相同的分布。
- 将最终树的叶节点统计数据视为纯监督数据来报告性能指标——需要进行袋外(out-of-bag)或保留(held-out)标记评估。
- 在伪标签增强后跳过剪枝,导致对嘈杂的暂定标签严重过拟合。
- 将结果直接与在同一标记子集上训练的全监督树进行比较,而不考虑使用的额外未标记数据。
常见问题
半监督决策树与常规自训练分类器有何不同?
核心原理——使用未标记数据的预测来增强训练——是相同的。树特定的方法之所以与众不同,是因为它可以通过修改分裂标准本身来整合未标记的分布信息,而不仅仅是迭代地扩展标记集。
我需要多少标记样本才能开始?
没有通用的最小值,但初始监督树必须足够可靠才能产生有用的伪标签。实践中,通常建议每类至少有 20-50 个标记样本;如果样本更少,错误传播的风险很高,标签传播等替代方法可能效果更好。
我应该使用所有未标记数据还是选择一个子集?
选择高置信度的伪标签——例如叶节点概率超过 0.85 等阈值的标签——通常优于使用所有未标记点,尤其是在初始树不完美的情况下。
这会取代标准的交叉验证吗?
不。因为伪标签是从模型本身派生的,所以样本内度量会过于乐观。评估必须使用保留的标记测试集或严格应用于标记分区的 k 折交叉验证。
我能将它与集成方法结合使用吗?
可以。半监督随机森林和协同森林方法将该思想扩展到集成方法,这可以减少伪标签错误的方差,并且通常优于单个半监督树。
相关方法
参考文献
Levin, E. & Shapiro, E. (2000). Learning Decision Trees from Semi-labeled Examples. Proceedings of the ICML Workshop on Attribute-Value and Relational Learning.
打开出版物文献已复制。Zhu, X. & Goldberg, A. B. (2009). Introduction to Semi-Supervised Learning. Morgan & Claypool Publishers.
ISBN:978-1-598-29548-9已复制。