启发式算法的优缺点,启发式算法是不是每次结果不同

决策树算法是一种非常常用的算法模型，决策树的启发算法就是构建决策树模型的方式。该问题通俗理解就是决策树算法模型的构建方式有几种？每种方式是怎样构建的？有何优缺点？

通过这几个问题，可以很快地判断面试者对决策树

算法的理解程度，在此基础上还会考察到面试者的一些数学知识，比如熵、信息增益、信息增益比。延展度非常大。和决策树相关的集成算法也有可能在此基础上被引出，如果面试者在回答完各种构建决策树的方式之后，还能引出集成学习，那么就有可能变被动为主动，主动引导面试官来询问集成学习的各种模型，如果此时你对随机森林、GDBT、Xbgoost等集成算法了如指掌，并且还能够在此基础上有过一定的实践，那么我认为这都是你的加分项。

一般这个问题就可以聊好久了，在各种算法面经上，多次出现决策树算法，下面就对这个问题进行详细的解释。

我觉得回答可以分为四个步骤：

1. 决策树的简介
2. 各种启发式算法
3. 优缺点
4. 随机森林（随机森林）

在机器学习中已知输入变量和输出变量均为连续变量的预测问题称为回归问题，输出变量为有限个离散变量的问题被称为分类问题。现在介绍一种新的机器学习算法模型，它是一种常见的分类与回归算法，该算法模型即可以完成回归任务又可以完成分类任务，由于它的结构和树结构相似，所以它的名字是决策树算法。

从物理结构来看，决策树算法模型由结点和有向边组成。其中结点分为内部结点和叶节点，每个内部结点表示一个特征，叶节点表示类别。从顶部根节点开始，所有样本聚集在一起，根节点根据某个特征进行划分，样本被划分到不同的子节点中。然后子结点根据某个特征继续进行划分，直到结点中所有的样本都是一个类别。

构建决策树模型的方式主要有三种：

ID3、C4.5、CART

ID3算法的核心是在决策树各个结点上应用信息增益作为特征选择的方式，递归地构建决策树。具体方法是：从根结点开始，计算所有可能特征的信息增益， 选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点；再对子结点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小、没有特征可以选择为止或者这个节点的样本标签都相同。

ID3使用了信息增益的方法来构建决策树，取值比较多的特征比取值少的特征信息增益大，使得模型偏向特征取值多的，而C4.5就是使用信息增益率来完成特征的选择，可以很好的解决这个问题。C4.5算法在构建决策树的过程中可以对连续的数据进行离散化处理，从而解决ID3无法处理连续值得问题。

ID3算法和C4.5算法使用较为复杂的多叉树，都只能处理分类问题，而不能处理回归问题，而CART算法形成的决策树是即可以做回归，也可以做分类的二叉树，CART模型的全称为分类与回归树模型，它每次对某个特征的划分时分为两类，但会对该特征的不同取值进行多次划分，以保证信息得到充分使用。CART假设决策树是二叉树，内部结点特征的取值为“是”和“否”，左分支是取值为“是”的 分支，右分支是取值为“否”的分支，这样的决策树等价于递归地二分每个特征。其中分类树使用基尼系数来进行评估，回归树使用平方差来进行评估。

我建议在回答各种优势劣势的时候，应该分点来进行回答：

特征选择

信息增益会比较偏向特征较多的特征，特征越多意味着确定性越高，那么信息增益就越大，C4.5实际上是对ID3进行了优化，通过信息增益比来对取值较多的特征进行惩罚，避免出现ID3中出现过拟合的特性，提升决策树的泛化能力。

离散还是连续

ID3只能处理离散型变量，而C4.5和CART都可以处理连续型的变量。其中C4.5处理连续型变量的时候，通过对数据排序之后找到类别不同的分割线作为切分点，根据切分点把连续属性转成布尔型，从而将连续型变量转换为多个取值区间的离散型变量。而对于CART，由于构建每次都对特征进行二值化分（每次分左右两个分支），因此可以很好的适用连续型的变量。

分类还是回归

其中ID3和C4.5只能用于分类任务，而CART既可以应用分类又可以用于回归，所以针对于不同的机器学习任务，我们应该使用不同的类型的决策树模型。

特征是否可以复用

ID3和C4.5可以在每个结点可以产生出多叉的分支，所以每个特征在层级之间不会复用。而CART每个结点只能产生两个分支，最终形成一颗二叉树，每个特征可以被重复使用。

缺失值敏感吗

ID3对样本的缺失值比较敏感，而C4.5和CART可以对缺失值进行不同方式的处理。

随机森林算法是集成学习算法的一种，属于Bagging，随机森林中包含多个决策树，就算每棵数的分类能力比较弱，或者存在误差，但是依靠大量决策树的投票结果，误差会相对抵消，从而使得效果较好的“决策树”的分类结果表现出来。这就是随机森林的算法的思想。随机森林使用CART决策树，所以随机森林既可以处理回归问题又可以处理分类问题。

随机森林的实施步骤

1.自助采样样本：随机有放回地从N个训练样本中抽取N个样本，作为生成树地训练集。

2.随机选取特征：对K个特征随机选择k个作为特征子集，在对树做特征选择时，从特征子集中选择最优地特征。

3.按照此时的样本生成一棵树

4.重复1~3执行T次，此时建立T棵决策树。如果要是想要解决回归问题，那么T棵决策树的回归结果的算数平均值既为最终结果。