决策树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值最大，画出的树如下：

实现ID3决策树学习算法

这里有些。

Diversity(整体)-diversity(左节点)-diversity(右节点)，值越大，分割就越好。

三种diversity的指标：

1. min(P(c1),P(c2))

2. 2P(c1)P(c2)

3. [P(c1)logP(c1)]+[P(c2)logP(c2)]

这几个参数有相同的性质：当其中的类是均匀分布的时候，值最大；当有一个类的个数为0的时候，值为0。

选择分割的时候，对每个字段都考虑；对每个字段中的值先排序，然后再一一计算。最后选出最佳的分割。

树的生成：

错误率的衡量：最初生成的树中也是有错误率的！因为有些叶子节点并不是“Pure”的。

树的修剪：是不是当所以的叶子都很纯是，这棵树就能工作的很好呢?

修剪的要点是：应该回溯多少、如何从众多的子树总寻找最佳的。

1) 鉴别生成候选子树 ：使用一个调整的错误率。AE(T)=E(T)+aleaf_count(T)。一步步的生成一些候选子树。

2) 对子树的评估：通过test set找到最佳子树

3) 对最佳子树进行评估：使用evaluation set。

4) 考虑代价(cost)的问题

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划分的信息增益

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

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

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

一、实验目的

1、理解分类

2、掌握分类挖掘算法ID3

3、为改进ID3打下基础

二、实验内容

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

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

3、给出分类规则

三、实验原理

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

新闻名称：包含id3决策树代码java的词条
本文来源：http://myzitong.com/article/dodogoo.html