概要 简介 决策树表示法 决策树学习的适用问题 基本的决策树学习算法 决策树学习中的假想空间搜索 决策树学习的常见问题
简介 决策树方法的起源是概念学习系统CLS，然后发展到ID3方法而为高潮，最后又演化为能处理连续属性的C4.5。有名的决策树方法还有CART和Assistant。 是应用最广的归纳推理算法之一 一种逼近离散值目标函数的方法 对噪声数据有很好的健壮性且能学习析取表达式
决策树的表示法 决策树通过把实例从根节点排列到某个叶子节点来分类实例，叶子节点即为实例所属的分类。树上的每一个节点说明了对实例的某个属性的测试，并且该节点的每一个后继分支对应于该属性的一个可能值
图
表达式
决策树学习的适用问题 实例是由属性-值对表示的 目标函数具有离散的输出值 可能需要析取的描述 训练数据可以包含错误 训练数据可以包含缺少属性值的实例
属性选择 构造好的决策树的关键在于如何选择好的逻辑判断或属性。对于同样一组例子，可以有很多决策树能符合这组例子。人们研究出，一般情况下或具有较大概率地说，树越小则树的预测能力越强。要构造尽可能小的决策树，关键在于选择恰当的逻辑判断或属性。由于构造最小的树是NP-难问题，因此只能采取用启发式策略选择好的逻辑判断或属性。
用熵度量样例的均一性（纯度） 熵的定义 举例
用信息增益度量期望熵最低
举例
ID3算法 创建树的Root结点 如果Examples都为正，那么返回label=+中的单结点Root 如果Examples都为反，那么返回lable=-单结点树Root 如果Attributes为空，那么返回单节点树Root，lable=Examples中最普遍的目标属性值 否则开始 AAttributes中分类能力最好的属性 Root的决策属性A 对于每个可能值 在Root下加一个新的分支对应测试A=vi 令Example-vi为Examples中满足A属性值为vi的子集 如果Examples-vi为空 在这个新分支下加一个叶子结点，节点的lable=Examples中最普遍的 目标属性值 否则在这个新分支下加一个子树ID3(example-vi,target- attribute,attributes-|A| 结束 返回 Root
C4.5 C4.5是对ID3的改进算法 对连续值的处理 对未知特征值的处理 对决策树进行剪枝 规则的派生
决策树学习中的假设空间搜索 假设空间 ID3算法中的假设空间包含所有的决策树 当遍历决策树空间时，ID3仅维护单一的当前假设。
决策树学习的常见问题(1) 避免过度拟合数据 基本的决策树构造算法没有考虑噪声，生成的决策树完全与训练例子拟合。有噪声情况下，完全拟合将导致过分拟合（overfitting），即对训练数据的完全拟合反而不具有很好的预测性能。
解决方法 剪枝是一种克服噪声的技术，同时它也能使树得到简化而变得更容易理解。 向前剪枝（forward pruning） 向后剪枝（backward pruning） 理论上讲，向后剪枝好于向前剪枝，但计算复杂度大。剪枝过程中一般要涉及一些统计参数或阈值，如停机阈值；有人提出了一种和统计参数无关的基于最小描述长（MDL）的有效剪枝法
决策树学习的常见问题（2） 合并连续值属性 属性选择的其他度量标准 信息增益比（gain ratio）、Gini-index、距离度量（distance measure）等。不同的度量有不同的效果，特别是对于多值属性。
决策树学习的常见问题（3） 处理缺少属性值的训练样例 处理不同代价的属性
决策树的优点 可以生成可以理解的规则； 计算量相对来说不是很大； 可以处理连续和离散字段； 决策树可以清晰的显示哪些字段比较重要
不足之处 对连续性的字段比较难预测 当类别太多时，错误可能会增加的比较快 一般的算法分类的时候，只是根据一个属性来分类。 不是全局最优。
Thanks a lot!