比较树算法

Ⅰ 请比较k近邻，决策树和朴素贝叶斯这三种分类算法之间的异同点

决策树算法主要包括id3，c45，cart等算法，生成树形决策树，而朴素贝叶斯是利用贝叶斯定律，根据先验概率求算后验概率。

如果训练集很小，那么高偏差/低方差分类器（如朴素贝叶斯分类器）要优于低偏差/高方差分类器（如k近邻分类器），因为后者容易过拟合。然而，随着训练集的增大，低偏差/高方差分类器将开始胜出（它们具有较低的渐近误差），因为高偏差分类器不足以提供准确的模型。

一些特定算法的优点：

朴素贝叶斯的优点：

超级简单，你只是在做一串计算。如果朴素贝叶斯（NB）条件独立性假设成立，相比于逻辑回归这类的判别模型，朴素贝叶斯分类器将收敛得更快，所以只需要较小的训练集。而且，即使NB假设不成立，朴素贝叶斯分类器在实践方面仍然表现很好。

如果想得到简单快捷的执行效果，这将是个好的选择。它的主要缺点是，不能学习特征之间的相互作用（比如，它不能学习出：虽然你喜欢布拉德·皮特和汤姆·克鲁斯的电影，但却不喜欢他们一起合作的电影）。

逻辑回归的优点：

有许多正则化模型的方法，不需要像在朴素贝叶斯分类器中那样担心特征间的相互关联性。与决策树和支撑向量机不同，还可以有一个很好的概率解释，并能容易地更新模型来吸收新数据（使用一个在线梯度下降方法）。

如果想要一个概率框架（比如，简单地调整分类阈值，说出什么时候是不太确定的，或者获得置信区间），或你期望未来接收更多想要快速并入模型中的训练数据，就选择逻辑回归。

决策树的优点：

易于说明和解释（对某些人来说—我不确定自己是否属于这个阵营）。它们可以很容易地处理特征间的相互作用，并且是非参数化的，所以你不用担心异常值或者数据是否线性可分（比如，决策树可以很容易地某特征x的低端是类A，中间是类B，然后高端又是类A的情况）。

一个缺点是，不支持在线学习，所以当有新样本时，你将不得不重建决策树。另一个缺点是，容易过拟合，但这也正是诸如随机森林（或提高树）之类的集成方法的切入点。另外，随机森林往往是很多分类问题的赢家（我相信通常略优于支持向量机），它们快速并且可扩展，同时你不须担心要像支持向量机那样调一堆参数，所以它们最近似乎相当受欢迎。

(1)比较树算法扩展阅读：

朴素贝叶斯算法：

设每个数据样本用一个n维特征向量来描述n个属性的值，即：X={x1，x2，…，xn}，假定有m个类，分别用C1, C2,…，Cm表示。给定一个未知的数据样本X（即没有类标号），若朴素贝叶斯分类法将未知的样本X分配给类Ci，则一定是

P(Ci|X)>P(Cj|X) 1≤j≤m，j≠i

根据贝叶斯定理：

由于P(X)对于所有类为常数，最大化后验概率P(Ci|X)可转化为最大化先验概率P(X|Ci)P(Ci)。如果训练数据集有许多属性和元组，计算P(X|Ci)的开销可能非常大，为此，通常假设各属性的取值互相独立，这样

先验概率P(x1|Ci)，P(x2|Ci)，…，P(xn|Ci)可以从训练数据集求得。

根据此方法，对一个未知类别的样本X，可以先分别计算出X属于每一个类别Ci的概率P(X|Ci)P(Ci)，然后选择其中概率最大的类别作为其类别。

朴素贝叶斯算法成立的前提是各属性之间互相独立。当数据集满足这种独立性假设时,分类的准确度较高，否则可能较低。另外，该算法没有分类规则输出。

TAN算法（树增强型朴素贝叶斯算法）

TAN算法通过发现属性对之间的依赖关系来降低NB中任意属性之间独立的假设。它是在NB网络结构的基础上增加属性对之间的关联(边)来实现的。

