机器学习综述

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