机器学习算法汇总汇总课件.ppt

,2016.11,机器学习(Machine Learning),报告建议内容,基本概念以及数学定义基本性质及其物理意义具体算法应用（详细举例讲解）该算法与其他类似算法的分析比较可能的发展方向附参考文献,2,机器学习，TomM.Mitchell（汤姆米切尔）著，曾华军，张银华等译，机械工业出版社，2003年。,参考书,其它参考书,机器学习及其应用，周志华，王钰主编，清华大学出版社，2009。神经网络与机器学习，Simon Haykin著，机械工业出版社，2010。机器学习导论，Ethem Alpaydin著，机械工业出版社，2009。Machine Learning A Probabilistic Perspective Kevin P.Murphy,2012,第1章 引 言,什么是机器学习【经典定义】：计算机程序如何随着经验积累自动提高性能，系统自我改进的过程。或：计算机利用经验改善系统自身性能的行为。米切尔随着该领域的发展，主要做智能数据分析。,学习与智能,学习现象语言、文字的认知识别图像、场景、自然物体的认知识别规则（eg 下雨天要带雨伞）复杂的推理、判断能力（智能）好人与坏人？好猫与坏猫？,什么是机器学习？,使得计算机具备和人类一样的学习能力决策推理认知识别 等智能给定数据（样本、实例）和一定的学习规则，从数据中获取知识的能力,机器学习与人工智能,自然智慧的伟大与奥妙举例：婴儿的认知能力（声音、人脸、汽车）重要的二个特点：容错性，推广能力（举一反三）机器智能：希望用机器实现部分智能基于数据的机器学习问题（引自清华张学工教授）根据已知样本估计数据之间的依赖关系，从而对未知或无法测量的数据进行预测和判断关键：推广能力,什么是机器学习,中科院王珏研究员给出的定义：令W是给定世界的有限或无限所有观测对象的集合，由于我们的观测能力有限，我们只能获得这个世界的一个子集，称为样本集。机器学习就是根据这个样本集，推算这个世界W的模型，使它对这个世界（尽可能地）为真。三个重要的理论问题：一致：W与Q有相同的性质。eg.i.i.d划分：设样本定义于d维空间，要寻找在这个空间上的决策分界面泛化（推广能力）：对未知样本的判断能力,Whats is the Learning Problem?,Learning=Improving with experience at some taskImprove over task TWith respect to performance measurement PBased on experience EExample:中国象棋任务T：下中国象棋 性能目标P：比赛中击败对手（的百分比）训练经验E：和自己进行对弈，或者看棋谱,Ref：机器学习（曾华军等译）,Pedro对学习理解,Machine Learning,引用自CMU Dr.Eric Xing的Lecture Notes,机器学习的研究意义,机器学习的重要性！,Science2001年论文：每个科学领域的科学过程都有它自己的特点，但是，观察、创立假设、根据决定性实验或观察的检验、可理解检验的模型或理论，是各个学科所共有的。对这个抽象的科学过程的每一个环节，机器学习都有相应的发展，我们相信它将导致科学方法中从假设生成、模型构造到决定性实验这些所有环节的合适的、部分的自动化。当前机器学习研究在一些基本论题上取得令人印象深刻的进展，我们预期机器学习研究在今后若干年中将有稳定的进展！”在稍早前，2000年Science还发表了另外3篇ML方面的论文“The Manifold Way of Perceptron”,“A global geometric framework for nonlinear dimensionality reduction”,”Nonlinear dimensionality reduction by locally”,Mjolsness,D DeCoste,Machine Learning for Science:State of the Art and Future Prospects-Science,2001:2051-2055.,受到令人惊讶的重视！,机器学习的重要性,摘自南京大学周志华教授,生物信息学,计算金融学,分子生物学,行星地质学,工业过程控制,机器人,遥感信息处理,信息安全,机 器 学 习,多学科交叉,机器学习也是一个多学科交叉的产物，它吸取了人工智能、概率统计、神经生物学、认知科学、信息论、控制论、计算复杂性理论、哲学等学科的成果。实践证明，机器学习在很多应用领域发挥了重要的实用价值，特别是在数据挖掘、语音识别、图像处理、机器人、车辆自动驾驶、生物信息学、信息安全、遥感信息处理、计算金融学、工业过程控制。,重要性：例子网络安全,入侵检测：是否是入侵？是何种入侵？,如何检测？历史数据：以往的正常访问模式及其表现、以往的入侵模式及其表现对当前访问模式分类,这是一个典型的预测型机器学习问题常用技术：神经网络 决策树支持向量机 k近邻序列分析 聚类,搜索引擎,摘自南京大学周志华教授,重要性：例子生物信息学,常用技术：神经网络 支持向量机隐马尔可夫模型k近邻 决策树序列分析 聚类,重要性：例子数据驱动控制,相关学科对ML的影响,人工智能：学习的概念符号表示Bayes 方法统计学：统计学习理论(SLT)计算复杂性理论控制论信息论：最小描述长度哲学：“Occams Razor原则”，“没有免费午餐”心理学和神经生物学：Neural Networks（神经网络）,机器学习目前主要的一些研究领域,符号机器学习Eg.决策树，ID3，计算学习理论（统计学习理论）PAC，SVM监督学习，非监督学习，半监督学习集群机器学习Ensemble Learning，Boosting流行（Manifold）学习强化学习Ranking学习聚类学习,Machine Learning Topics from Wiki,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的一些描述：“you wont leave home without it”；”embodied as a software environment that transcends workstations,PDAs,cell phones,”),讨论议题,机器学习的主要策略与基本结构 机器学习的主要策略 机器学习系统的基本结构,机器学习系统的基本结构,我们以西蒙的学习定义做为出发点，建立起下图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章，增强学习,参考期刊与会议,相关杂志Machine LearningNeural ComputationJournal of the American Statistical AssociationIEEE transactions on Pattern Analysis&Machine Intelligence国际会议国际机器学习会议ICML神经信息处理系统会议NIPS计算学习理论会议CCLT国际遗传算法会议ICGA,参考学术期刊及国际会议,一些网络资源(1),http:/machine-AAAI Machine Learning Topics：www.aaai.org/AITopics/html/machine.html-Support Vector Machines：http:/www.support-vector-machines.org/index.html,一些网络资源(2),http:/www.cs.cmu.edu/tom/10701_sp11/lectures.shtmlMachine Learning(Spring 2011)CMUTom MitchellVideo Lecture&SlidesMachine Learning Resources:http:/,一些网络资源(3),Weka：Data Mining(ML)software in Java:http:/www.cs.waikato.ac.nz/ml/weka/LibSVM-A Library for Support Vector Machines：www.csie.ntu.edu.tw/cjlin/libsvm MLC+:http:/:A library of C+classes for supervised machine learning UCI-Machine Learning information,software and databases:http:/archive.ics.uci.edu/ml/,一些网络资源(4),Kernal Machines:http:/www.kernel-machines.org/http:/mloss.org/software/:Machine Learning Open Source Softwarehttp:/www3.ntu.edu.sg/home/aswduch/ai-ml.html 数据挖掘研究院：http:/,概念学习给定某一类别的若干正例和反例，从中获得该类别的一般定义。搜索的观点在预定义的假设空间中搜索假设，使其与训练样例有最佳的拟合。利用假设空间的偏序结构算法收敛到正确假设的条件?归纳学习的本质，从训练数据中泛化的理由?,第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：包含322222=96种不同的实例假设空间H包含544444=5120种语法不同的假设由于：包含有符号的假设将每个实例都分类为反例。因此，语义不同的假设只有1+433333=973个。,假设的一般到特殊序,假设的一般到特殊序关系考虑下面两个假设h1=h2=任何被h1划分为正例的实例都会被h2划分为正例，因此h2比h1更一般。利用这个关系，无需列举所有假设，就能在无限的假设空间中进行彻底的搜索,假设的一般到特殊序（2）,关系“更一般”的精确定义任给实例x和假设h，说x满足h，当且仅当h(x)=1令hj和hk是在X上定义的布尔函数，称hj比hk更一般，当且仅当(xX)(hk(x)=1)(hj(x)=1)记为hj more_general_than_or_equal_to hk，或hj g hk,假设的一般到特殊序（3）,“更一般”的严格情形hj g hk，当且仅当，(hj g hk)(hk g hj)“更特殊”关系的定义hj g hk，当且仅当，hk g hj以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上的应用hhh遇到反例，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)“一致”与“满足”的关系变型空间（Version Space）与训练样例一致的所有假设组成的集合表示了目标概念的所有合理的变型关于H和D的变型空间，记为VSH,D，是H中与训练样例D一致的所有假设构成的子集VSH,D=hH|Consistent(h,D),变型空间和候选消除算法（3）,列表后消除算法表示变型空间的一种方法是列出其所有成员变型空间包含H中所有假设的列表对每个训练样例，从变型空间中移除所有h(x)c(x)的假设输出Version Space中的假设列表优点保证得到所有与训练数据一致的假设缺点非常繁琐地列出H中的所有假设，大多数实际的假设空间无法做到,变型空间和候选消除算法（4）,变型空间的更简洁表示变型空间被表示为它的极大一般和极大特殊的成员这些成员形成了一般和特殊边界的集合，这些边界在整个偏序结构中划分出变型空间以EnjoySport为例,变型空间和候选消除算法（5）,形式化定义极大一般极大特殊关于假设空间H和训练数据D的一般边界G，是在H中与D相一致的极大一般成员的集合关于假设空间H和训练数据D的特殊边界S，是在H中与D相一致的极大特殊成员的集合,变型空间和候选消除算法（6）,变型空间表示定理:令X为一任意的实例集合，H为X上定义的布尔假设的集合。令c:X0,1为X上定义的任一目标概念，并令D为任一训练样例集合。对所有的X,H,c,D以及良好定义的S和G：VSH,D=hH|(sS)(gG)(gghgs)证明：只需证明：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:,S2 S3:,S4:,G4:,G0 G1:,G0 G1 G2:,图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）,归纳偏置的精确定义(Dcxi)L(xi,Dc)需要在Dcxi上附加怎样的前提，以使L(xi,Dc)能够演绎派生。L的归纳偏置定义为前提集合B，使所有的新实例满足：(BDcxi)L(xi,Dc)考虑对于实例集合X的概念学习算法L。令c为X上定义的任一概念，并令Dc为c的任意训练样例集合，L(xi,Dc)表示经过Dc训练后L赋予实例xi的分类。L的归纳偏置是最小断言集合B，它使任意目标概念c和相应的训练样例Dc满足：xiX(BDcxi)L(xi,Dc),归纳偏置（6）,候选消除算法的归纳偏置cHInductive Systems and Equivalent Deductive Systems(归纳与演绎),归纳偏置（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-Tree Algorithm),共有145人参加了ICDM 2006 Panel(会议的专题讨论),并对18种候选算法进行投票，选出了机器学习10大算法,ICDM 2006会议的算法投票结果,概 论,决策树学习是应用最广的归纳推理算法之一是一种逼近离散值函数的方法很好的健壮性能够学习析取表达式ID3,Assistant,C4.5搜索一个完整表示的假设空间归纳偏置是优先选择较小的树决策树表示了多个if-then规则,提 纲,决策树定义适用问题特征基本ID3算法决策树学习的归纳偏置训练数据的过度拟合,决策树基本概念,关于分类问题,分类（Classification）任务就是通过学习获得一个目标函数（Target Function）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值否则开始AAttributes中分类examples能力最好的属性root的决策属性A对于A的每个可能值vi在root下加一个新的分支对应测试A=vi令Examplesvi为Examples中满足A属性值为vi的子集如果Examplesvi为空在这个新分支下加一个叶子节点，节点的label=Examples中最普遍的Target_attribute值否则在新分支下加一个子树ID3（Examplesvi,Target_attribute,Attributes-A）结束返回root,最佳分类属性,信息增益(Information Gain)用来衡量给定的属性区分训练样例的能力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.246 Gain（S，Humidity）0.151 Gain（S，Wind）0.048 Gain（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,D114,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的归纳偏置的哲学基础奥坎姆剃刀优先选择拟合数据的最简单的假设科学上的例子物理学家优先选择行星运动的简单假设；简单假设的数量远比复杂假设的数量少；简单假设对训练样例的针对性更小，更像是泛化的规律，而不是训练样例的另一种描述。,奥坎姆剃刀,设想你是在一条积雪的街上行