《AI-第6章 机器学习（1）-决策树.pptx》由会员分享，可在线阅读，更多相关《AI-第6章 机器学习（1）-决策树.pptx（70页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、人工智能导论6.1 概述6.2 决策树学习6.3 贝叶斯学习6.4 统计学习6.5 聚类6.6 特征选择与表示学习6.7 其他学习方法第六章第六章 机器学习机器学习6.1 6.1 概述概述u学习是系统改进其性能的过程。这是西蒙的观点。西蒙的观点：学习就是系统在不断重复的工作中对本身能力的增强或者改进，使得系统在下一次执行同样任务或类似任务时，会比现在做得更好或效率更高。u学习是获取知识的过程。这是从事专家系统研究的人们的观点。u学习是技能的获取。这是心理学家的观点。u学习是事物规律的发现过程。46.1.1 6.1.1 什么是机器学习什么是机器学习基本的学习形式u知识获取和技能求精。u我们的意思
2、是，此人已经掌握了有关物理学的基本概念，并且理解其含义，同时还懂得这些概念之间以及它们与物理世界之间的关系。u一般地，知识获取可看作学习新的符号信息，而这些符号信息是以有效方式与应用这种信息的能力相适应的。u学习的很多过程都是由改进所学的技能组成。这些技能包括意识的或者机制的协调，而这种改进又是通过反复实践和从失败的行为中纠正偏差来进行的。5机器学习的定义u1959年美国的塞缪尔(Samuel)设计了一个下棋程序，这个程序具有学习能力，它可以在不断的对奕中改善自己的棋艺。4年后，这个程序战胜了设计者本人。又过了3年，这个程序战胜了美国一个保持8年之久的常胜不败的冠军。6MLML、KDDKDD和
3、DMDM u1980年,在美国召开了第一届国际机器学习研讨会;1984年,机器学习杂志问世。我国于1987年召开了第一届全国机器学习研讨会;1989年成立了以中国科技大学蔡庆生教授为理事长的理事会。uKDD一词是在1989年于美国底特律市召开的第一届KDD国际学术会议上正式形成的。7u融汇工学、数学、医学、认知学等很多学科的一个交叉学科u人工智能中最火热火热的研究领域之一u最火热火热的机器学习方法之一人工智能人工智能机器学习机器学习深度学习深度学习机器学习系统的基本结构9学习系统的基本结构机器学习的一般步骤10深度学习深度学习深度学习u有监督学习（或有导师学习）、无监督学习（或无导师学习）和强
4、化学习（或增强学习）。u有机械式学习、指导式学习、范例学习、类比学习、解释学习。u有演绎学习、归纳学习、类比学习、解释学习等。u有人工神经网络学习、进化学习、概念学习、分析学习、基于范例的学习等等。116.1.2 6.1.2 机器学习方法分类机器学习方法分类u分类、聚类、预测、联想、优化。u机器学习就是在现有观察的基础上求得一个函数L:SZ实现从给定数据到目标空间的映射。126.1.3 6.1.3 机器学习的基本问题机器学习的基本问题分类问题已知有限离散已知有限离散即，Z=C=c1,c2,ci,cn有监督学习有监督学习u决策树方法、贝叶斯方法、前馈神经网络BP算法、支持向量机、逻辑回归、深度学
5、习等 13预测问题连续值连续值此时机器学习解决预测问题，也就是求一个数据在目标空间中符合某观测规律的象。u一般情况下我们事先已知（或者选择了）曲线（面）模型，需要学习的是模型中的参数。u例如已知多项式模型，但是要学习各项的系数。u人工神经网络方法、线性回归、非线性回归、灰色预测模型等。14聚类问题未知有限离散未知有限离散即，Z=X=x1,x2,xk待求函数就是聚类函数，也称为聚类模型。无监督学习无监督学习u划分聚类法、层次聚类法、基于密度的聚类、基于网格的聚类、自组织特征映射网络、谱聚类等等。15联想问题即，Z=S待求函数就是求自身内部的一种映射。u就是发现不同数据（属性）之间的相互依赖关系。
6、u简单地说，就是可以从事物A推出事物B，即ABu反馈神经网络、关联规则、回归分析等等。16优化问题u例如时空资源的限制等等。u典型代表就是NP问题，这也是计算机科学中的一类经典问题。u遗传算法、粒子群算法、蚁群算法、Hopfield神经网络、线性规划方法等等。17u模型的泛化能力（Generalization）越强越好。u时间复杂度、空间复杂度等。u减小时间复杂度常用的思路：简化问题，降低要求；用空间换时间；用并行化算法，提高并行度 186.1.4 6.1.4 评估学习结果评估学习结果评估原则u就是系统的健壮性，就是系统处理各种非正常数据的能力。u包括对数据噪声的处理，对缺失数据及其它包含不完
7、整信息数据的处理，对错误数据或者含有矛盾数据的处理等等。19评估原则是指对于不同数据，学习模型本身需要做多少人工调整。我们一般都希望模型本身需要人工指定参数越少越好。自适应模型并不意味着彻底不需要人工指定的参数。根据奥坎姆剃刀（Occams Razor）原则，应该优先选择更简单的假设。模型描述愈简洁、愈容易理解，则愈受欢迎。20机器学习中的测试数据u假设S是已有数据集，并且训练数据和测试数据都遵从同样的分布规律。u取S的一部分（通常为2/3）作为训练数据，剩下的部分（通常为1/3）作为测试数据。u最后在测试数据集上验证学习结果。u仅仅使用了部分（2/3）数据训练学习模型，没有充分利用所有的已知
8、数据。u保留法一般用于已知数据量非常巨大的时候。21机器学习中的测试数据u也称为交叉纠错法u把S划分为k个不相交的子集，即S=S1,S2,Sk，(SiSj=,1i,jk)u然后取其中一个子集作测试集，剩下数据作训练集。取Si做测试集，则S-Si就做训练集。重复k次，把每一个子集都做一次测试集。于是会得到k个测试结果，最终的测试结果就是这k个测试结果的平均值。u交叉验证法还可以再重复多次，每次变换不同的k值或者不同的划分。u交叉验证法充分利用了所有已知数据，可以获得较好的学习结果，但是显然需要更长的训练时间。u交叉验证法一般用于已知数据量不太大的时候。22机器学习中的测试数据u随机抽取S中的一部
9、分数据作为测试数据，把剩下的数据作为训练数据。u重复这一过程足够多次。u最终测试结果是所有测试结果的平均值。u随机法可以重复无数次，每个数据都可能被充分地用于训练和测试，可以把测试结果的置信区间减小到指定宽度。u随机法中不同的测试集不能看作是对已知数据的独立抽取。而交叉验证法中不同的测试集是独立的，因为一个数据只在测试集中出现一次。23度量学习结果有效性的指标 u测试数据集T上的误差是其中，Ei表示某个数据的理想结果，Li表示该数据的机器学习结果。u常用的误差实际上就是方差 24度量学习结果有效性的指标u正确率是被正确处理的数据个数与所有被处理数据个数的比值其中TError表示被正确处理的数据
10、，也就是误差足够小的数据 u错误率则是没有被正确处理的数据个数与所有被处理数据个数的比值 25度量学习结果有效性的指标u精度（Precision，或称为命中率，准确率）u召回率（Recall，或称为覆盖率）a：判定属于类且判定正确；b：判定属于类且判定错误；c：判定不属于类且判定正确；d：判定不属于类且判定错误。T=a+b+c+d26度量学习结果有效性的指标u反映敏感性和特异性连续变量的综合指标u当测试集中正负样本分布变化时，ROC曲线能够保持不变u横坐标是假阳性率（误诊率，FPR）u纵坐标是真阳性率（召回率或敏感度TPR）uROC曲线下方的面积度量学习结果有效性的指标uF度量是精度和召回率的
11、调和平均数（Harmonic Mean）其中是一个大于0的实数，表示精度相对于召回率的权重。u最常用=1，即F1度量 28度量学习结果有效性的指标u对于测试集T，目标类别共有k个u思路先计算各个类别自身的精度和召回率，然后把各个类别的指标加在一起求算术平均值。u宏平均精度u宏平均召回率 29度量学习结果有效性的指标u把整个测试集看作单分类问题，一次性计算所有个体样本指标的平均值。u微平均精度 u微平均召回率 306.2 6.2 决策树学习决策树学习决策树学习u应用最广的归纳推理算法之一。u是一种逼近离散值函数的方法。u在这种方法中学习到的函数被表示为一颗决策树。u学习得到的决策树也能再被表示为
12、多个if-then规则，以提高可读性。u比如ID3、C4.5、ASSISTANT等等。u这些决策树学习方法搜索一个完整表示的假设空间，从而避免了受限假设空间的不足。u决策树学习的归纳偏置是优先选择较小的树。32u从这颗树的根节点开始，测试这个节点指定的属性；u然后按照给定实例的该属性值对应的树枝向下移动；u然后这个过程再以新节点为根的子树上重复。336.2.1 6.2.1 决策树表示法决策树表示法决策树示例例子：在一个水果的分类问题中，采用的特征向量为：颜色，尺寸，形状，味道，其中：样本集：一批水果，知道其特征向量及类别34决策树示例35决策树示例36决策树的适用问题u实例是由“属性-值”对表
13、示的：实例是用一系列固定的属性和它们的值来描述的。u目标函数具有离散的输出值：决策树给每个实例赋予一个布尔型的分类。决策树方法很容易扩展到学习有两个以上输出值的函数。u可能需要析取的描述：决策树很自然地代表了析取表达式。u训练数据可以包含错误：决策树学习对错误有很好的健壮性，无论是训练样例所属的分类错误，还是描述这些样例的属性值错误。u训练数据可以包含缺少属性值的实例：决策树甚至可以再有未知属性值的训练样例中使用。37386.2.2 6.2.2 ID3ID3算法算法ID3ID3算法 u在每个节点选取能最好分类样例的属性；u继续这个过程指导这棵树能完美分类训练样例；u或所有的属性都已被使用过。u
14、分类能力最好的属性被选作树的根节点的测试。u然后为根节点属性的每个可能值产生一个分枝，并把训练样例排列到适当的分枝（也就是，样例的该属性值对应的分枝）之下。u算法从不回溯重新考虑以前的选择。39ID3算法的核心问题u如何衡量一个属性价值的高低呢？u这个问题没有统一答案。uID3算法选择信息增益（Information GainInformation GainInformation GainInformation Gain）最大的属性作为决策树结点。40熵（Entropy）那么数据集D对于这c个状态的熵为其中Pi是数据集D中取值为i（或者说属于类别i）的数据的比例（或者概率）。41信息增益（In
15、formation Gain）u由于使用该属性分割数据集D，而导致数据集D期望熵减少的程度。uValues(A)是属性A所有可能值的集合。uDv是D中属性A的值为v的子集，即Dv=d|dD,A(d)=v。uEntropy(D)是D未用属性A分割之前的熵。uEntropy(Dv)是D用属性A分割之后的熵。u属性A的每一个可能取值都有一个熵，该熵的权重是取该属性值的数据在数据集D中所占的比例。42决策树的结点划分 u结点n中的样本属于同一类，即结点n绝对纯净。此时结点n不可进一步划分。u结点n中的样本不属于同一类，但是不存在任何一个划分可以使其子结点的平均熵低于结点n。此时结点n不可进一步划分。u
16、可以用一个属性对结点n进行划分，从而使结点n的子结点具有更低的熵。此时结点n可以进一步划分。43确定叶节点u对于每一个可以进一步划分的结点都进行划分，直到得到一个不可划分的子结点，并将该子结点定为叶结点。u这种策略完美分类训练数据，u但是当训练数据不能覆盖真实数据分布时，就会过度拟合。u只要适度保证叶结点的纯净度，适度保证对训练样本的正确分类能力就可以了。u当然叶结点纯净度也不能过低，过低则是欠学习。u我们应该在过度拟合与欠学习之间寻求合理的平衡。u即，在结点还可以进一步划分的时候，可根据预先设定的准则停止对其划分，并将其设置为叶结点。44确定叶节点u将数据样本集合分为训练集与测试集。u根据训
17、练集构建决策树，每展开一层子结点，并将其设为叶结点，就得到一棵决策树，然后采用测试集对所得决策树的分类性能进行统计。u重复上述过程，可以得到决策树在测试集上的学习曲线。u根据学习曲线，选择在测试集上性能最佳的决策树为最终的决策树。u在决策树开始训练之前，先设定一个阈值作为终止学习的条件。u在学习过程中如果结点满足了终止条件就停止划分，作为叶结点。u终止条件可以选择为信息增益小于某阈值，或者结点中的数据占全体训练数据的比例小于某阈值等等。45叶结点的类别46ID3算法伪代码47ID3ID3算法特点 u也是一个关于现有属性的有限离散值函数的完整空间。u并未彻底地搜索整个空间，而是当遇到第一个可接受
18、的树时，就终止了。uID3算法实际上用信息增益度量作启发式规则，指导爬山搜索。u优先选择较短的树，而不是较长的；u选择那些高信息增益高属性更靠近根结点的树。u优先选择短的树，即复杂度小的决策树，更符合奥坎姆剃刀原则。u也就是优先选择更简单的假设。uID3算法收敛到局部最优解，而不是全局最优。u可以对ID3算法得到的决策树进行修剪，增加某种形式的回溯，从而得到更优解。u使用全体数据的统计属性（信息增益）可以大大降低个别错误训练数据对学习结果的影响。u所以ID3算法可以很容易地扩展到处理含有噪声的训练数据。48u确定决策树增长的深度，避免过度拟合；u处理连续值的属性；u选择一个适当的属性筛选度量标
19、准；u处理属性值不完整的训练数据；u处理不同代价的属性；u提高计算效率。496.2.3 6.2.3 决策树决策树学习的常见问题学习的常见问题过度拟合问题u给定一个假设空间H和一个训练数据集D。对于一个假设h（hH），如果存在其它的假设h（hH），使得在训练数据集D上h的错误率小于h的错误率，但是在全体可能数据集合上h的错误率大于h的错误率。u那么假设h就过度拟合（Overfit）了训练数据D。50过度拟合问题u当模型遇到非训练数据集中的数据时，干扰模型的判断结果，降低了最终精度。u严重影响模型的泛化能力，降低模型的实用性能。u决策树结点过多，分支过深，u对训练数据可以完美分类，u但是对于非训练
20、数据则精度下降。51解决过度拟合问题u及早停止树增长在完美分类训练数据之前就终止学习。u后修剪法先允许树过度拟合数据，然后对过度拟合的树进行修剪 52决策树的修剪u第一步 从训练数据学习决策树，允许过度拟合。u第二步 将决策树转化为等价的规则集合。从根结点到叶子结点的一条路径就是一条规则。u第三步 对每一条规则，如果删除该规则中的一个前件不会降低该规则的估计精度，则可删此前件。u第四步 按照修剪后规则的估计精度对所有规则排序，最后按照此顺序来应用规则进行分类。53信息增益度量的问题u特别是当某属性可能值的数目大大多于类别数目时，该属性就会有很大的信息增益。u例如天气预报的训练数据中包含日期属性
21、。u因为太多的可能值把训练数据分割成了非常小的空间。u在每一个小空间内，数据都非常纯净，甚至数据完全一致，熵为0。u这样与未分割之前比，信息增益必然非常大。54增益比率（Gain RatioGain Ratio）度量u在信息增益度量的基础上加一个惩罚项来抑制可能值太多的属性 u对于可能值比较多的属性，由于其分裂信息也比较大，所以最终的增益比率反而可能减小。u但是当分裂信息过小，增益比率会过大，甚至无定义。55MantarasMantaras基于距离的度量u对于数据集假设存在一个理想划分，使得每一个数据都被正确分类。u那么我们定义一个距离度量其它划分到这个理想划分之间的差距。u于是距离越小的划分
22、自然是越好的划分 56MantarasMantaras基于距离的度量u其中P(AiBj)表示一个数据既在划分A中属于Ai类，又在划分B中属于Bj类的概率。57MantarasMantaras基于距离的度量不会偏向可能值较多的属性；也不会出现增益比率度量的缺陷。58u三个臭皮匠顶个诸葛亮u采用组合(Ensemble)策略，将多个基本算法组合使用每个基算法单独预测，最后的结论由全部基算法进行投票（用于分类问题）；或者求平均（包括加权平均，用于回归问题）。u使用多颗树进行单独预测，最后的结论由这些树预测结果的组合共同来决定u每个基分类器可以很弱，但最后组合的结果通常很强据测试，随机森林和支持向量机的
23、分类能力分别为第一和第二。M.Fernndez-Delgado,et al.,Journal of Machine Learning Research.15(2014)3133-31816.2.4 6.2.4 随机森林算法随机森林算法u把有限个性能不是很好的学习模型组合在一起，达到提高整体模型泛化能力的目的。u单个学习模型称之为基模型。u基模型之间应该具有差异性。显然，重复几个性能相同的学习模型不会提升学习结果。u每个基模型的分类精度必须大于0.5，即其泛化能力要略优于随机猜测u如何构建具有差异性的基模型；u如何整合多个基模型的学习结果。集成学习集成学习u在原有数据集上采用抽样技术获得多个训练
24、数据集，从而生成多个差异性基模型u主要有Bagging方法和Boosting方法u对原数据集进行有放回的采样构建出大小和原数据集D一样的新数据集D1，D2，D3；u用这些新的数据集分别训练多个基模型H1，H2，H3u是一个迭代过程，不断建立新模型并强调上一个模型中被错误分类的样本，再将这些模型组合起来u刚开始训练的时候，每一个训练数据赋有相等权重。u每次训练后，对分类错误的训练数据赋以较大权重。u也就是让学习模型在每次学习以后更注意学错的样本，从而得到多个基模型u例如，Adaboost算法、梯度提升决策树（Gradient Boost Decision Tree，GBDT）算法、XGBoost
25、（Extreme Gradient Boosting）算法等集成学习u在训练数据的不同特征子集上分别进行训练，从而构建出具有差异性的基模型。u一般采用随机子空间，少量余留法（抽取最重要的一些特征），遗传算法等u改变一个算法的参数来生成有差异性的同质基模型。u例如改变神经网络的拓扑结构就可以构建出不同的基模型集成学习u可以用一个学习模型来自动学习组合参数，u也可以采用人工固定的组合策略u指训练一个学习模型用于组合其他各个基模型。u把训练好的各个基模型的输出作为输入来训练一个另外一个模型，以得到最终输出u线性组合模型u逻辑回归（Logistic Regression）法u简单投票法u概率法，例如S
26、oftmax层u简单平均法u加权平均法u代数法集成学习u实质是对决策树算法的一种改进，u将多个决策树合并在一起，每棵树的建立依赖于一个独立抽取的样品，u森林中的每棵树具有相同的分布，分类误差取决于每一棵树的分类能力和它们之间的相关性。u单棵树的分类能力可能很小，但通过随机产生大量决策树，然后统计每一棵树的分类结果，从而选择最可能的分类随机森林算法随机森林算法训练样本集S.SKS2S1.决策树模型K决策树模型2决策树模型1.决策树模型1产生的分类结果DK决策树模型1产生的分类结果D2决策树模型1产生的分类结果D1RF模型产生的最优分类结果简单投票机制随机森林算法的核心u“随机”是其核心灵魂，u“
27、森林”只是一种简单的组合方式而已。u随机性是为了保证各个基算法模型之间的相互独立，从而提升组合后的精度。u数据的随机选取每颗树都独立随机地在原有数据上进行有放回的抽样独立随机抽样保证了每颗树学习到的数据侧重点不一样u待选特征的随机选取随机选取N个特征，选择最好的属性进行分裂或者在N个最好的分裂特征中，随机选择一个进行分裂随机森林算法的特点u两层随机性的引入，使得随机森林不容易陷入过拟合，并且具有很好的抗噪声能力u具有天然的并行性，易于并行化实现，适用于大数据u能够计算特征的重要性，可用于数据降维、特征选择u结果的可解释性不如决策树u在大数据环境下，随着森林中树的增加，最后生成的模型可能过大，耗用内存较大课下阅读uGBDT（Gradient Boost Decision Tree）算法uXGBoost（Extreme Gradient Boosting）算法u讲述对比二者的联系与区别待续待续