文档介绍：1
决策树算法
2
Input
ID3 Algorithm
Data Mining
Algorithm
Output
Data set
DT
3
决策树是用样本的属性作为结点,用属性的取值作为分支的树结构。
决策树的根结点是所有样本中信息量最大的属性。树的中间结点是该结点为根的子树所包含的样本子集中信息量最大的属性。决策树的叶结点是样本的类别值。
决策树概念
4
决策树是一种知识表示形式,它是对所有样本数据的高度概括。
决策树能准确地识别所有样本的类别,也能有效地识别新样本的类别。
5
ID3方法基本思想
首先找出最有判别力的属性,把样例分成多个子集,每个子集又选择最有判别力的属性进行划分,一直进行到所有子集仅包含同一类型的数据为止。最后得到一棵决策树。
,他将其称为信息增益(information gain),作为属性判别能力的度量,设计了构造决策树的递归算法。
下面通过一个例子,说明ID3算法的基本思想。
6
对于气候分类问题,属性为:
天气(A1) 取值为: 晴,多云,雨
气温(A2) 取值为: 冷,适中,热
湿度(A3) 取值为: 高,正常
风(A4) 取值为: 有风, 无风
一、ID3基本思想
7
每个样例属于不同的类别,此例仅有两个类别,分别为P,N。P类和N类的样例分别称为正例和反例。将一些已知的正例和反例放在一起便得到训练集。
。由ID3算法得出一棵正确分类训练集中每个样例的决策树,见下图。
8
天气
湿度
风
晴
雨
多云
高
正常
有风
无风
P
N
N
P
P
BACK
GO
9
决策树叶子为类别名,即P 或者N。其它结点由样例的属性组成,每个属性的不同取值对应一分枝。
若要对一样例分类,从树根开始进行测试,按属性的取值分枝向下进入下层结点,对该结点进行测试,过程一直进行到叶结点,样例被判为属于该叶结点所标记的类别。
10
现用图来判一个具体例子,
某天早晨气候描述为:
天气:多云
气温:冷
湿度:正常
风: 无风
它属于哪类气候呢?
从图中可判别该样例的类别为P类。