文档介绍：决策树算法
目录
1、决策树算法概述 3
2、决策树表示法 3
3、决策树学****的适用问题 4
4、基本的决策树学****算法 4
哪个属性是最佳的分类属性 5
．用熵度量样例的均一性 5
. 用信息的属性列表。返回一棵能正确 分类给定 Example 的决策树。
•创建树的Root节点
•如果Examples都为正，那么返回label=+的单节点树Root
•如果Examples都为负，那么返回label=-的单节点树Root
•如果Attributes为空，那么返回单节点树Root, label=Examples中最普遍的 Target_attribute 值
•否则开始
• Av Attributes中分类能力最好的属性
・Root的决策属性v——A
•对于 A 的每个可能值 vi
•在 Root 下加一个新的分支对应测试 A= vi
•令Examples vi为Examples中满足A属性值为vi的子集
•如果Examples vi为空
在这个新的分支下加一个叶子及节点，节点的 label=Examples 中最普遍的 arget_attribute 值
•否则在这个新的分支下接一个子树ID3
(Examplesvi arget_attribute Attributes-{A})
•结束 V1
•返回
ID3 算法的核心问题是选取在树的每个节点要测试的属性。又希望选择的是最有 助于分类实例的属性。因而如何衡量属性的价值标准就需要有一个统一的规定。 这里我们定义一个统计属性，称为“信息增益”。用来衡量给定的属性区分训练 样例的能力。ID3算法在增长树的每一步使用这个信息增益标准从候选属性中选 择属性。
．用熵度量样例的均一性
信息论中广泛使用的一个度量标准,这里我们可以用来定义信息增益，它就是熵
(entrop),它刻画了任意样例集的纯度(purity)。给定包含关于某个目标概念的 正反样例的样例集S,那么S相对这个布尔函数的熵就可以用一个公式来计算： Entrop(S)=-曲log2p通-p-：' log2 石
其中p通是在S中的正例的比例，PJ是S中反例的比例。此外还有还定义01og0=0。 如果目标属性具有c个不同的值，那么s相对于c个状态(c-wise。的分类熵定义为：
Entrop(S)=乞-p ilog2pi
i=1
其中P］是S中属于类别i的比例。
. 用信息增益度量期望的熵降低
有了熵作为衡量训练样例集合纯度的标准，就可以定义属性分类训练数据的能力 的度量标准。这个标准就是“信息增益"(information gain)。简单的说一个信息 增益就是由于使用这个属性分割样例而导致的期望熵降低。更精确的说，一个属 性
A相对训练样例集合S的信息增益Gain(S,A)被定义为：
| sv |
Gain(S,A)=Entropy(S)- 乙 ——Entropy (sv)
| S |
v ^Values (A)
其中Values(A)是属性A所有可能值的集合。Sv是S中属性A的值为v的子集(也就是， Sv={sw SIA(s)=v})。
信息增益正式ID3算法增长树的每一步中选择最佳属性的度量标准。
为了演示ID3算法的具体操作，我们考虑以下表的训练数据所代表的学****任务。 目标属性Play Tennis对于不同的星期六上午具有yes和no两个值，我们将根 据其他属性来预测这个目标属性值。先考虑这个算法的第一步，创建决策树的最 顶端结点。ID3算法计算每一个候选属性的信息增益，然后选择信息增益最高的 一个。
所有四个属性的信息增益为：
Gain(S,Outlook)= Gain(S,Humidity)= Gain(S,Wind)= Gain(S,Temperature)=
S来自下表的训练样例的集合
目标概念PlayTennis的训练样例
Day
Outlook
Temperature
Humidity
Wind
PlayTennis
D1
Sunny
Hot
High
Weak
No
D2
Sunny
Hot
High
Strong
No
D3
Overcast
Hot
High
Weak
Yes
D4
Rain
Mild
High
Weak
Yes
D5
Rain
Cool
Normal
Weak
Yes
D6
Rain
Cool
Normal
Strong
No
D7
Overcast
Cool
No