使用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)=-(2/4)log₂(2/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的一个改进，但是总体来看，由于需要反复遍历数据，二者都是效率很低的算法。

文章系本人原创，转载请保持完整性并注明出自《四火的唠叨》