什么是决策树？

参考:

决策树(分类树、回归树)

决策树:这个博客的图解真的很美，很好理解。哈哈的笑

决策树的详细解释

决策树是一种监督学习算法，常用于分类和回归。本文只讨论分类问题。

决策树模型是一种用于分类和回归的树结构。决策树由节点和有向边组成。通常，决策树包含一个根节点、几个内部节点和几个叶节点。决策树的决策过程需要从决策树的根节点开始，将待测数据与决策树中的特征节点进行比较，根据比较结果选择下一个比较分支，直到叶子节点为最终决策结果。

简而言之，决策树是一种使用树模型进行决策的多分类模型。

为了找到最优分割特征，我们需要先了解一些信息论知识:

纯度:

你可以把决策树的构建过程理解为寻找纯除法的过程。数学上，我们可以表示纯度，另一种解释纯度的方法是最小化目标变量的差异。

信息的不确定性。

在信息论中，随机离散事件的概率是不确定的。为了度量这些信息的不确定性，信息学之父香农引入了信息熵的概念。

不确定性越大，包含的信息量越大，信息熵越高。

信息熵越大，纯度越低。当集合中所有样本混合均匀时，信息熵最大，纯度最低。

“杂质”有三个经典指标，分别是信息增益(ID3算法)、信息增益率(C4.5算法)和基尼指数(Cart算法)。

信息增益:

信息增益意味着除法可以提高纯度，降低信息熵。它的计算公式是父节点的信息熵减去所有子节点的信息熵。

信息增益率

信息增益率=信息增益/属性熵

基尼指数

基尼指数(Gini杂质):表示样本集中随机选择的样本被错误分类的概率。

即基尼指数(基尼杂质)=样本被选中的概率*样本被错误分类的概率。

基尼系数的性质和信息熵一样:它度量的是随机变量的不确定性；

g越大，数据的不确定性越高；

g越小，数据的不确定性越低；

G = 0，数据集中的所有样本属于同一类别。

详细参考:机器学习-基尼指数

ID3算法基于奥卡姆剃刀(你可以用更少的东西把事情做好):决策树越小，决策树越好。

ID3算法的核心是根据决策树各节点的信息增益选择待划分的特征，然后递归构造决策树。该算法使用自顶向下的贪婪搜索来遍历可能的决策树空间。

具体方法:

ID3的局限性:

C4.5与ID3类似，但它的一大特点是克服了ID3注重特征数量的缺点，引入了信息增益率作为分类标准。

C4.5的实现是在ID3的基础上改进的；

信息增益率偏向于期望值较低的特征(分母越小，整体越大)，所以C4.5并不直接划分增益率最大的特征，而是采用启发式的方法:首先从候选划分特征中找出信息增益高于平均值的特征，然后选择增益率最高的特征。

C4.5的限制:

ID3和C4.5生成的决策树分支和规模都很大。CART算法的二分法可以简化决策树的规模，提高生成决策树的效率。

Cart(分类回归树)是一种分类回归树算法，既可以用于分类，也可以用于回归。在这一部分，我们主要是先生成它的分类树。与ID3和C4.5不同的是，CART假设决策树是二叉树，内部节点特征值为“是”和“否”，左分支是值为“是”的分支，右分支是值为“否”的分支。这样的决策树相当于递归地将每个特征一分为二，并将输入空间(即特征空间)划分为有限个单元。

CART的分类树使用基尼指数来选择最优特征的最优分界点，具体过程如下。

剪枝就是给决策树瘦身。这一步的目标是不需要过多的判断就能得到好的结果。这样做的原因是为了防止“过拟合”的现象。

过拟合:是指模型的训练结果“太好了”，在实际应用过程中会出现“刚性”，导致分类错误。

欠拟合:指模型的训练结果不理想。

修剪方法:

参考:机器学习决策树(一)-ID3，C4.5，CART(非常详细)

更多的型号在不断更新。。。。