机器学习-决策树ID3算法


昨天看到西瓜书中的决策树,决策树的核心就是如何选择特征来创建一颗树,今天实现了一个ID3的算法,ID3使用信息信息增益来选择特征;
信息增益的公式为:

Gain.png

其中,D表示数据集,a表示特征,V表示特征a包含特征值的数量,D^v表示特征a中特征值为v的数据集
Ent表示熵,定义如下:

Entropy.png

其中,|Y|表示label的数量,如果是二分类则|Y|=2,pk表示类别的概率
例如西瓜数据集:
编号,色泽,根蒂,敲声,纹理,脐部,触感,好瓜
1,青绿,蜷缩,浊响,清晰,凹陷,硬滑,是
2,乌黑,蜷缩,沉闷,清晰,凹陷,硬滑,是
3,乌黑,蜷缩,浊响,清晰,凹陷,硬滑,是
4,青绿,蜷缩,沉闷,清晰,凹陷,硬滑,是
5,浅白,蜷缩,浊响,清晰,凹陷,硬滑,是
6,青绿,稍蜷,浊响,清晰,稍凹,软粘,是
7,乌黑,稍蜷,浊响,稍糊,稍凹,软粘,是
8,乌黑,稍蜷,浊响,清晰,稍凹,硬滑,是
9,乌黑,稍蜷,沉闷,稍糊,稍凹,硬滑,否
10,青绿,硬挺,清脆,清晰,平坦,软粘,否
11,浅白,硬挺,清脆,模糊,平坦,硬滑,否
12,浅白,蜷缩,浊响,模糊,平坦,软粘,否
13,青绿,稍蜷,浊响,稍糊,凹陷,硬滑,否
14,浅白,稍蜷,沉闷,稍糊,凹陷,硬滑,否
15,乌黑,稍蜷,浊响,清晰,稍凹,软粘,否
16,浅白,蜷缩,浊响,模糊,平坦,硬滑,否
17,青绿,蜷缩,沉闷,稍糊,稍凹,硬滑,否
计算熵为:

entropy_result.png


计算色泽包含属性值的熵为:

sezegongshi.png


则色泽的信息增益为:

sezegain.png


其他的特征依次计算出来即可。
附件给出具体实现过程及数据集。
下图为最终的ID3决策树:

下载.png
已邀请:

要回复问题请先登录注册

返回顶部