使用 ID3 算法构造决策树

决策树

决策树是一个预测模型，它代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。

这张图很好地解释了决策树：

明天要不要出去玩？

• 晴天：
  • 潮湿：不出去
  • 不潮湿：出去
• 阴天：出去玩
• 雨天：
  • 刮风：不出去
  • 不刮风：出去

例子中可以找到两层的分类依据属性，第一层是晴/阴/雨，第二层是是否潮湿和是否刮风，分类依据的确定和先后顺序对决策树的质量有决定性的影响。另外，在实际构造决策树时，经常要进行剪枝，主要是因为数据中往往存在一些噪音数据，或者是存在分类过细的问题，反而失去了分类的意义。一种是先剪枝，在构造树的过程中，当某个节点满足剪枝条件，则直接停止此分支的构造；还有一种是后剪枝，先构造完成完整的决策树，再通过某些条件遍历树进行剪枝。

ID3 算法

ID3 算法是 J. Ross Quinlan 提出的分类预测算法，它的核心是用贪心算法来根据“ 信息熵” 分类。何为信息熵？这个概念还是香农（C. E. Shannon）提出来的，用以表示信息的不确定性。信息不确定的因素越多，这个熵就越大。

如果一组数据由 {d1,d2,…,dn} 构成，其和是 sum，那么信息熵可以表示为：

下面举例来说明这个公式：

假使说我们要研究狗的智商（目标属性），潜在的关联因素包括颜色和毛的长度。

颜色（color）	毛的长度（length）	智商（IQ）
black	长	高
white	长	高
white	短	高
white	短	低

3 次出现“ 高” 智商，1 次出现“ 低智商”，所以目标属性 IQ 的信息熵：H_IQ(D)=-(3/4)log₂(3/4)-(1/4)log₂(1/4)

color 属性在取不同的值对应目标属性 IQ 的信息熵：

• 在 color 取值为 black 的时候，IQ 只取“ 高” 这个值：H_color(D_black)=-(1/1)log₂(1/1)
• 在 color 取值为 white 的时候，IQ 取值有两个“ 高”，一个“ 低”：H_color(D_white)=-(1/3)log₂(1/3)-(2/3)log₂(2/3)

而 color 属性的整体信息熵是上述二者的加权平均值：H_color(D)=(1/4)H_color(D_black)+(3/4)H_color(D_white)。同样可以求得 H_length(D)。

现在定义信息增益 Gain_color=H_IQ(D)-H_color(D)，Gain_length=H_IQ(D)-H_length(D)，它是信息熵的有效减少量，值越高，说明目标属性 IQ 在参考属性处损失的信息熵越多，也就是失去的不确定性越多，那么在决策树进行分类的时候，这个参考属性应该越早作为决策的依据属性。

这个例子中如果 Gain_length > Gain_color，说明 length 比 color 要对 IQ 有更大的影响，所以决策树中，要先依据 length 来进行分类。

在实际应用中，往往引入一个“ 阈值”，当节点下的任意一分类所占百分比超过这个阈值时，就不再进行分类，以避免产生出过小的没有实际意义分类节点。

ID3 算法也存在诸多不足，比如分类偏向于取值数量，只能处理离散数据等等问题。C4.5 算法是对 ID3 的一个改进，但是总体来看，由于需要反复遍历数据，二者都是效率很低的算法。

文章未经特殊标明皆为本人原创，未经许可不得用于任何商业用途，转载请保持完整性并注明来源链接 《四火的唠叨》