决策树

### 概述
决策树模型是一种对实例进行分类的树形结构。决策树由结点`node`和有向边`directed edge`组成。
结点有两种类型：
- 内部结点：表示一个特征或属性
- 叶节点：表示一个分类

### 熵
在信息论与概率统计中，熵`entropy`表示随机变量的不确定性。熵越大，随机变量的不确定性越大。
设$$X$$是一个离散型随机变量，其概率分布为
```latex
P(X=x_{i})=p_{i}
```
则随机变量$$X$$的熵定义为：
```latex
H(X)=-\sum_{i=1}^{n}p_{i}logp_{i}
```
对于二项分布(伯努利分布)，随机变量只取两个值0和1，其概率分布为：
```latex
P(X=1)=p \qquad \\
P(X=0)=1-p
```
它的熵为：
```latex
H(p)=-plogp - (1-p)log(1-p)
```
![](/media/202212/QQ截图20221204104354_1670121843.png)
- 当`p=0`或`p=1`时，`H(p)=0`，表示随机变量完全没有不确定性；
- 当`p=0.5`时，`H(p)=1`，熵取得最大值，表示随机变量的不确定性最大；

### 决策树特征选择的方法
#### 信息增益
> 信息增益(Information gain)表示不确定性减小的程度，也就是熵减小的值

决策树的学习使用信息增益准则来选择特征。
给定训练数据集X和特征A，熵H(X)表示对数据集X进行分类的不确定性，条件熵H(X|A)表示在特征A给定的条件下对数据集X进行分类的不确定性，那么它们的差，即信息增益，就表示由于特征A而使得对数据集X的分类不确定性减少的程度。
```latex
Gain = H(X) - H(X|A)
```
显然，信息增益依赖所选择的特征，不同的特征有不同的信息增益。
信息增益大的特征有更强的分类能力。
根据信息增益准则选择特征的方法是：
> 对训练数据集X，计算其每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征

#### 信息增益比
以信息增益作为划分训练数据集的准则，存在偏向于选择取值较多的特征的问题。使用信息增益比可以对这一问题进行校正。这是特征选择的另一个准则。

#### 基尼系数
> 基尼系数反应的是：从数据集D中随机抽取两个样本，其类别标记不一样的概率
> Gini(D) 越小，说明数据集D纯度越高
```latex
Gini(D)=\sum p_{i}(1-p_{i}) \\
\ \\
\quad \quad \ \ =1-\sum p_{i}^2
```

### 常见的决策树算法
- ID3算法：使用信息增益来选择特征；
- C4.5算法：使用信息增益比来选择特征；
- CART算法：使用基尼系数来选择特征；

### 分类树与回归树
- 在分类决策树中，特征变量是离散型变量，使用信息熵来表示混乱程度，叶子结点的众数表示分类结果；
- 在回归决策树中，特征变量是连续型变量，使用均方差表示混乱程度，叶子结点的平均数作为结果；

### 参考
> [CART 决策树算法](https://zhuanlan.zhihu.com/p/139523931)