实现方法是：用结点表示属性，用有向边表示属性之间的依赖关系，把类别属性作为根结点，其余所有属性都作为它的子节点。通常，用虚线代表NB所需的边，用实线代表新增的边。属性Ai与Aj之间的边意味着属性Ai对类别变量C的影响还取决于属性Aj的取值。

这些增加的边需满足下列条件：类别变量没有双亲结点，每个属性有一个类别变量双亲结点和最多另外一个属性作为其双亲结点。

Ⅱ 数据挖掘-决策树算法

决策树算法是一种比较简易的监督学习分类算法，既然叫做决策树，那么首先他是一个树形结构，简单写一下树形结构（数据结构的时候学过不少了）。

树状结构是一个或多个节点的有限集合，在决策树里，构成比较简单，有如下几种元素：

在决策树中，每个叶子节点都有一个类标签，非叶子节点包含对属性的测试条件，用此进行分类。
所以个人理解，决策树就是 对一些样本，用树形结构对样本的特征进行分支，分到叶子节点就能得到样本最终的分类，而其中的非叶子节点和分支就是分类的条件，测试和预测分类就可以照着这些条件来走相应的路径进行分类。

根据这个逻辑，很明显决策树的关键就是如何找出决策条件和什么时候算作叶子节点即决策树终止。

决策树的核心是为不同类型的特征提供表示决策条件和对应输出的方法，特征类型和划分方法包括以下几个：

注意，这些图中的第二层都是分支，不是叶子节点。

如何合理的对特征进行划分，从而找到最优的决策模型呢？在这里需要引入信息熵的概念。

先来看熵的概念：

在数据集中，参考熵的定义，把信息熵描述为样本中的不纯度，熵越高，不纯度越高，数据越混乱（越难区分分类）。

例如：要给（0，1）分类，熵是0，因为能明显分类，而均衡分布的（0.5，0.5）熵比较高，因为难以划分。

信息熵的计算公式为：
其中 代表信息熵。 是类的个数， 代表在 类时 发生的概率。
另外有一种Gini系数，也可以用来衡量样本的不纯度：
其中 代表Gini系数，一般用于决策树的 CART算法 。

举个例子：

如果有上述样本，那么样本中可以知道，能被分为0类的有3个，分为1类的也有3个，那么信息熵为：
Gini系数为：
总共有6个数据，那么其中0类3个，占比就是3/6，同理1类。

我们再来计算一个分布比较一下：

信息熵为：
Gini系数为：

很明显，因为第二个分布中，很明显这些数偏向了其中一类，所以 纯度更高 ，相对的信息熵和Gini系数较低。

有了上述的概念，很明显如果我们有一组数据要进行分类，最快的建立决策树的途径就是让其在每一层都让这个样本纯度最大化，那么就要引入信息增益的概念。

所谓增益，就是做了一次决策之后，样本的纯度提升了多少（不纯度降低了多少），也就是比较决策之前的样本不纯度和决策之后的样本不纯度，差越大，效果越好。
让信息熵降低，每一层降低的越快越好。
度量这个信息熵差的方法如下：
其中 代表的就是信息熵（或者其他可以度量不纯度的系数）的差， 是样本(parent是决策之前， 是决策之后)的信息熵（或者其他可以度量不纯度的系数）， 为特征值的个数， 是原样本的记录总数， 是与决策后的样本相关联的记录个数。

当选择信息熵作为样本的不纯度度量时，Δ就叫做信息增益 。

我们可以遍历每一个特征，看就哪个特征决策时，产生的信息增益最大，就把他作为当前决策节点，之后在下一层继续这个过程。

举个例子：

如果我们的目标是判断什么情况下，销量会比较高（受天气，周末，促销三个因素影响），根据上述的信息增益求法，我们首先应该找到根据哪个特征来决策，以信息熵为例：

首先肯定是要求 ，也就是销量这个特征的信息熵：

接下来，就分别看三个特征关于销量的信息熵，先看天气，天气分为好和坏两种，其中天气为好的条件下，销量为高的有11条，低的有6条；天气坏时，销量为高的有7条，销量为低的有10条，并且天气好的总共17条，天气坏的总共17条。

分别计算天气好和天气坏时的信息熵，天气好时：

