cover.jpg
引言
圈外人听到“决策树”的想法：这是什么树？难道是类似于二叉树的数据结构吗？
圈内人听到“决策树”的想法：决策树哦，机器学习常用模型，用树型结构来模拟决策过程，具有很好的模型解释型，其常用的决策树模型有：（1）ID3（2）C4.5（3）CART，巴拉巴拉。。。。（头晕了）
关于决策树算法，我打算分两篇来讲，一篇讲思想原理，另一篇直接撸码来分析算法。本篇为原理篇。
通过阅读这篇文章，你可以学到：
1、决策树的本质
2、决策树的构造过程
3、决策树的优化方向
决策树根据使用目的分为：分类树和回归树，其本质上是一样的。本文只讲分类树。
Niffler.gif
决策树的本质
决策树，根据名字来解释就是，使用树型结构来模拟决策。
用图形表示就是下面这样。
决策树长这样
其中椭圆形代表：特征或属性。长方形代表：类别结果。
面对一堆数据（含有特征和类别），决策树就是根据这些特征（椭圆形）来给数据归类（长方形）
例如，信用贷款问题，我根据《神奇动物在哪里》的剧情给银行造了个决策树模型，如下图：
麻鸡银行贷款模型
《神奇动物在哪里》的雅各布想开面包店向银行贷款，一开始银行根据该模型拒绝了他的贷款。
到最后，纽特给了他鸟蛇蛋作为抵押（其他值钱的抵押物），银行便给予了贷款。
你可以感受一下这种分类的过程。
然而，决定是否贷款可以根据很多特征，然麻鸡银行选择了：（1）是否房产价值>100w；（2）是否有其他值钱的抵押物；（3）月收入>10k；（4）是否结婚；这四个特征，来决定是否给予贷款。
先不管是否合理，但可以肯定的是，决策树做了特征选择工作，即选择出类别区分度高的特征。
对应信贷问题就是，信用贷款最重要的一点就是是否有偿还能力，麻鸡银行需要的是能明显区分申请人是否有偿还能力的特征。
由此可见，决策树其实是一种特征选择方法。（特征选择有多种，决策树属于嵌入型特征选择，以后或许会讲到，先给个图）即选择区分度高的特征子集。
分类决策树的特征选择框架
那么，从特征选择角度来看决策树，决策树就是嵌入型特征选择技术
同时，决策树也是机器学习中经典分类器算法，通过决策路径，最终能确定实例属于哪一类别。
那么，从分类器角度来看决策树，决策树就是树型结构的分类模型
从人工智能知识表示法角度来看，决策树类似于if-then的产生式表示法。
那么，从知识表示角度来看决策树，决策树就是if-then规则的集合
由上面的例子可知，麻鸡银行通过决策树模型来决定给哪些人贷款，这样决定贷款的流程就是固定的，而不由人的主观情感来决定。
那么，从使用者角度来看决策树，决策树就是规范流程的方法
最后我们再来看看决策树的本质是什么已经不重要了。
决策树好像是一种思想，而通过应用在分类任务中从而成就了“决策树算法”。
Nifflers.png
下面内容还是继续讲解用于分类的“决策树算法”。
决策树的构建过程
前面讲了决策树是一种特征选择技术。
既然决策树就是一种特征选择的方法，那么经典决策树算法其实就是使用了不同的特征选择方案。
如：
（1）ID3：使用信息增益作为特征选择
（2）C4.5：使用信息增益率作为特征选择
（3）CART：使用GINI系数作为特征选择
具体选择的方法网上一大把，在这里我提供几个链接，不细讲。
但，不仅仅如此。
决策树作为嵌入型特征选择技术结合了特征选择和分类算法，根据特征选择如何生成分类模型也是决策树的一部分。
其生成过程基本如下：
- 根据某个指标（如：信息增益的大小）来选择特征；
- 根据某个停止指标，使用自上而下或自下而上的方式构建决策树（类似上述例子中麻鸡银行决策树模型），直到满足停止指标条件，则停止构建；
- 根据某个过拟合指标对决策树进行剪枝。
根据这三个步骤，可以确定决策树由：（1）特征选择；（2）生成方法；（3）剪枝，组成。
决策树中学习算法与特征选择的关系如下图所示：
分类决策树的特征选择框架
原始特征集合T：就是包含收集到的原始数据所有的特征，例如：麻瓜银行收集到与是否具有偿还能力的所有特征，如：是否结婚、是否拥有100w的房产、是否拥有汽车、是否有小孩、月收入是否>10k等等。
中间的虚线框就是特征选择过程，例如：ID3使用信息增益、C4.5使用信息增益率、CART使用GINI系数。
其中评价指标（如：信息增益）就是对特征的要求，特征需要满足这种条件（一般是某个阈值），才能被选择，而这一选择过程嵌入在学习算法中，最终被选择的特征子集也归到学习算法中去。
这就是抽象的决策树生成过程，不论哪种算法都是将这一抽象过程的具体化。
其具体算法我将留在下一篇文章来讲解。
而决策树的剪枝，其实用得不是很多，因为很多情况下随机森林能解决决策树带来的过拟合问题，因此在这里也不讲了。
决策树的优化方向
决策树的优化主要也是围绕决策树生成过程的三个步骤来进行优化的。
树型结构，可想而知，算法效率决定于树的深度，优化这方面主要从特征选择方向上优化。
提高分类性能是最重要的优化目标，其主要也是特征选择。
面对过拟合问题，一般使用剪枝来优化，如：李国和基于决策树生成及剪枝的数据集优化及其应用。
同时，决策树有很多不足，如：多值偏向、计算效率低下、对数据空缺较为敏感等，这方面的优化也有很多，大部分也是特征选择方向，如：陈沛玲使用粗糙集进行特征降维。
由此，决策树的优化方向大多都是特征选择方向，像ID3、C4.5、CART都是基于特征选择进行优化。
end.png
参考文献
统计学习方法-李航
特征选择方法综述-李郅琴
决策树分类算法优化研究_陈沛玲
基于决策树生成及剪枝的数据集优化及其应用-李国和
网友评论