决策树–强烈推荐南京大学周志华教授

  • 什么时候停止分类？

      1. 每一类的内容十分相近
      • 或者类为空
      • if not beat_feature 就是分类器找不到最好的分类特征
      1. 属性集空了
      • 也就是所有能分类的都问过了
      • if depth == self.max_depth or len(set(y)) == 1: 就是决策树到了最大深度或者属性值为 1 个

    • 信息增益 information gain

      • 信息熵 Ent⁡(D)=−Σpklog⁡2pk\operatorname{Ent}(D) = -\Sigma p_k \log_2p_k

        • 信息熵越小， DD 的纯度越高
        • 信息熵可以定性理解为 “需要多少信息才能将其区分开”

      • 增益函数 Gain(D,a)=Ent⁡(D)−Σ∣Dv∣∣D∣Ent⁡(Dv)Gain(D,a)=\operatorname{Ent}(D) - \Sigma\frac{|D^v|}{|D|}\operatorname{Ent}(D^v)

        • Ent⁡(D)\operatorname{Ent}(D) 表示的是划分之前的信息熵
        • Σ∣Dv∣∣D∣Ent⁡(Dv)\Sigma\frac{|D^v|}{|D|}\operatorname{Ent}(D^v) 表示的是划分之后的信息量，vv 表示不同的种类，这一项表示比例乘以新的信息熵
        • 整体表示多加了的一层所能带来的信息熵减小值

    • 分类之后样本量过小，比如我们按照邮箱地址分类，每一类就只有一个人了，效果反而不好了

      • 所以我们需要新的一个描述信息分类效果的算法

      • 增益率 Gain Ratio

        • Gain_ratio(D,a)=Gain(D,a)IV(a)Gain\_ratio (D,a) = \frac{Gain(D,a)}{IV(a)}
        • IV(a)=−Σ∣Dv∣∣D∣log⁡2∣Dv∣∣D∣IV(a) = -\Sigma\frac{|D^v|}{|D|}\log_2\frac{|D^v|}{|D|}
        • aa 的可能取值的数目越多，IV(a)IV(a) 越大

    • 基尼系数 Gini Index

      • Gini(D)=ΣΣpkpk′=1−Σpk2Gini(D) = \Sigma\Sigma p_kp_{k'} = 1-\Sigma p_k^2 用于表示两次第一次抽到另一次抽不到的概率

        • 基尼系数越大，表示数据分类越不纯净

      • 属性 aa 的基尼系数 Gini_index(D,a)=Σ∣Dv∣∣D∣Gini(Dv)Gini\_index(D,a) = \Sigma\frac{|D^v|}{|D|}Gini(D^v)

        • 需要用概率进行加权处理，这样就可以不同种类之间相互比较了

  • 划分选择 vs. 剪枝

    • 剪枝定义pruning：在树结构中去掉部分的节点及其子节点

    • 剪枝目标：防止训练数据的过拟合

      • 我们和机器学习斗争的对象是过拟合 --周志华
      • 实际上就是随机少学了对象的一些特征

    • 分类

      • 预剪枝 pre-pruning: 提前种植某些分支的生长
      • 后剪枝 post-pruning: 生成一棵树之后再返回去剪枝

    • 预剪枝举例：我们现在有关于西瓜的是否为好瓜的几个相关性质的7例数据，3好4坏

      • 直接理解我们有 37\frac 3 7 的好瓜猜测率
      • 如果告知性质 A 的属性和其对应的正确性，我们可以获得新的正确率 p1p_1
      • 再告知 B 属性和对应正确性，获得新新正确率 p2p_2
      • 如果发现 某节点的子节点正确率低于其本身正确率p2<p1p_2<p_1 则停止生成，即剪枝

    • 后剪枝举例：先生成完整的决策树，我们从最深层开始向根节点分析(越深越有可能是过拟合的)

      • 最初对比对象是不生成决策树的情况下的正确概率 即 true casesall cases\frac{true\ cases}{all\ cases}
      • 某个最小枝节点下若正确概率大于错误概率，则令其枝节点变为正确概率的叶节点，vice versa
      • 对比剪枝前后概率变化，正确率提升则剪枝
      • 子结点不适合剪枝不代表父节点不适合剪枝

    • 如果剪枝/生成枝前后概率不变，那么依照结构简单原则

    • 对比预剪枝和后剪枝

      • 时间开销：

        • 预剪枝：使用时间低，训练时间低
        • 后剪枝：使用时间低，训练时间高

      • 拟合问题：

        • 预剪枝：过拟合风险降低，欠拟合风险增加

          • 树的生长是贪心算法模型，局部最优不一定是全局最优，我们剪枝是去掉了局部不优秀

        • 后剪枝：过拟合风险降低，欠拟合风险不变

        • 性能问题首先考虑后剪枝

  • 缺失值 Missing

    • 定义：我们默认数据是全的，即每个属性其对应的对象都有值

      • 问题：如果维数高，每个样本多半会有几个维度没有值，所以不能直接舍弃

    • 思路：样本赋权，权重划分

    • 首先要定量计算没有值的维度的信息增益

      • 对于属性 A 只用有内容的部分计算信息熵 Ent(DˉA)Ent(\bar D_A)

      • 划分后信息熵：ΣrˉAEnt(DˉA)\Sigma \bar r_A Ent(\bar D_A)

        • 无缺失值样例中属性 A 的取值占比
        • 以上得到的只考虑了有信息的部分，需要乘以一个权重

      • 权重：首先给每个样例一样的权重 1

        • 对已知的部分按照 ∣Dv∣∣D∣\frac{|D_v|}{|D|} 获得权重（D不包含未知）
        • 未知量按照概率权重同时进入几个分布