（计算机软件与理论专业论文）数据变化时分类器的更新问题研究.pdf

c l a s s i fi c a t i o n i s a n i m p o r t a n t b r a n c h o f d a t a m i n i n g . t h e fi rs t s t e p o f c l a s s i fi c a t i o n i s t o l e a rn a m o d e l fr o m t w in in g d a t a , a n d t h e s e c o n d i s t o p r e d i c t th e c l a s s l a b e l f o r t h e s a m p l e w h o s e c l a s s a t t r i b u t e i s u n k n o w n . f o r e a c h c la s s i f i c a t io n m o d e l , i t i s d e m a n d t h a t t h e a s s u m p t i o n t h a t th e t r a i n i n g d a t a s e t a n d t h e c l a s s i fi e d d a t a s e t s h o u l d b e g e n e r a t e d fr o m t h e i n d e p e n d e n t a n d i d e n t i c a l d i s t r i b u t io n m u s t b e s a t i s fi e d . 加s o m e p r o b l e m , h o w e v e r , d a t a c h a n g e s s o m e t i m e s w h i c h l e a d s to t h a t t h e a s s u m p t i o n m e n ti o n e d a b o v e w i ll n o t b e s a t i s fi 喊 a n d t h e c l a s s i fi e r i s n o t a b l e t o p扮r e fl e c t t h e d a t a d i s t r i b u t io n a s a re s u l t , t h e c l a s s i fi e r m u s t b e u p d a t e d . i t i s 州t o s t r a i g h t f o r w a r d t h a t r e tr a i n t h e c l a s s i fi c a t io n m o d e l w i t h a ll t r a i n i n g s a m p l e s i n o r d e r t o u p d a t e t h e o u t - o f - d a t e c l a s s i fi e r . i n s o m e p r a c t i c a l a p p li c a t io n s , p a rt i c u l a r l y 运o n l i n e c l a s s i f i c a t i o n a p p li c a t i o n s , h o w e v e r , t h e a m o u n t o f d a t a i s s o h u g e t h a t i t i s t o o c o s t iv e i n t i m e a n d s p a c e t o u p d a t e t h e c l a s s i f i e r i n s u c h m a n n e r . c o n s e q u e n t l y i t i s n e c e s s a ry t o fi n d a n e ff i c i e n t m e t h o d t o u p d a t e t h e c l a s s i fi e r w h e n d a t a c h a n g e . s t a t i s t i c a l l e a rn i n g t h e o ry o r s l t i s a s m a l】 一 p i e s t a t i s t i c s 勿v a p n i k e t 吐， w h i c h c o n c e r n s m a i n l y t h e m a c h i n e l e a r n i n g p r in c ip l e w h e n s a m p l e s a r e l i m i t e d . s l t p ro v i d e s a n e w fr a m e w o r k f o r t h e g e n e r a l l e a rn i n g p r o b l e m . s u p p o rt v e c t o r m a c h i ne a n d s u p p o rt v e c t o r d a t a d e s c r i p t i o n 。 t w o n o v e l c l a s s i fi c a t i o n m e th o d s w h i c h a re b a s e d u p o n s l t t h e y h a v e s h o w n s o m e a d v a n t a g e s o v e r t r a d it i o n a l m e th o d s . t o a t t a c k t h e p r o b l e m m e n t i o n e d a b o v e , t h i s t h e s i s p r o p o s e s m e t h o d s f o r u p d a t i n g s v m a n d s v d d w h e n n e w t r a in i n g s a m p l e s e m e r g e o r a t t ri b u t e v a l u e s o f to 血 面g d a t a c h a n g e . i n o r d e r t o u p d a t e s v d d m o d e l w h e n n e w t r a inin g s a m p l e s e m e r g e , t h i s p a p e r c o m b i n e s s u p p o rt v e c t o r s o f t h e t r a i n e d m o d 俄w h i c h r e p r e s e n t h i s to r ic a l d a t a , w i t h t h e n e w l y e m e r g i n g s a m p l e s t o f o r m t h e t r a in in g s e t w h i c h i s u s e d t o r e tr a i n t h e c l a s s i fi e r . a t t h e m e a n t i m e , t h i s m e th o d a l s o c a n b e u s e d t o d e a l w i 山l a r g e - s c a le t r a i n i n g p ro b l e m . f o r t h e p r o b l e m t h a t t h e a t t r i b u t e v a l u e s o f t r a in i n g d a t a c h a n g e , t h i s p a p e r p ro p o s e s f u - s v m a n d f u - s v d d , t h e f o r m e r i s u s e d t o u p d a t e s v m c la s s i f i e r a n d ab s tr a c t t h e l a t t e r i s u s e d t o u p d a t e s v d d c l a s s i fi e r . b o t h o f t h e s e t w o m e th o d s u s e t h e c h a n g e d s a m p l e s t h a t a ff e c t t h e c l a s s b o r d e r a n d u n c h a n g e d s u p p o rt v e c to r s t o r e t r a i n t h e c l a s s i fi e r mo d e l . t h e t h r e e m e th o d s t h i s p a p e r h a s p r o p o s e s i s a p p r o x i m a t e , h o w e v e r , e x p e r im e n t s o n u c i s t a n d a r d d a t a s e t r e v e a l t h a t a m u c h b e t t e r p e r f o r m a n c e 运u p d a t i n g e ff i c i e n c y i s g a i n e d w i 山v e ry li t t l e c l a s s i fi c a t i o n a c c u r a c y l o s t , w h i c h i s v e ry i m p o r t a n t t o o n l i n e u p d a t i n g o f c l a s s i fi e r s . k e y w o r d s : d a t a m i n i n g , c l a s s i fi c a t i o n , s t a t i s t i c a l l e a r n i n g t h e o ry , s u p p o r t v e c t o r m a c h i n e , s u p p o r t v ect o r d a ta d e s c r i p t i o n , c l a s s i fi e r u p d a t i n g m 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、 保存、使用学位论文的规定， 同意如下各项内容:按照学校要求提交学位论文的印刷本和电子版 本; 学校有权保存学位论文的印 刷本和电 子版，并采用影印、缩印、 扫描、 数字化或其它手段保存论文; 学校有权提供目 录检索以 及提供 本学位论文全文或者部分的阅览服务; 学校有权按有关规定向国 家有 关部门 或者机构送交论文的复印件和电 子版; 在不以 赢利为目 的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学 位 论 文 作 者 签 名 : ; 二 每 z s o 7 年了 月/ t 日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名: 学 ” “ 作 者 ， 名 : 沁 峰 解密 时 间:年月口 各密级的最长保密年限及书写格式规定如下: 内部5 年 ( 最长5 年，可少于5 年) 秘密1 0 年 ( 最长1 0 年，可少于1 0 年) 机密2 0 年 ( 最长2 0 年， 可少于2 0 年) 南开大学学位论文原创性声明 本人郑重声明: 所呈交的学位论文， 是本人在导师指导下， 进行 研究工作所取得的成果。 除文中己 经注明引用的内 容外， 本学位论文 的研究成果不包含任何他人创作的、 已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体， 均己 在文中以明确方式标明。 本学位论文原创性声明的法律责任 由本人承担。 学 位 论 文 作 者 签 名 : 外 咚 - 7 年t月才日 第一章 绪论 第一章 绪论 1 . 1引言 随 着计算机技术、网 络技术和信息技术的发展， 人们生产和搜集数据的能 力大幅度提高.但是面对如此大量的数据，人们却很难从中找到需要的知识， 大量的 数 据形 成了 一 座座“ 信息 坟墓” . 数 据 挖掘 ( d a t a m in i n g ) 技 术正 是在这 种背景下产生的，它是从大量的数据中抽取出隐含的、未知的、潜在有用的知 识， 以 便 对发 展 趋势 进 行 预 测 1-3 1 . 分 类( c la s s i fi c a t io n ) 问 题是 数 据 挖 掘 领 域 一 个重要的 研究分支，其过程是基于对训练数据集 ( 即其类标记已 知的数据对象) 的分析来预测标记未知的对象。具体地讲，分类方法能够根据对象的数据特征 来判定其类别。而如何从训练数据集 ( 对象的特征及所属类别的数据集合)中 学习得到分类所用的模型被称为分类器的学习，这是分类研究的主要问 题。 分类任务中的分类模型都基于 “ 独立同分布” 这一前提假设，即用于训练 分类器的数据集与待分数据都是由同一分布独立生成的。但是在更多的实际应 用中，数据的分布不是静止不变的，而是呈现出随时间的推移而变化的特点。 例如，在客户等级划分、资信评估、网络入侵检测、垃圾邮件检测、博客空间 挖掘等应用中，数据分布会随着时间推移而变化。数据的变化有很多种情况， 其中 有两种典型的情况: 1 .当分类器模型的训练结束后，又出现了新的训练样本; 2 .训练样本数量不变， 但某些训练样本属性的取值情况发生了 变化。 当数据发生变化时，用发生变化之前的训练数据训练得到的分类器模型将 不能正确描述数据分布的特征，这样的分类器模型是无效的。因此，当数据变 化时，必须对现有的分类器模型进行更新。 在数据发生变化之后，可以通过使用所有训练样本重新训练分类器的方法 更新分类器模型。但在实际应用中，训练数据集的规模往往非常大，使用所有 的训练数据重新训练分类器模型是一个非常耗时的过程，特别是在某些数据更 新十分频繁的应用中， 往往在一次更新过程刚结束， 训练数据的 分步情况又发 生了 变化，分类器模型的 更新落后于训练数据分布的变化将影响了解决实际问 题的效果;另一方面，对于一些分类器模型而言，由于数据量太大，不能将所 第一章 绪论 有训练数据都载入到内 存中 进行计算， 使用所有训练样本更新分类器的 方法是 行不通的。对于在线分类系统，上述问题显得更加突出。 因此， 对在数据分布变化后，找到一种根据变化情况对己有分类模型进行 快速、有效、可行的更新方法是十分必要的，该问 题的研究将从某些角度提高 分类理论方法的实用性，从而推动分类方法在解决现实问 题过程中的 应用。 1 . 2 致据挖掘中的分类问题 1 .2 . 1 数据挖掘概念和应用 数据 挖掘 ( d a t a m i n i n g ) 指的 是从 大型数据库或数 据仓 库中 提取人们感兴 趣的知识，这些知识是隐含的、事先未知的、潜在的有用信息。这个定义包括 以 下含义:数据源必须是真实的、大量的、 含噪声的:发现的是用户感兴趣的 知识;发现的知识要可接受、可理解、可运用，最好能用自 然语言表达发现结 果:并不是要求发现放之四海皆准的知识，也不是要去发现崭新的自 然科学定 理和纯数学公式，更不是什么机器定理证明，所有发现的知识都是相对的，是 有特定前提和约束条件、面向特定领域的。 数据挖掘即知识发现 ( k d d ) 的主要过程如图1 - 1 所示， 主要由四 个部分组 成: 1 .数据清理 ( 消除噪音或不一致数据) 和集成 ( 多种数据源可以组合在一 起) 2 .数据选择 ( 从数据库中提取与分析任务相关的数据) 和变换 ( 数据变换 或统一成适合挖掘的形式) 3 .数据挖掘 ( 基本步骤， 使用智能 方法提取数据模式) 4 .模式评估 ( 根据某种兴趣度度量， 识别提供知识的真正有趣的 模式) 和 知识表示 ( 使用可视化和知识表示技术，向用户提供挖掘的知识) 第一章 绪论 、1i/ / .，.。奋月 r1，1:，幸 徽拐库 曰曰 二 : _ 生 一 理 吮 黔 me甲乡吐 诵f j i ll 二 :l ; : _一_ j-_ _一_ 一一， 图l l 知识发现过程模型 目前，在国外，数据挖掘技术及其相关的决策支持系统发展得很快，它们 在商业界，公共服务行业等众多行业被广泛应用，并快速、 直接的带来了吃 惊 的利润，同时也带动了这些行业的飞速发展。因此，有人称这项技术为二十世 纪影响人类的计算机方面的三大事件之一。 根据知识的 种类不同， 数据挖掘技术主要 有关联分析、分类和预测、聚类 分析、局外者分析和演变分析等几种。 1 .2 .2 分类问题简介 分类问题是数据挖掘领域的重要研究分支之一， 其过程是基于对训练数据 集 ( 即其类标记已 知的数据对象)的分析来预测标记未知的 对象。 分类问题具 体定义是: 对 于 给 定 的m 个 由 向 量 y e r 及 、 的 类 别 标 签y , e ( 1 , 2 . . .n 组 成 的 训 练 样 本 ( x i, y 1 ) i ( z 2 i y 2 ) , ., ( ii m + y m， 找 到 一 个 映 射 函 数 f : 侧- + 1 1 , 2 , .n 将 输 入 向 量 x 映 射到类别标 签r 上。 训练样本组成的集合称为训练数据集，映射函数通常被称为分类器模型或 分 类器3 7 4 1 1 5 11 。 如何 从训 练数 据集中学习 得到 分 类所用的 模型 被称为分 类器的 学习，这是分类问题研究的主要问题。 人们对分类学习理论的研究己经有很多年的历史，从二十世纪 5 0年代末 第一章 绪论 r o s e n b l a tt提出 感知 器 模型并 证明 其收 敛 性 7 1开始， 分别 经 历了 感知 器、 分 类器 学习理论的建立、神经网络、统计学习理论四个阶段。 从上世纪8 0 年代中期开 始， 对神经网 络的 研究和9 0 年代初至今对统 计学习理论的 研究使得分类研究步 入成熟期，其研究成果 也得到了广泛应用， 并在一些应用上取得了 很好的效果， 例如， 光学 字符识别( o c r ) 、 语音识别、 信息 检索 ( i n f o r m a t i o n r e tr i e v 成i r ) . 文本和图像的分类等。 统 计 学习 理 论 4 5 1 是 一 种专门 研究小 样 本 情况 下 机器学习理论规 律的 理 论。 v v a p n i k 等 人从二 十 世纪 六十年代便开 始了 对于 该理 论的 研究， 到二 十世纪 九 十年代中 期， 随着统计学习理论的不断发展完善， 它受到了 越来越广泛的重视。 以 统 计 学习 理论为 基 础发 展而来的 分 类方 法 一 一支持向 量 机( s v m) 4 1 以 及 支持 向 量数 据 描 述( s v d d ) 61 等 方法表现出 优 于已 有方 法的 性能， 对于 这 些方 法的 相关研究也成为了数据挖掘领域的一个研究重点。 1 . 3 教据变化时分类器的更新 数据变化的情况是复杂多样的，其中有两种典型的变化情况: 1 .类别情况不变，出现了新增训练样本，即出现了增量训练样本。 2 .类别情况不变， 一些训练样本的某些属性的取值发生了 变化， 这种变化 可能 会引 起样本类别属性的变化。 本文的研究内容是当数据发生这两种变化时分类器的更新方法。 当数据发生变化时，最直观的做法就是用所有训练数据重新对分类器进行 训练，当训练完成后，分类器的更新也就完成了。但是，在一些应用领域， 特 别是在商业决策等需要即时更新的在线分类的 应用中，这种做法不具有可行性， 其原因有二个:第一是实际应用中的训练数据量是十分巨大的，用所有的数据 重新训练分类器是非常耗时的过程，在重新训练分类器的这段时间里，使用失 效的分类器对类别属性未知的样本进行分类将出 现严重的错分情况，由 此带来 的损失将是非常大的;第二个原因是有时候不能将所有的数据一次都加载到内 存中进行计算，虽然计算机硬件的发展能 减少这种情况的发生， 但能够解决的 问 题的 规模始终是受到了 很大的限制， 这种限 制在增量样本的数据变化问 题中 显得尤为突出。 综上所述，对数据变化时，如何降低分时间开销和空间开销，快速、 准确、 第一章 绪论 有效地对分类器模型进行更新的研究是非常必要的。 1 .4 本文研究内容和组织结构 1 .4 . 1 主要研究内容 本文的 研究内 容主要分成两个部分， 第一部分是对支持向 量数据描述分类 器模型提出 一种出 现增量样本时的调整方法: 第二部分是对支持向 量机分类器 模型以 及支持向量数据描述分类器模型提出当训练数据属性值变化时的更新方 法。 1 .4 .2 研究思路 通过分析可以发现，当 数据发生 变化时， 更新后的分类模型与更新前的分 类器模型有着一定的关联性:第一，变化前后的训练数据集有一定的重复、数 据分布有一定的交益;第二，数据变化前训练所得的分类模型对变化后的数据 仍有一定的描述能力。因 此， 充分利用已 有的计算结果， 将其应用到分类器模 型的更新过程中，减少不必要的重复计算，能够减小更新过程的时间开销和空 间开销，提高分类器模型更新的效率。 对于s v m和s v d d分类模型， 支持向 量是非常重要的数据， 它们是位于类 别边界上的样本，直接决定了分类器模型的情况。支持向量是训练样本中最具 类别区分性的 样本，得到它们需要经过大量的计算，并且能 够直接体现数据的 分布信息，受此启发，在本文需要解决的分类器动态更新的问题中提出使用支 持向量代替原有的训练数据集的思路，以 减少更新模型的数据量，从而降低更 新模型的空间开销和时间开销。 1 .4 . 3 本文组织结构 本文第二章对相关工作进行综述。 在这一章中，首先介绍两种典型的数据 变化类型， 然后介绍数据变化时分类器更新方法的主要研究成果。 在 2 . 5节到 2 .7 节中，分别介绍统计学习理论以及由统计学习理论发展而来的支持向量机和 支持向量数据描述两种分类方法，这两种方法在某些方面的性能优于其他已 有 的分类方 法， 本文的 研究 就是针对这两种分类方法展开的。 第三章针对出 现新增训练样本后分类器的更新方法进行研究。 在本章中， 第一章 绪论 首先介绍两种s v m样本增量学习方法， 并对两种方法进行比 较。 通过对比， 本 文 采用s y e d 的 方法作为出 现新 增 训 练样本时s v m分 类模型 的 更 新方法. 基于 相同的思想，本章提出了 支持向 量数据描述的样本增量学习方法，用于出现新 增训练样本时s v d d模型的更新。在本章中，对支持向量数据描述的增量学习 方法结果的精确性，时间复杂度进行了详细的讨论。 第四章研究当训练数据集中某些样本的属性值发生变化后，支持向量机分 类器和支持向量数据描述分类器的更新方法。本文在这一章中，提出针对不同 变化情况，支持向量机和支持向 量数据描述两种分类器相应的 更新策略。 本文最后对研究工作进行总结，并提出进一步的研究方向。 第二章 相关工作综述 第二章 相关工作综述 z . ，引言 本文的研究工作得益于机器学习和数据挖掘领域中丰硕的研究成果，本章 将详细介绍与本文相关的 研究工作和成果。 在传统的分类方法中按照训练数据介入分类器训练过程方式的不同，可以 将分类器的训练分成批量学习和串行学习，前者在分类器训练开始便将所有训 练数据提供给训练算法，而后者则是逐条数据提供给分类器的训练算法。在分 类器的实际使用中，更多的 情况是供给分类器训练的数据是成块到来的，例如 时间序列数据、需要间隔一定时间补充的客户消费或资信数据等情况。此外， 还有一种情况是训练数据的数据量太大，以 至于不能一起被载入内 存进行计算， 需要分块解决。由 于分类器训练之初获取的训练数据很难反映所有可能情况， 因此，训练数据是随着新样本的标注而逐批提供的。这种在分类器训练完成之 后又提供新的训练样本集合的情况被称为增量。 分类器根据新增样本及其特征 对自 身分类模型进行更新和调整被称为分类器的增量学习。增量学习可以充分 利用分类模型中学习到的历史知识，并可缩短分类器对新增样本的适应时间。 目 前，分类器的 增量学习己 有很多成果。 按照 新增 样 本 变 化的 元素不同， 增量 可 分 为 样本 增量 和 类别 增量等情况11 1: 1 .样本增量是指在分类器训练后， 得到新的训练样本， 而这些新增样本所 属的类别都属于已有类别，即各类的条件概率发生了变化， 但类别集合 与属性集合均不变. 2 .类别增量是指新增训练样本所属的类别不同于已 有类别， 也就是说不仅 已 有各类的 类条 件概率发生了变化， 而且会引 入新增类的类条件概率。 因此，分类模型也会因为输出结构的变化而严重失效。 在这两种情况中， 大部分工作集中 在分类器的样本增量学习上。而关于分 类器的 类别 增量 工 作 只 有 很少 研究 成果 得出 i i i ，目 前发 现的 成果 有 19 - 1 0 1 基于数据的 机器学习 是现代智能技术中的重要方面. 研究从观测数据( 样本) 出发寻找规律， 利用这些规律对未来数据或无法观测的 数据进行预测。 包括模式 识别、神经网络等在内， 现有机器学习方法共同的重要理论基础之一是统计学。 第二章 相关工作综述 传统统计学研究的是样本数目 趋于无穷大时的渐近理论， 现有学习方法也多是基 于此假设. 但在实际问 题中， 样本数往往是 有限的， 因此一些理论上很优秀的学 习方法实际中表现却可能不尽人意. 与 传统 统计 学 相比， 统计 学习 理 论( s t a ti s ti c a l l e a rn i n g t h e o ry) 是 一种专门 研究 小 样 本情 况 下机器 学习 规 律的 理论. v . v a p n ik 等 人从 六、 七 十年 代开 始致 力于此方面研究，到九十年代中期，随着其理论的不断发展和成熟，也由于神 经网络等学习方法在理论上缺乏实质性进展，统计学习理论开始受到越来越广 泛的重视。统计学习理论建立在一套较坚实的理论基础之上，为解决有限样本 学习问题提供了 一个统一的框架。它能将很多现有方法纳入其中，有望帮助解 决许多 原来难以 解决的问 题( 比 如神经网 络结 构选择问 题、 局部极小点问 题等) ; 同时， 在这一理论基础上发展了一种新的 通用学习方法一一支持向量机( s u p p o r t v e c t o r m a c h i n e , s v m )， 它已 初步表 现出 很多 优于已 有方法的 性能 11 9 1 . 对支 持 向 量机 理论相关问 题的 研究已 经成为数 据 挖 掘领域的 一 个热点 13 9 a. 受支持向 量机的 启 发， t a x 和d u i n 等 人提出了 支持向 量 数据描 述( s u p p o rt v e c to r d a t a d e s c r i p ti o n , s v d d ) ， 该方法主 要用 于新奇 点 检 测， 有着很好的 性能。 本章的 2 .2节中，通过一个实际应用中的问题介绍数据变化的两种典型情 况:出现新增训练样本和训练数据属性值变化，当数据发生这两种变化时分类 器的更新方法是本文研究的内容。 在2 .3 和2 .4 节中，介绍了数据变化时分类器更新方法研究主要成果， 这些 成果主要集中在样本增量学习。 在2 .5 至2 .7 节中，分别介绍了统计学习方法以及基于该方法的分类器一 支持向 量机和支持向量数据描述。统计学习 方法及相关的分类器是当前数据挖 掘及机器学习领域的研究热点，与传统方法相比，它们具有一定的优越性， 本 文的研究内容，就是基于s v m和s v d d的更新方法展开的。 2 . 2 数据变化种类 在一些实际应用中，用于训练分类器模型的训练数据不是静止不变的，当 数据变化时， 用变化前的数据训练得到的分类器模型不能正确描述数据分布的 特征，这时分类器模型已 经失效，使用这样的分类器对类别属性未知的样本进 行分类是错误的，因此，当数据变化时需要对已经训练好的分类器模型进行更 第二章 相关工作综述 新。 为了形象的阐述问题，以下的讨论都基于一个来源于现实生活中的分类任 务: 信用卡客户信用等级评定。为了研究持卡人的消费习惯，从中发现有价值 的商业规律以获取更大的经营利益、规避商业风险，某银行对信用卡持有人建 立了详细的档案，对于每个客户，档案中记录着客户的姓名、年龄、职务、年 收入情况、汽车拥有情况、婚姻情况等个人信息，同时，银行根据持卡人的信 用情况将持卡人划分成 “ 金牌客户” 、 “ 银牌客户” 、 “ 普通客 户” 三个信用等级， 针对这三个信用等级的持卡人银行规定了不同的透支额度以 及还款期限。银行 根据持卡人的档案数据建立了 个一个分类器模型，希望当有人申 请信用卡时， 根据客户的个人情况使用训练好的分类器模型自 动、准确地确定申 请人的信用 等级。 但是持卡人的个人信息以 及信用状况不是静止不变的，随着时间的推移， 这些信息 ( 数据)发生了复杂的变化，其中两种典型的情况是: 1 .随着时间的推移， 该银行的信用卡客户越来越多， 银行建立的持卡人档 案不断增加。 2 .某些持卡人的个人信息发生了 变化，比如有些人的年收入增加了， 因而 具有了更强的消费能力， 需要提升他的信用等级; 又比如某些人年龄等 状况出现了变化， 但消费能力没有变化，不需要改变他的信用等级。 从上面的分析可以总结出两种典型的数据变化，它们分别是: 1 .类别情况不变，出 现了 新增训练样本，即出 现了增量训练样本。 2 .类别情况不变， 一些训练样本的某些属性的取值发生了变化， 这种变化 可能会引起样本类别属性的变化。 2 . 3 数据变化后分类器的更新 目 前对于数据变化时分类器调整问题的研究成果主要集中在分类器的样本 增量学习上，对于训练样本属性值变化时分类器模型的调整问题未见深入研究。 分类器的样本增量学习是指:当分类器学习好之后又获得了新的训练样本 时，分类器对自 身模型及参数的更新调整。其目的是在尽量继承已经学习到的 知识的同时， 能 够对新知 识 进 行学习 n n . 增量样本的 属性 集合 和类别集合都不 发生变化。 第二章 相关工作综述 在现实中，很多分类应用都要求分类器具有样本增量学习能力，因为，训 练样本很难一起提供， 而成块分批提供更为 普遍， 主要的 原因 有两点: 1 .对于时间序列数据和需要每隔一定时间补充数据的分类应用， 供给分类 器训练的数据是随时间成块到来的， 如客户消费数据、 网 络访问情况等 等。此外， 还有一些需要定期补充更新训练数据的情况，比如，新客户 的资信数据等。 2 .另外一种情况是训练数据的量太大， 以至于不能被一起载入内 存中进行 计算， 此时便需要将训练数据集分割成相对较小的块， 逐块学习。 对于 此种情况， 就要求分类器的学习具有知识压缩能力， 也就是可将训练数 据集中对分类起作用的计算结果或部分数据保存下来供未来训练使用， 而这部分结果的 存储尺寸要远小于训练数据集。 增量式学习是解决上述问题的有效途径，它能够通过充分利用先验信息求 解当 前的问 题 1 2 1 . 分类 器的 样本增量学习，目 前的 研究 成果 主 要集中 在神经网 络、决策树和支持向 量机等样本增量学习的研究中。 神经网络由于它的训练过程就是增量处理方式，即每条参与训练的样本可 以 逐个更新分类器的连接权值，当更新迭代到一定次数收敛后，便可以记住这 些训练样本，因此， 神经网络家族的分类器天生具有样本增量学习的能力，当 然这同它一开始便模拟人脑和神经系统有很大关系。 对于决策树分类器的 样本增量学习的研究成果有: s c h li m m e r 和 f i s h e r 于 1 9 8 6 年 提出 决策 树的 增 量 学习 算法ld 4 1 3 ， 该 算法使用 新 增数 据更 新决策树节 点中的信息增益，当分割属性没有变化时保留子树继续更新， 如果分割属性发 生变化，则丢弃子树。 此种方式虽可以实现决策树的增量学习， 但其不足在于 简单地丢弃分割属性发生 变化的子树， 浪费了 历史计算. 针对该问 题， u t g o ff 于1 9 8 9 年提出1 d 5 r 1a 1 算 法， 当 结点中 的 分 割属 性失 效 后， 如 果新的 分 割属性 出现在其历史子树中，则执行一个提升动作，继承其部分子树。随后，其又于 1 9 9 7 年 提出 了mi . k a l le s 等 人 于1 9 9 6 年 提出t d id t 算 法 1 16 1 ， 该 算 法 对 树中 结点的分割属性的质量进行评价，并对这些属性确保该选择的最小步数进行估 计。 支持向 量机的 样本 增量 学习 研究 有s y e d 等 人于1 9 9 9 年 提出 的 增量学习 算 法 1 刀 ， 它根据内 存 容量 将 大数据集切分成多 个数据块， 在每一 轮训 练后只 保留 本轮得到的支持向量，并将其加入增量的训练数据集中继续训练，直至所有数 第二章 相关工作综述 据 块都被 增 量处 理 完. 另 一 种s v m的 增 量 学习 方法是g e rt c a u w e n b e r g h s 等 人 于2 0 0 0 年 提出 的 1 8 1 ， 该 算 法在出 现增量 样 本 后， 每次 将一 个增量 样本 加入到己 有训 练样本中， 对已 有s v m模型 进行调 整. 与s y e d 提出 的 算法 相比 ， 该算 法 最终所得结果是精确解， 而非近似解。在后续章节中， 本文将详细介绍这两种 算法。 2 . 4 属性值发生改变时的分类器更新 属性值发生改变是指，当分类器训练完成之后，在用于训练分类器的训练 数据中，某些样本属性的取值发生了变化， 其中有些样本的类别属性可能会发 生变化， 其所属的类别将发生改变。 无论类别属性变化与否， 所有样本所属的 类别都属于己 有类别，即各类的条件概率发生了变化， 但类别集合与属性集合 均不变。 目 前，未发现属性值改变时分类器更新方法的研究。 2 . 5 统计学习理论 2 . 5 . 1 机器学习的基本问题 机器学习的目的是根据给定的训练样本求对某系统输入输出之间依赖关系 的估计，使它能够对未知输出做出尽可能准确的预测。可以一般地表示为:变 量y 与x 在 一 定 的 未 知 依 赖 关 系 ， 即 遵 循 某 一 未 知 的 联 合 概 率 f ( x , 月 ( x 和y 之间的确定性关系可以 看作是其特例) ， 机器学习问 题就是根据n 个独立同分布 观 测 样 本 伪 , y , ) ,( xi , y = ) , ., ( x . , y . ) 在 一 组 函 数 f ( x , w ) 中 求 一 个 最 优 的 函 数 i f ( x , - . ) 对 依 赖 关 系 进 行 估 计 ， 使 期 望 风 险 r ( w ) = 乒 ( y , f ( x , w ) d f (x ,y ) ( 2 .1 ) 最 小 其 中 ， i f ( x , w ) 称 为 预 测 函 数 集 ， w 为 函 数 的 广 义 参 数 ， f ( x , w ) 可 以 表 示 任 何 函 数 集 ; 以 y ,f ( x , w ) ) 为 由 于 用 f ( x , w ) 对 y 进 行 预 测 而 造 成 的 损 失 ， 不同类型的学习问题有不同形式的损失函数。预测函数也称作学习函数、学习 模型或学习机器。 有三类基本的机器学习问题，即模式识别、函数逼近和概率密度估计.对 模 式 识 别 问 题 ， 输 出y 是 类 别 标 号 ， 在 两 类 情 况 下 y = 0 , 1 或 y = ( - 1 , 1 ) 预 测 函 第二章 相关工作综述 数称作指示函数，损失函数可以定义为 l ( y , f ( . , - ) ) 二 0 , y = ax , w ) 1 , y # f ( x w ) ( 2 . 2 ) 使风险 最小 就是b a y e s 决策中 使错 误 率 最小. 在函 数逼 近问 题中， y 是 连续 变量 ( 这里假设为单值函 数) ， 损失函数可定义为 l ( y ,f ( x ,w ) ) = ， 一 f ( x , w ) 2 ( 2 .3 ) 即采用最小平方误差准则。 而对概率密度估计问题，学习的目的是根据训练样 本 确 定x 的 概 率 密 度 ， 记 估 计 的 密 度 函 数 为 p ( x , w ) ， 则 损 失 函 数 可以 定 义 为 l ( p ( x ,w ) ) = 一 lo g p ( x , w ) ( 2 .4 ) 2 .5 . 1 . 1经验风险最小化 在上面的问题表述中，学习的目 标在于使期望风险最小化，但是，由于可 以 利 用 的 信 息 只 有 样 本 “, y , ) , ( x z , y , ) , ., ( x . , y . ) , ( 2 . 1 ) 式 的 期 望 风 险 并 无 法 计 算，因此传统的学习方法中采用了所谓经验风险最小化 ( e r m)准则，即用样 本定义经验风险 、 = 去 幼y f (x, w ) ( 2 . 5 ) 做为对 ( 2 . 1 ) 式的估计， 设计学习 算法使它最小化。 对损失函数 ( 2 .2 ) ， 经验风 险就是训练样本错误率; 对 ( 2 .3 ) 式的损失函数， 经验风险就是平方训练误差; 而采用 ( 2 .4 )式损失函数的e r m准则就等价于最大似然方法。 事实上， 用e r m准则代替期望风险最小化并没有经过充分的理论论证， 只 是直观上合理的想当然做法，但这种思想却在多年的机器学习方法研究中占 据 了主要地位。 人们多年来将大部分注意力集中到如何更好地最小化经验风险上， 而实际上，即 使可以 假定当n 趋向 于无穷 大时 ( 2 .5 ) 式趋近于 ( 2 . 1 ) 式， 在很 多问题中的样本数目 也离无穷大相去甚远。 那么在有限 样本下e r m准则 得到的 结果能使真实风险也较小吗? 2 . 5 . 1 .2复杂性与推广能力 e r m准则不成功的一个例子是神经网 络的过学习问题。开始，很多注意力 都 集 中 在 何 使 r . ( w ) 更 小 ， 但 很 快 就 发 现 ， 训 练 误 差 小 并 不 总 能 导 致 好 的 预 测 第二章 相关工作综述 效果。某些情况训练误差过小反而会导致推广能力的下降，即真实风险的增加， 这就是过学习问题。 之所以出 现过学习现象， 一是因为 样本不充分， 二是学习 机器设计不合理， 这两个问题是互相关联的。例如在神经网络中，若对有限的样本来说网络学习 能力过强，足以 记住每个样本，此时经验风险很快就可以收敛到很小甚至零， 但却根本无法保证它对未来样本能给出好的预测。学习机器的复杂性与推广性 之间的 这种矛 盾同 样可以 在其它学习方法中 看到。 文献 2 9 1 给出了 一 个实 验例子， 在 有噪 声 条 件下用模 型y = x2产生1 0个 样 本， 分别用一个一次函数和一个二次函数根据e r m原则去拟合， 结果显示， 虽 然真实模型是二次， 但由 于样本数有限且受噪声的影响， 用一次函数预测的结 果更好，同 样的实 验进行了1 0 0 次， 7 1 % 的结果是一次拟合好于二次拟合。 由此可看出， 有限样本情况下，经验风险最小并不一定意味着期望风险最 小:学习机器的复杂性不但应与所研究的系统有关，而且要和有限数目 的样本 相适应。 我们需要一种能够指导我们在小样本情况下建立有效的 学习和推广方 法的理论。 2 . 5 . 2 统计学习理论的核心内 容 统计学习理论就是研究小样本统计估计和预测的理论，主要内容包括四个 方面: 1 .经验风险最小化准则下统计学习一致性的条件; 2 ，在这些条件下关于统计学习方法推广性的界的结论: 3 .在这些界的基础上建立的小样本归纳推理准则: 4 .实现新的准则的实际方法 ( 算法). 其中，最有指导性的理论结果是推广性的界，与此相关的一个核心概念是 v c维。 2 . 5 . 3 v c维 为了 研究学习 过程一致收敛的 速度和推广性， 统计学习 理论定义了 一系列 有关函 数 集学习 性能的 指标， 其中 最重 要的 是v c维 ( v a p n i k .,)就 可 以 实 现 某 一 非 线 性变换后的线性分类， 而计算复杂度却没有增加，此时目 标函数 ( 2 . 1 1 )变为 q (a ) = 冬一 告 名 a ,a iy ,y ,k (_ ,= i ( 2 . 1 5 ) 而相应的分类函数为: ， 卜 sgn nf (x)= 380(y a,y k (x x)+ b* ( 2 . 1 6 ) 这就是支持向量机。 概括地说，支持向 量机方法通过预先选定的一些非线性映射将输入空间映 射到高维特征空间， 使得在高维属性空间中有可能对训练数据实现超平面的分 割，避免了在原输入空间中进