决策树分类算法
决策树是一种用来表示人们为了做出某个决策而进行的一系列判断过程的树形图。决策树方法的基本思想是：利用训练集数据自动地构造决策树，然后根据这个决策树对任意实例进行判定。
1．决策树的组成
决策树的基本组成部分有：决策节点、分支和叶，树中每个内部节点表示一个属性上的测试，每个叶节点代表一个类。图1就是一棵典型的决策树。
图1 决策树
决策树的每个节点的子节点的个数与决策树所使用的算法有关。例如，CART算法得到的决策树每个节点有两个分支，这种树称为二叉树。允许节点含有多于两个子节点的树称为多叉树。
下面介绍一个具体的构造决策树的过程，该方法
是以信息论原理为基础，利用信息论中信息增益寻找数据库中具有最大信息量的字段，建立决策树的一个节点，然后再根据字段的不同取值建立树的分支，在每个分支中重复建立树的下层节点和分支。 ID3算法的特点就是在对当前例子集中对象进行分类时，利用求最大熵的方法，找出例子集中信息量（熵）最大的对象属性，用该属性实现对节点的划分，从而构成一棵判定树。
首先，假设训练集C 中含有P 类对象的数量为p ，N 类对象的数量为n ，则利用判定树分类训练集中的对象后，任何对象属于类P 的概率为p/(p+n)，属于类N 的概率为n/(p+n)。
当用判定树进行分类时，作为消息源“P ”或“N ”有关的判定树，产生这些消息所需的期望信息为：
n
p n
log n p n n p p log n p p )n ,p (I 22++-++-
= 如果判定树根的属性A 具有m 个值｛A 1, A 2, …, A m ｝，它将训练集C 划分成｛C 1, C 2, …, C m ｝，其中A i 包括C 中属性A 的值为A i 的那些对象。设C i 包括p i 个类P 对象和n i 个类N 对象，子树C i 所需的期望信息是I(p i , n i )。以属性A 作为树根所要求的期望信息可以通过加权平均得到
)n ,p (I n
p n p )A (E i i m
1
i i
i ∑
=++=
(p i +n i )/(p+n)就是第i 个分支的权值，显然，它与训练集C 中属于C i 的对象数量成比例。所以按A 分支的信息增益为：
Gain(A)=I(p, n)-E(A) ID3算法在构造树的过程中，选择增益最大的属性A k 作为根节点。然后，对子树C 1, C 2, …, C m 做同样处理，递归形成判定树。
1假设表1是一个天气情况的气候数据，描述气候的特征属性有四个：outlook 、temperature 、humidity 、windy ，而每个特征属性的可取值为：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 气候训练集
在表1所示的训练集中，总共有14个对象，其中9个正例(P类)，5个反例(N类)。分类要求的信息是
I(p, n)=-(9/14)log(9/14)-(5/14)log(5/14)=0.94bit
下面分别计算四个属性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)=0.97
同理可得：
p2＝4 n2=0 I(p2, n2)=0
p3＝3 n3=2 I(p3, n3)=0.971 则属性A1＝outlook的期望信息要求为：
E(A1)=(5/14) I(p1, n1)+(4/14) I(p2, n2)+(5/14) I(p3, n3) ＝0.694bit
属性outlook的信息增益为：
Gain(outlook)=I(p, n)-E(A1)=0.940-0.694=0.246bit 类似分析可得：
Gain (temperature)=0.029 bit
Gain (humidity) =0.151 bit
Gain (windy) =0.048 bit
①构建判定树的树根和分枝
ID3算法将选择信息增益最大的属性outlook作为判定
树的根节点，在14个例子中对outlook的3个取值进行分枝，3个分枝对应3个子集，分别是：
F1={1，2，8，9，11}，F2={3，7，12，13}，
F3={4，5，6，10，14}
其中F2中的例子全属于P类，因此对应分枝标记为P，其余两个子集既含有正例又含有反例，将递归调用建树算法。
②递归建树算法
分别对F1和F3子集利用ID3算法，在每个子集中对各特征（仍为四个特征）求信息增益。
(a)F1中的outlook全取sunny值，则I(p, n)= E(outlook)，
有Gain(outlook)＝0，在余下三个特征属性中求出
humidity的信息增益最大，以它为该分枝的根结点，
再向下分枝。Humidity取high全为N类，该分枝标
记N，取值normal全为P类，该分枝标记P。
(b)在F3中，对四个特征属性求信息增益，得到windy特
征属性的信息增益最大，则以它为该分枝根结点，再
向下分枝，它取ture时全为N类，该分枝标记为N，
取false时全为P类，该分枝标记P。
这样就得到如图2所示的判定树。
图2 用ID3算法得到的有关气候的判定树
