（运筹学与控制论专业论文）数据挖掘方法研究：关联和趋势分析.pdf

电子科技大学硕士学位论文 摘要 本文研究了两类数据挖掘方法。全文分五个部分：引言、数据挖掘方法 概述、关联分析方法研究、趋势分析方法研究和结论。 在引言中介绍了数据挖掘产生的原因：数据的急剧膨胀和高度时效性与 人们得不到科学决策所需要的有效信息和知识之间的矛盾；给出了数据挖掘 的发展和演化过程；然后指出了数据挖掘前景，最后叙述了本文所做的全部 工作。 在第一章数据挖掘方法概述部分，重点阐述了数据挖掘的定义、数据挖 掘方法分类、数据挖掘方法研究现状以及数据挖掘和统计学的区别与联系。 指出了数据挖掘定义所包括的几层含义：面向真实数据、面向具体问题等； 给出了数据挖掘方法的分类，确定了本文研究的两类挖掘方法在整个数据挖 掘方法中的地位和作用；从八个方面详细总结了现阶段数据挖掘方法的研究 现状；最后对数据挖掘与统计学的关系进行了讨论，指出了数据挖掘与统计 学相同之处和本质区别。 在第二章关联分析方法研究部分，重点讨论关联分析的经典方法和基于 兴趣度的否定关联分析方法。通过一个实例，指出了经典关联分析方法在“支 持度一置信度”框架下产生了错误的关联规则：并针对这种情况，提出了基于 兴趣度的否定关联分析方法，对所举实例进行分析，表明该方法能挖掘出更 加符合实际的、用户感兴趣的否定关联规则。该方法采用卡方统计量作为兴 趣度度量，并修改经典关联分析方法： 在第三章趋势分析方法研究部分， a p r i o r i 方法，以进行否定关联分析。 通过对交易数据项集进行编码把原始 数据转换成整数值随机变量序列，并说明了该序列为马尔可夫链，然后用频 率代替转移概率，建立了一个趋势分析的模型。对超市销售数据进行分析表 明该方法简单、实用，而且得到一个有趣的结果：顾客对同一产品的不同品 牌的选择是没有差别的。 在第四章结论部分，对本文在数据挖掘方法上的研究工作进行了总结。 关键词数据挖掘方法，关联分析，否定关联规则，趋势分析 第1 i 页，共2 页 电子科技大学硕士学位论文 r e s e a r c ho fd a t a m i n i n g m e t h o d ：a s s o c i a t i o na n dt r e n d a n a l y s i s a b s t r a e t t h i sd i s s e r t a t i o nm a i n l ys t u d i e st w om e t h o d so fd a t am i n i n ga n dc o n s i s t so f f i v ec o m p o n e n t s ：i n t r o d u c t i o n ，t h es u m m a r i z a t i o no fd a t am i n i n g ，t h er e s e a r c ho f a s s o c i a t ea n a l y s i s ，t h er e s e a r c ho ff e n d a n a l y s i sa n d c o n c l u s i o n i nt h ei n t r o d u c t i o n ，t h er e a s o no fs t u d y i n gd a t am i n i n gi s g i v e n ：c o n f l i c t b e t w e e nt h ee x p l o r i n ga n d u p d a t i n go f d a t aw i t hl a c k i n go fe f f e c t i v ei n f o r m a t i o n a n dk n o w l e d g et h a t p e o p l en e e di n w i s ed e c i s i o n t h e nt h ed e v e l o p m e n ta n d e v o l v e m e n to f d a t am i n i n ga r eg i v e n i nt h ee n do ft h ei n t r o d u c t i o nt h ep r o s p e c t o fd a t a m i n i n g i sd i s c u s s e d i nc h a p t e r1 ，t h ed e f i n i t i o no f d a t am i n i n g ，t h ec a t e g o r yo fm e t h o d so fd a t a m i n i n g ，t h ef r o n to f d a t a m i n i n g a n dt h ed e f e r e n c ea n dc o r r e l a t i o no fd a t am i n i n g a n ds t a t i s t i c sa r ed i s c u s s e dd e t a i l e d f i r s t ，i n v e s t i g a t i n gt w on e c e s s a r yd e f i n i t i o n s i nt h ed e f i n i t i o no f d a t a m i n i n g ：h a v i n gt h et r u ed a t aa n df a c i n gt h er e a lp r o b l e m t h er e s u l to ft w oc l a s s i f yo fm e t h o d so fd a t am i n i n gt h a ta r ed i s c u s s e di nt h i s p a p e r l e a dt ot h e i m p o r t a n tp o s i t i o n i nt h er e s e a r c ho fd a t a m i n i n g t h e n s u m m a r i z i n gt h es t a t u so fr e s e a r c hi nd a t am i n i n gf r o me i g h ta s p e c t s l a s t ，i n d i s c u s s i n gt h er e l a t i o no f d a t am i n i n ga n ds t a t i s t i c s ，t h es a m e n e s sa n d d i s t i n g u i s h b e t w e e nt h e ma r eg i v e n c h a p t e r 2m a i n l y d i s c u s s i n gt h ec l a s s i cm e t h o do f a s s o c i a t ea n a l y s i sa n dt h e m e t h o do fn e g a t i v ea s s o c i a t e a n a l y s i s t 1 1 a tb a s e do ni n t e r e s tm e a s u r e m e n t t h r o u g h ac a s et h ef a l s er u l et h a tc o n c l u d e df r o mt h ec l a s s i cm e t h o do fa s s o c i a t e a n a l y s i st h a tb a s e do n s u p p o r t - - e o n f i d e n c e ”w h i l ea n a l y s e st h es a m ec a s eu s i n g t h em e t h o do f n e g a t i v ea s s o c i a t ea n a l y s i st h a tb a s e do ni n t e r e s t ，w ec a ns e et h a t t h i sm e t h o dc a nm i n em o r ea p p l i c a b l ea n dm o r ei n t e r e s t i n gd a t af o rt h eu s e r i n o r d e rt 0a p p l yt h em e t h o d o f n e g a t i v ea s s o c i a t ea n a l y s i st h i sm e t h o d h a st h e z 2a s i t si n t e r e s tm e a s u r e m e n ta n d m o d i f y t h ec l a s s i cm e t h o d ：a p r i o r im e t h o d c h a p t e r 3b a s e do n e n c o d i n gt h e t r a n s a c t i o nd a t ai t e ms e t ，t h eo r i g i n a ld a t ai s 第m 页，共5 页 皇王型垫查堂堡主堂垡丝苎 t r a n s f o r m e di n t oas e r i e so fi n t e g r a lv a r i a b l ea n dt h i s s e r i e si s p r o v e dt ob ea m a r k o vc h a i ni nt h e o r y a n di n s t e a do ft r a n s f o rp r o b a b i l i t y , f r e q u e n c yi s u s e di n t r a n s f e r p r o b a b i l i t y m a t r i x t h e na n a l y s i sf o rt h es a l e d a t ao fs u p e r m a r k e t i n d i c a t e st h a tt h em e t h o di sf i n e ，a n dan i c er e s u l tt h a tc u s t o m sc h o i c ei s s a m et o d i f f e r e n tb l a n do fo n ep r o d u c ti sr e c e i v e d i nt h ec o n c l u s i o np a r t ，t h ea u t h o rs u m m a r i e st h er e s e a r c ho f d a t am i n i n g s m e t h o d k e y w o r d s ：d a t am i n i n gm e t h o d ，a s s o c i a t ea n m y s i s ，n e g a t i v ea s s o c i a t i o n r u l e ，t r e n da n a l y s i s 第页共5 页 电子科技大学硕士学位论文 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得 的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究 所做的任何贡献均己在论文中作了明确的说明并表示谢意。 签名： 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查 阅和借阅。本人授权电子科技大学可以将学位论文的全部或部分内容编入有 关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位 论文。 第1 页，共5 页 期：2 0 0 2 年月日 电子科技大学硕士学位论文 引言 目前，数据库的应用已经触及到人类生活的各个方面，银行、商 业、工业、农业、科技、军事等各行业都在应用着数据库。据统计， 1 9 8 9 年全世界数据库总量为5 0 0 万个，而且数量还以每2 0 个月翻一番 的数据增长着，其中储存的数据量成指数性增长，如w a lm a r t 公司( 美 国最大的零售连锁店) 每天产生两千万个事务；又如美国航天局1 9 9 9 年发射的地球观测系统每天要产生i 2 0 0 g b 的图像数据；还有生物学领 域中数以百万计的遗传基因，世界各国定期进行的人口普查，国土资 源地理信息，铁路动态调度控制，公安司法部门的案件处理等等都是 海量数据。但是对如此众多的数据的利用还主要是检索查询，效率很 低，而且相当数量的数据具有很强的时效性，往往很多数据还没来得 及分析就已经过时，数据的价值没有得到充分利用“1 。 面对数据的急剧膨胀和高度时效性，一方面，人们苦于不能及时 得到科学决策所必须的可靠知识，另一方面，大量宝贵的数据资源甚 至还没有得到利用就已经过时，这导致了一个新的问题，即所谓的“数 据丰富，知识贫乏”问题，“我们淹没在信息之中，但仍处于知识的饥 渴中”j o h en a is b e t t 说。迫切需要研究新一代数据处理技术，以提高 数据的利用率。数据挖掘技术就是这样一个背景下产生了，它的宗旨 就是分析处理海量数据，以发现有用的知识，为用户提供所需问题的 答案。 数据挖掘技术的产生有很强的技术基础，它是人们长期对数据库 技术进行研究和开发的结果。起初各种商业数据是存储在计算机的数 据库中的，然后发展到可对数据库进行查询和访问，进而发展到对数 据库的即时遍历。数据挖掘使数据库技术进入了一个更高级的阶段， 它不仅能对过去的数据进行查询和遍历，并且能够找出过去数据之间 的潜在联系，从而促进信息的传递。这是个革命性进步，因为从用户 的角度来看，数据挖掘已经可以快速地回答诸如“下个月成都的销售 会怎么样? 为什么? ”等许多商业问题了。 第l 页，共3 7 页 电子科技大学硕士学位论文 数据挖掘技术的产生也不是一蹴而就的，它的产生和发展其实是 一个逐渐演变的过程。电子数据处理的初期，人们就试图通过某些方 法来实现自动决策支持，当时机器学习成为人们关注的焦点。机器学 习的过程就是将一些已知的并已被成功解决的问题作为范例输入计算 机，机器通过学习这些范例总结并生成相应的规则，这些规则具有通 用性，使用它们可以解决某一类的问题。随后，由于神经网络技术的 形成和发展，人们的注意力转向知识工程，知识工程不同于机器学习 之处就是直接给计算机输入己被代码化的规则，专家系统就是这种方 法所得到的成果，但它有投资大、效果不甚理想等不足。8 0 年代人们 又在新的神经网络理论的指导下，重新回到机器学习的方法上，并将 其成果应用于处理海量商业数据。直到1 9 8 9 年在美国底特律举行了第 十一届国际人工智能学术会议，在这次会议上定义了一个新的术语， 它就是数据库中的知识发现( k n o w l e d g ed is c o v e r yi nd a t a b a s e ) ，简 称k d d 。人们接受了这个术语，并用k d d 来描述整个发现知识的过程。 包括最开始的制定业务目标到最终的结果分析，而用数据挖掘( d a t a m i n i n g ，d m ) 来描述使用挖掘方法进行数据挖掘的子过程。随后，知 识发现与数据挖掘流行起来了，大量学者及产业界参与近来，取得长 足的进展。 由加州理工学院喷气推进实验室与天文科学家合作开发的 s k i c a t ( s k yi m a g ec a t a l o g i n ga n da n a l y s i s t 0 0 1 ) 是第一个获得相 当成功的数据挖掘应用，已经帮助科学家发现了1 6 颗极其遥远的类星 体。 总之，数据挖掘经过二十几年的发展，有了很大的进步，其前景 越来越被看好。最近，g a r t n e rg r o u p 的一次高级技术调查将数据挖掘 和人工智能列为“未来三到五年内将对工业产生深远影响的五大关键 技术”之首，并且还将并行处理体系和数据挖掘列为未来五年内投资 焦点的十大新兴技术前两位。根据最近g a r t n e r 的h p c 研究表明，“随 着数据捕获、传输和存储技术的快速发展，大型系统用户将更多地需 要采用新技术来挖掘市场以外的价值，采用更为广阔的并行处理系统 来创建新的商业增长点”。 本文对数据挖掘方法进行了研究。首先全面介绍了数据挖掘方法， 第2 页共3 7 页 电子科技大学硕士学位论文 重点阐述了数据挖掘的定义、数据挖掘方法分类、数据挖掘方法研究 现状以及数据挖掘和统计学的区别与联系。指出了数据挖掘定义所包 括的几层含义：面向真实数据、面向具体问题等；给出了数据挖掘方 法的分类，确定了本文研究的两种挖掘方法在整个数据挖掘方法中的 地位和作用；从八个方面详细总结了现阶段数据挖掘方法的研究现状； 最后对数据挖掘与统计学的关系进行了讨论，指出了数据挖掘与统计 学相同之处和本质区别。然后介绍了对关联分析方法的研究，重点讨 论关联分析的经典方法和基于兴趣度的否定关联分析方法。通过一个 实例，指出了经典关联分析方法在“支持度一置信度”框架产生错误的 关联规则；针对这种情况，提出了基于兴趣度的否定关联分析方法， 对所举实例进行分析，表明该方法能挖掘出更加符合实际的、用户感 兴趣的否定关联规则。最后对趋势分析方法进行了研究，通过对交易 数据项集进行编码把原始数据转换成整数值随机变量序列，并说明了 该序列为马尔可夫链，然后用频率代替转移概率，建立了一个趋势分 析的模型。对超市销售数据进行分析表明该方法简单、实用，而且得 到一个有趣的结果：顾客对同一产品的不同品牌的选择是没有差别的。 第3 页，共3 7 页 电子科技大学硕士学位论文 第一章数据挖掘方法概述 1 1 数据挖掘的定义 u s a m am f a y y a d 等在1 9 8 9 年在美国底特律举行了第十一届国际人 工智能学术会议给出了k d d 最初的描述性定义，即k d d 就是数据集中 识别出有效的、新颖的、潜在有用的，以及最终可理解的模式的非平 凡过程“1 。可是这次会议并没有给出数据挖掘的定义，实际上这导致 许多学者在这两个术语上的混用。m e t ag r o u p1 9 9 6 年给出了数据挖掘 ( d a t am i n i n g ，d m ) 的定义，即“d a t am i n i n gi st h e a p p l i c a t i o n o f a r t i f i c i a l i n t e l l i g e n c e ( a i ) t e c h n i q u e s ( n e u r a ln e t w o r k ，f u z z yl o g i c ， g e n e t e t i ca l g o r i t h m s ) t ol a r g eq u a n t i t i e so f d a t a ，t od i s c o v e r yh i d d e n t r e n d s p a t t e r n a n dr e l a t i o n s h i p ”。现在数据挖掘界普遍认为数据挖掘 是指从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据 中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息 和知识的过程”1 。 这个定义包括好几层含义：数据源必须是真实的、大量的、含噪 声的：发现的是用户感兴趣的知识；发现的知识应该可接受、可理解、 可运用：并不要求发现放之四海皆准的知识，也不是要去发现崭新的 自然科学定理和纯数学公式，更不是什么机器定理证明。实际上，所 有发现的知识都是相对的，是有特定前提和约束条件，面向特定领域 的，同时还要能够易于被用户理解，最好能用自然语言表达所发现的 结果。数据挖掘所得到的知识应具有先前未知这个特征。先前未知的 知识是指预先未曾预料到的，甚至是违背直觉的信息或知识，挖掘出 的信息越是出乎意料，就可能越有价值。在商业应用中最典型的例子 就是w a lm a r t 公司( 美国最大的零售连锁店) 通过数据挖掘发现了小 孩尿布和啤酒之间有着惊人的联系( 后面称之为关联规则) 。 那么何为知识? 从广义上理解，数据、信息也是知识的表现形式， 数据是指有关事实的集合，记录和事物有关的原始信息。信息是根据表 第4 页，共3 7 页 电子科技大学硕士学位论文 示数据所用的约定，赋予数据的意义。但是人们更把概念、规则、模 式、规律和约束等看作知识，因为这些东西是对数据包涵的信息更抽 象的描述。人们把数据看作是形成知识的源泉，好像从矿石中采矿或 淘金一样。原始数据可以是结构化的，如关系数据库中的数据；也可 以是半结构化的，如文本、图形和图像数据；甚至是分布在网络上的 异构型数据。发现知识的方法可以是数学的，也可以是非数学的；可 以是演绎的，也可以是归纳的。发现的知识可以被用于信息管理，查 询优化，决策支持和过程控制等，还可以用于数据自身的维护。因此， 数据挖掘是一门交叉学科，它把人们对数据的应用从低层次的简单查 询，提升到从数据中挖掘知识，提供决策支持。在这种需求牵引下， 汇聚了不同领域的研究者，尤其是数据库技术、人工智能技术、数理 统计、可视化技术、并行计算等方面的学者和工程技术人员，投身到 数据挖掘这一新兴的研究领域，形成新的技术热点。 而从商业角度上来看，数据挖掘是一种新的商业信息处理技术， 其主要特点是对商业数据库中的大量业务数据进行抽取、转换、分析 和其他模型化处理，从中提取辅助商业决策的关键性数据。 因此，数据挖掘可以说是一类深层次的数据分析方法。数据分析 本身并不什么新鲜的东西，它已经有很多年的历史，只不过以前数据 收集和分析的目的是用于科学研究，而且限于当时计算的能力，对大 数据量进行分析的复杂数据分析方法发展缓慢。现在，由于各行业业 务自动化的实现，商业领域产生了大量的业务数据，分析这些数据主 要是为商业决策提供真正有价值的信息，进而获得利润。但所有企业 面临的一个共同的问题：企业数据量非常大，而其中真正有价值的信 息却很少。因此从大量的数据中经过深层分析，获得有利于商业运作、 提高竞争力的信息，就像从矿石中淘金一样，数据挖掘也因此而得名。 因此，数据挖掘也可以描述为：按企业既定业务目标，对大量的 企业数据进行探索和分析，揭示隐藏的、未知的或验证已知的规律性， 并进一步将其模型化的先进有效的方法。 第5 页，共3 7 页 电子科技大学硕士学位论文 1 2 据挖掘方法分类 数据挖掘涉及的学科领域很多，有多种分类方法。根据挖掘的知 识分，数据挖掘方法可分为分类或预测型发现、数据总结、聚类、关 联规则发现、序列模式发现、依赖关系或依赖模型发现、异常和趋势 发现等等；根据挖掘的对象分，数据挖掘方法有针对关系数据库、面 向对象数据库、空间数据库、时态数据库、文本数据库、多媒体数据 库、异质数据库、遗产数据库以及环球网w e b ；根据所采用的技术分为 机器学习方法、统计方法、神经网络方法和数据库方法。其中，机器 学习方法可细分为归纳学习方法( 决策树、规则归纳等) 、基于范例学 习、遗传算法等；统计方法可细分为回归分析( 多元回归、自回归等) 、 判别分析( 贝叶斯判别、费歇尔判别、非参数判别等) 、聚类分析( 系 统聚类、动态聚类等) 、探索性分析( 主元分析方法、相关分析方法等) 等；神经网络方法可细分为前向神经网络( b p 算法等) 、自组织神经网 络( 自组织特征影射、竞争学习等) 等；数据库方法主要是多维数据 分析或o l a p 方法，以及面向属性的归纳方法。 1 3 数据挖掘方法的研究现状 自k d d 一词首次出现到目前为止，由美国人工智能协会主办的k d d 国际研讨会已经召开了8 次，规模由原来的专题讨论会发展到国际学 术大会，研究重点也逐渐从发现方法转向系统应用，注重多种发现策 略和技术的集成，以及多种学科之间的相互渗透。1 9 9 9 年，亚太地区 在北京召开的第三届p a k d d 会议收到1 5 8 篇论文，空前热烈。i e e e 的 k n o w l e d g ea n dd a t ae n g i n e e r i n g 会刊率先在1 9 9 3 年出版了k d d 技术专 刊。并行计算、计算机网络和信息工程等其他领域的国际学会、学刊 也把数据挖掘和知识发现列为专题和专刊讨论。1 9 9 6 年，i b m 在 s u p e r b o w l 期间举办的一场商业活动中出现了时装模特们参与讨论数 据挖掘应用优势的场面“1 ，可见数据挖掘已经到了脍炙人e l 的程度。 与国外相比，国内对数据挖掘与知识发现( d m k d ) 的研究稍晚， 没有形成整体力量。1 9 9 3 年国家自然科学基金开始资助对d m k d 的研究 第6 页莛3 7 页 电子科技大学硕士学位论文 项目。目前，国内的许多科研单位和高等院校竞相开展d m k d 的基础理 论及其应用研究，这些单位包括清华大学、中科院计算技术研究所、 空军第三研究所、海军装备论证中心等。其中，北京系统工程研究所 对模糊方法在知识发现中的应用进行了较深入的研究，北京大学开展 了对数据立方体代数的研究，华中理工大学、复旦大学、浙江大学、 中国科技大学、中科院数学研究所、吉林大学等单位开展了对关联规 则挖掘算法的优化和改造；南京大学、四川大学和上海交通大学等单 位探讨、研究了非结构化数据的知识发现以及w e b 数据挖掘”1 。 下面就对现阶段数据挖掘方法进行回顾与总结。 1 ) r a g r a w a l 等综合了机器学习与数据库技术，对三类数据挖掘问 题即分类、关联及序列作为一个统一的蕴藏与巨量数据中的规则发现 来处理，给出了一个统一的模型和规则发现过程中的几个基本运算， 并给出了数据挖掘问题如何映射到模型和通过提出的基本运算如何解 决发现问题的方法。他们提出的利用基本操作构造的分类器算法c d p 不仅能够有效的挖掘分类规则，而且还具有i d 3 的精度( i d 3 是目前最 好的分类器之一) 。 2 ) s a n a n d 等提出的基于证据理论( e v i d e n tt h e o r y ) 的数据挖掘 一般框架e d m ”1 。在e d m 框架内开发的算法是并行的，对分布的和异构 的大数据集的进行发掘有很好的效率，并且用户的先验知识与先前发 现的知识可以耦合到发现过程中；另外在强规则( 满足最小支持度和 最小置信度的关联规则) 的发掘及空间数据库的发掘上，能对提出的 方法进行了检验。 g s h a f e r 的证据理论、z a d e h 的可信度理论和最近国内发展起来 的未确知数学，都是关于不完全信息的表达与处理的系统方法。e d m 框架基于证据理论，可望对不完全信息的发掘提供系统的方法。 3 ) 针对不前各种各样的数据挖掘技术，w e i m i n gs h e n 与b i n g l e n g 提出了无监督关系模式学习的基于元模式( 元查询) 的自动挖 掘集成方法。该方法不同于工具箱似的集成方法，他们提出的元模式 的概念便于自动利用归纳、演绎及人的指导之间的相互依赖。由于元 模式具有普遍的机制，因此，可望在人的指导下与数据挖掘开发者自 己偏好的演绎及归纳技术集成。 第7 页，共3 7 页 电子科技大学硕士学位论文 4 ) 可视化已成为整个计算机行业的一种趋势，也是数据挖掘领域 的重要研究方向之一。在数据挖掘领域中，自动知识发现与可视化有 很多相似之处，可视化的数据挖掘也有助于数据分析的解释，并且在 大数据集的挖掘方面也有很大的潜力。g p i a t e t s k y s h a p i r o 等开发的 知识发现平台k d w 是一个数据探测的交互式可视化数据挖掘系统。该 系统集成了几种数据挖掘技术如数据聚类、数据可视化汇总分类及数 据变更的发现。整个系统采用了领域知识辅助初始发现的聚焦限制性 的搜索，以及揭示出的模式的评价和发现的结果的有意义显示。在处 理大数据库方面，系统采用的是统计估计技术，统计方法同时还用在 系统的不确定性模式的处理上。 大数据库发掘的可视化技术，大都集成了多种数据挖掘技术，都 可挖掘多种形式的知识规则。除了k d w 外，有代表性的还有d a n i e l a k e i m 等开发的多维数据库可视化挖掘系统v is d b 。 5 ) 实际挖掘中挖掘的知识质量如何，严重依赖于数据库的知识的 特征表示，以及现存的知识与已发现的知识如何一致。发现的知识可 能不能不是用户感兴趣的，或者与先前的知识有矛盾。j o n g p y o o n 与l a r r yk e r s c h b e r g 。1 针对这个问题提出了数据库中知识发现与进化 的概念，利用数据库查询以发现新的知识，使用正反两个方面的例子 来发现新知识以及新旧知识的协调一致，对数据库中例外的特征化以 及随着知识与数据库的同步进化。 6 ) 在数据挖掘中，大量的工作是关于关联规则、分类规则、聚类 规则等某种特定规则的挖掘研究。数据库的规模巨大，数据的分布广 泛，一些数据挖掘方法的计算复杂等等，多要求研究高效挖掘方法。 原来一般采用a p r i o r i 和d h p 方法，目前d w c h e u n g 1 等人对分布式数 据库的关联规则的挖掘提出了一种有效方法d m a ( d i s t r i b u t e dm i n i n g o fa s s o c i a t i o nr u l e s ) 。因为需要大量的额外通讯开销，将串行算法 直接用分布式数据库的效率不高；d m a 生成一个小的候选集，且对每个 候选集为支持数目交换仅需0 ( i 2 ) 个信息，这里n 是分布式数据库的分 布点数。因此，d m a 具有很高的性能。 7 ) 数据挖掘除了集成方法或一般框架上的研究和对某种特定规则 的研究外，对特定数据库的挖掘也做了大量的工作，如针对关系数据 第8 页。共3 7 页 电子科技大学硕士学位论文 库、面向对象数据库、空间数据库、时态数据库、文本数据库、多媒 体数据库、异构数据库、遗产数据库以及环球网w e b 等等。 8 ) h o n g j u nl u “等提出了利用神经网络挖掘符号分类规则的方 法。与基于决策树的方法相比，他们提出的方法具有跟小的分类出错 率，抽取的规则也更简洁；不同的是，抽取规则的时间消耗比基于决 策树的方法长。 总而言之，目前数据挖掘的研究主要是以挖掘的任务描述、挖掘 结果的评价与表示为主线，以有效的挖掘方法为中心。具体而言，数 据挖掘的研究主要是在各类真实的数据库( 关系、演绎、时序、空间、 分布式、面向对象等) 中，利用统计学、证据理论、归纳学习、近似 推理、人工神经网络、遗传算法、概念树提升算法、关联方法、分类 方法、数据聚类、r o u g h 集理论、现代数学分析方法及其集成方法等技 术，挖掘诸如关联规则、分类规则、数据聚类、序贯模式、相似模式、 混沌模式等知识，以开发其数据挖掘原型系统、实用系统研究和基于 数据挖掘的通用工具。几次数据挖掘国际会议基本上围绕着数据挖掘 的基础理论、挖掘方法、数据仓库、可视化技术、挖掘结果表示方法、 挖掘结果的再利用、网络环境下的数据挖掘等几个专题进行讨论。 1 4 数据挖掘与统计学 从前面的描述可以看出，数据挖掘和统计学有着密切的联系，基 于统计学的方法在数据挖掘方法中占了很重要的地位，这也可以从本 文后面的叙述中反映出来。总的来说数据挖掘和统计学有很多共同点， 但与此同时它们也有很多差异。 数据挖掘和统计学有着共同的目标：发现数据中的结构“”。事实 上，不少人认为数据挖掘只不过是统计学的一种新说法，这当然是一 个不切合实际的看法。因为数据挖掘还应用了其它领域的思想、工具 和方法，尤其是计算机学科，例如数据库技术和机器学习，而且它所 关注的某些领域和统计学家所关注的有很大不同。 其一，数据挖掘是一个“数据驱动”的过程，目的是发掘以前没 有发现或容易忽视的有意义的数据模式；而统计学推理是以某个假设 第9 页，共3 7 页 电子科技大学硕士学位论文 为开端，然后再利用统计学的方法来论证或否定这个假设。其二，数 据挖掘依靠计算机而不是人力来做发现模式的复杂的数学运算。大量 原始数据的分析需要深层次的归纳推理，这部分工作也是有计算机来 完成。推理结束后，计算机再按能为人所理解的格式输出分析结果。 只有通过大量的实例数据集的分析，才能得出比较准确的分析结 果。纯粹的统计分析要求统计学家与数据集进行大量的引导型交互， 从而对新的发现产生了消极的影响。在数据挖掘领域，“发现”指的是 这样的一个过程：通过扫描整个数据集，找出数据隐含的模式。该过 程并非以对数据的某种预想甚至假设为前提。换句话说，程序使用自 己的计算能力来发现模式，并不需要用户过多的引导。计算机也可以 帮助人们发现许多他们平时未曾想到过的模式。正是计算机使数据挖 掘与统计学区分开来。 尽管如此，数据挖掘与统计学还是有定的渊源关系。除了具有 共同的研究目标外，数据挖掘与统计学有不少共同的术语，诸如样本、 偏差、相关性等，而统计学的一个较新的分支一一探索性数据分析“， 强调“数据”驱动，与数据挖掘有着惊人的相似。 第1 0 页，共3 7 页 电子科技大学硕士学位论文 第二章关联分析方法研究 关联分析是数据挖掘中研究最成熟的一个方面。关联分析的目的 就是发现大量数据中项集之间有趣的关联或相关联系。随着大量数据 不停地收集和存储，许多商业人士对于从他们的数据库中发现关联越 来越有兴趣。因为从大量商务事务中发现有趣的关联关系，可以帮助 制定许多商务决策，如分类设计、交叉购物和折扣分析。一个典型的 例子就是进行购物篮分析。该过程通过分析顾客同时购买的不同商品 之间的联系，以分析顾客的购买习惯。通过了解那些商品频繁地被顾 客同时购买，这可以帮助零售商制定营销策略，这进一步刺激顾客同 时购买这些商品。 关联分析的重要对象是事务数据库，针对的应用是销售数据，如 在超级市场的前端收款机中就收集存储了大量的数据。一般情况下， 一个事务( t r a n s a c t i o n ) 有如下几个部分组成：事务处理时间、一组 顾客购买的物品、物品的数量及金额，以及顾客的标识号( 如信用卡 号或会员卡号) 。现实中，这样的例子很多。 在事务数据库中，考察一些涉及到许多物品的事务：事务l 中出 现了物品甲，事务2 中出现了物品乙，事务3 中同时出现了物品甲和 乙。那么，物品甲和乙在事务中的出现相互之间是否有规律可循呢? 关联分析将把事务数据转换成如此形式的关联规则：如果一个事务包 含了物品甲，那么，在x 的情况下，这个事务也包含物品乙( 即甲一 乙) 。但有些数据不像销售数据那样很容易能看出一个事务就是许多物 品的集合，不过本质上仍然可以像对销售数据一样处理。比如，人寿 保险，一份保单就是一个事务。保险公司在接受投保前，往往需要记 录投保人详尽的信息，有时还要到医院做身体检查。保单上记录有投 保人的年龄、性别、健康状况、工作单位、工作地址、工资水平等。 这些投保人的个人信息就可以看作事务中的物品。通过分析这些数据， 也许可以发现有较多的工作在a 地区的投保人曾经向保险公司索赔过。 原因可能是a 地区污染比较严重，导致在该地区工作的人健康状况不 第1 1 页，共3 7 页 电子科技大学硕士学位论文 好，因此，保险公司可以在接受投保前采取相应的措施。 在数据挖掘中，关联分析就是发现描述这种在一个事务中物品之 间同时出现的规律的模式。更确切地说，关联分析就是通过量化的数 字描述物品甲的出现对物品乙的出现有多大的影响1 。 2 1 基本概念 设= f 。，i ：，f 。) 是项的集合。前面提到的物品集合就是一个项的 集合。设d 是数据库事务的集合，其中每个事务，是项的集合，即 t ，每个事务有一个标识符，称作t i d ，设是一个项集，事务r 包 含一当且仅当t 。关联分析得到的技术如下形式的蕴涵：一一b ，其 中a c i ，b c 彳，并且4 n b = 庐，称之为关联规则“”。一个关联规则可 以用支持度、置信度、期望置信度、作用度等来描述。 1 ) 支持度( s u p p o r t ) 设d 中有s 的事务同时支持项集a 和b ，s 称为关联规则一一b 的支持度。支持度描述了一和b 这两个项集的并集 c 在所有事务中出现的概率有多大。如某天共有1 0 0 0 个顾客到商场购 买物品，其中有1 0 0 个顾客同时购买了牛奶和面包，那么上述关联规 则的支持度就是l o ( 1 0 0 1 0 0 0 ) 。 2 ) 置信度( c o n f i d e n c e ) 设d 中支持项集一的事务中，有c 的事 务同时也支持项集b ，则c 称为关联规则一一b 的鼍信度。简单地说， 置信度就是指在出现了项集a 的事务中，项集曰也同时出现的概率有多 大。如前面所举的牛奶和面包的例子，假设购买牛奶的顾客中有8 0 的人购买了面包那么，该称为关联规则a b 的置信度就是8 0 。 3 ) 期望置信度( e x p e c t e dc o n f i d e n c e ) 设d 中有e 的事务支持项 集b ，e 称为关联规则a - - b 的期望置信度。期望置信度描述了在没有 任何条件影响时，项集b 在所有事务中出现的概率有多大。如前面所 举牛奶和面包的例子，其中有2 0 0 个顾客购买了面包，则上述的关联 规则的期望置信度就是2 0 。 4 ) 作用度( l i f t ) 作用度是置信度与期望置信度的比值。作用度 描述了项集4 出现对项集b 的出现有多大的影响。因为项集b 在所有事 务中出现的概率是期望置信度，而项集b 在有项集a 出现的事务中出现 第1 2 页。共3 7 页 电子科技大学硕士学位论文 的概率是黄信度，通过置信度对期望置信度的比值反映了在加入“项 集a 出现”这个条件后，项集b 的出现概率发生了多大的变化。在上例 作用度就是8 0 2 0 = 4 。 用p ( 4 ) 表示事务中出现项集4 的概率，p ( b l a ) 表示在出现项集4 的 事务中，出现项集b 的概率，则上面四个关联规则度量就可以用公式 表示，如表2 一l 所示。 表2 一l四个关联规则度量的计算公式 名称描述公式 支持度( s u p p o r t )项集a 、b 同时出现的 p ( a t j 占、 概率 置信度( c o n f i d e n c e )在项集一出现的前提h b f 一) 下，b 出现的概率 期望置信度( e x p e c t e d项集b 出现的概率 p ( 曰) c o n f i d e n c e ) 作用度( l i f t )置信度对期望置信度p l a ) p ( b ) 的比值 支持度是对关联规则重要性的衡量，置信度是对关联规则的准确 度的衡量。显然支持度越大，关联规则越重要，在所有事务中有更大 的代表性。有些关联规则置信度虽然很高，但其支持度很低，说明关 联规则实用的机会较小，但有时候却不一定不重要。 期望置信度描述了在没有项集的作用下，项集b 本身的支持度， 作用度描述了项集4 对项集b 的影响力的大小。作用度越大，说明项集 曰受项集一的影响越大。一般情况，有用的关联规则的作用度都应该大 于1 ，即只有关联规则的置信度大于期望置信度，才说明项集a 的出现 对项集b 的出现有促进作用，也说明了它们之间某种程度的相关性； 但如果作用度不大于1 ，并不能说明该关联规则没有意义“。 第1 3 页，共3 7 页 电子科技大学硕士学位论文 2 2 研究动态 a g r a w a l 、i m ie l i n s k i 和s w a m i 1 于1 9 9 3 年首次提出了关联规则 的概念。随后1 9 9 4 年a g r a w a l 和s r i k a n t 给出了关联规则中的经典方 法：a p r i o r i 方法“。a p r i o r i 方法是基于频繁集合理论的递推方法，由于 可能产生大量的侯选集，性能有时不高。为提高a p r i o r i 方法的有效性， 研究人员提出了许多a p r i o r i 方法的改进。p a r k 、c h e n 和y u “”提出使用 散列技术来压缩侯选k 一项集；而h a n 和f u 等”研究了事务压缩技术， 考虑到不包含任何k 一项集的事务不可能包含任何( k + 1 ) 一项集，这样， 这种事务在后续步骤中，可以加上标记或删除，因为已经不再需要它 们了。s a v a s e r e 、o m i e c i n s k i 和n a v a t h e ”提出对数据进行划分的方 法，对每一部分，找出该部分内的频繁项集，称为局部频繁项集。把 所有局部频繁项集作为熬个数据的侯选项集，通过再次扫描数据库， 就可以确定全局频繁项集。另外t o i v o n e n “”提出使用抽样技术，即在 数据库的随机样本中搜索频繁项集。用这个方法，实质是牺牲一些精 度来换取有效性。从另一个方面，h a n 、p e i 和y i n ”提出挖掘全局频 繁项集不产生侯选的方法。这种方法称之为频繁模式增长 ( f r e q u e n t p a t t e r ng r o w t h ) ，简称f p 一增长。f p 一增长方法将发现长 频繁模式的问题转换成递归地发现一些短模式，然后进行连接，这大 大降低了搜索开销，比a p r i o r i 方法大约快了一个数量级。 自a g r a w a l 等提出关联规则的概念后，对关联规则挖掘有许多扩 充。一是从单一概念层次关联规则的发现发展到多概念层次的关联规 则的发现。也就是说在很多具体的应用中，可以在数据库中的不同层 面上挖掘关联规则。如，在分析超级市场销售事务数据库过程中，若 单单从数据库中的原始字段，如牛奶、面包等等进行挖掘，可能难以 发现令人感兴趣的规则。这时若把一些抽象层次概念也考虑进