决策树
关键是划分最优属性
结点的纯度要越来越高，三种度量节点纯度的指标：
-
信息增益
香农用“信息熵”来描述信源的不确定性
信息熵：当前样本集合D中第$i$类样本所占的比例为$p_i$，则D的信息熵定义为：$$
H(D) = -\sum_{i=1}^{n} p_i \log_2 p_i
$$H(D) 越大，数据集 D 的纯度越低；H(D) 越小，数据集 D 的纯度越高。对于二分类问题，n等于2.
假设离散属性A有V个不同的取值，按照A的每个取值划分数据集D后得到V个子集$D_1, D_2, …, D_V$，则属性A对数据集D的信息增益定义为：$$
G(D, A) = H(D) - \sum_{v=1}^{V} \frac{|D^v|}{|D|} H(D^v)
$$其中，$D^v$ 表示属性A取第v个值时，数据集D中对应的子集。
信息增益准则对可取值较多的属性有偏好，倾向于选择取值较多的属性进行划分。 -
增益率
增益率是信息增益的改进版本，旨在解决信息增益对取值较多属性的偏好问题。增益率定义为：$$
GR(D, A) = \frac{G(D, A)}{IV(A)}
$$其中，$IV(A)$ 是属性A的信息增益率，定义为：
$$
IV(A) = -\sum_{v=1}^{V} \frac{|D^v|}{|D|} \log_2 \frac{|D^v|}{|D|}
$$增益率准则对可取值数目较少的属性有所偏好
-
基尼系数
基尼系数是 CART（Classification and Regression Trees）算法中使用的纯度度量指标。对于数据集D，基尼系数定义为：$$
Gini(D) = 1 - \sum_{i=1}^{n} p_i^2
$$基尼系数越小，数据集 D 的纯度越高；基尼系数越大，数据集 D 的纯度越低。对于二分类问题，n等于2.
决策树算法：
- 决定分类属性
- 对目前的数据表，建立一个节点N
- 如果数据表中数据都属于一个类，那么N就是一个叶子节点，标记为该类，并返回
- 如果数据表中没有属性了，那么N就是一个叶子节点，标记为数据表中样本数最多的类，并返回
- 否则，根据属性选择方法选择一个最优属性A，并根据A的不同取值划分数据表，得到若干个子数据表
- 对于每个子数据表，递归调用步骤2-5，建立子节点，并将其连接到N上
决策树剪枝：
预剪枝
后剪枝
回归树：
连续属性离散化技术：
考虑n-1个切分点，计算每个切分点的信息增益，选择信息增益最大的切分点进行划分。
属性缺失：
每个样本的部分属性值缺失。
如果大多数缺失在同一个属性，就直接舍弃这个属性。
如果属性缺失较为分散，可以使用样本的其他属性来预测缺失值，或者在计算信息增益时只考虑非缺失值的样本。