毕业论文决策树算法研究

决策树基本上就是把我们以前的经验总结出来。我给你准备了一个打篮球的训练集。如果我们要出门打篮球，一般会根据“天气”、“温度”、“湿度”、“刮风”这几个条件来判断，最后得到结果：去打篮球？还是不去？ 上面这个图就是一棵典型的决策树。我们在做决策树的时候，会经历两个阶段：构造和剪枝。 构造就是生成一棵完整的决策树。简单来说，构造的过程就是选择什么属性作为节点的过程，那么在构造过程中，会存在三种节点： 根节点：就是树的最顶端，最开始的那个节点。在上图中，“天气”就是一个根节点； 内部节点：就是树中间的那些节点，比如说“温度”、“湿度”、“刮风”； 叶节点：就是树最底部的节点，也就是决策结果。 剪枝就是给决策树瘦身，防止过拟合。分为“预剪枝”（Pre-Pruning）和“后剪枝”（Post-Pruning）。 预剪枝是在决策树构造时就进行剪枝。方法是在构造的过程中对节点进行评估，如果对某个节点进行划分，在验证集中不能带来准确性的提升，那么对这个节点进行划分就没有意义，这时就会把当前节点作为叶节点，不对其进行划分。 后剪枝就是在生成决策树之后再进行剪枝，通常会从决策树的叶节点开始，逐层向上对每个节点进行评估。如果剪掉这个节点子树，与保留该节点子树在分类准确性上差别不大，或者剪掉该节点子树，能在验证集中带来准确性的提升，那么就可以把该节点子树进行剪枝。 1是欠拟合，3是过拟合，都会导致分类错误。 造成过拟合的原因之一就是因为训练集中样本量较小。如果决策树选择的属性过多，构造出来的决策树一定能够“完美”地把训练集中的样本分类，但是这样就会把训练集中一些数据的特点当成所有数据的特点，但这个特点不一定是全部数据的特点，这就使得这个决策树在真实的数据分类中出现错误，也就是模型的“泛化能力”差。 p(i|t) 代表了节点 t 为分类 i 的概率，其中 log2 为取以 2 为底的对数。这里我们不是来介绍公式的，而是说存在一种度量，它能帮我们反映出来这个信息的不确定度。当不确定性越大时，它所包含的信息量也就越大，信息熵也就越高。 ID3 算法计算的是信息增益，信息增益指的就是划分可以带来纯度的提高，信息熵的下降。它的计算公式，是父亲节点的信息熵减去所有子节点的信息熵。 公式中 D 是父亲节点，Di 是子节点，Gain(D,a) 中的 a 作为 D 节点的属性选择。 因为 ID3 在计算的时候，倾向于选择取值多的属性。为了避免这个问题， 采用信息增益率的方式来选择属性。信息增益率 = 信息增益 / 属性熵，具体的计算公式这里省略。 当属性有很多值的时候，相当于被划分成了许多份，虽然信息增益变大了，但是对于 来说，属性熵也会变大，所以整体的信息增益率并不大。 ID3 构造决策树的时候，容易产生过拟合的情况。在 中，会在决策树构造之后采用悲观剪枝（PEP），这样可以提升决策树的泛化能力。 悲观剪枝是后剪枝技术中的一种，通过递归估算每个内部节点的分类错误率，比较剪枝前后这个节点的分类错误率来决定是否对其进行剪枝。这种剪枝方法不再需要一个单独的测试数据集。 可以处理连续属性的情况，对连续的属性进行离散化的处理。比如打篮球存在的“湿度”属性，不按照“高、中”划分，而是按照湿度值进行计算，那么湿度取什么值都有可能。该怎么选择这个阈值呢， 选择具有最高信息增益的划分所对应的阈值。 针对数据集不完整的情况， 也可以进行处理。 暂无 请你用下面的例子来模拟下决策树的流程，假设好苹果的数据如下，请用 ID3 算法来给出好苹果的决策树。 「红」的信息增益为：1「大」的信息增益为：0 因此选择「红」的作为根节点，「大」没有用，剪枝。 数据分析实战45讲.17 丨决策树（上）：要不要去打篮球？决策树来告诉你

