id3决策树java的简单介绍

今天给各位分享id3决策树java的知识，其中也会对进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！

本文目录一览：

• 1、【理论篇】决策树算法 - 信息增益率、GINI系数
• 2、决策树ID3，C4.5，CART算法中某一属性分类后，是否能运用该属性继续分类
• 3、5.10 决策树与ID3算法
• 4、白话梳理树模型——从决策树到lightGBM
• 5、决策树——ID3算法应用实例
• 6、为什么id3树不能处理连续性属性

【理论篇】决策树算法 - 信息增益率、GINI系数

ID3 决策树算法在特征选择时存在什么问题呢？

我们来举个例子：数据集 A 存在一个非常稀疏的特征 ID 列，我们知道 ID 是唯一不重复的，种类自然就会非常庞大。

这个时候，如果我们使用 ID 去切分数据集，那切分到最后，每个样本都会被分配到单独的样子结点上，每个样子结点的数据只有一样，不确定性为 0 ，熵值也为 0 。

那这样是不是就说名 ID 这个特征非常好呢？根据 ID 就能预测标签？当然不是，实际上 ID 这个特征毫无意义。

小鱼这里拿 ID 举例，只是个极端的例子。但足以说明，对于类似 ID 这样数据种类非常多，分布非常稀疏的特征来说，ID3 决策树算法通过信息增益来选取结点特征是远远不够的。

为了解决 ID3 决策树算法的问题，我们引入了信息增益率，计算信息增益时，考虑特征分布的自身熵。

C4.5 决策树算法使用信息增益率来衡量特征节点的分类能力。所谓信息增益率就是在信息增益的基础上除以该特征自身的熵值计算而来。

为什么要除以特征自身的熵值呢？我们举个例子：还是刚才的 ID 特征，ID 特征切分完数据后的熵值为 0 ，原始数据集的熵值为 G，特征 ID 的熵值为 -n*(1/n)*log(1/n) = -log(1/n) 其中 n 为数据集样本的个数。因此，特征 ID 的熵 G2 是一个非常庞大的数值。

使用 ID 节点切分数据集之后，得到的信息增益为：G - 0 = G，信息增益非常大，分类效果堪称完美。但如果使用信息增益率去衡量，则：(G - 0)/G2，其中 G2 一定是远远大于 G 的，因为很显然标签的混乱层度远低于 ID 列的混乱层度。

因此，我们求得的信息增益率就是一个非常小的值了，这个时候就可以发现 ID 这个特征分类效果非常差。也因此 C4.5 算法很好地解决了 ID3 算法对稀疏特征衡量的不足。

GINI 系数和熵的衡量标准类似，只是计算方式不同。GINI 系数的公式为：

当概率 P 为 0 或者 1 时，此时没有不确定性。其中概率为 1 时，GINI系数为 0 ，概率为 0 时，GINI 系数也为 0 。

决策树ID3，C4.5，CART算法中某一属性分类后，是否能运用该属性继续分类

决策树主要有ID3，C4.5，CART等形式。ID3选取信息增益的属性递归进行分类，C4.5改进为使用信息增益率来选取分类属性。CART是Classfication and Regression Tree的缩写。表明CART不仅可以进行分类，也可以进行回归。其中使用基尼系数选取分类属性。以下主要介绍ID3和CART算法。

ID3算法：

信息熵： H(X)=-sigma（对每一个x）（plogp） H(Y|X)=sigma(对每一个x)（pH(Y|X=xi)）

信息增益：H（D）-H(D|X) H(D)是整个数据集的熵

信息增益率：（H(D)-H(D|X)）/H(X)

算法流程：（1）对每一个属性计算信息增益，若信息增益小于阈值，则将该支置为叶节点，选择其中个数最多的类标签作为该类的类标签。否则，选择其中最大的作为分类属 性。

（2）若各个分支中都只含有同一类数据，则将这支置为叶子节点。

否则 继续进行（1）。

CART算法：

基尼系数：Gini（p）=sigma（每一个类）p(1-p)

回归树：属性值为连续实数。将整个输入空间划分为m块，每一块以其平均值作为输出。f(x)=sigma(每一块)Cm*I(x属于Rm)

回归树生成：（1）选取切分变量和切分点，将输入空间分为两份。

（2）每一份分别进行第一步，直到满足停止条件。

切分变量和切分点选取：对于每一个变量进行遍历，从中选择切分点。选择一个切分点满足分类均方误差最小。然后在选出所有变量中最小分类误差最小的变量作为切分 变量。

分类树：属性值为离散值。

