文档介绍：*
现在学****的是第1页，共67页
第9章决策树算法
*
现在学****的是第2页，共67页
本章大纲：
决策树算法原理
常用决策树算法
决策树剪枝
由决策树提取分类规则
应用实例分析
*
现在学****的是第3页
（）
*
现在学****的是第15页，共67页
ID3算法
上式即为著名的香农信息量公式。注意到式中的对数以2为底，当n=2时且时，熵=1比特。由此可见，一个等概率的二选一事件具有1比特的不确定性。所以，可以把一个等概率的二选一事件所具有信息量定为信息量的单位。任何一个事件能够分解成n个可能的二选一事件，它的信息量就是n比特。
*
现在学****的是第16页，共67页
ID3算法
Quinlan的首创性工作主要是在决策树的学****算法中第一次引入了信息论中的互信息（称之为信息增益），以之作为属性选择的标准，并且将建树的方法嵌入在其中，其核心是在决策树的各级节点上选择属性，用信息增益作为属性选择标准
*
现在学****的是第17页，共67页
ID3算法
下面给出的是ID3算法中将香农的信息熵定义应用到决策树构造中，进而给出的信息增益的定义。
设训练数据集D=
, 是n维有穷向量空间，其中
是有穷离散符号集，D中的每个元素
，叫做例子，其中
设PD和ND是D的两个子集，分别叫做正例集和反例集。
*
现在学****的是第18页，共67页
ID3算法
假设训练数据集D中的正例集PD和反例集ND的大小分别为p和n，则ID3基于下面两个假设给出该决策树算法中信息增益的定义，因为信息是用二进制编码的，所以在下面的公式定义中都用以2为底的对数。（1）在训练数据集D上的一棵正确决策树对任意例子的分类概率同D中正反例的概率一致；（2）一棵决策树能对一个例子做出正确类别判断所需的信息量如下公式所示：
*
现在学****的是第19页，共67页
ID3算法
如果以属性A作为决策树的根，A具有v个值，它将A分为v个子集，假设中含有p个正例和n个反例，那么子集所需的信息期望是，那么，以属性A为根所需的信息期望如下公式所示：
因此，以A为根的信息增益如下公式所示：
*
现在学****的是第20页，共67页
ID3算法
上面给出的ID3中的信息论的相关定义主要是在两类分类问题的前提下，下面给出将其扩展到多类后的相关定义描述。
设训练数据集D一共有m类样例，每类样例数为：。同样以属性A作为决策树的根，具有v个值，它将D分为v个子集，假设子集中任意元组属于类C的概率用表示，并用估计。那么，该子集的信息量定义如下所示：
那么以A为根分类后所需的信息期望如下面公式所示：
*
现在学****的是第21页，共67页

（1）分裂
（2）连续数据
（3）缺失数据
（4）规则
*
现在学****的是第22页，共67页

ID系列的算法为什么会产生归纳偏置呢？
归纳偏置是一系列前提，这些前提与训练数据一起演绎论证未来实例分类。如果给定一个训练数据集，那么通常有很多决策树与这些样例一致。所以，要描述ID系列算法的归纳偏置，应找到它从所有一致假设中选择一个的根据。
*
现在学****的是第23页，共67页

ID系列的搜索策略为：（1）优先选择较短的树而不是较长的；（2）选择那些信息增益高的属性离根节点较近的树。
结论：ID系列算法的归纳偏置是因为它在选的时候较短的树比较长的树优先所产生的，也就是那些信息增益高的属性更靠近的根节点将会有优先生成树的特权。
*
现在学****的是第24页，共67页

为了避免这个偏置，弥补ID系列算法的不足就要舍弃信息增益这个度量而选择别的决策属性作为度量标准。Quinlan在他1986年中的论文中提出了一种可以使用的度量标准：增益比率。
增益比率通过加入一个被称为分裂信息（split informatio