划分数据集的最大原则：让无序的数据变得更加有序。组织杂乱无章数据的一种方法就是使用信息论度量信息。

在决策树的构造过程中，经常会碰到一个问题：特征很多，应该先使用哪个特征来做第一次划分，然后再用哪个特征来做第二次划分？

在数据划分完之后，信息发生的变化称为信息增益 。如果知道如何计算信息增益，就可以计算每个特征值划分数据集后获得的信息增益，获得信息增益最高的特征，就是最好的选择。

我们使用熵来计算信息增益。熵的计算公式： $$H=-\sum_{i=1}^{n}p(x_i) \log_{2}p(x_i)$$ 其中， \(x_i\) 是第 \(i\) 个特征， \(p(x_i)\) 是选择该特征的概率。一般概率就用频率来计算。在前面的例子中，只有两种特征，可以通过遍历数据集中的每一条数据，如果该数据有特征1或特征2，则进行累加. 最后利用累加完的数据来计算概率. 熵越大, 表示越混乱.

calcShannonEnt()代码解释. 输入参数: 数据集. 遍历数据集中的每一个特征, 分别累加, 以频率为概率, 计算熵.

信息增益就是新熵值-旧熵值.

splitDataSet()代码解释. 输入参数: 待划分的数据集; 第 \(n\) 个特征; 该特征对应的值value. 遍历每一条数据, 如果该数据的第 \(n\) 个特征是value, 则提取出来.

将熵与splitDataSet()结合起来, 找到最好的特征划分方式.

chooseBestFeatureToSplit()代码解释. 输入参数: 数据集, 该数据集可能有多个特征, 且每个数据集的最后一个元素是其分类结果. 计算整个数据集的熵baseEntroy, 初始化最好的信息收益bestInfoGain=0.0; 遍历数据集, 取出每个数据集的第 \(i\) 个特征, 存进列表, 此时这个列表中的数据有可能会重复; 将列表转成集合(set), python中, set里面的值是不重复的, 这是 python里面去除列表中重复元素的最快的方法; 遍历集合中的每个元素, 使用splitDataSet()划分数据集, 再用calcShannonEnt()计算每个子数据集的熵newEntroy; 信息增益infoGain=baseEntroy-newEntroy, 若新的信息增益大于bestInfoGain, 则更新bestInfoGain=infoGain; 返回bestInfoGain所对应的index.

majorityCnt()代码解释. 输入参数: 分类列表; 输出参数: 出现次数最多的分类名称.

createTree()代码解释. 输入参数: 数据集, 分类列表; 输出参数: 决策树. 遍历数据集, 取出每个数据集的最后一个元素(分类结果), 存入分类列表classList, 若数据集只有一种类别, 则直接返回; 如果使用完所有特征, 都不能将数据集划分成只有一个类别的分级, 则用majorityCnt()找出出现次数最多的分类名称; 使用chooseBestFeatureToSplit()找出最好信息收益对应的index; 根据index到输入参数中的分类列表中, 找出对应的分类名称, 将其作为决策树中的一个元素(决策树是嵌套字典), 并将分类名称从分类列表中删除; 遍历数据集, 将每条数据集中第 \(index\) 个特征找出来放进列表, 转成集合, 去除重复元素; 递归createTree(), 赋给myTree[bestFeatLabel][value], bestFeatLabel是字典的键; 返回myTree.

决策树的一个例子:{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}} 冒号前面的是键, 后面的是分类结果, 也可能是另一个字典.