目录
一、前言
二、介绍
三、树的组成
四、决策树的训练与测试
五、熵的作用
六、决策树构造实例
七、信息增益率与gini系数
八、连续值应用
九、决策树的剪枝策略
十、回归，分类问题的解决
一、前言
本文需要了解树这一数据结构的基础知识。
二、介绍
决策树：如下图所示
从根节点开始一步步走到叶子节点（决策）
所有的数据最终都会落到叶子节点
有监督学习
提个问题: 怎样做分类？怎么做回归？
每一个条件都可以当作一个特征，根据特征判断。那么提出一个问题：条件1和条件2的位置是否可以对调，或者凭什么条件1当作根节点？就像NBA球队，有首发，有替补。根据什么度量？那么就让给我们继续看下去吧。
三、树的组成
根节点：第一个选择的作为判断的特征
非叶子节点与分支：中间过程
叶子节点：最终的决策结果
四、决策树的训练与测试
训练阶段：从给定的训练集构造出来一棵树（从根节点开始选择特征，如何进行特征划分）
测试阶段：根据构造出来的树模型从上到下走一遍就好了
一旦构造好了决策树，那么分类或者回归预测任务就很简单了，只需要走一遍就好了，那么难点就在于如何构造出一颗好的决策树呢？需要考虑的问题有很多！
五、熵的作用
记得上面的问题：如何切分特征，即根节点的选择该用那个特征呢？接下来呢？如何切分呢？
想象一下：我们的目标应该是通过根节点就能把大致的正确分类结果呈现出来，根节点就像球队老大对比赛结果产生极大的影响，有无它结果是两个样。根节点下面的节点自然就是在此基础上完善了。
目标：通过一种衡量标准，来计算通过不同的特征进行分支选择后的分类情况，找出来最好的那个当成根节点，以此类推。
开门见山，这种衡量标准就是熵，熵是表示随即变量不确定性的度量（物体内部的混乱程度）。那么熵值大小与决策树的关系？
如图：
经过一次决策后熵值是否减少（分类后的混乱程度）
熵的公式：
其图像：
当减小时，减小，其中表示某一特征值的概率。
一个例子：A集合:[1,1,1,1,2,2,2] B集合:[1,2,3,4,5,6,7]
显然A集合的熵值要低，因为A里面只有两种类别，相对稳定一些，B中的类别太多了熵值就会大很多。（在分类任务中我们希望通过节点分治后的数据类别的熵值大还是小呢？当然是小喽）
我们已经知道了，不确定性越大，得到的熵值也就越大。
当p=0或者p=1时，H(p)=0,随机变量完全没有不确定性。
当p=0.5时，H(p)=1,此时随机变量的不确定性最大。
如何决策一个节点的选择呢？
信息增益：表示特征X使得类Y的不确定性减少的程度。（分类后的专一性，希望分类后的结果是同类在一起）
六、决策树构造实例
数据：14天的打球情况
特征：4种环境变化
目标：构造决策树
outlooktemperaturehumiditywindyplaysunnyhothighFALSEnosunnyhothighTRUEnoovercasthothighFALSEyesrainymildhighFALSEyesrainycoolnormalFALSEyesrainycoolnormalTRUEnoovercastcoolnormalTRUEyessunnymildhighFALSEnosunnycoolnormalFALSEyesrainymildnormalTRUEyessunnymildnormalFALSEyesovercastmildhighTRUEyesovercasthotnormalFALSEyesrainymildhighTRUEno
划分方式：4种 基于天气outlook的划分，基于温度temperature的划分，基于湿度humidity的划分，基于有风windy的划分。
问题：谁当根节点？
依据：信息增益
在历史数据中（14天）有9天打球，5天不打球，所以此时的熵应为（即什么都不做）：
4个特征逐一分析，先从outlook开始：
outlooksunnyovercastrainyyesyesyesyesyesyesnoyesyesnoyesnonono
outlook=sunny时：
outlook=overcast时：0
outlook=rainy时：0.971
根据数据统计，outlook值分别为sunny,overcast,rainy时的概率分别为：5/14,4/14,5/14，当作权值
熵值的计算：
信息增益：系统的熵值从原始的0.940下降到了0.693，增益为0.247
同理算出其他特征的信息增益为：
gain(temperature）=0.029,gain(humidity）=0.152,gain(windy）=0.048,相当于遍历了一遍特征，选择最大的。
以此类推
七、信息增益率与gini系数
决策树算法
ID3：信息增益（存在问题）
在左侧加一列ID，以ID为特征出现的问题：
IDoutlooktemperaturehumiditywindyplay1sunnyhothighFALSEno2sunnyhothighTRUEno3overcasthothighFALSEyes4rainymildhighFALSEyes5rainycoolnormalFALSEyes6rainycoolnormalTRUEno7overcastcoolnormalTRUEyes8sunnymildhighFALSEno9sunnycoolnormalFALSEyes10rainymildnormalTRUEyes11sunnymildnormalFALSEyes12overcastmildhighTRUEyes13overcasthotnormalFALSEyes14rainymildhighTRUEno
虽然信息增益很大，却不是我们想要的结果，可见ID3不适合解决像ID种类特别多的特征。
C4.5 ：信息增益率（解决ID3问题，考虑自身熵）
公式：
若自身的熵很大的时候，信息增益率就变得小了
CART：使用gini系数来当作衡量标准
公式：(和熵的衡量标准类似的计算方式)
八、连续值应用
对于连续值应该选取那个分界点？
例如：对于排好序的人的体重公斤： 60 70 75 85 86 87 90 95 96 100
一样进行‘二分’，则可能有9个分界点，算出熵值增益。
九、决策树的剪枝策略
为什么剪枝：决策树过拟合的风险很大，理论上可以完全分得开，即每个叶子节点有一个样本数。
剪枝策略：预剪枝，后剪枝
预剪枝：边建立决策树边进行剪枝的操作（更使用）比如：限制树的深度，叶子节点的个数，叶子节点的样本数，信息增益量，这些在建树之前做一个判断就可。
后剪枝：当建立完决策树后来进行剪枝操作。（通过一定的衡量标准：
,其中：表示损失，表示当前节点的熵值或者Gini系数，表示节点的样本数，是自定参数，即惩罚系数。
）
例如：
左边的Age<=2.5的特征节点，其分类后的
当其结果超过设置的阈值，其被剪枝。
十、回归，分类问题的解决
分类任务：做完决策树后，看叶子节点样本中，Y值的纵数是啥，其预测的结果就是啥。
回归任务：回归的到的值是一个具体的值，那么怎么建立决策树呢？答案是用样本的方差来来作为衡量标准。大家想一想，方差越小说明数据越接近，就越被划分为同一类，随着划分的进行，方差也像熵一样减小。而预测的结果就用节点样本的平均值。
精彩文章
您阅读本篇文章共花了：
发表评论