决策树(Decision Tree）是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。在机器学习中，决策树是一个预测模型，他代表的是对象属性与对象值之间的一种映射关系。Entropy = 系统的凌乱程度，使用算法ID3, C4.5和C5.0生成树算法使用熵。这一度量是基于信息学理论中熵的概念。

如果我们有一套数据集：

颜色	响声	甜度	好瓜
青绿	浑浊	不甜	不是
青绿	浑浊	不甜	不是
青绿	清脆	甜	是
青绿	浑浊	不甜	不是
深绿	清脆	甜	是
深绿	浑浊	甜	是
深绿	浑浊	不甜	是
深绿	清脆	甜	是
深绿	清脆	甜	是

根据数据集，可以生成一套决策树：

graph TD
color[颜色]
sound[响声]
sweet[甜度]

color --青绿--> sound
color --深绿--> 是好瓜 
sound --清脆--> 是好瓜.
sound --浑浊--> sweet
sweet --甜--> 是好瓜..
sweet --不甜--> 不是好瓜

然而，上面随便编的决策树是否合理？

关于如何生成决策树，需要涉及一些问题：

如何挑选根结点
如果挑选分枝结点
如何判断是继续向下分枝还是停止
...

这就是我们接下来要解决的问题。

ID3

ID3 算法是一种基于信息熵理论的决策树算法。

ID3 算法的思想：

先计算数据集的信息熵
再逐个计算每一个条件确定之后的条件熵
通过信息熵 - 条件熵得到每个条件的信息增益系数
挑选增益最大的条件作为根结点
对每个分枝的数据集开始新一轮计算
对于每一个数据集，如果结果唯一或数据集个数小于某一阈值，就不再继续分枝

计算信息熵

根据数据集：

颜色	响声	甜度	好瓜
青绿	浑浊	不甜	不是
青绿	浑浊	不甜	不是
青绿	清脆	甜	是
青绿	浑浊	不甜	不是
深绿	清脆	甜	是
深绿	浑浊	甜	是
深绿	浑浊	不甜	是
深绿	清脆	甜	是
深绿	清脆	甜	是

$是好瓜不是好瓜$ 计算信息熵：

计算条件熵

确定颜色的情况

颜色 = 青绿：

响声	甜度	好瓜
浑浊	不甜	不是
浑浊	不甜	不是
清脆	甜	是
浑浊	不甜	不是

$颜色青绿$

颜色 = 深绿：

响声	甜度	好瓜
清脆	甜	是
浑浊	甜	是
浑浊	不甜	是
清脆	甜	是
清脆	甜	是

$颜色深绿$

故 $颜色颜色青绿颜色深绿$

确定响声的情况

响声 = 清脆：

颜色	甜度	好瓜
青绿	甜	是
深绿	甜	是
深绿	甜	是
深绿	甜	是

$响声清脆$

响声 = 浑浊：

颜色	甜度	好瓜
青绿	不甜	不是
青绿	不甜	不是
青绿	不甜	不是
深绿	甜	是
深绿	不甜	是

$响声浑浊$

故 $响声响声清脆响声浑浊$

确定甜度的情况

甜度 = 甜：

颜色	响声	好瓜
青绿	清脆	是
深绿	清脆	是
深绿	浑浊	是
深绿	清脆	是
深绿	清脆	是

$甜度甜$

甜度=不甜：

颜色	响声	甜度	好瓜
青绿	浑浊	不甜	不是
青绿	浑浊	不甜	不是
青绿	浑浊	不甜	不是
深绿	浑浊	不甜	是

$甜度不甜$

故 $甜度甜度甜甜度不甜$

计算增益系数

$颜色颜色$

$响声响声$

$甜度甜度$

挑选根结点

注意到颜色、甜度的增益系数最大，我们可以任选其一，比如将颜色作为根节点。

第二次分类：颜色=青绿

数据集为：

响声	甜度	好瓜
浑浊	不甜	不是
浑浊	不甜	不是
清脆	甜	是
浑浊	不甜	不是

按照同样的方法计算出此时的信息熵：计算条件熵： $响声浑浊响声清脆$ 故 $响声$

$甜度甜甜度不甜$

故 $甜度$ 计算增益系数： $响声$

$甜度$

一样大，任选其一，若选择响声，注意到分类后的结果集中：

响声=清脆一定是好瓜
响声=浑浊一定不是好瓜

故不用继续分枝。

第二次分类：颜色=深绿

响声	甜度	好瓜
清脆	甜	是
浑浊	甜	是
浑浊	不甜	是
清脆	甜	是
清脆	甜	是

注意到结果集只有好瓜，故不用继续分枝。

生成决策树

graph TD
color[颜色]
sound[响声]
color --深绿--> 是好瓜
color --青绿--> sound
sound --清脆--> 是好瓜.
sound --浑浊--> 不是好瓜

CART

CART 算法基于基尼系数，它的运算比 ID3 更简单，其特点是只能生成二叉树。

CART 算法的思想：

计算数据集的基尼系数
计算数据集每个条件下的基尼系数
选择最小的基尼系数作为最优切分点
对切分出的新数据集开始新一轮计算
对于每一个数据集，如果其基尼系数小于某一阈值或数据个数小于某一阈值，就不再继续分枝

为了体现基尼系数的一些特性，下面模拟一套新的数据集：

颜色	响声	甜度	好瓜
青绿	浑浊	80	不是
青绿	浑浊	75	不是
深绿	清脆	80	是
深绿	浑浊	90	是
乌黑	清脆	85	不是
乌黑	清脆	95	是

计算颜色的基尼系数

当样本超过 2 类时，我们需要将样本切分成两类，逐个计算基尼系数后，再找到最佳的切分方法。

青绿为一类，深绿或乌黑为一类

$颜色青绿$

$颜色深绿或乌黑$

故 $颜色颜色青绿颜色深绿或乌黑$

深绿为一类，青绿或乌黑为一类

$颜色深绿$

$颜色青绿或乌黑$

故 $颜色颜色深绿颜色青绿或乌黑$

乌黑为一类，青绿或深绿为一类

$颜色乌黑$

$颜色青绿或深绿$

故 $颜色颜色乌黑颜色青绿或深绿$ 综上，最小的基尼系数为：青绿为一类，深绿或乌黑为一类；或深绿为一类，青绿或乌黑为一类，最小值为： $颜色$

计算响声的基尼系数

由于响声只有两种类型，故不需要多次切分： $响声浑浊$

$响声清脆$

故 $响声响声浑浊响声清脆$

计算甜度的基尼系数

注意到甜度是一组连续的变量，要求解连续变量的最优切分点，我们需要对分界位置进行逐个切分。

X = {75, 80, 85, 90, 95}

{75} 为一类，{80,85,90,95} 为一类

$甜度$

$甜度$ 故 $甜度甜度甜度$

{75,80}为一类，{85,90,95}为一类

$甜度$

故 $甜度甜度甜度$

{75,80,85}为一类，{90,95}为一类

$甜度$

故 $甜度甜度甜度$

{75,80,85,90}为一类，{95}为一类

$甜度$

故 $甜度甜度甜度$ 综上，当{75,80,85}为一类，{90,95}为一类时： $甜度$

确定最优切分点

$颜色甜度$

故任选其一，如选择甜度，则确定切分点为{75,80,85,90} 和 {95}.

第二次切分：甜度属于 {75,80,85,90}

颜色	响声	好瓜
青绿	浑浊	不是
青绿	浑浊	不是
深绿	清脆	是
深绿	浑浊	是
乌黑	清脆	不是

根据颜色切分

$颜色青绿$

$颜色深绿$

$颜色乌黑$

$颜色青绿或深绿$

$颜色青绿或乌黑$

$颜色深绿或乌黑$

故深绿为一类，青绿或乌黑为一类时： $颜色颜色深绿颜色青绿或乌黑$

根据响声切分

$响声浑浊$

$响声清脆$

故 $响声响声浑浊响声清脆$ 综上，选择颜色进行切分，最优切分点为颜色=深绿和颜色=青绿或乌黑。由于切分后结果唯一，故不需要再次切分。

第二次切分：甜度属于 {95}

颜色	响声	好瓜
乌黑	清脆	是

只有一种结果，故无需继续切分。

生成决策树

graph TD
sweet[甜度]
color[颜色]

sweet--小于等于90-->color
sweet--大于90-->是好瓜
color--深绿-->是好瓜.
color--青绿或乌黑-->不是好瓜

吴世涵的博客

【机器学习自学笔记2】决策树

ID3

计算信息熵

计算条件熵

确定颜色的情况

确定响声的情况

确定甜度的情况

计算增益系数

挑选根结点

第二次分类：颜色=青绿

第二次分类：颜色=深绿

生成决策树

CART

计算颜色的基尼系数

青绿为一类，深绿或乌黑为一类

深绿为一类，青绿或乌黑为一类

乌黑为一类，青绿或深绿为一类

计算响声的基尼系数

计算甜度的基尼系数

{75} 为一类，{80,85,90,95} 为一类

{75,80}为一类，{85,90,95}为一类

{75,80,85}为一类，{90,95}为一类

{75,80,85,90}为一类，{95}为一类

确定最优切分点

第二次切分：甜度属于 {75,80,85,90}

根据颜色切分

根据响声切分

第二次切分：甜度属于 {95}

生成决策树