决策树(Decision Tree)
本文学习内容来自西瓜书和机器学习导论。
什么是决策树
1111
目的：产生一棵泛化能力强的决策树。泛化能力强指对非训练集的样本进行预测时仍能保持较高的准确性。
思想：分治(divide and conquer)
算法
22222
\((x_1,y_1)\)表示第一个样本，\(x_1\)为该样本在各个属性中值的集合\(\{x_{11},x_{12}...x_{1n}\}\)，\(y_1\)指该样本的类别（好瓜or坏瓜）。
图中算法为递归算法，共有三处可返回递归：
- line 2~3:当前节点下的所有样本均属于同一类别，将此节点记为叶节点，并标记出分类结果。
- line 5~7:当前节点下属性值为空（不再有可以用于划分的属性），或者所有样本在所有属性上取值相同，此时无法进行下一步划分，那么将此节点记为叶节点，分类结果为大多数样本的类别。
- line 11~12:当前无样本，无法划分，将其记为叶节点，分类结果为其父节点中大多数样本的类别。
第二点使用的是当前节点的后验分布。
后验分布：
\[
g(\theta|x)=c_xL(\theta,x)g(\theta)
\]
其中\(\theta\)为我们要估计的参数，这里可以理解为用于判断样本类别的函数，\(x\)为已知的参数，可以理解为我们现在对这些样本的属性值和类别都已知。\(c_x\)为\(f(x)\)的倒数，这里可视为常数。\(L(\theta,x)\)为最大似然估计。\(g(\theta)\)为先验分布。
第三点把父节点的样本分布作为当前节点的先验分布。
以上是我对西瓜书上内容的理解，不太准确，希望大神不吝赐教。
然后我们来介绍决策树的第一个算法：ID3。
ID3(Iterative Dichotomiser 3)
如何选择最优划分属性
在非叶节点中，我们需要找到一个属性，通过样本在该属性上取值的不同，将其分类，最终得到我们的决策树。
那么如何来评判这个属性是否适合用来划分样本集呢？
信息熵(Information Entropy)
信息熵度量样本的纯度，信息熵越小代表样本越纯。
| 样本 | 性别 |
|---|---|
| {1,2,3} | 男 |
| {4,5,6} | 女 |
| 样本 | 性别 |
|---|---|
| {1,2,3,4,5} | 男 |
| {6} | 女 |
以上两个样本集均为6个人，第一个样本集男女各为3人，第二个样本集男生达到5人，女生只有1人。我们称第二个样本集的纯度较高。
\[
Ent(D) = -\sum_{k=1}^\gamma p_k \log_2p_k
\]
其中，\(D\)表示所有用于计算样本。\(p_k\)表示样本属于第\(k\)个类别的概率。\(\gamma\)表示样本*有多少种不同的类别。
若所有样本均属于同一类别，此时我们记:\(0\log_20\equiv0\)。
仅仅了解信息熵是不够的，我们需要判断如果使用某个属性作为划分属性，那么是否会使分类后的样本纯度提高。
信息增益(Information Gain)
对于某个属性\(a\)以及样本集\(D\)，我们可以计算信息增益：
\[
Gain(D,a)=Ent(D)-\sum_{v=1}^V\frac{|D^v|}{|D|}·Ent(D^v)
\]
其中\(|D|\)表示\(D\)中样本的数量，\(|D^v|\)表示样本集中在\(a\)属性上值为\(v\)的样本数量
信息增益越大，表示用此属性进行划分后的样本集纯度提高程度越大。所以我们要找到：
\[
a^*=\mathop{\arg\max}_aGain(D,a)
\]
举个例子，对于西瓜书P76表4.1：
3333333
\(\gamma=2\)，好瓜or坏瓜。
\[
Ent(D) = -\frac{8}{17}·\log_2\frac{8}{17}-\frac{9}{17}·\log_2\frac{9}{17}
\]
我们选择属性“色泽 ”，可以看到:
\(V=3\)，分别为“青绿”，“乌黑”，“浅白”。
\(|D_1|=6\)，“青绿”，其中好瓜3个，坏瓜3个。
\[
Ent(D_1)=-\frac{3}{6}·\log_2\frac{3}{6}-\frac{3}{6}·\log_2\frac{3}{6}
\]
\(|D_2|=6\)，“乌黑”，其中好瓜4个，坏瓜2个。
\[
Ent(D_2)=-\frac{4}{6}·\log_2\frac{4}{6}-\frac{2}{6}·\log_2\frac{2}{6}
\]
\(|D_3|=5\)，“浅白”，其中好瓜1个，坏瓜4个。
\[
Ent(D_3)=-\frac{1}{5}·\log_2\frac{1}{5}-\frac{4}{5}·\log_2\frac{4}{5}
\]
则：
\[
Gain(D=全集,a=“色泽”)=Ent(D)-\frac{6}{17}Ent(D_1)-\frac{6}{17}Ent(D_2)-\frac{5}{17}Ent(D_3)
\]
然后我们在所有的属性中找到最优的属性，作为此节点的划分属性。然后对分类后的每一个样本子集递归计算最优划分属性。
如果？
| 序号 | 居住地 | 学业 | 性别 |
|---|---|---|---|
| 1 | 北京 | 初中 | 男 |
| 2 | 北京 | 高中 | 男 |
| 3 | 上海 | 初中 | 女 |
| 4 | 上海 | 高中 | 女 |