决策树学习及ID3算法
决策树学习
决策树学习是应用最广的归纳推理算法之一，它是一种逼近离散值函数的方法，对噪声数据又很好地健壮性且能够学习析取表达式。
下图是一颗典型的学习决策树
图一 一颗典型的学习决策树
所谓能够学习析取表达式是指，根据这颗决策树我们可以写出与之对应的表达式：
(Outlook=Sunny ^ Humidity=Normal) V (Outlook=Overcast) V (Outlook=Rain ^ Wind=Weak)
决策树学习最适合具有以下特征的问题：
- 实例是由“属性-值”对（pair）表示；（例如温度Temperatue用值Hot、Mild、Cold表示而不是连续的数值）
- 目标函数具有离散的输出值；（例如给每一个实例赋予一个bool类型的分类，如yes和no）
- 可能需要析取的描述；（上文已描述）
- 训练数据可以包含错误；（决策树学习对错误有很好的健壮性）
- 训练数据可以包含缺少属性值的实例。
ID3算法
如图一所示，该决策树把属性Outlook作为树的根节点被第一个测试，而之后是Humidity和Wind属性，为什么？测试属性的先后顺序有什么关系和标准？决策树算法的核心就是要解决这个问题。
ID3是一种自顶向下增长树的贪婪算法，在每个结点选取能最好地分类样例的属性。继续这个过程指导这棵树能完美分类训练样例，或所有的属性都已被使用过。
ID3算法概要：
该算法描述并没有解决其核心问题：在选取树的每个结点时，哪个属性是最佳的分类属性？
衡量属性价值的一个好的定量标准是什么呢？这里定义一个统计属性，称为“信息增益”（information gain），用来衡量给定的属性区分训练样例的能力。ID3算法在增长树的每一步使用这个信息增益标准从候选属性中选择属性。
信息增益
在学习信息增益之前，先来了解一个信息论中的一个名词：熵（entropy）。
熵刻画了任意样例集的纯度，它的取值为0-1。举个例子，一个箱子里有10个水果，或苹果或梨子，如果10个水果都是苹果或都是梨子，那说明水果的纯度最高，用熵来描述就是熵最低（0），如果5个苹果5个梨子，那么纯度最低，用熵来描述就是熵最高（1）。
信息论中熵的另一种解释更有利于理解：熵确定了要编码集合S中任意成员（即以均匀地概率随机抽出的一个成员）的分类所需要的最少二进制位数。
需要进一步了解可移步[百度百科-信息熵]
给定样例集S，计算对S进行布尔分类的熵的公式为：
我们定义0log0为0。
其中，p+是在S中正例的比例，p-是在S中反例的比例，参考上述水果的例子，假设苹果为正例，苹果个数为10，梨子个数为0时，1log1=0, 0log0=0，所以熵为0。如果苹果梨子各5个，那么p+ = 0.5, p- = 0.5，代入公式，熵为1。
一般的，如果目标属性具有c个不同的值，那么S相对于c个状态的分类的熵定义为：
那么，信息增益是什么意思呢？简单地说，一个属性的信息增益就是由于这个属性分割样例而导致的期望熵降低。
举例来说，一个水果是一个样例，如果要验证该水果是苹果还是梨子，最准确地方法是通过验证该水果的基因。但是水果本身的颜色、形状、口味等几个属性可以帮助我们对该水果进行分类，那么，哪个属性最有助于判断这个水果是苹果还是梨子呢？如果因为这个属性可以将水果进行苹果/梨子分类的熵降低，那么降低的熵的量就是信息增益，当然，如果信息增益越大（即降低的熵越多），那么这个属性就是最佳属性。
更精确的讲，一个属性A相对样例集合S的信息增益Gain(S, A)被定义为：
对水果的几个属性（颜色、形状、口味..）依次根据此公式计算信息增益，然后再互相比较，选择信息增益最大的属性为最佳属性。
所以，信息增益正是ID3算法增长树的每一步中选取最佳属性的度量标准。
