搜索
CHAP1机器学习吴海冰1120141807第2页Outline•机器学习的三个W（What，Why，How）•监督学习(SupervisedLearning)•非监督学习(UnsupervisedLearning)•强化学习（ReinforcementLearning）第3页PartI什么是机器学习•明斯基：“学习是我们头脑里有用的变化”。•西蒙：“学习是系统中的变化，这种变化使系统在重复同样工作或类似工作时，能够做得更好”。•那什么是机器学习呢？机器还会学习？•我们先来看两个小故事：什么是机器学习？•故事一：瑞雪兆丰年•我们中国有一句关于农业生产的古老谚语：瑞雪兆丰年。•就是说，如果前一年冬天下雪很大很多，那么第二年庄稼丰收的可能性比较大。•这条谚语是怎么来的呢？我们可以想象当时的情景：第一年冬天，下了很大的雪，第二年的收获季节，大丰收，亩产万斤。第二年冬天，没怎么下雪，第三年收获季节，庄稼颗粒无收，第三年冬天，大雪，第四年收获季节，又是大丰收，年复一年，若干年后的冬天，好大的雪，大家纷纷根据多年经验，来年肯定是丰收年。•这就是瑞雪兆丰年的故事。头年的瑞雪和来年的丰收，本是两个看起来并不相关的现象，但是智慧的农民伯伯通过几十年甚至几代人的经验，总结出了两个现象之间的规律。•现代的农业学家通过科学的分析，弄清了瑞雪兆丰年规律背后的本质原理。但是对于古代农民伯伯来说，知道规律就足够了，可以通过规律来为下一年的生产生活做出有效的调整。什么是机器学习•故事二：啤酒和尿布•上个世纪90年代。沃尔玛的超市管理人员分析销售数据时发现了一个令人难于理解的现象：在某些特定的情况下，“啤酒”与“尿布”两件看上去毫无关系的商品会经常出现在同一个购物篮中，经过后续调查发现，这种现象出现在年轻的父亲身上。在美国有婴儿的家庭中，一般是母亲在家中照看婴儿，年轻的父亲前去超市购买尿布。父亲在购买尿布的同时，往往会顺便为自己购买啤酒，这样就会出现啤酒与尿布这两件看上去不相干的商品经常会出现在同一个购物篮的现象。沃尔玛发现了这一独特的现象，开始在卖场尝试将啤酒与尿布摆放在相同的区域，让年轻的父亲可以同时找到这两件商品，并很快地完成购物；这就是沃尔玛啤酒和尿布的故事。•顾客购买啤酒的行为和顾客购买尿布的行为，原本是两个看起来没什么关联的现象。但是沃尔玛的技术专家以大量的用户购物数据为样本，通过先进的算法，最终寻找到了两者之间的重要关联和规律。什么是机器学习多年的冬天降雪和收获情况长年劳动经验总结假设模型沃尔玛顾客购物情况Apriori啤酒和尿布的关联TrainingSetLearningalgorithm新一年的降雪情况Training预测来年收获情况回归Regression什么是机器学习•这两个故事与机器学习有什么关系呢？•这两个故事的共同点是，都是把散乱的现象归纳成一定规律，然后为人所用。区别是，一个是劳动经验的总结，对新的现象给予结果预测。一个使用了计算机程序，是对于相关性的挖掘。•机器学习的概念大体如此。机器学习属于人工智能领域的一部分，其核心思想是让计算机程序随着数据样本积累，自动获得精确的判断和归纳能力。在啤酒尿布的故事中，沃尔玛所使用的是一种叫做Apriori的算法，用来挖掘关联规则的频繁项集。简单来说，就是寻找数据集合内在的联系。机器怎么学习EnvironmentPerceptionEvaluationPerformanceLearning第9页PartII监督学习•记忆学习•决策树学习•贝叶斯学习2.1记忆学习•最简单的监督学习方式•定义：保存问题的解，当再次遇见这个问题时，直接检索答案•需要权衡保存的代价和计算的代价•只有它的检索时间小于它的重新计算时间，记忆学习才有价值记忆学习的典型代表塞缪尔的西洋跳棋程序该程序用极大极小搜索算法来选择对应当前棋局的最佳走法，这就相当于完成了执行机构与评价机构的工作。而其学习机构则记忆当前棋局和对应的通过极大极小过程所获得的倒推值。这样，在下棋过程中，只要碰到过去出现过的棋局，就可以直接利用原来记住的通过向前搜索所获得的倒推值，而不是通过静态评估所获得的倒推值来决定最佳走步。这就相当于扩大了博弈子树的搜索深度，因而有更好的结果什么是监督学习•定义：对具有概念标记（分类）的训练样本进行学习，以尽可能对训练样本集外的数据进行标记（分类）预测。这里，所有的标记（分类）是已知的。•Learnafunctionfromexamples(x,f(x))•找到一个h约等于f•Twoproblems:•怎么定义函数形式•怎么优化函数参数甚至结构2.3决策树学习•1、它是一种逼近离散值函数的学习方法，对噪声数据有很好的健硕性，并且能用于学习规则。•2、非叶子节点对应数据属性，叶子节点对应数据类别，也代表一种决策结果，从根节点到叶子节点的路径则对应一条分类(决策规则)•3、决策树学习的主要任务：根据训练数据形成一棵相应的决策树，以对未来数据进行有效的分类基本决策树生成算法(ID3算法)•基本思想：•自顶向上的贪婪算法，从根节点开始，递归地用所选属性对数据进行分类，直到明确的类别信息，或没有供选择的属性为止。在ID3算法中，属性值需为离散值，如果是连续数据，则需要离散化决策树剪枝•ID3算法存在的最大问题是过度学习问题，或称过度拟合问题。•解决过度拟合问题的基本思路：通过剪枝降低树的复杂性，从而减小对训练数据的过度拟合，提高对未知数据的分类精度。有两种途径：•预先剪枝：在数的生成过程中根据一定的准则来决定是否停止树的扩展•后剪枝：待决策树完全生成后再进行剪枝•最小描述长度准则MDL（判断是否进行剪枝）•用奥坎姆剃刀原则来概括，即“如无必要。勿增实体”，表示在满足分类性能的要求的前提下，应该尽量选择结构简单的决策树•使下面两项编码长度之和最小•1）编码该决策树的比特树•2）编码例外数据（不能被该决策树解释的数据）所需要的比特数基于MDL的决策树剪枝过程•选择最小描述长度代替信息增益，作为树生成时选择属性的依据，使得每次树扩展时总的“树+例外数据”描述长度增加最小。•待树生成后，再进行自下而上的剪枝，知道继续剪枝不能减少“树+例外数据”描述长度为止2.4贝叶斯学习•是一种基于贝叶斯法则的统计学习方法•贝叶斯法则：•P(h|D)=P(D,h)/P(D)=P(D|h)P(h)/P(D)其中P(h)为先验概率，P(h|D)为后验概率，P(D|h)为类条件概率•极大后验概率(MAP)：在决策时，优先选择后验概率值大的结论•我们不必知道准确的后验概率值，只需关心其相对大小hPhDPDPhPhDPDhPhhhhMAPmaxargmaxargminarg贝叶斯学习•主要目标：类条件概率P(D|h)和先验概率P(h)•对于先验概率，两种处理方法：•1）假设各事件出现的可能性一样•2）统计各事件在训练数据出现的概率•如何学习类条件概率•NaïveBayesianClassifiers(NBC)朴素贝叶斯分类器•BayesianBeliefNetwork(BBN)贝叶斯信念网•GaussianMixtureModel(GMM)高斯混合模型朴素贝叶斯分类器（NBC）•在NBC中，假设数据向量中各分量相互独立，从而将高维数据分布转化为若干一维数据分布进行处理•朴素贝叶斯分类器是基于独立假设的，即假设样本每个特征与其他特征都不相关。•P(di|h)可通过统计训练数据中各分量取值的频率来实现，从而完成NBC的学习任务。iinhdPhddPhDP,,1朴素贝叶斯分类器（NBC）•样本修正•如果一个给定的类和特征值在训练集中没有一起出现过，那么基于频率的估计下该概率将为0。这将是一个问题。因为与其他概率相乘时将会把其他概率的信息统统去除。所以常常要求要对每个小类样本的概率估计进行修正，以保证不会出现有为0的概率出现。PartIII非监督学习•数据之间与聚类之间的相似性•计算方法•划分聚类•K-均值算法•K-中心点算法•层次聚类•BIRCH•CURE•CHEMELEON3.1聚类分析•什么是聚类？•1.一种非监督学习方法•2.根据数据之间的相似性，对数据集进行分组或分类，分类后的数据集称为簇。•3.利用聚类结果，可以提取数据集中隐含的信息，对未来数据进行预测和分类。•聚类分析可以干啥？•数据挖掘，模式识别，图像处理，经济预测等。•从机器学习的角度看，神经网络部分介绍的自组织特征映射网就是一种聚类分析方法。聚类分析两个基本问题1、数据相似性度量方法2、聚类策略数据相似性度量方法•1、连续数据的相似性度量•1）连续数据是相应数据控件中的点或向量，点之间的距离越近，表示数据相似性越大•2）距离•设X=(x1,x2,……,xn)，Y=(y1,y2,……,yn)为两个n维数据向量，Z表示任意n维数据向量，则X和Y的距离度量d(X,Y)应满足如下距离公理•(1)d(X,Y)=0(2)1)d(X,Y)=0(3)d(X,Y)=1)d(Y,X)•(4)1)d(X,Y)=d(X,Z)+d(Z,Y)•几种常用的距离：•欧几里得距离•城区距离•切比雪夫距离•闵可夫斯基距离•2、离散数据的相似性度量聚类策略•划分聚类•层次聚类3.2划分聚类•基本思想：•把数据集划分为K个子集，根据所定义的度量划分结果的优劣的准则，获得最优划分结果（K通常为人为设定）划分聚类过程是一种从所有可能划分中搜索最优划分的过程•Get全局最优聚类•盲目搜索(穷举算法)：问题规模不大时可使用。•启发式搜索•K-均值聚类算法•K-中心点聚类算法1、K-均值聚类算法•算法思想：使用均值向量代表每个簇，以数据与簇均值向量之间的距离作为数据到簇的距离，将它划分给最近的簇•过程：•Step1:从数据集中随机选择k个数据，作为初始簇的均值向量•Step2:对剩余的每个数据，根据其与各个簇均值向量的距离，将它划分给最近的簇•Step3:在新产生的k个簇的基础上，更新各个簇的均值向量•Step4:重复2，3，直到聚类稳定K-均值聚类算法•特征：•1.时间复杂度：O(tkn)•2.局部最优•3.缺点•需要实现给定k值•易受噪声点和初始向量影响K-中心点聚类算法•1.也叫PAM算法(PartitioningAroundMedoids)•2.使用中心点而不是均值来代表每个簇•3.四种情况的替换代价(假设i,t为原来两中心点,𝐶𝑗𝑖ℎ为用h代替i后,j付出的代价)•1)j本来属于i,用h代替i后，j属于t；𝐶𝑗𝑖ℎ=d(j,t)-d(j,i)•2)j本来属于i,用h代替i后，j属于h；𝐶𝑗𝑖ℎ=d(j,h)-d(j,i)•3)j本来属于t,用h代替i后，j属于t；𝐶𝑗𝑖ℎ=0•4)j本来属于t,用h代替i后，j属于h；𝐶𝑗𝑖ℎ=d(j,h)-d(j,t)•设其他非中心点个数为n,则总的替换代价为𝐶𝑖ℎ=𝐶𝑗𝑖ℎ𝑛𝑗=1•IF𝐶𝑖ℎ0,则进行替换，else不替换•4.过程•Step1:随机选择K个中心点数据•Step2:对每一对中心点h和中心点i,计算替换总代价𝐶𝑖ℎ•Step3:确定最小𝐶𝑖ℎ，if最小𝐶𝑖ℎ0,则相应的中心点i被非中心点h代替•Step4:重复2，3，直到min𝐶𝑖ℎ=0•Step5:将非中心点数据分配给距离其最近的中心点数据•5.局限性•K中心点算法对大数据集效率不高•6.改进的算法•CLARA:在抽样的数据子集上找到最优中心点•CLARANS:在CLARA基础上，进一步利用多次不同的抽样来改进CLARA3.3层次聚类•自下而上的凝聚层次聚类:首先将每个数据作为一类，然后逐步合并它们•自上而下的分裂层次聚类:首先将所有数据作为一类，然后逐步分解它们•1、类间距离和层次聚类的对应关系•最短距离法—单连接聚类方法（Single-Linkage）•最长距离法—全连接聚类方法（Complete-Linkage）•平均距离法—平均连接聚类方法（Average-Linkage）•2、局限