决策树分类算法
- 格式：doc
- 大小：128.00 KB
- 文档页数：7
决策树分类算法
决策树是一种用来表示人们为了做由某个决策而进行的一系列判断过程的树形图。决策树方法的基本思想是：利用训练集数据自动地构造决策树，然后根据这个决策树对任意实例进行判定。
1.决策树的组成
决策树的基本组成部分有：决策节点、分支和叶,树中每个内部节点表示一个属性上的测试，每个叶节点代表一个类。图1就是一棵典型的决策树。
图1决策树
决策树的每个节点的子节点的个数与决策树所使
用的算法有关。例如，CART算法得到的决策树每个
节点有两个分支，这种树称为二叉树。允许节点含有
多于两个子节点的树称为多叉树。
F面介绍一个具体的构造决策树的过程，该方法是以信息论原理为基础，利用信息论中信息增益寻找数据库中具有最大信息量的字段，建立决策树的一个节点，然后再根据字段的不同取值建立树的分支，在每个分支中重复建立树的下层节点和分支。
ID3算法的特点就是在对当前例子集中对象进行分类时，利用求最大嫡的方法，找由例子集中信息量(嫡)最大的对象属性，用该属性实现对节点的划分，从而构成一棵判定树。
首先，假设训练集C中含有P类对象的数量为p,N类对象的数量为n,则利用判定树分类训练集中的对象后，任何对象属于类P的概率为p/(p+n),属于类N的概率为n/(p+n)。
当用判定树进行分类时，作为消息源“P”或“N”
有关的判定树，产生这些消息所需的期望信息为：
ppnn I(P,n)….lOg2^rGlOg27^
如果判定树根的属性A具有m个值{Ai,A2,,,Am},它将训练集C划分成{C1,C2,,,Cm},其中Aj包括C中属性A的值为Aj的那些对象。设J包括pi个类P对象和内个类N对象，子树Cj所需的期望信息是I(pi,ni)o以属性A作为树根所要求的期望信息可以通过加权平均得到
i-ni E(A)八I(pi,ni)i』pn
(Pi+nJ/(p+n)就是第i个分支的权值，显然，它与训
练集C中属于Ci的对象数量成比例。所以按A分
支的信息增益为：
Gain(A)=I(p,n)-E(A)
ID3算法在构造树的过程中，选择增益最大的属性Ak作为根节点。然后，对子树C1,C2,,,Cm做
同样处理，递归形成判定树。
例1假设表1是一个天气情况的气候数据，描述气候的特征属性有四个：outlook、temperature、
humidity>windy,而每个特征属性的可取值为：outlook={sunny,overcast,rain},temperature={cool,mild,hot},humidity={high,normal},windy={true,false}。
如果某天早晨的天气描述为：
Outlook（天象）
Temperature（温度）
Humidity（湿度）
Windy（风）那么，它属于哪种类型的气候呢？
解：下面介绍用ID3算法如何从表1所给的训练集中:overcast（阴）
:cool
:normal
:false
构造由一棵能对训练集进行正确分类的判定树。
表1气候训练集
No. Attributes
Class
Outlook Temperature Humidity Windy
1 Sunny Hot High False N
2 Sunny Hot High True N
3 Overcast Hot High False P
4 Rain Mild High False P
5 Rain Cool Normal False P
6 Rain Cool Normal True N
7 Overcast Cool Normal True P
8 Sunny Mild High False N
9 Sunny Cool Normal False P
10 Rain Mild Normal False P
11 Sunny Mild Normal True P
12 Overcast Mild High True P
13 Overcast Hot Normal False P
14 Rain Mild High True N
在表1所示的训练集中，总共有14个对象，其中9个
正例(P类)，5个反例(N类)。分类要求的信息是
I(p,n)=-(9/14)log(9/14)-(5/14)log(5/14)=0.94bit =humidity,A4=windy的信息增益，选择信息增益最大的属性作为判定树的树根。
A1=outlook的取值为｛sunny,overcast,rain｝。训练集C中14个对象有5个是sunny,2个是正例P,3个是反例N,即
PI=2n1=3
I(p1,n1)=0.97
同理可得：
p2=4n2=0I(p2,n2)=0
P3=3&=2I(p3,惠)=0.971
则属性AI=outlook的期望信息要求为：
E(AI)=(5/14)I(pI,%)+(4/14)I(p2,兔)+(5/14)I(p3,nJ=0.694bit
属性outlook的信息增益为：
Gain(outlook)=I(p,n)-E(A1)=0.940-0.694=0.246bit类似分析可得：
Gain(temperature)=0.029bit
Gain(humidity)=0.151bit
Gain(windy)=0.048bit
①构建判定树的树根和分枝
ID3算法将选择信息增益最大的属性outlook作为判定 3个分枝对应3个子集，分别是：
F产{1,2,8,9,11},F2={3,7,12,13},F3={4,5,6,10,14}
其中F2中的例子全属于P类，因此对应分枝标记为P,
其余两个子集既含有正例又含有反例，将递归调用建树算法。
②递归建树算法
分别对F#DF3子集利用ID3算法，在每个子集中对各特征(仍为四个特征)求信息增益。
(a)F1中的outlook全取sunny值，贝UI(p,n)=E(outlook),有Gain(outlook)=0,在余下三个特征属性中求生humidity的信息增益最大，以它为该分枝的根结点，再向下分枝。Humidity取high全为N类，该分枝标记N,取值normal全为P类，该分枝标记P。
(b)在F3中，对四个特征属性求信息增益，得到windy特征属性的信息增益最大，则以它为该分枝根结点，再向下分枝，它取ture时全为N类，该分枝标记为N,取false时全为P类，该分枝标记Po
这样就得到如图2所示的判定树。
图2用ID3算法得到的有关气候的判定树
N
