0x00 决策树

决策树在机器学习中是一种经典的分类算法。决策树的结构是一个树结构(可以是二叉树或非二叉树)。其中每个非叶节点表示一个特征属性上的测试，每个分支代表这个特证属性在某个值域上的输出，而每个叶子节点存放一个类别。使用决策树进行决策的过程就是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，此时叶子节点上的类别就是决策结果。

举个例子，假如我们要判断一只动物是不是兔子，这是典型的二分类问题，结果只有是兔子和不是兔子两种。我们可以用来判断的特征有：四条腿走路、耳朵、体型、尾巴等很多信息，这些特征都位于非叶节点，我们输入一个新的动物，就可以通过这些特征来一步步走向分类的叶子节点。

0x01 决策树过程描述

具体过程如下图

最重要的问题在于第八行中如何选择这个最优属性，什么是最优属性呢？就是说这个属性要做到尽量多的降低不确定性，为了找出算哪个属性才能降低最多不确定性，就需要引入信息熵的概念了。

0x02 信息熵与信息增益

信息

在看信息熵之前我们先看一下香农对信息的定义：信息是用来消除随机不确定性的东西。

信息的衡量-信息熵

信息熵指一个信息能够消除不确定性的大小

信息熵的定义式：

条件熵计算：

信息增益

特征A对训练数据集D的信息增益g(D,A)，定义为集合D的信息熵H(D)与特征A给定条件下D的信息条件熵H(D|A)之差，公式为：

随着决策树的每层进行，我们希望决策树分支节点所包含的样本尽可能的属于同一类别，也就是说“纯度”越来越高，而信息增益越大，意味着使用这个属性对决策树的“纯度”提升越大。

所以，我们根据这里计算出来的信息增益的大小，就可以解决选择最优属性的问题。

0x03 剪枝处理

剪枝是决策树中应对过拟合的手段，在决策树学习中由于划分过程不断重复，有时会造成决策树分支过多，这种情况下一些训练集的特点会被当作所有数据都具有的一般性质而导致过拟合。需要进行剪枝处理。

决策树的剪枝策略分为预剪枝和后剪枝。

• 预剪枝是指在决策树的生成过程中，对每个节点在划分前先进行估计。若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶子结点。
• 后剪枝是从训练集生成一颗完整的决策树，然后自底向上对非叶结点进行考察，如果将该结点替换成叶结点会提升泛化性能，则替换。

0x04 连续值处理

实际情况中，我们遇到的属性并不一定都是像“有无尾巴”等这样离散的，有一部分属性是连续的数值如“质量”、“密度”等等。这种情况下由于连续值是无限多的，不能分别作为结点，所以就要采取一定的策略对连续属性进行处理。

最常用的策略是二分法，首先我们假设在样本D中有n个不同的取值，将他们从小到大进行排序，记为{a1、a2、···an}，然后取每两个相邻点的平均值

共n-1个值作为候选划分点，然后用考察离散属性值的方法来选取最优划分点来进行集合的划分。