（计算机应用技术专业论文）面向数据挖掘的支持向量机技术研究.pdf

摘要 摘要 随着网络和通讯技术的日益发展，大量的信息蜂拥而至。如何有效地选择需 要的信息成为越来越突出的问题。数据挖掘就是为顺应这种需要应运而发展起来 的数据处理技术。支持向量机( s u p p o r tv e c t o r 腿c h i n e ，s ) 是数据挖掘中的一 项新技术，是借助于最优化方法解决机器学习问题的新工具。 本文首先讨论了数据挖掘的基本概念，国内外的研究现状，数据挖掘的应用， 数据挖掘的过程以及数据挖掘的基本方法。然后又研究了统计学习理论的一些基 本知识，其中包括了机器学习，v c 维，推广性的界和结构风险最小化。接下来 重点介绍了支持向量机，其中包括了支持向量机的发展历史和现状，主要的基本 概念和研究内容，并在此基础上对当前各种比较通用的支持向量机训练算法进行 了研究，比较了各种算法的优劣。最后针对当前几种基于增量学习的支持向量机 训练算法的缺点，分析了支持向量的性质和增量学习的过程，提出了一种新的增 量学习算法，在保证测试精度的同时减少了训练时间。最后的数值实验和应用实 例说明了，算法是可行的、有效的。 关键词：数据挖掘统计学习理论支持向量机增量学习 垒! 坐! 璺一 a b s t r a c t w i t ht h ed e v e l 叩m e n to ft h et e c l l i l o l o g yj nn e m o r ka i i d 咖m u n i c a t i o n ，m a s s i n f o r m a t i o nc r o w di no n h o wt oe 伍e c t i v e l ys e l e c tw h a tw en e e db e c o m e sm o f c o u t s t a n d i n gt h 卸c v e ld a t am i n i i l 岛舔ap r o c e s s i n gt e c l l n i q u e ，j sp o p u i a r t ob eu dt o m e e tt h en e e d s u p p o n 斌o rm a c b i n e ( s v m ) j sam wt e c l l n o l o g yo fd a t am i n i n g a n dan e wi m p l e m e n tr e c u r r e dt 0o p t i m i z a t i o nt e c h n j q u e st 0s o l v et h ep f o b l e m so f m a c h i n ek a m j n g a tt h eb e 百仰i n gt h cc o n c c p t s ，t h er c s c a r c hs t a t ci i ll h ew o r i d t h ea p p i i c a t i o n ，t h c p r o c c s sa i l d t h eb 舔i cm e t h o do fd a t am i n i n ga 陀a d d r c s d a n dn e x t t h i sp a p c r s t u d j e st h cb a s i ck n o w l e d g co fs t a t i s t j c a ik a n l j n gn e o 哆而c nt h j sp a p c rs t r c s st 0 i n t r o d u c es v m ，i n v o l v e do ft h ed e v e i o p m e n th i s t o r y t h es t a t es of a r ，m a i nc o n c e p t s a dt h e n t e n to fr e s e a r c h b ya n a i y z i n gt h ec b a r a c t c 打s t i c so fs u p p o r t 蛐r sa i l dt h e p r o c c s s i n go fj n c r c m e n t a ll e 椰j n 岛t h j sp 叩盯p r e s e n t san e wa l g o r i t h mo fi n c r 锄e n t a l l e 锄i n 臣nd j s c a r d sn s e l 姻ss 锏p l e sa n dk c e p st h et e s t i n ga c c h f a c y ，m e a i l w 恤主l e t m i i l j n gt i m ei sr c d u c c d n u m e c a l 柚da p p l i c a b l er c s u l t sn l u s t t a t et h a tt h et e c h n i q u e i sf e a s i b l ea n de 矗e c t i v ei nt h ee n d k e y w o r d ： d a t am i n i n gs t a t i s l j c a lk 爆皿i n gt h e o r y s u p p o r t v e c t o rm a c h i n e i n c 心m c n t a ll e a m i n g 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其他教育机构的学位或证书而使用过的材料。与我一同工作过的同志对本研究所 做的任何贡献己在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：监日期丕幽：2 ：兰1 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本学位论文属于保密在年解密后适用本授权书。 本人签名： 导师签名： ：望。查：。：i z日期呈! ! z 2 ：2 2 日期主珥皇：驾 第一章绪论 第一章绪论 1 1 课题背景 数据挖掘源于数据库技术引发的海量数据和人们利用这些数据的愿望。用数 据管理系统存储数据，用机器学习的方法分析数据、挖掘海量数据背后的知识， 便促成了数据挖掘( d a t a m i n i n g ) 的产生。概括地讲，数据挖掘的任务是从大型数 据库或数据仓库中提取人们感兴趣的、事先未知的、有用的或潜在有用的信息。 支持向量机( s u p p o r tv e c t o r 腿c h i n e ，s ) 是数据挖掘中的一项新技术，是 借助于最优化方法解决机器学习问题的新工具。它最初于2 0 世纪9 0 年代由v 却n i k 提出，近年来在其理论研究和算法实现方面都取得了突破性进展，开始成为克服 “维数灾难”和“过学习”等困难得有力手段。虽然它还处于飞速发展的阶段， 但是它的理论基础和实现途径的基本框架已经形成。 1 2 国内外的研究现状 数据挖掘是数据库研究、开发和应用最活跃的分支之一。其研究重点也逐渐 从发现方法转向系统应用，注重多种发现策略和技术的集成，以及多种学科之间 的相互渗透。目前，世界上比较有影响的数据挖掘系统有：s a s 公司的e n t e i p r i s e m i n e r ， i b m 公司的i n t e l l i g e n tm i n e r ， s g i 公司的s e tm i n e r ，s p s s 公司的 a e m c n t i n e ，s v b 硒e 公司的w 缸e h o 璐es t u d i o ， r u l eo u e s tr c s e 盯c h 公司的s e e 5 ， 由加拿大s i m o nf r a s e 大学智能数据库系统研究实验室与d bm j n e rt c c i l n o l o g y 公司 共同开发的产品d bm j n e r 等1 7 j 。 与国外相比，国内对数据挖掘的研究稍晚，还没有形成整体力量。目前，国 内己有一些科研单位和高等院校开展了知识发现和数据挖掘的基础理论及其应用 研究，这些单位包括清华大学、中科院计算技术研究所、空军第三研究所、海军 装备论证中心等。 早在6 0 年代v j v a p n i k 就开始了统计学习理论的研究，1 9 7 1 年，v v a p n i k l 删和 九c h e n ，o n e n “s 提出了s v m 的一个重要的理论基础一v c 维理论。1 9 8 2 年， v v a p n i k i ”j 进一步提出了具有划时代意义的结构风险最小化原理。1 9 9 2 年， b o s e f 【矧，g u y o na l l dv a p n j k 提出了最优边界分类器。1 9 9 3 年，c o n e s l 6 卅和v a p n k i 进 一步探讨了非线性晟优边界的分类问题。1 9 9 5 年，v v a p n i k 完整地提出了s v m 分类 【1 引。1 9 9 7 年，v v a p n j k 【嗣，s g o k o w i c h 和a s 肿l a ，详细介绍了基于s v m 方法的回 2 面向数据挖掘的支持向量机技术研究 归算法和信号处理方法。 由于s v m 算法的潜在应用价值，吸引了国际上众多的知名学者。近几年出现 了许多发展和改进的支持向量机算法和有关非线性s v m 中核的研究方法。 s v m 在模式识别领域已经有了一些应用，如手写体数字识别，人脸识别与人 脸检测，以及文本分类等各种领域。此外，s v m 还很好地应用于时间序列分析和 回归分析等领域的研究。例如，m r r 、b e 儿l a b 和微软研究所等已成功地将s v m 算法应用于动态图像的人脸跟踪，信号处理，语音识别，图象分类和控制系统等 诸多领域。 1 3 本文的组织结构 本文的组织结构如下： 第二章描述了数据挖掘理论的基本概念，以及数据挖掘的过程和用到的方 法。 第三章描述了机器学习的基本问题和统计学习理论，其中包括了经验风险最 小化，复杂性与推广能力，以及v c 维和结构风险。 第四章和第五章重点描述了支持向量机的基本概念和当前流行的支持向量 机训练算法。 第六章描述了当前的增量学习算法，并且比较了它们的各自优缺点，在此基 础上给出了一种新的增量学习算法。 第七章描述了本文研究工作的总结与展望。 第二章数据挖掘理论与技术 3 第二章数据挖掘理论与技术 2 1 数据挖掘概述 随着数据库技术的成熟和计算机应用的普及，各行各业积累的数据迅速增长。 进入二十世纪末，伴随着网络的出现和发展，使得整个世界变成一个地球村，人 们可以跨越时空地在网上交换数据信息和协同工作。这样，展现在人们面前的已 不是局限于本部门，本单位和本行业的庞大数据库，而是浩瀚无垠的信息海洋。 当数据量越来越大时，使用传统或经典的方法，即便是使用计算机来提取有用信 息和知识，人们也会在面对海量的数据时感到无能为力。因此，如何有效地解决 数据获取的快捷与数据分析困难之间的矛盾，成为计算机科学技术中的一个重要 问题，而数据挖掘正是解决这一矛盾的一种有效手段。 2 1 1 数据挖掘的基本概念 所谓数据挖掘，是从海量的数据中，抽取出潜在的、有价值的知识( 模式或规 则) 的过程。也就是根据预定义的商业目标，对大量的企业数据进行探索和分析， 揭示其中隐含的商业规律，并进一步将其模式化的先进有效技术的过程。数据挖 掘是一门交叉学科，它集成了许多学科中成熟的工具和技术，包括数据库技术、 统计学、机器学习、模式识别、人工智能、神经网络等等。 许多人把数据挖掘视为另一个常用的术语：数据库中的知识发现或k d d 的同 义词。而另些人只是把数据挖掘视为数据库中知识发现过程的一个基本步骤。 知识发现过程由以下步骤组成： 数据清理f 消除噪声或者不一致的数据) 数据集成( 多种数据源可以组合一起) 数据选择( 从数据库中检索与分析人物相关的数据) 数据变换( 数据变换或统一成适合挖掘的形势) 数据挖掘( 使用方法提取数据模式) 模式评估( 根据某种兴趣度度量，识别表示知识的真正有趣的模式1 知识表示( 使用可视化和知识表示技术，向用户提供挖掘的知识) 广义的数据挖掘是从存放在数据库、数据仓库或者其他信息库中的大量数据 中挖掘有趣知识的过程。 在这种观点下，数据挖掘系统具有以下主要成分1 1 1 ：数据库、数据仓库或其他 信息库、数据库或数据仓库服务器、知识库、数据挖掘引擎、模式评估模块和图 4 面向数据挖掘的支持向量机技术研究 形用户界面。 可以用图2 1 表示： 图2 1 数据挖掘系统的主要成分 2 1 2 数据挖掘的应用 由于数据挖掘能分析出数据中的有用信息，给企业带来显著的经济效益，这 使碍数据挖掘技术越来越普及。 英国电信需要发布一种新的产品，需要通过直邮的方式向客户推荐这种产品， 使用数据挖掘技术使直邮的回应率提高了1 0 0 ；c m s 日用品零售商店需要准确的 预测未来的商品销售量，降低库存成本，使用数据挖掘技术使库存成本比原来减 少了3 8 ；汇丰银行需要对不断增长的客户群进行分类，对每种产品找出最有价 值的客户，使用数据挖掘技术营销费用减少了3 0 ：美国国防财务部需要从每年上 百万比的军火交易中发现可能存在的欺诈现象，使用数据挖掘技术发现可能存在 欺诈的交易，进行深入调查，节约了大量的调查成本。 许多企业都在利用数据挖掘技术帮助管理客户生命周期的各个阶段，包括争 取新的客户和保持住好的客户。分析潜在客户，根据挖掘出的客户的特点，为客 户提供针对性的服务。 许多公司已将数据挖掘产品化，两个大型统计软件公司s a s 和s p s s 也推出了 各自的数据挖掘工具e n t e r d r i s em j n e r 和c i e m e n i j n e 。 从事数据挖掘研究与开发的还有微软、i b m 等，m m 公司的i n t e l j i 帮n tm j n e 具 有典型数据集自动生成、关联发现、序列规律发现、概念性分类和可视化显示等 功能。它可以自动实现数据选择、数据转换、数据挖掘和结果显示。若有必要， 对结果数据集还可以重复这一过程，直至得到满意结果为止。 第二章数据挖掘理论与技术 5 医疗应用是数据挖掘的一个前景广阔的领域，数据挖掘可以用来预测外科手 术、医疗试验和药物治疗的效果。零销商使用数据挖掘来决定每种商品在不同地 点的库存，通过数据挖掘更灵活的使用促销和优惠卷手段。制药公司通过挖掘巨 大的化学物质和基因对疾病的影响的数据库来判断哪些物质可能对治疗某种疾病 产生效果。 在农业生产方面，农业生产与气候、气象有着密切的关系，我国是一个农业 大国，农业生产关系到国家经济命脉和人民生活，数据挖掘在农业气象预报中的 应用是较有意义的工作。 人们普遍认为数据挖掘的未来是美好的。m e t ag r o u 口曾做出这样的评论： “全球重要的企业、组织会发现，到2 1 世纪数据挖掘技术将是他们商业成功与否 的至关重要的影响因素”，国际知名调查机构g a r t n e fg m u p 在高级技术调查报告 中，将数据挖掘和人工智能列为“未来三到五年内将对工业产生深远影响的五大 关键技术”之首，还将并行处理体系和数据挖掘列为未来五年内投资焦点的十大 新兴技术前两位。g a f t n e r 的调查报告预计：到2 0 l o 年，数据挖掘在相关市场的 应用将从目前少于5 增加到超过8 0 。美国银行家协会预测数据仓库和数据挖 掘技术在美国商业银行的应用增长率是1 4 9 i 引。 2 2 数据挖掘过程 概括地说，基本数据挖掘步骤一般包括以下三个部分：数据的准备、模型的 建立、模型的验证和评价【6 】。 1 数据的准备 数据的准备包括数据取样、数据特征探索、分析和预处理，同时要明确问题， 选择适合的数据，必要时要进行调整。具体说来，例如计算统计变量( 譬如平均值、 均方差等) 。再用图表或图片直观地表示出来，进而可以看出一些变量之间的相关 性( 比如有一些值，经常一起出现) 。选择正确的数据源对整个数据挖掘项目的成败 至关重要。 数据取样要把好数据的质量关，在任何时候都不要忽视数据的质量，即使是 从一个数据仓库中进行数据取样，也不要忘记检查其质量如何。因为数据挖掘的 目的是要探索企业运作的规律性的，如果原始数据有误，则还谈什么从中探索规 律性? 若你真的从中还探索出来了什么“规律性”，再依此去指导工作，则很可能 是在进行误导。若你是从正在运行着的系统中进行数据取样，则更要注意数据的 完整性和有效性。 2 模型的建立 这一步是数据挖掘工作的核心环节。对建立模型来说，要记住的最重要的事 6 面向数据挖掘的支持向量机技术研究 就是它是一个反复的过程。需要仔细考察不同的模型以判断哪个模型对你的问题 最有用。在寻找好的模型的过程中学到的东西会启发你修改你的数据，甚至改变 最初对问题的定义。 一旦决定了挖掘类型之后，就需要选择模型的类型。模型的类型可能是一棵 决策树、神经网络、甚至是传统的数学统计。选择什么样的模型决定了你需对数 据做哪些预处理工作。如神经网络需要做数据转换，有些数据挖掘工具可能对输 入数据的格式有特定的限制等。一旦所有的数据准备好了之后，就可以开始训练 你的模型了。 就目前的技术发展水平而言，数理统计方法还是数据挖掘工作中最常用的主 流技术手段。市场上很多的软件供应商和数据挖掘咨询公司一般都提供了很多的 软件包，包含有很多实用的数理统计方法。而在你的数据挖掘模型中使用哪一种 方法，具体用软件包中的什么方法来实现，主要取决于数据集的特征和要实现的 商业目标。实际上，这种选择也不一定是唯一的，可以多试几种方法，从具体的 实践中选出最合适的方法和软件。 3 模型的验证和评价 从上述过程中将会得到一系列的分析结果、模式和模型，评价的方法之一是 直接使用原来建立模型的样板数据来进行检验。假如这一关就通不过的话，那么 决策支持信息的价值就大打折扣了。一般来说，在这一步应得到较好的评价。这 说明确实从这批数据样本中挖掘出了符合实际的规律性。 另一种方法是另外找一批数据，已知这些数据反映了客观实际的规律性。这 次的检验效果可能会比前一种差。差多少是要注意的。若是差到不能容忍的程度， 那就要考虑第一次构建的样本数据是否具有充分的代表性或是否是模型本身不够 完善。这时候可能要对前面的工作进行反思了。若这一步也得到了肯定的结果， 那么数据挖掘应该能得到很好的评价了。 再一种办法是在实际运行的环境中取出新鲜数据进行检验。如在一个应用实 例中，就再进行了一个月的现场实际检验。 一般来说，使用模型得到的如果是一个直接的结论，则当然很好，但是，实 际上这种情况非常的少，更多的时候得出的是对目标问题多侧面的描述，这时就 要能很好地总结它们的规律性，提供合理的决策支持信息。所谓合理，实际上往 往是要在所付出的代价和达到预期目标的可靠性的平衡上做出选择。假如在数据 挖掘过程中，就预见到晟后要进行这样的选择的话，那么最好把这些平衡的指标 尽可能地量化，以利于综合抉择。 在实际应用中，随着应用数据的不同，模型的准确率肯定会有所变化。更重 要的是，准确度自身并不一定是选择最好模型的正确评价方法，需要进步了解 第二章数据挖掘理论与技术 7 错误的类型和由此带来的相关费用的多少。在实际应用中，如果每种不同的预测 错误所需付出的代价( 金钱) 也不同的话，那么代价最小的模型( 而小一定是错误率 最小的模型) 就是我们所要选择的。 模型建立并经过验证之后，可以有两种主要的使用方法。第一种是提供给业 务人员或分析人员做参考，通过察看和分析这个模型之后提出行动方案建议。比 如，可以把模型检测到的聚集、模型中蕴含的规则或表明模型效果的图表拿给分 析人员看。另一种是把此模型应用到不同的数据集上。模型可以用来标识一个事 例的类别，给一项申请打分等。还可以用模型在数据库中选择符合特定要求的记 录，并用0 l 廿工具做进一步的分析。 数据挖掘过程的步骤示意图如图2 。2 所示 图2 2 数据挖掘过程的步骤 这里需要指出的是，上面的各个步骤按顺序排列，要注意数据挖掘过程并不 是线性的，要取得好的结果就要不断重复这些步骤。比如在“建立模型”时，你 可能觉得在“数据预处理”时做得不够好，或者是要往里面添加一些新的数据等。 当提交一个复杂的应用时，数据挖掘可能只是整个产品的一小部分，虽然可 能是最关键的一部分。例如，在欺诈检测系统中，我们常常把数据挖掘得到知识 与领域专家的知识结合起来，然后应用于数据库中的数据。 2 3 数据挖掘方法 数据挖掘中采用的方法综合了数据库、人工智能、统计学、模式识别、机器 学习、数据分析等领域的研究成果。现有的数据挖掘方法主要有以下几种1 4 1 ：人 工神经网络( a n j f i d a ln e u r a jn e t w o r k s ) 、遗传算法( g e n e t i c 9 0 r i t h m s ) 、决策树方 法( d e c i s i 1 r c e s ) 、关联分析( a s s o c j a t i o n s ) 、序列模式分析( s e q u e n t j a ip a t t e m s ) 、 分类分析( c l a s s i f i e r s ) 、聚类分析( c l u s t e r i n g ) 。 8 面向数据挖掘的支持向量机技术研究 2 3 1 人工神经网络( a n i f i c i a ln e u r a ln e 觚o r l 【s ) 神经网络为解决复杂度问题提供了一种相对来说比较有效的简单方法。神经 网络可以很容易的解决具有上百个参数的问题( 当然实际生物体中存在的神经网络 要比我们这里所说的程序模拟的神经网络要复杂的多1 。神经网络常用于两类问题： 分类和回归。 在结构上，可以把一个神经网络划分为输入层、输出层和隐含层。输入层的 每个节点对应一个个的预测变量。输出层的节点对应目标变量，可有多个。在输 入层和输出层之间是隐含层( 对神经网络使用者来说不可见) ，隐含层的层数和每层 节点的个数决定了神经网络的复杂度。 除了输入层的节点，神经网络的每个节点都与很多它前面的节点( 称为此节 点的输入节点) 连接在一起，每个连接对应一个权重，此节点的值就是通过它所有 输入节点的值与对应连接权重乘积的和作为一个函数的输入而得到，我们把这个 函数称为活动函数。要完成神经网络的训练可能需要很多个训练周期，经常是几 百个。训练完成之后得到的神经网络就是在通过训练集发现的模型。描述了训练 集中响应变量受到预测变量影响的变化规律。 神经元网络和统计方法在本质上有很多差别。神经网络的参数可以比统计方 法多得多。参数通过各种各样的组合方式来影响输出结果，以至于很难对一个神 经网络表示的模型做出直观的解释。实际上神经网络也正是当作“黑盒”来用的， 不用去管“盒子”里面是什么，只管用就行了。在大部分情况下，这种限制条件 是可以接受的。比如银行可能需要一个笔迹识别软件，但它没必要知道为什么这 些线条组合在一起就是一个人的笑名，而另外一个相似的则不是。在很多复杂度 很高的问题如化学试验、机器人、金融市场的模拟以及语言图像的识别等领域神 经网络都取得了很好的效果。 神经网络的另一个优点是很容易在并行计算机上实现。可以把它的节点分配 到不同的c p u 上并行计算。 2 3 2 遗传算法( g e n e t i c g o f i c h m s ) 遗传算法是模拟生物进化过程的算法，由三个基本算子( 或过程) 组成： ( 1 ) 繁殖( 选择) 。即从一个旧种群( 父代) 选出生命力强的个体，产生新的种群( 后 代) 的过程。 ( 2 ) 交叉( 重组) 。即对选择两个不同的个体( 染色体) 的部分( 基因) 进行交换，形 成新个体的过程。 第二章数据挖掘理论与技术 9 ( 3 ) 变异( 突变) 。即对某些个体的某些基因进行变异( o 变1 ，或1 变0 ) ，形成新 个体的过程。 这种遗传算法可起到产生优良后代的作用。这些后代需满足适应值，经过若 干代的遗传，将得到满足要求的后代( 也就是闯题的解) 。遗传算法己在优化计算和 分类机器学习方面发挥了显著作用。 2 3 3 决策树方法( d e c i s i o nt r e e s ) 决策树提供了种展示类似在什么条件下会得到什么值这类规则的方法。比 如，在贷款申请中，要对申请的风险太小做出判断。决策树的基本组成部分：决 策节点、分支和叶子。决策树中最上面的节点称为根节点，是整个决策树的开始。 决策树的每个节点的子节点的个数与决策树在用的算法有关。如c a r t 算法得到的 决策树每个节点有两个分支，这种树称为二叉树。允许节点含有多于两个子节点 的树，称为多叉树。 每个分支要么是一个新的决策节点，要么是树的结尾，称为叶子。在沿着决 策树从上到下遍历的过程中，在每个节点都会遇到一个问题，对每个节点上问题 的不同回答导致不同的分支，最后会到达一个叶子节点。这个过程就是利用决策 树进行分类的过程，利用几个变量( 每个变量对应一个问题) 来判断所属的类别，最 后每个叶子会对应一个类别。 建立决策树的过程，即树的生长过程是不断的把数据进行切分的过程，每次 切分对应一个问题，也对应着一个节点。对每个切分都要求分成的组之间的“差 异”最大。 2 3 4 关联分析( 触s o c i a t i o n s ) 关联规则从用户指定的数据库中挖掘出满足一定条件的依赖性关系。关联规 则形如“4j4 ，支持度( s u p p o r t ) = s ，置信度( c o n f i d e n c e ) = c ”，其中s 和c 是用户指定的支持度和置信度的a 值。这种关联规则挖掘可以在不同的抽象概念 层次上进行。例如r ：“尿布一啤酒，支持度= 5 ，置信度= 5 0 ”与r ：“婴 一 儿用品类一饮料类，支持度= 2 5 。置信度= 8 0 ”相比，冗 在更高的抽象层次上， 更为宏观，因而有较大的支持度和置信度，更适合高层决策需要。 1 0 面向数据挖掘的支持向量机技术研究 2 3 5 序列模式分析( s e q u e n t i a lp a t t e m s ) 序列模式分析和关联分析法相似，其目的也是为了挖掘出数据之间的联系， 但序列模式分析的侧重点在于分析数据间的前后( 因果) 关系。它能发现数据库中形 如“在某一段时间内，顾客购买商品a ，接着贿买商品b ，而后购买商品c ，即序 列a _ b 一 c 出现的频度较高”之类的知识，序列模式分析描述的问题是：在给定 交易序列数据库中，每个序列是按照交易时间排列的一组交易集，挖掘序列函数 作用在这个交易序列数据库上，返回该数据库中出现的高频序列。在进行序列模 式分析时，同样也需要由用户输入最小置信度c 和最小支持度s 。关联规则中采用的 a p r i o r i 算法也可以用于序列模式的挖掘，因为若长度为k 的序列模式是非频繁的， 其超集( 长度为k + 1 ) 不可能是频繁的。因此序列模式挖掘的大部分方法都采用了类 a p r i o r i 算法的变种，只是所考虑的参数设置和约束有所不同。 2 3 6 分类分析( c l a s s i f i e r s ) 设有一个数据库和一组具有不同特征的类别( 标记) ，该数据库中的每一个记录 都赋予一个类别的标记，这样的数据库称为示例数据库或训练集。分类分析就是 通过分析示例数据库中的数据，为每个类别做出准确的描述或建立分析模型或挖 掘出分类规则，然后用这个分类规则对其它数据库中的记录进行分类。 2 3 7 聚类分析( c 1 u s t e r i n g ) 聚类与分类不同，在分类模块中，对于目标数据库中存在哪些类这一信息我 们是知道的，在那里我们要做的就是将每一条记录分别属于哪一类标记出来；与 此相似但又不同的是，聚类是在预先不知道目标数据库到底有多少类的情况下， 希望将所有的纪录组成不同的类，或者说“聚类”( d u s t e r ) ，并且使得在这种分类 情况下，以某种度量为标准的相似性，在同一聚类之间最小化而在不同聚类之间 最大化。事实上，聚类算法中一大类算法中的相似性都是基于距离的，而且由于 现实数据库中数据类型的多样性，关于如何度量两个含有非数值型字段的记录之 间的距离的讨论有很多，并提出了相应的算法。在很多应用中，由聚类分析得到 的每个聚类中的成员都可以被统一看待。聚类分析的算法可以分为以下几大类： 分裂法、层次法、基于密度的方法、基于网格的方法和基于模型的方法等。 聚类分析作为数据挖掘中的一个模块，它既可以作为个单独的工具以发现 数据库中数据分布的一些深入的信息，并且概括出每一类的特点，或者把注意力 第二章数据挖掘理论与技术 1 1 放在某一个特定的类上以作进一步的分析；聚类分析也可以作为数据挖掘算法中 其他分析算法的一个预处理步骤。 2 4 本章小结 本章论述了数据挖掘的一些基本概念，介绍了数据挖掘的国内外现状，以及 数据挖掘的应用，并且具体阐述了数据挖掘的步骤和其中用到的技术和方法。 第三章统计学习理论 第三章统计学习理论 3 1 引言 基于数据的机器学习是现代智能技术中的重要方面，研究从观测数据( 样本) 出发寻找规律，利用这些规律对未来数据或无法观测的数据进行预测，包括模式 识别、神经网络等在内，现有机器学习方法共同的重要理论基础之一是统计学。传 统统计学所研究的是渐进理论，即当样本数目趋向于无穷大时的极限特性，统计 学中关于估计的一致性、无偏性和估计方差的界等，以及分类错误率的诸多结论， 都属于这种渐近特性。但在实际问题中，样本数目往往是有限的，当问题处在高 维空间时尤其如此，因此一些理论上很优秀的学习方法实际中表现却可能不尽人 意。 与传统统计学相比，统计学习理论( s t a t i s t i c a ik a m j n g1 n h e o r y 或s u l 是一种 专门研究小样本情况下机器学习规律的理论。v a p n i k 等人从六、七十年代开始致 力于此方面研究，到九十年代中期，随着其理论的不断发展和成熟，也由于神经 网络等学习方法在理论上缺乏实质性进展，统计学习理论开始受到越来越广泛的 重视。 统计学习理论是建立在一套较坚实的理论基础之上的，为解决有限样本学习 问题提供了一个统一的框架。它能将很多现有方法纳入其中，有望帮助解决许多 原来难以解决的问题( 比如神经网络结构选择问题、局部极小点问题等1 ；同时， 在这一理论基础上发展了一种新的通用学习方法支持向量机( s u p p o f tv e c 6 d f m a c h i n e 或s v m l ，它已经初步表现出很多优于已有方法的性能。在解决小样本、 非线性及高维模式识别问题中表现出许多特有的优势，并能够推广应用到函数拟 合等其他机器学习问题中。虽然统计学习理论和支持向量机方法中尚有很多问题 需要进一步研究，但很多学者认为，它们正在成为继模式识别和神经网络研究之 后机器学习领域新的研究热点，并将推动机器学习理论和技术有重大的发展。 3 2 机器学习的基本问题 3 2 1 机器学习问题的表示 机器学习问题的基本模型，可以用图3 1 表示。其中，系统s 是我们研究的对象 1 4 面向数据挖掘的支持向量机技术研究 它在给定一定输入x 下得到一定的输出y ，l m 是我们所求的学习机，输出为y 。 机器学习的目的根据给定的己知训练样本求取对系统输入输出之间依赖关系的估 计，使它能够对未知输出做出尽可能准确的预测【们。 图3 1 机器学习问题的基本模型 机器学习问题可以形式化地表示为：己知变量y 与输入x 之间存在一定的未知依 赖关系，即存在一个未知的联合概率，( 石，) ) ，( x 和y 之间的确定性关系可以看作是 一个特例1 ，机器学习就是根据n 个独立同分布样本 “，m ) ，_ ) ，：) ，瓴，y ) ， 式( 3 1 ) 在一组函数 ，o ，w ) ) 中求一个最优的函数 ，o ，) ) 对依赖关系进行估计，使期望 风险 r ( w ) = 弘( _ ) ，( 工，) ) 卵( 工，) ，) ， 式( 3 2 ) 最小。其中，( 工，w ) 称作预测函数集，为函数的广义参数，( 五w ) 可以表示任 何函数集；( _ ，( 工，w ) ) 为由于用，( j ，w ) 对y 进行预测而造成的损失，不同类型的 学习问题有不同形式的损失函数，预测函数也称作学习函数、学习模型或学习机 器。 有三类基本的机器学习问题，即模式识别、函数逼近和概率密度估计。对模 式识别问题，输出y 是类别标号，两类情况下yt o ，1 ) 或仙一1 】，预测函数称作指 示函数，损失函数可以定义为： 三( y ，( z ，) ) - j f y = ，( 石，w ) i f y ，( 工，) ， 式( 3 3 ) 第三章统计学习理论 使风险最小就是b a y e s 决簟中使错误率最小，在函数逼近问题中，y 是连续变量( 这 里假设为单值函数1 ，损失函数可定义为： l ( _ ) ，( 五w ) ) t ( ) ，一，( 五w ) ) 2 ， 式( 3 4 ) 即采用最小平方误差准则，而对概率密度估计问题，学习的目的是根据训练样本 确定x 的概率密度，记估计的密度函数为p k w ) ，则损失函数可以定义为 l ( p ( z ，) ) 一一l o g p ( 工，) 。 式( 3 5 ) 经常采用的损失函数有以下几种： ( 1 ) 二次型损失函数 l ( ) ，o ，) ) - 0 ，一，o ，w ) ) 2式( 3 6 ) ( 2 ) 绝对值损失函数 ( y ，0 ，) ) = i _ r 一，o ，叻i ( 3 ) h u b e r 损失函数 r c l y 一，o ，1 _ 圭c 2 若l y 一，g ，训) c 工( ) ，o ，) ) 0 为l a 芦a n g c 系数，我们的问题是对w 和b 求l a g r a n g e 函数的极小值。 把式( 4 5 分别对w 和b 求偏微分并令它们等于o ，就可以把原问题转化为如下 这种较简单的对偶问题，在约束条件 蓍叭。0 q 己0 2 ，n式 之下对q 求解下列函数的最大值： q ( 。) - 砉g 专毫鹏( a 若口，为最优解，则 式( 4 7 ) 第四章支持向量机的研究 w ，- 咒玉 式睁8 ) 即最优分类面的权系数向量是训练样本向量的线性组合。 这是一个不等式约束下二次函数极值问题，存在唯一解。且根据k u h n _ t l l c k e r 条件，这个优化问题的解须满足 q ( 咒( w 毛+ 6 ) 一1 ) 一o ， f 一1 ，2 ，一，h 式( 4 9 ) 因此，对多数样本a 。将为零，取值不为零的口；对应于使式p 2 ) 等号成立的样本即 支持向量，它们通常只是全体样本中的很少一部分。 求解上述问题后得到的最优分类函数是 厂( j ) l s g n “w 工) + 厶。 i s g n 砉z 舅( 畸了) + 6 ， 式( 4 。，。 s 卸o 为符号函数。由于非支持向量对应的q 均为0 ，因此，式中的求和实际上 只对支持向量进行。而6 是分类的域值，可以由任意一个支持向量用式( 4 2 ) 求得( 因 为支持向量满足其中的等式) ，或通过两类中任意一对支持向量取中值求得。 4 1 2 广义最优分类面 最优分类面是在线性可分的前提下讨论的，在线性不可分的情况下，就是某 些训练样本不能满足式( 4 2 ) 的条件，因此可以在条件中增加一个松弛项岳乏0 ，变 成： y i 【( w 毛) + 扫卜1 + 毫苫o 式( 4 1 1 ) 对于足够小的盯，o ，只要使 c ( 亭) = 第， 式( 4 1 2 ) 最小就可以使错分样本数最小。对应线性可分情况下的使分类间隔最大，在线性 不可分情况下可引入约束 8 w l l 2s q 。 式( 4 1 3 ) 在约束条件( 4 1 1 ) 和( 4 1 3 ) 下，对式( 4 1 2 ) 求极小，就得到了线性不可分情况下的最 优分类面，称作广义最优分类面。为了计算方便，我们取口- 1 。 为了使计算进一步简化，广义最优分类面问题可以进一步演化为在条件( 4 1 0 ) 面向数据挖掘的支持向量机技术研究 的约束下求下列函数的极小值： 庐( ，亭) 抄w ) + c ( 善皇) 式( 4 - 1 4 ) 其中c 为某个指定的常数，它实际上起控制对错分样本惩罚的程度的作用，实现在 错分样本的比例与算法复杂度之间的折衷。 用与求解最优分类到时同样的方法求解这一优化问题，同样得到一个二次函 数极值问题，其结果与可分情况下得到的式( 4 6 ) 式( 4 1 0 ) 几乎完全相同，只是条 件( 4 6 ) 变为 o q 量c ， f 一1 ，2 ，以 式( 4 1 5 ) 4 。l 。3 支持向量机 7 f 、x 专矽( x ) 险趑 第四章支持向量机的研究 式。根据泛函的有关理论，只要一种核函数k “，工，) 满足m e r c e r 条件，它就对 应某一变换空间中的内积。 定理( m e r c e r 条件) 对于任意的对称函数k o ，工，) ，它是某个特征空间中的内 积运算的充分必要条件是，对于任意的伊o ) 一。且p 2 0 ) 出c 。，有 仃k 工印扛) 矿( 茗) 如出，o a 式( 4 1 6 ) 因此，在最优分类面中采用适当的内积函数k “，工，) 就可以实现某一非线性变 换后的线性分类，面计算复杂度却没有增加，此时目标函数( 4 7 ) 变为 q ( 口) 。荟q 一撬峨现k ( ，) ， 式件1 7 ) 而相应的分类函数也变为 几卜驴 j ) “ 一，刚刊1 式) 这就是支持向量机。 概括地说，支持向量机就是首先通过用内积函数定义的非线性变换将输入空 间变换到一个高维空间，在这个空间中求( 广义) 最优分类面，而这种非线性变换 是通过定义适当的内积函数实现的。 支持向量机求得的分类函数形式上类似于一个神经网络，其输出是若干中间 层节点的线性组合，而每一个中间节点对应于输入样本与一个支持向量的内积， 因此也被叫做支持向量网络，如图4 3 所示。 x ( 上i 工z 图4 3 支持向量机示意图 由以上不难看出，支持向量机具有以下特点： ( 1 ) 支持向量机算法是基于统计学习理论的结构风险最小化原则的，与传统的算 面向数据挖掘的支持向量机技术研究 法不同，它不仅优化经验风险，而且通过最大化分界面来控制模型的复杂度， 从而有效地避免了过学习现象，为模型选择问题提供了很好的思路。 ( 2 ) 它是专门针对有限样本情况的，其目标是得到现有信息下的最优解而不仅仅 是样本数趋于无穷大时的最优值。 ( 3 ) 训练算法最终将转化为一个二次寻优问题，从理论上说， ! 导到的将是全局最 优解，解决了在神经网络方法中存在的局部极值问题。 ( 4 ) 算法将输入空间中的训练样本通过非线性变换到高维的特征空间中，在高维 空间中构造线性判别函数来实现原空间中的非线性判别函数，并能保证机器 有较好的泛化能力，同时它巧妙地解决了维数问题，其算法复杂度与样本维 数无关。 4 1 4 核函数( k e r n e lf u n c t i o n ) 支持向量机由训练集和核函数完全刻画，这样在实际问题中，常常是直接给 出核函数( 而不是给出映射9 0 ) ) ，所以如何构造和选择核函数是个重要问题。常用 的核函数主要有三类： ( 1 ) 多项式核函数： x 0 ，薯) 一( 0 毛) + 妒， 式( 4 一1 9 ) 所得到的是q 阶多项式分类器。 ( 2 ) 径向基核函数( r b f ) ： 叫一呼) r 抑。， 所得到的分类器与传统r b f 方法的重要区别是，这里每个基函数中心对应一个支 持向量，它们及输出权值都是由算法自动确定的。 ( 3 ) s i g m o i d 核函数： k o ，玉) tt a n h p 0 。) + c ) ，式( 4 2 1 ) 这时s v m 实现的就是包含一个隐层的多层感知机，隐层节点数是由算法自动 确定的，而且算法不存在困扰神经网络方法的局部极小点问题。 4 2 支持向量机理论的主要研究内容 支持向量机结构简单，并且具有全局最优性和较好的推广能力，自九十年代 中期提出以来得到了广泛的研究。目前，还有很多关于s v m 和v c 维的理论和应用 第四章支持向量机的研究 问题待研究。一方面，这种基于统计学习原理的理论思路对新的学习算法的提出 很有启发，另一方面，由于s v m 出现不久，其理论依据和算法是尚有大量问题有 待于发展和完善。在上述问题中，我们认为下面几个问题尤其值得研究： ( 1 ) 把v c 理论和结构风险最小原理等理论框架进一步推广，产生新的学习算 法或改进算法。 ( 2 ) 完善s v m 方法。s 叩p o nv c c t o 巧的确定可转化为约束的优化问题，但当训 练集的规模很大时，传统的优化方法难以满足实时性要求，如何设计快速有效算 法是s 、，i h 中的重要问题之一。 ( 3 ) 基于s v m 算法的多类别分类方法。 ( 4 ) 对非线性分类问题，s v m 的核方法仍有一些理论缺陷。 ( 5 ) 在s v m 的应用研究方面，由于s v m 算法是对神经网络学习算法、最小二 乘法的改良，尚需要大量应用到实际问题中去，如建模、参数辨识和自适应控制 等问题，并将它与已有的处理结果进行比较和分析，以便进一步深入研究。 目前主要对支持向量机理论如下的主要内容进行研究：各种改进的支持向量 机新算法