决策树.ppt

决策树学习 主讲人 高相辉 河北大学机器学习中心 教学内容 教学内容 分类问题 训练样例条件属性 Sky AirTempHumidity 决策属性 EnjoySport 属性取值 对于Sky Suny Rainy 对于EnjoySport Yes No 分类问题示例 Aldo进行水上运动的日子 1 决策树简介 第二章中Find S CandidateElimination算法学习得到一个假设 决策树学习是一种逼近离散值目标函数的方法 在这种方法中学习到的函数被表示为一棵决策树 学习得到的决策树也能在表示为多个IF THEN规则 h4 1 决策树简介 结点 属性 边 属性值 叶子结点 类别 2 决策树表示方法 合取的析取表达式 Outlook SunnyANDHumidity Normal OR Outlook Overcast OR Outlook RainANDWind Weak 2 决策树表示方法 IF THEN规则 IFOutlook SunnyANDHumidity HighTHENPlayTennis No 3 决策树适用的问题 决策树学习最适合具有以下特征的问题 实例是由 属性 值 对表示的 目标函数具有离散的输出值 可能需要析取的描述 训练数据可以包含错误 训练数据可以包含缺少属性值的实例 4 基本的决策树学习算法 主要内容 1 ID3算法 2 熵 Entropy 3 信息增益 InformationGain 4 演示例子 4 1ID3算法 1 ID3 Examples Target Attribute Attributes Examples即训练样例集 Target Attribute是这棵树要预测的目标属性 Attributes是条件属性列表 返回能正确分类给定Examples的决策树 创建树的Root结点IFExamples都为正 Then返回label 的单结点树RootIFExamples都为反 Then返回label 的单结点树RootIFAttributes为空 Then返回单结点树Rootlabel Examples中最普遍的Target attribute值 4 1ID3算法 2 ElseA Attributes中分类Examples能力最好 的属性Root的决策属性 A 对于A的每个可能值vi 在Root下加一个新的分支对应测试A vi令ExamplesVi为Examples中满足A属性值为vi的子集如果 ExamplesVi为空在这个新分支下加一个叶子结点 结点label Examples中最普遍的Target attribute值否则 在这个新分支下加一个子树ID3 ExamplesVi Target attribute Attributes A 结束返回Root 算法终止条件 4 2熵 Entropy ID3算法的核心问题 如何选取属性 Outlook Temperature Humidity Wind 一组样本S对于二元分类的熵为 其中p 和p 为S中的正例 反例所占比例 例子 S中有9个正例 5个负例 该选哪个呢 4 2熵 Entropy 对于多分类问题 假设有c个分类 则熵的推广定义 其中pi为属于分类i的样本在S中所占比例 4 3信息增益 属性的信息增益是按该属性分割后熵的消减期望值 其中Sv是S中属性A值为v的子集 问题 属性的信息增益越大越好 还是越小越好 信息增益是否可以为负值 信息增益什么情况下为零 4 3信息增益 例 按照属性Wind分类14个样例得到的信息增益可以计算如下 4 4ID3算法示例 4 4ID3算法示例 S中共有9个正例 5个负例 Examples D1 D2 D3 D4 D5 D6 D7 D8 D9 D10 D11 D12 D13 D14 Target attribute PlayTennis Yes No Attributes Outlook Temperature Humidity Wind 4 4ID3算法示例 Step1 Gain S Outlook 0 246Gain S Humidity 0 151Gain S Wind 0 048Gain S Temperature 0 029 4 4ID3算法示例 Step2 Gain SSunny Temperature 0 5826Gain SSunny Humidity 0 9710Gain SSunny Wind 0 9710 0 5510 0 4 0 020 4 4ID3算法示例 Step3 Humidity High D1 D2 D8 都为NoHumidity Normal D9 D11 都为YesOutlook Overcast D3 D7 D12 D13 都为Yes 4 4ID3算法示例 Step4 Gain SRain Temperature 0 020Gain SRain Humidity 0 020Gain SRain Wind 0 9710 Wind Strong Weak D6 D14 D4 D5 D10 4 4ID3算法示例 Step5 Wind Strong D6 D14 都为NoWind Weak D4 D5 D10 都为Yes 5 决策树学习中的假设空间搜索 ID3算法中的假设空间包含所有的决策树 它是相对于现有属性的有限离散值函数的一个完整空间 当遍历决策树空间时 ID3仅维护单一的当前假设 基本的ID3算法在搜索中不进行回溯 ID3算法在搜索的每一步使用当前的所有训练样例 以统计为基础决定怎样精化当前的假设 6 决策树学习的归纳偏置 概略地讲 ID3的搜索策略为 a 优先选择较短的树而不是较长的 b 选择那些信息增益高的属性离根结点较近的树 近似的ID3算法归纳偏置 较短的树比较长的优先 ID3归纳偏置的更贴切近似 较短的树比较长的得到优先 那些信息增益高的属性更靠近根结点的树得到优先优先 6 决策树学习的归纳偏置 归纳偏置Theinductivebiasofalearningalgorithmisthesetofassumptionsthatthelearnerusestopredictoutputsgiveninputsthatithasnotencountered 优选偏置preferencebias搜索偏置searchbiasID3的归纳偏置是对某种假设胜过其他假设的一种优选 preference 它对最终可列举的假设没有硬性限制 这种类型的偏置通常被称为优选偏置 6 决策树学习的归纳偏置 限定偏置候选消除算法的偏置是对待考虑假设的一种限定 restriction 这种形式的偏置通常被称为限定偏置 或者叫语言偏置 languagebias 奥坎姆剃刀 优先选择拟合数据的最简单假设 注意 优选偏置是对某种假设胜过其他假设的一种优选 因此得到的假设不一定是最优的 限定偏置是对待考虑假设的一种限定 目标概念可能不在假设空间中 因此可能得不到要学习的概念 6 决策树学习的归纳偏置 补充 两种归纳偏置与两类错误 ApproximationErrorEstimationError 6 决策树学习的归纳偏置 补充 7 决策树学习中的常见问题 主要内容 1 过度拟合与剪枝 2 连续值属性 3 属性选择的其他度量标准 4 缺少属性值的训练样例 5 代价不同的属性 7 1过度拟合与剪枝 定义 给定一个假设空间H 一个假设h H 如果存在其他的假设h H 使得在训练样例上h的错误率比h 小 但在整个实例分布上h 的错误率比h小 那么就说假设h过度拟合 overfit 训练数据 训练集合上的错误 整个分布上的错误 7 1过度拟合与剪枝 7 1过度拟合与剪枝 为什么会产生过度拟合 1 训练样例中含有随机错误或噪声 2 没有噪声时 过度拟合也可能发生 如何避免过度拟合 1 及早停止增长树法 在ID3算法完美分类训练数据之前停止增长树 2 后修剪法 post prune 即允许树过度拟合数据 然后对这个树后修剪 7 1过度拟合与剪枝 用什么样的准则来确定最终正确树的大小 MeasureperformanceovertrainingdataMeasureperformanceoverseparatevalidationdatasetMDL minimizesize tree size misclassifications tree 7 1过度拟合与剪枝 决策树剪枝 错误率降低修剪 Error reducedpruning 规则后修剪 Rulepost pruning 规则后修剪 Rulepost pruning ConverttreetoequivalentsetofrulesPruneeachruleindependentlyofothersSortfinalrulesintodesiredsequenceforuse 7 1过度拟合与剪枝 错误率降低修剪 Error reducedpruning SplitdataintotrainingandvalidationsetCreatetreethatclassifiestrainingsetcorrectlyDountilfurtherpruningisharmful Evaluateimpactonvalidationsetofpruningeachpossiblenode plusthosebelowit Greedilyremovetheonethatmostimprovesvalidationsetaccuracy 7 1过度拟合与剪枝 错误率降低修剪的效果 7 2连续值属性 连续属性的离散化 对于连续值的属性A 算法可动态地创建一个新的布尔属性Ac 如果A c 那么为Ac真 否则为假 问题是如何选取最佳的阈值c 例子 可供选择的阈值 48 60 2 54 80 90 2 85c 54所对应的信息增益大 所以选择Temperture54 7 3属性选择的其他度量标准 信息增益度量存在一个内在偏置 它偏袒具有较多值的属性 增益比率 GainRatio 分裂信息 SplitInformation 衡量属性分裂数据的广度和均匀性 7 4处理缺少属性值的训练样例 在某些情况下 可供使用的数据可能缺少某些属性的值 解决策略 赋给它结点n的训练样例中该属性的最常见值 赋给它结点n的被分类为c x 的训练样例中该属性的最常见值 为A的每个可能值赋与一个概率 7 5代价不同的属性 不同属性的代价不同 可以通过引入一个代价项到属性选择度量 例如 8 总结 决策树学习为概念学习和学习其他离散值的函数提供了一个实用的方法 ID3系列算法使用从根向下增长法推断决策树 为每个要加入树的新决策分支贪婪地选择最好的属性 ID3算法搜索完整的假设空间 所以它避免了仅考虑有限的假设集合的方法的主要问题 目标函数可能不在假设空间中 8 总结 隐含在ID3算法中的归纳偏置包括优先选择较小的树 也就是说 它通过对假设空间的搜索增长树 使树的大小为正好能分类已有的训练样例 过度拟合训练数据是决策树学习中的重要问题 后修剪决策树的方法可以避免决策树学习中的过度拟合 决策树的优点 可以生成可以理解的规则 计算量相对来说不是很大 可以处理连续和离散字段 决策树可以清晰的显示哪些字段比较重要 决策树的不足 对连续性