关键词：
引言
本文主要是对分类型决策树的一个总结。在分类问题中，决策树可以被看做是if-then规则的结合，也可以认为是在特定特征空间与类空间上的条件概率分布。决策树学习主要分为三个步骤：特征选择、决策树的生成与剪枝操作。本文简单总结ID3和C4.5算法，之后是决策树的修剪。
ID3算法
ID3算法和核心是：在决策树各级节点上选择属性时，用信息增益（information gain）作为属性的选择标准，具体做法是：检测所有的属性，选择信息增益最大的属性产生决策树节点，由该属性的不同取值建立分支，再对各分支循环调用该方法建立决策树节点的分支，直到所有子集仅包含同一类别为止。
信息增益
了解信息增益，首先介绍熵与条件熵的概念。
熵表示随机变量不确定性的度量。设$X$是一个取有限值的离散随机变量，其概率分布为：
$$p(X=x_i)=p_i$$
则随机变量 $X$ 的熵定义为:
$$H(X)=-sum_i=1^np_ilogp_i ， i=1,2,n$$
由定义可知，熵只依赖于$X$的分布，而与$X$的取值无关。
熵越大，随机变量的不确定性越高，并且：
$$0leqslantH(p)leqslantlogn$$
当随机变量只有两个取值时，例如0，1，则$X$的分布为：
$$p(X=1)=p，p(X=0)=1-p， 0leqslantpleqslant1$$
熵为：
$$H(p)=-plog_2p-(1-p)log_2(1-p)$$
当$p=0$或$p=1$时，$H(p)=0$，随机变量完全没有不确定性，当$p=0.5$时，$H(p)=1$，熵取最大值，随机变量的不确定性最大。
条件熵
设随即变量$(X,Y)$，其联合概率分布为：
$$P(X=x_i,Y=y_i)=p_ij,i=1,2,dots,n;j=1,2,dots,n$$
条件熵$H(Y|X)$表示在已知随机变量$X$的条件下随机变量$Y$的不确定性，随机变量$X$给定的条件下随机变量$Y$的条件熵$H(Y|X)$，定义为$X$给定的条件下$Y$的条件概率分布的熵对$X$的数学期望：
$$H(Y|X)=sum_i=1^np_iH(Y|X=x_i)$$
这里，$p_i=P(X=x_i)$
信息增益
特征$A$对训练数据集$D$的信息增益，定义为集合$A$的经验熵$H(D)$与特征$A$给定条件下$D$的经验条件熵$H(D|A)$之差：
$$g(D,A)=H(D)-H(D|A)$$
小结
ID3算法就是在每次需要分裂时，计算每个属性的增益率，然后选择增益率最大的属性进行分裂.
其核心是：决策树各级结点上选择属性时，用信息增益（information?gain）作为属性的选择标准，以使得在每一个非叶结点进行测试时，能获得关于被测试记录最大的类别信息。
其方法是：检测所有的属性，选择信息增益最大的属性产生决策树结点，由该属性的不同取值建立分支，再对各分支的子集递归调用该方法建立决策树结点的分支，直到所有子集仅包含同一类别的数据为止。最后得到一棵决策树。
C4.5算法
C4.5算法首先定义了“分裂信息”，即信息增益比：
$$g_R(D,A)=fracg(D,A)H(D)qquad$$
C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进：?
- 1：用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足
- 2：能够完成对连续属性的离散化处理；?
- 3：能够对不完整数据进行处理。
决策树剪枝
决策树构造时，由于训练数据中的噪音或孤立点，许多分枝反映的是训练数据中的异常，使用这样的判定树对类别未知的数据进行分类，分类的准确性不高。因此试图检测和减去这样的分支，检测和减去这些分支的过程被称为树剪枝。树剪枝方法用于处理过分适应数据问题。通常，这种方法使用统计度量，减去最不可靠的分支，这将导致较快的分类，提高树独立于训练数据正确分类的能力。
树枝修剪包括事先修剪和事后修剪两种方法：
（1）事前修剪方法：在决策树生成分支的过程，除了要进行基础规则的判断外，还需要利用统计学的方法对即将分支的节点进行判断，比如$chi^2$或统计信息增益，如果分支后使得子集的样本统计特性不满足规定的阈值，则停止分支；但是阈值如何选取才合理是比较困难的。
（2）事后修剪方法：在决策树充分生长后，修剪掉多余的分支。根据每个分支的分类错误率及每个分支的权重，计算该节点不修剪时预期分类错误率；对于每个非叶节点，计算该节点被修剪后的分类错误率，如果修剪后分类错误率变大，即放弃修剪；否则将该节点强制为叶节点，并标记类别。产生一系列修剪过的决策树候选之后，利用测试数据（未参与建模的数据）对各候选决策树的分类准确性进行评价，保留分类错误率最小的决策树。
除了利用分类错误率进行树枝修剪，也可以利用决策树的编码长度进行修剪。所谓最佳决策树是编码长度最短的决策树，这种修剪方法利用最短描述长度（MDL）原则来进行决策树的修剪。
机器学习决策树分类原理(代码片段)
决策树分类原理1.熵1.1概念1.2案例2.决策树的划分依据2.1信息增益2.1.1概念2.1.2案例2.2信息增益率2.2.1概念2.2.2案例案例一案例二2.2.3为什么使用C4.5要好?2.3基尼值和基尼指数2.3.1概念2.3.2案例3.小结3.1常见决策树的启发函数比较3.1.1ID3... 查看详情
机器学习决策树算法和分类原理(代码片段)
目录1决策树算法简介2决策树分类原理2.1熵2.1.1概念2.1.2案例2.2划分依据一：信息增益2.2.1概念2.2.2案例2.3划分依据二：信息增益率2.3.1概念2.3.2案例2.3.2.1案例一2.3.2.2案例二2.3.3为什么使用C4.5要好2.4划分依据三：基尼值... 查看详情
决策树--id3算法小结
...eDichotomiser3迭代二叉树3代)，是一个由RossQuinlan发明的用于决策树的算法；简单理论是越是小型的决策树越优于大的决策树。算法归纳：1、使用所有没有使用的属性并计算与之相关的样本熵值；2、选取其中熵值最小的属性3、生成... 查看详情
史诗级干货长文决策树算法(代码片段)
决策树算法1.决策树算法简介2.决策树分类原理3.cart剪枝3.1为什么要剪枝?3.2常用的减枝方法3.2.1预剪枝3.2.2后剪枝3.3小结4.特征工程-特征提取5.决策树算法API6.案例：泰坦尼克号乘客生存预测7.回归决策树1.决策树算法简介决策... 查看详情
18大经典数据挖掘算法小结
...掘的经典算法进行了学习并且进行了代码实现，涉及到了决策分类，聚类，链接挖掘，关联挖掘，模式挖掘等等方面。也算是对数据挖掘领域的小小入门了吧。下面就做个小小的总结，后面都是我自己相应算法的博文链接，希望... 查看详情
机器学习决策树算法和分类原理(代码片段)
目录1决策树算法简介2决策树分类原理2.1熵2.1.1概念2.1.2案例2.2划分依据一：信息增益2.2.1概念2.2.2案例2.3划分依据二：信息增益率2.3.1概念2.3.2案例2.3.2.1案例一2.3.2.2案例二2.3.3为什么使用C4.5要好2.4划分依据三：基尼值... 查看详情
机器学习--决策树分类算法及应用
1.决策树分类算法原理1.1概述决策树（decisiontree）——是一种被广泛使用的分类算法。相比贝叶斯算法，决策树的优势在于构造过程不需要任何领域知识或参数设置在实际应用中，对于探测式的知识发现，决策树更加适用1.2算法... 查看详情
分类算法——决策树
】分类算法——决策树【英文标题】：Classificationalgorithm-decisiontree【发布时间】：2018-12-1217:22:15【问题描述】：我有从感应电机收集的MPU6050加速度计数据。我想训练一种算法并使用新数据集进行预测。我已经使用决策树分类器... 查看详情
ml:决策树算法
...sp;在众多的分类模型中，应用最为广泛的两种分类模型是决策树模型(DecisionTreeModel)和朴素贝叶斯模型（NaiveBayesianModel，NBC）。决策树模型通过构造树来解决分类问题。首先利用训练数据集来构造一棵决策树，一旦树建立起来，... 查看详情
机器学习回归决策树算法(代码片段)
目录1原理概述2算法描述3简单实例3.1实例计算过程3.2回归决策树和线性回归对比4小结1原理概述前面已经讲到，关于数据类型，我们主要可以把其分为两类，连续型数据和离散型数据。在面对不同数据时，决策树... 查看详情
sparkmllib分类算法之决策树学习
SparkMLlib分类算法之决策树学习（一）决策树的基本概念 决策树(DecisionTree）是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法... 查看详情
分类算法之决策树
分类问题，主要介绍决策树算法、朴素贝叶斯、支持向量机、BP神经网络、懒惰学习算法、随机森林与自适应增强算法、分类模型选择和结果评价。一、分类基本介绍 物以类聚，人以群分，分类问题只古以来就出现我们的生... 查看详情
机器学习算法学习02：决策树的学习以及应用决策树解决cora数据集论文分类问题(代码片段)
机器学习算法学习02：决策树的学习以及应用决策树解决Cora数据集论文分类问题文章目录机器学习算法学习02：决策树的学习以及应用决策树解决Cora数据集论文分类问题1.前言2.算法分析2.1算法概述2.2算法优化3.算法代码3.... 查看详情
机器学习决策树
1、决策树简介1.1决策树概述决策树算法是一种基于树形结构的分类算法，它能从给定的无序的训练样本中，提炼出树型的分类模型，树形中包含判断模块和终止模块。它是一种典型的分类算法，首先对数据进行处理，利用归纳... 查看详情
机器学习算法决策树-6prism
目录PRISM决策规则算法如何使用分类树来进行分类预测：分类树与分类规则间的关系PRISM决策规则的产生方式我的主页：晴天qt01的博客_CSDN博客-数据分析师领域博主目前进度：第四部分【机器学习算法】PRISM决策规则... 查看详情
提升算法
...采用加法模型(即基函数的线性组合)与前向分布算法，以决策树为基函数的提升方法称为提升树，对分类问题决策树是二叉分类树，对回归问题决策树是二叉回归树，其根据特征x<v与x>v将根结点直接连接两个叶结点，以作为... 查看详情
matlab基于决策树算法实现多分类预测（源码可直接替换数据）
【Matlab】基于决策树算法实现多分类预测（源码可直接替换数据））1.算法简介1.1算法原理1.2算法优点1.3算法缺点1.4算法步骤2.测试数据集3.替换数据4.函数说明4.1文件结构4.2文件函数5.混淆矩阵6.对比结果7.代码及注释1.算法简介1.... 查看详情
matlab基于决策树算法实现多分类预测（源码可直接替换数据）
【Matlab】基于决策树算法实现多分类预测（源码可直接替换数据））1.算法简介1.1算法原理1.2算法优点1.3算法缺点1.4算法步骤2.测试数据集3.替换数据4.函数说明4.1文件结构4.2文件函数5.混淆矩阵6.对比结果7.代码及注释1.算法简介1.... 查看详情