决策树

   这是一颗决策树，根据天气状况来判断某天是否适合打网球。

假设某一天情况是这样的，（天气：晴天；温度：高温；湿度：高，风力：强），那么按照这颗决策树，这一天不适合打网球。

   决策树不但能表示属性的合取，而且能表示析取，比如上面的决策树，表示适合打网球的条件为：阴天或者（晴天并且湿度正常）或者（雨天并且风力弱）。实际上决策树能表示自变量和因变量都为有限个离散值的所有函数。

ID3算法

   决策树的每个节点都是一个属性，根据属性测试的不同结果，产生不同的分枝。ID3算法优先选择信息增益高的属性。信息增益的公式：

上面的Ent表示信息熵：

下面举例说明：

   整个数据集的信息熵：

计算色泽这个属性的信息增益。色泽包括三个值青绿、乌黑、浅白。分别记为D¹(色泽=青绿)，D²(色泽=乌黑)，D³(色泽=浅白)。

   色泽的信息增益为：

   同理，可算出其他属性的信息增益：

纹理的信息增益最大，所以决策树选择这个属性作为根节点。根据属性值，把样例分到不同的分支。

然后在各个分支上，再重复上述过程，优先选择增益信息高的节点。最后得到的决策树如下：

ID3算法的归纳偏好：

ID3算法的搜索范围是完整的假设空间（即能表示任何有限的离散值函数的空间），每个假设对应于一棵决策树。但它不彻底地搜索这个空间，它有两个偏好：优先选择较短的树，和那些信息增益高的属性更靠近根节点的树。这样的偏好叫优选偏好。

前面的说的候选消除算法，搜索范围是不完全的假设空间，但它彻底地搜索这个空间。这种偏好叫限定偏好。Find-s算法，既有限定偏好，又有优选偏好。

一般来说，优选偏好比限定偏好更好，因为它保证目标函数在假设空间中。

C4.5算法：

ID3的信息增益准则，偏爱那些值较多的属性，这有时会带来不利的影响。比如如果在上面的例子里，把编号也作为一个属性，则它的信息增益为0.998。只利用这个属性就可以把样本区分开。但这样的决策树没有泛化能力，不能对新样本进行预测。

为了克服这个问题，C4.5算法用增益率代替信息增益，增益率通过引入IV项来惩罚类似编号这样的属性：

决策树算法的其他问题：

   1、过拟合

机器学习有时出现过拟合现象，即处理训练数据时效果很好，但处理测试数据时效果欠佳。解决这问题的一个方法就是对决策树进行剪枝。剪枝分两种，包括先剪枝和后剪枝。

先剪枝就是在决策树的生成过程中，提前终止决策树的生长。后剪枝是从训练集生成一棵完整的决策树，然后自底向上对非叶节点进行考察。若将该节点对应的子树剪掉，将其变成叶节点，用子树中最频繁的类别来标记。如果这样能提供决策树的泛化能力，则进行剪枝。

2、连续值

如果属性的值是连续的，可将其分类后再用决策树算法。比如温度给出的是具体的数值，样例的温度数分别为：40,48,60,72,80,90。计算最大值和最小值的平均值：(40+90)/2=65,大于65把它的值设为高，否则设为低。

3、不同成本的属性

在实际应用中，获取属性的值是需要成本的。比如疾病检测时，用下列属性来描述患者：体温、脉搏、血液化验、切片检查等。获取这些属性在成本方面区别非常大。要权衡信息和成本两个方面，来确定决策树应优先考虑哪些属性。