PPT《分类》

分类 IRLAB 大纲 自然语言中的重要技术决策树最大熵模型K近邻 自然语言中的分类问题 分类的一般过程 训练集数学模型训练过程测试集评价精确率,宏平均,微平均 本课介绍的几种方法 决策树最大熵模型K近邻 决策树 简介决策树表示法决策树学习的适用问题基本的决策树学习算法决策树学习中的假想空间搜索决策树学习的常见问题 简介 决策树方法的起源是概念学习系统CLS,然后发展到ID3方法而为高潮,最后又演化为能处理连续属性的C4.

5.有名的决策树方法还有CART和Assistant.是应用最广的归纳推理算法之一一种逼近离散值目标函数的方法对噪声数据有很好的健壮性且能学习析取表达式 决策树的表示法 决策树通过把实例从根节点排列到某个叶子节点来分类实例,叶子节点即为实例所属的分类.树上的每一个节点说明了对实例的某个属性的测试,并且该节点的每一个后继分支对应于该属性的一个可能值 图 表达式 决策树学习的适用问题 实例是由属性-值对表示的目标函数具有离散的输出值可能需要析取的描述训练数据可以包含错误训练数据可以包含缺少属性值的实例 属性选择 构造好的决策树的关键在于如何选择好的逻辑判断或属性.对于同样一组例子,可以有很多决策树能符合这组例子.人们研究出,一般情况下或具有较大概率地说,树越小则树的预测能力越强.要构造尽可能小的决策树,关键在于选择恰当的逻辑判断或属性.由于构造最小的树是NP-难问题,因此只能采取用启发式策略选择好的逻辑判断或属性. 用熵度量样例的均一性(纯度) 熵的定义举例 用信息增益度量期望熵最低 举例 ID3算法 创建树的Root结点如果Examples都为正,那么返回label=+中的单结点Root如果Examples都为反,那么返回lable=-单结点树Root如果Attributes为空,那么返回单节点树Root,lable=Examples中最普遍的目标属性值否则开始A?Attributes中分类能力最好的属性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仅维护单一的当前假设.基本的ID3算法在搜索中不进行回溯ID3算法在搜索的每一步都使用当前的所有训练样例 决策树学习的常见问题(1) 避免过度拟合数据基本的决策树构造算法没有考虑噪声,生成的决策树完全与训练例子拟合.有噪声情况下,完全拟合将导致过分拟合(overfitting),即对训练数据的完全拟合反而不具有很好的预测性能. 解决方法 剪枝是一种克服噪声的技术,同时它也能使树得到简化而变得更容易理解.向前剪枝(forward pruning)向后剪枝(backward pruning) 理论上讲,向后剪枝好于向前剪枝,但计算复杂度大.剪枝过程中一般要涉及一些统计参数或阈值,如停机阈值;

有人提出了一种和统计参数无关的基于最小描述长(MDL)的有效剪枝法 决策树学习的常见问题(2) 合并连续值属性属性选择的其他度量标准信息增益比(gain ratio)、Gini-index、距离度量(distance measure)等.不同的度量有不同的效果,特别是对于多值属性. 决策树学习的常见问题(3) 处理缺少属性值的训练样例处理不同代价的属性 决策树的优点 可以生成可以理解的规则;