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

2016.11机器学习(Machine Learning)报告建议内容基本概念以及数学定义基本性质及其物理意义具体算法应用（详细举例讲解）该算法与其他类似算法的分析比较可能的发展方向附参考文献2机器学习机器学习，TomM.MitchellTomM.Mitchell（汤姆（汤姆 米切尔）著，曾华军，张银华等译，机米切尔）著，曾华军，张银华等译，机械工业出版社，械工业出版社，20032003年年 。参考书参考书其它参考书机器学习及其应用机器学习及其应用，周志华，王钰主编，周志华，王钰主编，清华大学出版社，清华大学出版社，20092009。神经网络与机器学习神经网络与机器学习，SimonHaykinSimonHaykin著，著，机械工业出版社，机械工业出版社，20102010。机器学习导论机器学习导论，EthemAlpaydinEthemAlpaydin著，机著，机械工业出版社，械工业出版社，20092009。MachineLearningMachineLearningAProbabilisticPerspectiveAProbabilisticPerspectiveKevinP.Murphy,2012KevinP.Murphy,2012第1章 引 言什么是机器学习 【经典定义】：计算机程序如何随着经验积累自动提高性能，系统自我改进的过程。或：计算机利用经验改善系统自身性能的行为。米切尔随着该领域的发展，主要做智能数据分析智能数据分析。学习与智能学习与智能学习现象语言、文字的认知识别图像、场景、自然物体的认知识别规则（eg下雨天要带雨伞）复杂的推理、判断能力（智能）好人与坏人？好猫与坏猫？数据知识认知推理决策识别学习什么是机器学习？什么是机器学习？使得计算机具备和人类一样的学习能力决策推理认知识别等智能给定数据（样本、实例）和一定的学习规则，从数据中获取知识的能力机器学习与人工智能机器学习与人工智能q自然智慧的伟大与奥妙举例：婴儿的认知能力（声音、人脸、汽车）重要的二个特点：容错性，推广能力（举一反三）q机器智能：希望用机器实现部分智能q基于数据的机器学习问题（引自清华张学工教授）根据已知样本估计数据之间的依赖关系，从而对未知或无法测量的数据进行预测和判断关键：推广能力什么是机器学习什么是机器学习q中科院王珏研究员给出的定义：令W是给定世界的有限或无限所有观测对象的集合，由于我们的观测能力有限，我们只能获得这个世界的一个子集，称为样本集。机器学习就是根据这个样本集，推算这个世界W的模型，使它对这个世界（尽可能地）为真。q三个重要的理论问题：一致：W与Q有相同的性质。eg.i.i.d划分：设样本定义于d维空间，要寻找在这个空间上的决策分界面泛化（推广能力）：对未知样本的判断能力WhatWhats is the Learning Problem?s is the Learning Problem?qLearning=ImprovingwithexperienceatsometaskImproveovertaskTWithrespecttoperformancemeasurementPBasedonexperienceEqExample:中国象棋任务T：下中国象棋性能目标P：比赛中击败对手（的百分比）训练经验E：和自己进行对弈，或者看棋谱Ref：机器学习（曾华军等译）PedroPedro对学习理解对学习理解Machine LearningMachine Learning引用自CMUDr.EricXing的LectureNotes机器学习的重要性！机器学习的重要性！qScience2001年论文：每个科学领域的科学过程都有它自己的特点，但是，观察、创立假设、根据决定性实验或观察的检验、可观察、创立假设、根据决定性实验或观察的检验、可理解检验的模型或理论，是各个学科所共有的理解检验的模型或理论，是各个学科所共有的。对这个抽象的科学过程的每一个环节，机器学习都有相应的发展，我们相信它将导致科学方法中从假设生成、模型构造到决定性实验这些所有环节的合适的、部分的自动化。当前机器学习研究在一些基本论题上取得令人印象深刻的进展，我们预期机器学习研究在今后若干年中将有稳定的进展！”在稍早前，2000年Science还发表了另外3篇ML方面的论文“TheManifoldWayofPerceptron”,“Aglobalgeometricframeworkfornonlineardimensionalityreduction”,”Nonlineardimensionalityreductionbylocally”Mjolsness,D DeCoste,Machine Learning for Science:State of the Art and Future Prospects-Science,2001:2051-2055.受到令人惊讶的重视！机器学习的重要性机器学习的重要性摘自南京大学周志华教授生物信息学计算金融学分子生物学行星地质学工业过程控制机器人遥感信息处理信息安全机 器 学 习多学科交叉机器学习机器学习也是一个多学科交叉的产物，它吸也是一个多学科交叉的产物，它吸取了人工智能、概率统计、神经生物学、认取了人工智能、概率统计、神经生物学、认知科学、信息论、控制论、计算复杂性理论、知科学、信息论、控制论、计算复杂性理论、哲学等学科的成果。哲学等学科的成果。实践证明，实践证明，机器学习机器学习在很多应用领域发挥了在很多应用领域发挥了重要的实用价值，特别是在数据挖掘、语音重要的实用价值，特别是在数据挖掘、语音识别、图像处理、机器人、车辆自动驾驶、识别、图像处理、机器人、车辆自动驾驶、生物信息学、信息安全、遥感信息处理、计生物信息学、信息安全、遥感信息处理、计算金融学、工业过程控制。算金融学、工业过程控制。重要性：例子网络安全入侵检测：是否是入侵？是何种入侵？如何检测？历史数据：以往的正常访问模式及其表现、以往的入侵模式及其表现对当前访问模式分类这是一个典型的预测型机器学习问题常用技术：神经网络 决策树支持向量机 k近邻序列分析 聚类 搜索引擎摘自南京大学周志华教授重要性：例子生物信息学常用技术：神经网络 支持向量机隐马尔可夫模型k近邻 决策树序列分析 聚类 重要性：例子数据驱动控制相关学科对相关学科对MLML的影响的影响q人工智能：学习的概念符号表示qBayes方法q统计学：统计学习理论(SLT)q计算复杂性理论q控制论q信息论：最小描述长度q哲学：“OccamsRazor原则”，“没有免费午餐”q心理学和神经生物学：NeuralNetworks（神经网络）机器学习目前主要的一些研究领域符号机器学习Eg.决策树，ID3，计算学习理论（统计学习理论）PAC，SVM监督学习，非监督学习，半监督学习集群机器学习EnsembleLearning，Boosting流行（Manifold）学习强化学习Ranking学习聚类学习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的一些描述：“youwontleavehomewithoutit”；embodiedasasoftwareenvironmentthattranscendsworkstations,PDAs,cellphones,”)讨论议题机器学习的主要策略与基本结构机器学习的主要策略机器学习系统的基本结构机器学习系统的基本结构 我们以西蒙的学习定义做为出发点，建立起下图1.1所示的简单的学习模型，然后通过对这个简单模型的讨论，总结出设计学习系统应当注意的某些总的原则。图图 1.1 1.1 学习系统的基本结构学习系统的基本结构 学习问题的标准描述定义如果一个计算机针对某类任务如果一个计算机针对某类任务T T，用，用P P来衡量性来衡量性能，根据经验能，根据经验E E来自我完善，那么我们称这个来自我完善，那么我们称这个计算机程序在从经验计算机程序在从经验E E中学习，针对某类任务中学习，针对某类任务T T，它的性能用，它的性能用P P来衡量。来衡量。西洋跳棋学习问题的解释E E，和自己下棋，和自己下棋T T，参与比赛，参与比赛P P，比赛成绩（或赢棋能力，击败对手的百分，比赛成绩（或赢棋能力，击败对手的百分比）比）手写识别学习问题机器人驾驶学习问题学习问题的标准描述（2）定义太宽泛甚至包括了以非常直接的方式通过经验自我提甚至包括了以非常直接的方式通过经验自我提高的计算机程序高的计算机程序实际的机器学习问题往往比较复杂定义一类问题定义一类问题探索解决这类问题的方法探索解决这类问题的方法理解学习问题的基本结构和过程理解学习问题的基本结构和过程有监督学习q有监督的学习方法在样本标签已知的情况下，可以统计出各类训练样本不同的描述量，如其概率分布，或在特征空间分布的区域等，利用这些参数进行分类器设计，称为有监督的学习方法。无监督学习q无监督学习然而在实际应用中，不少情况下无法预先知道样本的标签，也就是说没有训练样本因而只能从原先没有样本标签的样本集开始进行分类器设计，这就是通常说的无监督学习方法。q对一个具体问题来说有监督与无监督的作法是不相同的有监督学习x1x2无监督学习x1x2机器学习的问题存在什么样的算法能从特定的训练数据学习一般的目标函数呢存在什么样的算法能从特定的训练数据学习一般的目标函数呢？如果提供了充足的训练数据，什么样的条件下，会使特定？如果提供了充足的训练数据，什么样的条件下，会使特定的算法收敛到期望的函数？哪个算法对哪些问题和表示的性的算法收敛到期望的函数？哪个算法对哪些问题和表示的性能最好？能最好？多少训练数据是充足的？怎样找到学习到假设的置信度与训练多少训练数据是充足的？怎样找到学习到假设的置信度与训练数据的数量及提供给学习器的假设空间特性之间的一般关系数据的数量及提供给学习器的假设空间特性之间的一般关系？学习器拥有的先验知识是怎样引导从样例进行泛化的过程的？学习器拥有的先验知识是怎样引导从样例进行泛化的过程的？当先验知识仅仅是近似正确时，它们会有帮助吗？当先验知识仅仅是近似正确时，它们会有帮助吗？关于选择有效的后验训练经验，什么样的策略最好？这个策略关于选择有效的后验训练经验，什么样的策略最好？这个策略的选择会如何影响学习问题的复杂性。的选择会如何影响学习问题的复杂性。怎样把学习任务简化为一个或多个函数逼近问题？换一种方式，怎样把学习任务简化为一个或多个函数逼近问题？换一种方式，系统该试图学习哪些函数？这个过程本身能自动完成吗？系统该试图学习哪些函数？这个过程本身能自动完成吗？学习器怎样自动地改变表示法来提高表示和学习目标函数的能学习器怎样自动地改变表示法来提高表示和学习目标函数的能力？力？课程内容简介 第第2 2章，基于符号和逻辑表示的章，基于符号和逻辑表示的概念学习概念学习（简介简介）第第3 3章，章，决策树决策树 第第4 4章，章，回归模型与神经网络回归模型与神经网络 第第5 5章，章，评估假设评估假设 第第6 6章，章，贝叶斯理论（贝叶斯理论（混合模型与混合模型与EMEM算法算法）第第7 7章，章，基于实例的学习（基于实例的学习（核函数与径向基函数网络核函数与径向基函数网络）第第8 8章，章，马尔科夫与隐马尔可夫模型马尔科夫与隐马尔可夫模型 第第9 9章，章，支持向量机（支持向量机（线性判别与线性判别与SVMSVM）第第1010章，章，增强学习增强学习参考期刊与会议相关杂志相关杂志 MachineLearningMachineLearning NeuralComputationNeuralComputation JournaloftheAmericanStatisticalAssociationJournaloftheAmericanStatisticalAssociation IEEEtransactionsonPatternAnalysis&IEEEtransactionsonPatternAnalysis&MachineIntelligenceMachineIntelligence国际会议国际会议国际机器学习会议国际机器学习会议ICMLICML神经信息处理系统会议神经信息处理系统会议NIPSNIPS计算学习理论会议计算学习理论会议CCLTCCLT国际遗传算法会议国际遗传算法会议ICGAICGA参考学术期刊及国际会议一些网络资源(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:http:/ 概念学习和一般到特殊序简介许多机器学习涉及到从特殊训练样例中得到一般概念。概念概念，可被看作一个对象或事件集合，它是从更大的集合中选取的子集，或在这个较大集合中定义的布尔函数。概念学习问题概念学习问题的定义给定一个样例集合以及每个样例是否属于某个概念的标注，怎样推断出该概念的一般定义概念的一般定义。又称从样例中逼近布尔函数。概念学习是指从有关某个布尔函数的输入输出训练样例中推断出该布尔函数。概念学习任务一个例子目标概念Aldo进行水上运动的日子，表示为布尔函数进行水上运动的日子，表示为布尔函数EnjoySport任务目的基于某天的各属性，预测基于某天的各属性，预测EnjoySport的值的值给定一个样例集D每个样例表示为每个样例表示为6个属性的集合个属性的集合概念学习任务（2）YesChangeCoolStrongHighWarmSunny4NoChangeWarmStrongHighColdRainy3YesSameWarmStrongHighWarmSunny2YesSameWarmStrongNormalWarmSunny1EnjoySportForecastWaterWindHumidityAirTempSkyExample表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包含5444445120种语法不同语法不同的假设由于：包含有符号的假设将每个实例都分类为反例。因此，语义不同语义不同的假设只有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)记为hjmore_general_than_or_equal_tohk，或hjghk假设的一般到特殊序（3）“更一般”的严格情形hjghk，当且仅当，(hjghk)(hkghj)“更特殊”关系的定义hjghk，当且仅当，hkghj以EnjoySport为例说明上面的定义偏序的特点（区别于全序），全序上的搜索可以是二分法，偏序的搜索比无序简单，比全序复杂。这个偏序关系的定义与目标概念无关h1=h2=h3=x1=x2=Find-S：寻找极大特殊假设使用more_general_than偏序的搜索算法从H中最特殊假设开始，然后在假设覆盖正例失败时将其一般化Find-SFind-S算法算法1.将h初始化为H中最特殊假设2.对每个正例x对对h的每个属性约束的每个属性约束ai如果如果x满足满足ai那么不做任何处理那么不做任何处理否则将否则将h中中ai替换为替换为x满足的另一个更一般约束满足的另一个更一般约束3.输出假设hFind-S：寻找极大特殊假设（2）Find-S算法在例子EnjoySport上的应用hhh遇到反例，h不变（因为h已经能够正确地识别反例）hFind-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=hH|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: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）候选消除算法的归纳偏置cHInductiveSystemsandEquivalentDeductiveSystems(归纳与演绎)归纳偏置（7）3个有偏程度不同的归纳学习算法机械式候选消除算法Find-S一种算法的有偏性越强，它的归纳能力越强，可以分类更多的未见实例。某些归纳偏置隐含在学习器中，有些表示为断言集合，可由学习器操作。小结 主要内容主要内容概念学习可看作搜索预定义潜在假设空间搜索预定义潜在假设空间的过程;假设的一般到特殊偏序结构偏序结构可以定义在任何概念学习问题中，这种结构便于假设空间的搜索;Find-SFind-S算法算法使用一般到特殊序，在偏序结构的一个分支上执行一般到特殊搜索，寻找一个与样例一致的最特殊假设;候选消除算法候选消除算法利用一般到特殊序，通过渐近地计算极大特殊假设集合和极大一般假设集合发现变型空间；候选消除算法缺少健壮性缺少健壮性，后面会描述一些学习算法，它们能够处理有噪声的数据和目标概念无法在假设空间中表示的情况归纳学习算法隐含了归纳偏置隐含了归纳偏置，候选消除算法的偏置是：目标概念可以在假设空间中找到。输出的假设和对新实例的分类可由归纳偏置和训练样例演绎推出思考题2-1.解释为什么EnjoySport学习任务的假设空间的大小为973。如果增加一属性WaterCurrent，可取值Light、Moderate和Strong，那么可能的实例数和可能的假设数将会增加多少？推广到一般，增加一新属性A，有k种取值，实例数和假设数将会增加多少？思考题2-2在候选消除算法中，如果训练样例按EnjoySport例子中的逆序出现，请分步给出S和G边界集合。尝试对训练样例排序，以使EnjoySport例子中的所有S和G集合的中间结果的大小之和为最小？YesChangeCoolStrongHighWarmSunny4NoChangeWarmStrongHighColdRainy3YesSameWarmStrongHighWarmSunny2YesSameWarmStrongNormalWarmSunny1EnjoySportForecastWaterWindHumidityAirTempSkyExample思考题23实现Find-S算法和候选消除算法。验证它是否可成功地产生EnjoySport例子中各步骤结果。第3章决策树学习(Decision-TreeAlgorithm)排排名名主题主题算法算法得票数得票数发表时发表时间间作者作者陈述陈述人人1分类C4.5611993Quinlan,J.RHiroshi Motoda2聚类k-Means601967MacQueen,J.BJoydeep Ghosh3统计学习SVM581995Vapnik,V.NQiangYang4关联分析Apriori521994RakeshAgrawalChristos Faloutsos5统计学习EM482000McLachlan,GJoydeep Ghosh 6链接挖掘PageRank461998Brin,S.Christos Faloutsos7集装与推进AdaBoost451997Freund,Y.Zhi-Hua Zhou 8分类kNN451996Hastie,TVipin Kumar 9分类NaveBayes452001Hand,D.JQiang Yang 10分类CART341984L.BreimanDan Steinberg 共有145人参加了ICDM2006Panel(会议的专题讨论),并对18种候选算法进行投票，选出了机器学习10大算法ICDM2006会议的算法投票结果概论决策树学习是应用最广的归纳推理归纳推理算法之一是一种逼近离散值函数的方法很好的健壮性健壮性能够学习析取表达式析取表达式ID3,Assistant,C4.5搜索一个完整表示的假设空间归纳偏置归纳偏置是优先选择较小的树决策树表示了多个if-then规则提纲决策树定义适用问题特征基本ID3算法决策树学习的归纳偏置训练数据的过度拟合决策树基本概念关于分类问题 分类（分类（ClassificationClassification）任务就是通过学习获得一个目标函数（）任务就是通过学习获得一个目标函数（Target Target FunctionFunction）f,f,将每个属性集将每个属性集x x映射到一个预先定义好的类标号映射到一个预先定义好的类标号y y。分类任务的输入数据是记录的集合，每条记录也称为实例或者样例。分类任务的输入数据是记录的集合，每条记录也称为实例或者样例。用元组用元组(X,y)(X,y)表示，其中，表示，其中，X X 是属性集合，是属性集合，y y是一个特殊的属性，指出样例是一个特殊的属性，指出样例的类标号（也称为分类属性或者目标属性）的类标号（也称为分类属性或者目标属性）决策树基本概念关于分类问题名称体温表皮覆盖胎生水生动物飞行动物有腿冬眠类标号人类恒温毛发是否否是否哺乳动物海龟冷血鳞片否半否是否爬行类鸽子恒温羽毛否否是是否鸟类鲸恒温毛发是是否否否哺乳类Xy分类与回归分类与回归分类目标属性y是离散的，回归目标属性y是连续的决策树基本概念解决分类问题的一般方法通过以上对分类问题一般方法的描述，可以看出分类问题一般包括两个步骤：1 1、模型构建（归纳）、模型构建（归纳）通过对训练集合的归纳，建立分类模型。2 2、预测应用（推论）、预测应用（推论）根据建立的分类模型，对测试集合进行测试。决策树基本概念解决分类问题的一般方法TIDA1A2A3类1Y100LN2N125SN3Y400LY4N415MN学习算法学习模型模型应用模型TIDA1A2A3类1Y100L？2N125S？3Y400L？4N415M？训练集（类标号已知）检验集（类标号未知）归纳推论决策树表示法u内部节点(包括根节点)指定了对实例的某个属性的测试u节点的每个后继分支对应于该属性的一个可能值u叶子节点即为实例所属的分类 uu决策树代表实例属性值约束决策树代表实例属性值约束的合取的析取式的合取的析取式图3-1 概念Play Tennis的决策树OutlookHumidityWindNoYesNoYesYesSunnyRainyOvercastHighNormal StrongWeak决策树学习的适用问题适用问题的特征实例由“属性-值”对表示目标函数具有离散的输出值可能需要析取的描述训练数据可以包含错误训练数据可以包含缺少属性值的实例问题举例医学中的应用（如根据疾病分类患者、疾病分析与预测）根据起因分类设备故障（故障诊断根据拖欠支付的可能性分类贷款申请分类问题核心任务是把样例分类到各可能的离散值对应的类别基本的决策树学习算法ID3大多数决策树学习算法是一种核心算法的变体采用自顶向下的贪婪搜索遍历可能的决策树空间ID3是这种算法的代表该方法使用信息增益度选择测试属性。ID3算法通过自顶向下构造决策树来进行学习。构造过程：构造过程：ID3ID3算法的核心问题是选取在树的每个节点要测试的属性。算法的核心问题是选取在树的每个节点要测试的属性。选择根节点使用统计测试确定每一个实例属性单独分类训练样例的能力，分类能力最好的属性被选作树的根分类能力最好的属性被选作树的根节点节点为根节点属性的每个可能值产生一个分支，并把训练样例排列到适当的分支重复上面的过程，用每个分支节点关联的训练样例来选取在该点被测试的最佳属性，直到满足以下两个条件中的任一个:1）所有的属性已经被这条路径包括；2）与这个节点关联的所有训练样例具有相同的目标属性值表3-1用于学习布尔函数的ID3算法ID3(Examples,Target_attribute,Attributes)创建树的root节点如果Examples都为正,返回label=+的单节点树root如果Examples都为反,返回label=-的单节点树root如果Attributes为空，那么返回单节点root，label=Examples中最普遍的Target_attribute值否则开始 A AAttributesAttributes中分类中分类examplesexamples能力最好的属性能力最好的属性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)