分类树生成：（1）根据每一个属性的每一个取值，是否取该值将样本分成两类，计算基尼系数。选择基尼系数最小的特征和属性值，将样本分成两份。

（2）递归调用（1）直到无法分割。完成CART树生成。

决策树剪枝策略：

预剪枝（树提前停止生长）和后剪枝（完全生成以后减去一些子树提高预测准确率）

降低错误率剪枝：自下而上对每一个内部节点比较减去以其为叶节点和子树的准确率。如果减去准确率提高，则减去，依次类推知道准确率不在提高。

代价复杂度剪枝：从原始决策树T0开始生成一个子树序列{T0、T1、T2、...、Tn},其中Ti+1是从Ti总产生，Tn为根节点。每次均从Ti中 减去具有最小误差增长率的子树。然后通过 交叉验证比较序列中各子树的效果选择最优决策树。

5.10 决策树与ID3算法

决策树（decision tree）是一个树结构（可以是二叉树或非二叉树）。决策过程是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点存放的类别作为决策结果。

决策树的关键步骤是分裂属性。就是在某节点处按某一特征属性的不同划分构造不同的分支，目标是让各个分裂子集尽可能地“纯”。即让一个分裂子集中待分类项属于同一类别。

简而言之，决策树的划分原则就是：将无序的数据变得更加有序

分裂属性分为三种不同的情况 ：

构造决策树的关键性内容是进行属性选择度量，属性选择度量（找一种计算方式来衡量怎么划分更划算）是一种选择分裂准则，它决定了拓扑结构及分裂点split_point的选择。

属性选择度量算法有很多，一般使用自顶向下递归分治法，并采用不回溯的贪心策略。这里介绍常用的ID3算法。

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，所做出的是在某种意义上的局部最优解。

此概念最早起源于物理学，是用来度量一个热力学系统的无序程度。

而在信息学里面，熵是对不确定性的度量。

在1948年，香农引入了信息熵，将其定义为离散随机事件出现的概率，一个系统越是有序，信息熵就越低，反之一个系统越是混乱，它的信息熵就越高。所以信息熵可以被认为是系统有序化程度的一个度量。

熵定义为信息的期望值，在明晰这个概念之前，我们必须知道信息的定义。如果待分类的事务可能划分在多个分类之中，则符号x的信息定义为：

在划分数据集之前之后信息发生的变化称为信息增益。

知道如何计算信息增益，就可计算每个特征值划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择。

条件熵 表示在已知随机变量的条件下随机变量的不确定性，随机变量X给定的条件下随机变量Y的条

件熵(conditional entropy) ，定义X给定条件下Y的条件概率分布的熵对X的数学期望：

根据上面公式，我们假设将训练集D按属性A进行划分，则A对D划分的期望信息为

则信息增益为如下两者的差值

ID3算法就是在每次需要分裂时，计算每个属性的增益率，然后选择增益率最大的属性进行分裂

步骤：1. 对当前样本集合，计算所有属性的信息增益；

是最原始的决策树分类算法，基本流程是，从一棵空数出发，不断的从决策表选取属性加入数的生长过程中，直到决策树可以满足分类要求为止。CLS算法存在的主要问题是在新增属性选取时有很大的随机性。ID3算法是对CLS算法的改进，主要是摒弃了属性选择的随机性。

基于ID3算法的改进，主要包括：使用信息增益比替换了信息增益下降度作为属性选择的标准；在决策树构造的同时进行剪枝操作；避免了树的过度拟合情况；可以对不完整属性和连续型数据进行处理；使用k交叉验证降低了计算复杂度；针对数据构成形式，提升了算法的普适性。

信息增益值的大小相对于训练数据集而言的，并没有绝对意义，在分类问题困难时，也就是说在训练数据集经验熵大的时候，信息增益值会偏大，反之信息增益值会偏小，使用信息增益比可以对这个问题进行校正，这是特征选择

的另一个标准。

特征对训练数据集的信息增益比定义为其信息增益gR( D,A) 与训练数据集的经验熵g(D,A)之比 ：

gR(D,A) = g(D,A) / H(D)

sklearn的决策树模型就是一个CART树。是一种二分递归分割技术，把当前样本划分为两个子样本，使得生成的每个非叶子节点都有两个分支，因此，CART算法生成的决策树是结构简洁的二叉树。

分类回归树算法(Classification and Regression Trees,简称CART算法)是一种基于二分递归分割技术的算法。该算法是将当前的样本集，分为两个样本子集，这样做就使得每一个非叶子节点最多只有两个分支。因此，使用CART

