关于增量学习算法

增量学习的概念数据挖掘过程面对的一个重要问题是不断演化的新数据。至关重要的是,现有的分类和聚类方法要以这样一种方式解决这个问题：分类器不断的适应它，这里我们就需要增量学习；一种随着新数据的发生这个过程也要跟着发生变化的学习。对大批量数据集（如商场销售记录、多媒体数据）进行处理时，如果将新增样本与已有样本合并后处理，一方面会增加学习的难度，另一方面也因样本集过大而消耗过多的时间和存储空间。一个有效的解决方法是将新增样本集分别训练，并随着样本集的积累逐步提高学习精度，这就是增量学习的概念。增量学习可以就新增加的知识以及演化成新的类或一个聚类而言，它甚至可以合并或重组这些类。增量学习已经成功的应用到了许多分类问题，特别是在商业领域中增量学习的过程将有助于做出重大决策。增量学习就数据集而言是有选择性的，同时使用自适应和动态的有能力根据目前看到的做出正确的决策。考虑决策的影响，精度同样应该被考虑。摘要具有增量学习功能的数据分类技术正逐渐成为当前信息处理的关键技术之一。与传统的数据分类技术相比，增量学习分类技术具有显著的优越性。这主要表现在两个方面：一方面由于其无需保存历史数据，从而减少存储空间的占用；另一方面增量学习在当前的样本训练中充分利用了历史的训练结果，从而显著地减少了后续训练的时间。随着增量学习在数据挖掘应用领域的逐渐发展，实质上，增量学习算法领先一步发展变得极其重要。无标号数据的巨大增长已经使增量学习产生了一个大的飞跃。从BI应用到图像分类,从分析到预测,每个领域都需要学习和更新。增量学习在开拓新领域的同时可以进行知识积累。研究背景随着信息时代的到来，特别是随网络迅猛发展而出现的“信息爆炸”问题，使得传统的信息挖掘，知识获取技术面临极大的挑战。图灵奖获得者JimGray提出了一个新的经验定律：网络环境下每18个月产生的数据量等于有史以来数据量之和。美国加利福尼亚大学伯克利分校研究人员的一项新研究发现：在1999年到2002年这3年间，世界范围内信息生产量以平均每年30%左右的速度递增，也就是说，在过去3年中，全球新生产出的信息量就翻了一番。2002年中，全球由纸张、胶片以及磁、光存储介质所记录的信息生产总量达到5万亿兆字节，如果以馆藏1900万册书籍和其他印刷出版物的美国国会图书馆为标准，5万亿兆字节信息量足以填满50万座美国国会图书馆。同时随着网络的发展,许多应用领域获取新的数据变得很容易。但是对于传统的批量学习技术来说,如何从日益增加的新数据中得到有用信息是一个难题。随着数据规模的不断增加,对时间和空间的需求也会迅速增加,最终会导致学习的速度赶不上数据更新的速度。机器学习是一个解决此问题的有效方法。然而传统的机器学习是批量学习方式,需要在进行学习之前,准备好所有的数据。为了能满足在线学习的需求,需要抛弃以前的学习结果,重新训练和学习,这对时间和空间的需求都很高,因此,迫切需要研究增量学习方法,可以渐进的进行知识更新,且能修正和加强以前的知识,使得更新后的知识能适应新增加的数据。一方面，我们拥有的数据极大丰富，其间蕴含的信息和知识具有很大的潜在价值；另一方面，信息的更新速度也达到了令人吃惊的地步。因此，具有增量学习功能的数据分类技术，正逐渐成为当前信息处理的关键技术之一。与传统的数据分类技术相比，增量学习分类技术具有显著的优越性，这主要表现在两个方面：一方面由于其无需保存历史数据，从而减少存储空间的占用；另一方面，由于其在新的训练中充分利用了历史的训练结果，从而显著地减少了后续训练的时间。增量学习技术（incrementallearningtechnique）是一种得到广泛应用的智能化数据挖掘与知识发现技术。其思想是当样本逐步积累时，学习精度也要随之提高。与传统学习技术相比，增量学习技术可以充分利用历史学习的结果，显著节省后继训练时间。一种机器学习方法是否具有良好的增量学习功能已经成为评价其性能优劣的重要标准之一。一般来说,增量学习主要有两方面的应用:一是用于数据库非常大的情形,例如Web日志记录;二是用于流数据,因为这些数据随着时间在不断的变化,例如股票交易数据.另外在增量学习中,现有的增量学习算法[9]大多采用决策树和神经网络算法实现的,它们在不同程度上具有以下两方面的缺点:一方面由于缺乏对整个样本集期望风险的控制,算法易于对训练数据产生过量匹配;另一方面,由于缺乏对训练数据有选择的遗忘淘汰机制,在很大程度上影响了分类精度。目前无论是在国际还是国内，增量学习技术[18-23,27]的研究还处于刚起步阶段，还没有形成比较统一的体系和比较成熟的理论。尤其是对新增的样本中含有新增的特征以及新增特征的维数不同的情况下所做的工作较少。然而，随着特征采集的手段的不断多样化，如用于分类的特征是通过多个传感器共同获得，增量学习作为一种获取知识的有效手段，必定在知识经济的发展中扮演着重要的角色，需要对增量学习的方法和增量学习的应用进行更深更广的研究。研究现状和选题意义近几十年来,科学技术迅猛发展,信息技术广泛应用,人类产生的数据越来越多,人们获取数据能力也迅速提高,从制造业到服务业,从生物研究到空间探索,时刻产生大量数据,如何对已有的海量数据进行有效分析和科学研究是一个难题。为了有效管理和充分利用这些数据,有必要对它们进行学习和分类。机器学习是实现该目的的一个有效方法,也是人工智能的核心研究领域之一。基于数据的机器学习是现代智能技术中的重要方面，研究从观测数据（样本）出发寻找规律，利用这些规律对未来数据或无法观测的数据进行预测。迄今为止，关于机器学习还没有一种被共同接受的理论框架，关于其实现方法大致可以分为三种：第一种是经典的（参数）统计估计方法。包括模式识别、神经网络等在内，现有的机器学习方法共同的重要理论基础之一是统计学。参数方法正是基于传统统计学的，在这种方法中，它需要已知样本分布形式，这需要花费很大的代价。还有，传统统计学研究的是样本数目趋于无穷大时的渐近理论，现在学习方法也多是基于此假设。但在实际问题中，样本数往往是有限的，因此一些理论上很优秀的学习方法实际中表现却可能不尽人意。第二种方法是经验非线性方法，如人工神经网络(ANN)。这种方法利用已知样本建立非线性模型，克服了传统参数估计方法的困难。但是，这种方法缺乏一种统一的数学理论。与传统统计学相比，统计学习理论（StatisticalLearningTheory或SLT）是一种专门研究小样本情况下机器学习规律的理论。该理论针对小样本统计问题建立了一套新的理论体系，在这种体系下的统计推理规则不仅考虑了对渐近性能的要求，而且追求在现有有限信息的条件下得到最优结果。V.Vapnik等人从六、七十年代开始致力于此方面的研究，到九十年代中期，随着其理论的不断发展和成熟，也由于神经网络等学习方法在理论上缺乏实质性进展，统计学习理论开始受到越来越广泛的关注。统计学习理论是建立在一套较坚实的理论基础之上，为解决有限样本学习问题提供了一个统一的框架。它能将很多现有的方法纳入其中，有望帮助解决许多原来难以解决的问题（比如神经网络结构选择问题、局部极小点问题等）。然而在数据挖掘领域，分类学习在理论与实践应用中都获得了不少成就[12-15]。分类学习各方向都有不少成熟的数据预处理方法或算法被相继提出，如数据挖掘预处理阶段中，样本选择的方法有：Bootstrap[16]、上采样(Over-sampling)、下采样(Under-sampling)等；属性选择方法有：Filter、Wrapper方法以及基于信息增益或互信息(MutualInformation)的方法；学习算法方面有：贝叶斯算法、神经网络、决策树、K近邻、支持向量机(SupportVectorMachineSVM)[17]等。制作良好的强分类器的一般方法是训练一个没有被完全重新训练就不能嵌入新的数据的静态分类器。对所有数据训练强静态分类器的方法是既费时又昂贵的。在这种情况下,并不是以前训练的所有数据都是可用的,因为它已经有缺失或变得腐化。这使得它需要有一个分类器,可以逐步进化采取新颖的数据和类，它们同样可用并且不遗忘以前的训练数据。对于一个好的增量学习算法的分类器需要具有稳定性但是还要具有良好的可塑性[1]。一个完全稳定的分类器能够保存知识但是不能学习新的信息，而一个完全可塑的分类器可以学习提交给它的新的信息,但不能保留之前的知识。支持向量机比传统的机器学习方法[2]已经证明是稳定并且具有更好的模式识别性能的分类器,但稳定的支持向量机分类器遭受缺乏可塑性和倾向于灾难性遗忘现象[3,4]。因此要充分受益于支持向量机分类器的性能,增量学习方法需要被应用到标准支持向量机，将保持其稳定性但是还要使它具有可塑性。增量学习已以不同的方式应用见文献[5]。最简单的方法之一是增量学习存储的所有数据允许重新训练。在另一个极端是数据的训练、一个实例接一个实例,一个流行的在线学习。采用在线学习算法的方法已经实现增量学习但没有考虑所有的学习问题,特别是学习的新类[6、7]。对于一个分类器是增量应该满足以下标准:1.“它应该能够从新的数据学习更多的信息。2.用于训练现有的分类器它应该不需要访问原始数据。3.它应该保存先前获得的知识(也就是说,它不应该遭受灾难性的遗忘)。4.它应该能够适应新的类,可以引进新的数据”[6]。随着分类学习理论及应用在深度及广度上的不断探索，新的问题与挑战亦层出不穷。其中有一个问题比较突出：对于实际的任务，在分类学习各环节中有如此多的方法和算法可供选择，那应该如何衡量问题的难度和数据特性，然后依据这些信息在分类学习的各环节中选择适合的方法或方案，从而可以避免不必要的过多试探。在此背景下，数据复杂度衡量指标应运而生。它通过衡量数据各方面的特性来衡量对于某一领域问题进行分类学习的难易程度，从而对数据预处理、分类器选择等环节提供有效的指导信息。Bell实验室TKHo等人针对分类学习问题提出了数据几何复杂度衡量方法[19,20]。然而在数据挖掘过程中不可避免的会不断演化出新的数据，那么针对这种现象我们就需要增量学习。本文围绕分类学习中分类复杂度的衡量问题，在总结前人在这一领域的相关问题所得成果的基础上，作进一步的深化研究，提出了基于数据复杂度指标的增量学习算法。增量学习(IncrementalLearning)是指一个学习系统能不断地从新样本中学习新的知识,并能保存大部分以前已经学习到的知识。增量学习非常类似于人类自身的学习模式。因为人在成长过程中,每天学习和接收新的事物,学习是逐步进行的,而且,对已经学习到的知识,人类一般是不会遗忘的。因此,增量学习最早出现在心理学家对人类或者其它生物学习新事物过程的研究中。1962年,Coppock和Freund在Science上发表了关于增量学习的文章[28]。随着人工智能和机器学习的发展,人们幵发了很多机器学习算法。这些算法大部分都是批量学习(BatchLearning)模式,即假设在训练之前所有训练样本一次都可以得到,学习这些样本之后,学习过程就终止了,不再学习新的知识。然而在实际应用中,训练样本通常不可能一次全部得到,而是随着时间逐步得到的,并且样本反映的信息也可能随着时间产生了变化。如果新样本到达后要重新学习全部数据,需要消耗大量时间和空间,因此批量学习的算法不能满足这种需求。只有增量学习算法可以渐进的进行知识更新,且能修正和加强以前的知识,使得更新后的知识能适应新到达的数据,而不必重新对全部数据进行学习。增量学习降低了对时间和空间的需求,更能满足实际要求。虽然增量学习的研究已经有一定的历史,但由于不同的作者对其理解不同,至今增量学习也没有统一的定义。许多作者甚至将增量学习等同于在线学习(OnlineLearning)。这里,引用Robipolikar对增量学习算法的定义[29],即一个增量学习算法应同时具有以下特点:1)可以从新数据中学习新知识;2)以前已经处理过的数据不需要重复处理;3)每次只有一个训练观测样本被看到和学习;4)学习新知识的同时能保存以前学习到的大部分知识;5)