机器学习综述

机器学习分类和组合技术综述,汇报人：邵宏赡导师：严爱军2013.1.13,目录,1引言,2基本概念与学习系统,3机器学习主要策略,机器学习（ML）,4发展与展望,1引言,随着信息技术的发展,互联网数据及资源呈现海量特征。为了有效地管理和利用这些分布的海量信息,如何使机器具有认识问题和解决问题的能力,就是让机器如何更聪明、更具有人的智能,这就是机器学习。,ML基本概念,2基本概念与学习系统,机器学习是一门边缘学科,机器学习的一个形象描述,基本概念,研究一种算法1）提高它的性能（P）2）在某项任务中（T）3）利用一些经验（E）well-definedlearningtask:,目前在众多涉及计算机处理的技术应用中,机器学习在许多领域都取得了很大的进步,如用于人工智能、数据挖掘、自然语言处理、汉字识别、机器翻译、专家系统以及商业领域等。,机器学习应用,学习系统,学习系统,学习系统,机器学习的发展极为迅速,应用亦日益广泛,有很多优秀的学习算法,基本上可以分为基于符号学习和基于非符号学习(连接学习)。其中符号学习比较好的有机械式学习、指导式学习、示例学习、类比学习、基于解释的学习。,3机器学习主要策略,集成学习,最近邻算法,遗传算法,贝叶斯网络,决策树,八种主要学习策略,ML主要策略,支持向量机,EM算法,人工神经网络,按原理分类,支持向量机,决策树,决策树就是根据特征值对实例进行分类。决定树中的每个节点代表待分类实例的一个特征，每个分支代表该节点可以假设的一个值。,决策树模型,决策树,决策树可看作一个树状预测模型,它通过把实例从根节点排列到某个叶子节点来分类实例,叶子节点即为实例所属的分类。决策树的核心问题是选择分裂属性和决策树的剪枝。决策树的算法有很多,有ID3、C4.5、CART等等。这些算法均采用自顶向下的贪婪算法,每个节点选择分类效果最好的属性将节点分裂为2个或多个子结点,继续这一过程直到这棵树能准确地分类训练集,或所有属性都已被使用过。决定树最有用的特性之一是其可理解性。人们可以很容易地理解为什么一颗决策树把一个实例分类归类到一个特定的类。,决策树原理及优点,遗传算法,遗传算法（GA）是建立在自然选择和群体遗传学机理基础上的随机迭代和进化,具有广泛适用性的搜索方法,具有很强的全局优化搜索能力。它模拟了自然选择和自然遗传过程中发生的繁殖、交配和变异现象,根据适者生存、优胜劣汰的自然法则,利用遗传算子选择、交叉和变异逐代产生优选个体(即候选解),最终搜索到较优的个体。遗传算法本质上是基于自然进化原理提出的一种优化策略,在求解过程中,通过最好解的选择和彼此组合,则可以期望解的集合将会愈来愈好。遗传算法受到研究人员广泛重视是由于它采用随机搜索方法,其特点是几乎不需要所求问题的任何信息而仅需要目标函数的信息,不受搜索空间是否连续或可微的限制就可找到最优解,具有强的适应能力和便于并行计算。,遗传算法介绍,遗传算法,遗传算法是一种种群型操作,该操作以种群中的所有个体为对象。具体求解步骤如下:(1)参数编码(2)初始种群的生成(3)适应度函数的设计(4)选择复制(5)杂交(交叉)(6)变异GA适用于解决复杂的非线性和多维空间寻优问题。经典遗传算法的缺点是:有时计算时间过长,不能保证解是全局最优的。,遗传算法步骤及优缺点,最近邻算法,最近邻算法,贝叶斯网络,贝叶斯网络简介,贝叶斯网络分类及特点,贝叶斯网络,EM算法,EM算法,一个连接模型(神经网络)是由一些简单的类似神经元的单元以及单元间带权的连接组成。每个单元具有一个状态，这个状态是由与这个单元相连接的其他单元的输入决定的。连接学习通过使用各类例子来训练网络，产生网络的内部表示，并用来识别其他输入例子。学习主要表现在调整网络中的连接权,这种学习是非符号的，并且具有高度并行分布式处理的能力。一个人工神经网络是由大量神经元节点经广泛互连而组成的复杂网络拓扑，用于模拟人类进行知识和信息表示、存储和计算行为。人工神经网络学习的工作原理是：一个人工神经网络的工作由学习和使用两个非线性的过程组成。从本质上讲，人工神经网络学习是一种归纳学习，它通过对大量实例的反复运行，经过内部自适应过程不断修改权值分布，将网络稳定在一定的状态下。比较出名的网络模型和学习算法有单层感知器(Perceptron)、Hopfield网络、Boltzmann机和反向传播算法(BackPropagation，BP)。,人工神经网络,ANN原理,人工神经网络,是一个正数（为学习率），它决定梯度下降搜索的步长。一个较大的值使反向传播以更快的速度向目标权重配置移动，但同时也增加了不能达到这个目标的几率。,对于输出神元，是第j个神经元的期望输出对于内部（隐藏）神经元，,更新权重的一般规则是：,其中：,是第i个神经元的计算输出,反向传播ANN,权重计算,在神经网络中，因为缺乏问题的先验知识，往往需要经过大量费力费时的试验摸索才能确定合适的神经网络模型、算法以及参数设置，其应用效果完全取决于使用者的经验。基于此原因，于1990年，Hansen和Salamon开创性地提出了神经网络集成(NeuralNetworkEnsemble)方法。该技术来源于机器学习界目前极热门的Boosting方法，也已成为当前研究的热点。神经网络的另一大缺陷就是其典型的“黑箱性”，即训练好的神经网络学到的知识难以被人理解，神经网络集成又加深了这一缺陷。神经网络是基于经验风险最小化原则的学习算法,有一些固有的缺陷,比如层数和神经元个数难以确定,容易陷入局部极小,还有过学习现象,这些本身的缺陷在SVM算法中可以得到很好的解决。,人工神经网络,ANN缺陷,支持向量机是Vapnik等人提出的一类新型的机器学习算法。SVM算法的目的在于寻找一个超平面H(d)，该超平面可以将训练集中的数据分开，且与类域边界的沿垂直于该超平面方向的距离最大，故SVM法亦被称为最大边缘(MaximumMargin)算法。所谓最优超平面就是要求超平面不但能将两类正确分开，而且使分类间隔最大；使分类间隔最大实际上就是对模型推广能力的控制，这正是SVM的核心思想所在。总的来说,支持向量机就是首先通过用核函数定义的非线性变换将输入空间变换到一个高维空间,在这个空间中求(广义)最优分类面。SVMs分类函数形式上类似于一个神经网络,输出是中间节点的线性组合,每个中间节点对应一个支持向量,如图所示。选择不同的核函数就可以生成不同的支持向量机。常用的核包括:多项式核、高斯(径向基函数)核、二层神经网络核等。目前支持向量机的训练算法是以序贯最小最优化(SMO)为代表的，其中工作集的选择是实现SMO算法的关键。,支持向量机,SVM算法实现,基于统计学习理论的支持向量机（SVM）方法，与传统的基于经验风险最小化原则的学习方法不同，SVM基于结构风险最小化，能在训练误差和分类器容量之间达到一个较好的平衡,它具有全局最优、适应性强、推广能力强等优点。但是直到目前为止,支持向量机方法还存在一些问题，例如训练时间过长、核参数的选择等，成为限制支持向量机应用的瓶颈。,支持向量机,SVM模型及优缺点,集成学习,集成学习提出,集成学习（EnsembleLearning）始于Hansen和Salamon的开创性工作。他们研究发现，通过训练多个神经网络并将其结果按照一定的规则进行组合，就能显著提高整个学习系统的泛化性能。Schapire通过构造性方法提出Boosting算法，证明了这一点。集成学习通过训练和组合多个准确而有差异的分类器，提高了分类系统的泛化能力，成为近十年来机器学习领域最主要的研究方向之一。目前，国内外以神经网络、决策树等为基分类器的集成学习研究已经取得了很大的进展。,在分类时，采用投票的方式决定新样本属于哪一类。,集成学习示意图,集成学习,由于每个分类器的分类能力不同，在集成时，需要对所有分类器加权均，以决定分哪类。,集成学习构造,集成学习,基分类器的构造方法：1）采用不同训练样本集2）采用不同输入特征子集3）输出编码分解方法4）引入随机性5）多种方法相结合分类器的输出信息可以分为抽象层、排序层和度量层三个层次。基分类器的组合方法有：a）排序层组合方法b）抽象层组合方法c）度量层组合方法根据基分类器是否属于相同类型，可以分为同类分类器集成和异类分类器集成。根据基分类器是否由集成算法选择，可以分为面向选择（selection-oriented）和面向组合器（combiner-oriented）的集成。现在已经有很多集成学习算法,比如:Bagging算法、Boosting算法、Arcing算法、RandomForest算法等等。,机器学习的研究就是希望计算机能像人类那样具有从现实世界获取