决策树

1.决策树原理

• 树模型
  • 决策树：从根结点开始一步一步走到叶子节点（做出了决策）
  • 所有的数据最终都会落到叶子节点，即可以做分类也可以做回归
• 举个例子：
  • 五个样本数据，就是家里的5个人，进行分类，是否愿意玩电脑游戏。

  • 首先判断年龄，年龄大于15岁的就认为不会玩，走到了叶子节点上，对于小于15岁的再判断时候是男生，男生就玩，女生不玩。

    
    例子
• 树的组成：
  • 根结点：第一个选择点
  • 非叶子节点与分支：中间过程
  • 叶子节点：最终的决策结果
• 节点
  • 增加节点相当于在数据中切一刀，越多的特征，切的越多。
  • 希望数据切得细一点，那么节点越多越好吗？
• 决策树的训练与测试
  • 训练阶段：从给定的训练集构造出来一棵树（从根节点开始选择特征，如何进行特征切分）
  • 测试阶段：根据构造出来的树模型从上到下去走一遍就好了。
  • 一旦构造好了决策树，那么分类或者预测任务就很简单了，只需要走一遍就可以了，那么难点在于如何构造出来一棵树，这就没那么容易了，要考虑的问题还有很多。需要从根结点开始每一步选择什么样的特征进行分类。
• 如何切分特征（选择节点）
  • 问题：根结点的选择该用哪个特征？如何进行切分？
  • 我们的目标应该是根结点就像一个老大似的能更好的切分数据（分类的效果更好），根结点下面的节点自然就是二当家了。
  • 目标：通过一种衡量标准，来计算通过不同特征进行分支选择后的分类情况，找出来最好的那个当成根结点，以此类推。随着划分过程不断进行，我们希望决策树的分支节点所包含的样本尽可能属于统一类别。

2. 衡量标准

• 熵：
  • 定义：表示了随机变量的不确定性的度量
  • 解释：说白了就是物体内部的混乱程度。
  • 公式： 信息熵公式
    • 越大的概率，得到的熵值越少，越小的概率，熵值越大。
  • 一个例子：
    • A集合[1,1,1,1,1,1,1,1,2,2];B集合[1,2,3,4,5,6,7,8,9,1]
    • 显然A集合的熵值要低，因为A中得到类别的概率比较大。我们的目标就是通过分类，得到纯度较高的分类。
  • 熵值：不确定性越大，得到的熵值也就越大
    • 当概率值为0或1是，得到的熵值为0，随机变量完全没有不确定性
    • 当概率值为0.5时，熵值为1，此时随机变量的不确定性最大。
    • 熵值图像

如何决策一个节点的选择呢？

3. 信息增益

• 定义：表示特征X使得类Y的不确定性减少的程度。（分类后的专一性，希望分类后的结果是同类在一起。）

• 公式：a表示样本D中的属性，v代表属性a的不同取值，D^v表示不同取值组成的集合。

  
  信息增益公式
• 信息增益越大，则意味着使用属性a来进行划分所获得的“纯度提升”最大。

4. 决策树算法

1. ID3：信息增益（有什么问题呢？）
   • 在算信息增益是，有意的忽略了编号那一列，若编号也作为一个候选划分属性，每一个编号都是一个各自的叶子节点，算出熵值等于0，信息增益是最大的，选特征的时候就会选到“编号”这个特征，对于划分类别没有用。
2. C4.5：信息增益率（解决ID3问题，考虑自身熵）
   • 公式： 信息增益率公式

     其中

     
     image.png
     

     属性a的可能取值数目越多，IV(a)的值通常会越大

3. CART：使用GINI系数来当做衡量标准

• GINI系数： GINI系数
• Gini(D)反映了从数据D中随机抽取两个样本，其中类别标记不一致的概率，值越小，数据集D的纯度越高。

5. 连续值处理

1. 连续属性离散化技术处理
   • 最简单的策略是“二分法”
   • 对属性a中不同的取值进行排序，基于划分点t将数据集划分为两个子集，一个子集中的数据均小于t，另一个子集中的数据均大于t。从而来达到分类的效果。

6. 决策树剪枝策略

• 为什么要剪枝？
  • 决策树的过拟合风险很大(在训练集上表现很好，在测试集上表现很差)，理论上可以完全分得开数据。(如果树足够庞大，每个叶子节点都是一个数据了)
• 剪枝策略：预剪枝，后剪枝

1. 预剪枝

• 边建立决策树边进行剪枝的操作（更实用）
• 限制深度，叶子节点个数，叶子节点样本数，信息增益量等

2. 后剪枝

• 当建立完决策树后来进行剪枝操作

• 通过一定的衡量标准

  
  image.png
  

  （叶子节点越多，损失越大）