决策树是什么玩意
决策树是广泛用于分类和回归任务的模型。本质上，它从一层层的 if/else 问题中进行学习，并得出结论。
这些问题类似于你在“20 Questions”游戏 9 中可能会问的问题。想象一下，你想要区分下面这四种动物：熊、鹰、企鹅和海豚。你的目标是通过提出尽可能少的 if/else 问题来得到正确答案。你可能首先会问：这种动物有没有羽毛，这个问题会将可能的动物减少到只有两种。如果答案是“有”，你可以问下一个问题，帮你区分鹰和企鹅。例如，你可以问这种动物会不会飞。如果这种动物没有羽毛，那么可能是海豚或熊，所以你需要问一个问题来区分这两种动物——比如问这种动物有没有鳍。这一系列问题可以表示为一棵决策树
animal.png
在这张图中，树的每个结点代表一个问题或一个包含答案的终结点（也叫叶结点）。树的边将问题的答案与将问的下一个问题连接起来。用机器学习的语言来说就是，为了区分四类动物（鹰、企鹅、海豚和熊），我们利用三个特征（“有没有羽毛”“会不会飞”和“有没有鳍”）来构建一个模型。我们可以利用监督学习从数据中学习模型，而无需人为构建模型
决策树核心
分类决策树的核心思想就是在一个数据集中找到一个最优特征，然后从这个特征的选值中找一个最优候选值(这段话稍后解释)，根据这个最优候选值将数据集分为两个子数据集，然后递归上述操作，直到满足指定条件为止。
上述这段话是我对分类决策树的一个简单概述，里面有几个需要注意的点：
-
最优特征怎么找？这个问题其实就是决策树的一个核心问题了。我们常用的方法是更具信息增益或者信息增益率来寻找最优特征，信息增益这东西怎么理解呢！搞清这个概念我们首先需要明白熵这个东西！熵简单的讲就是说我们做一件事需要的代价，代价越高肯定就越不好了。放到机器学习的数据集中来讲就是我们数据的不确定性，代价越高对应的不确定就越高，我们用决策树算法的目的就是利用数据的一些规则来尽可能的降低数据集的不确定性。好了，有了这个思想我们要做的事就很简单了，给定一批数据集，我们可以很容易得到它的不确定性(熵)，然后呢！我们要想办法降低这个不确定性，我们需要挖掘数据集中有用的特征，在某个特征的限制下，我们又能得到数据集的不确定性（这个其实就是书上的条件熵），一般而言给定了一个有用的特征，数据的不确定性肯定降低了(因为有一个条件约束，比没有条件约束效果肯定会好一点，当然你的特征没有用，那就另说了)。我们用两次的值作差，这个结果的含义很明了，给定了这个特征，让我们数据集的不确定性降低了多少，当然降低的越多这个特征肯定就越好了。而我们讲了这么多就是要找到那一个让数据集不确定性降低最多的特征。我们认为这个特征是当前特征中最好的一个。
-
我们找到了最优特征，为什么还要找最优特征的最优候选值？其实呀，找不找主要看我们面对的问题，一般的二分类问题确实没必要找(因为总共就两个类)，但对于多分类问题，这个还是建议找，为什么要找呢？我们来分析一下：假如我们的某个最优特征有三个类别：我们如果不找就直接分为三个子节点了。这样会出现一个问题，就是我们的这个分类对特征值会变得敏感，为什么这么说，我们来讲一个很简答的例子：我们平时考试规定了60分及格，这个控制对于大多数学生很好把控，因为就一个条件，相当于一个二分类。但是如果我们把条件控制严格一些，比如超过60分，不超过80分为优秀学生(当然有点扯蛋了)。这个控制很多学霸就不好控制了，对于多分类问题也是这个道理，如果我们一下子从父节点直接分了多个子节点，那么我们的数据肯定会对这个控制很敏感，敏感就会导致出错。出错不是我们希望看到的，所以我们建议对多分类问题找最优候选值来转化为二分类问题，同样多个二分类问题其实也是一个多分类问题，只是多了几个递归过程而已。
-
什么时候停止？停止条件是什么？这个问题其实书上也讲得很简单，基本都是一笔带过的，我来稍微详细说一下：我们从问题的根源出发去想一下，我们构造一颗决策树的目的是什么？当然是为了能在数据集上取得最好的分类效果，很好这就是一个停止标准呀！当我们检测到数据的分类效果已经够好了，我们其实就可以停止了。当然我们常用的是控制叶节点，比如控制叶节点的样本数目，比如当某个子节点内样本数目小于某一个指定值，我们就决定不再分了。还有叶节点的纯度，我们规定叶节点样本必须属于同一类才停止，这也是一个停止条件。还有最大树的深度，比如我们规定树的最大深度为某一个值，当树深度到达这个值我们也要停止。还有比如：分裂次数，最大特征数等等。总之停止条件不是死的，我们可以更具自己的问题来随意控制，开心就好
决策树构建
构建
那么问题就来了，如何构建决策树,决策树的构建是数据逐步分裂的过程，构建的步骤如下:
步骤 1：将所有的数据看成是一个节点，进入步骤 2；
步骤 2：从所有的数据特征中挑选一个数据特征对节点进行分割，进入步骤 3；
步骤 3：生成若干孩子节点，对每一个孩子节点进行判断，如果满足停止分裂的条件，进入步骤 4；否则，进入步骤 2；
步骤 4：设置该节点是子节点，其输出的结果为该节点数量占比最大的类别。
从上述步骤可以看出，决策生成过程中有两个重要的问题：
-
数据如何分割
-
如何选择分裂的属性
-
什么时候停止分裂
数据分割
假如我们已经选择了一个分裂的属性，那怎样对数据进行分裂呢？
分裂属性的数据类型分为离散型和连续性两种情况，对于离散型的数据，按照属性值进行分裂，每个属性值对应一个分裂节点；对于连续性属性，一般性的做法是对数据按照该属性进行排序，再将数据分成若干区间，如 [0,10]、[10,20]、[20,30]…，一个区间对应一个节点，若数据的属性值落入某一区间则该数据就属于其对应的节点。
例如：
| 职业 | 年龄 | 是否贷款 |
|---|---|---|
| 白领 | 30 | 否 |
| 工人 | 40 | 否 |
| 工人 | 20 | 否 |
| 学生 | 15 | 否 |
| 学生 | 18 | 是 |
| 白领 | 42 | 是 |
属性1“职业”是离散型变量，有三个取值，分别为白领、工人和学生，根据三个取值对原始的数据进行分割，如下表所示
| 值 | 贷款 | 不贷款 |
|---|---|---|
| 白领 | 1 | 1 |
| 工人 | 0 | 2 |
| 学生 | 1 | 1 |
以表示成如下的决策树结构：
（2）属性 2 是连续性变量，这里将数据分成三个区间，分别是 [10，20]、[20,30]、[30,40]，则每一个区间的分裂结果如下：
可以表示成如下的决策树结构：
image
属性2是连续性变量，这里将数据分成三个区间，分别是[10，20]、[20,30]、[30,40]，则每一个区间的分裂结果如下：
| 区间 | 贷款 | 不贷款 |
|---|---|---|
| [0,20] | 1 | 2 |
| (20,40] | 0 | 2 |
| (40-] | 1 | 0 |
可以表示成如下的决策树结构
3.2 分裂属性的选择
我们知道了分裂属性是如何对数据进行分割的，那么我们怎样选择分裂的属性呢？
决策树采用贪婪思想进行分裂，即选择可以得到最优分裂结果的属性进行分裂。那么怎样才算是最优的分裂结果？最理想的情况当然是能找到一个属性刚好能够将不同类别分开，但是大多数情况下分裂很难一步到位，我们希望每一次分裂之后孩子节点的数据尽量” 纯”，以下图为例：
image
从图 3.1 和图 3.2 可以明显看出，属性 2 分裂后的孩子节点比属性 1 分裂后的孩子节点更纯：属性 1 分裂后每个节点的两类的数量还是相同，跟根节点的分类结果相比完全没有提高；按照属性 2 分裂后每个节点各类的数量相差比较大，可以很大概率认为第一个孩子节点的输出结果为类 1，第 2 个孩子节点的输出结果为 2。选择分裂属性是要找出能够使所有孩子节点数据最纯的属性，决策树使用信息增益或者信息增益率作为选择属性的依据。
- 信息增益
用信息增益表示分裂前后跟的数据复杂度和分裂节点数据复杂度的变化值，计算公式表示为：
image
其中 Gain 表示节点的复杂度，Gain 越高，说明复杂度越高。信息增益说白了就是分裂前的数据复杂度减去孩子节点的数据复杂度的和，信息增益越大，分裂后的复杂度减小得越多，分类的效果越明显。
节点的复杂度可以用以下两种不同的计算方式：
- 熵
image
其中 Pi 表示类 i 的数量占比。以二分类问题为例，如果两类的数量相同，此时分类节点的纯度最低，熵等于 1；如果节点的数据属于同一类时，此时节点的纯度最高，熵 等于 0。
3. 基尼值
基尼值计算公式如下：
image
其中 Pi 表示类 i 的数量占比。其同样以上述熵的二分类例子为例，当两类数量相等时，基尼值等于 0.5 ；当节点数据属于同一类时，基尼值等于 0 。基尼值越大，数据越不纯。
例:以熵作为节点复杂度的统计量，分别求出下面例子的信息增益，图 3.1 表示节点选择属性 1 进行分裂的结果，图 3.2 表示节点选择属性 2 进行分裂的结果，通过计算两个属性分裂后的信息增益，选择最优的分裂属性。
image
属性 1：
image
属性 2：
image
由于 [图片上传失败...(image-476dba-1544716762883)]，所以属性 1 与属性 2 相比是更优的分裂属性，故选择属性 1 作为分裂的属性。
- 信息增益率
使用信息增益作为选择分裂的条件有一个不可避免的缺点：倾向选择分支比较多的属性进行分裂。为了解决这个问题，引入了信息增益率这个概念。信息增益率是在信息增益的基础上除以分裂节点数据量的信息增益（听起来很拗口），其计算公式如下：
image
image
表示信息增益，
image
表示分裂子节点数据量的信息增益，其计算公式为：
image
image
表示第 i 个子节点的数据量，N 表示父节点数据量，说白了， 其实[图片上传失败...(image-52cf7b-1544716762883)]是分裂节点的熵，如果节点的数据链越接近，[图片上传失败...(image-c650a8-1544716762883)]越大，如果子节点越大，[图片上传失败...(image-796aa-1544716762883)]越大，而
image
就会越小，能够降低节点分裂时选择子节点多的分裂属性的倾向性。信息增益率越高，说明分裂的效果越好。
还是信息增益中提及的例子为例：
image
属性 1 的信息增益率：
属性 2 的信息增益率：
image
由于
image
，故选择属性 2 作为分裂的属性。
3 停止分裂的条件
决策树不可能不限制地生长，总有停止分裂的时候，最极端的情况是当节点分裂到只剩下一个数据点时自动结束分裂，但这种情况下树过于复杂，而且预测的经度不高。一般情况下为了降低决策树复杂度和提高预测的经度，会适当提前终止节点的分裂。
以下是决策树节点停止分裂的一般性条件：
（1）最小节点数
当节点的数据量小于一个指定的数量时，不继续分裂。两个原因：一是数据量较少时，再做分裂容易强化噪声数据的作用；二是降低树生长的复杂性。提前结束分裂一定程度上有利于降低过拟合的影响。
（2）熵或者基尼值小于阀值。
由上述可知，熵和基尼值的大小表示数据的复杂程度，当熵或者基尼值过小时，表示数据的纯度比较大，如果熵或者基尼值小于一定程度数，节点停止分裂。
（3）决策树的深度达到指定的条件
节点的深度可以理解为节点与决策树跟节点的距离，如根节点的子节点的深度为 1，因为这些节点与跟节点的距离为 1，子节点的深度要比父节点的深度大 1。决策树的深度是所有叶子节点的最大深度，当深度到达指定的上限大小时，停止分裂。
（4）所有特征已经使用完毕，不能继续进行分裂。
被动式停止分裂的条件，当已经没有可分的属性时，直接将当前节点设置为叶子节点。
3.4 决策树的构建方法
根据决策树的输出结果，决策树可以分为分类树和回归树，分类树输出的结果为具体的类别，而回归树输出的结果为一个确定的数值。
决策树的构建算法主要有 ID3、C4.5、CART 三种，其中 ID3 和 C4.5 是分类树，CART 是分类回归树
其中 ID3 是决策树最基本的构建算法，而 C4.5 和 CART 是在 ID3 的基础上进行优化的算法。
4. 决策树的优化
一棵过于复杂的决策树很可能出现过拟合的情况，如果完全按照 3 中生成一个完整的决策树可能会出现预测不准确的情况，因此需要对决策树进行优化，优化的方法主要有两种，一是剪枝，二是组合树
网友评论