id3算法拟合

⑴ 决策树原理及算法比较

决策树是什么？

    和线性回归一样是一种模型，内部节点和叶节点。实现分类，内部节点和叶节点通过有向线（分类规      则）连接起来

决策树的目标是什么？

    决策树通过对数据复杂度的计算，建立特征分类标准，确定最佳分类特征。

    表现为“熵”（entropy）和信息增益（information gain），基于决策树思想的三种算法：ID3，C4.5,CART算法，三种算法的信息衡量的指标也不同.

    熵来表示信息的复杂度，熵越大，信息也就越复杂，公式如下：

那些算法能够实现决策树？

    在决策树构建过程中，什么是比较重要的。特征选择（按照熵变计算），算法产生最重要的部分，

决策树中叶节点的分类比较纯，

节点顺序的排列规则：

熵变：

数据的预处理：

改进思路一般有两个1，换算法；2，调参数

做好数据的预处理：

1，做好特征选择；

2，做好数据离散化、异常值处理、缺失填充

分类器：

在决策树中，从根到达任意一个叶节点的之间最长路径的长度，表示对应的算法排序中最坏情况下的比较次数。这样一个比较算法排序中的最坏情况的比较次数就与其决策树的高度相同，同时如果决策树中每种排列以可达叶子的形式出现，那么关于其决策树高度的下界也就是关于比较排序算法运行时间的下界，

ID3算法存在的缺点：

    1，ID3算法在选择根节点和内部节点分支属性时，采用信息增益作为评价标准。信息增益的缺点是倾向于选择取值较多的属性

    2，当数据为连续性变量的时候，ID3算法就不是一个合理的算法的模型了

C4.5信息增益比率，

     1，在信息增益的基础上除以split-info，是将信息增益改为信息增益比，以解决取值较多的属性的问题，另外它还可以处理连续型属性，其判别标准是θ，

      2，C4.5算法利用增益/熵值，克服了树生长的过程中，总是‘贪婪’选择变量分类多的进行分类

      3，处理来内需型变量，C4.5的分类树的分支就是两条

衡量指标：

（1）信息增益

基于ID3算法的信息增益对于判定连续型变量的时候病不是最优选择，C4.5算法用了信息增益率这个概念。

分类信息类的定义如下：

这个值表示将训练数据集D划分成对应属性A测试的V个输出v个划分产生的信息，信息增益率定义为：

选择最大信息增益率的属性作为分裂属性

Gini指标，CART

表明样本的“纯净度”。Gini系数避免了信息增益产生的问题，

过拟合问题，非常好的泛化能力，有很好的推广能力

Gini系数的计算：

在分类问题中，假设有k个类，样本点属于第k类的概率为Pk，则概率分布的gini指数的定义为：

如果样本集合D根据某个特征A被分割为D1，D2两个部分，那么在特征A的提哦啊见下，集合D的gini指数的定义为：

Gini指数代表特征A不同分组下的数据集D的不确定性，gini指数越大，样本集合的不确定性也就越大，这一点和熵的概念相类似

决策树原理介绍：

第三步：对于每个属性执行划分：

（1）该属性为离散型变量

记样本中的变量分为m中

穷举m种取值分为两类的划分

对上述所有划分计算GINI系数

（2）该属性为连续型变量

将数据集中从小到大划分

按顺序逐一将两个相临值的均值作为分割点

对上述所有划分计算GINI系数

学历的划分使得顺序的划分有个保证，化为连续型变量处理。

决策树的生成算法分为两个步骤：

预剪枝和后剪枝  CCP（cost and complexity）算法：在树变小和变大的的情况有个判断标准。误差率增益值：α值为误差的变化

决策树的终止条件：

      1，某一个节点的分支所覆盖的样本都是同一类的时候

      2，某一个分支覆盖的样本的个数如果小于一个阈值，那么也可以产生叶子节点，从而终止Tree-Growth

确定叶子结点的类：

      1，第一种方式，叶子结点覆盖的样本都属于同一类

      2， 叶子节点覆盖的样本未必是同一类，所占的大多数，那么该叶子节点的类别就是那个占大多数的类

⑵ 什么是ID3算法

