决策树（ID3）
决策树的构建
构造决策树时，所需要解决的第一个问题就是，每划分一个分支时，应该根据哪一维特征进行划分。这时候我们需要定义某种指标，然后对每一维特征进行该指标的评估，最后选择指标值最高的特征进行划分。
划分完毕之后，原始数据集就被划分为几个数据子集。如果某一个下的数据属于同一类型，则算法停止；否则，重复划分过程。
伪代码（创建分支）
|
|
那么接下来的重点便是如何寻找划分数据集的最好特征，在这里我们使用ID3算法中使用的划分数据集的方法，也即根据熵来划分。
信息增益
熵
划分数据的核心思想是将无序的数据变得更加有序。而一个数据有序程度可以进行量化表示，也就是信息，其度量方式就是熵。其显然，数据集划分前后其所含的信息会发生变化，这个变化便称为信息增益。
熵定义为信息的期望，其中信息的定义如下，信息一般针对的对象为多个类别中的某一个类别：
$$l(x_i) = -log_{2}p(x_i)$$
其中$x_i$表示某一类别，$p(x_i)$表示从多个类别中选择该类别的概率。
接下来，熵的定义如下：
$$H = \sum_{i=1}^{n}p(x_i)l(x_i)=-\sum_{i=1}^{n}p(x_i)log_{2}p(x_i)$$
信息增益定义如下：
$$IG(S|T) = H(S) - \sum_{value(T)} \frac{|S_v|}{|S|} H(S_v)$$
其中$S$ 为全部样本集合，$value(T) $是属性 $T$所有取值的集合，$v$ 是 $T$ 的其中一个属性值，$S_v$是 $S$ 中属性 $T$ 的值为 $v$ 的样例集合，$|S_v|$ 为 $S_v$ 中所含样例数，$|S|$ 为 $S$ 中所含样例数。
代码实现：
|
|
为了进行测试，以及之后的算法运行，我们写一个十分naive的数据生成方法：
|
|
注意，这里的labels并不代表分类标签，yes以及no才是，labels代表特征名。
下面进行一个简单的demo:
|
|
熵越高，表明数据集中类别数越多。
另一个度量无序程度的方法是基尼不纯度（Gini impurity）。
基尼不纯度
基尼不纯度的定义为，对于每一个节点，从所有类别标签中随机选择一个，选择出来的类别标签与其本身的类别标签不一致的概率之和。形式化地定义如下：
$$G = \sum_{i \ne j}p(x_i)p(x_j) = \sum_{i}p(x_i)\sum_{j \ne i}p(x_j) = \sum_{i}p(x_i)(1-p(x_i)) = \sum_{i}p(x_i) - \sum_{i}(p(x_i))^2 = 1 - \sum_{i}(p(x_i))^2$$
代码实现如下：
|
|
同样进行一个简单的demo：
|
|
最后再介绍一种度量无序程度的方式，误分类不纯度。
误分类不纯度
定义如下：
$$M = 1 - \max_{i}(p(x_i))$$
代码实现如下：
|
|
进行一个简单的demo:
|
|
最后用一个图来总结一下这三种不纯度度量的函数图像（以二类情况为例）
[Ref: http://www.cse.msu.edu/~cse802/DecisionTrees.pdf]：
数据划分
根据以上，数据划分的思路是，基于每一维特征的每一个值进行划分，并计算划分前后的信息增益，最后选取增益最大的特征及其所对应的值进行划分，由于这里运用的是ID3算法，因此选择的信息度量方式是熵。
代码实现如下：
|
|
由以上代码（ID3算法）可以看出，其计算熵的依据是根据最后一个特征，是否这种naive的选取方式能够达到平均的最好结果？另外，其划分依据仅仅根据划分一次后的子数据集的熵之和，属于一种贪心策略，这样是否可以达到最优解？
递归构建决策树
既然是递归算法，那么必须设定递归结束条件：
- 遍历完所有属性
- 每个分支下的数据都属于相同的分类
这里存在一个问题，如果遍历完所有属性后，某些分支下还是存在多个分类，这种情况下一般采用多数表决的方式，代码实现方式如下：
|
|
下面进行树的创建：
|
|
下面进行一下简单的测试：
|
|
可见决策树已经构造成功（图形化如下所示），但是这显然不够，我们需要的是用决策树进行分类。
决策树分类
demo如下：
|
|
C4.5
C4.5算法是由ID3算法引申而来，主要改进有以下两点：
- 选取最优分裂属性时根据信息增益率 (IGR)
- 使算法对连续变量兼容
下面分别对分裂信息以及信息增益率进行定义：
$$IGR = \frac{IG}{IV}$$
因此只需对ID3算法的代码做一些改动即可，为了兼容ID3， 具体实现如下：
|
|
下面需要解决的问题是连续变量的问题，为了实验的方便，我们更改一下naive的数据生成方法（Ref: http://blog.csdn.net/lemon_tree12138/article/details/51840361 ）：
|
|
假设我们选择了温度属性，则被提取的关键数据为：
[[85, No], [80, No], [83, Yes], [70, Yes], [68, Yes], [65, No], [64, Yes], [72, No], [69, Yes], [75, Yes], [75, Yes], [72, Yes], [81, Yes], [71, No]]
现在我们对这批数据进行从小到大进行排序，排序后数据集就变成：
[[64, Yes], [65, No], [68, Yes], [69, Yes], [70, Yes], [71, No], [72, No], [72, Yes], [75, Yes], [75, Yes], [80, No], [81, Yes], [83, Yes], [85, No]]
绘制成如下图例：
当我们拿到一个已经排好序的（温度，结果）的列表之后，分别计算被某个单元分隔的左边和右边的分裂信息，比如现在计算 index = 4 时的分裂信息。则：
$$IV(v_4) = IV([4, 1], [5, 4]) = \frac{5}{14}IV([4, 1]) + \frac{9}{14}IV([5, 4])$$
$$IV(v_4) = \frac{5}{14}(-\frac{4}{5} \log_{2} \frac{4}{5} - \frac{1}{5} \log_{2} \frac{1}{5}) + \frac{9}{14}(-\frac{5}{9} \log_{2} \frac{5}{9} - \frac{4}{9} \log_{2} \frac{4}{9})$$
下图表示了不同分裂位置所得到的分裂信息：
最后给出完整的代码实现 (最后的Classify方法还需修改)：
trees.py
|
|
一个小demo：
|
|