文档介绍：决策树分类算法
决策树是一种用来表示人们为了做出某个决策而 进行的一系列判断过程的树形图。决策树方法的基本 思想是：利用训练集数据自动地构造决策树，然后根 据这个决策树对任意实例进行判定。
决策树的基本组成部分有：决
Gain(A)=I(p, n)-E(A)
ID3算法在构造树的过程中，选择增益最大的属
性Ak作为根节点。然后，对子树Cl, C2,…，Cm做
同样处理，递归形成判定树。
1假设表1是一个天气情况的气候数据，描
述气候的特征属性有四个：outlook> temperature> humidity> windy,而每个特征属性的可取值为： outlook={sunny, overcast, rain）, temperature={cool, mild, hot）, humidity={high, normal）, windy={true, false} o
如果某天早晨的天气描述为:
Outlook （天象）
:overcast （阴）
Temperature （温度）Humidity （湿度）
:cool
: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)=
下面分别计算四个属性Ai = outlook, A2=temperature, A3 =humidity, A4=windy的信息增益，选择信息增益最大的 属性作为判定树的树根。
Ax = outlook 的取值为{sunny, overcast, rain}o 训练集 C中14个对象有5个是sunny, 2个是正例P, 3个是反例 N,即