机器学习之决策树
决策树是一个有监督分类与回归算法。
决策树的生成只考虑局部最优，相对的，决策树剪枝则考虑全局最优
1 树模型
分类决策树模型是一种描述对实例进行分类的树形结构。结点有两种类型，内部结点表示一个特征或属性，叶结点表示一个类。 用决策树分类，从根结点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到其子节点；这时，每一个子结点对应着该特征的一个取值，如此递归下去，直到到达叶子结点。最后将实例分到叶结点的类中。
如下图：
2 划分依据
① 熵
物理学上，熵 Entropy 是“混乱” 程度的量度。
系统越有序，熵值越低；系统越混乱或者分散，熵值越高.
② 熵计算公式
其中pi表示分类选择的概率，log2pi为信息定义
③ 特征选择(信息增益)
1、以某特征划分数据集前后的熵的差值。熵可以表示样本集合的不确定性，熵越大，样本的不确定性就越大。因此可以使用划分前后集合熵的差值来衡量使用当前特征对于样本集合D划分效果的好坏
计算方法如下:
1 |
|
3 决策树构建
构建决策树就要基于划分依据，进行划分数据信息增益的计算，选择信息增益最大的来进行划分数据，直到求到叶子节点，实现数据集的划分
例子:
分类数据如下
- 不划分，计算原始的熵
- 如果划分的话第一步，先假设按照outlook这一标准划分，结果如下：
- 分别计算这三种类别的熵，然后计算三种类别的总熵(概率和熵值得乘积之和)
- 计算信息增益，IG(outlook)=0.940−0.694=0.246
- 分别计算另外两种划分的信息增益率，然后构建第一层决策树
- 接着在每一种类别下再进行划分，直到每个节点下只有一个分类，即叶子节点，如下图
4 代码示例
略
5 参考文章
1 | https://blog.csdn.net/sinat_30353259/article/details/80917362 |