决策树学习笔记
介绍
决策树（Decision Tree）是广泛用于分类（Classification）和回归（Regression）任务的模型。 本质上，它从一层层的if/else问题中进行学习、并得出结论。 决策树的原理，就像一个问答游戏：参与游戏的一方在脑海里想某个事物， 其他参与者向他提问题，只允许提20个问题，问题的答案也只能用对或错回答。问问题的人通过推断分解，逐步缩小待猜测的事物的范围。
在使用决策树之前，需要先训练（构建）出决策树的模型。 构建决策树（离线训练） ===》 使用决策树分类（在线计算）。
近年来调查表明，决策树是最经常使用的数据挖掘算法。 决策树的原理简单易懂，不需要太多机器学习的基础，也能理解其基础原理。 机器学习中树模型相关算法包括：决策树/DT（Decision Tree）、分类回归树/CART（Classification And Regression Tree）、随机森林（Random Forest）、Boosting方法。虽有共性、本文篇幅仅侧重于基础的决策树。
设计决策树的一般流程
- 收集数据
- 准备数据：树构造算法只适用于标称型数据（scale型），因此数值型数据必须离散化。
- 分析数据
- 训练数据：构造决策树的数据结构。
- 测试算法：使用测试集计算错误率。
- 使用算法
构建树
在构建决策树时，我们需要解决的第一个问题就是，当前数据集上哪个特征在划分数据分类时起决定性作用。为了找到决定性的特征，划分出最好的结果，我们必须评估每个特征。
如此，递归地划分、分类，就可以组成一棵决策树啦～
递归构建决策树的伪代码
func CreateBranch(setA):
If setA 中的每个子项属于同以分类:
return 类标签
Else:
寻找划分数据集的最好特征
划分数据集，得setSub
创建分支节点
for 每个划分的子集
CreateBranch(setSub)
return 分支节点
构建算法：
- 二分法
- ID3
- C4.5
划分数据的准则
划分数据集的基本原则是：将无序的数据变得更加有序。
衡量信息无序程度的算法有两种：
- 信息熵（entropy）（衡量信息混杂程度）
- 基尼不纯度（gini impurity）（简单来说，是从一个数据集中随机抽取子项，度量其被错误分类到其他分组里的概率）
熵（entropy）
熵定义为信息的不纯度。 熵值越高，表示信息越混杂。
信息增益（information gain）
信息发生的变化称为信息增益，数值上等于熵的减少量。
通过计算信息增益，我们就可以计算每个特征值划分后子数据集获得信息增益，通过比较信息增益，就可以判断哪个是当前最好的选择。
PS:笔者仅对信息熵有个粗浅的了解，望各位读者海涵。
决策树中的信息熵与信息增益
ID3
对于树中的每一个节点，算法会选择其中一个使得样本分离出来的子集能够成为一个单独分类的最有效的属性/特征。判断属性有多有效的标准，就是信息增益、信息熵的差异。
使用数据类型：无法直接处理数值型数据（numeric），一般用作处理标称型数据（scaled）。
ID3算法学习笔记
C4.5
由ID3改进而来。
剪枝
为了降低过拟合，对一颗完全长成树逐步剪支的过程。
- 如果拆分后子分区国小，或末端叶子的规模过小，就停止拆分。
- 如果新分区并未使不纯度“显著”地降低，就放弃拆分该分区。
上述两种方法都需要调参，通过交叉校验的方法可确定的误差最小的参数。
总结
构造决策树是很耗时的任务，即使处理很小的数据集，也要花费不少的时间。然而用构建好的决策树来解决分类问题时，则可以很快完成！ 我们首先测量集合中数据的不一致性，也就是熵，然后寻找最优方案划分数据集，指导数据集中的所有数据属于同一分类。 我们可以通过裁剪决策书，合并相邻的无法产生大量信息增益的叶节点，消除过拟化问题。
优点
- 计算复杂度不高
- 输出结果易于理解
- 对中间值的缺失不敏感
- 可以处理不相关特征数据
缺点
- 可能会产生过度匹配问题（过拟化，需要剪枝来解决）
相关源码
参考
- 《机器学习实战》
- 《Python机器学习基础教程》
- 《面向数据科学家的实用统计学》
- WIKI-Decision Tree Learning
- WIKI-ID3