更多：决策树…
看到这是不是发现，这非常像程序员熟悉的 if else 语句？实际上，决策树是一种自上而下，对样本数据进行树形分类的过程，有一个根结点、若干个内部结点和若干个叶结点组成。每一个内部结点表示一个特征或树形，叶结点表示类别。
在决策树中，需要考虑的问题主要有结点划分、剪枝处理，结点划分是为了解决每次划分时应该使用什么特征，剪枝处理主要是为了解决过拟合问题。这一篇文章我们主要来看下如何进行结点划分。
一般来说，我们是希望划分后得到的子结点中所包含的样本尽可能属于同一类别，即结点的“纯度”越来越高。再直白的说就是希望划分时选择的特征能够对目标有更好的区分度。
常用的决策树有 ID3（Iterative Dichotomiser 3）、C4.5、CART（Classification And Regression Tree），它们在划分时采用的方式是有区别的，我们来分别看下。
最大信息增益
首先需要解释下熵和条件熵的含义。
假定当前样本集合 D 中第 k 类样本所占的比例为 \(p_k, (k = 1,2,…|y|)\) ，则数据集 D 的熵可以表示为：
如果熵越小，表明纯度越高。
有了数据集的熵之后，我们来看下某个离散特征 A 对于数据集 D 的条件熵。假设离散特征A包含了V个可能的取值 \(a_1,a_2,…,a_v\) ，将数据集 D 中所有特征 A 的值为 \(a_v\) 的样本记为 \(D_v\) 。这样，根据熵的定义可以计算出子数据集 Dv 的熵，将所有的子数据集 Dv 的熵求和便是离散特征 A 对于数据集D 的条件熵。 由于不同的 \(a_v\) 对应的样本个数不同，所以需要为不同的 \(D_v\) 赋予不同的权重 \(|D_v|/|D|\) 。这样，最终离散特征 A 对于数据集 D 的条件熵可以表示为：
有了数据集 D 的熵和离散特征 A 对于数据集D 的条件熵，那么，使用特征 A 来进行划分数据集 D 可获得信息增益（information gain）为：
一般来说，信息增益越大，使用该特征划分所获得的“纯度提升”就越大，所以每次可以选择获得最大信息增益的特征来进行划分结点。ID3 算法就是选择最大信息增益来划分结点的。
这里举一个示例来理解一下基于最大信息增益划分结点的过程。下面是一个包含了5 个样本的相亲数据集，每个样本表示一个男孩的各个条件（特征）以及女孩是否对他有意愿见面。
在这个问题中，整个数据集的熵为：
接下来，计算出“年龄”、“长相”、“工资”、“写代码”这 4 个特征对于整个数据集的条件熵：
接下来就能够计算每个特征的信息增益：
可以看到，“写代码”这个特征对应的信息增益最大，所以第一次划分是使用“写代码”这个特征来划分，在这个例子中，通过“写代码”这个特征划分能够将所有样本划分正确。但是在实际生活中，很难有这种只进行一次特征划分就将所有样本正确划分的情况，基本都需要进行多次划分。不过每次划分时的原理都是一样的。
最大信息增益比
信息增益反应的是给定条件以后不确定性减少的程度，它有一个弊端是偏向于取值数目较多的特征。为了解决这个问题，引入了信息增益比的概念。
其中
称为数据集 D 关于特征 A 的取值熵。C4.5 算法就是选择最大信息增益比来划分结点的。
现在来计算下相亲示例中每个特征的取值熵。
然后就可以计算出对应的信息增益比。
可以看到，相比于信息增益，信息增益比中“年龄”这个特征的值上升了，“长相”和“工资”特征的值下降了。
最小基尼系数
除了信息增益和信息增益比两种度量数据集“纯度”的方式外，基尼系数也可以来度量。
数据集 D 的基尼系数如下：
直观来说，Gini(D) 反映了从数据集 D 中随机抽取两个样本，其类别标记不一致的概率，因此基尼系数越小，数据集的纯度越高。
特征 A 的基尼系数定义如下：
CART 算法进行分类任务时每次都是选择基尼系数最小的特征及其对应的切分点进行划分的。此外，CART 算法在每个结点只会生成两个分支，也就是最后会生成二叉树。
如果说 CART 算法生成的是二叉树，这就引入了一个问题，很多离散特征的取值可能会有很多，那如何将它转为只包含两个取值呢？答案是可以通过看某个的取值是否是等于其中的一个值来将它进行二分。
举个例子来说明，比如“长相”这个特征包含了“帅”、“一般”、“丑”三种取值，可以将它转为“长相是否为帅”，可以得到：
该特征对应的基尼系数为：
通过这种方式，也可以求出其他离散特征的基尼系数，最后选择基尼系数最小的特征来进行划分结点。
可以看到，通过决策树来解决分类问题，会非常简单，同时解释性会非常好。但是决策树决策树如果不做限制完全生长，很容易过拟合。此外，前面介绍的特征划分都仅限于离散特征，关于连续特征如何处理并没有说明。这些我们放在下一篇文章来介绍。
参考：
- 诸葛越.百面机器学习.第3章（经典算法）
- 周志华.机器学习.第四章（决策树）