1 从LR到决策树

相信大家都做过用LR来进行分类，总结一下LR模型的优缺点：

优点

• 适合需要得到一个分类概率的场景。
• 实现效率较高。
• 很好处理线性特征。

缺点

• 当特征空间很大时，逻辑回归的性能不是很好。
• 不能很好地处理大量多类特征。
• 对于非线性特征，需要进行转换。

以上就是LR模型的优缺点，没错，决策树的出现就是为了解决LR模型不足的地方，这也是我们为什么要学习决策树的原因了，没有任何一个模型是万能的。

决策树（Decision Tree）
在数据挖掘领域，比较经典的分类算法有：决策树算法、贝叶斯网络算法、人工神经网络算法、支持向量机以及其它一些基于关联规则的算法等。国际权威的学术组织the IEEE International Conference on Data Mining（ICDM）曾在21世纪初期，将两种决策树算法（C4.5算法和CART算法）列入数据挖掘领域十大经典算法之中。可见决策树算法优良的结构特性和算法效率，使其得到更多专家学者的一致认可。

决策树（Decision Tree），又称判断树，它是一种以树形数据结构来展示决策规则和分类结果的模型，作为一种归纳学习算法，其重点是将看似无序、杂乱的已知实例，通过某种技术手段将它们转化成可以预测未知实例的树状模型，每一条从根结点（对最终分类结果贡献最大的属性）到叶子结点（最终分类结果）的路径都代表一条决策的规则。决策树算法的优势在于，它不仅简单易于理解，而且高效实用，构建一次，就可以多次使用，或者只对树模型进行简单的维护就可以保持其分类的准确性。

决策树

决策树算法采用自上至下递归建树的技术，该算法的产生源于CLS系统，即概念学习系统，下图展示一个CLS系统的简易模型。该模型是决策树发展的理论基础，该模型定义了一个学习系统的基本结构。

CLS系统的简易模型

J.R.Quinlan在上世纪80年代提出了ID3（Iterative Dichotomiser 3）算法，该算法奠定了日后决策树算法发展的基础。这种算法的提出得益于，香农（Shannon C E.）在信息论中提出的信息熵的概念，其表示离散随机事件出现的概率。ID3算法最核心的思想，就是以信息增益作为分裂属性选取的依据，信息增益表示某个属性能够为分类系统带来多少“信息”，信息越多，则通过该属性对数据集的分类更为准确。ID3算法适用于大多数据集的分类问题，分类速度和测试速度都比较快。但该算法在设计之初未考虑如何处理连续属性、属性缺失以及噪声等问题。之后，随后J.R.Quinlan针对ID3算法的不足设计了C4.5算法，引入信息增益率的概念。它克服了ID3算法无法处理属性缺失和连续属性的问题，并且引入了优化决策树的剪枝方法，使算法更高效，适用性更强。

Breiman.L.I等人在1984年提出了CART（Classification and Regression Tree）算法，即分类回归树算法。CART算法用基尼指数（Gini Index）代替了信息熵，用二叉树作为模型结构，所以不是直接通过属性值进行数据划分，该算法要在所有属性中找出最佳的二元划分。CART算法通过递归操作不断地对决策属性进行划分，同时利用验证数据对树模型进行优化。

1996年Shafer.J.C等人提出了一种可伸缩的并行归纳决策树算法，SPRINT算法（Scalable Parallelizable Induction of Decision Trees），通过并行运算增加决策效率，增强了算法的的扩展性和可伸缩性。同一年Mehta.M等人提出了C4.5算法的改进算法SLIQ算法，该算法采用属性表、分类表、类直方图的策略来解决内存溢出的问题。Cehrke.J等人设计了雨林（Rain Forest）算法，提高了对大数据集进行分类的能力。2000年Rastogi.R等人以CART算法为理论基础，提出了PUBLIC（A Decision Tree Classifier that Integrates Building and Pruning）算法，剪枝策略更加高效。

当今社会，信息化得程度日益提高，人们被各种数据所包围。数据挖掘作为一种新兴的学术领域，它的发展极大的促进了人们对海量数据中所蕴含的知识的认识程度。数据挖掘最根本的目的就是，通过各种有效的技术手段，在已知的数据中探寻有价值的信息。决策树分类算法，作为一种简单高效、容易理解的启发式算法，有着广泛的应用领域。近年来随着模糊理论与决策树的融合，使得该算法更为智能，更符合人的思维方式，极大的扩展了其应用范围。

决策树的优点

• 模拟人的直观决策规则。
• 可以处理非线性特征。
• 考虑了特征之间的相互作用。

其实用一下图片能更好的理解LR模型和决策树模型算法的根本区别，我们可以思考一下一个决策问题：是否去相亲，一个女孩的母亲要给这个女海介绍对象。

大家都看得很明白了吧！LR模型是一股脑儿的把所有特征塞入学习，而决策树更像是编程语言中的if-else一样，去做条件判断，这就是根本性的区别。

