决策树总结

参考链接：https://www.cnblogs.com/yonghao/p/5061873.html

定义

树：由节点和边两种元素组成。
父节点、子节点是相对的，子节点由父节点根据某一规则分裂而来。
根节点：没有父节点的节点，初始分裂节点。
叶子节点：没有子节点的节点。

决策树： 利用树形结构进行决策，每一个非叶子节点是一个判断条件，每一个叶子节点是结论。从根节点开始，经过多次判断得出结论。

如何做决策

每次选择一个属性进行判断（如何选择？），如果不能得出结论，继续选择其他属性进行判断，知道能够肯定地判断出用户类型或者上述属性都已使用完毕。

在决策树的过程中，三个问题最为关键：

1. 如何选择属性
2. 数据如何分割
3. 终止分裂的条件是什么

1. 如何选择属性

贪婪思想：选择可以得到最有分裂结果的属性进行分裂。每一次分裂之后孩子节点的数据尽量“纯”。

信息增益
信息增益率

信息增益作为选择分裂的条件有一个不可避免的缺点：倾向选择分支比较多的属性进行分裂。（为什么？）

1）信息增益

表示分列前后的数据复杂度和分裂节点数据复杂度的变化值：

Gain表示节点复杂度，Gain越大复杂度越高。
信息增益大，分裂后复杂度减小得多，分类效果明显。

复杂度的两种计算方式：
熵和基尼指数，主要区别在于，熵达到峰值的过程要相对慢一些。因此，熵对于混乱集合的判罚要更重一些。
a）熵Entropy
取值范围：[0,1]
熵大，混乱程度高，纯度低。v.v.

pi表示第i类的数量占比。Entropy也记为H(X)。
二分类中：如果两类数量相同，纯度最低，熵为1 。如果全部数据都属于一个类，及诶单纯度最高，熵为0 。

pi<1， 由上图可知，pilog(pi)为负值，故熵为pilog(pi)的和乘以-1。

条件熵：
随机变量X在给定条件下随机变量Y的条件熵。
X给定条件下Y的条件干率分布的熵对X的数学期望，在机器学习中为选定某个特征后的熵，公式如下：

b）基尼指数 Gini Index
取值范围：[0,1]
是一种不等性度量
总体内包含的类别越杂乱，gini指数越大，数据越不纯。

pi依旧为第i类的数量占比

2) 信息增益率

使用信息增益作为选择分裂的条件倾向选择分支比较多的属性进行分裂。
为了解决这个问题，引入了信息增益率这个概念。信息增益率是在信息增益的基础上除以分裂节点数据量的信息增益。

InstrinsicInfo：分裂子节点数据量的信息增益
m：子节点数量
ni：第i个子节点的数据量
N：父节点数据量

2. 数据如何分割

离散型属性：按照属性值进行分裂，每一种属性值对应一个分裂节点。
连续性属性：按照该属性进行排序，并分为若干区间，每个区间对应一个节点。（区间大小如何选择？）

3. 终止分裂的条件

1）最小节点数
当街点数据量小于一个指定的数据量时，不继续分裂。
原因：

• 当数据量较少时，继续分裂容易强化噪声数据的作用
• 可以降低树生长的复杂性，有利于避免过拟合
  2）熵或者基尼指数小鱼阈值
  即数据纯度比较大的时候。
  3）树的深度达到指定条件
  4）所有特征使用完毕，不能继续分裂（有可能不收敛？）

4. 决策树的构建方法

分类树：输出具体的类别
回归树：输出确定的数值
构建方法主要有三种：

• ID3（分类树）
• C4.5（分类树）
• CART（回归树）

决策树的优化

1. 剪枝

预剪枝（Pre-Pruning）
后剪枝（Post-Pruning）

2. 组合树