决策树算法的优缺点

‘壹’ 决策树基本概念及算法优缺点

分类决策树模型是一种描述对实例进行分类的树形结构. 决策树由结点和有向边组成. 结点有两种类型: 内部结点和叶节点. 内部节点表示一个特征或属性, 叶节点表示一个类.
决策树(Decision Tree),又称为判定树, 是一种以树结构(包括二叉树和多叉树)形式表达的预测分析模型.

分类树--对离散变量做决策树

回归树--对连续变量做决策树

优点:
(1)速度快: 计算量相对较小, 且容易转化成分类规则. 只要沿着树根向下一直走到叶, 沿途的分裂条件就能够唯一确定一条分类的谓词.
(2)准确性高: 挖掘出来的分类规则准确性高, 便于理解, 决策树可以清晰的显示哪些字段比较重要, 即可以生成可以理解的规则.
(3)可以处理连续和种类字段
(4)不需要任何领域知识和参数假设
(5)适合高维数据
缺点:
(1)对于各类别样本数量不一致的数据, 信息增益偏向于那些更多数值的特征
(2)容易过拟合
(3)忽略属性之间的相关性

若一事假有k种结果, 对应概率为 , 则此事件发生后所得到的信息量I为:

给定包含关于某个目标概念的正反样例的样例集S, 那么S相对这个布尔型分类的熵为:

其中 代表正样例, 代表反样例

假设随机变量(X,Y), 其联合分布概率为P(X=xi,Y=yi)=Pij, i=1,2,...,n;j=1,2,..,m
则条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性, 其定义为X在给定条件下Y的条件概率分布的熵对X的数学期望

在Hunt算法中, 通过递归的方式建立决策树.

使用信息增益, 选择 最高信息增益 的属性作为当前节点的测试属性

ID3( Examples,Target_attribute,Attributes )

Examples 即训练样例集. Target_attribute 是这棵树要预测的目标属性. Attributes 是除目标属性外供学习到的决策树测试的属性列表. 返回能正确分类给定 Examples 的决策树.

class sklearn.tree.DecisionTreeClassifier(criterion='gini', splitter='best', max_depth=None, min_samples_split=2, min_samples_leaf=1, min_weight_fraction_leaf=0.0, max_features=None, random_state=None, max_leaf_nodes=None, min_impurity_decrease=0.0, min_impurity_split=None, class_weight=None, presort=False)

限制决策树层数为4的DecisionTreeClassifier实例

This plot compares the decision surfaces learned by a dcision tree classifier(first column), by a random forest classifier(second column), by an extra-trees classifier(third column) and by an AdaBoost classifier(fouth column).

Output:

A comparison of a several classifiers in scikit-learn on synthetic datasets.
The point of this examples is to illustrate the nature of decision boundaries of different classifiers.

Particularly in high-dimensional spaces, data can more easily be separated linearly and the simplicity of classifiers such as naive Bayes and linear SVMs might lead to better generalization than is achieved by other classifiers.

This example fits an AdaBoost decisin stump on a non-linearly separable classification dataset composed of two "Gaussian quantiles" clusters and plots the decision boundary and decision scores.

Output:

‘贰’ 决策树CART算法优点和缺点

CART的全称是分类和回归树，既可以做分类算法，也可以做回归。
决策树的优缺点：
优点：

1.可以生成可以理解的规则。
2.计算量相对来说不是很大。
3.可以处理连续和种类字段。
4.决策树可以清晰的显示哪些字段比较重要
缺点：

1. 对连续性的字段比较难预测。
2.对有时间顺序的数据，需要很多预处理的工作。
3.当类别太多时，错误可能就会增加的比较快。
4.一般的算法分类的时候，只是根据一个字段来分类。

‘叁’ 机器学习中常见的算法的优缺点之决策树

决策树在机器学习中是一个十分优秀的算法，在很多技术中都需要用到决策树这一算法，由此可见，决策树是一个经典的算法，在这篇文章中我们给大家介绍决策树算法的优缺点，希望这篇文章能够更好的帮助大家理解决策树算法。
其实决策树倍受大家欢迎的原因就是其中的一个优势，那就是易于解释。同时决策树可以毫无压力地处理特征间的交互关系并且是非参数化的，因此你不必担心异常值或者数据是否线性可分。但是决策树的有一个缺点就是不支持在线学习，于是在新样本到来后，决策树需要全部重建。另一个缺点就是容易出现过拟合，但这也就是诸如随机森林RF之类的集成方法的切入点。另外，随机森林经常是很多分类问题的赢家，决策树训练快速并且可调，同时大家无须担心要像支持向量机那样调一大堆参数，所以在以前都一直很受欢迎。
那么决策树自身的优点都有什么呢，总结下来就是有六点，第一就是决策树易于理解和解释，可以可视化分析，容易提取出规则。第二就是可以同时处理标称型和数值型数据。第三就是比较适合处理有缺失属性的样本。第四就是能够处理不相关的特征。第五就是测试数据集时，运行速度比较快。第六就是在相对短的时间内能够对大型数据源做出可行且效果良好的结果。
那么决策树的缺点是什么呢？总结下来有三点，第一就是决策树容易发生过拟合，但是随机森林可以很大程度上减少过拟合。第二就是决策树容易忽略数据集中属性的相互关联。第三就是对于那些各类别样本数量不一致的数据，在决策树中，进行属性划分时，不同的判定准则会带来不同的属性选择倾向；信息增益准则对可取数目较多的属性有所偏好，而增益率准则CART则对可取数目较少的属性有所偏好，但CART进行属性划分时候不再简单地直接利用增益率尽心划分，而是采用一种启发式规则。
通过上述的内容相信大家已经知道了决策树的优点和缺点了吧，大家在学习或者使用决策树算法的时候可以更好的帮助大家理解决策树的具体情况，只有了解了这些算法，我们才能够更好的使用决策树算法。

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

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

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

