人工智能-6机器学习-ID3

1人工智能ARTIFICIALINTELLIGENCE主讲：鲍军鹏博士西安交通大学电信学院计算机系电子邮箱：[e-mail]版本：2.02010年1月1第六章机器学习6.1概述6.2决策树学习6.3贝叶斯学习6.4统计学习6.5遗传算法6.6聚类6.7特征选择与提取6.8其他学习方法26.1概述6.1.1什么是机器学习？学习是人类具有的一种重要智能行为，但究竟什么是学习，长期以来却众说纷纭。关于“学习”这一概念的主要观点：学习是系统改进其性能的过程。这是西蒙的观点。西蒙的观点：学习就是系统在不断重复的工作中对本身能力的增强或者改进，使得系统在下一次执行同样任务或类似任务时，会比现在做得更好或效率更高。学习是获取知识的过程。这是从事专家系统研究的人们的观点。学习是技能的获取。这是心理学家的观点。学习是事物规律的发现过程。3基本的学习形式基本的学习形式有2种：知识获取和技能求精。例如，我们说某人学过物理。我们的意思是，此人已经掌握了有关物理学的基本概念，并且理解其含义，同时还懂得这些概念之间以及它们与物理世界之间的关系。一般地，知识获取可看作学习新的符号信息，而这些符号信息是以有效方式与应用这种信息的能力相适应的。第二类学习形式是通过实践逐步改进机制和认知技能。例如骑自行车或弹钢琴等等。学习的很多过程都是由改进所学的技能组成。这些技能包括意识的或者机制的协调，而这种改进又是通过反复实践和从失败的行为中纠正偏差来进行的。知识获取的本质可能是一个自觉的过程，其结果产生新的符号知识结构和智力模型。而技能求精则是下意识地借助于反复实践来实现的。人类的学习一般表现尾这两种活动的结合。4机器学习的定义至今，还没有统一的“机器学习”定义，而且也很难给出一个公认的和准确的定义。一般认为机器学习是研究如何使用机器来模拟人类学习活动的一门学科。最早的具有学习能力的程序：1959年美国的塞缪尔(Samuel)设计了一个下棋程序，这个程序具有学习能力，它可以在不断的对奕中改善自己的棋艺。4年后，这个程序战胜了设计者本人。又过了3年，这个程序战胜了美国一个保持8年之久的常胜不败的冠军。5机器学习发展简史第一阶段在50年代中叶到60年代中叶，神经元模型的研究。第二阶段在60年代中叶至70年代，符号学习的研究。第三阶段80年代，连接学习的研究与符号学习的进展。90年代以后，综合多学科、多种方法的知识发现、数据挖掘与机器学习研究6ML、KDD和DM知识发现(KnowledgeDiscoveringinDatabase)与数据挖掘(DataMining)是人工智能、机器学习与(MachineLearning)数据库技术相结合的产物。1980年,在美国召开了第一届国际机器学习研讨会;1984年,《机器学习》杂志问世。我国于1987年召开了第一届全国机器学习研讨会;1989年成立了以中国科技大学蔡庆生教授为理事长的理事会。KDD一词是在1989年于美国底特律市召开的第一届KDD国际学术会议上正式形成的。1995年,在加拿大召开了第一届知识发现和数据挖掘国际学术会议。由于数据库中的数据被形象地喻为矿床,因此数据挖掘一词很快流传开来。7机器学习系统的基本结构环境向系统的学习部分提供某些信息，学习部分利用这些信息修改知识库，以增进系统执行部分完成任务的效能，执行部分根据知识库完成任务，同时把获得的信息反馈给学习部分。在具体的应用中，环境，知识库和执行部分决定了具体的工作内容，学习部分所需要解决的问题完全由上述3部分确定。8学习系统的基本结构机器学习的一般步骤机器学习系统中学习环节的一般过程9收集数据确定学习模型清洗数据提取特征训练获得知识6.1.2机器学习方法分类按照有无指导来分：有监督学习（或有导师学习）、无监督学习（或无导师学习）和强化学习（或增强学习）。按学习方法来分：有机械式学习、指导式学习、范例学习、类比学习、解释学习。按推理策略来分：有演绎学习、归纳学习、类比学习、解释学习等。综合多因素的分类：有人工神经网络学习、进化学习、概念学习、分析学习、基于范例的学习等等。106.1.3机器学习的基本问题机器学习中解决的基本问题主要有：分类、聚类、预测、联想、优化。令S表示数据空间，Z表示目标空间。机器学习就是在现有观察的基础上求得一个函数L:S→Z，实现从给定数据到目标空间的映射。不同特征的学习函数实际上表示了不同的基本问题。11分类问题目标空间是已知有限离散值空间，即，Z=C={c1,c2,…ci,…,cn}待求函数就是分类函数（分类器/分类模型）。分类问题所用的训练数据是D,C，。由于学习时目标类别已知，所以分类算法都是有监督学习。常用的方法：决策树方法、贝叶斯方法、前馈神经网络BP算法、支持向量机方法等12SDc1cnc2...SC●●●●●●●预测问题目标空间是连续值空间，待求函数就是回归（拟合）曲线（面）。此时机器学习解决预测问题，也就是求一个数据在目标空间中符合某观测规律的象。预测问题所用的训练数据是D,R，。一般情况下我们事先已知（或者选择了）曲线（面）模型，需要学习的是模型中的参数。例如已知多项式模型，但是要学习各项的系数。常用的方法：人工神经网络方法、线性回归、非线性回归、灰色预测模型等。13SDSR●●●●●●聚类问题目标空间是未知有限离散值空间，即，Z=X={x1,x2,…,xk}待求函数就是聚类函数，也称为聚类模型。聚类问题就是把已知数据集划分为不同子集（类别），并且不同类别之间的差距越大越好，同一类别内的数据差距越小越好。聚类问题所用的训练数据是D（）。聚类问题要用无监督学习常用的方法：划分聚类法、层次聚类法、基于密度的聚类、基于网格的聚类、自组织特征映射网络等等。14SDx1xkx2...SX●●●●●●●联想问题目标空间就是数据空间本身，即，Z=S待求函数就是求自身内部的一种映射。联想问题，也称为相关性分析或者关联问题就是发现不同数据（属性）之间的相互依赖关系。简单地说，就是可以从事物A推出事物B，即A→B常用的方法：反馈神经网络、关联规则、回归分析等等。15SS●●●●●●⊙●●●●⊙⊙⊙⊙优化问题目标空间是数据空间上的某种函数（用F(S)表示），且学习目标为使对函数F(S)的某种度量d[F(S)]达到极值。解决优化问题，就是在给定数据范围内寻找使某值达到最大（最小）的方法。优化问题一般都有一些约束条件例如时空资源的限制等等。典型代表就是NP问题，这也是计算机科学中的一类经典问题。解决优化问题对于提高系统效率，保证系统实用性有重要意义。常用的方法有：遗传算法、Hopfield神经网络、线性规划方法等等。16SF(S)★Max{d[F(S)]}6.1.4评估学习结果机器学习一般不要求结果100%正确。评估原则学习结果的合理性和有效性模型的泛化能力（Generalization）越强越好。算法复杂度（Complexity）时间复杂度、空间复杂度等。减小时间复杂度常用的思路：简化问题，降低要求；用空间换时间；用并行化算法，提高并行度17评估原则模型鲁棒性（Robustness）就是系统的健壮性，就是系统处理各种非正常数据的能力。包括对数据噪声的处理，对缺失数据及其它包含不完整信息数据的处理，对错误数据或者含有矛盾数据的处理等等。18评估原则模型适应性。是指对于不同数据，学习模型本身需要做多少人工调整。我们一般都希望模型本身需要人工指定参数越少越好。自适应模型并不意味着彻底不需要人工指定的参数。模型描述的简洁性和可解释性。根据奥坎姆剃刀（Occam’sRazor）原则，应该优先选择更简单的假设。模型描述愈简洁、愈容易理解，则愈受欢迎。19机器学习中的测试数据从S中分割出训练数据和测试数据假设S是已有数据集，并且训练数据和测试数据都遵从同样的分布规律。保留法（Holdout）取S的一部分（通常为2/3）作为训练数据，剩下的部分（通常为1/3）作为测试数据。最后在测试数据集上验证学习结果。特点仅仅使用了部分（2/3）数据训练学习模型，没有充分利用所有的已知数据。保留法一般用于已知数据量非常巨大的时候。20机器学习中的测试数据交叉验证法（CrossValidation）也称为交叉纠错法把S划分为k个不相交的子集，即S={S1,S2,…,Sk}，(Si∩Sj=Φ,1≤i,j≤k)然后取其中一个子集作测试集，剩下数据作训练集。取Si做测试集，则S-Si就做训练集。重复k次，把每一个子集都做一次测试集。于是会得到k个测试结果，最终的测试结果就是这k个测试结果的平均值。特点交叉验证法还可以再重复多次，每次变换不同的k值或者不同的划分。交叉验证法充分利用了所有已知数据，可以获得较好的学习结果，但是显然需要更长的训练时间。交叉验证法一般用于已知数据量不太大的时候。21机器学习中的测试数据随机法随机抽取S中的一部分数据作为测试数据，把剩下的数据作为训练数据。重复这一过程足够多次。最终测试结果是所有测试结果的平均值。特点随机法可以重复无数次，每个数据都可能被充分地用于训练和测试，可以把测试结果的置信区间减小到指定宽度。随机法中不同的测试集不能看作是对已知数据的独立抽取。而交叉验证法中不同的测试集是独立的，因为一个数据只在测试集中出现一次。22度量学习结果有效性的指标误差（Error）测试数据集T上的误差是其中，Ei表示某个数据的理想结果，Li表示该数据的机器学习结果。常用的误差实际上就是方差23||1)(TiiiiLEPTError||112)()(TidjijijiLEPTError度量学习结果有效性的指标正确率（Accuracy）或错误率（ErrorRate）正确率是被正确处理的数据个数与所有被处理数据个数的比值其中TErrorε表示被正确处理的数据，也就是误差足够小的数据错误率则是没有被正确处理的数据个数与所有被处理数据个数的比值24||||)(TTTAccuracyError)(1||||1||||||)(TAccuracyTTTTTTErrorRateErrorError度量学习结果有效性的指标复合指标精度（Precision，或称为命中率，准确率）召回率（Recall，或称为覆盖率）a：判定属于类且判定正确；b：判定属于类且判定错误；c：判定不属于类且判定正确；d：判定不属于类且判定错误。T=a+b+c+d25Tcadb||||)(baaTprecision||||)(daaTrecall||||)(dcbacaTAccuracy度量学习结果有效性的指标Fβ度量（Fβ-Measure）Fβ度量是精度和召回率的调和平均数（HarmonicMean）其中β是一个大于0的实数，表示精度相对于召回率的权重。最常用β=1，即F1度量26)()()()()1()(22TrecallTprecisionTrecallTprecisionTF)()()()(2)(1TrecallTprecisionTrecallTprecisionTF度量学习结果有效性的指标多分类问题学习结果的评判对于测试集T，目标类别共有k个宏平均法（MacroAverage）思路先计算各个类别自身的精度和召回率，然后把各个类别的指标加在一起求算术平均值。宏平均精度宏平均召回率27kiimacroTprecisionkTprecision1)(1)(kiimacroTrecallkTrecall1)(1)(度量学习结果有效性的指标微平均法（MicroAverage）把整个测试集看作单分类问题，一次性计算所有个体样本指标的平均值。微