id3决策树代码java的简单介绍

决策树Decision Trees - Introduction(ID3)

你在一生中遇到各种不同的人，在有了一些经验后，你知道自己喜欢哪种类型的人。于是在遇见新人类时，很多时候你可以判断自己是否喜欢它们，通过经验知道的，然后不通过大脑感觉。我们通过建立相似的机制。

我们来假设你遇到了一些人，你不希望vmpires成为你的未来的朋友，所以你做出以下的列表，判断他们是否是吸血鬼。

观察这个数据集后，我们画出一个树来判断是否是吸血鬼

因为画出这棵树可以帮助我们做出选择，所以我们称之为“Decision Tree”，这棵树必须满足所给数据集中的所有数据，并且我们也希望它可以满足以后的所有输入。

但如何构造出这棵树呢？以上的树是通过所及观察画出的。

通过观察我们得出以下结论：

        所有with pale complexion的人都不是吸血鬼

        所有有ruddy complexion和吃garlic的人都不是吸血鬼，如果他们不吃大蒜则是吸血鬼

        所有有average complexion的人，并且他们没有影子或不知道是否有影子的是吸血鬼，否则如果有影子则不是吸血鬼

这是我们通过简单数据判断出的决策树，这种随机的猜测在巨大的数据集上是行不通的，我们需要更加系统的步骤来解决这个问题。

那我们来用贪心算法尝试解决一下！

首先通过看数据集，决定选择哪一个属性作为树的根节点.... 这是个 二分类问题 ，所以在决策树的最后我们可以有两种可能的解决方式，所以每个输入的例子可以分类为真或假两类。这里用P表示positive，是吸血鬼，N表示negative，不是吸血鬼。

我们想要那些把数据分为同类的属性，也就是说，P或N各自存在于一个子集，也就可以区分是否是吸血鬼，这就将是叶子节点。

检查每个特征，观察哪一个在相同集合中有最多的元素，此时找到了shadow？这个属性

shadow这个属性，可以决定一个人是否是吸血鬼，但是如果不清楚是否有shadow则不能判断这个人是否是吸血鬼，我们需要另一个特征在shadow=？时将数据集分开。

当shadow=？时，我们分析得知garlic这个属性将其划分为同质子集，区分了最多的元素。

此时的决策树长这样：

这棵树比我们之前随机选特征得出的树更加简单，所以我们发现贪心算法帮助我们获得更好的结果。但这是正确的方式去做吗？

不是，因为数据集很庞大，我们不需要最终将属性区分到同质集中，我们可能会发现所有的属性元素在同质集中是零个。

现在我们用ID3算法生成决策树，这运用了 Information gain 这个概念，是通过 entropy熵 定义的，熵是在信息理论学中的根本quantity

想象这有通过某个特征区分的两个分类

我们观察到，左边的P和N有相同的数量，所以这不能给我们提供任何判断的提示，但是右边的P大于N，所以它可能会指引我们到P，所以这两个中我们会考虑右边的分类。

所以，我们并不直接给它们打零分，我们说，如果一个分类中P和N有相同的数量的有更高的熵值，最混乱，另一个分类中只有P或只有N，它的熵最低，值为0，表示最不混乱。以下我们可以看到这个图，P/（P+N）和熵值的图

所以，当P=N时，也就是P/(P+N)=0.5时，熵值最大为1，如果P=K(某个int值)N=0，熵值为0

那计算出这个熵值，得出这个图有没有数学方程呢？幸运的是，这个曲线可以通过以下方差获得：

我们可以把x的取值 代入这个熵的形式

公式中的P 和 N就是根据该特征划分的Ps和Ns的数量，同时我们也想从属性中获取信息熵Information gain，也定义为IG。

举个例子

知道了信息熵和熵之后，我们来构建决策树

我们计算出最大的IG信息熵是shadow属性，将其作为根节点

此时我们需要决定另一个属性划分Shadow=？的子集

接着算出garlic的 IG值最大，画出的树如下：

相关问答

Q1: 决策树之ID3算法及其Python实现

决策树之ID3算法及其Python实现

1. 决策树背景知识

??决策树是数据挖掘中最重要且最常用id3决策树代码java的方法之一，主要应用于数据挖掘中的分类和预测。决策树是知识的一种呈现方式，决策树中从顶点到每个结点的路径都是一条分类规则。决策树算法最先基于信息论发展起来，经过几十年发展，目前常用的算法有id3决策树代码java：ID3、C4.5、CART算法等。