根据公式 ，可以知道，N是34，而天气特征有2个值，则k=2，第一个值有17条可以关联到决策后的节点，第二个值也是17条，则能得出计算：

再计算周末这个特征，也只有两个特征值，一个是，一个否，其中是有14条，否有20条；周末为是的中有11条销量是高，3条销量低，以此类推有：


信息增益为：

另外可以得到是否有促销的信息增益为0.127268。

可以看出，以周末为决策，可以得到最大的信息增益，因此根节点就可以用周末这个特征进行分支：

注意再接下来一层的原样本集，不是34个而是周末为“是”和“否”分别计算，为是的是14个，否的是20个。
这样一层一层往下递归，直到判断节点中的样本是否都属于一类，或者都有同一个特征值，此时就不继续往下分了，也就生成了叶子节点。

上述模型的决策树分配如下：

需要注意的是，特征是否出现需要在分支当中看，并不是整体互斥的，周末生成的两个分支，一个需要用促销来决策，一个需要用天气，并不代表再接下来就没有特征可以分了，而是在促销决策层下面可以再分天气，另外一遍天气决策下面可以再分促销。

决策树的模型比较容易解释，看这个树形图就能很容易的说出分类的条件。

我们知道属性有二元属性、标称属性、序数属性和连续属性，其中二元、标称和序数都是类似的，因为是离散的属性，按照上述方式进行信息增益计算即可，而连续属性与这三个不同。

对于连续的属性，为了降低其时间复杂度，我们可以先将属性内部排序，之后取相邻节点的均值作为决策值，依次取每两个相邻的属性值的均值，之后比较他们的不纯度度量。

需要注意的是，连续属性可能在决策树中出现多次，而不是像离散的属性一样在一个分支中出现一次就不会再出现了。

用信息熵或者Gini系数等不纯度度量有一个缺点，就是会倾向于将多分支的属性优先分类——而往往这种属性并不是特征。

例如上面例子中的第一行序号，有34个不同的值，那么信息熵一定很高，但是实际上它并没有任何意义，因此我们需要规避这种情况，如何规避呢，有两种方式：

公式如下：

其中k为划分的总数，如果每个属性值具有相同的记录数，则 ，划分信息等于 ，那么如果某个属性产生了大量划分，则划分信息很大，信息增益率低，就能规避这种情况了。

为了防止过拟合现象，往往会对决策树做优化，一般是通过剪枝的方式，剪枝又分为预剪枝和后剪枝。

在构建决策树时，设定各种各样的条件如叶子节点的样本数不大于多少就停止分支，树的最大深度等，让决策树的层级变少以防止过拟合。
也就是在生成决策树之前，设定了决策树的条件。

后剪枝就是在最大决策树生成之后，进行剪枝，按照自底向上的方式进行修剪，修剪的规则是，评估叶子节点和其父节点的代价函数，如果父节点的代价函数比较小，则去掉这个叶子节点。
这里引入的代价函数公式是：
其中 代表的是叶子节点中样本个数， 代表的是该叶子节点上的不纯度度量，把每个叶子节点的 加起来，和父节点的 比较，之后进行剪枝即可。

Ⅲ 最优二叉树算法的判定问题中的应用

在本章的引入部分，两个例子都是判定问题，这两个判定问题都可以通过构造哈夫曼树来优化判定，以达到总的判定次数最少。
再如，要编制一个将百分制转换为五级分制的程序。显然，此程序很简单，只要利用条件语句便可完成。
程序段
if a<60 then b:=’bad’
else if a<70 then b:=’pass’
else if a<80 then b:=’general’
else if a<90 then b:=’good’
else b:=’excellent’;
如果上述程序需反复使用，而且每次的输入量很大，则应考虑上述程序的质量问题，即其操作所需要的时间。因为在实际中，学生的成绩在五个等级上的分布是不均匀的，假设其分布规律如表4所示： 分数 0-59 60－69 70－79 80－89 90－100 比例数 0.05 0.15 0.40 0.30 0.10 表4 分数段的分布频率
则80%以上的数据需进行三次或三次以上的比较才能得出结果。假定以5，15，40，30和10为权构造一棵有五个叶子结点的哈夫曼树，它可使大部分的数据经过较少的比较次数得出结果。但由于每个判定框都有两次比较，将这两次比较分开，得到新的判定树，按此判定树可写出相应的程序。请您自己画出此判定树。
假设有10000个输入数据，若上程序段的判定过程进行操作，则总共需进行31500次比较；而若新判定树的判定过程进行操作，则总共仅需进行22000次比较。

