（计算机应用技术专业论文）数据库关联规则挖掘的研究及在股市板块联动中的应用.pdf

沈阳工业大学硕士学位论文 摘要 从大型数据库中挖掘未知的并且是潜在有用的信息和知识，是数据呈爆炸性增长所 提出的迫切要求，于是数据挖掘技术便应运而生了。而关联规则作为一类知识模式，是 数据挖掘所要研究的一项重要内容。 目前，数据挖掘技术正在升温。作为数据挖掘技术的一个重要分支关联规 则，也成为众多研究者的研究对象。关联规则能够清楚地描述现实事物之间可能存 在的某种强度的联系，有着很强的实用性，从而吸引了众多研究者的兴趣。本文结 合关联规则的研究现状和最新动态，着重研究了挖掘关联规则的高效率算法及其实 现。论文首先介绍了数据挖掘技术的基本概念，基本过程和一般方法；然后就关联 规则的研究现状、挖掘关联规则的一般步骤进行了展开，并且探讨了关联规则的主 要研究方向；接着分析了几种基本的关联规则挖掘算法，并指出了这几种算法的共 同不足之处因扫描数据库次数过多而造成的算法效率低的弊端。提出了基于前 缀广义链表的关联规则生成算法和基于频繁模式增长的关联规则挖掘算法，这两种 算法只需扫描数据库两次，而且不需要产生过多的候选频繁项集，这样不仅提高了 算法的运行效率，而且节约了内存空间。在生成规则的过程中，为提高生成速度， 采取了有效的措施，尽可能地减少除法运算。整个算法在这两个方面进行了改进， 因此大大地提高了算法的运行效率。另外，将新提出的算法应用于殷市板块联动 中，取得了预期的运行效果。最后对整个论文工作进行了总结，展望了未来这方面 工作的前景。 关键词：数据挖掘关联规则频繁模式链衷 鲨堕三些奎兰堡主兰垡堡塞一 l h es t u d y in go fm j n i n ga s s o c i a t j o dr u l e s i nd a t a b a s e a n dt h ea p p li c a t i o n i ns t o c km a r k e tb 1 0 c k sm o v i n g b e t w e e ne a c ho t h e o a b s tr a c t m i n i n gp r e v i o u s l y u n k n o w na n d p o t e n t i a ll y u s e f u l i n f o r m a t i o na n dk n o w l e d g ef r o ml a r g ed a t a b a s e si sa nu r g e n tn e e d p o s e db yt h ee x p l o s i v eg r o w t hi nd a t a c o n s e q u e n t l y ，d a t am i n i n g t e c h n o l o g yh a se m e r g e d f o rt h i s p u r p o s e a s s o c i a t i o nr u l ei sa n i m p o r t a n tk i n do fk n o w l e d g ep a t t e r n st h a t a r ed i s c o v e r e db yd a t a m i n i n g n o wt h er e s e a r c ho nd a t am i n i n gb e c o m e sah o t t o p i c b e c a u s eo fi t sc l e a rd e s c r i p t i o no ft h er e l a t i o n sw i t hc e r t a i n l e v e l a m o n g t h er e a l i s t i c o b j e c t s ， w h i c hi s v e r yp r a c t i c a l ， a s s o e ja t i o nr u l ea t t r a c t sal a r g eq u a n t i t yo fr e s e a r c h e r si nm a n y d i f f e r e n tf i e l d s i nt h i s p a p e r ， w e p u te m p h a s i s o nt h e a l g o r i t h m s t om i n ea s s o c i a t i o nr u l e sa n dt h e i r i m p l e m e n t a t i o n s w i t hr e f e r e n c et ot h er e s e a r c h i n gc o n d i t i o no fa s s o c i a t i o nr u l e a n d t h el a t e s t t e n d e n c yi n t h e s e t o p i c s i f i r s ti n t r o d u c e dt h e b a s i c c o n c e p t ， r e s e a r c hm e t h o d sa n dc o m m o nm e t h o d so fd a t a m i n i n gt e c h n o l o g y ：s e c o n d l y o nt h eb a s i so ft h er e s e a r c h c o n d i t i o no fa s s o c i a t i o nr u l e sp r e s e n t l ya n d t h ec o m m o n p r o c e s s o f m i n i n ga s s o c i a t i o nr u l e s ，t h ep a p e r d o e saf u r t h e r s t u d y i n g a n dd i s c u s s e sm a i n s t u d y i n gd i r e c t i o n ：t h i r d l y ，i ta n a l y s e s s e v e r a lk i n d so fb a s i ca l g o r i t h m si nm i n i n ga s s o c i a t i o nr u l e sa n d p o i n t st ot h es h o r t c o m i n gi nt h e m i tp u t sf o r w a r dt w oa 】g o r i t h m s w h i c ha r ed a t am i n i n ga l g o r i t h mb a s e do np r e f e r l i n k i n g 1i s ta n d 一1 1 鎏塑三些查堂堡主塑壑 f r e q u e n tp a t t e r ng r o w t h t r e et o p r o d u c ea s s o c i a t i o n r u l e ss o a s t o i m p r o v e t h e m i n i n ge f f i c i e n c y w h i c hi sr e d u c e d b y s o m a n y i n d e x i n g d a t a b a s e i t p r o v e s t h e i re f f e c t i v e n e s so ft h e s et w o s t r a t e g i e s i n t h e o r y t h e t w oa l g o r i t h m so n l ys c a nd a t a b a s et w o t i m e s t h e yn e e dn o tp r o d u c ee x c e s s i v ec a n d i d a t el a r g e i t e ms e t s ， s ot h a tt h e yn o to n l yi m p r o v et h er u n n i n g e f f i c i e n c y b u ta l s o s a v et h e s p a c e o fi n t e r i o r s t o r a g e d u r i n gp r o d u c i n g t h e r u l e s ， w et a k ee f f e c t i v em e t h o d st oi n c r e a s ei t ss p e e da n da s l a r g ea s p r o b a b l y t or e d u c et h et i m e so fd i v i d e t h ew h o l e a l g o r i t h mh a s b e e n i m p r o v e d i nt h et w os i d e ss oa st o l a r g e l y i n c r e a s et h e a l g o r i t h m ss p e e d ，i nt h i st h e s i s w ea l s o p u t t h e t h e o r y i n t o t h er e a l i t y o ft h es t o c kb l o c k s a f t e r r u n n i n g ，w er e c e i v ea p l e a s i n gr e s u l t a tl a s t id r a wac o n c l u s i o nf r o mt h ew h o l ep a p e r a n dl o o kf o r w a r dt ot h ef u t u r e sb l u e p r i n ti nt h i sf i e l d k e y w o r d s ：d a t am i n i n g ，a s s o c i a t i o nr u l e ， f r e q u e n t p a t t e r n ，l i n k1 i s t 1 1 1 独创性说明 本人郑重声明：所呈交的论文是我个人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 沈阳工业大学或其他教育机构的学位或证书所使用过的材料。与我一同 工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表 示了谢意。 签名：孟j 拯日期： 趁堕! 主! f 至 关于论文使用授权的说明 ( 保密的论文在解密后应遵循此规定) 签名：刭姒导师签名：童盔墨i 日期： 即哆、多ij z ：公论即以存 ，可保定校段规学手的：制文阅复论借他 位和其学阅或用查印使被缩 、文、留论印保许影关允用有，采学件以大印可 业复， 工的容阳文内沈论分 解交部了送或全留部 完保全人权的本有文 校论。学布文 沈阳工业大学硕士学位论文 1 绪论 1 1 为什么要研究数据挖掘技术 随着现代科学技术和社会经济的迅速发展，各种数据的爆炸性增长，数据库的规模 变得越来越庞大。例如，美国n a s a 计划于1 9 9 8 年发射的一系列地球观测卫星，每年 将要发回有关地球大气、海洋、陆地等信息约3 0 多万g b 的数据，这些数据将存放于若 干个大型数据库中。面对类似的大型数据，若要有效地使用它们，仅仅依靠数据库管理 系统的查询检索机制和统计分析方法，已远远不能满足应用的需求。为此，人们需要有 新的、更为有效的手段对各种“数据矿藏”( 信息资源) 进行挖掘以发挥其应用潜能。 数据挖掘( d a t am i n i n g ) 正是在这样的应用需求背景下产生并迅速发展起来的一门技 术，它是开发信息资源的一整套科学方法、算法、软件工具以及相应环境的综合。 近年来，数据挖掘技术之所以受到越来越多研究者的关注，是由于数据挖掘技术的 发展有着广阔的市场前景。企业界若能及时有效地使用数据挖掘技术，就能够带来意想 不到的经济效益。例如，美国加州某个超级市场连锁店通过数据挖掘从记录着每天营销 和顾客基本情况的数据库中发现；在周末或下班后前来购买婴儿尿布的顾客多数是男 性，而且他们同时还购买啤酒。于是这个连锁店的经理当机立断地重新布置了货架，把 啤酒类商品布置在婴儿尿布货架附近：并在二者之间放上土豆片之类的佐酒小食品，同 时把男士们需要的日常生活用品也就近布置。这样一来，上述几种商品的销量马上几乎 成倍增长。从这个例子可以看出，数据挖掘将为决策者提供多么重要的、前所未料的信 息或知识，从而产生不可估量的效益。 数据的丰富带来了对强有力的数据分析工具的需求，大量的数据被描述为数据丰 富，但信息贫乏。快速增长的海量数据被收集、存放在大型数据库中，没有强有力的工 具，理解他们已经远远超出了人的能力。结果，收集在大型数据库中的数据变成了数据 坟墓难得再访问的数据档案。这样，重要的决策常常不是基于数据库中信息丰富 的数据，而是基于决策者的直觉。数据挖掘工具进行数据分析，可以发现重要的数据模 式，对商务决策、知识库、科学和医学研究做出了巨大贡献。数据和信息之间的鸿沟要 求系统地的开发数据挖掘工具，将数据坟墓转化成知识金块。 沈阳工业大学硕士学位论文 1 2 国内外动态 尽管数据挖掘还是一个很新的研究课题，但它所固有的为企业创造巨大经济效益的 潜力，已经使它很快有了许多成功的应用。 数据挖掘在生物医学上的应用主要集中在分子生物学特别是基因工程的研究上。基 因研究中，有一个著名的国际性研究课题一人类基因组计划。人类基因组计划是对染 色体位鬣，构成基因的分子及对构成人体基因组的多种调节分子进行定位和全顺序测定 的大工程。科学家已经确认的基因有4 5 5 0 个，其中仅有1 5 0 0 个己被定位于各条染色体 上，而组成人类基因组的基因估计在1 0 万个。1 9 9 8 年成立了国际人类基因组协会的目 的在于促进这一计划的实施。表征人体组织结构，精确维持生命进程的5 万多各类蛋白 质的信息以线性顺序方式编码在约6 0 亿对核苷酸中，不同的基因组合会导致不同特征 的人体，因此基因的准确定位及全顺序分析对研究人类遗传以及对某些疾病的治疗是很 有帮助的。近几年，利用数据挖掘技术已在基因研究上做出了很多种重大的发现。 数据挖掘在保险评估中也起到了重大作用。保险是一项风险业务，保险公司的一个 重要工作就是进行风险评估，即对不同风险领域的鉴定和分析。风险评估对保险公司的 正常运作起着至关重要的作用，保费和保单的设计都需要有比较详细的风险分析。保险 公司成功的一个关键因索是在设置具有竞争力保费和覆盖风险之间选择一种平衡。保费 通常是通过对一些主要的因素进行多种分析和直觉判断来确定。由于投资组合的数量很 大，分析方法通常是粗略的。数据挖掘就是用来处理大型数据库的，因此它提供了进行 保险投资组合数据库分析的环境。 数据挖掘在通信网络警报处理中也有重要应用。通常情况下，一个般的通信网 络，每天可能产生2 0 0 l o o o o 个警报。利用数据挖掘知识，可以根据当前的警报信 息，得到其后继发生的各种情况的可能性，对危险时间可以起到预防的作用，从而使通 信网络得以安全运转。 除了以上这些比较著名的数据挖掘的应用以外，美国钢铁公司和神户钢铁公司利用 基于数据挖掘技术的i s p a 系统，研究分析产品性能规律和进行质量控制，取得了显著 效果；通用电气公司与法国飞机发动机制造公司，利用数据挖掘技术研制了c a s s i o p - e e 质量控制系统，被三家欧洲航空公司用于诊断和预期4 波音7 3 7 的故障，带来了可观 2 沈阳工业大学硕士学位论文 的经济效益；享有盛誉的市场研究公司，如：美国的a c n i e l s o n 和i n f o r m a t i o n r e s o u r c e s ，欧洲的g f k 和i n f i a t e s tb u r k 等纷纷开始使用数据挖掘工具来应付迅速增长 的销售和市场信息数据。商家的激烈竞争导致了市场快速饱和，产品的迅速更新，使得 经营者对市场信息的需求格外强烈。利用数据挖掘所形成的市场预测能力和服务，使这 些市场研究公司取得了巨大收益。中国的公安部门也在研究利用数据挖掘技术总结各类 案件的共性和发生规律，从而在宏观上制定最有效的社会治安综合治理的方案和措施； 在微观上指出犯罪人的特点，划定罪犯的范围，为侦破工作提供方向。 如此看来，数据挖掘这门学科在当今这个信息爆炸的时代确实有着举足轻重的作 用。 1 3 课题的来源及主要内容 关联规则是数据挖掘过程所要挖掘的一类很重要的模式或知识。可用它来描述事物 之阐在特定条件下存在的某种强度的联系。随着大量数据不停地收集和存储，许多业界 人士对于从他们的数据库中挖掘关联规则越来越感兴趣。从大量商务事务记录中发现有 趣的关联关系，可以帮助制定许多商务决策。比如，在前面所讲的美国加州连锁店的例 子中，经关联规则挖掘后发现：男性顾客购买婴儿尿布的同时常常还要购买啤酒。这个 发现就是一个有用的关联规则，它描述了超市中两种商品之间在“周末或下班后”、 “男性顾客购买”这些条件下的一种强的y e 黔- j e 系。现实中，这样的例子很多。例如超 级市场利用前端收款机收集存储了大量的售货数据，这些数据是一条条的购买事务记 录，每条记录存储了事务处理时间，顾客购买的物品、物品的数量及金额等。这些数据 中常常隐含形式如下的关联规则：在购买铁锤的顾客当中，有7 0 的人同时购买了铁 钉。这些关联规则很有价值，商场管理人员可以根据这些关联规则更好地规划商场，如 把铁钉和铁锤这两样商品摆放在起，能够促进销售。 有些数据不象销售数据那样很容易就能看出一个事务是很多物品的集合，但是稍微 转换一下思考角度，仍然可以象销售数据一样处理。比如人寿保险，一份保单就是一个 事务。保险公司在接受保险前，往往需要记录投保人详尽的信息，有时还要到医院做身 体检查。保单上记录投保人的年龄、性剐、健康状况、工作单位、工作地址、工资水平 等n 这些投保人的个人信息就可以看作事务中的物品，通过分析这些数据，可以得到类 似以下这样的关联规则：年龄在4 0 岁以上，工作在a 区的投保人当中，有4 5 的人曾 经向保险公司索赔过。在这条觌则中，“年龄在4 0 岁以上”是物品甲，t 。工作在a 一3 一 沈阳工业大学硕士学位论文 区”是物品乙，“向保险公司索赔过”是物品丙。可以看出来，a 区可能污染比较严 重，环境比较差，导致工作在该区的人健康状况不好，索赔率也比较高。 目前，国内外的研究者在关联规则挖掘方面已经作了很多工作，并获得突破性进 展。但是仍然有一些领域需要在今后的工作中不断地被填补，具体表现在如下几个方 面： ( 1 ) 有效去除数据噪音 ( 2 ) 自动生成多概念层挖掘的背景知识概念树 ( 3 ) 挖掘带有约束条件的关联规则 ( 4 ) 研究更高效率的挖掘算法 ( 5 ) 可视化表达挖掘的关联规则 在本次课题研究中，我就是要把工作重心放在提高关联规则挖掘算法的效率方面。 我首先对前人的工作进行了分析总结，发现最典型最经典的算法是a p r i o r i 算法。这个 算法的突出特点是：为了生成频繁k 项集，先生成候选频繁k 项集，而候选频繁k 项集 的产生又依赖于频繁k - 1 项集，这就增加了数据库的扫描次数，降低了算法的运行效 率。为了改掉这个弊端，我调整了数据库的存储方式，使数据库的逻辑存储方式是一棵 树或者是一个双淘链表的形式，这样就不需要在生成频繁项集之前先产生候选频繁项集 了，提出了不需要产生候选频繁项集的关联规则生成算法，并将算法应用于股市板块联 动中。近年来我国股市逐渐走向规范化，股票涨跌信息量成指数倍增长，各个行业之间 的连带关系千丝万缕，这种关系我们称之为板块联动关系。股票信息随时间千变万化。 虽然商业方面的数据也是很好的研究对象，但是对我们业外人士来说很难获得，而网络 时代为我们研究关联规则挖掘提供了数据来源。因此我们把股市各板块每天收盘价的涨 跌信息作为挖掘关联规则的应用实例。具体工作安排如下：首先对数据挖掘技术有一个 总体的认识，了解数据挖掘的基本过程及一般方法，从总体上把握该门技术；接着把重 点放在关联规则挖掘方法上，对当前有关挖掘关联规则的算法作了比较深入的探讨，详 细分析了a p r i o r i 算法、a i s 算法和d h p 算法的基本思想，吸取其中对我有帮助的成 分，鉴于这些算法的基本出发点都是先产生候选频繁项集，然后在此基础上生成频繁项 集，这就需要多次扫描数据库以判断哪些候选是真正的频繁项集，哪些候选不士频繁 项，时间浪费在扫描数据库上，当候选项集很大时，这种浪费就显得尤为突出。基于这 点考虑，我们提出了不需要产生候选大项集来生成频繁项集的算法，弥补了传统算法中 因扫描数据库次数过多造成的效率偏低的不足，因此提高了关联规则挖掘算法的的运行 效率。除此之外，在由频繁项集生成关联规则时，尽量采用已经确定的关联规则结果来 d 沈阳工业大学硕士学位论文 判定即将产生的规则是否满足规则成立条件，从而使除法运算次数趋于最小，这又在一 定程度上节俭了时间。从这两个方面着手来改进原有算法，并将新算法应用到股市板块 联动中，看看能否达到预期运行结果。 5 沈阳工业大学硕士学位论文 2 数据挖掘技术概述 数据挖掘( d a t am i n i n g ，简称d m ) ，又译作数据开采。它可定义为：从大量数据 中鉴别出有效模式的非平凡过程，该模式是新的、可能有用的和最终可理解的 4 i 。d m 的定义还有一些不同的表达形式，但其本质都是样的，即从数据库中提取隐含的、感 兴趣的、高水平的模式，其目的是为数据库理解与应用提供自动化、智能化的手段。 数据挖掘的前身是知识发现( k n o w le d g ed i s c o v e r yf r o md a t a b a s e s 简称 皿d ) ，是人工智能、机器学习与数据库技术相结合的产物。机器学习( m a c h i n e l e a r n i n g ) 是用计算机模拟人类学习过程的一门科学，始于6 0 年代末，但真正发展是 在7 0 年代末。由于在专家系统的研究开发中存在知识获取的瓶颈问题，所以设法采用 机器学习来完成知识的自动获取。k d d 一词是在1 9 8 9 年于美国底特律市召开的第一届 k d d 国际学术会议上正式形成的。国际k d d 学术会议起初每两年召开一次，1 9 9 3 年后 每年召开次。 数据挖掘的研究领域主要包括以下几个方面； ( 1 ) 定性知识与定量知识的发现； ( 2 ) 数据汇总； ( 3 ) 知识发现方法； ( 4 ) 数据依赖关系的发现和分析； ( 5 ) 发现过程中知识的应用： ( 6 ) 集成的、交互式的知识发现系统： ( 7 ) 知识发现的应用。 由于数据库中的数据被形象地喻为矿藏，因此数据挖掘( d a t a m s n i u g ) 一词于 1 9 9 5 年在加拿大召开的第一届知识发现和数据挖掘国际会议e 被提出，并很快流传开 来。 2 1 数据挖掘的基本过程及一般方法 数据挖掘过程，如图2 - - i 所示，是一个由多个步骤相互连接、反复进行人机交互 的过程。具体包括： ( 1 ) 建立一个目标数据集：选择一个数据集或在多数据集的子集上聚焦。 ( 2 ) 数据清理和预处理：去除噪声或无关数据，去除空白数据域，考虑时间顺序和数据 变化等。 6 沈阳工业大学硕士学位论文 ( 3 ) 数据换算和投影：找到数据的特征表示，用维变换或其它转换方法减少有效变量的 数目或找到数据的不变式。 ( 4 ) 选择特定的挖掘；根据数据挖掘的目的，选择某个特定的数据挖掘算法( 如汇总、 分类、聚类等) ，用于搜索数据中的模式，该算法可以是近似的( 如采样算法 等) 。 ( 5 ) 解释：解释某个发现的模式，去掉多余的不切题意的模式，转换成某个有用的、便 于用户理解的模式。 ( 6 ) 发现知识：把这些知识结合到运行系统中，发挥这些知识的作用或证明这些知识， 用预先可信的知识检查和解决知识中可能存在的矛盾。 口 毒 ，j 。一 f i垦堡墼量jl i l 预处理+ 叫 匝基困l l 塑坐墨夔量fl 转i 一 转换+ 叫 毒 等 互b 图2 1 数据挖掘的基本过程 上述基本过程在实际数据挖掘过程中并不是一成不变的，要根据具体情况适当地选 择相应的运行步骤。 数据挖掘是多学科和多技术交叉综合的新领域，它综合了机器学习、数据库、专家 系统、模式识别、统计、管理信息系统、基于知识的系统、可视化等领域的有关技术， 因而数据挖掘的方法是极其丰富的。下面列举了几种常用的数据挖掘技术，具体使用 时，可针对目标数据库的特点及所要挖掘的知识类型，采用相应的方法。 7 沈阳工业大学硕士学位论文 ( 1 ) 决策树 在数据挖掘中最常使用的方法就是决策树方法，它属于归纳学习方法。它的基本想 法是：给一组用属性描述的训练例，然后按属性( 值) 构造一棵树( - - 叉树或多叉 树) ，从根节点到叶节点是一条规则，叶节点就是一个类，由这棵树( 或由这棵树形成 的规则集) 对另一组测试例进行分类( 或) 预测。这棵树就是知识。 决策树归纳方法主要有两个问题：一是先从哪一属性往下分叉，即特征选择问题 ( 或称偏向问题) ，二是如何构造一棵“好”的树( 树剪枝问题) 。为解决前一问题研 究出许多方法：最有代表性的是i d 3 ( 改进的c 4 5 ，c 5 o ) ，该方法用信息熵来找出最 大增益作为构造树的依据。剪枝一般来说有两种策略：向前剪枝和向后剪枝。许多人给 出各种剪枝方法，究竟采用什么剪枝方法，视问题而定。 决策树方法的优点是速度快，直观可理解，所以被广泛采用，但由于它是归纳学习 方法，它有两个弱点：树不唯一且不永真。一般来说精度也不高。为了提高精度，近年 来发展起来的b a g g i n g 和b o o s t i n g 方法取得较好的效果。在选择特征上也有人提出信 息熵之外的方法，也有人提出多属性方法，即决策树向下分叉时不是用一个属性，而是 用多个属性，也就是多属性( 变量) 决策树。 ( 2 ) 分类 分类在数据挖掘中是一项非常重要的任务。分类的目的是学会一个分类函数或分类 模型( 也常常称作分类器) ，该模型能把数据库中的数据项映射到给定类别中的某一 个。分类和回归都可用于预测。预测的目的是从利用历史数据记录中自动推导出对给定 数据的推广描述，从而能对未来数据进行预测。和回归方法不同的是，分类的输出是离 散的类别值，而回归的输出则是连续数值。 要构造分类器，需要有一个训练样本数据集作为输入。训练集由一组数据库数据记 录或部分元组映射的记录构成，每个元组是一个由有关属性值组成的特征向量，除了这 些外，训练样本还有一个类别标记，不同的分类器有不同的特点。另外要注意的是，分 类的效果一般和数据的特点有关，有的数据噪声大，有的数据有缺省值，有的分布稀 疏，有的字段或属性间相关性强，有的属性是离散的而有的是连续的或者是混合式的。 目前普遍认为不存在某种方法能适合于各种特点的数据。 ( 3 ) 聚类 在某些情况下，没有办法界定要分析的数据类，这时使用聚类算法发现以前不知道 的数据类或怀疑的数据类。它属于描述模型，有缺陷分析。其过程是找出一个共享一些 ，g 沈阳工业大学硕士学位论文 公共类别的群体，把类似的实例聚类的例子分到不同的组。聚类过程可以以某一特定案 例为依据，这时确定该案例类别的有关规则是未知的，聚类过程就能确定这种规则。 ( 4 ) 粗糙集 粗糙集理论是一种新型的处理模糊和不确定知识的数学工具。自1 9 8 2 年由波兰数 学家p a w l a k 首次提出以来，经过几十年的研究与发展，已经在理论和实际应用上取得 了长足的进展，特别是由于八十年代末和九十年代初在知识发现等领域得到了成功的应 用而受到国际上广泛关注。目前，它己经在人工智能、知识发现、模式识别与分类、故 障检测等方面得到了较为成功的应用。粗糙集理论具有一些独特的观点，这些观点使得 粗糙集特别适合于进行数据分析。粗糙集理论认为知识的粒度性是造成使用已有知识不 能精确地表示某些概念的原因。通过引入不可区分关系作为粗糙集理论的基础，并在此 基础上定义了上下近似等概念，粗糙集理论能够有效地逼近这些不精确概念。和模糊集 合需要指定成员隶属度不同，粗糙集的成员是客观计算的，只和已知数据有关，从而避 免了主观因素的影晌。 ( 5 ) 贝叶斯网络 八十年代贝叶斯网络成功地应用于专家系统，成为表示不确定性专家知识和推理的 一种方法。九十年代以来，研究者们进一步研究了直接从数据中学习并生成贝叶斯网络 的方法，为贝叶斯网络用于数据挖掘和知识发现开辟了新途径。这些新的方法和技术还 在发展之中，但已在些数据建模问题中显示出令人瞩目的效果。与其它用于数据挖掘 的表示法如规则库、决策树、人工神经网络相比，贝时斯网络有如下特点：适合处理不 完整数据集问题，可以发现数据间的因果关系，可以综合先验信息( 领域知识) 和样本 信息，在样本难以获得或者代价高昂对特别有用。可以预见，在数据挖掘和知识发现 中，贝叶斯网络将成为一个有力的工具。贝叶斯网络至少可以解决如下四个方面的问 题：其一是贝叶斯网络能够真正地处理具有不完整的数据集合；其二是贝叶斯网络能够 获得因果联系；其三是贝叶斯网络能够更有机更充分地利用已有的知识和观钡4 数据进行 学习、预测；其四是贝叶斯网络结合其它一些方法可以有效地避免数据的过度拟合。 ( 6 ) 关联规则 关联规则挖掘问题的提出：在大型零售商店或超级市场，存储了大量的销售记录， 这些销售记录又称为货篮数据( b a s k e td a t a ) 。货篮数据保存了顾客在次购买中所 涉及的商品的详情( 如商品名称、价格、数量等) ，我们称之为事务。数据库仅存大量 的事务数据，决策者们想从这些数据中发现有用的信息，指导他们的营销活动。在这样 的应用背景下，产生了关联规则挖掘算法，用来从事务数据库中发现有关客户购买行为 一9 沈阳工业大学硕士学位论文 的知识。顾客购买一些商品与另外一些商品之间的关系，称之为关联规则。以后关联规 则又被广泛应用到其他领域。这种方法就是本文所采用的方法。 当然，这些方法不是孤立使用的，为了发现某类知识，常常要综合应用这些方法。 2 2 数据挖掘的系统结构 数据挖掘的系统结构，如图2 - 2 所示，是一种c l i e n t s c h v c r 结构，特定的数据挖掘 请求经客户端的挖掘界面送到服务器端的数据挖掘内核，数据挖掘内核通 过数据访问接口( d a t aa c c e s sa p i ) 在某个特定的数据库或文件系统进行相应的挖 掘处理后，再将最终的挖掘结果反馈给挖掘界面。系统中的数据访问接口可为 o d b c 接口或a d o 接口；数据源可以是应用最为广泛的关系数据库，也可以是般文 件系统、w w w 数据或其它包含复杂结构数据的数据库，如面向对象数据库、多媒体数 据库、空间数据库、时态数据库等； 其中数据挖掘内核，根据其目的不同，可分为如图2 3 所示的若干模块，每个模块 用来发现一类规则( 或称为知识) ，每类规则的具体描述如下： ( 1 ) 关联规则( a s s o c i a t i o nr u l e ) ：描述事物之间的某种联系。例如，某些疾病会引 发诸多并发症，那么，这种疾病和它的并发症之间就存在某种关联关系。 ( 2 ) 分类规则( c l a s s i f i c a t i o nr u l e ) ：将一组相关的数据集按照某种原则分成若干 类的规则。例如，可用某个分类规则将各种各样的疾病按照症状的不周，分成各种 疾病类。 0 ) 特征规则( c h a r a c t e r i s t i cr u l e ) ：是对目标类的某个或某些特征的描述。例 如：可用一个特征规则来对某个特定疾病的症状进行描述。 1 0 沈阳工业大学硕士学位论文 图2 _ 2数据挖掘的系统结构 e 二二二) f 知识库l 、_ - _ i _ _ _ _ - _ _ _ l 一一 ( 4 ) 判别规则( d i s c r i m i n a n tr u l e ) ：是一种将耳标类与其它类区别开来的特性描述 模式。例如 可用一个判别规则描述某种疾病的某些特殊症状，以便于将其与其 它疾病区分开来。 ( 5 ) 预测规则( p r e d i c a t i o nr u l e ) ：是根据一组数据已有的分布情况，来预测某个相 关数据的可能值的一种模式。例如，一个刚进公司的员工想要知道他今后的报酬如 何，可根据公司中与他情况类似的老员工的薪金分布来作出大概预测。 沈阳工业大学硕士学位论文 ( 6 ) 演化规则( e v o l u t i o nr u l e ) ：是对某个事物在某特定时间段内的演化趋势作出估 计的一种模式。例如，可用某个演化规则来对某种特定的股票在未来一段时间内可 能出现的变化趋势作出初步预测。 在数据挖掘内核中，除了以上各规则的挖掘模块，还可以加入元规则指导的规则挖掘 器，以及基于多概念层的规则挖掘器。 图2 - 3 数据挖掘内核的构成 2 3 数据挖掘成功的关键 数据挖掘不是给出一些数据，采用些数据挖掘算法就可以轻易地挖掘出知识，数 据挖掘成功的关键必须做到下面几点： ( 】) 有明确的目标：用数据挖掘方法要解决什么问题，挖掘什么样的模式、规律或知 识，必须提出要挖掘的目标。这一点是能否挖掘出有用知识的基本点。不能说，我 给你一些数据，你给我挖掘出知识来。在给出数据后，采用什么挖掘方法，怎样挖 掘，必须在有明确目标隋况下进行，盲目地挖掘使挖掘系统无法进行。 ( 2 ) 相对较长一段时间和相对准确的数据积累：数据是知识发现的基础，数据的质量和 数量对知识发现起决定性作用，不是随便给一些数据就能挖掘出有用的知识，数据 1 2 沈阳工业大学硕士学位论文 必须有一定的质量和数量，在极不完整的数据上进行数据挖掘，是不会得到好的结 果的，往往数据质量和数量比数据挖掘方法更重要。 ( 3 ) 领域专家的参与和指导：从目标的明确到得到信息，以及知识的评价与判断，这些 都需要领域专家的指导，否则知识的可信度和可靠性都值得怀疑。 ( 4 ) 数据挖掘是一个新兴的研究领域，目前还处在发展的阶段，还有很多的难题亟待解 决。 1 3 沈阳工业大学硕士学位论文 3 关联规则挖掘综述及算法讨论 通过前面的有关介绍，我们已经知道数据挖掘的最终知识是一组规则。关联规贝u 就 是其中一类很重要的规则。在现实生活中，诸多事物之间看似毫无联系，但在某些场合 或条件下却隐含着某种联系。关联规则就是对这类联系的一种描述，它在现实生活中具 有广泛的用途。例如，从超级市场通过条形码阅读器得到的数据库中，数据项对应商 品，每条交易对应某一时刻被购买的商品集( 数据项集) ，通过挖掘其中的关联规则， 我们可以发现类似如下的规则：购买面包和黄油的同时有9 0 的顾客可能购买牛奶。 为促销牛奶，决策者可以依据这条规则将存放牛奶的货架紧挨存放面包和黄油的货架。 再如，从出版物数据库中可获取出版物之间互相引用的情况，如果发现某类出版物被引 用率较高，出版商可以制定促销该出版物的新计划。1 9 9 3 年，a g r a w a l 、i n m i e l i n s k i 和s w a m i 等人首先提出了关联规则的基本概念，并且给出了一种从所有属性都是b o o l 型的关系表中发现关联规则的算法。 3l 关联规则的基本模型 设i = ( i ，i 。，i ) 是数据项的集合，数据库d 是事务t 的集合，其中每个事 务t 是项的集合，使得t a i 。每一个事务有一个标识符，称作t i d 。设a 、b 是数据项 的集合( 简称项集) ，事务t 包含a 当且仅当a t 。关联规则是形如a b 的蕴涵式， 其中a c i ，b i ，并且a r 、b = o 。规则a b 在事务集d 中成立，具有支持度s ，其中 s 是d 中事务包含a u b ( 即a 和b 二者) 的百分比。它是概率p ( a u b ) 。规则a j b 在 事务集d 中具有置信度c ，其中c 是d 中包含a 的事务同时也包含b 的百分比，它是条 件概率p ( b a ) 。即； s = s u p p o r t ( a = b ) = p ( a u b ) c = c o n f i d e n c e ( a j b ) = p ( b a ) 同时满足最小支持度阈值( m i n _ s u p ) 和最小置信度阈值( m i n _ c o n f ) 的规则称作 强规则。在研究关联规则之前，还应该了解如下几个常常涉及的概念： 项集：项的集合。包含k 个项的项集称为k 一项集 一1 4 沈阳工业大学硕士学位论文 项集的频度( f r e q u e n c y ) ：又称支持度( s u p p o r t ) 3 3 ，是指含有该项集的记录 在数据库中出现的概率，用f r 来表示。例如，数据库的总行数为n ，项集a 的频度记 为f r ( a ) ，项集a 在数据库中出现了m 次，则项集a 的频度f r ( a ) = m n 。 频繁项集：它是这样一些项集，项集的支持度不小于最小支持度阈值。“频繁”这 一词汇，在本文中经常用到，它是一个很形象的词汇，凡是支持度大于或等于最小支持 度阂值的，就称之为频繁的。 3 2 关联规则的研究现状 挖掘关联规则，就是在大型数据库中发现所有可能有用的或者用户感兴趣的强关联 规则的过程。按照文献 3 3 提出的思想，挖掘关联规则一般可以分为以下两个步骤： ( 1 ) 求出频繁项集的集合( f r e q u e n ts e t s ) 。这些项集出现的频繁性至少和预定 义的最小支持计数一样。 ( 2 ) 由频繁项集产生强关联规则。这些规则必须满足最小支撇和最小置信度。如 果愿意，也可以使用附加的兴趣度度量。 在这两步中，第二步的工作比较简单直接，挖掘关联规则的总体性能由第步决 定。具体来说，若已知所有频繁项集的集合为f ，x 为f 中的任一频度项集，设项集 y x ，测试规则c ( y j x - y ) ，测试该规则的置信度是否大于设定的最小置信度闽值， 若是，则规则y jx y 是强关联则。按此方法郎能将f 中所能构造的所有强关联规则我 出来。因此，挖掘关联规则算法的主要工作应集中在第一步，即设法高效地发现目标数 据库中包含的所有的频繁项集。为了测试某些特定项集是否是频繁项集，不可避免地需 要扫描整个数据库。如果目标数据库很大，应设法尽可能减少扫描数据库的次数。 r a g r a w a l 等人在1 9 9 3 年首先提出了关联规则的挖掘问题并给出解决此问题最原 始的算法m s 3 2 】之后，该问题得到了国际人工智能和数据库等领域学者的密切关注， 提出了多种算法，其中最为经典的算法当属a p f i o l i 挖掘算法，其后又有人在此基础上 提出了d h p 关联规则挖掘算法。这几个算法的共同之处在予先生成候选频繁项集，再 扫描数据库判断每个候选频繁项是否是真正的频繁集。下面就分别介绍这几个算法： ( 1 ) a i s 算法 a i s 算法也是采用多次扫描数据库的方法来获得所有的频繁集。只不过其生成候选 频繁项集( c a n d i d a t e s e t s ) 的方法与a p r i o r i 算法不同，并不是在获得某一维频繁集 之后再生成下一维的候选项集的集合，而是在扫描数据库的过程中不断更新候选项集的 集合。 一1 5 沈阳工业大学硕士学位论文 算法首先构造一个只含有单个空项集的初始集( f r o n t i e rs e t ) ，然后扫描数据 库，在扫描每个记录时，对初始集中包含于当前记录的各项集进行扩展( 扩展其维 数) ，并将该扩展项集( e x t e n d e ds e t ) 加入候选项集的集合，同时，估计该扩展项集 是否是频繁集( 根据项集的各个项或属性在数据库中出现真值的频率来估计) ，若是， 则对其继续扩展，直到某次扩展所得项集被估计为非频繁集或再也不能扩展时为止。当 完整扫描一次数据库后，可根据各候选项集的实际频度，筛选出真正的频繁集。这时， 须将所有一开始被估计为非频繁集而最终经证实却又恰恰是频繁集的候选项集加入到初 始集中去，作为下次扫描数据库时构造候选项集的初始集。之所以这样做，是因为它们 的超集也有可能是频繁项集，但在本次数据库扫描程序中却未能得到检测，而有待于进 一步验证。 具体算法如下： 输入：o 、1 i r 的值，目标数据库d ，d 的大小d b s i z e 输出：所有频繁项集的集合f r e q u e n t s e t s 。 算法流程： p r o c e d u r el a r g e l t e m s e t s ( ) b e g i n f r o n t i e r s e t s = ( () ) ；术清空f r e q u e n t s e t s w h i l e ( f r o n t i e r s e t s 不为空) d o b e g i n 将c a n d i d a t e s e t s 清空： f o r a llt r a n s a c t i o n si ndd o f o r a l li t e m s e t sf f r o n t i e r s e t sd o i f ( t 中包含f ) t h e n b e g i n e x t e n d s e t s = e x t e n d ( t ，f ) ： f o r a lli t e m s e t sei ne x t e n d s e t sd o i f ( c a n d i d a t e s e t s 中已存在项集e ) t