ID3决策树算法

        学习算法的重点在于如何选择最优划分属性。显然我们希望分支节点尽可能的属于同一个类--即希望节点的纯度越高越好。关键在于我们如何定义节点的纯度。

        一般我们采用的是信息熵的指标。其定义如下

信息熵

        信息熵的值越小，则节点的纯度越高。（熵用于表示事物的混乱程度）

        为了选择最佳划分属性，则我们需要对每个属性都进行信息熵的计算。对每个属性（即特征）而言，利用每个属性的多个分类（比如高矮这一属性就可以分为：<160，160-180，>180等等），分别计算划分后的样本空间的信息熵，并利用样本空间的样本数量为权重相加。为了表达纯度的提升，我们用最初的信息熵减去分类之后的信息熵，就可以得到熵减，也就是纯度的提升(称为信息增益)，具体计算公式如下（绝对值符号代表该空间的样本数量）：

信息增益

        我们可以通过计算每个属性的信息增益，选择信息增益最大的那项属性来进行划分，这就是ID3决策树学习算法。

C4.5决策树算法

        在ID3决策树学习算法中，我们采用信息增益准则来决定最佳划分属性，然而信息增益准则会偏好可取值数目较多的属性，为了减少这种偏好所带来的不利影响，著名的C4.5决策树算法不直接使用信息增益，而是利用增益率来选择最佳划分属性。增益率的定义如下：

增益率

        分子仍采用之前的信息增益，而分母被称为属性a的固有值。属性a的可能取值越多，其固有值也会越大。增益率准则通过添加分母的方式抑制了对可取值较多属性的抑制，但不幸的是，这种抑制是过量的，增益率准则会偏好可取值较少的属性。

CART决策树算法

        cart决策树采用“基尼指数”来划分属性。基尼系数的定义如下

基尼系数

        基尼系数可以直观理解为从数据集D中随机选取两个样本，其属性不一致的概率。因此基尼系数越小，数据集的纯度越高。同样，属性a的基尼指数定义为分类后的样本空间乘以权重的和。

基尼指数