一些特定算法的优点：

朴素贝叶斯的优点：

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

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

逻辑回归的优点：

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

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

决策树的优点：

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

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

(4)决策树算法的优缺点扩展阅读：

朴素贝叶斯算法：

设每个数据样本用一个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的取值。

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

‘伍’ 决策树算法总结

目录

一、决策树算法思想

二、决策树学习本质

三、总结

一、决策树（decision tree）算法思想：

决策树是一种基本的分类与回归方法。本文主要讨论分类决策树。决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。 它可以看做是if-then的条件集合，也可以认为是定义在特征空间与类空间上的条件概率分布 。决策树由结点和有向边组成。结点有两种类型：内部结点和叶结点，内部结点表示一个特征或属性，叶结点表示一个类。（椭圆表示内部结点，方块表示叶结点）

         决策树与if-then规则的关系

决策树可以看做是多个if-then规则的集合。将决策树转换成if-then规则的过程是：由决策树的根结点到叶结点的每一条路径构建一条规则；路径上的内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论。决策树的路径或其对应的if-then规则集合具有一个重要的性质：互斥且完备。这就是说，每一个实例都被一条路径或一条规则所覆盖，且只被一条路径或一条规则所覆盖。这里的覆盖是指实例的特征与路径上的特征一致或实例满足规则的条件。

         决策树与条件概率分布的关系

决策树还表示给定特征条件下类的条件概率分布。这一条件概率分布定义在特征空间的一个划分上。将特征空间划分为互不相交的单元或区域，并在每个单元定义一个类的概率分布，就构成一个条件概率分布。决策树的一条路径对应于划分中的一个单元。决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。

         决策树模型的优点

决策树模型具有可读性，分类速度快。学习时，利用训练数据，根据损失函数最小化原则建立决策树模型；预测时，对新的数据，利用决策树模型进行分类 。

二、决策树学习本质：

决策树学习是从训练数据集中归纳一组分类规则、与训练数据集不相矛盾的决策树可能有多个，也可能一个没有。我们需要训练一个与训练数据矛盾较小的决策树，同时具有很好的泛化能力。从另一个角度看 决策树学习是训练数据集估计条件概率模型 。基于特征空间划分的类的条件概率模型有无穷多个。我们选择的条件概率模型应该是不仅对训练数据有很好的拟合，而且对未知数据有很好的预测。 决策树的学习使用损失函数表示这一目标，通常的损失函数是正则化的极大似然函数。决策树的学习策略是以损失函数为目标函数的最小化。当损失函数确定后，决策树学习问题变为损失函数意义下选择最优决策树的问题。这一过程通常是一个递归选择最优特征，并根据特征对训练数据进行分割，使得对各个子数据集有一个最好分类的过程。这一过程对应着特征选择、决策树的生成、决策树的剪枝。

         特征选择 ： 在于选择对训练数据具有分类能力的特征，这样可以提高决策树的学习效率。

         决策树的生成 ： 根据不同特征作为根结点，划分不同子结点构成不同的决策树。

         决策树的选择 ：哪种特征作为根结点的决策树信息增益值最大，作为最终的决策树（最佳分类特征）。

         信息熵 ： 在信息论与概率统计中，熵是表示随机变量不确定性的度量。设X是一个取有限个值的离散随机变量，其概率分布为P(X= ) = ，i=1，2，3...n，则随机变量X的熵定义为

        H(X) =  —  ，0 <=  H(X) <= 1，熵越大，随机变量的不确定性就越大。

        条件熵（Y|X） ： 表示在已知随机变量X的条件下随机变量Y的不确定性。

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

        信息增益  = 信息熵(父结点熵 ) — 条件熵（子结点加权熵）

三、 总结 ：

        优点

        1、可解释性高，能处理非线性的数据，不需要做数据归一化，对数据分布没有偏好。

        2、可用于特征工程，特征选择。

        3、可转化为规则引擎。

        缺点

        1、启发式生成，不是最优解。

        2、容易过拟合。

        3、微小的数据改变会改变整个数的形状。

        4、对类别不平衡的数据不友好。