当前位置:   article > 正文

决策树之ID3、C4.5、C5.0_id3算法c4.5c5.0

id3算法c4.5c5.0

罗斯.昆兰(Ross Quinlan


2011年获得了数据挖掘领域最高荣誉奖KDD创新奖,昆兰发明了著名的决策树学习算法ID3、C4.5,其个人主页公布了C4.5的C代码。

—————————————————————————————————————————————————————————————————————————————

决策树之ID3,说一个例子,就会明白,拿 Tom M .mitchen 的《Machine Learing》第三章中的例子。


我们先解释一下这张表,表中有14条实例数据,就是我们的训练数据,其中 Outlook,Temperature,Humidity ,Wind 称作条件属性PlayTennis 称作是决策属性(标签)

每一个属性都有各自的值记做:Value(Outlook)={Sunny,OverCast,Rain},Value(Temperature)={Hot,Mild,Cool},Value(Humidity)={High,Normal},Value(Wind)={Strong,Weak},Value(PlayTennis)={NO,Yes}。

第一个重要的概念:Entropy。

我们数一下  决策属性PlayTennis,一共有两个类别:Yes,No。Yes的实例数是 9,No的实例数是 5。计算决策属性的Entropy(熵):

,

计算结果为:0.940286

这里的决策属性S的值只有两个值(Yes,No),当然可以有多个值(s1,s2,s3,...,sk),这些决策属性的值的概率分别为:p1,p2,p3,...,pk所以决策属性的Entroy的计算公式:



第二个重要的概念:information gain(信息增益)

我们只Outlook条件属性举例,其他的属性一样:

Value(Outlook)={Sunny,OverCast,Rain}:

Outlook是sunny的实例数为5(其中Yes的个数为2,No的个数为3),占总的实例数为5/14,那么针对sunny的Entropy,


计算结果为:0.97095

Outlook是OverCast的实例数为4(其中Yes的个数为4,No的个数为0),占总的实例数为4/14,那么针对Overcast的Entropy,


计算结果为:0

Outlook是Rain的实例数为5(其中Yes的个数为3,No的个数为2),占总的实例数为5/14,那么针对Rain的Entropy,


计算结果为:0.97095

那么最后针对Outlook条件属性的information gain为:


计算结果为:0.24675

所以针对某一条件属性的information gain为:

       

那么其他三个条件属性Temperature、Humidity、Wind的信息增益为:




我们看到Outlook的信息增益是最大的,所以作为决策树的一个根节点。即:



然后,从Outlook下面出来三个树枝,最左边的Sunny,我们从Outlook是Sunny的实例数据中,找到信息增益最大的那一个,依次类推。

—————————————————————————————————————————————————————————————————————————————

决策树之C4.5

上面讨论的决策树的ID3算法,属性只能是枚举型的(离散的),当然属性值可以是连续的数值型,但是需要对这些数据进行预处理,变为离散型的,才可以运用ID3算法。

所以Ross Quinlan又提出了C4.5算法,能够处理属性是连续型的。而且,在C4.5算法中,又提出了两个新的概念:

分离信息(Split Information)和信息增益率(Information gain ratio)

首先,给出分离信息的计算方法,数学符号表达式为:

解释为:数据集通过条件属性A的分离信息。上面一个例子,数据集通过Outlook这个条件属性的分离信息,Outlook有三个属性值分别为:Sunny,Overcast,Rain,它们各占5,4,5,所以:


再次,给出信息增益率的公式:

上面这个例子如:数据集S针对Outlook的信息增益率,

分子和分母这两个值都已经求出来,选择信息增益率最大的那个属性,作为节点。

—————————————————————————————————————————————————————————————————————————————

决策树之C5.0

这是决策树C4.5的商用算法,在内存管理等方面,给出了改进。比如在商用软件SPSS中,就有该算法。

___________________________________________________________________________________________________________________________________

注意上述三个算法只能做分类,不能做回归,下一篇博文CART类似于C4.5,但可以做回归。

开源的软件:

java语言中最著名的的Weka,对ID3,C4.5都有实现。



声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/不正经/article/detail/129102
推荐阅读
相关标签
  

闽ICP备14008679号