Ⅳ 决策树原理及算法比较

决策树是什么？

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

决策树的目标是什么？

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

    表现为“熵”（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， 叶子节点覆盖的样本未必是同一类，所占的大多数，那么该叶子节点的类别就是那个占大多数的类

Ⅳ 判定树的算法

可以解决.
1.0 任意取2枚于天平量测重量,如: a+b; a+c; a+d; a+e;
a+f; a+g; a+h, 检查称得的重量数值就能知道.
2.0 还有一个简单一点的. 取天平之砝码一个(砝码重量
已知,5g; 2g; 10g均可以),分别与a;b;c........
等8枚硬币一起测试,从测试数据即知道哪个硬币是假的.

你觉得计算方法对吗? 个人觉得比较快捷.

Ⅵ 目前比较流行的决策树算法有哪些

ID3算法，最简单的决策树
c4.5 是最经典的决策树算法，选择信息差异率最大的作为分割属性。
CART算法，适合用于回归

Ⅶ 常见决策树分类算法都有哪些

在机器学习中，有一个体系叫做决策树，决策树能够解决很多问题。在决策树中，也有很多需要我们去学习的算法，要知道，在决策树中，每一个算法都是实用的算法，所以了解决策树中的算法对我们是有很大的帮助的。在这篇文章中我们就给大家介绍一下关于决策树分类的算法，希望能够帮助大家更好地去理解决策树。
1.C4.5算法
C4.5算法就是基于ID3算法的改进，这种算法主要包括的内容就是使用信息增益率替换了信息增益下降度作为属性选择的标准；在决策树构造的同时进行剪枝操作；避免了树的过度拟合情况；可以对不完整属性和连续型数据进行处理；使用k交叉验证降低了计算复杂度；针对数据构成形式，提升了算法的普适性等内容，这种算法是一个十分使用的算法。
2.CLS算法
CLS算法就是最原始的决策树分类算法，基本流程是，从一棵空数出发，不断的从决策表选取属性加入数的生长过程中，直到决策树可以满足分类要求为止。CLS算法存在的主要问题是在新增属性选取时有很大的随机性。
3.ID3算法
ID3算法就是对CLS算法的最大改进是摒弃了属性选择的随机性，利用信息熵的下降速度作为属性选择的度量。ID3是一种基于信息熵的决策树分类学习算法，以信息增益和信息熵，作为对象分类的衡量标准。ID3算法结构简单、学习能力强、分类速度快适合大规模数据分类。但同时由于信息增益的不稳定性，容易倾向于众数属性导致过度拟合，算法抗干扰能力差。
3.1.ID3算法的优缺点
ID3算法的优点就是方法简单、计算量小、理论清晰、学习能力较强、比较适用于处理规模较大的学习问题。缺点就是倾向于选择那些属性取值比较多的属性，在实际的应用中往往取值比较多的属性对分类没有太大价值、不能对连续属性进行处理、对噪声数据比较敏感、需计算每一个属性的信息增益值、计算代价较高。
3.2.ID3算法的核心思想
根据样本子集属性取值的信息增益值的大小来选择决策属性，并根据该属性的不同取值生成决策树的分支，再对子集进行递归调用该方法，当所有子集的数据都只包含于同一个类别时结束。最后，根据生成的决策树模型，对新的、未知类别的数据对象进行分类。
在这篇文章中我们给大家介绍了决策树分类算法的具体内容，包括有很多种算法。从中我们不难发现决策树的算法都是经过不不断的改造趋于成熟的。所以说，机器学习的发展在某种程度上就是由于这些算法的进步而来的。

Ⅷ 数据结构 算法判断两棵二叉树是否等价

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
typedef char datatype;

typedef struct node
{
datatype data;
struct node *lchild,*rchild;
}*bitree;

