决策树
Last updated
Was this helpful?
Last updated
Was this helpful?
构建分类模型和使用分类模型进行预测、分类。
例如，我现在给你一个训练集，是客户是否买房与客户年龄、性别、收入、婚姻状况等因素相关性的表格。
这样，你就能通过决策树算法构建一个客户是否会买房的决策树；你还能通过这个模型去预测，新来的客户是否会买房。
可以理解是一种决策流程，例如顾客买不买车，有如下这样的决策流程：
对于一个复杂的问题，可能有非常多的影响因素，如何判断哪个因素对最终结果影响大呢？决策流程如何设计更合理呢？这就是决策树算法存在的意义。
对于从训练集生成的决策树模型，可以精确的解释该决策树是怎样生成的，又会进行怎样的预测，决策树有很好的可解释性。
度量随机变量Y={c1，c2,c3…,ck}的不确定性，熵越大，不确定性越高。在分类中类别越多，也就说包含的信息越多，熵越大（越不确定是哪个分类）。如果只有一个分类，则p(x)=1,熵即为0，熵越小，越确定。
比如预测客户是否会买房，那么“客户的收入”这个条件比“今天晚上吃不吃鸡腿”这个信息更能确定用户买房的确定性，它的信息熵就更小。
对上述数据集，一共8条，其中3人买房，5人没买。
将20-30，30-40，40+三个阶段的条件熵按照总体比例相乘累加（分子的8指的是总共有8条数据，分母则对应的是20-30（3人）；30-40（2人）；40+（3人）这三个特定年龄阶段的人数，得到以AGE为特征的总体熵值。
信息增益=总熵-以某特性为特征的条件熵
同理可计算出收入、婚姻、性别的相关熵值、信息增益
可知，以收入为特征的信息增益最大，那么就可以以收入特征作为根节点来构造决策树：
CART 树（分类回归树）分为分类树和回归树。分类树用于处理分类问题；回归树用来处理回归问题。
CART 树和 ID3、C4.5 决策树相似，都用来处理分类问题。不同之处是划分方法，CART 树利用基尼系数进行二分，生成决策树的结构与二叉树一致。
训练决策树包括将当前数据分成两个分支。假设我们有以下数据点:
现在，我们的分支里有5个蓝点和5个绿点。如果我们在x=2处进行划分:
这很明显是个完美划分，因为它把数据集分成了两个分支：
左分支全是蓝点
右分支全是绿点
但如果我们在x=1.5处进行划分呢?
这个划分把数据集分成了两个分支：
左分支，4个蓝点
右分支，1个蓝点+5个绿点
很明显，这种划分更糟糕，但我们如何量化呢?
解决方法就是基尼杂质系数。
按以上不完美划分为例：
划分前整个数据集的基尼杂质系数是0.5，划分后，左分支是基尼杂质系数为0，右分支为0.278，由于左分支有4个样本，右分支有6个样本，因此划分后的总体基尼杂质系数为：(0.4∗0)+(0.6∗0.278)=0.167
因此，用这个划分“降低”的杂质量是：0.5−0.167=0.333
这就是基尼增益系数。
绝大部分情况下熵（entropy）和基尼指数（Gini Index）在决策树节点分裂时做出的决策都是等价的。
那为啥存在两种常用算法呢？其实是因为[1]使用了熵，而[2]使用了基尼指数，两个工作都很有开创性就都保留了下来。
•横轴表示在决策树创建过程中树的结点总数，纵轴表示决策树的预测精度。 •实线显示的是决策树在训练集上的精度，虚线显示的则是在一个独立的测试集上测量出来的精度。
可以看出随着树的增长， 在训练样集上的精度是单调上升的， 然而在独立的测试样例上测出的精度先上升后下降。
产生这种现象的原因如下：
•原因1：噪声、样本冲突，即错误的样本数据。
•原因2：特征即属性不能完全作为分类标准。
•原因3：巧合的规律性，数据量不够大。
这个时候，就需要对生成树进行修剪，也就是剪枝。剪枝通常有两种做法：预剪枝和后剪枝。
预剪枝就是在完全正确分类训练集之前，较早地停止树的生长。
由于预剪枝不必生成整棵决策树，且算法相对简单， 效率很高， 适合解决大规模问题。但是尽管这一方法看起来很直接， 但是 怎样精确地估计何时停止树的增长是相当困难的。
预剪枝有一个缺点， 即视野效果问题 。 也就是说在相同的标准下，也许当前的扩展会造成过度拟合训练数据，但是更进一步的扩展能够满足要求，也有可能准确地拟合训练数据。这将使得算法过早地停止决策树的构造。
后剪枝，在已生成过拟合决策树上进行剪枝，可以得到简化版的剪枝决策树。
有四个纬度，年龄，性别，收入，婚姻状况，其中，我们可以看到年龄、收入两个维度由具体数值构成，为了更加方便的进行分层，我们将它划分为几个层次~年龄分为20-30，30-40，40+三个阶段，把收入分为10-20，20-40，40+三个级别。
