文档介绍：决策树分类算法
决策树是一种用来表示人们为了做出某个决策而进行的一系列判断过程的树形图。决策树方法的基本思想是：利用训练集数据自动地构造决策树，然后根据这个决策树对任意实例进行判定。
决策树的组成
决策树的基本组成部分有：决策节点、分：outlook={sunny，overcast，rain}，temperature={cool，mild，hot}，humidity={high，normal}，windy={true，false}。
如果某天早晨的天气描述为：
Outlook（天象） ：overcast（阴）
Temperature（温度） ：cool
Humidity（湿度） ：normal
Windy（风） ：false
那么,它属于哪种类型的气候呢？
下面介绍用ID3算法如何从表1所给的训练集中构造出一棵能对训练集进行正确分类的判定树。
表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)=
下面分别计算四个属性A1＝outlook，A2＝temperature，A3＝humidity，A4＝windy的信息增益，选择信息增益最大的属性作为判定树的树根。
A1＝outlook的取值为{sunny，overcast，rain}。训练集C中14个对象有5个是sunny，2个是正例P，3个是反例N，即
p1＝2 n1=3
I(p1, n1)=
同理可得：
p2＝4 n2=0 I(p2, n2)=0
p3＝3 n3=2 I(p3, n3)=
则属性A1＝outlook的期望信息要求为：
E(A1)=(5/14) I(p1, n1)+(4/14) I(p2,