机器学习算法汇总大全.ppt

2016 11 机器学习 MachineLearning 报告建议内容 基本概念以及数学定义基本性质及其物理意义具体算法应用 详细举例讲解 该算法与其他类似算法的分析比较可能的发展方向附参考文献 2 机器学习 TomM Mitchell 汤姆 米切尔 著 曾华军 张银华等译 机械工业出版社 2003年 参考书 其它参考书 机器学习及其应用 周志华 王钰主编 清华大学出版社 2009 神经网络与机器学习 SimonHaykin著 机械工业出版社 2010 机器学习导论 EthemAlpaydin著 机械工业出版社 2009 MachineLearning AProbabilisticPerspective KevinP Murphy 2012 第1章引言 什么是机器学习 经典定义 计算机程序如何随着经验积累自动提高性能 系统自我改进的过程 或 计算机利用经验改善系统自身性能的行为 米切尔随着该领域的发展 主要做智能数据分析 学习与智能 学习现象语言 文字的认知识别图像 场景 自然物体的认知识别规则 eg下雨天要带雨伞 复杂的推理 判断能力 智能 好人与坏人 好猫与坏猫 什么是机器学习 使得计算机具备和人类一样的学习能力决策推理认知识别 等智能给定数据 样本 实例 和一定的学习规则 从数据中获取知识的能力 机器学习与人工智能 自然智慧的伟大与奥妙举例 婴儿的认知能力 声音 人脸 汽车 重要的二个特点 容错性 推广能力 举一反三 机器智能 希望用机器实现部分智能基于数据的机器学习问题 引自清华张学工教授 根据已知样本估计数据之间的依赖关系 从而对未知或无法测量的数据进行预测和判断关键 推广能力 什么是机器学习 中科院王珏研究员给出的定义 令W是给定世界的有限或无限所有观测对象的集合 由于我们的观测能力有限 我们只能获得这个世界的一个子集 称为样本集 机器学习就是根据这个样本集 推算这个世界W的模型 使它对这个世界 尽可能地 为真 三个重要的理论问题 一致 W与Q有相同的性质 eg i i d划分 设样本定义于d维空间 要寻找在这个空间上的决策分界面泛化 推广能力 对未知样本的判断能力 What sistheLearningProblem Learning ImprovingwithexperienceatsometaskImproveovertaskTWithrespecttoperformancemeasurementPBasedonexperienceEExample 中国象棋任务T 下中国象棋性能目标P 比赛中击败对手 的百分比 训练经验E 和自己进行对弈 或者看棋谱 Ref 机器学习 曾华军等译 Pedro对学习理解 MachineLearning 引用自CMUDr EricXing的LectureNotes 机器学习的研究意义 机器学习的重要性 Science 2001年论文 每个科学领域的科学过程都有它自己的特点 但是 观察 创立假设 根据决定性实验或观察的检验 可理解检验的模型或理论 是各个学科所共有的 对这个抽象的科学过程的每一个环节 机器学习都有相应的发展 我们相信它将导致科学方法中从假设生成 模型构造到决定性实验这些所有环节的合适的 部分的自动化 当前机器学习研究在一些基本论题上取得令人印象深刻的进展 我们预期机器学习研究在今后若干年中将有稳定的进展 在稍早前 2000年 Science 还发表了另外3篇ML方面的论文 TheManifoldWayofPerceptron Aglobalgeometricframeworkfornonlineardimensionalityreduction Nonlineardimensionalityreductionbylocally Mjolsness DDeCoste MachineLearningforScience StateoftheArtandFutureProspects Science 2001 2051 2055 受到令人惊讶的重视 机器学习的重要性 摘自南京大学周志华教授 生物信息学 计算金融学 分子生物学 行星地质学 工业过程控制 机器人 遥感信息处理 信息安全 机器学习 多学科交叉 机器学习也是一个多学科交叉的产物 它吸取了人工智能 概率统计 神经生物学 认知科学 信息论 控制论 计算复杂性理论 哲学等学科的成果 实践证明 机器学习在很多应用领域发挥了重要的实用价值 特别是在数据挖掘 语音识别 图像处理 机器人 车辆自动驾驶 生物信息学 信息安全 遥感信息处理 计算金融学 工业过程控制 重要性 例子 网络安全 入侵检测 是否是入侵 是何种入侵 如何检测 历史数据 以往的正常访问模式及其表现 以往的入侵模式及其表现 对当前访问模式分类 这是一个典型的预测型机器学习问题常用技术 神经网络决策树支持向量机k近邻序列分析聚类 搜索引擎 摘自南京大学周志华教授 重要性 例子 生物信息学 常用技术 神经网络支持向量机隐马尔可夫模型k近邻决策树序列分析聚类 重要性 例子 数据驱动控制 相关学科对ML的影响 人工智能 学习的概念符号表示Bayes方法统计学 统计学习理论 SLT 计算复杂性理论控制论信息论 最小描述长度哲学 Occam sRazor原则 没有免费午餐 心理学和神经生物学 NeuralNetworks 神经网络 机器学习目前主要的一些研究领域 符号机器学习Eg 决策树 ID3 计算学习理论 统计学习理论 PAC SVM监督学习 非监督学习 半监督学习集群机器学习EnsembleLearning Boosting流行 Manifold 学习强化学习Ranking学习聚类学习 MachineLearningTopicsfromWiki http en wikipedia org wiki Machine Learning 机器学习简要发展历史回顾 ML的发展历史 1 1950s 神经科学的理论基础James关于神经元是相互连接的发现McCullon Pitts的神经元模型Hebb学习律 相互连接强弱度的变换规则 1960s 感知器 Perceptron 时代1957年Rosenblatt首次提出 ML的发展历史 2 1969年 Perceptron 出版 提出著名的XOR问题1970s 符号主义 逻辑推理1980s MLP BP算法成功解决XOR问题 从此进入神经网络时代 连接主义 1960s 1970s 统计学习理论创立VC维的基本概念结构风险最小化原则概率空间的大数定律 ML的发展历史 3 1990s 统计学习理论的发展及完善典型代表 SVM Vapnik Bell实验室 结构风险最小化最小描述长度原则小样本问题核函数 核空间变化PAC理论下的弱可学习理论的建立支持向量机 ML的发展历史 4 2000s 各种机器学习理论及算法得以充分发展符号机器学习计算机器学习 统计学习理论 典型例子 SVM 集群机器学习 典型代表 Boosting 强化机器学习流行机器学习监督学习 非监督学习半监督学习 未来发展趋势 机器实际上是一个应用驱动的学科 其根本的驱动力是 更多 更好地解决实际问题 由于近20年的飞速发展 机器学习已经具备了一定的解决实际问题的能力 似乎逐渐开始成为一种基础性 透明化的 支持技术 服务技术 基础性 在众多的学科领域都得以应用 无所不在 透明化 用户看不见机器学习 看见的是防火墙 生物信息 搜索引擎 无所不在 机器更好用了 正如CALO的一些描述 youwon tleavehomewithoutit embodiedasasoftwareenvironmentthattranscendsworkstations PDA s cellphones 讨论议题 机器学习的主要策略与基本结构机器学习的主要策略机器学习系统的基本结构 机器学习系统的基本结构 我们以西蒙的学习定义做为出发点 建立起下图1 1所示的简单的学习模型 然后通过对这个简单模型的讨论 总结出设计学习系统应当注意的某些总的原则 图1 1学习系统的基本结构 学习问题的标准描述 定义如果一个计算机针对某类任务T 用P来衡量性能 根据经验E来自我完善 那么我们称这个计算机程序在从经验E中学习 针对某类任务T 它的性能用P来衡量 西洋跳棋学习问题的解释E 和自己下棋T 参与比赛P 比赛成绩 或赢棋能力 击败对手的百分比 手写识别学习问题机器人驾驶学习问题 学习问题的标准描述 2 定义太宽泛甚至包括了以非常直接的方式通过经验自我提高的计算机程序实际的机器学习问题往往比较复杂定义一类问题探索解决这类问题的方法理解学习问题的基本结构和过程 有监督学习 有监督的学习方法在样本标签已知的情况下 可以统计出各类训练样本不同的描述量 如其概率分布 或在特征空间分布的区域等 利用这些参数进行分类器设计 称为有监督的学习方法 无监督学习 无监督学习然而在实际应用中 不少情况下无法预先知道样本的标签 也就是说没有训练样本因而只能从原先没有样本标签的样本集开始进行分类器设计 这就是通常说的无监督学习方法 对一个具体问题来说有监督与无监督的作法是不相同的 有监督学习 x1 x2 无监督学习 x1 x2 机器学习的问题 存在什么样的算法能从特定的训练数据学习一般的目标函数呢 如果提供了充足的训练数据 什么样的条件下 会使特定的算法收敛到期望的函数 哪个算法对哪些问题和表示的性能最好 多少训练数据是充足的 怎样找到学习到假设的置信度与训练数据的数量及提供给学习器的假设空间特性之间的一般关系 学习器拥有的先验知识是怎样引导从样例进行泛化的过程的 当先验知识仅仅是近似正确时 它们会有帮助吗 关于选择有效的后验训练经验 什么样的策略最好 这个策略的选择会如何影响学习问题的复杂性 怎样把学习任务简化为一个或多个函数逼近问题 换一种方式 系统该试图学习哪些函数 这个过程本身能自动完成吗 学习器怎样自动地改变表示法来提高表示和学习目标函数的能力 课程内容简介 第2章 基于符号和逻辑表示的概念学习 简介 第3章 决策树第4章 回归模型与神经网络第5章 评估假设第6章 贝叶斯理论 混合模型与EM算法 第7章 基于实例的学习 核函数与径向基函数网络 第8章 马尔科夫与隐马尔可夫模型第9章 支持向量机 线性判别与SVM 第10章 增强学习 参考期刊与会议 相关杂志MachineLearningNeuralComputationJournaloftheAmericanStatisticalAssociationIEEEtransactionsonPatternAnalysis MachineIntelligence国际会议国际机器学习会议ICML神经信息处理系统会议NIPS计算学习理论会议CCLT国际遗传算法会议ICGA 参考学术期刊及国际会议 一些网络资源 1 http machine AAAIMachineLearningTopics www aaai org AITopics html machine html SupportVectorMachines http www support vector machines org index html 一些网络资源 2 http www cs cmu edu tom 10701 sp11 lectures shtmlMachineLearning Spring2011 CMUTomMitchellVideoLecture SlidesMachineLearningResources 一些网络资源 3 Weka DataMining ML softwareinJava http www cs waikato ac nz ml weka LibSVM ALibraryforSupportVectorMachines www csie ntu edu tw cjlin libsvmMLC 一些网络资源 4 KernalMachines http www kernel machines org http mloss org software MachineLearningOpenSourceSoftwarehttp www3 ntu edu sg home aswduch ai ml html数据挖掘研究院 概念学习给定某一类别的若干正例和反例 从中获得该类别的一般定义 搜索的观点在预定义的假设空间中搜索假设 使其与训练样例有最佳的拟合 利用假设空间的偏序结构算法收敛到正确假设的条件 归纳学习的本质 从训练数据中泛化的理由 第2章概念学习和一般到特殊序 简介 许多机器学习涉及到从特殊训练样例中得到一般概念 概念 可被看作一个对象或事件集合 它是从更大的集合中选取的子集 或在这个较大集合中定义的布尔函数 概念学习问题的定义给定一个样例集合以及每个样例是否属于某个概念的标注 怎样推断出该概念的一般定义 又称从样例中逼近布尔函数 概念学习是指从有关某个布尔函数的输入输出训练样例中推断出该布尔函数 概念学习任务 一个例子目标概念Aldo进行水上运动的日子 表示为布尔函数EnjoySport任务目的基于某天的各属性 预测EnjoySport的值给定一个样例集D每个样例表示为6个属性的集合 概念学习任务 2 Yes Change Cool Strong High Warm Sunny 4 No Change Warm Strong High Cold Rainy 3 Yes Same Warm Strong High Warm Sunny 2 Yes Same Warm Strong Normal Warm Sunny 1 EnjoySport Forecast Water Wind Humidity AirTemp Sky Example 表2 1目标概念EnjoySport的训练样例 概念学习任务 3 表示假设的形式 目标函数的表示 一个简单的形式 实例的各属性约束的合取式令每个假设为6个约束 或变量 的向量 每个约束对应一个属性可取值范围 为 任意本属性可接受的值明确指定的属性值 不接受任何值假设的例子 所有的样例都是正例 所有的样例都是反例 概念学习任务 4 形式化描述 已知实例集X每个实例x由6个属性描述 每个属性的取值范围已确定假设集H每个假设h描述为6个属性的取值约束的合取目标概念c一个布尔函数 变量为实例训练样例集D目标函数 或目标概念 的正例和反例求解H中的一假设h 使对于X中任意x h x c x 术语定义 实例x实例集X概念目标概念c训练样例x训练样例集D正例 目标概念成员反例 非目标概念成员假设h假设集H机器学习的目标就是寻找一个假设h 使得对所有的h 都有h x c x 归纳学习假设 什么是归纳学习 从特殊的样例得到普遍的规律 从特殊到一般 归纳只能保证输出的假设能与训练样例相拟合归纳假设的一个基本假定对于未见实例最好的假设就是与训练数据最佳拟合的假设归纳学习假设任一假设如果在足够大的训练样例集中很好地逼近目标函数 它也能在未见实例中很好地逼近目标函数 作为搜索的概念学习 概念学习可以看作一个搜索的过程搜索范围 假设的表示所隐含定义的整个空间搜索目标 能够最好地拟合训练样例的假设当假设的表示形式选定后 那么就隐含地为学习算法确定了所有假设的空间例子EnjoySport的假设空间 如果属性Sky有3种可能的值 而AirTemp Humidity Wind Water和Forecast都只有两种可能值 实例空间X 包含3 2 2 2 2 2 96种不同的实例假设空间H包含5 4 4 4 4 4 5120种语法不同的假设由于 包含有 符号的假设将每个实例都分类为反例 因此 语义不同的假设只有1 4 3 3 3 3 3 973个 假设的一般到特殊序 假设的一般到特殊序关系考虑下面两个假设h1 h2 任何被h1划分为正例的实例都会被h2划分为正例 因此h2比h1更一般 利用这个关系 无需列举所有假设 就能在无限的假设空间中进行彻底的搜索 假设的一般到特殊序 2 关系 更一般 的精确定义任给实例x和假设h 说x满足h 当且仅当h x 1令hj和hk是在X上定义的布尔函数 称hj比hk更一般 当且仅当 x X hk x 1 hj x 1 记为hjmore general than or equal tohk 或hj ghk 假设的一般到特殊序 3 更一般 的严格情形hj ghk 当且仅当 hj ghk hk ghj 更特殊 关系的定义hj ghk 当且仅当 hk ghj以EnjoySport为例说明上面的定义偏序的特点 区别于全序 全序上的搜索可以是二分法 偏序的搜索比无序简单 比全序复杂 这个偏序关系的定义与目标概念无关 h1 h2 h3 x1 x2 Find S 寻找极大特殊假设 使用more general than偏序的搜索算法从H中最特殊假设开始 然后在假设覆盖正例失败时将其一般化Find S算法将h初始化为H中最特殊假设对每个正例x对h的每个属性约束ai如果x满足ai那么不做任何处理否则将h中ai替换为x满足的另一个更一般约束输出假设h Find S 寻找极大特殊假设 2 Find S算法在例子EnjoySport上的应用h h h 遇到反例 h不变 因为h已经能够正确地识别反例 h Find S 寻找极大特殊假设 3 Find S算法演示了一种利用more general than偏序来搜索假设空间的方法 沿着偏序链 从较特殊的假设逐渐转移到较一般的假设 因此 每一步得到的假设都是在那一点上与训练样例一致的最特殊的假设 Find S的重要特点 对以属性约束的合取式描述的假设空间H 保证输出为H中与正例一致的最特殊的假设 存在的问题是否收敛到了正确的目标概念 为什么要用最特殊的假设 训练样例是否相互一致 如果有多个极大特殊假设怎么办 变型空间和候选消除算法 候选消除算法概说概念学习的另一种方法 候选消除算法 candidate elimination Find S算法的不足 输出的假设只是H中能够拟合训练样例的多个假设中的一个候选消除算法输出与训练样例一致的所有假设的集合候选消除算法在描述这一集合时不需要明确列举所有成员利用more general than偏序结构 可以维护一个一致假设集合的简洁表示候选消除算法的应用 化学质谱分析 启发式搜索的控制规则候选消除算法的缺点 容错性能差 变型空间和候选消除算法 2 一致 的定义一个假设h与训练样例集合D一致 当且仅当对D中每一个样例都有h x c x 即Consistent h D D h x c x 一致 与 满足 的关系变型空间 VersionSpace 与训练样例一致的所有假设组成的集合表示了目标概念的所有合理的变型关于H和D的变型空间 记为VSH D 是H中与训练样例D一致的所有假设构成的子集VSH D h H Consistent h D 变型空间和候选消除算法 3 列表后消除算法表示变型空间的一种方法是列出其所有成员变型空间 包含H中所有假设的列表对每个训练样例 从变型空间中移除所有h x c x 的假设输出VersionSpace中的假设列表优点保证得到所有与训练数据一致的假设缺点非常繁琐地列出H中的所有假设 大多数实际的假设空间无法做到 变型空间和候选消除算法 4 变型空间的更简洁表示变型空间被表示为它的极大一般和极大特殊的成员这些成员形成了一般和特殊边界的集合 这些边界在整个偏序结构中划分出变型空间以EnjoySport为例 变型空间和候选消除算法 5 形式化定义极大一般极大特殊关于假设空间H和训练数据D的一般边界G 是在H中与D相一致的极大一般成员的集合关于假设空间H和训练数据D的特殊边界S 是在H中与D相一致的极大特殊成员的集合 变型空间和候选消除算法 6 变型空间表示定理 令X为一任意的实例集合 H为X上定义的布尔假设的集合 令c X 0 1 为X上定义的任一目标概念 并令D为任一训练样例集合 对所有的X H c D以及良好定义的S和G VSH D h H s S g G g gh gs 证明 只需证明 1 每一个满足上式右边的h都在VSH D中 2 VSH D的每个成员都满足都满足等式右边 变型空间和候选消除算法 7 候选消除算法初始化G和S如果d是一个正例从G中移去所有与d不一致的假设对S中每个与d不一致的假设s从S中移去s把s的所有的极小泛化式h加入到S中 其中h满足h与d一致 而且G的某个成员比h更一般从S中移去所有这样的假设 它比S中另一个假设更一般如果d是一个反例从S中移去所有与d不一致的假设对G中每个与d不一致的假设g从G中移去g把g的所有的极小特殊化式h加入到G中 其中h满足h与d一致 而且S的某个成员比h更特殊从G中移去所有这样的假设 它比G中另一个假设更特殊 变型空间和候选消除算法 8 算法举例 S1 S2 G3 S2S3 S4 G4 G0G1 G0G1G2 图2 7最终变型空间 变型空间和候选消除的说明 候选消除算法收敛到正确的假设训练样例中没有错误H中确实包含描述目标概念的正确假设如果样例中存在错误如果给定足够的训练数据 我们会发现S和G边界收敛得到一个空的变型空间如果目标概念不能由假设表示方式所描述比如是约束的析取 变型空间和候选消除 2 下一步需要什么样的训练样例一般来说 概念学习的最优查询策略 是产生实例以满足当前变型空间中大约半数的假设 这样 变型空间的大小可以在遇到每个新样例时减半 正确的目标概念就可在只用log2 VS 次实验后得到 变型空间和候选消除 3 怎样使用不完全学习概念虽然图2 7的变型空间中仍包含多个假设 即目标概念还未学习到 但是仍然有可能对新样例进行一定可信度的分类 待分类的新实例 概念的应用 概念的应用 判断是否是正例判断是否满足S中的每个假设判断是否是反例判断是否不满足G中的每个假设 归纳偏置 有关候选消除算法的几个问题如果目标概念不在假设空间中怎么办 是否可设计一个包含所有假设的空间来解决这一困难 假设空间的大小对于算法推广到未见实例的能力有什么影响 假设空间的大小对所需训练样例的数量有什么影响 归纳偏置 2 一个有偏的假设空间在EnjoySport这个例子中 假设空间限制为只包含属性值的合取 有偏 这一限制 导致假设空间不能够表示最简单的析取形式的目标概念 归纳偏置 3 无偏的学习器为了保证目标概念在假设空间中 需要提供一个假设空间 它能表达所有的可教授概念 换言之 它能表达实例集X的所有子集 问题 为什么2 3节中合取假设空间只能表示973个假设 归纳偏置 4 EnjoySport的无偏形式带来的问题 概念学习算法无法从训练样例中泛化 要想获得单个目标概念 就必须提供X中所有实例作为训练样例使用2 6 3节讨论的部分学习的无效 归纳偏置 5 无偏学习的无用性归纳学习的一个基本属性 学习器如果不对目标概念的形式做预先的假定 它从根本上无法对未见实例进行分类归纳学习需要的预先假定 称为归纳偏置 归纳偏置 6 归纳偏置的精确定义 Dc xi L xi Dc 需要在Dc xi上附加怎样的前提 以使L xi Dc 能够演绎派生 L的归纳偏置定义为前提集合B 使所有的新实例满足 B Dc xi L xi Dc 考虑对于实例集合X的概念学习算法L 令c为X上定义的任一概念 并令Dc为c的任意训练样例集合 L xi Dc 表示经过Dc训练后L赋予实例xi的分类 L的归纳偏置是最小断言集合B 它使任意目标概念c和相应的训练样例Dc满足 xi X B Dc xi L xi Dc 归纳偏置 6 候选消除算法的归纳偏置 c H InductiveSystemsandEquivalentDeductiveSystems 归纳与演绎 归纳偏置 7 3个有偏程度不同的归纳学习算法机械式候选消除算法Find S一种算法的有偏性越强 它的归纳能力越强 可以分类更多的未见实例 某些归纳偏置隐含在学习器中 有些表示为断言集合 可由学习器操作 小结 主要内容概念学习可看作搜索预定义潜在假设空间的过程 假设的一般到特殊偏序结构可以定义在任何概念学习问题中 这种结构便于假设空间的搜索 Find S算法使用一般到特殊序 在偏序结构的一个分支上执行一般到特殊搜索 寻找一个与样例一致的最特殊假设 候选消除算法利用一般到特殊序 通过渐近地计算极大特殊假设集合和极大一般假设集合发现变型空间 候选消除算法缺少健壮性 后面会描述一些学习算法 它们能够处理有噪声的数据和目标概念无法在假设空间中表示的情况归纳学习算法隐含了归纳偏置 候选消除算法的偏置是 目标概念可以在假设空间中找到 输出的假设和对新实例的分类可由归纳偏置和训练样例演绎推出 思考题 2 1 解释为什么EnjoySport学习任务的假设空间的大小为973 如果增加一属性WaterCurrent 可取值Light Moderate和Strong 那么可能的实例数和可能的假设数将会增加多少 推广到一般 增加一新属性A 有k种取值 实例数和假设数将会增加多少 思考题 2 2在候选消除算法中 如果训练样例按EnjoySport例子中的逆序出现 请分步给出S和G边界集合 尝试对训练样例排序 以使EnjoySport例子中的所有S和G集合的中间结果的大小之和为最小 Yes Change Cool Strong High Warm Sunny 4 No Change Warm Strong High Cold Rainy 3 Yes Same Warm Strong High Warm Sunny 2 Yes Same Warm Strong Normal Warm Sunny 1 EnjoySport Forecast Water Wind Humidity AirTemp Sky Example 思考题 2 3实现Find S算法和候选消除算法 验证它是否可成功地产生EnjoySport例子中各步骤结果 第3章决策树学习 Decision TreeAlgorithm 共有145人参加了ICDM2006Panel 会议的专题讨论 并对18种候选算法进行投票 选出了机器学习10大算法 ICDM2006会议的算法投票结果 概论 决策树学习是应用最广的归纳推理算法之一是一种逼近离散值函数的方法很好的健壮性能够学习析取表达式ID3 Assistant C4 5搜索一个完整表示的假设空间归纳偏置是优先选择较小的树决策树表示了多个if then规则 提纲 决策树定义适用问题特征基本ID3算法决策树学习的归纳偏置训练数据的过度拟合 决策树基本概念 关于分类问题 分类 Classification 任务就是通过学习获得一个目标函数 TargetFunction f 将每个属性集x映射到一个预先定义好的类标号y 分类任务的输入数据是记录的集合 每条记录也称为实例或者样例 用元组 X y 表示 其中 X是属性集合 y是一个特殊的属性 指出样例的类标号 也称为分类属性或者目标属性 决策树基本概念 关于分类问题 X y 分类与回归 分类目标属性y是离散的 回归目标属性y是连续的 决策树基本概念 解决分类问题的一般方法 通过以上对分类问题一般方法的描述 可以看出分类问题一般包括两个步骤 1 模型构建 归纳 通过对训练集合的归纳 建立分类模型 2 预测应用 推论 根据建立的分类模型 对测试集合进行测试 决策树基本概念 解决分类问题的一般方法 学习算法 学习模型 模型 应用模型 训练集 类标号已知 检验集 类标号未知 归纳 推论 决策树表示法 内部节点 包括根节点 指定了对实例的某个属性的测试节点的每个后继分支对应于该属性的一个可能值叶子节点即为实例所属的分类决策树代表实例属性值约束的合取的析取式 决策树学习的适用问题 适用问题的特征实例由 属性 值 对表示目标函数具有离散的输出值可能需要析取的描述训练数据可以包含错误训练数据可以包含缺少属性值的实例问题举例医学中的应用 如根据疾病分类患者 疾病分析与预测 根据起因分类设备故障 故障诊断 根据拖欠支付的可能性分类贷款申请分类问题核心任务是把样例分类到各可能的离散值对应的类别 基本的决策树学习算法ID3 大多数决策树学习算法是一种核心算法的变体采用自顶向下的贪婪搜索遍历可能的决策树空间ID3是这种算法的代表该方法使用信息增益度选择测试属性 ID3算法通过自顶向下构造决策树来进行学习 构造过程 ID3算法的核心问题是选取在树的每个节点要测试的属性 选择根节点 使用统计测试确定每一个实例属性单独分类训练样例的能力 分类能力最好的属性被选作树的根节点为根节点属性的每个可能值产生一个分支 并把训练样例排列到适当的分支重复上面的过程 用每个分支节点关联的训练样例来选取在该点被测试的最佳属性 直到满足以下两个条件中的任一个 1 所有的属性已经被这条路径包括 2 与这个节点关联的所有训练样例具有相同的目标属性值 表3 1用于学习布尔函数的ID3算法 ID3 Examples Target attribute Attributes 创建树的root节点如果Examples都为正 返回label 的单节点树root如果Examples都为反 返回label 的单节点树root如果Attributes为空 那么返回单节点root label Examples中最普遍的Target attribute值否则开始A 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 最佳分类属性 信息增益 InformationGain 用来衡量给定的属性区分训练样例的能力ID3算法在增长树的每一步使用信息增益从候选属性中选择属性用熵度量样例的均一性给定包含关于某个目标概念的正反样例的样例集S 那么S相对这个布尔型分类的熵为信息论中对熵的一种解释 熵确定了要编码集合S中任意成员的分类所需要的最少二进制位数更一般地 如果目标属性具有c个不同的值 那么S相对于c个状态的分类的熵定义为Entropy S S的所有成员属于同一类 Entropy S 0 S的正反样例数量相等 Entropy S 1 S的正反样例数量不等 熵介于0 1之间 抛一枚均匀硬币的信息熵是多少 解 出现正面与反面的概率均为0 5 信息熵是 用信息增益度量期望的熵降低属性的信息增益 由于使用这个属性分割样例而导致的期望熵降低一个属性A相对样例集合S的信息增益Gain S A 被定义为 Values A 是属性A所有可能值的集合 Sv是S中属性A的值为v的子集Gain S A 是在知道属性A的值后可以节省的二进制位数 计算属性的信息增益 表3 2目标概念PlayTennis的训练样例 计算属性的信息增益 110 考虑表3 2的训练数据所代表的学习任务 创建决策树的根节点 计算每一个候选属性的信息增益 然后选择信息增益最高的一个 Gain S Outlook 0 246Gain S Humidity 0 151Gain S Wind 0 048Gain S Temperature 0 029根据信息增益标准 属性Outlook被选作根节点的决策属性 并为它的每一个可能值 Sunny Overcast和Rainy 在根节点下创建分支 得到部分决策树显示在图3 4中 对非终端的后继节点再重复前面的过程以选择一个新的属性来分割训练样例 这一次仅使用与这个节点关联的训练样例 直到满足结束条件 ID3算法示例 表3 2目标概念PlayTennis的训练样例 112 ID3算法步骤1 Gain S Outlook 0 246Gain S Humidity 0 151Gain S Wind 0 048Gain S Temperature 0 029 Outlook Yes Sunny Overcast Rain D1 2 8 9 11 D3 7 12 13 D4 5 6 11 14 D1 14 9 5 2 3 4 0 3 2 什么属性 ID3算法第一步后形成的部分决策树 114 ID3算法步骤2 Gain SSunny Humidity 0 970Gain SSunny Temperature 0 570Gain SSunny Wind 0 019 Gain SRain Humidity 0 019Gain SRain Temperature 0 019Gain SRain Wind 0 970 115 决策树学习中的假设空间搜索 ID3算法搜索的假设空间就是可能的决策树的集合 ID3以爬山算法遍历这个假设空间 引导这种爬山搜索的评估函数是信息增益度量 观察ID3的搜索空间和搜索策略 认识到这个算法的优势和不足 假设空间包含所有的决策树 它是关于现有属性的有限离散值函数的一个完整空间维护单一的当前假设 不同于上章变型空间候选消除算法 不能判断有多少个其他的决策树也与现有的训练数据一致不进行回溯 可能收敛到局部最优每一步都使用当前所有的训练样例 不同于基于单独的训练样例递增作出决定 容错性增强 决策树学习的归纳偏置 ID3的搜索策略优先选择较短的树选择那些信息增益高的属性离根节点较近的树很难准确刻画ID3的归纳偏置近似的ID3的归纳偏置较短的树比较长的树优先近似在于ID3得到局部最优 而不一定是全局最优一个精确具有这个归纳偏置的算法 BFS ID3更贴切近似的归纳偏置较短的树比较长的树优先 信息增益高的属性更靠近根节点的树优先 限定偏置和优选偏置 ID3和候选消除算法的比较ID3的搜索范围是一个完整的假设空间 但不彻底地搜索这个空间候选消除算法的搜索范围是不完整的假设空间 但彻底地搜索这个空间ID3的归纳偏置完全是搜索策略排序假设的结果 来自搜索策略候选消除算法完全是假设表示的表达能力的结果 来自对搜索空间的定义 限定偏置和优选偏置 优选偏置 搜索偏置 ID3的归纳偏置是对某种假设胜过其他假设的一种优选 对最终可列举的假设没有硬性限制限定偏置 语言偏置 候选消除算法的偏置是对待考虑假设的一种限定通常优选偏置比限定偏置更符合归纳学习的需要优选偏置和限定偏置的结合考虑第1章下棋的例子 优选偏置和限定偏置 为什么短的假设优先 ID3的归纳偏置的哲学基础奥坎姆剃刀优先选择拟合数据的最简单的假设科学上的例子物理学家优先选择行星运动的简单假设 简单假设的数量远比复杂假设的数量少 简单假设对训练样例的针对性更小 更像是泛化的规律 而不是训练样例的另一种描述 奥坎姆剃刀 设想你是在一条积雪的街上行走 在你前面有一个人带着一顶黑色的高筒礼帽 街对面站着一群男孩 觉得这顶礼帽是个很好的目标 其中一个扔雪球一下击中了帽子 让我们举出两种解释来说明这顶帽子的随后遭遇 第一 在帽子受击的一刹那 一队天使疾飞而下 出其不意地把帽子从那人头上揭走了 第二 雪球把帽子击落了 我们将选择 种解释 这就是科学上普遍适用的所谓 节俭律 的简单说明 这条定律的意义 就在于说明 最可能的解释就是最好的解释 有时这条定律又被称为奥坎姆剃刀 为什么短的假设优先 奥坎姆剃刀的困难可以定义很多小的假设集合 根据什么相信有短描述的决策树组成的小假设集合比其他可定义的小假设集合更适当 假设的规模由学习器内部使用的特定表示决定从生物进化的观点看内部表示和奥坎姆剃刀原则 决策树学习的常见问题 决策树学习的实际问题确定决策树增长的深度处理连续值的属性选择一个适当的属性筛选度量标准处理属性值不完整的训练数据处理不同代价的属性提高计算效率针对这些问题 ID3被扩展成C4 5 避免过度拟合数据 过度拟合对于一个假设 当存在其它的假设对训练样例的拟合比它差 但事实上在实例的整个分布上表现得却更好时 我们说这个假设过度拟合训练样例 定义 给定一个假设空间H 一个假设h H 如果存在其它的假设h H 使得在训练样例上h的错误率比h 小 但在整个实例分布上h 的错误率比h小 那么就说假设h过度拟合训练数据 树的规模 accuracy 避免过度拟合数据 2 导致过度拟合的原因 1 一种可能原因是训练样例含有随机错误或噪声 SunnyHotNormalStrongPlayTennis No 避免过度拟合数据 3 导致过度拟合的原因 2 当训练数据没有噪声时 过度拟合也有可能发生 特别是当少量的样例被关联到叶子节点时 很可能出现巧合的规律性 使得一些属性恰巧可以很好地分割样例 但却与实际的目标函数并无关系 过度拟合使决策树的精度降低 10 25 避免过度拟合数据 4 避免过度拟合的方法及早停止树增长后修剪法两种方法的特点第一种方法更直观第一种方法中 精确地估计何时停止树增长很困难第二种方法被证明在实践中更成功 避免过度拟合数据 5 避免过度拟合的关键使用什么样的准则来确定最终正确树的规模解决方法使用与训练样例截然不同的一套分离的样例 来评估通过后修剪方法从树上修剪节点的效用 使用所有可用数据进行训练 但进行统计测试来估计扩展 或修剪 一个特定的节点是否有可能改善在训练集合外的实例上的性能 使用一个明确的标准来衡量训练样例和决策树的复杂度 当这个编码的长度最小时停止树增长 避免过度拟合数据 6 方法评述第一种方法是最普通的 常被称为训练和验证集法 可用数据分成两个样例集合 训练集合 形成学习到的假设验证集合 评估这个假设在后续数据上的精度方法的动机 即使学习器可能会被训练集合误导 但验证集合不大可能表现出同样的随机波动验证集合应该足够大 以便它本身可提供具有统计意义的实例样本 常见的做法是 样例的三分之二作训练集合 三分之一作验证集合 错误率降低修剪 将树上的每一个节点作为修剪的候选对象修剪步骤删除以此节点为根的子树 使它成为叶结点把和该节点关联的训练样例的最常见分类赋给它反复修剪节点 每次总是选取那些删除后可以最大提高决策树在验证集合上的精度的节点继续修剪 直到进一步的修剪是有害的为止数据分成3个子集训练样例 形成决策树验证样例 修剪决策树测试样例 精度的无偏估计如果有大量的数据可供使用 那么使用分离的数据集合来引导修剪 决策树学习中错误率降低的修剪效果 规则后修剪 从训练集合推导出决策树 增长决策树直到尽可能好地拟合训练数据 允许过度拟合发生将决策树转化为等价的规则集合 方法是为从根节点到叶节点的每一条路径创建一条规则通过删除不会导致估计精度降低的前件来修剪每一条规则按照修剪过的规则的估计精度对它们进行排序 并按这样的顺序应用这些规则来分类后来的实例 规则后修剪 2 例子if outlook sunny Humidity High thenPlayTennis Noif outlook sunny Humidity Normal thenPlayTennis Yes 考虑删除先行词 outlook sunny 或 Humidity High 选择使估计精度有最大提升的步骤考虑修剪第二个前件作为进一步的修剪步骤 规则后修剪 3 规则精度估计方法使用与训练集不相交的验证集基于训练集合本身被C4 5使用 使用一种保守估计来弥补训练数据有利于当前规则的估计偏置过程先计算规则在它应用的训练样例上的精度然后假定此估计精度为二项式分布 并计算它的标准差对于一个给定的置信区间 采用下界估计作为规则性能的度量评论对于大的数据集 保守预测非常接近观察精度 随着数据集合的减小 离观察精度越来越远不是统计有效 此概念第5章介绍 但是实践中发现有效 规则后修剪 4 把决策树转化成规则集的好处可以区分决策节点使用的不同上下文消除了根节点附近的属性测试和叶节点附近的属性测试的区别提高了可读性 合并连续值属性 ID3被限制为取离散值的属性学习到的决策树要预测的目标属性必须是离散的树的决策节点的属性也必须是离散的简单删除上面第2个限制的方法通过动态地定义新的离散值属性来实现 即先把连续值属性的值域分割为离散的区间集合 合并连续值属性 2 例子 Temperature应该定义什么样的基于阈值的布尔属性选择产生最大信息增益的阈值按照连续属性排列样例 确定目标分类不同的相邻实例产生一组候选阈值 它们的值是相应的A值之间的中间值可以证明产生最大信息增益的c值位于这样的边界中 Fayyad1991 通过计算与每个候选阈值关联的信息增益评估这些候选值方法的扩展连续的属性分割成多个区间 而不是单一阈值的两个空间 属性选择的其它度量标准 信息增益度量存在一个内在偏置 偏向具有较多值的属性避免方法 其它度量 比如增益比率增益比率通过加入一个被称作分裂信息的项来惩罚多值属性 分裂信息用来衡量属性分裂数据的广度和均匀性SplitInformation S A GainRatio S A 分裂信息项阻碍选择值为均匀分布的属性问题 当某个Si S 解决方法 采用一些启发式规则 比如仅对增益高过平均值的属性应用增益比率测试 属性选择的其它度量标准 2 基于距离的度量定义了数据划分间的一种距离尺度计算每个属性产生的划分与理想划分间的距离选择最接近完美划分的属性LopezdeMantaras定义了这个距离度量 证明了它不偏向有大量值的属性此外Mingers实验 不同的属性选择度量对最终精度的影响小于后修剪的程度和方法的影响 缺少属性值的训练样例 例子 医学领域经常需要根据此属性值已知的实例来估计这个缺少的属性值为了评估属性A是否是决策节点n的最佳测试属性 要计算决策树在该节点的信息增益Gain S A 假定是S中的一个训练样例 并且其属性A的值A x 未知 缺少属性值的训练样例 2 处理缺少属性值的策略一种策略是赋给它节点n的训练样例中该属性的最常见值另一种策略是赋给它节点n的被分类为c x 的训练样例中该属性的最常见值更复杂的策略 为A的每个可能值赋予一个概率 而不是简单地将最常见的值赋给A x 处理不同代价的属性 实例的属性可能与代价相关优先选择尽可能使用低代价属性的决策树 仅当需要产生可靠的分类时才依赖高代价属性通过引入一个代价项到属性选择度量中 可以使ID3算法考虑属性代价Tan和Schlimmer的例子 C4 5改进的具体方面 用信息增益率来选择属性克服了用信息增益来选择属性时偏向选择值多的属性的不足 可以处理连续数值型属性采用了一种后剪枝方法对于缺失值的处理 143 小结和补充读物 决策树学习为概念学习和学习其他离散值的函数提供了一个实用的方法ID3算法贪婪算法从根向下推断决策树搜索完整的假设空间归纳偏置 较小的树过度拟合问题ID3算法的扩展 参考 C4 5Tutorialhttp www2 cs uregina ca dbd cs831 notes ml dtrees c4 5 tutorial htmlBuildingClassificationModelsID3andC4 5http www cis temple edu ingargio cis587 readings id3 c45 html 第4章人工神经网络 A