研究生课程：现代信息检索-第13讲 决策树与面向文档的机器学习

《现代信息检索》课程笔记：第13讲 决策树与面向文档的机器学习

第13讲 决策树与面向文档的机器学习

面向文本分类的决策树

• 树结构：内部节点由词项作为标记
• 分支标记：词项权重的“测试” (test)，或仅仅是出现/不出现
• 叶节点标记：类别
• 分类器
  • 分类器通过“测试”后的降序树对文档进行分类
  • 然后将叶节点的标签分配给文档
• 大多数决策树都是二叉树

决策树的学习

学习一个序列的特征测试，典型的做法是由上到下的贪心搜索，每一步选择具有最高信息收益的未使用特征

叶节点标记：yes/no 类别标记，或连续值

如果有个特征，决策树的节点数量上限是（太大了，会有计算开支等方面的问题）

我们可以通过在每个节点上递归选择最佳拆分特征，以贪心的方式创建树

属性选择基本思想：（理想情况下）一个好的特征能够把所有样本划分成“全部正样本”和“全部负样本”两个子集

利用信息论：

信息熵（Entropy）：考虑每个节点的类分解

信息增益

对每个节点，我们选择使信息增益最大的特征f

数值特征 (例如tf-idf)：通常使用二元的切分 (f < t), t怎样确定?

穷尽式（搜索）：评估观察值之间的每个分割点的信息增益。

• 慢；通过优化计数方法可以稍微提高效率

分箱（Discretize into bins）

• 将所有的数值切分到k个箱中
• （连续的数值）特征被离散化
• 分箱操作可以基于整个语料集的统计

（树的构建）什么时候停止?

• 当一个节点的所有样本都属于同一个类别
• 当树的深度d达到一个固定阈值
• 如果没有合适的属性可以拆分中区分具有统计意义的类（例如，使用卡方检验或Fisher精确检验），则停止构建。
• 最常用/最佳方法：使用单独的验证数据
  • 构建一个较大的树（可以给树的深度设定阈值）
  • 自下而上的修剪未能（显著）改善验证数据分类性能的节点

面向文本的决策树学习

宏平均：计算每个类别的性能指标，然后取平均值

微平均：收集所有类别的决策（分类）结果，计算列联表，评价

判别式 (discriminative) 分类方法: Logistic Regression (逻辑回归) 与 Support vector machines (支持向量机)

Ensemble 方法

随机森林 （Random Forests）

从原始数据集重复采样（bootstrap采样），在采样数据上构建K个树，p=特征数量

• 获得K个大小为N的bootstrap采样，其中N是原始数据集大小
• 通过在每个节点的p个特征中随机选择m个，并选择最佳特征来扩展每个决策树。
• m的典型取值： sqrt(p)
• 预测(Runtime)：汇总树的预测（最受欢迎的投票）以产生最终分类

原则：我们希望在不同的学习器(learner)之间进行投票，因此我们不希望这些模型过于相似。这两个标准确保了各个树的多样性

优点：

• 在实践中非常流行，有段时间是密集数据（dense data）上最流行的分类器（<=几千个特征）
• 容易实现 (训练多个树).
• 容易并行化 (但并不意味着效率高)。适合用于 MapReduce.

缺点：

• 现在和一些新方法相比准确度并不高 – Gradient-boosted trees (特征少) 与 深度神经网络(视觉, 语音, 语言, …)通常更好
• 需要多次遍历数据 – 至少是树的最大深度 (虽然远小于boosted trees )
• 容易过拟合 – 需要权衡准确度（accuracy）与拟合度（fit）

Boosted Decision Trees (BDT, 增强决策树)

• 一个比随机森林（RF）提出更晚的算法
• 与独立训练树的RF不同，BDT的树通过增强(boosting)的方式依次(sequetially)训练树：
  • 每个树都在加权数据上训练，通过加权强调之前（训练）
    的树错误标记的样本
• 这两个方法都能够通过训练产生高质量模型
• 但是BDT通常都更适用于中等数量特征的数据集

随机森林（RF） vs 增强树（BDT）