决策树：ID3、C4.5和CART特征选择方式

1 前言

该文章主要目的是记录ID3、C4.5和CART特征选择方式，这里只对决策树进行简单介绍。
决策树（Decision Tree）算法是一种有监督学习算法，它利用分类的思想，根据数据的特征构建数学模型，从而达到数据的筛选和决策的目标。它的重点是将看似无序、杂乱的已知数据，通过某种技术手段转化成可以预测未知数据的树状模型。每一条从根节点（对最终分类结果贡献最大的属性）到叶子节点（最终分类结果）的路径都代表一条决策的规则。

在预测时，从根节点出发，根据特征实际值，转移至某个子节点，直至叶子节点，从而完成决策。
在决策树构建的过程中，首先由所有的数据构成根节点，根据某种策略对某个特征进行划分，数据集被分割成若干份，每一份构成一个子节点。进而对子节点继续划分，直至决策树生成完毕。
常用的决策树构建算法有ID3、C4.5和CART等，它们之间关键区别是用于划分数据集的特征的选择策略不同，以下对其策略进行介绍。

2 ID3

ID3算法使用信息增益指导决策树的划分。
首先介绍概念：熵。熵表示随机变量不确定性的度量。先给出公式：
$Info(Y)=-{\sum }_{y}p(y)\log p(y)$
对于决策树中的某一个节点，可以通过上述公式计算熵，其中$Y$表示类别，$y$表示具体的类别值。熵越小越好。
信息增益表示特征$A$使得类Y的不确定性减小的程度。公式如下：
$Gain(D,A)=Info(D)-Info(D,A)$
D是数据集，$A$表示被划分的特征。$Info(D)$表示某个节点的熵，$Info(X,D)$表示当前节点按照$A$划分之后，得到的子节点的熵的加权和。
$Info(D,A)={\sum }_a\frac{|D_{A=a}|}{|D|}Info(D_{A=a})$
$D_{A=a}$表示$A$为a的样本组成的子节点，权重是$D_{A=a}$的样本数量与$D$的样本数量的比值。
每次划分，计算每个特征的$Gain(D,A)$，选择$Gain(D,A)$最大的特征划分数据集。

3 C4.5

C4.5相比于ID3的主要区别是使用信息增益率替代信息增益。信息增益率是信息增益与自身熵$IV(D,A)$的比值。
$Gain\_ratio(D,A)=\frac{Gain(D,A)}{IV(D,A)}$
自身熵表示当前节点划分的程度，划分的子节点越少，越均匀，自身熵越小，信息增益率越大。
$IV(D,A)=-{\sum }_a\frac{|D_{A=a}|}{|D|}\log \frac{|D_{A=a}|}{|D|}$
每次划分，计算每个特征的信息增益率，选择信息增益率最大的特征划分数据集。

4 CART

相比于上面的方法，CART使用基尼（Gini）指数选择特征。
基尼（Gini）指数使用$p(y)(1-p(y))$替代$p(y)\log p(y)$，公式如下：
$Gini(D)={\sum }_{i}p(y)(1-p(y))=1-{\sum }_i{p}^2(y)$
做这个替代有什么影响呢。可以看一下图像。
$p(y)\log p(y)$为：

$p(y)(1-p(y))$为：

可以看到$p(y)\log p(y)$图像比较倾斜，而$p(y)(1-p(y))$比较对称，在0.5取到最大值。一个类别准确率为0.5是最具不确定性的，也就是最差的，所以从图像上看明显$p(y)(1-p(y))$更符合目标。
D根据特征A被划分为多个子结点后，得到的子节点的基尼（Gini）指数的加权和。
$Gini(D,A)={\sum }_a\frac{|D_{A=a}|}{|D|}Gini(D_{A=a})$
每次划分，计算每个特征的$Gini(D,A)$，选择$Gini(D,A)$最大的特征划分数据集。