决策树系列（三）——ID3
决策树系列（三）——ID3
预备知识：决策树
初识ID3
回顾决策树的基本知识，其构建过程主要有下述三个重要的问题：
（1）数据是怎么分裂的
（2）如何选择分类的属性
（3）什么时候停止分裂
从上述三个问题出发，以实际的例子对ID3算法进行阐述。
例：通过当天的天气、温度、湿度和季节预测明天的天气
表1 原始数据
|
当天天气 |
温度 |
湿度 |
季节 |
明天天气 |
|
晴 |
25 |
50 |
春天 |
晴 |
|
阴 |
21 |
48 |
春天 |
阴 |
|
阴 |
18 |
70 |
春天 |
雨 |
|
晴 |
28 |
41 |
夏天 |
晴 |
|
雨 |
8 |
65 |
冬天 |
阴 |
|
晴 |
18 |
43 |
夏天 |
晴 |
|
阴 |
24 |
56 |
秋天 |
晴 |
|
雨 |
18 |
76 |
秋天 |
阴 |
|
雨 |
31 |
61 |
夏天 |
晴 |
|
阴 |
6 |
43 |
冬天 |
雨 |
|
晴 |
15 |
55 |
秋天 |
阴 |
|
雨 |
4 |
58 |
冬天 |
雨 |
1.数据分割
对于离散型数据，直接按照离散数据的取值进行分裂，每一个取值对应一个子节点，以“当前天气”为例对数据进行分割，如图1所示。
对于连续型数据，ID3原本是没有处理能力的，只有通过离散化将连续性数据转化成离散型数据再进行处理。
连续数据离散化是另外一个课题，本文不深入阐述，这里直接采用等距离数据划分的李算话方法。该方法先对数据进行排序，然后将连续型数据划分为多个区间，并使每一个区间的数据量基本相同，以温度为例对数据进行分割，如图2所示。
2. 选择最优分裂属性
ID3采用信息增益作为选择最优的分裂属性的方法，选择熵作为衡量节点纯度的标准，信息增益的计算公式如下：
其中， 表示父节点的熵；
表示节点i的熵，熵越大，节点的信息量越多，越不纯；
表示子节点i的数据量与父节点数据量之比。
越大，表示分裂后的熵越小，子节点变得越纯，分类的效果越好，因此选择
最大的属性作为分裂属性。
对上述的例子的跟节点进行分裂，分别计算每一个属性的信息增益，选择信息增益最大的属性进行分裂。
天气属性：（数据分割如上图1所示）
温度：（数据分割如上图2所示）
湿度：
季节：
由于最大，所以选择属性“季节”作为根节点的分裂属性。
3.停止分裂的条件
停止分裂的条件已经在决策树中阐述，这里不再进行阐述。
（1）最小节点数
当节点的数据量小于一个指定的数量时，不继续分裂。两个原因：一是数据量较少时，再做分裂容易强化噪声数据的作用；二是降低树生长的复杂性。提前结束分裂一定程度上有利于降低过拟合的影响。
（2）熵或者基尼值小于阀值。
由上述可知，熵和基尼值的大小表示数据的复杂程度，当熵或者基尼值过小时，表示数据的纯度比较大，如果熵或者基尼值小于一定程度时，节点停止分裂。
（3）决策树的深度达到指定的条件
节点的深度可以理解为节点与决策树跟节点的距离，如根节点的子节点的深度为1，因为这些节点与跟节点的距离为1，子节点的深度要比父节点的深度大1。决策树的深度是所有叶子节点的最大深度，当深度到达指定的上限大小时，停止分裂。
（4）所有特征已经使用完毕，不能继续进行分裂。
被动式停止分裂的条件，当已经没有可分的属性时，直接将当前节点设置为叶子节点。
程序设计及源代码(C#版本)
（1）数据处理
用二维数组存储原始的数据，每一行表示一条记录，前n-1列表示数据的属性，第n列表示分类的标签。
static double[][] allData;
为了方便后面的处理，对离散属性进行数字化处理，将离散值表示成数字，并用一个链表数组进行存储，数组的第一个元素表示属性1的离散值。
static List<String>[] featureValues;
那么经过处理后的表1数据可以转化为如表2所示的数据：
表2 初始化后的数据
|
当天天气 |
温度 |
湿度 |
季节 |
明天天气 |
|
1 |
25 |
50 |
1 |
1 |
|
2 |
21 |
48 |
1 |
2 |
|
2 |
18 |
70 |
1 |
3 |
|
1 |
28 |
41 |
2 |
1 |
|
3 |
8 |
65 |
3 |
2 |
|
1 |
18 |
43 |
2 |
1 |
|
2 |
24 |
56 |
4 |
1 |
|
3 |
18 |
76 |
4 |
2 |
|
3 |
31 |
61 |
2 |
1 |
|
2 |
6 |
43 |
3 |
3 |
|
1 |
15 |
55 |
4 |
2 |
|
3 |
4 |
58 |
3 |
3 |
其中，对于当天天气属性，数字{1，2，3}分别表示{晴，阴，雨}；对于季节属性{1，2，3，4}分别表示{春天、夏天、冬天、秋天}；对于明天天气{1，2，3}分别表示{晴、阴、雨}。
（2）两个类：节点类和分裂信息
a）节点类Node
该类存储了节点的信息，包括节点的数据量、节点选择的分裂属性、节点输出类、子节点的个数、子节点的分类误差等。
View Code （篇幅限制，源码参见原微博）
b）分裂信息类SplitInfo
该类存储节点进行分裂的信息，包括各个子节点的行坐标、子节点各个类的数目、该节点分裂的属性、属性的类型等。
View Code（篇幅限制，源码参见原微博）
（3）节点分裂方法findBestSplit(Node node,List<int> nums,int[] isUsed)，该方法对节点进行分裂，返回值Node
其中：
node表示即将进行分裂的节点；
nums表示节点数据对应的行坐标列表；
isUsed表示到该节点位置所有属性的使用情况（1：表示该属性不能再次使用，0：表示该属性可以使用）；
findBestSplit主要有以下几个组成部分：
1）节点分裂停止的判定
判断节点是否需要继续分裂，分裂判断条件如上文所述。源代码如下：
View Code（篇幅限制，源码参见原微博）
2）寻找最优的分裂属性
寻找最优的分裂属性需要计算每一个分裂属性分裂后的信息增益，计算公式上文已给出，其中熵的计算代码如下：
View Code（篇幅限制，源码参见原微博）
3）进行分裂，同时子节点也执行相同的分类步骤
其实就是递归的过程，对每一个子节点执行findBestSplit方法进行分裂。
全部源代码：
View Code（篇幅限制，源码参见原微博）
（注：上述代码只是ID3的核心代码，数据预处理的代码并没有给出，只要将预处理后的数据输入到主方法findBestSplit中，就可以得到最终的结果）
总结
ID3是基本的决策树构建算法，作为决策树经典的构建算法，其具有结构简单、清晰易懂的特点。虽然ID3比较灵活方便，但是有以下几个缺点：
（1）采用信息增益进行分裂，分裂的精确度可能没有采用信息增益率进行分裂高
（2）不能处理连续型数据，只能通过离散化将连续性数据转化为离散型数据
（3）不能处理缺省值
（4）没有对决策树进行剪枝处理，很可能会出现过拟合的问题