2. 决策树一般构建过程

??构建决策树是一个自顶向下的过程。树的生长过程是一个不断把数据进行切分细分的过程，每一次切分都会产生一个数据子集对应的节点。从包含所有数据的根节点开始，根据选取分裂属性的属性值把训练集划分成不同的数据子集，生成由每个训练数据子集对应新的非叶子节点。对生成的非叶子节点再重复以上过程，直到满足特定的终止条件，停止对数据子集划分，生成数据子集对应的叶子节点，即所需类别。测试集在决策树构建完成后检验其性能。如果性能不达标，id3决策树代码java我们需要对决策树算法进行改善，直到达到预期的性能指标。

??注：分裂属性的选取是决策树生产过程中的关键，它决定id3决策树代码java了生成的决策树的性能、结构。分裂属性选择的评判标准是决策树算法之间的根本区别。

3. ID3算法分裂属性的选择——信息增益

??属性的选择是决策树算法中的核心。是对决策树的结构、性能起到决定性的作用。ID3算法基于信息增益的分裂属性选择。基于信息增益的属性选择是指以信息熵的下降速度作为选择属性的方法。它以的信息论为基础，选择具有最高信息增益的属性作为当前节点的分裂属性。选择该属性作为分裂属性后，使得分裂后的样本的信息量最大，不确定性最小，即熵最小。

??信息增益的定义为变化前后熵的差值，而熵的定义为信息的期望值，因此在了解熵和信息增益之前，我们需要了解信息的定义。

??信息：分类标签xi 在样本集 S 中出现的频率记为 p(xi)，则 xi 的信息定义为：?log2p(xi) 。

??分裂之前样本集的熵：E(S)=?∑Ni=1p(xi)log2p(xi)，其中 N 为分类标签的个数。

??通过属性A分裂之后样本集的熵：EA(S)=?∑mj=1|Sj||S|E(Sj)，其中 m 代表原始样本集通过属性A的属性值划分为 m 个子样本集，|Sj| 表示第j个子样本集中样本数量，|S| 表示分裂之前数据集中样本总数量。

??通过属性A分裂之后样本集的信息增益：InfoGain(S,A)=E(S)?EA(S)

??注：分裂属性的选择标准为：分裂前后信息增益越大越好，即分裂后的熵越小越好。

4. ID3算法

??ID3算法是一种基于信息增益属性选择的决策树学习方法。核心思想是：通过计算属性的信息增益来选择决策树各级节点上的分裂属性，使得在每一个非叶子节点进行测试时，获得关于被测试样本最大的类别信息。基本方法是：计算所有的属性，选择信息增益最大的属性分裂产生决策树节点，基于该属性的不同属性值建立各分支，再对各分支的子集递归调用该方法建立子节点的分支，直到所有子集仅包括同一类别或没有可分裂的属性为止。由此得到一棵决策树，可用来对新样本数据进行分类。

ID3算法流程：

(1) 创建一个初始节点。如果该节点中的样本都在同一类别，则算法终止，把该节点标记为叶节点，并用该类别标记。

(2) 否则，依据算法选取信息增益最大的属性，该属性作为该节点的分裂属性。

(3) 对该分裂属性中的每一个值，延伸相应的一个分支，并依据属性值划分样本。

(4) 使用同样的过程，自顶向下的递归，直到满足下面三个条件中的一个时就停止递归。

??A、待分裂节点的所有样本同属于一类。

??B、训练样本集中所有样本均完成分类。

??C、所有属性均被作为分裂属性执行一次。若此时，叶子结点中仍有属于不同类别的样本时，选取叶子结点中包含样本最多的类别，作为该叶子结点的分类。

ID3算法优缺点分析

优点：构建决策树的速度比较快，算法实现简单，生成的规则容易理解。

缺点：在属性选择时，倾向于选择那些拥有多个属性值的属性作为分裂属性，而这些属性不一定是最佳分裂属性；不能处理属性值连续的属性；无修剪过程，无法对决策树进行优化，生成的决策树可能存在过度拟合的情况。

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

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

一、实验目的

1、理解分类

2、掌握分类挖掘算法ID3

3、为改进ID3打下基础

二、实验内容

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

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

3、给出分类规则

三、实验原理

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

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