python实现决策树C4.5算法(数据挖掘算法系列之三)

By | 2016-12-15

关于C4.5

C4.5算法是ID3算法的改进版本,与ID3的主要区别在于属性选择的衡量标准上。ID3算法是通过选择最大的信息增益,而C4.5算法的分枝指标采用增益比例

关于增益比例

信息增益是一种衡量最优分支属性的有效函数,但是它倾向于选择具有大量不同取值的属性,从而产生许多小而纯的子集。例如ID,姓名,日期等。因而使用增益比例来代替信息增益作为新的指标来降低这种情况下的增益。

训练样本关于属性值的信息量(熵)split_info(D,A)的计算公式如下:

样本在A上的取值分布越均匀,split_info的值就越大。split_info用来衡量属性分裂数据的广度和均匀度。

属性A的增益比例gain_ratio(D,A)计算公式如下:

一个属性分割样本的广度越大,均匀性越强,该属性的split_info越大,增益比例就越小。因此,split_info降低了选择那些值较多且均匀分布的属性的可能性。

python实现

C4.5的实现与ID3是一样的,区别只是在于分支选择标准上。

计算split_info(D,A)

计算gain_ratio(D,A)

修改完后运行测试,发现出现除零错误,currentsplitInfo存在等于0的可能。

教程提及,当存在|Di| ≈ |D|时,split_info将非常小(可能等于0),从而导致增益比例异常大,改进方法是计算每个属性的信息增益,对于超过平均信息增益的属性再进一步根据增益比例来选取属性。

但是为了方便,也为了避免考虑浮点误差等问题(根本原因是懒),在本次实现中,只是排除除零的错误。

所以在总体上,跟ID3的python实现只是小小修改的区别而已。

此处完整代码,欢迎学习讨论。

发表评论

电子邮件地址不会被公开。