ID3算法是由Quinlan首先提出的。该算法是以信息论为基础，以信息熵和信息增益度为衡量标准，从而实现对数据的归纳分类。以下是一些信息论的基本概念：
定义1：若存在n个相同概率的消息，则每个消息的概率p是1/n，一个消息传递的信息量为-Log2(1/n)
定义2：若有n个消息，其给定概率分布为P=(p1,p2…pn)，则由该分布传递的信息量称为P的熵，记为
。
定义3：若一个记录集合T根据类别属性的值被分成互相独立的类C1C2..Ck，则识别T的一个元素所属哪个类所需要的信息量为Info(T)=I(p)，其中P为C1C2…Ck的概率分布，即P=(|C1|/|T|,…..|Ck|/|T|)
定义4：若我们先根据非类别属性X的值将T分成集合T1,T2…Tn，则确定T中一个元素类的信息量可通过确定Ti的加权平均值来得到，即Info(Ti)的加权平均值为：
Info(X, T)=(i=1 to n 求和)((|Ti|/|T|)Info(Ti))
定义5：信息增益度是两个信息量之间的差值，其中一个信息量是需确定T的一个元素的信息量，另一个信息量是在已得到的属性X的值后需确定的T一个元素的信息量，信息增益度公式为：
Gain(X, T)=Info(T)-Info(X, T)
ID3算法计算每个属性的信息增益，并选取具有最高增益的属性作为给定集合的测试属性。对被选取的测试属性创建一个节点，并以该节点的属性标记，对该属性的每个值创建一个分支据此划分样本.
数据描述
所使用的样本数据有一定的要求,ID3是:
描述-属性-值相同的属性必须描述每个例子和有固定数量的价值观。
预定义类-实例的属性必须已经定义的,也就是说,他们不是学习的ID3。
离散类-类必须是尖锐的鲜明。连续类分解成模糊范畴(如金属被“努力,很困难的,灵活的,温柔的,很软”都是不可信的。
足够的例子——因为归纳概括用于(即不可查明)必须选择足够多的测试用例来区分有效模式并消除特殊巧合因素的影响。
属性选择
ID3决定哪些属性如何是最好的。一个统计特性,被称为信息增益,使用熵得到给定属性衡量培训例子带入目标类分开。信息增益最高的信息(信息是最有益的分类)被选择。为了明确增益,我们首先从信息论借用一个定义，叫做熵。每个属性都有一个熵。

⑶ 简述ID3算法基本原理和步骤

1.基本原理：
以信息增益/信息熵为度量，用于决策树结点的属性选择的标准，每次优先选取信息量最多（信息增益最大）的属性，即信息熵值最小的属性，以构造一颗熵值下降最快的决策树，到叶子节点处的熵值为0。（信息熵 无条件熵 条件熵 信息增益 请查找其他资料理解）
决策树将停止生长条件及叶子结点的类别取值：
①数据子集的每一条数据均已经归类到每一类，此时，叶子结点取当前样本类别值。
②数据子集类别仍有混乱，但已经找不到新的属性进行结点分解，此时，叶子结点按当前样本中少数服从多数的原则进行类别取值。
③数据子集为空，则按整个样本中少数服从多数的原则进行类别取值。

步骤：
理解了上述停止增长条件以及信息熵，步骤就很简单

⑷ 5.10 决策树与ID3算法

https://blog.csdn.net/dorisi_h_n_q/article/details/82787295

决策树（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算法及其python实现

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

1. 决策树背景知识
??决策树是数据挖掘中最重要且最常用的方法之一，主要应用于数据挖掘中的分类和预测。决策树是知识的一种呈现方式，决策树中从顶点到每个结点的路径都是一条分类规则。决策树算法最先基于信息论发展起来，经过几十年发展，目前常用的算法有：ID3、C4.5、CART算法等。
2. 决策树一般构建过程
??构建决策树是一个自顶向下的过程。树的生长过程是一个不断把数据进行切分细分的过程，每一次切分都会产生一个数据子集对应的节点。从包含所有数据的根节点开始，根据选取分裂属性的属性值把训练集划分成不同的数据子集，生成由每个训练数据子集对应新的非叶子节点。对生成的非叶子节点再重复以上过程，直到满足特定的终止条件，停止对数据子集划分，生成数据子集对应的叶子节点，即所需类别。测试集在决策树构建完成后检验其性能。如果性能不达标，我们需要对决策树算法进行改善，直到达到预期的性能指标。
??注：分裂属性的选取是决策树生产过程中的关键，它决定了生成的决策树的性能、结构。分裂属性选择的评判标准是决策树算法之间的根本区别。
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算法优缺点分析
优点：构建决策树的速度比较快，算法实现简单，生成的规则容易理解。
缺点：在属性选择时，倾向于选择那些拥有多个属性值的属性作为分裂属性，而这些属性不一定是最佳分裂属性；不能处理属性值连续的属性；无修剪过程，无法对决策树进行优化，生成的决策树可能存在过度拟合的情况。

⑹ 用python实现红酒数据集的ID3,C4.5和CART算法

ID3算法介绍
ID3算法全称为迭代二叉树3代算法（Iterative Dichotomiser 3）
该算法要先进行特征选择，再生成决策树，其中特征选择是基于“信息增益”最大的原则进行的。
但由于决策树完全基于训练集生成的，有可能对训练集过于“依赖”，即产生过拟合现象。因此在生成决策树后，需要对决策树进行剪枝。剪枝有两种形式，分别为前剪枝（Pre-Pruning）和后剪枝（Post-Pruning），一般采用后剪枝。
信息熵、条件熵和信息增益
信息熵：来自于香农定理，表示信息集合所含信息的平均不确定性。信息熵越大，表示不确定性越大，所含的信息量也就越大。
设x 1 , x 2 , x 3 , . . . x n {x_1, x_2, x_3, ...x_n}x
1

,x
2

,x
3

,...x
n

为信息集合X的n个取值，则x i x_ix
i

的概率：
P ( X = i ) = p i , i = 1 , 2 , 3 , . . . , n P(X=i) = p_i, i=1,2,3,...,n
P(X=i)=p
i

,i=1,2,3,...,n

信息集合X的信息熵为：
H ( X ) = − ∑ i = 1 n p i log ⁡ p i H(X) =- \sum_{i=1}^{n}{p_i}\log{p_i}
H(X)=−
i=1
∑
n

p
i

logp
i

条件熵：指已知某个随机变量的情况下，信息集合的信息熵。
设信息集合X中有y 1 , y 2 , y 3 , . . . y m {y_1, y_2, y_3, ...y_m}y
1

,y
2

,y
3

,...y
m

组成的随机变量集合Y，则随机变量（X，Y）的联合概率分布为
P ( x = i , y = j ) = p i j P(x=i,y=j) = p_{ij}
P(x=i,y=j)=p
ij

条件熵：
H ( X ∣ Y ) = ∑ j = 1 m p ( y j ) H ( X ∣ y j ) H(X|Y) = \sum_{j=1}^m{p(y_j)H(X|y_j)}
H(X∣Y)=
j=1
∑
m

p(y
j

)H(X∣y
j

)
由
H ( X ∣ y j ) = − ∑ j = 1 m p ( y j ) ∑ i = 1 n p ( x i ∣ y j ) log ⁡ p ( x i ∣ y j ) H(X|y_j) = - \sum_{j=1}^m{p(y_j)}\sum_{i=1}^n{p(x_i|y_j)}\log{p(x_i|y_j)}
H(X∣y
j

)=−
j=1
∑
m

p(y
j

)
i=1
∑
n

p(x
i

∣y
j

)logp(x
i

∣y
j

)
和贝叶斯公式：
p ( x i y j ) = p ( x i ∣ y j ) p ( y j ) p(x_iy_j) = p(x_i|y_j)p(y_j)
p(x
i

y
j

)=p(x
i

∣y
j

)p(y
j

)
可以化简条件熵的计算公式为:
H ( X ∣ Y ) = ∑ j = 1 m ∑ i = 1 n p ( x i , y j ) log ⁡ p ( x i ) p ( x i , y j ) H(X|Y) = \sum_{j=1}^m \sum_{i=1}^n{p(x_i, y_j)\log\frac{p(x_i)}{p(x_i, y_j)}}
H(X∣Y)=
j=1
∑
m

i=1
∑
n

p(x
i

,y
j

)log
p(x
i

,y
j

)
p(x
i

)

信息增益：信息熵-条件熵，用于衡量在知道已知随机变量后，信息不确定性减小越大。
d ( X , Y ) = H ( X ) − H ( X ∣ Y ) d(X,Y) = H(X) - H(X|Y)
d(X,Y)=H(X)−H(X∣Y)

python代码实现
import numpy as np
import math

def calShannonEnt(dataSet):
""" 计算信息熵 """
labelCountDict = {}
for d in dataSet:
label = d[-1]
if label not in labelCountDict.keys():
labelCountDict[label] = 1
else:
labelCountDict[label] += 1
entropy = 0.0
for l, c in labelCountDict.items():
p = 1.0 * c / len(dataSet)
entropy -= p * math.log(p, 2)
return entropy

def filterSubDataSet(dataSet, colIndex, value):
"""返回colIndex特征列label等于value，并且过滤掉改特征列的数据集"""
subDataSetList = []
for r in dataSet:
if r[colIndex] == value:
newR = r[:colIndex]
newR = np.append(newR, (r[colIndex + 1:]))
subDataSetList.append(newR)
return np.array(subDataSetList)

def chooseFeature(dataSet):
""" 通过计算信息增益选择最合适的特征"""
featureNum = dataSet.shape[1] - 1
entropy = calShannonEnt(dataSet)
bestInfoGain = 0.0
bestFeatureIndex = -1
for i in range(featureNum):
uniqueValues = np.unique(dataSet[:, i])
condition_entropy = 0.0

for v in uniqueValues: #计算条件熵
subDataSet = filterSubDataSet(dataSet, i, v)
p = 1.0 * len(subDataSet) / len(dataSet)
condition_entropy += p * calShannonEnt(subDataSet)
infoGain = entropy - condition_entropy #计算信息增益

if infoGain >= bestInfoGain: #选择最大信息增益
bestInfoGain = infoGain
bestFeatureIndex = i
return bestFeatureIndex

def creatDecisionTree(dataSet, featNames):
""" 通过训练集生成决策树 """
featureName = featNames[:] # 拷贝featNames，此处不能直接用赋值操作，否则新变量会指向旧变量的地址
classList = list(dataSet[:, -1])
if len(set(classList)) == 1: # 只有一个类别
return classList[0]
if dataSet.shape[1] == 1: #当所有特征属性都利用完仍然无法判断样本属于哪一类，此时归为该数据集中数量最多的那一类
return max(set(classList), key=classList.count)

bestFeatureIndex = chooseFeature(dataSet) #选择特征
bestFeatureName = featNames[bestFeatureIndex]
del featureName[bestFeatureIndex] #移除已选特征列
decisionTree = {bestFeatureName: {}}

featureValueUnique = sorted(set(dataSet[:, bestFeatureIndex])) #已选特征列所包含的类别， 通过递归生成决策树
for v in featureValueUnique:
FeatureName = featureName[:]
subDataSet = filterSubDataSet(dataSet, bestFeatureIndex, v)
decisionTree[bestFeatureName][v] = creatDecisionTree(subDataSet, FeatureName)
return decisionTree

def classify(decisionTree, featnames, featList):
""" 使用训练所得的决策树进行分类 """
classLabel = None
root = decisionTree.keys()[0]
firstGenDict = decisionTree[root]
featIndex = featnames.index(root)
for k in firstGenDict.keys():
if featList[featIndex] == k:
if isinstance(firstGenDict[k], dict): #若子节点仍是树，则递归查找
classLabel = classify(firstGenDict[k], featnames, featList)
else:
classLabel = firstGenDict[k]
return classLabel
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
下面用鸢尾花数据集对该算法进行测试。由于ID3算法只能用于标称型数据，因此用在对连续型的数值数据上时，还需要对数据进行离散化，离散化的方法稍后说明，此处为了简化，先使用每一种特征所有连续性数值的中值作为分界点，小于中值的标记为1，大于中值的标记为0。训练1000次，统计准确率均值。

from sklearn import datasets
from sklearn.model_selection import train_test_split

iris = datasets.load_iris()
data = np.c_[iris.data, iris.target]

scoreL = []
for i in range(1000): #对该过程进行10000次
trainData, testData = train_test_split(data) #区分测试集和训练集

featNames = iris.feature_names[:]
for i in range(trainData.shape[1] - 1): #对训练集每个特征，以中值为分界点进行离散化
splitPoint = np.mean(trainData[:, i])
featNames[i] = featNames[i]+'<='+'{:.3f}'.format(splitPoint)
trainData[:, i] = [1 if x <= splitPoint else 0 for x in trainData[:, i]]
testData[:, i] = [1 if x <= splitPoint else 0 for x in testData[:, i]]

decisionTree = creatDecisionTree(trainData, featNames)
classifyLable = [classify(decisionTree, featNames, td) for td in testData]
scoreL.append(1.0 * sum(classifyLable == testData[:, -1]) / len(classifyLable))
print 'score: ', np.mean(scoreL)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
输出结果为：score: 0.7335，即准确率有73%。每次训练和预测的准确率分布如下：

数据离散化
然而，在上例中对特征值离散化的划分点实际上过于“野蛮”，此处介绍一种通过信息增益最大的标准来对数据进行离散化。原理很简单，当信息增益最大时，说明用该点划分能最大程度降低数据集的不确定性。
具体步骤如下：

对每个特征所包含的数值型特征值排序
对相邻两个特征值取均值，这些均值就是待选的划分点
用每一个待选点把该特征的特征值划分成两类，小于该特征点置为1， 大于该特征点置为0，计算此时的条件熵，并计算出信息增益
选择信息使信息增益最大的划分点进行特征离散化
实现代码如下：

def filterRawData(dataSet, colIndex, value, tag):
""" 用于把每个特征的连续值按照区分点分成两类，加入tag参数，可用于标记筛选的是哪一部分数据"""
filterDataList = []
for r in dataSet:
if (tag and r[colIndex] <= value) or ((not tag) and r[colIndex] > value):
newR = r[:colIndex]
newR = np.append(newR, (r[colIndex + 1:]))
filterDataList.append(newR)
return np.array(filterDataList)

def dataDiscretization(dataSet, featName):
""" 对数据每个特征的数值型特征值进行离散化 """
featureNum = dataSet.shape[1] - 1
entropy = calShannonEnt(dataSet)

for featIndex in range(featureNum): #对于每一个特征
uniqueValues = sorted(np.unique(dataSet[:, featIndex]))
meanPoint = []

for i in range(len(uniqueValues) - 1): # 求出相邻两个值的平均值
meanPoint.append(float(uniqueValues[i+1] + uniqueValues[i]) / 2.0)
bestInfoGain = 0.0
bestMeanPoint = -1
for mp in meanPoint: #对于每个划分点
subEntropy = 0.0 #计算该划分点的信息熵
for tag in range(2): #分别划分为两类
subDataSet = filterRawData(dataSet, featIndex, mp, tag)
p = 1.0 * len(subDataSet) / len(dataSet)
subEntropy += p * calShannonEnt(subDataSet)

## 计算信息增益
infoGain = entropy - subEntropy
## 选择最大信息增益
if infoGain >= bestInfoGain:
bestInfoGain = infoGain
bestMeanPoint = mp
featName[featIndex] = featName[featIndex] + "<=" + "{:.3f}".format(bestMeanPoint)
dataSet[:, featIndex] = [1 if x <= bestMeanPoint else 0 for x in dataSet[:, featIndex]]
return dataSet, featName
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
重新对数据进行离散化，并重复该步骤1000次，同时用sklearn中的DecisionTreeClassifier对相同数据进行分类，分别统计平均准确率。运行代码如下:

from sklearn.tree import DecisionTreeClassifier
import matplotlib.pyplot as plt
scoreL = []
scoreL_sk = []
for i in range(1000): #对该过程进行1000次
featNames = iris.feature_names[:]
trainData, testData = train_test_split(data) #区分测试集和训练集
trainData_tmp = .(trainData)
testData_tmp = .(testData)
discritizationData, discritizationFeatName= dataDiscretization(trainData, featNames) #根据信息增益离散化
for i in range(testData.shape[1]-1): #根据测试集的区分点离散化训练集
splitPoint = float(discritizationFeatName[i].split('<=')[-1])
testData[:, i] = [1 if x<=splitPoint else 0 for x in testData[:, i]]
decisionTree = creatDecisionTree(trainData, featNames)
classifyLable = [classify(decisionTree, featNames, td) for td in testData]
scoreL.append(1.0 * sum(classifyLable == testData[:, -1]) / len(classifyLable))

clf = DecisionTreeClassifier('entropy')
clf.fit(trainData[:, :-1], trainData[:, -1])
clf.predict(testData[:, :-1])
scoreL_sk.append(clf.score(testData[:, :-1], testData[:, -1]))

print 'score: ', np.mean(scoreL)
print 'score-sk: ', np.mean(scoreL_sk)
fig = plt.figure(figsize=(10, 4))
plt.subplot(1,2,1)
pd.Series(scoreL).hist(grid=False, bins=10)
plt.subplot(1,2,2)
pd.Series(scoreL_sk).hist(grid=False, bins=10)
plt.show()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
两者准确率分别为：
score: 0.7037894736842105
score-sk: 0.7044736842105263

准确率分布如下：

两者的结果非常一样。
（但是。。为什么根据信息熵离散化得到的准确率比直接用均值离散化的准确率还要低啊？？哇的哭出声。。）

最后一次决策树图形如下：

决策树剪枝
由于决策树是完全依照训练集生成的，有可能会有过拟合现象，因此一般会对生成的决策树进行剪枝。常用的是通过决策树损失函数剪枝，决策树损失函数表示为:
C a ( T ) = ∑ t = 1 T N t H t ( T ) + α ∣ T ∣ C_a(T) = \sum_{t=1}^TN_tH_t(T) +\alpha|T|
C
a

(T)=
t=1
∑
T

N
t

H
t

(T)+α∣T∣

其中，H t ( T ) H_t(T)H
t

(T)表示叶子节点t的熵值，T表示决策树的深度。前项∑ t = 1 T N t H t ( T ) \sum_{t=1}^TN_tH_t(T)∑
t=1
T

N
t

H
t

(T)是决策树的经验损失函数当随着T的增加，该节点被不停的划分的时候，熵值可以达到最小，然而T的增加会使后项的值增大。决策树损失函数要做的就是在两者之间进行平衡，使得该值最小。
对于决策树损失函数的理解，如何理解决策树的损失函数? - 陶轻松的回答 - 知乎这个回答写得挺好，可以按照答主的思路理解一下

C4.5算法
ID3算法通过信息增益来进行特征选择会有一个比较明显的缺点：即在选择的过程中该算法会优先选择类别较多的属性（这些属性的不确定性小，条件熵小，因此信息增益会大），另外，ID3算法无法解决当每个特征属性中每个分类都只有一个样本的情况（此时每个属性的条件熵都为0）。
C4.5算法ID3算法的改进，它不是依据信息增益进行特征选择，而是依据信息增益率，它添加了特征分裂信息作为惩罚项。定义分裂信息：
S p l i t I n f o ( X , Y ) = − ∑ i n ∣ X i ∣ ∣ X ∣ log ⁡ ∣ X i ∣ ∣ X ∣ SplitInfo(X, Y) =-\sum_i^n\frac{|X_i|}{|X|}\log\frac{|X_i|}{|X|}
SplitInfo(X,Y)=−
i
∑
n

∣X∣
∣X
i

∣

log
∣X∣
∣X
i

∣

则信息增益率为：
G a i n R a t i o ( X , Y ) = d ( X , Y ) S p l i t I n f o ( X , Y ) GainRatio(X,Y)=\frac{d(X,Y)}{SplitInfo(X, Y)}
GainRatio(X,Y)=
SplitInfo(X,Y)
d(X,Y)

关于ID3和C4.5算法
在学习分类回归决策树算法时，看了不少的资料和博客。关于这两个算法，ID3算法是最早的分类算法，这个算法刚出生的时候其实带有很多缺陷：

无法处理连续性特征数据
特征选取会倾向于分类较多的特征
没有解决过拟合的问题
没有解决缺失值的问题
即该算法出生时是没有带有连续特征离散化、剪枝等步骤的。C4.5作为ID3的改进版本弥补列ID3算法不少的缺陷：

通过信息最大增益的标准离散化连续的特征数据
在选择特征是标准从“最大信息增益”改为“最大信息增益率”
通过加入正则项系数对决策树进行剪枝
对缺失值的处理体现在两个方面：特征选择和生成决策树。初始条件下对每个样本的权重置为1。
特征选择：在选取最优特征时，计算出每个特征的信息增益后，需要乘以一个**“非缺失值样本权重占总样本权重的比例”**作为系数来对比每个特征信息增益的大小
生成决策树：在生成决策树时，对于缺失的样本我们按照一定比例把它归属到每个特征值中，比例为该特征每一个特征值占非缺失数据的比重
关于C4.5和CART回归树
作为ID3的改进版本，C4.5克服了许多缺陷，但是它自身还是存在不少问题：

C4.5的熵运算中涉及了对数运算，在数据量大的时候效率非常低。
C4.5的剪枝过于简单
C4.5只能用于分类运算不能用于回归
当特征有多个特征值是C4.5生成多叉树会使树的深度加深
————————————————
版权声明：本文为CSDN博主“Sarah Huang”的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_44794704/article/details/89406612

⑺ id3算法是什么

ID3算法是一种贪心算法，用来构造决策树。ID3算法起源于概念学习系统（CLS），以信息熵的下降速度为选取测试属性的标准，即在每个节点选取还尚未被用来划分的具有最高信息增益的属性作为划分标准，然后继续这个过程，直到生成的决策树能完美分类训练样例。

ID3算法的背景

ID3算法最早是由罗斯昆（J. Ross Quinlan）于1975年在悉尼大学提出的一种分类预测算法，算法的核心是“信息熵”。ID3算法通过计算每个属性的信息增益，认为信息增益高的是好属性，每次划分选取信息增益最高的属性为划分标准，重复这个过程，直至生成一个能完美分类训练样例的决策树。

⑻ 算法入门

ROC曲线（受试者工作特征曲线）的横坐标为假阳性率（分错的负样本占所有负样本比率），纵坐标为真阳性率（分对的正样本占所有正样本比率）。通过动态地调整分类模型的分类阈值，可以在ROC图上绘制出每一个分类阈值对应的两个坐标值，再连接所有点绘制出模型的ROC曲线。AUC指ROC曲线下面积的大小，该指标能够量化地反映基于ROC曲线的模型性能，AUC的取值一般都在0.5～1之间，值越大，说明分类器越可能把真正的正样本排在前面，分类性能越好。相比较P-R曲线，ROC曲线在正负样本的分布发生变化时，形状能够基本保持不变，而P-R曲线一般会发生较剧烈的变化，这个特点可以使得ROC曲线能够尽量降低不同测试集带来的干扰，更加客观地衡量模型本身的性能。在实际中，正负样本数量往往不均衡，因此ROC曲线的适用场景更广泛。

对于任意线性可分的两组点，它们在SVM分类的超平面上的投影都是线性不可分的。由于SVM的分类超平面仅由支持向量决定，可以考虑只含有支持向量的场景：假设存在一个SVM超平面满足投影线性可分，则样本中分属两类的支持向量之间的中垂线所组成的超平面是相较于SVM超平面更优的解，这与SVM超平面为最优分类超平面的假设相违背。

SVM的KKT条件：

结合(3)和(4)，当 时，必有 ，将这一结果与拉格朗日对偶优化问题的公式相比较： ，其中 。除了支持向量之外，其他系数均为0，因此SVM的分类结果仅依赖于支持向量，SVM的分类结果与仅使用支持向量的分类结果一致。

该问题也可以通过凸优化理论中的超平面分离定理解决。

高斯核SVM的预测公式为： ，固定 ，则有 。由于不存在两个点在同一位置，则对于任意点 ，有 .

对于任意 ，取 ，有

所以，对于任意 ，预测结果 与真实标签的距离小于1，所有样本的类别都被正确预测，训练误差为0.

本题等价于找到使训练误差为0的参数，且是SVM模型的一个解。上述所找到的参数可以满足 ，若想成为SVM的解，还需要满足 。

仍然固定 ，则有 . 此时可以把每个 都选择一个很大的值，同时取一个非常小的 ，使得核映射项 非常小，就可以满足题意。

不一定能得到训练误差为0的模型，因为此时优化的目标改变了，当松弛变量模型目标函数参数C选取较小的值时，正则项将占据优化的较大比重，此时一个带有训练误差但是参数较小的点将成为更优的结果。

如果把一个事件的几率定义为该事件发生与该事件不发生的概率比值，根据逻辑回归的公式 ，逻辑回归可以看作是对于事件"y=1|x"的对数几率的线性回归，所以有回归的名称。但是逻辑回归的因变量是离散的，处理的是分类问题；线性回归中的因变量是连续的，处理的是回归问题。逻辑回归与线性回归的相似处是：都使用了极大似然估计，线性回归的最小二乘实际上是自变量和超参数确定、因变量服从正态分布的假设下使用极大似然估计的一个化简，逻辑回归中通过对似然函数的学习来得到最佳超参数；二者在求解超参数的过程中，都可以使用梯度下降法。

如果一个样本只对应于一个标签，可以假设每个样本属于不同标签的概率服从于几何分布，使用多项逻辑回归(Softmax Regression)来进行分类：
当存在样本可能属于多个标签的情况时，可以训练k个二分类的逻辑回归分类器，第i个分类器用于区分每个样本是否可以归为第i类。

ID3会倾向于选取取值较多的特征，因为信息增益反应的是给定条件以后不确定性减少的程度，特征取值越多就意味着确定性更高，也就是条件熵越小，信息增益越大，C4.5通过引入信息增益比，一定程度对取值比较多的特征进行惩罚，避免ID3出现过拟合的特性，提升模型的泛化能力；ID3只能处理离散变量，而C4.5和CART都可以处理连续变量；ID3和C4.5只能用于分类任务，CART不仅可以分类也可以用于回归；ID3和C4.5可以在每个结点上产生出多叉分支，且每个特征在层级之间不会复用，而CART每个结点只会产生两个分支，且每个特征可以被重复使用；ID3和C4.5通过剪枝来权衡树的准确性与泛化能力，而CART直接利用全部数据发现所有可能的树结构进行对比。

对于给定的一组数据点 ，中心化后表示为 ，其中 ，目标是找到一个投影方向 (单位方向向量)使数据点在其上的投影方差尽可能大。投影之后的均值： 投影之后的方差(均值为0，直接平方)： 其中， 是样本的协方差矩阵，将其写作 ，则有求解最大化问题： 引入拉格朗日乘子，并对 求导令其等于0，可以推出 ，此时 该值为协方差矩阵的最大特征值

LDA的最大化目标： 其中 分别表示两类投影后的方差： 则目标函数可以写成： 定义类间散度矩阵 ，类内散度矩阵 ，最大化 即是对 求偏导且令其等于零： 可以得出 在简化的二分类问题中，可以令 ，则有 这里LDA最大化的目标对应了矩阵 的特征值，而投影方向就是这个特征值对应的特征向量。

PCA为无监督降维算法，LDA为有监督降维算法，两种降维算法的求解过程有很大的相似性，但是对应的原理却有所区别：PCA选择投影后数据方差最大的方向，由于算法无监督，PCA假设方差越大信息量越多，用主成分来表示原始数据可以去除冗余的维度，达到降维；LDA用到了类别标签的信息，选择投影后类内方差小、类间方差大的方向，使得原始数据在这些方向上投影后不同类别尽可能区分开。应用的原则是无监督任务使用PCA，有监督任务使用LDA。

优点：对于大数据集，K均值聚类算法相对是可伸缩和高效的，它的计算复杂度是 接近于线性，其中 是数据对象的数目， 是聚类的簇数， 是迭代的轮数；尽管算法经常以局部最优结束，但一般情况下达到局部最优已经可以满足聚类的需求

缺点：需要人工预先确定初始K值，且该值和真实的数据分布未必吻合；受初值和离群点的影响，每次的结果不稳定；结果通常不是全局最优而是局部最优解，效果受到初始值影响；无法良好地解决数据簇分布差别比较大的情况（比如一类是另一类样本数量的100倍）；不太适用于离散分类；样本点只能被划分到单一的类中

SOM本质上是一个两层的神经网络，包含模拟感知的输入层和模拟大脑皮层的输出层，输出层中神经元的个数通常是聚类的个数。具有保序映射的特点，可以将任意维输入模式在输出层映射为一维或者二维图形，并保持拓扑结构不变，使得输出层神经元的空间位置对应于输入空间的特定域或特征。在SOM中，以获胜神经元为中心，近邻者相互激励，远邻者相互抑制，这种交互作用的方式以曲线可视化则类似于“墨西哥帽”。

输出层神经元数量：和样本的类别数相关。若不清楚样本的类别，则尽可能地设定较多的节点数，以便更好地映射样本的拓扑结构，如果分类过细再酌情减少输出节点。这样可能会带来少量从未更新过权重的“死节点”，但一般可通过重新初始化权重来解决

输出层节点排列：排列形式应尽量直观地反映出实际问题的物理意义。例如，对于一般的分类问题，一个输出节点能代表一个模式类，使用一维线阵；对于颜色空间或者旅行路径问题，二维平面则比较直观

初始化权重：可以随机初始化，但尽量使权值的初始位置与输入样本的大概分布区域充分重合，避免出现大量初始"死节点"。可以从训练集中随机抽取m个输入样本作为初始权重

拓扑领域：设计原则是使领域不断缩小，这样输出平面上相邻神经元对应的权向量之间既有区别又有相当的相似性，从而保证当获胜节点对某一类模式产生最大响应时，其领域节点也能产生较大响应。领域的形状可以是正方形、六边形或者菱形。优势领域的大小用领域的半径表示，通常凭借经验来选择

学习率：学习率为递减函数，训练开始时，学习率可以选取较大的值，之后以较快的速度下降，有利于很快地捕捉到输入向量的大致结构，然后学习率在较小的值上缓降为0，这样可以精细地调整权值使之符合输入空间的样本分布结构。

如果数据基本随机，那么聚类的结果毫无意义。可以用霍普金斯统计量来判断数据在空间上的随机性：从样本中随机找 个点 ，对每一个 ，都在样本空间中找到一个离它最近的点并计算它们之间的距离 ，从而得到距离向量 ；从样本可能取值范围内随机生成 个点 ，使用同样的原则得到距离向量 ，则霍普金斯统计量 可表示为： 。如果样本接近随机分布，则 的值接近于0.5，如果聚类趋势明显，随机生成的样本点距离应该远大于实际样本点距离，则 的值接近于1。

⑼ 决策树的原理及算法

决策树基本上就是把我们以前的经验总结出来。我给你准备了一个打篮球的训练集。如果我们要出门打篮球，一般会根据“天气”、“温度”、“湿度”、“刮风”这几个条件来判断，最后得到结果：去打篮球？还是不去？

上面这个图就是一棵典型的决策树。我们在做决策树的时候，会经历两个阶段：构造和剪枝。

构造就是生成一棵完整的决策树。简单来说，构造的过程就是选择什么属性作为节点的过程，那么在构造过程中，会存在三种节点：
根节点：就是树的最顶端，最开始的那个节点。在上图中，“天气”就是一个根节点；
内部节点：就是树中间的那些节点，比如说“温度”、“湿度”、“刮风”；
叶节点：就是树最底部的节点，也就是决策结果。

剪枝就是给决策树瘦身，防止过拟合。分为“预剪枝”（Pre-Pruning）和“后剪枝”（Post-Pruning）。

预剪枝是在决策树构造时就进行剪枝。方法是在构造的过程中对节点进行评估，如果对某个节点进行划分，在验证集中不能带来准确性的提升，那么对这个节点进行划分就没有意义，这时就会把当前节点作为叶节点，不对其进行划分。

后剪枝就是在生成决策树之后再进行剪枝，通常会从决策树的叶节点开始，逐层向上对每个节点进行评估。如果剪掉这个节点子树，与保留该节点子树在分类准确性上差别不大，或者剪掉该节点子树，能在验证集中带来准确性的提升，那么就可以把该节点子树进行剪枝。

1是欠拟合，3是过拟合，都会导致分类错误。

造成过拟合的原因之一就是因为训练集中样本量较小。如果决策树选择的属性过多，构造出来的决策树一定能够“完美”地把训练集中的样本分类，但是这样就会把训练集中一些数据的特点当成所有数据的特点，但这个特点不一定是全部数据的特点，这就使得这个决策树在真实的数据分类中出现错误，也就是模型的“泛化能力”差。

p(i|t) 代表了节点 t 为分类 i 的概率，其中 log2 为取以 2 为底的对数。这里我们不是来介绍公式的，而是说存在一种度量，它能帮我们反映出来这个信息的不确定度。当不确定性越大时，它所包含的信息量也就越大，信息熵也就越高。

ID3 算法计算的是信息增益，信息增益指的就是划分可以带来纯度的提高，信息熵的下降。它的计算公式，是父亲节点的信息熵减去所有子节点的信息熵。

公式中 D 是父亲节点，Di 是子节点，Gain(D,a) 中的 a 作为 D 节点的属性选择。

因为 ID3 在计算的时候，倾向于选择取值多的属性。为了避免这个问题，C4.5 采用信息增益率的方式来选择属性。信息增益率 = 信息增益 / 属性熵，具体的计算公式这里省略。

当属性有很多值的时候，相当于被划分成了许多份，虽然信息增益变大了，但是对于 C4.5 来说，属性熵也会变大，所以整体的信息增益率并不大。

ID3 构造决策树的时候，容易产生过拟合的情况。在 C4.5 中，会在决策树构造之后采用悲观剪枝（PEP），这样可以提升决策树的泛化能力。

悲观剪枝是后剪枝技术中的一种，通过递归估算每个内部节点的分类错误率，比较剪枝前后这个节点的分类错误率来决定是否对其进行剪枝。这种剪枝方法不再需要一个单独的测试数据集。

C4.5 可以处理连续属性的情况，对连续的属性进行离散化的处理。比如打篮球存在的“湿度”属性，不按照“高、中”划分，而是按照湿度值进行计算，那么湿度取什么值都有可能。该怎么选择这个阈值呢，C4.5 选择具有最高信息增益的划分所对应的阈值。

针对数据集不完整的情况，C4.5 也可以进行处理。

暂无

请你用下面的例子来模拟下决策树的流程，假设好苹果的数据如下，请用 ID3 算法来给出好苹果的决策树。

“红”的信息增益为：1“大”的信息增益为：0
因此选择“红”的作为根节点，“大”没有用，剪枝。

数据分析实战45讲.17 丨决策树（上）：要不要去打篮球？决策树来告诉你

⑽ 决策树算法基础 ID3与C4.5

决策树算法基础：ID3与C4.5
设X是一个取有限个值得离散随机变量，其概率分布为P(X=xi)=pi, i=1,2,…,n。则随机变量X的信息熵为
条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性。H(Y|X)的计算公式为
所以决策树分支后信息总熵H(D|A)=P1*H1+P2*H2+...+Pn*Hn,(特征A条件下D的经验条件熵)
所以信息增益ΔH=H(D)-H(D|A)
H(D|A)越小，ΔH越大，该特征A越适合作为当前的决策节点。
选取最佳特征伪代码：
计算信息总熵H(D)
遍历每一个特征下的关于D的经验条件熵H(D|A)
计算每一个特征的信息增益ΔH
将信息增益ΔH最大的特征作为最佳特征选为当前决策节点
ID3算法伪代码：
如果第一个标签的数量等于所有的标签数量，说明这是一个单节点树，返回这个标签作为该节点类
如果特征只有一个，说明这是一个单节点树，用多数表决法投票选出标签返回作为该节点类
否则，按信息增益最大的特征A作为当前决策节点，即决策树父节点
如果该特征的信息增益ΔH小于阈值，则用多数表决法投票选出标签返回作为该节点类
否则，对于该特征A的每一个可能值ai，将原空间D分割为若干个子空间Di
对于若干个非空子集Di，将每个Di中实例数最大的类作为标记，构建子节点
以Di为训练空间，递归调用上述步骤
由于信息增益存在偏向于选择取值较多的特征的问题，而C4.5算法中，将ID3算法里的信息增益换成信息增益比，较好地解决了这个问题。
决策树的优点在于计算量简单，适合有缺失属性值的样本，适合处理不相关的特征。而缺点是容易过拟合，可以通过剪枝来简化模型，另外随机森林也解决了这个问题。