算法所建立的决策树是一棵二叉树，树的结构简单，与其它决策树算法相比，由该算法生成的决策树模型分类规则较少。

CART分类算法的基本思想是：对训练样本集进行递归划分自变量空间，并依次建立决策树模型，然后采用验证数据的方法进行树枝修剪，从而得到一颗符合要求的决策树分类模型。

CART分类算法和C4.5算法一样既可以处理离散型数据，也可以处理连续型数据。CART分类算法是根据基尼(gini)系

数来选择测试属性，gini系数的值越小，划分效果越好。设样本集合为T，则T的gini系数值可由下式计算：

CART算法优点：除了具有一般决策树的高准确性、高效性、模式简单等特点外，还具有一些自身的特点。

如，CART算法对目标变量和预测变量在概率分布上没有要求，这样就避免了因目标变量与预测变量概率分布的不同造成的结果；CART算法能够处理空缺值，这样就避免了因空缺值造成的偏差；CART算法能够处理孤立的叶子结点，这样可以避免因为数据集中与其它数据集具有不同的属性的数据对进一步分支产生影响；CART算法使用的是二元分支，能够充分地运用数据集中的全部数据，进而发现全部树的结构；比其它模型更容易理解，从模型中得到的规则能获得非常直观的解释。

CART算法缺点：CART算法是一种大容量样本集挖掘算法，当样本集比较小时不够稳定；要求被选择的属性只能产生两个子结点，当类别过多时，错误可能增加得比较快。

sklearn.tree.DecisionTreeClassifier

1.安装graphviz.msi ， 一路next即可

ID3算法就是在每次需要分裂时，计算每个属性的增益率，然后选择增益率最大的属性进行分裂

按照好友密度划分的信息增益：

按照是否使用真实头像H划分的信息增益

**所以，按先按好友密度划分的信息增益比按真实头像划分的大。应先按好友密度划分。

白话梳理树模型——从决策树到lightGBM

本文仅为简单梳理树模型升级过程，尽量少牵扯到数学公式，用大白话来理解。

熵，熵用来描述事件的不确定性，越随机熵值越大。

如何理解不确定性呢？假设现在有一个伯努利分布，p(0) = p(1) = 1/2，则这个分布的不确定性是最大的，因为我们抽样的时候完全无法确定抽样出来的那个数值的概率更大，两者都是1/2，所以不确定性在这里可以理解为某个事件发生的概率。我们再来看看熵值的公式：

对于一个伯努利其熵值为：

H(p) = -p(p)log(p) - (1-p)log(1-p)

为了验证我们上面提到的伯努利分布的某个事件发生概率为1/2时熵最大，将p=1/2代入上式得到的熵值与p=4/5时的熵值进行比较即可，可以得到

H(p=1/2) H(p=4/5)。

当P等于4/5时，我们有很大的概率（80%）可以确定事件会发生，而p=1/2时，则完全无法确定事件是否会发生，因为发生不发生的概率相等，这就是事件发生的不确定性。也即熵值H(p=1/2) H(p=4/5)可以得出p=4/5时，不确定性更小，能更方便的猜出事件是否会发生。

树模型作为一种简单易理解的方式，其训练过程即是通过简单if/else来将所有的样本划分到其对应的叶子中。

ID3决策树使用信息增益来作为特征选择标准，每次选择信息增益最大的特征。需要注意的是ID3是一颗多叉树，因此他总是倾向于选择特征值更多的特征来进行分裂。如何理解呢？

一个极端的例子，假设我们以人的DNA为特征来对训练集中的人群进行分类，毫无疑问的，只需要这一个特征（每个样本一个特征值）且只要这一次分裂就可以将所有人分开，因为每个人的DNA是唯一的，因此每一个人都是一个叶子结点。但是这个时候如果我们想要预测测试集怎么办？测试集中的人群DNA在训练集中没出现过，因此模型无法对测试集进行正确预测。也就是发生了我们常常说的过拟合现象。

ID3小总结：

C4.5决策树针对ID3决策树偏好值多的缺点进行改进，引入了信息增益比来作为分裂标准。

C4.5相较于ID3的改进有：

C4.5树仍然使用的是多叉树，因此每个特征仅使用一次，在后续分裂中不再使用。且只能用于分类。

CART决策树相对于C4.5树进行了改进：

随机森林属于bagging算法，有两个随机过程：

预测时，分类问题投票，回归问题求平均。

优点：

梯度提升树 由多个回归决策树 串联得到，因此建树时的分裂标准是均方误差和。

梯度提升树的每个树都会拟合上棵树的拟合目标残差。