目录 一、决策树算法思想 二、决策树学习本质 三、总结 一、决策树（decision tree）算法思想： 决策树是一种基本的分类与回归方法。本文主要讨论分类决策树。决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。 它可以看做是if-then的条件集合，也可以认为是定义在特征空间与类空间上的条件概率分布 。决策树由结点和有向边组成。结点有两种类型：内部结点和叶结点，内部结点表示一个特征或属性，叶结点表示一个类。（椭圆表示内部结点，方块表示叶结点）          决策树与if-then规则的关系 决策树可以看做是多个if-then规则的集合。将决策树转换成if-then规则的过程是：由决策树的根结点到叶结点的每一条路径构建一条规则；路径上的内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论。决策树的路径或其对应的if-then规则集合具有一个重要的性质：互斥且完备。这就是说，每一个实例都被一条路径或一条规则所覆盖，且只被一条路径或一条规则所覆盖。这里的覆盖是指实例的特征与路径上的特征一致或实例满足规则的条件。          决策树与条件概率分布的关系 决策树还表示给定特征条件下类的条件概率分布。这一条件概率分布定义在特征空间的一个划分上。将特征空间划分为互不相交的单元或区域，并在每个单元定义一个类的概率分布，就构成一个条件概率分布。决策树的一条路径对应于划分中的一个单元。决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。          决策树模型的优点 决策树模型具有可读性，分类速度快。学习时，利用训练数据，根据损失函数最小化原则建立决策树模型；预测时，对新的数据，利用决策树模型进行分类 。二、决策树学习本质： 决策树学习是从训练数据集中归纳一组分类规则、与训练数据集不相矛盾的决策树可能有多个，也可能一个没有。我们需要训练一个与训练数据矛盾较小的决策树，同时具有很好的泛化能力。从另一个角度看 决策树学习是训练数据集估计条件概率模型 。基于特征空间划分的类的条件概率模型有无穷多个。我们选择的条件概率模型应该是不仅对训练数据有很好的拟合，而且对未知数据有很好的预测。 决策树的学习使用损失函数表示这一目标，通常的损失函数是正则化的极大似然函数。决策树的学习策略是以损失函数为目标函数的最小化。当损失函数确定后，决策树学习问题变为损失函数意义下选择最优决策树的问题。这一过程通常是一个递归选择最优特征，并根据特征对训练数据进行分割，使得对各个子数据集有一个最好分类的过程。这一过程对应着特征选择、决策树的生成、决策树的剪枝。          特征选择 ： 在于选择对训练数据具有分类能力的特征，这样可以提高决策树的学习效率。          决策树的生成 ： 根据不同特征作为根结点，划分不同子结点构成不同的决策树。          决策树的选择 ：哪种特征作为根结点的决策树信息增益值最大，作为最终的决策树（最佳分类特征）。          信息熵 ： 在信息论与概率统计中，熵是表示随机变量不确定性的度量。设X是一个取有限个值的离散随机变量，其概率分布为P(X= ) = ，i=1，2，3...n，则随机变量X的熵定义为         H(X) =  —  ，0 <=  H(X) <= 1，熵越大，随机变量的不确定性就越大。         条件熵（Y|X） ： 表示在已知随机变量X的条件下随机变量Y的不确定性。          信息增益  ： 表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。         信息增益  = 信息熵(父结点熵 ) — 条件熵（子结点加权熵） 三、 总结 ：         优点         1、可解释性高，能处理非线性的数据，不需要做数据归一化，对数据分布没有偏好。         2、可用于特征工程，特征选择。         3、可转化为规则引擎。         缺点         1、启发式生成，不是最优解。         2、容易过拟合。         3、微小的数据改变会改变整个数的形状。         4、对类别不平衡的数据不友好。