（电路与系统专业论文）有效关联规则挖掘方法的研究[电路与系统专业优秀论文].pdf

摘要 近年束，数据挖掘己经成为人工智能、模式识别等领域的研究热点。伴随着数据 量的急剧增长，数据挖掘技术已经越来越引起人们重视。其中，关联规则是数据挖掘 中最活越的研究方向之一。本文对关联规则数据挖掘进行了较为深入的分析和研究。 主要工作包括以下几个方面： l 目前，灭联舰则的研究 要集中在效率的提高 ：。针对规则的分析相对较少。 本文首先分析了关联规则的衡量标准以及规则的前件与后件的相关性问题，总结了目 | ；1 对挖掘有效关联规则的相关研究。针。对传统关联规则中无法描述规则前件与后件的 相关性问题，提出了一种新的挖掘有效关联规则的框架：支持度一匹配度。将该框架f 生成的规则，j 支持度一置信度框架下生成的规则做了比较。结果表明，用所提出的方 法生成的规则4 i 仪前件和后件具有较高的相关性，而且减少了冗余规则的生成。最后， 给出该框架的扩鼹应用及部分实验结果。 2 在实际应用中，数据库或数据仓库是随时间变化的，因而其中的关联规则也随 之变化。已有许多研究人员对如何高效的更新关联规则进行了分析和研究，并提出了 相应的算法。其中关联规则的更新主要涉及三个方面：第一方面，在给定的最小支持 度和最小置信度f ，当个新的数据库d b 添加到数据库d b 中时，如何生成d b + d b 中的关联规则：第二：方面，在给定最小支持度和最小置信度下，当数据库d b 从d b 中删除时，如何生成d b d b 中的关联规则：第三方面，考虑新增加的d b 的新颖性时， 如何进行加权增量更新。 2 1 首先，本文针对第一方面进行了分析和研究，并提出了一种基于向量的增量 更新算法v f e p ( v e c t o r b a s e df a s tu p d a t i n ga g o r i t h m ) ，将浚算法和已有的增量 更新算法进行了分析和比较，说明了该算法的商效性和可行性。 2 。2 其次，对最小支持度，最小置信度不变的情况下，新增数据库d b 时的关联 舰则更新问题，进行了分析和研究。考虑到新增数据库的新颖性、以及生成规则的有 趣性等问题，本文结合v f u p 算法的效率以及匹配度的思想，提出了基于项目集加权 的增量更新算法。即：在新增数据库d b 中采取频繁项目集与非频繁项目集同时加权 的方法来挖掘d b + d b 中的关联规则。这样可以增加d b 中频繁项目集和非频繁项目集 对d b + d b 中关联规则的影响。在进行n 次增量更新算法的设计时，首先，结合增量更 新和加杈的特点，设计高效的算法束提高效率。在规则分析中采取新的框架理论，来 分析得到的规则。最后，将加权增量更新得到的结果同增量更新算法得到的结果进行 分析和比较，实验表明浚方法是有效的。 关键词：数据挖掘关联规则兴趣度加权增量更新匹配度 a b s t r a c t d a t a m i n i n g h a sb e c o m ear e s e a r c h h o t s p o t i n m a n y f i e l d ss u c ha sa r t i f i c i a l i n t e l l i g e n c ea n dp a t t e r nr e c o g n i t i o ni n r e c e n ty e a r s ；w i t ht h er a p i d i n c r e a s i n go fd a t a q u a n t i t y , t e c h n o l o g i e so fd a t am i n i n gh a v er e c e i v e d m o r ea n dm o r ea t t e n t i o n m i n i n g a s s o c i a t i o nr u l e si so n eo ft h em o s ta c t i v ed i r e c t i o n si nd a t am i n i n g i nt h i s p a p e r , t e c h n o l o g i e so fm i n i n ga s s o c i a t i o nr u l e sa r eg i v e nad e e pa n a l y s i sa n dr e s e a r c h ，a n dt h e m a i nw o r ki n c l u d e st h ef o l l o w i n gs e v e r a la s p e c t s ： 1n o wt h er e s e a r c ho na s s o c i a t i o nr u l e si sf o c u s e do nh o wt oe n h a n c ei t se f f i c i e n c y r a t h e rt h a na n a l y z et h er u l e s i nt h i sp a p e r , t w op r o b l e m sa b o u tt h ec r i t e r i o no fe v a l u a t i n g a s s o c i a t i o nr u l e sa n dt h er e l a t i v i t yb e t w e e nt h ea n t e c e d e n ta n dt h ec o n s e q u e n ta r eg i v e n f i r s t ，a n dt h e nt h er e l a t e dr e s e a r c ha b o u tm i n i n gv a l i da s s o c i a t i o nr u l e si ss u m m a r i z e d a n e wf r a m e ，s u p p o r t m a t c h , f o rm i n i n gv a l i da s s o c i a t i o nr u l e si sp r o p o s e di no r d e rt o r e m e d y t h el i m i t a t i o no ft h et r a d i t i o n a lo n ew h i c hi se n a b l et od e s c r i b et h e r e l a t i v i t y - q u e s t i o n so fa n t e c e d e n ta n dc o n s e q u e n to ft h er u l e t h e na r le x a m p l e i sg i v e nt o c o m p a r et h er u l e sc r e a t e db ym a t c hf r a m ew i t ht h eo n e sc r e a t e db ys u p p o r t - c o n f i d e n c e f r a m e r e s u l t sh a v es h o w nt h a tt h en e wa p p r o a c hn o to n l yc o n t a i n st h eh i g hr e l a t i v i t y b e t w e e nt h ea n t e c e d e n ta n dt h ec o n s e q u e n tb u ta l s or e d u c e dt h en u m b e ro f r e d u n d a n tr u l e s a n ds o m e e x p a n d e da p p l i c a t i o n so f t h i sn e w f r a m eh a v eb e e ng i v e nw i t hs o m er e s u l t s 2i nr e a l w o r l da p p l i c a t i o n s t h ea s s o c i a t i o nr u l e sa r ec h a n g i n gb e c a u s et h ed a t a b a s e s o rt h ed a t aw a r e h o u s e sa r ec h a n g i n ga l o n gw i t ht i m e s o m er e s e a r c hw o r k e r sh a v et a k e n u pi nh o w t ou p d a t et h ea s s o c i a t i o nr u l e sw i t hh i g he f f i c i e n c ya n ds o m ea l g o r i t h m sh a v e b e e np r o p o s e d u p d a t i n gt h ea s s o c i a t i o nr u l e sm a i n l yi n v o l v e st h r e ea s p e c t s ：f i r s t l y , h o w t oc r e a t ed b + d ba s s i o c i a t i o nr u l e sw h e nan e wd a t a b a s ed bi sa d d e di n t od a t a b a s ed b s e c o n d l y h o wt oc r e a t et h ed b d ba s s o c i a t i o nr u l e sw h e nd a t a b a s ed bi s d e l e t e df r o m d a t a b a s ed b a n dt h i r d l y , h o wt ou p d a t ei n c r e m e n t sw i t hw e t g h t sw h e n g i v e nt h en o v e l t y o f t h en e wd a t a b a s ed b 2 1f i r s to fa 1 1 t h i sp a p e rc a r r i e so nt h ea n a l y s i sa n dr e s e a r c ht ot h ef i r s ta s p e c ta n d a d v a n c e san e w a p p r o a c ho f v f u p ( v e c t o r - b a s e df a s tu p d a t i n ga l g o r i t h m ) a n dc o m p a r e s t h en e w a p p r o a c hw i t ht h ef o r m e ro n e ，w h i c hs h o w s t h eh i g he f f i c i e n c ya n dt h ef e a s i b i l i t y o f t h en e wo n e 2 2t h e n t h ep r o b l e mo fh o wt ou p d a t et h ea s s o c i a t i o nr u l e sw h e na d d i n gan e w d a t a b a s ed bw i t h o u tc h a n g i n gt h em i n i m a ls u p p o r ta n dt h em i n i m a lc o n f i d e n c ei sg i v e n a n da n a l y z e d an e w a l g o r i t h mo f i n c r e m e n t a lu p d a t i n gb a s e do n w e i g h i n g t h ei t e m s e t sh a s b e e ng i v e nc o m b i n i n gt h ee f f i c i e n c yo fv f u pa n dan e w c o n c e p to fm a t c h ，c o n s i d e r i n gt h e n o v e l t yo f t h e a d d e dd a t a b a s ea n dt h ei n t e r e s t i n go f t h er u l e s t h en e w a l g o r i t h mm i n e s t h e d b + d ba s s o c i a t i o nr u l e s b yw e i g h i n gt h ef r e q u e n c yi t e m s e t sa n dt h en o n f r e q u e n c y i t e m s e t ss i m u l t a n e o u s l yi nt h ea d d e dd a t a b a s ed b w h i c hc a ne n h a n c et h ee f f e c tt h a tt h e f r e q u e n c yi t e m s e t sa n dt h en o n - f r e q u e n c yi t e m s e t si nd a t a b a s ed bp r e s s e do nd b + d bi n t h ep r o c e s so fd e s i g n i n gt h ea l g o r i t h mo fn - i n c r e m e n t a lu p d a t i n g ，t h i sp a p e ri n t e n d st o d e s i g nah i g he f f i c i e n c ya l g o r i t h mt oi n c r e a s et h ee f f i c i e n c yc o m b i n i n gt h ep r o p e r t yo f i n c r e m e n t a lu p d a t i n gb a s e do nw e i g h i n ga n da n a l y z e st h er u l e sc r e a t e db yt h en e wf r a m e f i n a l l y , t h i sp a p e rc o m p a r e st h ea l g o r i t h mo f i n c r e m e n t a lu p d a t i n gb a s e do n w e i g h i n gw i t h t h eo n eo f i n c r e m e n t a lu p d a t i n g ；t h er e s u l t sh a v es h o w nt h ee f f i c i e n c yo f t h en e w o n e k e yw 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 s ；i n t e r e s t i n g ；w e i g h i n g ；i n c r e m e n t a lu p d a t i n g ； m a t c h 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究 _ w r 作及取得的研究成果。据我所知，除了文中特别加以标注和致 谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得东北师范大学或其他教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示谢意。 学位论文作者签名：倥里! 訇同期：在丛! ：至 学位论文版权使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位 论文的舰定，即：东北师范大学有权保留并向国家有关部f 或机 构送交学位论文的复印件和磁盘，允许论文被查阅和借阅。本人 授权东北师范大学可以将学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或其它复制手段保存、汇编 学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：在幽指导教师签名：越 f 1 期：石堕! 篁! 圣r h 学位沦文作者毕业后去向 1 ：作单位 通讯地址 期：丝签：丝 电话。三25 丝! n 6 鼬g 编：l 缝鳇星 第一章引言 1 1 数据挖掘背景 随着计算机互联网技术和数据库技术的迅速发展以及数据库管理系统的广泛应 用，人们积累的数据越来越多。激增的数据背后隐藏着许多重要的信息，人们希望能 够对其进行更高层次的分析，以便更好地利用这些数掘。目前的数据库系统可以高效 地实现数据的录入、金询、统计等功能，但无法发现数据中存在的关系和规则，无法 根掘现有的数据预测未来的发展趋势。缺乏挖掘数据背后隐藏的知t 的手段，导致了 “数据爆炸但知识贫乏”的现象。 数据挖掘技术是人们长期对数据库技术进行研究和丌发的结果。起初各种商业数 据是存储在计算机的数据库中的，然后发展到可对数据库进行查询和访问，进而发展 到对数据库的即时遍历。商业数据库现在正在以一个空前的速度增长，并且数据仓库 i f 扫二广泛地应用于各种行业；埘计算机硬件性能越来越高的要求，也可以用现在已经 成熟的并行多处理机的技术来满足；另外数掘挖掘算法经过了这1 0 多年的发展也逐 渐成为一种成熟、稳定目易于理解和操作的技术。数据挖掘使数据库技术进入了一个 更高级的阶段，它不仅能对过去的数据进行查询和遍历，并且能够找出过去数据之间 的潜在联系，从而促进信息的传递。现在数据挖掘技术在商业应用中已经可以投入使 用，凶为对这种技术进行支持的三种基础技术已经发展成熟，他们是：1 海量数据搜 集2 强大的多处理器计算机3 数据挖掘算法。 1 2 数据挖掘基本概念 数据库中发现知识( k d d ) 一词首次出现在1 9 8 9 年举行的第十届国际联合人工 智能学术会议上。到目前为【f ：，由美国人工智能协会主办的k d d 国际研讨会已经召丌 了8 次，规模由原来的专题讨论会发展到国际学术大会( 见表1 ) ，研究重点也逐渐 从发现方法转向系统应用，注重多种发现策略和技术的集成，以及多种学科之间的相 互渗透。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 技 术专叭并行计算、计算机网络和信息工程等其他领域的国际学会、学刊也把数据挖 掘和知i 发现列为专题和专刊讨论，甚至到了脍炙人口的程度。 数据挖掘( d a t am i n i n g ) ，为数据库中知识发现( k n o w e d g ed i s c o v e fd a t a b a s e ， k d d ) 的一个基本步骤，是从大量数据中提取出潜在的、新颖的、有价值的，并能被人 理解的模式的高级处理过程。数据挖掘目的：利用各种分析工具在海量数据中发现模 型和数据问关系，这些模型和关系可以用来做出预测。 典型的数据挖掘系统主要有以下组成部分： 数据库、数据仓库或其他信息库：足指一个或一组数据库、数据仓库或 其他类型的信息库。可以在数据上进行数据清理和集成。 数据库或数据仓库服务器：根据用户的需求，从数据库或数据仓库中提 取相关的数据。 知识库：是指领域知识，用于指导搜索，或评估结果模式的兴趣度。 数据挖掘引擎：由一组功能模块组成，用于特征化、关联、分类、聚类 分析以及演变分析和偏差分析。 模式评估：指对发现的模式进行评估，确定用户对他的兴趣程度。 图形用户界面：允许用户和数据挖掘系统进行通信，并与系统交互，指 定数据挖掘查询或任务，提供信息、帮助搜索聚焦等。 1 3 数据挖掘分类 1 3 1 模式分类 模式分类是一个分类函数( 分类器) ，能够把数据集中的数据项映射到某个给定的 类上。模式分类往往表现为一棵分类树，根据数据的值从树根开始搜索，沿着数据满 足的分支往上走，走到树叶就能确定类别。 1 3 2 聚类 聚类是把整个数据库分成不同的群组。它的目的是要群与群之间差别很明显，而 同一个群之间的数据尽量相似。与分类不同，在开始聚类之前你不知道要把数据分成 几组，也不知道怎么分( 依照哪几个变量) 。因此在聚类之后要有一个对业务很熟悉 的人来解释这样分群的意义。很多情况下一次聚类你得到的分群对你的业务来说可能 并不好，这时你需要删除或增加变量以影响分群的方式，经过几次反复之后才能最终 得到一个理想的结果。神经元网络和k 一均值是比较常用的聚类算法。 不要把聚类与分类混淆起来。在分类之前，你已经知道要把数据分成哪几类，每 个类的性质是什么，聚类则恰恰相反。 1 3 3 关联分析 关联分析是寻找数据库中值的相关性。常用的技术是共缓j 鲤刃巩关联规则是寻找 在同一个事件中出现的不同项的相关性，l v , 女n 在一次购买活动中所买不同商品的相关 性。 1 3 4 回归 嘲归是通过具有已知值的变量来预测其他变量的值。在最简单的情况下，回归采 用的是像线性回归这样的标准统计技术。但大多数现实世界中的问题是不能用简单的 线性回归预测的。如商品的销售量、股票价格、产品合格率等，很难找到简单有效的 方法术预测，因为要描述这此事什的变化所需的变量以上百计，且这些变量本身往往 2 ：i、j ， 2 3 4 5 6 “ 都是非线性的。为此人们又发明了许多新的手段来试图解决这个问题，如逻辑同归、 决策捌、神经网络等。 1 3 5 时间序列 时间序列是用变量过去的值来预测未来的值。与回归一样，它也是用已知的值来 预测未来的值，只不过这些值的区别是变量所处时间的不同。时问序列采用的方法一 般是在连续的时间流中截取一个时间窗口( 一个时间段) ，窗口内的数据作为一个数 据单元，然后让这个时间窗口在时间流上滑动，以获得建立模型所需要的训练集。比 如你可以用的六天的数据来预测第7 天的值，这样就建立了一个区间大小为7 的窗口。 1 3 6 序列模式 序列模式与关联模式相仿，把数据之间的关联性与时间联系起来。为了发现序列 模式，不仅需要知道事件是否发生，而且需要确定事件发生的时间。例如，在购买彩 电的人们当中，6 0 的人会在3 个月内购买影碟机。 在解决实际问题时，经常要同时使用多种模式。分类模式和回归模式是使用最普 遍的模式。分类模式、回归模式、时间序列模式也被认为是受监督知识，因为在建立 模式前数据的结果是己知的，可以直接用束检测模式的准确性，模式的产生是在受监 督的情况下进行的。般在建立这些模式时，使用部分数据作为样本，用另部分 数据来检验、校正模式。聚类模式、关联模式、序列模式则是非监督知识，因为在模 式建立前结果是未知的，模式的产生不受任何监督。 1 4 数据挖掘前景分析 随着k d d 在学术界和工业界的影响越来越大，国际k d d 组委会于1 9 9 5 年把专题 讨沦会更名为国际会议，在加拿大蒙特利尔市召开了第一届k d d 国际学术会议，以后 每年召开一次。近年来，k i ) d 在研究和应用方面发展迅速，尤其是在商业和银行领域 的应用比研究的发展速度还要快。 目前，国外数据挖掘的发展趋势其研究方面主要有：对知识发现方法的研究进一 步发展，如近年来注重对b a y e s ( 贝叶斯) 方法以及b o o s t i n g 方法的研究和提高：传 统的统计学回归法在k d d 中的应用；k d d 与数据库的紧密结合。在应用方面包括：k d d 商业软件工具不断产生和完善，注重建立解决问题的整体系统，而不是孤立的过程。 用户t 要集中在火型银 r 、保险公司、电信公司和销售业。囫辨很多计算机公司一 e 常 蘑视数据挖掘的开发应用，i b m 和微软都成立了相应的研究中心进行这方面的工作， 此外，一些公司的相关软件也丌始在国内销售，如p l a t i h u m 、b o 以及i b m 。 国内从事数据挖掘研究的人员主要在大学，也有部分在研究所或公司。所涉及的 研究领域很多，一般集中于学习算法的研究、数据挖掘的实际应用以及有关数据挖掘 理论方面的研究。 j 前进行的大多数研究项目是由政府资助进行的，如国家自然科学 基金、8 6 3 计划、”九五“计划等，但还没有关于国内数据挖掘产品的报道。 一份最近的g a r tr l e r 报告中列举了在今后3 5 年内对工业将产生重要影响的五 项关键技术，其中k d d 和人工智能排名第一。同时，这份报告将并行计算机体系结构 研究和k d d 列入今后5 年内公司应该投资的1 0 个新技术领域。 u 丁以看出，数据挖掘的研究和应用受到了学术界和实业界越来越多的重视。进行 数据挖掘的开发并不需要太多的积累，国内软件厂家如果进入该领域，将处于和图外 公司实力相差不很多的起跑线，卜，并且，现在关于数据挖掘的一些研究成果可以在 i n t e r n e t 上免费获取，这更是一个可以利用的条件。我们希望数据挖掘能够引起国 内实业界更多的重视，同时也希望能够有更多的国内软件厂商进入该领域，起促进 数据挖掘技术在中国的应用。 随着d m k d 研究逐步走向深入，数据挖掘和知识发现的研究已经形成了三根强 大的技术支柱：数据库、人工智能和数理统计。因此，k d d 大会程序委员会曾经出这 三个学科的权威人物同时来任主席。目前d m k d 的主要研究内容包括基础理论、发现 算法、数据仓库、可视化技术、定性定量互换模型、知识表示方法、发现知识的维护 和再利用、半结构化和非结构化数据中的知识发现以及网上数据挖掘等。 当前，d m k d 研究方兴未义，其研究与开发的总体水平相当于数据库技术在7 0 年 代所处的地位，迫切需要类似于关系模式、d b m s 系统和s o l 查询语言+ 等理论和方法 的指导，才能使d m k d 的应用得以普遍推广。预计在本世纪，b m k b 的研究还会形成更 大的高潮，研究焦点可能会集中到以下几个方面： 发现语言的形式化描述，即研究专门用于知识发现的数据挖掘语言，也许会像 s q l 语言一样走向形式化和标准化： 寻求数据挖掘过程中的可视化方法，使知识发现的过程能够被用户理解，也便 于在知识发现的过程中进行人机交互； 研究在网络环境下的数据挖掘技术( w e b m i n i n g ) ，特别是在因特网上建立d m k d 服务器，并且与数据库服务器配合，实现w e b m i n i n g ； 加强对各种非结构化数据的刀：采( b a t f d m i n i n g f o r a u d i o v i d e o ) ，如对文本数 据、图形数据、视频图像数据、声音数据乃至综合多媒体数据的开采； 处理的数据将会涉及到更多的数据类型，这些数据类型或者比较复杂，或者是 结构比较独特。为了处理这些复杂的数据，就需要一些新的和更好的分析和建 立模型的方法，同时还会涉及到为处理这些复杂或独特数据所做的费时和复杂 数据准备的一些工具和软件。 交互式发现： 知识的维护更新。 但是，不管怎样，需求牵引与市场推动是永恒的，d m k d 将首先满足信息时代用户 的急需，大量的基于d m k d 的决策支持软件产品将会问世。只有从数据中有效地提取 信息，从信息中及时地发现知识，j 能为人类的思维决策和战略发展服务。也只有到 那时，数据j 能够真m 成为与物质、能源相媲美的资源。 4 第二章关联规则数据挖掘 2 1 关联规则基本概念 关联规则是发现数据库中不同项目之| 日j 潜在的、有趣的联系。这些规则可用于预 测未柬的模式，以汲对模式进行评估等。如某些项目的出现对其他项目的影响。 a g r a w a l “1 等人于1 9 9 3 年首先提出了挖掘顾客交易数据库中项集问的关联规则问题， 以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。 到日前为止，关联规则的研究主要有以下几个方面：1 提高算法的运行效率，其 中著名的算法有a p r i o r i ，f p t r e e ，a p t i o r i t i d ，h a s ht r e e 等；2 生成的规则分析， 主要是如何删除冗余规则，如何发现规则中的相关性等方面。3 关联规则的扩展应用， 包括增量更新的关联规则，水平加权关联规则等。 本章在关联规则基本概念的基础上，对关联规则的种类进行了分类、归纳和总结， 对关联舰则的典型挖掘算法及其基本思想进行了详细地归纳、分析，对各算法之问的 差别进行了客观地比较，并通过实例说明了比较的结果。针对提高算法效率的各种优 化技术也在这里被进行了洋细地研究和讨论，同时客观地分析了它们的优缺点。对每 个算法以及每种优化技术都标识了参考文献。 2 2 关联规则基本问题 关联规则的基本问题描述如下：设i = i ，i ，j 。 是二进制文字的集合，其中 的几素称为项( i z e m ) 。定义交易( t r a n s a c t i o n ) t 为项的集合，并且t e l ，定义d 为 交易t 的集合。设x 是i 中若干项的集合，如果x c t ，那么称交易t 包含x 。在项目 集中所包含的项的个数成为项目集的长度。关联规则是形如x j y 的蕴涵式，这罩x 亡【， y c l ，并且x r 、y = o 。规则x j y 在交易数据库d 中的支持度( s u p p o r t ) 是交易集中包 含x 和v 的交易数与所有交易数之比，记为s u p p o r t ( x y ) ，即 s u p p o rl ( x j y ) = i r ：x u y _ _ t ，r e d l ! dj 。规则x j y 在交易集中的置信度 ( c o n f j d e n c e ) 是指包含x 和y 的交易数与包含x 的交易数之比，记为 c o n f 。i d e n c e ( x j y ) ，即c o n f i d e n c e ( x j y ) = t ：x u y g l 、，t e d ) l t ：x t ，t e d 。 给定一个交易集d ，挖掘关联规则就是找出支持度和置信度分别大于用户给定的 最小支持度( m in s u p ) 和最小置信度( m i n c o n f ) 的关联规则。因此挖掘关联规则可分解 为盘下两个子问题： ( 1 ) 找出交易数掘库d 中所有大于等于用户指定最小支持度的项闩集 ( it o m s e t ) 。具有最小支持度的项目集称为频集。 ( 2 ) 利用频集生成关联规则。对每一个频集m ，找到m 的所有非空子集m ，如果 s u p p o r t ( m ) s u p p o r t ( m ) = m in c o n f l ，就生成关联舰则m ： ( m - m ) ， s u p p o r t ( m ) s u p p o r t ( m ) 为规则m - ( m - m ) 的置信度。其中m 定义为规则的前件，m m 定义为规则的后件。 2 3 关联规则分类 关联规则的种类主要包括： ( 1 ) 基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。布尔型 关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的关系；而数值型 关联规则可以和多维关联或多层关联规则结合起来，对数值型字段进行处理，将其进 行离散化，或者直接对原始的数据进行处理，当然数值型关联规则中也可以包含种类 变量。 ( 2 ) 基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。在单 层的关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同的层次；而在 多层的关联规则中，对数据的多层性进行了充分的考虑。即，将变量基于概念划分成 多个层次。对多层次的关联规则挖掘又包含两个方面：1 层间关联规则，在同一个层 面上挖掘关联规则。2 混合关联规则，在不同的层面上挖掘关联规则。 ( 3 ) 基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。在单 维的关联规则中，我们只涉及到数据的一个维，如用户购买的物品；而在多维的关联 规则中，要处理的数据将会涉及多个维。即，单维关联规则是处理单个属性中的一些 关系：多维关联规则是处理各个属性之间的某些关系。目前，绝大多数都集中在单维 布尔关联规则的研究。 2 4 关联规则挖掘的算法 2 4 1 经典算法a p r i o r i a g r a w a l 等在1 9 9 3 年设计了一个基本算法a p r i o r i ，提出了挖掘关联规则的一个 重要方法。这是一个基于两阶段频集思想的方法，将关联规则挖掘算法的设计可以分 解为两个子问题： ( 1 ) 找到所有支持度大于最小支持度的项集( i t e m s e t ) ，这些项集称为频集 ( f r e q u e n tj t e m s e t ) 。 ( 2 ) 使用第l 步找到的频集产生期望的规则。 为了生成所有频集，使用了递推的方法。其核心思想如下： ( 1 ) l ，= l a r g el _ i t e m s e t s ： ( 2 )f o r ( k = 2 ：f 。：k + + ) d ob e g i n ( 3 )c 。= a p t i o r i g e n ( l ) ：新产生的候选集 ( 4 )f o ra l lt r a n s a c t i o n st 口d ob e g i n ( 5 )c 。= s u b s e t ( c 。，t ) ：事务l 中包含的候选集 6 ( 6 ) f o ra 1ic a n d i d a t e sc c 。d o ( 7 )c c o l i n t + + ： ( 8 ) e n d ( 9 )l k = c ec 。lc c o u n t _ m in s u p ( 1 0 )e n d ( 11 )a n s w e r - u k l 。： 首先产牛频繁卜项集l ，然后是频繁2 一项集l 。，氲到有某个r 值使得l ，为空， 这时算法停止。这里在第k 次循环中，首先产生候选k 一项集的集合c 。，c 。中的每一 个项集是对两个只有一个项不同的属于k 的频集做一个( k 一2 ) 一连接来产生的。c 。中 的项集是用来产生频集的候选集，最后的频集l k 必须是c 。的一个子集。c 。中的每个 元素需在交易数据库中进行验证来决定其是否加入l 。，这里的验证过程是算法性能的 一个瓶颈。这个方法要求多次扫描可能很大的交易数据库，即如果频集最多包含1 0 个项，那么就需要扫描交易数据库1 0 遍，这需要很大的i o 负载。 2 4 2f p t r e e 算法 针对a p r i o r i 算法的固有缺陷，j 1 l a n ”1 等提出了不产生候选挖掘频繁项集的方 法：f p 一树频集算法。采用分而治之的策略，在经过第一遍扫描之后，把数据库中的频 集压缩进一棵频繁模式树( f p t r e e ) ，同时依然保留其中的关联信息，随后再将 f p t r e e 分化成一些条件库，每个库和一个长度为1 的频集相关，然后再对这些条件 库分别进行挖掘。当原始数据量很大的时候，也可以结合划分的方法，使得一个 f pt r e e 可以放入主存中。f p g r o w t h 对不同长度的规则都有很好的适应性，同时在 效率上较之a p t i o r i 算法有巨大的提高。算法伪代码如下： 算法f p t r e e ，通过模式段增长，挖掘频繁模式。 输入：事务数据库d ：最小支持度阈值m i n s u p 。 输出：频繁模式的完全集。 伪代码： ( 1 ) 构造f p 树： a 扫描数据库d 一遍。收集频繁项的集合f 和它们的支持度。对f 按支持度降序 排列，结果为频繁项表l 。 b 创建f p 树的根结点，以“n u l l ”标记它。对于d 中每个事务t r a n s ，执行：选 择t r a n s 中的频繁项，并按l 中的次序排序。设排序后的频繁项目表为 p i p ，其中 p 足第一个元素，而p 是剩余元素的表。调用i n s e r t t r e e ( p i p ，t ) 。该过程执行情 况如下。如果t 有子女n 使得n i t e m n a m e = p i t e m f l a m e ，则n 的计数增加l ；否则 创建一个新的节点n ，将其计数设置为】，连接到它的父节点t ，并且通过节点链结 构将其链接到具有相同i t e m n a m e 的节点。如果p 非空，递归地调用 ir l g f 2 f i t r e e ( p ，n ) 。 ( 2 ) f pt r e e 的挖掘通过调用f p g r o w t h ( f pt f e e ，n u l l ) 实现。该过稗实现如r ： p r o c e d u r ef p g r o w t h ( t r e e ，m ) 1 ) i ft r e e 含单个路径pt h e n 2 ) f o r 路径p 中节点的每个组合( 记为n ) 3 ) 产生模式n u 1 1 ，其支持度s u p p o r t - n 中节点的最小支持度： 4 ) e l s ef o re a c ha 。在t r e e 的头部 5 ) 产牛。个模式n = a uj n ，其支持度s u p p o r t = a s u p p o r t ： 6 ) 构造n 的条件模式基，然后构造n 的条件f p - t r e e 即t r e e 7 ) i ft r e e 。0t h e n 8 ) 调用f p g r o w t h ( t r e e 。，n ) j 2 4 3 a p r i o r i t i d 算法和a p r i o r i h y b i r d a p r i o r i t i 1 算法是a p r i o r i 的改进算法，同样也采用a p r i o r i h e n 函数来产生 候选项目集c ，但是与a p r io r i 算法不同之处是，在每步( 除第一步) 计算候选项目 集c 。的支持数时，不需要浏览整个事务集合d ，而只需要浏览c 。，就可以得到频 繁项目集l k 的支持度了因此，h p y i o r i t i d 算法相对予a p r i o r i 大大减少了扫描数 据库的次数，提高了算法的效率 a p r i o r i t i d 算法在频集生成过程中，不需要对数据的所有扫描都使用同一个算 法，在初期扫描，a p r i o r i 算法比a d r i o r i t i d 算法好，但在后期扫描中a p r i o r i t i d 算法较好。原因是，a p r f o r i 算法和a p r i o r i7 r i d 算法使用同样的候选项目集生成过 程，因此对同样的项目集计数。在后期扫描中，虽然候选项目集减少了，但是a p r i o r i 算法仍然需要检测数据库中的每一个事务。另一方面，a p r i o r i t i d 算法扫描c 。来 获得支持度而不是扫描数据库，而c 。比数据库要小得多当c 。能放进内存时，将 大大节省i 0 的时间，提高了程序运行的效率a p r i o r h y b r id 2 1 算法的基本处理思 想是：在初期扫描时用a p r i o r i 算法，而当c 。能放进内存时就转向a p r i o r i t i d 算 法。 2 4 4 基于划分的方法。 s a v a s e r e “1 等设计了一个基于划分( p a r t jt i o i l ) 的算法，这个算法先把数据库从逻 辑上分成几个互小相交的块，每次单独考虑一个分块并对它生成所有的频集，然后把 产生的频集合并，用来生成所有r 叮能的频集，最后计算这些项集的支持度。这罩分块 的大小选择要使得每个分块可以被放入主存，每个阶段只需被扫描次。而算法的正 确性是出每一个可能的频集至少在某一个分块中是频集保证的。上面所讨论的算法是 可以高度并行的，可以把每一分块分别分配给某一个处理器生成频集。产生频集的每 一个循环结束后，处理器之间进行通信柬产生全局的候选k 项集。通常这里的通信 过程是算法执行时问的主要瓶颈：而另一方面，每个独立的处理器生成频集的时阳j 也 是一个瓶颈。其他的方法还有在多处理器之f 日j 共享一个杂凑树来产生频集。 2 4 5 基于h a s h 的方法。 一个高效地产牛频集的基于杂凑( h a s h ) 的算法由p a r k ”等提出来。通过实验我们 可以发现寻找频集主要的汁算是在生成频繁2 一项集l k 上，p a r k 等就是利用了这个性 质引入杂凑技术来改进产生频繁2 一项集的方法。 2 4 6 基于采样的方法。 基于前一遍扫描得到的信息，对此仔细地作组合分析，可以得到一个改进的算法， m a n n i l a 1 等先考虑了这一点，他们认为采样是发现规则的一个有效途径。随后又由 t o iv o t l e n ”1 进一步发展了这个思想，先使用从数据库中抽取出来的采样得到一些在整 个数据库中可能成立的规则，然后对数据库的剩余部分验证这个结果。t o i v o n e n 的 算法相当简单并显著地减少了i 0 代价，但是一个很大的缺点就是产生的结果不精 确，即存在所溜的数据扭| 】( d a t as k e w ) 。分布在同一页面上的数据时常是高度相关 的，可能不能表示整个数据库中模式的分布，由此而导致的是采样5 的交易数据所