2 “树”的成长过程

决策树基于“树”结构进行决策的，这时我们就要面临两个问题 ：

• “树”怎么长。
• 这颗“树”长到什么时候停。

弄懂了这两个问题，那么这个模型就已经建立起来了，决策树的总体流程是“分而治之”的思想，一是自根至叶的递归过程，一是在每个中间节点寻找一个“划分”属性，相当于就是一个特征属性了。接下来我们来逐个解决以上两个问题。

这颗“树”长到什么时候停

• 当前结点包含的样本全属于同一类别，无需划分；例如：样本当中都是决定去相亲的，属于同一类别，就是不管特征如何改变都不会影响结果，这种就不需要划分了。
• 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分；例如：所有的样本特征都是一样的，就造成无法划分了，训练集太单一。
• 当前结点包含的样本集合为空，不能划分。

3 “树”怎么长

在生活当中，我们都会碰到很多需要做出决策的地方，例如：吃饭地点、数码产品购买、旅游地区等，你会发现在这些选择当中都是依赖于大部分人做出的选择，也就是跟随大众的选择。其实在决策树当中也是一样的，当大部分的样本都是同一类的时候，那么就已经做出了决策。

我们可以把大众的选择抽象化，这就引入了一个概念就是纯度，想想也是如此，大众选择就意味着纯度越高。好，在深入一点，就涉及到一句话：信息熵越低，纯度越高。我相信大家或多或少都听说过“熵”这个概念，信息熵通俗来说就是用来度量包含的“信息量”，如果样本的属性都是一样的，就会让人觉得这包含的信息很单一，没有差异化，相反样本的属性都不一样，那么包含的信息量就很多了。

一到这里就头疼了，因为马上要引入信息熵的公式，其实也很简单：

Pk表示的是：当前样本集合D中第k类样本所占的比例为Pk。

信息增益
废话不多说直接上公式：

看不懂的先不管，简单一句话就是：划分前的信息熵--划分后的信息熵。表示的是向纯度方向迈出的“步长”。

3.1 ID3算法

解释：在根节点处计算信息熵，然后根据属性依次划分并计算其节点的信息熵，用根节点信息熵--属性节点的信息熵=信息增益，根据信息增益进行降序排列，排在前面的就是第一个划分属性，其后依次类推，这就得到了决策树的形状，也就是怎么“长”了。

不过，信息增益有一个问题：对可取值数目较多的属性有所偏好，例如：考虑将“编号”作为一个属性。这就引出了另一个 算法C4.5。

3.2 C4.5

为了解决信息增益的问题，引入一个信息增益率：

属性a的可能取值数目越多(即V越大)，则IV(a)的值通常就越大。信息增益比本质： 是在信息增益的基础之上乘上一个惩罚参数。特征个数较多时，惩罚参数较小；特征个数较少时，惩罚参数较大。不过有一个缺点：

缺点：信息增益比偏向取值较少的特征。
使用信息增益比：基于以上缺点，并不是直接选择信息增益率最大的特征，而是现在候选特征中找出信息增益高于平均水平的特征，然后在这些特征中再选择信息增益率最高的特征。

3.3 CART算法

数学家真实聪明，想到了另外一个表示纯度的方法，叫做基尼指数(讨厌的公式)：

表示在样本集合中一个随机选中的样本被分错的概率。举例来说，现在一个袋子里有3种颜色的球若干个，伸手进去掏出2个球，颜色不一样的概率，这下明白了吧。Gini(D)越小，数据集D的纯度越高。

举个例子
假设现在有特征 “学历”，此特征有三个特征取值： “本科”，“硕士”， “博士”，
当使用“学历”这个特征对样本集合D进行划分时，划分值分别有三个，因而有三种划分的可能集合，划分后的子集如下：
1.划分点： “本科”，划分后的子集合 ： {本科}，{硕士，博士}
2.划分点： “硕士”，划分后的子集合 ： {硕士}，{本科，博士}
3.划分点： “硕士”，划分后的子集合 ： {博士}，{本科，硕士}}
对于上述的每一种划分，都可以计算出基于 划分特征= 某个特征值 将样本集合D划分为两个子集的纯度：

因而对于一个具有多个取值（超过2个）的特征，需要计算以每一个取值作为划分点，对样本D划分之后子集的纯度Gini(D,Ai)，(其中Ai 表示特征A的可能取值)

然后从所有的可能划分的Gini(D,Ai)中找出Gini指数最小的划分，这个划分的划分点，便是使用特征A对样本集合D进行划分的最佳划分点。到此就可以长成一棵“大树”了。

3.4 三种不同的决策树

• ID3：取值多的属性，更容易使数据更纯，其信息增益更大。
  训练得到的是一棵庞大且深度浅的树：不合理。
• C4.5：采用信息增益率替代信息增益。
• CART：以基尼系数替代熵，最小化不纯度，而不是最大化信息增益。