在梯度提升决策树中，还添加了shrinkage，这个是与adaboost的一个重大区别，相当于学习率，控制每棵树学习到更少的东西，使用更多的树来进行集成学习。

缺点：

xgboost的相对于GBDT的一个非常重要的改进就是使用泰勒二阶展开来近似拟合残差，也即如下公式：

再加上模型复杂度的表示，可以得到最终loss：

这里我们简单说一下模型复杂度的组成，第一项 γT其实是控制的树的叶子节点不要太多（可以理解为参数不要太多，L1正则化），第二项其实是控制每个叶子结点的数值不要太大（可以理解为模型参数不要太大，L2正则化）。

上面几步看不明白的可以去 看一步一步的推导过程。

可以看到，模型的优化目标其实仅与前一棵树一阶导（G）、二阶导（H）、lambda（可以理解为L2正则化系数）、γ（理解为L1正则化系数）有关系。对于决策树的每次分裂，我们的目标其实就是要使得上面的目标函数值更小， 换句话说，上面的目标函数就是我们的分裂标准，这与前面所有的决策树的分裂方式都是完全不同的。

看看下面的图可能更好理解：

在分裂选择特征时，仅使用非缺失值来进行计算增益。而对于缺失结点的划分，则是将每个缺失样本分别放入到两个子节点中，哪个增益大就选择划分到哪个结点。

略。。。

优点：

更快，占用内存更小的GBM。

优化的点如下：

树模型解释性较好，我们常常可以通过树模型来进行特征选择，留下重要特征。不同树模型特征重要性评估方法略有区别。

决策树 、 随机森林 和 GBDT 的特征重要性评估方法相同都是根据不纯度减小(也即gini系数)来进行度量：

xgboost 的特征重要性评估方法更为多样，如下：

lightGBM 的特征评估方式如下：

参考：

《统计学习方法》李航

【机器学习】决策树（下）——XGBoost、LightGBM（非常详细）

树模型(六)：XGBoost (带手动建树实例，非常推荐)

决策树——ID3算法应用实例

在ID3决策树归纳方法中，通常是使用信息增益方法来帮助确定生成每个节点时所应采用的合适属性。这样就可以选择具有最高信息增益（熵减少的程度最大）的属性最为当前节点的测试属性，以便对之后划分的训练样本子集进行分类所需要的信息最小，也就是说，利用该属性进行当前（节点所含）样本集合划分，将会使得所产生的样本子集中的“不同类别的混合程度”降为最低。因此，采用这样一种信息论方法将有效减少对象分来所需要的次数，从而确保所产生的决策树最为简单。

一、实验目的

1、理解分类

2、掌握分类挖掘算法ID3

3、为改进ID3打下基础

二、实验内容

1、选定一个数据集（可以参考教学中使用的数据集）

2、选择合适的实现环境和工具实现算法 ID3

3、给出分类规则

三、实验原理

决策树是一种最常见的分类算法，它包含有很多不同的变种，ID3算法是其中最简单的一种。ID3算法中最主要的部分就是信息熵和信息增益的计算。

为什么id3树不能处理连续性属性

ID3算法是决策树的一个经典的构造算法，在一段时期内曾是同类研究工作的比较对象，但通过近些年国内外学者的研究，ID3算法也暴露出一些问题，具体如下：

(1)信息增益的计算依赖于特征数目较多的特征，而属性取值最多的属性并不一定最优。

(2)ID3是非递增算法。

(3)ID3是单变量决策树(在分枝节点上只考虑单个属性)，许多复杂概念的表达困难，属性相互关系强调不够，容易导致决策树中子树的重复或有些属性在决策树的某一路径上被检验多次。

(4)抗噪性差，训练例子中正例和反例的比例较难控制。

于是Quilan改进了ID3，提出了C4.5算法。C4.5算法现在已经成为最经典的决策树构造算法，排名数据挖掘十大经典算法之首，下一篇文章将重点讨论。

决策树的经典构造算法——C4.5（WEKA中称J48）

由于ID3算法在实际应用中存在一些问题，于是Quilan提出了C4.5算法，严格上说C4.5只能是ID3的一个改进算法。

C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进：

1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；

2) 在树构造过程中进行剪枝；

3) 能够完成对连续属性的离散化处理；

4) 能够对不完整数据进行处理。

C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。

另外，无论是ID3还是C4.5最好在小数据集上使用，决策树分类一般只试用于小数据。当属性取值很多时最好选择C4.5算法，ID3得出的效果会非常差。

id3决策树java的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于、id3决策树java的信息别忘了在本站进行查找喔。