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

华东师范丈学汁算机系硕士学位论文支持向量机在中医指症数据挖掘中的应用研究 摘要 中医药作为中华民族特有的文化和科学遗产，对世界有着重大的贡献。但由于不同的社 会背景和研究方法，中医还未得到现代医学的广泛承认，中医药的有效性和科学性还需要用 实际数据来证明。面对大量的数据和数据间复杂的关系，传统的分析手段已无能为力。 数据挖掘作为一种融合了人工智能、数据库和数理统计等学科特点的新兴技术，却善于 从这种大量的、复杂的数据中迅速获取新颖、有效的知识。能够弥补传统的分析方法在中医 药研究方面的不足。相应地，寻找一种快速有效的数据挖掘算法就变得非常必要。支持向量 机作为一种新兴的统计学习算法，以其优秀的理论基础( 结构误差理论，条件二次优化理论 和核空间理论) 脱颖而出。 本文首先讨论了数据挖掘的基本概念，关键技术，挖掘任务，挖掘方法，基本过程以及 发展状况。然后在研究了支持向量机的理论基础及基本概念和要解决的关键技术问题之后 又对当前各种比较通用的支持向量机训练算法进行了研究，比较了各种算法的优劣，尤其深 入研究了p l a t t 等人的s m o ( s e q u e n t i a lm i n i m a lo p t i m i z a t i o n ) 算法指出这种s m o 算 法低效的主要原因是采用了单一的阐值参数，然后参考k e e m h i 等人的思想，提出了一种使 用两个阅值参数的改进的s m o 算法在u c i 数据集和我们的i g a 肾病数据集上的试验结 果表明，这种改进的s m 0 算法在训练速度上有一定的提高。 本文还针对中医样本数据特征多的特点，提出了一种新的方法，将粗糙集( r o u g h s e t ) 应用于中医指症数据挖掘的预处理阶段，在不影响分类精度的前提下，对样本数据进行属性 约简，这样经过约简以后的样本在样本训练阶段可以明显地提高训练速度。 最后给出一种以支持向量机为核心的中医指症数据挖掘方案。基本设计完成了中医指症 数据挖掘原型系统。 关键词：数据挖掘，支持向量机，s m o 算法，粗糙集 o # 东师范大学计算机系硕士学位论文支持向量机在中医指症数据挖掘中的应用研究 a b s t r a c t a l t h o u g hc h i n e s em e d i c i n eh a sb e e nc o n s i d e r e dv a l u a b l ei na p p l i c a t i o n s ，i t st h e o r i e sa n d m e t h o d sh a v en o tb e e na c c e p t e dw i d e l yb ym o d e r nm e d i c i n ea si th a sl i t t l ep r e c i s ed a t ad e r i v e d f r o ms c i e n t i f i ce x p e r i m e n t st op r o v ei t s v a l i d i t ya n ds a f e t y i tw i l l b eb e n e f i c i a lf o r t h e d e v e l o p m e n ta n de x t e n s i o no fc h i n e s em e d i c i n ei fw ec a l ld i s c o v e rs o m er e l a t i o n s h i pb e t w e e n c l i n i c a ls y m p t o m sa n dd i a g n o s i s i ti sv e r yd i f f i c u l tt oa c h i e v et h i sg o a lm a n u a l l yb e c a u s eo f c o m p l i c a t e dk n o w l e d g eo f c h i n e s em e d i c i n ea n dv o l u m e so f d a t a b e i n gac l a s so fa u t o m a t i ca n di n t e l l i g e n td a t aa n a l y s i st e c h n i q u e s ，d a t am i n i n g ，a l s oc a l l e d k d d ，w h i c ha i n l sa te x t r a c t i n gn o v e la n du s e f u lk n o w l e d g ef r o ml a r g ev o l u m e so fd a t a ，h a s e m e r g e dm p i d l yi nr e c e n tt e ny e a r s s u p p o r tv e c t o rm a c h i n eh a sb e c o m eo n eo fr i s i n gd a t a m i n i n gt e c h n i q u e sb e c a u s eo f i t se x c e l l e n tt h e o r y i nt h i st h e s i sw ef i r s t l yo v e r v i e wd a t am i n i n gt e c h n i q u e s ，m a k i n gab r i e fd e s c r i p t i o na b o u t t h ec o n c e p t ，b a s i cm o d e l ，t y p i c a ls t r u c t u r e ，a n ds o m ep o p u l a rt e c h n i q u e so fd a t am i n i n g t h e nw e f o c u so ns u p p o r tv e c t o rm a c h i n ea n dd i s c u s si t st h e o r yf o u n d a t i o n ，b a s i cc o n c e p t s ，a n dc r u c i a l t e c h n i q u e so fs u p p o r tv e c t o rm a c h i n e w i t ht h e s eb a c k g r o u n d , w ef u m l e rs t u d ys e v e r a lg e n e r a l l y a l g o r i t h m sa b o u ts u p p o r tv e c t o rm a c h i n e ，e s p e c i a l l y f o rp l a t t l ss m o ( s e q u e n t i a lm i n i m a l o p t i m i z a t i o n ) a l g o r i t h m p o i n t so u ta ni m p o r t a n ts o l a c eo fi n e f f i c i e n c y i np l a r t s s e q u e n t i a l m i n i m a lo p t i m i z a t i o n ( s m o ) a l g o r i t h mt h a ti sc a u s e db yt h ed s eo f as i n g l ev a l u e ，t h e np r e s e n ta n i m p r o v e ds m oa l g o r i t h me m p l o y e dt w ot h r e s h o l dp a r a m e t e r s e x p e r i m e n t sd e m o n s t r a t et h e u n p r o v e ds m oa l g o r i t h mp e r f o r m sf a s t e rt h a no r i g i n a ls m oa l g o r i t h mo nu c id a t a s e t sa n do u r n e p h r o p a t h yd a t a s e t s a n dan e wp r e p r o c e s s i n gm e t h o du s i n gr o u g hs e tt h e o r yi sp r e s e n t e di nt h i st h e s i s ，a i m i n ga t t h ec h a r a c t e r i s t i co ft r a d i t i o n a lc h i n e s em e d i c i n e t h er e s u l to fe x p e r i m e n t si ss a t i s f i e dw i t hu s i nt h el a s tp a r to ft h i st h e s i s ，w ep r o p o s eap r o t o t y p ed a t am m i n gs y s t e mb a s e do ns u p p o r t v e c t o rm a c h i n e t h ec a s es t u d yo nan e p h r o p a t h yd a t a s e ti l l u s t r a t et h ep r o m i s eo fs u p p o r tv e c t o r r r 血c h i n eb a s e dd a t am i n i n gt e c h n i q u e si nc h i n e s em e d i c i n e k e y w o r d s ：d a t am i n i n g ，s u p p o r tv e c t o rm a c h i n e ，s e q u e n t i a lm i n i m a lo p t i m i z a t i o n a l g o r i t h m , r o x l g hs e t 华东师范大学计算机系硕十学位论文支持向量机在中医指症数据挖掘中的应用研究 第一章引言 数据挖掘( d a t am i n i n g ) 是近年来的热门话题之一。由于电脑、网络技术的飞速发展， 人仃j 收集到的资料、数据越来越多，面对着庞大的数据，如何从中获取所需要的信息，就成 了一个迫切需要解决的问题。统计分析、人工智能、数据库这些技术的发展为解决这一问 题准备了良好的条件，数据挖掘技术在这个基础上就应运而生了。而它与中医的研究工作又 有什么联系呢? 1 1 中医研究面临的问题 人类获得知识都是从经验上升为理论，然后不断为实践所证实，理论形成的初期往往是 一种假说，经过实践的不断证实成为众人能接受的理论。同样的道理也适合于疾病诊断。疾 病总是通过相关症状、体征表现出来1 2 5 】，古人在观察的基础上总结了这一规律，并逐渐上 升为理论，形成如今所言的“证”，辨证诊断的过程就是在相关症状体征中提取规则的过程。 但是，由于患者个体的特殊性带来症状的多样性使建立在经验和思辨基础上的“证”很难 标准化。仅凭经验的观察难免有个人经验主义的缺陷临床上就常有按名中医个案经验重复 应用有时有效、有时无效的情况，给中医“证”的学习掌握、临床应用以及走向世界带来很 大困难，中医“证”的研究其重要性由此可见一斑。如何从中医学大量现象描述中揭示出内 在规律，正是当今“证”研究的热点与难点。而且中医中经常遇到定性资料，如舌苔的颜色、 脉象的疾缓等等，我们需要把它们量化，量化后再按定量资料的方法来分析。 中医也可以依证分类，依病分类，它们之间的关系，有一致的，也有不一致的一种症 状或证候，可能是好几种疾病都有的，一种病也有各种症状或证候。那么它们之间的关系究 竟是怎样的呢? 人们可能很自然的会联想到曾经使人工智能研究工作者在应用领域发挥过 重大作用的专家系统。然而由于专家系统知识获取的主要手段是依靠领域专家，而当面对大 量的数据和数据间复杂的关系时领域专家就显得无能为力了，这己成为制约专家系统发展 的“瓶颈”。如能有效的利用数据挖掘技术，在不借助或较少借助医学专家的情况下能从人 量数据中得到可以接受的知识，将极大地促进传统中医的发展。 1 2 数据挖掘( d m ) 是解决这一问题的有效方法之一 d m 中有一项内容，就是寻找事物之间的联系，其中常被引用的一个例子，就是对超市 购物者资料进行分析时，发现买啤酒的人通常还要买尿布，这在一般情况下是不易发现的， 发现后又感到很易于理解。 中医有着悠久漫长的历史，积累的历史资料非常多，将d m 技术用于这一领域，一定 会有一些新的创造性的发现。如果我们手上有大量的病例，那么d m 就能帮你把这些关系 弄明白，当病例的数目大到一定的时候归纳出来的结论是可以让人信服的。当然也存在一 华东师范大学计算机系硕士学位论文支持向量机在中医指症数据挖掘中的应用研究 个问题，由于我们得到的这些病例都是非计算机专业的医护人员收集的，而且来源复杂，多 样，数据存在不一致性。所以，我们必须要有一个数据清理、整合、集成、变换、归约的过 程。这正是数据挖掘中的预处理所要解决的问题。 1 3 选用支持向量机( s u p p o r tv e c t o rm a c h i n e ) 方法的原因 对中医数据处理的方法有多种而本文侧重于使用支持向量机( s v m ) 来解决数据处 理中的知识获取问题，这是园为支持向量机和传统的分类方法相比有以下优点： 1 它是专门针对有限样本情况的，其目标是得到现有信息下的最优解而不仅仅是样本 数趋于无穷大时的晟优值： 2 ，算法最终将转化成为一个二次型寻优问题，从理论上说，得到的将是全局最优点， 解决了在神经网络方法中无法避免的局部极值问题； 3 算法将实际问题通过非线性变换转换到高维的特征空间( f e a t u r es p a c e ) 在高维空 间中构造线性判别函数来实现原空间中的非线性判别函数，这种特殊性质能保证学习机器有 较好的推广能力，同时也巧妙地解决了维数问题。 4 在s v m 方法中只要定义不同的内积函数，就可以实现多项式逼近、贝叶斯分类 器、径向基函数( r a d i a lb a s i cf u n c t i o n 或r b f ) ：法、多层感知器网络等许多现有学习算法。 i 4 本文的主要工作 本文首先讨论了数据挖掘的基本概念，关键技术，挖掘任务，挖掘方法，基本过程以及 发展状况。然后在研究了支持向量机的理论基础及基本概念和要解决的关键技术问题之后， 又对当前各种比较通用的s v m 训练算法进行了研究，比较了各种算法的优劣，尤其深入研 究了p l a t t 等人的s m o ( s e q u e n t i a lm i n i m a lo p t i m i z a t i o n ) 算法，指出这种s m 0 算法还 可以改进的地方，最后参考k e er t h i 等人的思想提出了一种改进的s m o 算法，试验结果 表明，这种改进的s m 0 算法在训练速度上有一定的提高。 本文还针对中医样本数据特征多的特点，提出了一种新的思想将粗糙集( r o u g h s e t ) 应用于中医指症数据挖掘的预处理阶段。在不影响分类精度的前提下，对我们的样本数据进 行属性约简，这样经过约简以后的样本在样本训练阶段可以明显地提高训练速度。 最后提出一种以支持向量机为核心的中医指症数据挖掘方案。基本设计完成了中医指症 数据挖掘原型系统。 1 5 本文的组织结构 第一章为引言，介绍了论文选题的背景和论文的主要研究工作。第二章综述了数据挖掘 的基本概念、关键技术以及发展状况。第三章阐述了支持向量机的理论基础及其基本原理。 第四章对s v m 的训练算法进行研究。主要讨论s v m 的几种基本训练算法，重点讨论了s m o 算法，并且针对s m o 算法学习效率低的主要原因，给出一种改进的s m o 算法。第五章分 毕东师范大学计算村i 系硕士学位论文支持向量机在中医指症数据挖掘中的应用研究 析了s v m 的算法复杂度，认为虽然s v m 通过核函数巧妙地解决了样本维数问题，但我们 研究发现s v m 的算法复杂度仍然和样本维数有关，基于这点认识，用r o u g h s e t 对我们 的中医样本进行属性选择。将些冗余的属性约简掉，实验结果表明这种预处理方法对样本 的训练速度有很大的提高。第六章为原型系统的设计与实现。从数据挖掘过程中的各个阶段 出发，提出了一个有效的针对中医指症数据集的数据挖掘方案。并以收集的i g a 肾病数据 集为例，给出了数据挖掘各个阶段的效果图。第七章则总结了本文的主要工作和存在的问题， 并展望了进一步工作的研究方向。 华东师范大学计算机系硕上学位论j 支持向量机在中医指症数据挖掘中的应用研究 第二章数据挖掘综述 近十几年来，人们利用信息技术生产和搜集数据的能力大幅度提高，千千万万个数据库 被用于商业管理、政府办公、科学研究和工程开发等等，并且这一势头仍将持续发展下去。 于是，一个新的挑战被提了出来：在这被称之为信息爆炸的时代信息过量几乎成为人人需 要面对的问题。如何才能不被信息的汪洋大海所淹没，从中及时发现有用的知识，提高信息 利用率呢? 要想使数据真正成为一个公司的资源，只有充分利用它为公司自身的业务决策和 战略发展服务才行，否则大量的数据可能成为包袱。甚至成为垃圾。因此，面对“人们被数 据淹没，却饥饿于知识”的挑战，数据挖掘技术应运而生，蓬勃发展。并且在很多领域已经 得到了非常成功的应用，例如加拿大b c 省电话公司和加拿大s i m o n f r a s e r 大学数据挖掘 研究组合作，根据其拥有十多年的客户数据，总结、分析并提出了新的电话收费和管理办法， 制定出了既有利于公司又有利于客户的一系列的优惠政策。下面再来看这样一份报告。 2 0 0 0 年7 月，i d c 发布了有关信息，l 竽取工具市场的报告。1 9 9 9 年，数据挖掘市场大概 约为75 亿美元，估计在下个5 年内市场的年增长率为3 2 4 ，其中哑太地区为2 6 6 。 到2 0 0 2 年，该市场会发展到2 2 亿美元1 3 5 。据国外专家预测，随着数据量的日益积累和计 算机的广泛应用，在今后的5 1 0 年内，数据挖掘将在中国形成一个新型的产业。 2 1 数据挖掘技术概述 本部分主要介绍数据挖掘的基本概念、发展状况以及基本过程。 2 1 1 数据挖掘的概念 数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、随机的数据中， 提取隐含在其中的、人仃j 事先不知道的、但又是潜在有用的信息和知识的过程【8 】。发现知 识的方法可以是数学的，也可以是非数学的：可以是演绎的，也可以是归纳的。发现的知识 可以被用于信息管理、查询优化、决策支持、过程控制等还可以用于数据自身的维护。因 此，数据挖掘是一门很j 义的交叉学科，它汇聚了不同领域的研究者，尤其是数据库、人j 二 智能、数理统计、可视化、并行计算等方面的学者和工程技术人员。 特别要指出的是，数据挖掘技术从一开始就是面向应用的。它不仅是面向特定数据库的 简单检索查询调用，而且要对这些数据进行微观、中观乃至宏观的统计、分析、综合和推理， 以指导实际问题的求解，企图发现事件间的相互关联，甚至利用已有的数据对未来的活动进 行预测。这样一来就把人们对数据的应用，从低层次的末端查询操作，提高到为各级经营 决策者提供决策支持。这种需求驱动力，比数据库查询更为强大。同时需要指出的是，这里 所说的知识友现，不是要求发现放之四海而皆准的真理也不是要击发现崭新的自然科学定 理和纯数学公式，更不是什么机器定理证明。所有发现的知识都是相对的，是有特定前提和 约束条件、面向特定领域的，同时还要能够易于被用户理解，最好能用自然语言表达发现结 4 华东师范人学计算机系硕上学位论文支持向量机在中医指症数据挖掘中的应用研究 果。冈此数据挖掘的研究成果是很讲求实际的。 2 1 2 数据挖掘研究现状 数据挖掘，有时也称为知识发现( k n o w l e d g e d i s c o v e r y ) ，简称为k d d 。k d d 一词首 次出现在1 9 8 9 年8 月举行的第1 1 届国际联合人工智能学术会议上。迄今为止，由美国人 工智能协会主办的k d d 国际研讨会已经召开了1 3 次，规模由原来的专题讨论会发展到国 际学术大会，人数由二三十人到七八百人，论文收录比例从2 ：1 到6 ：1 ，研究重点也逐渐从 发现方法转向系统应用，并且注重多种发现策略和技术的集成，以及多种学科之间的相互渗 透。其他内容的专题会议也把数据挖掘和知识发现列为议题之一，成为当前计算机科学界的 一大热点。 聆自着数据挖掘的研究逐步走向深入，人们越来越清楚地认识到，数据挖掘的研究主要有 3 大技术支柱，即数据库、人 二智能和数理统计 8 】。 1数据库技术。 s q l 统治数据库查询语言标准三十多年这一事实本身就与现在信息技术发展的节拍 不符，难道我们“只会查询”吗? 数据库最实质的应用仅仅是查询吗? 理论根基最深的关系 数据库晟本质的技术进步点，就是数据存放和数据使用之间的相互分离。查询是数据库的奴 隶发现才是数据库的主人。所以就有很多专家纷纷转向数据仓库与数据挖掘技术，从数据 查询转向数据挖掘、从数据演绎转向数据归纳。 2 人工智能技术。 人工智能技术的二大难题：“知识获取、知识表示、缺乏常识”直接制约了它在现实技 术市场上的作为。而在与数据仓库技术的结合上，它可以发挥重要作用，这使得它转向数据 挖掘技术。 3概率与数理统计。 数理统计技术是应用数学中最重要、最活跃的学科。但在与数据库技术的结合上作为有 限，这从s q l 中那可怜的几条汇总函数便可看出。随着数据挖掘对查询、归纳对演绎需求 的进化，概率与数理统计将获得新的生命力。 2 1 3 数据挖掘的基本过程 华东师范大学计算机系硕十学位论文支持向量机在中医指症数据挖掘中的应用研究 图2 1 数据挖掘过程 数据挖掘的过程描述如下： 1 确定业务对象 清晰地定义出业务问题，认清数据挖掘的目的是数据挖掘的重要一步。挖掘的最后结构 是不可预测的，但要探索的问题应是有预见的，为了数据挖掘而数据挖掘则带有盲目性的， 也是不会成功的。 2 数据准备 ( 1 ) 数据的选择 搜索所有与业务对象有关的内部和外部数据信息并从中选择出适用于数据挖掘应 用的数据。 ( 2 ) 数据的预处理 研究数据的质量，为进一步的分析作准备。并确定将要进行的挖掘操作的类型。 ( 3 ) 数据的转换 将数据转换成一个分析模型，这个分析模型是针对挖掘算法建立的，建立一个真正 适合挖掘算法的分析模型是数据挖掘成功的关键。 3 数据挖掘 对所得到的经过转换的数据进行挖掘。除了完善从选择合适的挖掘算法外，其余一 切工作都能自动地完成。 4 结果分析 解释并评估结果。其使用的分析方法一般应作数据挖掘操作而定通常会用到可视 化技术。 5 知识的同化 将分析所得到的知识集成到业务信息系统的组织结构中去。 2 2 数据挖掘的挖掘任务 在介绍了数据挖掘的基本概念和数据挖掘的基本过程之后，我们再来看数据挖掘的挖掘 任务。 数据挖掘的任务就是发现隐含在数据当中，可以为人们所用的知识。数据挖掘所能发现 的知识有如下几种：广义型知识，反映同类事物共同性质的知识；特征型知识，反映事物各 方面的特征知识；差异型知识，反映不同事物之间属性差别的知识；关联型知识，反映事物 之间依赖或关联的知识：预测型知识根据历史的和当前的数据推测未来数据：偏离型知识， 揭示事物偏离常规的异常现象。 从挖掘任务和挖掘方法的角度看我们认为数据抽取、分类、聚类和关联规则的发现是 数据挖掘的主要挖掘任务。 1 、数据抽取 华东帅范大学计算机系硕士学位论文 支持同量机在中医指疰数据挖掘中的应用研究 数据抽取的目的是对数据进行浓缩，给出它的紧凑描述。传统的也是最简单的数据抽取 方法是计算出数据库的各个字段上的求和值、平均值、方差值等统计值，或者用直方图、饼 状图等图形方式表示。数据挖掘主要关心从数据泛化的角度来讨论数据总结。数据泛化是一 种把数据库中的有关数据从低层次抽象到高层次上的过程。由于数据库上的数据或对象所包 含的信息总是最原始、基本的信息、( 这是为了不遗漏任何可能有用的数据信息) 。人们有时希 望能从较高层次的视图上处理或浏览数据，因此需要对数据进行不同层次上的泛化以适应各 种查询要求。数据泛化目前主要有两种技术：多维数据分析方法和面向属性的归纳方法。 多维数据分析方法是一种数据仓库技术，也称作联机分析处理( o l a p ) 。数据仓库是面 向决策支持的、集成的、稳定的、不同时问的历史数据集合。决策的前提是数据分析。在数 据分析中经常要用到诸如求和、总计、平均、最大、最小等汇集操作，这类操作的计算量特 别大。因此一种很自然的想法是把汇集操作结果预先计算并存储起来，以便于决策支持系 统使用。存储汇集操作结果的地方称作多维数据库。 采用多维数据分析方法进行数据抽取，它针对的是数据仓库，数据仓库存储的是脱机的 历史数据。为了处理联机数据，研究人员提出了一种面向属性的归纳方法。它的思路是，直 接对用户感兴趣的数据视图( 用一般的s q l 查询语言即可获得) 进行泛化而不是像多维数 据分析方法那样预先就存储好了泛化数据。方法的提出者对这种数据泛化技术称之为面向属 性的归纳方法。原始关系经过泛化操作后得到的是一个泛化关系，它从较高的层次上总结了 在低层次上的原始关系。有了泛化关系后，就可以对它进行各种深入的操作而生成满足用户 需要的知识，如在泛化关系基础上生成特性规则、判别规则、分类规则，以及关联规则等。 2 、分类发现 分类在数据挖掘中是一项非常重要的任务，目前的应用也最为广泛。分类的目的是找到 一个分类函数或分类器该模型能把数据库中的数据项映射到给定类别中的某一个。分类和 同归都可用了预测。预测的目的是从利用历史数据纪录中自动推导出对给定数据的推广描 述，从而能对未来数据进行预测。和回归方法不同的是，分类的输出是离散的类别值，而回 】= 1 的输出则是连续数值。这里我们将不讨论回归方法。 要构造分类器，需要有一个训练样本数据集作为输入。训练集由一组数据库记录或元组 构成，每个元组是一个由有关字段( 又称属性或特征) 值组成的特征向量此外，训练样本还 有一个类别标记。一个具体样本的形式可为：( 0 1 ，v 2 ，v 。：c ) ：其中v 表示字段值，c 表示类别。 分类器的构造方法有统计方法、机器学习方法、神经网络方法，支持向量机方法等等。 统计方法包括贝叶斯法和非参数法( 近邻学习或基于事例的学习) ，对应的知识表示则为判别 函数和原型事例。机器学习方法包括决策树法和规则归纳法，前者对应的表示为决策树或判 别树，后者则一般为产生式规则。神经网络方法主要是b p 算法，它的模型表示是前向反馈 神经网络模型( 由代表神经元的节点和代表聪接权值的边组成的一种体系结构) ，b p 算法本 质上是一种非线性判别函数。最近，又兴起了一种新的方法：支持向量机( s u p p o r t v e c t o r 华东师范大学计算机系硕士学位论文 支持向量机在中医指症数据挖掘中的应用研究 m a c h i n e ) ，它是建立在统计学习理论基础之上的优秀的分类方法，克服了神经网络所无法 避免的诸多缺点( 如陷入局部极小点过学习问题等) ，现在，s v m 正越来越多地受到人们 的重视，也开始逐步地应用到各个领域。 另外要注意的是，分类的效果一般和数据的特点有关，有的数据噪声大，有的有缺失值， 有的分布稀疏，有的字段或属性间相关性强，有的属性是离散的而有的是连续值或混台式的。 目前普遍认为不存在某种方法能适合于各种特点的数据。 3 、聚类 聚类是把一组个体按照相似性归成若干类别，它的目的是使得属于同一类别的个体之间 的距离尽可能的小，而不同类别上的个体间的距离尽可能的大。聚类方法包括统计方法、机 器学习方法、神经网络方法和面向数据库的方法。 在统计方法中，聚类称聚类分析，它是多元数据分析的三大方法之一( 其它两种是回归 分析和判别分析) 。它主要研究基于几何距离的聚类，如欧式距离、明可夫斯基距离等。传 统的统计聚类分析方法包括系统聚类法、分解法、加入法、动态聚类法、有序样品聚类、有 重叠聚类和模糊聚类等。这种聚类方法是一种基于全局比较的聚类，它需要考察所有的个体 才能决定类的划分：因此它要求所有的数据必须预先给定，而不能动态增加新的数据对象。 聚类分析方法不具有线性的计算复杂度，难以适用于数据库非常大的情况。 在机器学习中聚类称作无监督或无教师归纳；因为和分类学习相比，分类学习的样本或 数据对象有类别标记，而要聚类的例子则没有标记，需要由聚类学习算法来自动确定。很多 人工智能文献中，聚类也称概念聚类；因为这里的距离不再是统计方法中的几何距离而是 根据概念的描述来确定的。当聚类对象可以动态增加时，概念聚类则称是概念形成。 4 关联规则发现 关联规则是形式如下的一种规则“在购买面包和黄油的顾客中，有9 0 的人同时也买 了牛奶”( ( 面包+ 黄油) 一牛奶) 。用于关联规则发现的主要对象是事务型数据库其中针 对的应用则是售货数据，也称货篮数据。一个事务一般由如f 几个部分组成：事务处理时间， 一组顾客购买的物品，有时也有顾客标识号如信用譬号) 。 由于条形码技术的发展，零售部门可以利用前端收款机收集存储大量的售货数据。因此， 如果对这些历史事务数据进行分析则可对顾客的购买行为提供极有价值的信息。最经典的 关联规则方面的挖掘是众所周知的啤酒和尿布的故事。由此可见从事务数据中发现关联规 则，对于改进零售业等商业活动的决策非常重要。 2 3 数据挖掘系统的评价标准 如何评价一个数据挖掘系统的优劣呢? 需要从以下几个方面来考虑： 1 产生的模式种类的多少 2 解决复杂问题的能力 数据量的增大，对模式精细度、准确度要求的增高都会导致问题复杂性的增大。数据挖 。仁东师范大学计算机系硕上学位论文 支持向量机在中医指症数据挖掘中的应用研究 掘系统可咀提供下列方法解决复杂问题： 多种模式多种类别模式的结合使用有助于发现有用的模式，降低问题复杂性。例如，首 先用聚类的方法把数据分组，然后再在各个组上挖掘预测性的模式，将会比单纯在整个数据 集上进行操作更有效、准确率更高。 多种算法很多模式，特别是与分类有关的模式可以有不同的算法来实现，各有各的优 缺点，适用于不同的需求和环境。数据挖掘系统提供多种途径产生同种模式，将更有能力解 决复杂问题。验证方法在评估模式时，有多种可能的验证方法。比较成熟的方法像n 层交 叉验证或保持法等可以控制，以达到最大的准确度。 数据选择和转换模式通常被大量的数据项隐藏。有些数据是冗余的，有些数据是完全无 关的。而这些数据项的存在会影响到有价值的模式的发现。数据挖掘系统的一个很重要功能 就是能够处理数据复杂性提供工具，选择正确的数据项和转换数据值。 可视化工具提供直观、简洁的机制表示大量的信息。这有助于定位重要的数据，评价模 式的质量，从而减少建模的复杂性。扩展性为了更有效地提高处理大量数据的效率，数据 挖掘系统的扩展性十分重要。需要了解的是：数据挖掘系统能否充分利用硬件资源? 是否支 持并行计算? 算法本身设计为并行的还是利用了d b m s 的并行性能? 支持哪种井行计算 机，s m p ( s y m m e t n cm u l t ip r o c e s s i n g ) 服务器还是m p p ( m a s s i v e l yp a r a l l e lp r o c e s s i n g ) 服务器? 当处理器的数量增加时，计算规模是否相应增长? 是否支持数据并行存储? 为单处理器的计算机编写的数据挖掘算法不会在并行计算机上自动以更快的速度运行。 为充分发挥并行计算的优点需要编写支持并行计算的算法。 3 易操作性 易操作性是一个重要的因素。有的工具有图形化界面，引导用户半自动化地执行任务， 有的使用脚本语言。有些工具还提供数据挖掘的a p i ，可以嵌入到像v i s u a l b a s i c 、d e l p h i 这样的编程语言中。 模式可以延用到已存在或新增加的数据上。有的工具有图形化的界面有的允许通过使 用c 这样的程序语言或s q l 中的规则集，把模式导出到程序或数据库中。 4 数据存取能力 。好的数据挖掘工具可以使用s q l 语句直接从d b m s 中读取数据。这样可以简化数据准 备工作并且可以充分利用数据库的优点( 比如平行读取) 。没有一种工具可以支持大量的 d b m s ，但可以通过通用的接口连接大多数流行的d b m s 。m i c s 矾的o d t 3 , c 就是一个这 样的接口。 5 与其他产品的接口 有很多别的工具可以帮助用户理解数据，理解结果。这些工具可以是传统的查询工具、 可视化工具、o l a p 工具。数据挖掘工具是否能提供与这些工具集成的简易途径? 因为数据挖掘工具需要考虑的因素很多很难按照原则给工具排一个优劣次序。最重要 的还是用户的需要，根据特定的需求加以选择。数据挖掘工具可以给很多产业带来收益。国 o # 东师范大学计算机系颁二卜学位论文 支持向量机在中医指症数据挖掘中的应用砂究 外的许多行业如通信、信用卡公司、银行和股票交易所、保险公司、广告公司、商店等已经 大量利用数据挖掘工具来协助其业务活动，国内在这方面的应用还处于起步阶段，对数据挖 掘技术和工具的研究人员以及开发商来说，我国是一个有巨大潜力的市场。 华东师范大学计算机系硕士学位论文 支持向量机在中医指症数据挖掘中的啼j 用研究 第三章s v m 概述 s v m ，即支持向量机( s u p p o dv e c t o rm a c h i n e ) 是v a p n i k 根据统计学习理论提出的 一种新的学习方法，近年来受到了国际学术界的重视 2 9 ，5 1 。支持向量机理论的晟大特点是 根据结构风险晟小化准则，尽量提高学习机的泛化能力即由有限的训练样本集得到的小的 误差能够保证对独立的测试集仍保持小的误差。另外由于支持向量机算法是一个凸优化问 题，因此局部最优解一定是全局最优解。对于分类问题，支持向量机算法根据区域中的样本 计算该区域的决策曲面，由此确定该区域中未知样本的类别。对于估值问题，支持向量机算 法对区域中的样本进行回归，确定该区域的映射函数从而得到该区域中未知样本的取值。 s v m 的基本思想是通过某种事先选择的非线性映射将输入向量映射到一个高维特征空间， 在这个空间中构造最优分类超平面。在高维特征空问中构造最优超平面，只需要计算特征向 量与特征空间中向量的内积，然后使用某种核函数在原空间计算就可以了。从而克服了维数 困难。通过选用不同的核函数，可以构造输入空间中不同类型的非线性决策面的学习机。 3 1 支持向量机的理论基础 本小节主要讨论支持向量机的理论基础统计学习理论。给出经验风险，结构风险， v c 维( v a p n i k c h e r v o n e n k i sd i m e n s i o n ) 以及置信范围的基本概念。 3 1 1 机器学习的基本问题 基于数据的机器学习是现代智能技术中的重要方面，研究从观测数据( 样本) 出发寻找 规律，利用这些规律对未来数据或无法观测的数据进行预测。迄今为止，关丁二机器学习还没 有一种被共同接受的理论框架，关于其实现方法大致可以分为三种： 第一种是经典的参数统讨估训方法。包括模式识别、神经网络等在内，现有机器学习方 法共同的重菩理论基础之一是统计学。参数方法正是基于传统统计学的，在这种方法中，参 数的相关形式是己知的，训练样本用米估计参数的值。这种方法有很大的局限性，首先，它 需要己知样本分布形式，这需要花费很大代价，还有传统统计学研究的是样本数目趋于无 穷大时的渐近理论，现有学习方法也多是基于此假设。但在实际问题中样本数往往是有限 的，因此一些理论上很优秀的学习方法实际中表现却可能不尽人意。 第二种方法是经验非线性方法，如人工神经网络( a n n ) 。这种方法利用已知样本建立 非线性模型克服了传统参数估计方法的困难。但是，这种方法缺乏一种统一的数学理论。 3 1 2 问题的表示 机器学习的目的是根据给定的训练样本求对某系统输入输出之间依赖关系的估计，使它 能够对未知输出作出尽可能准确的预测。可以一般地表示为：变量y 与存在定的未知 依赖关系，即遵循某一未知的联合概率f ( x ，y ) ，( x 和y 之间的确定性关系可以看作是其 1 1 华东师范大学计算机系硕士学位论文支持向量机在中医指症数据挖掘中的应用研究 特例) ，机器学习问题就是根据n 个独立分布观测样本 ( x 1 y 1 ) ( x 2 ，y 2 ) ，( ) ( i 、，y n ) ( 3 1 ) r ( 们= i l ( y ，f ( x ，w ) ) d f ( x ，y ) ( 3 - 2 ) ， 在一组函数 f ( x ，w ) ) 中求一个最优的函数f ( x w o ) 对依赖关系进行估计，使期望风险( 3 - 2 式) 最小。其中， f i x ，w ) ) 称作预测函数集，w 为函数的广义参数， f i x w ) ) 可以表示任何 函数集；l ( y ，f ( x ，w ) ) 为由于用f ( x ，w ) 对y 进行预测而造成的损失。不同类型的学习问题有 不同形式的损失函数。预测函数我们也称作学习函数、学习模型或学习机器。 有三类基本的机器学习问题，即模式识别、函数逼近和概率密度估计。对模式识别问题， 输出y 是类别标号，两类情况fy = 0 ，1 ) 或( 1 - 1 ) ，预测函数称作指示函数，损失函数 可以定义为 l ( y f ( x w ) ) = o i f y ：f ( x ，w ) ， ( 3 - 3 a ) l ( h f ( x ，w ) ) = 1 ， f y f ( ，w )( 3 - 3 b ) 在函数逼近问题中，y 是连续变量( 这里假设为单值函数) ，损失函数可定义为 l ( y ，f ( x w ) ) = ( y - f ( x w ) ) ( 3 _ 4 ) 即采用最小平方误差准则。而对概率密度估计问题，学习的目的是根据训练样本确定x 的概率密度。记估计的密度函数为p ( x w ) ，则损失函数可以定义为 l ( p ( x w ) ) - - i o g p ( x ，w ) 。 ( 3 - 5 ) 3 1 3 经验风险最小化( e x p e r i e n c er i s km i n i m i z a t i o n ，e r m ) 在上面的问题表述中，学习的目标在于使期望风险最小化，但是，由于我们可以利用的 信息只有样本( 3 - 1 ) ，( 3 2 ) 式的期望风险并无法计算，因此传统的学习方法中采用了所谓 经验风险最小化( e r m ) 准则即用样本定义经验风险 ( w ) = 去喜m 删( 3 - 6 ) 作为对( 3 2 ) 式的估计，设计学习算法使它最小化。对损失函数( 3 - 3 ) ，经验风险就 是训练样本错误率；对( 3 - 4 ) 式的损失函数，经验风险就是平方训练误差：而采用( 3 - 5 ) 式损 失函数的e r m 准则就等价于最大似然方法。 事实上，用e r m 准则代替期望风险最小化并没有经过充分的理论论证，只是直观上台 理的想当然做法，但这种思想却在多年的机器学习方法研究中占据了主要地位。人们多年来 将大部分注意力集中到如何更好地最小化经验风险上，而实际上，即使可以假定当n 趋向 于无穷大时( 3 6 ) 式趋近于( 3 2 ) 式，在很多问题中的样本数目也离无穷大相去甚远。那么 在有限样本下e r m 准则得到的结果能使真实风险也较小吗? 华东师范大学计算机系预七学位论文支持向量机在中医指症数据挖掘中的应用研究 3 1 4 复杂性与推广能力 e r m 准则不成功的一个例子是神经网络的过学习问题。开始，很多注意力都集中在如 何使r e m p ( w ) 更小，但很快就发现，训练误差小并不总能导致好的预测效果。某些情况下， 训l 练误差过小反而会导致推广能力的下降，即真实风险的增加，这就是过学习问题。之所以 出现过学习现象，一是因为样本不充分二是学习机器设计不合理，这两个问题是互相关联 的。设想一个简单的例子，假设有一组实数样本 x y ) ，y 取值在【0 11 之间，那么不论 样本是依据什么模型产生的，只要用函数f ( x ，口) = s i n ( a x ) 去拟合它们( c t 是待定参数) ， 总能够找到一个a 使训练误差为零，但显然得到的“最优”函数并不能正确代表真实的函数 模型。究其原因，是试图用一个十分复杂的模型去拟合有限的样本，导致丧失了推广能力。 在神经网络中，若对有限的样本来说网络学习能力过强，足以记住每个样本，此时经验风险 很快就可以收敛到很小甚至零，但却根本无法保证它对未来样本能给出好的预测。学习机器 的复杂性与推广性之间的这种矛盾同样可以在其它学习方法中看到。文献给出了一个实验例 子，在有噪声条件下用模型y = x 2 产生1 0 个样本，分别用一个一次函数和一个- 二次函数 根据e r m 原则去拟合，结果显示，虽然真实模型是二次但由于样本数有限且受噪声的影 响用一次函数预测的结果更好。同样的实验进行了1 0 0 次7 1 的结果是一次拟合好于二 次拟合。由此可看出，有限样本情况下，经验风险最小并不一定意味着期望风险最小：学习 机器的复杂性不但应与所研究的系统有关，而且要和有限数目的样本相适应。我们需要一种 能够指导我们在小样本情况下建立有效的学习和推广方法的理论。 3 1 5 统计学习理论的核心内容 统计学习理论就是研究小样本统计