bitree createtree(bitree root)
{
char s;
s=getchar();
while(s!='@') /*'@'作为一种结束标识符 */
{
if(s==' ') /*‘ ’时将作为虚结点*/
{
root=NULL;
return root;
}
root=(bitree)malloc(sizeof(bitree));
root->data=s;
root->lchild=createtree(root->lchild); /* 递归 */
root->rchild=createtree(root->rchild); /* 递归 */
return root;
}
return root;
}

int comparetree(bitree a,bitree b)
{
if(a==NULL && b==NULL) return 1;
else if(a!=NULL && b!=NULL)
{
if(a->data == b->data) return(comparetree(a->lchild,b->lchild) && comparetree(a->rchild,b->rchild));
else return 0;
}
else return 0; //一种NULL，一种不NULL没考虑，直接返回0就好。
}

int main()
{
bitree a,b;
int p;
printf("请输入二叉树1的各元素，以'@'作为结束标志符:\n");
a=createtree(a);
getchar(); //这里需要把换行给吃掉，不然影响后面的输入。
printf("请输入二叉树1的各元素，以'@'作为结束标志符:\n");
b=createtree(b);
printf("输入结束\n");
p=comparetree(a,b);
if(p==1)
printf("\n两个二叉树等价\n");
else
printf("\n两个二叉树不等价\n");

return 0;
}

没输出主要是需要在两个输入之间加上getchar（）,还有判断是否等价少了一部分。

Ⅸ 决策树、随机森林

在了解树模型之前，自然想到树模型和线性模型，他们有什么区别呢？

决策树与逻辑回归的分类区别也在于此。

树形模型更加接近人的思维方式，可以 产生可视化的分类规则，产生的模型具有可解释性 。树模型拟合出来的函数其实是 分区间的阶梯函数 。

决策树（decision tree）是一种基本的分类与回归方法，此处主要讨论分类的决策树。决策树是一种十分常用的分类方法，属于有监督学习（Supervised Learning）。所谓有监督学习，就是给出一堆样本，每个样本都有一组属性和一个分类结果，也就是分类结果已知，那么通过学习这些样本得到一个决策树，这个决策树能够对新的数据给出正确的分类。

决策树是一种树形结构，它主要有三种不同的节点：

决策树算法主要包括三个部分： 特征选择、树的生成、树的剪枝。

比较常用的决策树算法有ID3，C4.5和CART（Classification And Regression Tree），CART的分类效果一般优于其他决策树。

样本数量，特征数量上面，一开始需要注意的：

当熵中的概率由数据估计(特别是最大似然估计)得到时，所对应的熵称为 经验熵 (empirical entropy)。

什么叫由数据估计？比如有10个数据，一共有两个类别，A类和B类。其中有7个数据属于A类，则该A类的概率即为十分之七。其中有3个数据属于B类，则该B类的概率即为十分之三。浅显的解释就是，这概率是我们根据数据数出来的。

训练数据集D，则训练数据集D的经验熵为H(D)，|D|表示其样本容量，及样本个数。设有K个类Ck，k = 1,2,3,···,K，|Ck|为属于类Ck的样本个数，这经验熵公式可以写为：

信息增益表示得知特征X的信息而使得类Y的信息不确定性减少的程度。

条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性，随机变量X给定的条件下随机变量Y的条件熵(conditional entropy) H(Y|X)，定义X给定条件下Y的条件概率分布的熵对X的数学期望：

当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的分别为经验熵和经验条件熵，此时如果有0概率，令0log0=0。

信息增益

一般地， 熵H(D)与条件熵H(D|A)之差成为互信息(mutual information) 。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。

信息增益比

Gini 指数

举例计算Gini指数（不纯度）

这个分类结果明显并不是很好，因为它没有将见面与不见面完全的分开，在算法中，当然不能凭我们的“感觉”去评价分类结果的好坏。我们需要用一个数去表示。（具体数值代入上面的基尼指数计算公式）

信息增益 vs 信息增益比

Gini 指数 vs 熵

ID3算法的核心是在决策树各个结点上对应信息增益准则选择特征，递归地构建决策树。

具体方法是：

1）从根结点(root node)开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征。

