小啃机器学习(1)-----ID3和C4.5决策树

时间:2022-05-12 03:02:37

小啃机器学习(1)-----ID3和C4.5决策树

第一部分:简介

ID3和C4.5算法都是被Quinlan提出的,用于分类模型,也被叫做决策树。我们给一组数据,每一行数据都含有相同的结构,包含了一系列的attribute/value对。 其中一个属性代表了记录的类别。决策树的问题是对那些没有类别属性的记录预测出正确的类别。一般,类别属性取值为true或者false,yes或者no,success或者faliure。

举例来看,我们这有一些数据是是否打高尔夫球和天气条件的关系。类别属性是是否打高尔夫。非类别属性具体如下:

ATTRIBUTE   | POSSIBLE VALUES
============+=======================
outlook     | sunny, overcast, rain
------------+-----------------------
temperature | continuous
------------+-----------------------
humidity    | continuous
------------+-----------------------
windy       | true, false
============+=======================

训练数据如下:

OUTLOOK | TEMPERATURE | HUMIDITY | WINDY | PLAY
=====================================================
sunny   |      85     |    85    | false | Don't Play
sunny   |      80     |    90    | true  | Don't Play
overcast|      83     |    78    | false | Play
rain    |      70     |    96    | false | Play
rain    |      68     |    80    | false | Play
rain    |      65     |    70    | true  | Don't Play
overcast|      64     |    65    | true  | Play
sunny   |      72     |    95    | false | Don't Play
sunny   |      69     |    70    | false | Play
rain    |      75     |    80    | false | Play
sunny   |      75     |    70    | true  | Play
overcast|      72     |    90    | true  | Play
overcast|      81     |    75    | false | Play
rain    |      71     |    80    | true  | Don't Play

考虑到5个非类别属性中,有2个是连续值,Temperature and Humidity,ID3算法没有直接处理这样的情况,我们需要C4.5里面来思路来处理这种情况,它是ID3的扩展。

一个决策树最重要的不是它总结了我们本身所知道的,而是我们期望它能对新的case可以预测准确。

ID3背后的基本含义是:

  • 在决策树中,每一个节点对应一个非类别属性,每一条弧线对应那个属性可能的值,每一个叶子代表了类别属性的期望值,通过根节点到叶子节点的路径。
  • 在决策树中,从根节点开始每一个节点必须是最有信息量的节点。
  • 熵是衡量一个节点信息量的方法。

第二部分:ID3的定义

通常,我们给一个类别结果的一个概率分布P = (p1, p2, .., pn),这个分布传达的信息量也被为P的熵,为:

I(P) = -(p1*log(p1) + p2*log(p2) + .. + pn*log(pn))

举例,比如P=(0.5,0.5),那么I(P)=1,如果P=(0.67, 0.33),那么I(P)=0.92,P=(1,0),那么I(P)=0。分布越均匀,熵越大。

我们根据非类别属性X的值进行分割为T1,T2...,Info(X,T) = Sum for i from 1 to n of  ----(|Ti|/|T|) * Info(Ti)。

以上面的是否打高尔夫球为例,以outlook属性进行分割,Info(Outlook,T) = 5/14*I(2/5,3/5) + 4/14*I(4/4,0) + 5/14*I(3/5,2/5) = 0.694。

信息增益为,Gain(X,T) = Info(T) - Info(X,T)。这个信息增益代表的意思是,在有和没有属性X值的上信息量的不同。

在Outlook属性上,Gain(Outlook,T) = Info(T) - Info(Outlook,T) = 0.94 - 0.694 = 0.246。同理,Info(Windy,T) = 0.892 and Gain(Windy,T) = 0.048。

Gain(Outlook,T)>Gain(Windy,T),说明可以带来更大的信息增益。我们用信息增益来对属性值进行rank排序,来作为首先决策的节点。

第三部分:ID3算法

ID3算法用来构建决策树,给你一些非分类的属性C1,C2...Cn,一个分类的属性C;一个训练集T;

function ID3 (R: a set of non-categorical attributes,
C: the categorical attribute,
S: a training set) returns a decision tree;
   begin
If S is empty, return a single node with value Failure;
If S consists of records all with the same value for
   the categorical attribute,
   return a single node with that value;
If R is empty, then return a single node with as value
   the most frequent of the values of the categorical attribute
   that are found in records of S; [note that then there
   will be errors, that is, records that will be improperly
   classified];
Let D be the attribute with largest Gain(D,S)
   among attributes in R;
Let {dj| j=1,2, .., m} be the values of attribute D;
Let {Sj| j=1,2, .., m} be the subsets of S consisting
   respectively of records with value dj for attribute D;
Return a tree with root labeled D and arcs labeled
   d1, d2, .., dm going respectively to the trees

ID3(R-{D}, C, S1), ID3(R-{D}, C, S2), .., ID3(R-{D}, C, Sm);
   end ID3;

在高尔夫的例子中,我们构建了下面的决策树:

			Outlook
/ | \
/ | \
overcast / |sunny \rain
/ | \
Play Humidity Windy
/ | | \
/ | | \
<=75 / >75| true| \false
/ | | \
Play Don'tPlay Don'tPlay Play

 第四部分:使用信息增益率

观念是信息增益会导致偏爱那些包含很多值的属性,举一个极端例子,如果我们有一个属性,它的每一条记录的属性值都不同,那么Info(D,T) = 0,但是G(D,T) = 最大。所以,Quinlan建议我们用信息增益率来代替信息增益。

GainRatio(D,T) = Gain(D,T) / SplitInfo(D,T)。而SplitInfo(D,T)代表属性值D的基础上分类T的信息,SplitInfo(D,T) = I(|T1|/|T|, |T2|/|T|, .., |Tm|/|T|)。以高尔夫为例子,SplitInfo(Outlook,T) = -5/14*log(5/14) - 4/14*log(4/14) - 5/14*log(5/14) = 1.577。那么GainRatio(Outlook,T) = 0.246/1.577 = 0.156。

第五部分:C4.5扩展

C4.5是ID3算法的一个扩展。改进地点有:

1)根据信息增益率来选择属性。用来克服了ID3用信息增益选择属性时偏向选择取值多的属性的不足。

2)在树构造过程中进行剪枝,在构造决策树的时候,那些挂着几个元素的节点,不考虑最好,不然容易导致overfitting。

3)对非离散数据也能处理。

4)能够对不完整数据进行处理。