2）由该特征的不同取值建立子节点，再对子结点递归地调用以上方法，构建决策树；直到 所有特征的信息增益均很小或没有特征可以选择 为止；

3）最后得到一个决策树。

ID3相当于用 极大似然法进行概率模型的选择 。

与ID3算法相似，但是做了改进，将信息增益比作为选择特征的标准。

CART 的全称是分类与回归树。从这个名字中就应该知道，CART 既可以用于分类问题，也可以用于回归问题。

回归树中，使用平方误差最小化准则来选择特征并进行划分。每一个叶子节点给出的预测值，是划分到该叶子节点的所有样本目标值的均值，这样只是在给定划分的情况下最小化了平方误差。

要确定最优化分，还需要遍历所有属性，以及其所有的取值来分别尝试划分并计算在此种划分情况下的最小平方误差，选取最小的作为此次划分的依据。由于回归树生成使用平方误差最小化准则，所以又叫做最小二乘回归树。

ID3

熵表示的是数据中包含的信息量大小。熵越小，数据的纯度越高，也就是说数据越趋于一致，这是我们希望的划分之后每个子节点的样子。

信息增益 = 划分前熵 - 划分后熵。信息增益越大，则意味着使用属性 a 来进行划分所获得的 “纯度提升” 越大 **。也就是说，用属性 a 来划分训练集，得到的结果中纯度比较高。

ID3 仅仅适用于二分类问题。ID3 仅仅能够处理离散属性。

C4.5 克服了 ID3 仅仅能够处理离散属性的问题，以及信息增益偏向选择取值较多特征的问题，使用信息增益比来选择特征。 信息增益比 = 信息增益 / 划分前熵 选择信息增益比最大的作为最优特征。

C4.5 处理连续特征是先将特征取值排序，以连续两个值中间值作为划分标准。尝试每一种划分，并计算修正后的信息增益，选择信息增益最大的分裂点作为该属性的分裂点。

CART 与 ID3，C4.5 不同之处在于 CART 生成的树必须是二叉树 。也就是说，无论是回归还是分类问题，无论特征是离散的还是连续的，无论属性取值有多个还是两个，内部节点只能根据属性值进行二分。

决策树生成算法递归的产生决策树，直到不能继续下去为止，这样产生的树往往对训练数据的分类很准确，但对未知测试数据的分类缺没有那么精确，即会出现过拟合现象。过拟合产生的原因在于在学习时过多的考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树，解决方法是考虑决策树的复杂度，对已经生成的树进行简化。

剪枝（pruning）：从已经生成的树上裁掉一些子树或叶节点，并将其根节点或父节点作为新的叶子节点，从而简化分类树模型。

实现方式：极小化决策树整体的损失函数或代价函数来实现

决策树学习的损失函数定义为：

https://www.cnblogs.com/ooon/p/5647309.html

鉴于决策树容易过拟合的缺点，随机森林采用多个决策树的投票机制来改善决策树，我们假设随机森林使用了m棵决策树，那么就需要产生m个一定数量的样本集来训练每一棵树，如果用全样本去训练m棵决策树显然是不可取的，全样本训练忽视了局部样本的规律，对于模型的泛化能力是有害的。

产生n个样本的方法采用Bootstraping法，这是一种有放回的抽样方法，产生n个样本。

而最终结果采用Bagging的策略来获得，即多数投票机制。

随机森林的生成方法：

1.从样本集中通过重采样的方式产生n个样本

2.假设样本特征数目为a，对n个样本选择a中的k个特征，用建立决策树的方式获得最佳分割点

3.重复m次，产生m棵决策树

4.多数投票机制来进行预测

（需要注意的一点是，这里m是指循环的次数，n是指样本的数目，n个样本构成训练的样本集，而m次循环中又会产生m个这样的样本集）

随机森林是一个比较优秀的模型，在我的项目的使用效果上来看，它对于多维特征的数据集分类有很高的效率，还可以做特征重要性的选择。运行效率和准确率较高，实现起来也比较简单。 但是在数据噪音比较大的情况下会过拟合，过拟合的缺点对于随机森林来说还是较为致命的。

机器学习实战（三）——决策树 https://blog.csdn.net/jiaoyangwm/article/details/79525237