（计算机应用技术专业论文）数据挖掘中关联规则的研究与应用.pdf

摘要 当今，社会已经进入了网络信息时代，计算机与网络信息技术的飞速发展使得各个 领域的数据和信息急剧增加，同时人类的参与使数据与信息系统中的不确定性更加显 著。如何有效地实现对数据的分析和处理，如何快速地从数据中提取出隐含的知识，一 直是人工智能领域的研究热点。在此背景下诞生的知识发现k d d ( k n o w l e d g ed i s c o v e r y i nd a t a b a s e s ) 和数据挖掘d m ( d a t am i n i n g ) 给人们提供了一种新的认识数据和理解数据 的智能手段。 在数据挖掘技术发展繁荣的大背景下，关联规则技术得到了蓬勃发展，并正向着更 为广泛而深入的方向继续发展。关联规则挖掘的目的是为了从数据中发现项之间有趣的 关联和相关关系，其应用背景从丌始的狭义购物篮分析扩展到网站设计与优化、网络入 侵检测、关联规则分类、交通事故模式分析、药物成份关联分析、蛋白质结构分析、软 件b u g 挖掘、设备故障诊断等等，其理论研究内容也从最初的频繁模式挖掘扩展到闭合 模式挖掘、最大模式挖掘、扩展型关联规则、衍生型关联规则、隐私保护、增量挖掘、 挖掘后处理、主观兴趣度度量、相关模式、数据流等多种类型数据上的关联规则挖掘等 等。因此，有必要对关联规则相关技术进行比较深入的研究和探讨。 本文主要的研究内容如下： 1 基于粗糙集和概念格，本文给出了一种挖掘关联规则的新算法。该算法首先通 过粗糙集的思想对形式背景进行了约简，然后通过预先给定的闽值，减少属性的个数， 从而减少了建格的复杂度和搜索概念的时间。利用概念格本身的信息，计算出了所得到 的关联舰则的支持度和信任度。 2 对于许多复杂系统产生的时间序列，研究序列的局部关联特征往往比原来的研 究系统全局特征性模型具有明显的优势。为研究时间序列内部或时间序列局部形态的关 联特征，文章借助f c m 来软化时间序列属性论域的划分边界，而后用改进布尔型关联规 则的并行挖掘算法来发现频繁模糊属性集，最后由多个处理器并行地产生满足最小模糊 信任度的模糊关联规则。 文章的最后对关联规则的应用前景和发展方向进行了展望。 关键字：数据挖掘关联规则概念格粗糙集时间序列f o i l a b s t r a c t n o w a d a y s ，t h es o c ie t yh a se n t e r e dt h ein f o r m a tio ne r a t h ec o m p u t e ra n dn e t w o r k i n f o r m a t i o nt e c h n o l o g yh a v eb e e nd e v e l o p e ds or a p i d l yt h a td a t aa n di n f o r m a t i o n a r ei n c r e a s i n gd r a m a t i c a l l y ( i n f o r m a t i o ne x p l o s i o n ) i na l lf i e l d s ，m e a n w h i l e d a t aa n di n f o r m a t i o ns y s t e m sb e c o m em o r eu n c e r t a i nd u et oh u m a n sp a r t i c i p a t i o n h o wt oe f f e c t i v e l ya c h i e v et h ed a t aa n a l y s i sa n dp r o c e s s i n ga n dq u i c k l yg e t i m p l i c i tk n o w l e d g e h a s l o n g b e e na ni m p o r t a n td i r e c t i o no f a r t i f i c i a l i n t e lli g e n c e i nt h isb a c k g r o u n d ，k n o w l e d g ed is c o v e r yi nd a t a b a s e s ( k d d ) a n dd a t a m i n i n g ( d m ) p r o v i d ean e wi n t e l l i g e n tw a yo fu n d e r s t a n d i n gd a t a i nt h ep r o s p e r o u sb a c k g r o u n do fd a t am i n i n gt e c h n o l o g y ，a s s o c i a t i o n r u l e s ( a r s ) t e c h n o l o g yo b t a i n st h ev i g o r o u sd e v e l o p m e n t m i n i n ga s s o c i a t i o n r u l e sa i m sa tf i n d i n gi n t e r e s t i n gc o r r e l a t i o n sa n da s s o c i a t i o n sf r o mb i gv o l u m e s o fd a t a it sa p p lic a tio ns c o p ee x p a n d sf r o mt h e n a r r o w s e n s em a r k e t b a s k e t a n a l y s i st ot h ed e s i g na n do p t i m i z a t i o n o fw e b s i t e ，t h en e t w o r ki n t r u s i o n d e t e c t i o n ，t h et r a f f i ca c c i d e n tp a t t e r na n a l y s i s ，t h ea n a l y s i so fm e d i c i n e i n g r e d i e n t ，t h ep r o t e i ns t r u c t u r ea n a l y s i s ， s o f t w a r eb u gm i n i n g ，a n df a u l t d i a g n o s i sf o rm a c h i n ea n ds oo n i t sf u n d a m e n t a lr e s e a r c hc o n t e n t sa l s oe x p e n d f r o mt h eo r i g i n a lf r e q u e n tp a t t e r nm i n i n gt ot h ec l o s ep a t t e r nm i n i n g ，m a x i m a l d a t t e r nm i n i n g ，e x t e n s i o na s s o c i a t i o nr u l em i n i n g ，p r i v a c yp r o t e c t i o ni na r s ， i n c r e m e n t a lm i n i n gf o ra r s ，p o s t m i n i n gp r o c e s s ，s u b j e c t i v ei n t e r e s t i n g m e a s u r e s ，c o r r e l a t e dp a t t e r n s ，a n da r sm i n i n gf r o md a t as t r e a m se t a 1 t h e r e f o r e ，i ti sn e c e s s a r yt oh a v ea ni n d e p t hs t u d yf o rr e l a t e dt e c h n o l o g i e s o fa s s o c i a t i o nr u l e s t h ek e yw o r k si nt h i st h e s i sa r ea sf o l l o w s ： 1 b a s e do nr o u g hs e tt h e o r ya n dc o n c e p tl a t t i c e ，an e wm e t h o di sp r o p o s e d t os e a r c hf o ra s s o c i a t i o nr u l e s t h ef o r m a lc o n t e x ti sf i r s tr e d u c e dv i ar o u g h s e tt h e o r y a n dt h e ns o m eo ft h ea t t r i b u t e sa r et h r o w no f ff o rt h eg i v e nt h r e s h o l d t h ec o m p l e x i t yo fc o n s t r u c t i n gl a t t i c ea n ds e a r c h i n gf o rt h ed e s i r ec o n c e p ti s d e c e a s e d t h es u p p o r t sa n dc o n f id e n c e sf o rt h eo b t a i n e da s s o c i a t i o nr u l e sa r e c o m p u t e dw i t ht h ea i do fc o n c e p tl a t t i c e 2 o nt h eo c c a s i o no fd e a l i n gw i t ht i m es e r i e sh a l l e df r o mc o m p l e xs y s t e m ， t h ei n v e s t i g a t i o no fs e r i e s l o c a lp a t t e r n sa n dl o c a lr e l a t i o n s h i p h a s d i s t i n c ts u p e r i o r i t yo v e rt r a d i t i o n a lg l o b a lm o d e l s i no r d e rt of i n dr u l e s r e 上a t l n gp a t t e r n si nat i m es e r i e st oo t h e rp a t t e r n si nt h a ts e r i e s ，o r p a t t e r n s 1 no n es e r l e st op a t t e r n si na n o t h e r s e r i e s ， af u z z ys u b s e r i e sd i s c r e t i z a t i o n m e t h o d ,w h i c hs o f t e nt h ee f f e c to fs h a r pb o u n d a r i e so fd e l e g a t eo fe a c hl o c a l s u b - s e r i e s ,i sp r o p o s e d t h e nt h e p a r a l l e la l g o r i t h mf o rm i n i n g b o o l e a n a s s o c i a t i o nr u l e si s i m p r o v e dt od i s c o v e rf r e q u e n tf u z z ya t t r i b u t e s f i n a l l y 。 t h e 上u z z ya s s o c i a t i o nr u l e sw i t hl e a s tf u z z yc o n f i d e n c ea r eg e n e r a t e db y a l l p r o c e s s o r s a t l a s t , t h ea p p l i c a t i o np r o s p e c to f a s s o c i a t i o nr u l em i n i n g a n df u r t h e r k e yw 。r d s ：d a t am i n i n g ：a s s o c i a t i 。n r u l e ：c o n c e p tl a t t i c e ：r o u g hs e t ： t i m e s e tj e s ：f c m 数据挖掘中关联规则的研究与应用 学位论文独创性声明 本人承诺：所呈交的学位论文是本人在导师指导下所取得的研究成果。论文中除特别加 以标注和致谢的地方外，不包含他人和其他机构已经撰写或发表过的研究成果，其他同：盘的 研究成果对本人的启示和所提供的帮助，均己在论文中做了明确的声明并表示谢意。 黼做懈戳：三乏邑p 日 飙节 学位论文版权的使用授权书 遗 罟 本学位论文作者完全了解辽。j 。师范人学有关保留、使用学位论文的规定，及学校有权保 留并向国家有关部门或机构送交复印什或磁盘，允许论文被夯阅和借阅。本文授权辽。j 。师范 人学，可以将学位论文的全部或部分内容编入有关数据库并进行检索，可以采用影印、缩印 或扫描等复制手段保存、汇编学位论文。保密的学位论文在解密后使用本授权一1 5 。 学位论文作者签名：三熙 指导教师签名 日期 4 7 数据挖掘中关联规则的研究与应用 1 绪论 1 1 问题的产生 计算机及信息技术发展的历史，也就是数据和信息加工手段不断更新和改善 的历史。随着计算机硬件和软件的飞速发展，尤其是数据库技术与应用的广泛推 广，摆在人们面前的问题出现了，这些飞快涨满的信息数据，如何有效利用这一 丰富数据海洋的宝藏为人类服务，也已成为广大信息技术工作者所重点关注的焦 点之一。与r 趋成熟的数据管理技术和软件工具相比，人们所依赖的数据分析工 具功能，却无法有效地为决策者提供其决策支持所需要的相关知识，从而形成了 一种独特的现象：“丰富的数据，贫乏的知识 。在这些大量数据的背后隐藏了很 多具有决策意义的信息，那么怎么得到这些“知识”呢? 也就是怎样通过一棵棵 的树木了解到整个森林的情况? 计算机科学对这个问题给出的最新回答就是：数 据挖掘，在“数据矿山”中找到蕴藏的“知识金块”f l 圳。 自二十世纪9 0 年代开始，数据挖掘技术逐步发展起来，随着全世界的各行 各业对将基础数据资源转化为信息和知识资源的巨大需求，数据挖掘技术得到迅 速发展，并广泛的应用于商业管理、生产控制、市场分析、工程设计和科学探索 等领域。 数据挖掘可以视为是数据管理与分析技术的自然进化产物【5 剖。当数据量极 度增长时，如果没有有效的方法，由计算机及信息技术来帮助从中提取有用的信 息和知识，人类显然就会感到像大海捞针一样束手无策。据估计，目前一个大型 企业数据库中数据，约只有百分之七得到很好应用。而今置身市场经济且面向全 球性剧烈竞争的环境下，任何商家的优势不单纯地取决于如产品、服务、地区等 方面因素，而在于创新。用知识作为创新的原动力，就能使商家长期持续地保持 竞争优势。因此要能及时迅速地从r 积月累庞大的数据库中，以及互联网上获取 与经营决策相关的知识，自然而然就成为满足易变的客户需求以及因市场快速变 化而引起激烈竞争局面的唯一武器。因此，如何对数据与信息快速有效地进行分 析加工提炼以获取所需知识，就成为计算机及信息技术领域的重要研究课题。 数据挖掘作为一个交叉学科领域，受多个学科影响，包括数据库系统、统计 学、机器学习、可视化和信息科学。如果从整体上看数据挖掘技术，可以分为数 据分析类、知识发现类和有针对性的数据挖掘技术。 1 数据分析类 数据分析( 或称统计分析) 技术中使用的数据挖掘模型有线性分析和非线性 数据挖掘中关联规则的研究与应用 分析、回归分析、逻辑回归分析、单变量分析、多变量分析、时间序列分析、最 近邻算法和聚类分析等技术。 2 知识发现类 知识发现类数据挖掘技术是与统计类数据挖掘技术完全不同的一种挖掘技 术。它可以从数据仓库的大量数据中筛选信息，寻找市场可能出现的运营模式， 发掘人们所不知道的事实。主要包含人工神经网络、决策树、遗传算法、粗糙集、 规则发现和关联顺序等。 3 有针对性地数据挖掘技术 除了上面的两类数据挖掘技术外，还有其他的有针对性地数据挖掘技术，如 文本数据挖掘、w e b 数据挖掘、分类系统、可视化系统、空间数据挖掘和分布式 数据挖掘等。 目前国内外数据挖掘的研究主要是以聚类分析、预测建模、关联分析和异常 检测为任务，以基于各种理论的有效知识发现算法研究为中心，以及更加广泛的 应用研究为主要特点。具体体现在结构化数据和非结构化的复杂数据类型的挖掘 技术和应用的研究上，以及相应软件产品和应用系统的开发中。信息挖掘机理和 一般性框架的理论研究同益受到重视。 结构化数据挖掘技术的研究。结构化数据挖掘技术的研究较为成熟，目前的 工作主要集中在算法的适应性、扩展性和鲁棒性的研究上。围绕统计学方法的数 据挖掘算法的研究一直受到关注，s a s ，s p s s 等软件厂商均在其统计软件中增加 数据挖掘的功能。他们通过b a y e s 理论的拓展，用于在具有先验知识的情况下不 确定知识发现。实际上，统计理论的基本概念，如概率、独立性和因果性等也是 数据挖掘算法的基础。 关联规则挖掘就是从大量的数据中挖掘出有价值描述数据项之间相互联系 的有关知识【_ 瑚】。随着收集和存储在数据库中的数据规模越来越大，人们对从这 些数据中挖掘相应的关联知识越来越有兴趣。例如：从大量的商业交易记录中发 现有价值的关联知识就可帮助进行商品目录的设计、交叉营销或帮助进行其它有 关的商业决策。 关联规则挖掘最早是由a g r a w a l 等人提出的( 1 9 9 3 ) 。最初提出的动机是针 对购物篮分析问题，其目的是为了发现交易数据库中不同商品之间的联系规则。 这些规则刻画了顾客购买行为模式，可以用来指导商家科学地安排进货、库存以 及货架设计等。根据被放到一个购物袋的( 购物) 内容记录数据而发现的不同( 被 购买) 商品之间所存在的关联知识无疑将会帮助商家分析顾客的购买习惯。发现 常在一起被购买的商品( 关联知识) 将帮助商家制定有针对性的市场营销策略。 比如：顾客在购买牛奶时，是否也可能同时购买面包或会购买哪个牌子的面包， 2 数据挖掘中关联规则的研究与应用 显然能够回答这些问题的有关信息肯定会有效地帮助商家进行有针对性的促销， 以及进行合适的货架商品摆放，如可以将牛奶和面包放在相近的地方或许会促进 这两个商品的销售。 如何从交易记录数据库或关系数据库的大量数据中挖掘出关联规则知识，什 么样的关联规则才是最有意义的，如何才能帮助挖掘过程尽快发现有价值的关联 知识，这些都是关联规则挖掘所要研究的方面。 诸多的研究人员对关联规则的挖掘问题进行了大量的研究。他们的工作涉及 到关联规则的挖掘理论的探索、原有的算法的改进和新算法的设计、并行关联规 则挖掘( p a r a l l e la s s o c i a t i o nr u l e m i n in g ) 以及数量关联规则挖掘 ( q u a n t i t i v ea s s o c i a t i o nr u l em i n i n g ) 等问题。在提高挖掘舰则算法的效率、 适应性、可用性以及应用推广等方面，许多学者进行了不懈的努力【9 】。 1 2 课题的目的和意义 数据挖掘技术从一开始就是面向应用的。目前，在很多重要的领域，数据挖 掘都可以发挥积极促进的作用，尤其是在如银行、电信、保险、交通、零售( 如 超级市场) 等商业应用领域【l m 眩】。数据挖掘能够帮助解决许多典型的商业问题， 其中包括：数据库营销、客户群体划分、背景分析、交叉销售等市场分析行为， 以及客户流失性分析、客户信用评分、欺诈发现等等【1 3 】。 数据挖掘技术在企业市场营销中得到了比较普遍的应用，它是以市场营销学 的市场细分原理为基础，其基本假定是消费者过去的行为是其今后消费倾向的最 好说明。通过收集、加工和处理涉及消费者消费行为的大量信息，确定特定消费 群体或个体的兴趣、消费习惯、消费倾向和消费需求，进而推断出相应消费群体 或个体下一步的消费行为，然后以此为基础，对所识别出来的消费群体进行特定 内容的定向营销，这与传统的不区分消费者对象特征的大规模营销手段相比，大 大节省了营销成本，提高了营销效果，从而为企业带来更多的利润。 在数据库的知识发现中，关联规则是很有价值的一类规律，它指的是一个形 如彳j b 的表达式，其中a 和b 是特征集合，其直观含义是：数据库中具有特征 a 的行( 或记录、对象) 可能也具备特征b 。自从a g r a w a l 等首次提出从大型数据 库中挖掘关联规则以来，关联规则发现已经得到了广泛而深入的研究，并已经成 为k d d 的核心任务之一。 关联知识( a s s o c i a t i o n ) 反映一个事件和其它事件之间的依赖或关联。数 据库中的数据关联是现实世界中事物联系的表现。数据库作为一种结构化的数据 组织形式，利用其依附的数据模型可能刻画了数据间的关联( 如关系数据库的主 键和外键) 。但是，数据之间的关联是复杂的，不仅是上面所说的依附在数据模 3 数据挖掘中关联规则的研究与应用 型中的关联，大部分是蕴藏的。关联知识挖掘的目的就是找出数据库中隐藏的关 联信息。关联可分为简单关联、时序( t i m es e r i e s ) 关联、因果关联、数量关 联等。这些关联并不总是事先知道的，而是通过数据库中数据的关联分析获得的， 因而对商业决策具有新价值。 经过十几年的研究，数据挖掘已经在继承和发展相关基础学科( 如机器学习、 统计学等) 已有成果方面取得了可喜的进步，探索出了许多独具特色的理论体系 1 1 4 - 1 5 】。但是，这决不意味着挖掘理论的探索已经结束，恰恰相反，它留给了研究 者丰富的理论课题。一方面，在这些大的理论框架下有许多面向实际应用目标的 挖掘理论等待探索和创新。另一方面，随着数据挖掘技术本身和相关技术的发展， 新的挖掘理论的诞生是必然的，而且可能对特定的应用产生推动作用。新理论的 发展必然促进新的挖掘算法的产生，这些算法可能扩展挖掘的有效性，如针对数 据挖掘的某些阶段、某些数据类型、大容量源数据集等更有效；可能提高挖掘的 精度或效率；可能融合特定的应用目标，如c r m 、电子商务等。因此，对数据挖 掘理论和算法的探讨将是长期而艰巨的任务。 面对大型数据库，关联规则挖掘需要在挖掘效率、可用性、精确性等方面得 到提升。因此，需要探索新的挖掘理论和模型；需要利用用户的约束等聚焦挖掘 目标；需要对一些传统的算法进行改进；也需要研究新的更有效的算法等。鉴于 目前关联规则挖掘研究的现状和发展趋势，我选择了这一课题丌展相关工作。 1 3 研究现状 关联分析，即利用关联规则进行数据挖掘。在数据挖掘研究领域，对于关联 分析的研究开展得比较深入，人们提出了多种关联规则的挖掘算法，如a p r i o r i 、 s t e m 、a i s 、d h p 等算法【1 6 17 1 。 一般地，关联规则挖掘问题可以划分成两个子问题： ( 1 ) 发现频繁项目集 通过用户给定的m i n s u p p o r t ，寻找所有频繁项目集( f r e q u e n ti t e ms e t ) ， 即满足s u p p o r t 不小于m i n s u p p o r t 的项目集。事实上，这些频繁项目集可能具 有包含关系。一般地，我们只关心那些不被其它频繁项目集所包含的所谓频繁大 项集( f r e q u e n tl a r g ei t e ms e t ) 的集合。这些频繁大项集是形成关联规则的 基础。 ( 2 ) 生成关联规则 通过用户给定的m i n c o n f i d e n c e ，在每个最大频繁项目集中，寻找 c o n f i d e n c e 不小于m i n c o n f i d e n c e 的关联规则。 4 数据挖掘中关联规则的研究与应用 子问题( 1 ) 是近年来关联规则挖掘算法研究的重点。比较流行的方法是基 于a g r a w a l 等人建立的项目集格空问理论。这个理论的核心是这样的原理：频繁 项目集的子集是频繁项目集；非频繁项目集的超集是非频繁项目集。对于子问题 ( 2 ) 而言，也许在每个频繁大项集中逐一匹配规则并进行c o n f i d e n c e ( 厶，：) m i n c o n f i d e n c e 的测试是必需的，因此这部分工作相对比较成熟。 a g r a w a l 等于1 9 9 3 年首先提出了挖掘顾客交易数据库中项集间的关联规则 问题，其核心方法是基于频集理论的递推方法，以后诸多的研究人员对关联规则 的挖掘问题进行了大量的研究。他们的工作包括对原有的算法进行优化，如引入 随机采样、并行的思想等，以提高算法挖掘规则的效率；提出各种变体，如泛化 的关联规则、周期关联规则等，对关联规则的应用进行推广。 关联规则的挖掘算法主要可以分为以下几个方面： ( 1 ) 利用频繁项集向下封闭的性质( a p r i o r i 性质) 的a p r i o r i 系列算法，主 要有：经典关联规则挖掘算法a p r i o r i 算法【l 引：对事务项集进行重组预选的 a p r i o r i t i d 算法：用h a s h 表进行事务项集重组的d h p 算法等。 ( 2 ) 利用对事务数据库分划来提高效率算法，包括基于采样的算法；分割方 法( p a r t i t i o n ) ：a g r a w l 等人提出的并行算法c d ( c o u n td i s t r i b u t i o n ) 、 c a d ( c a n d i d a t ed i s t r i b u t i o n ) 、d d ( d a t ad i s t r i b u t i o n ) ：c h e n g 等人提出的d m a 算法等。 ( 3 ) 利用各种数据结构进行的数据挖掘的算法，例如a n d e r s o n 和莫m o o r e 采用一种a d t r e e 的数据结构；a m i r ，f e l d m a n 和k a s h i 采用t r i e 树；p a s q u i r e r 和b a s t i d e 等使用项目格；胡可云等采用概念格来挖掘关联规则。 ( 4 ) 适应挖掘内涵、外延扩展的算法，如h a n 等人提出的基于概念分层的关 联规则算法( 即通常所说的广义关联规则挖掘) ；b a y a r d o 等提出的受限关联规则 挖掘算法。 ( 5 ) 挖掘全部频繁项集而不产生候选项集的算法。当前主要是 f r e q u e n t p a t t e r ng r o w t h ( 频繁模式增长) 算法，它通过f p 树来存储所有的频繁 模式信息，通过分析f p 树路径的条件模式基来得到所有的频繁项集。 ( 6 ) 遗传算法是一种崭新的数据挖掘算法，但它是针对具体的问题的，每一 个具体的问题都必须设计合理的编码、适应度函数等。 不论关联规则算法有多少，都可以归纳为两类，一类是产生频繁集候选项的 算法，另一种是不产生频繁集候选项的算法。对于前者，大多数利用a p r i o r i 性质对候选项集的数目进行压缩，虽然效果非常明显，但在频繁模式较长时，候 选频繁项集的数目仍然是十分惊人的；同时该类算法还有两种开销，一种是 a p r i o r i g e n 过程中要进行大量的自连接，还有就是要重复扫描数据库，i o 开 5 数据挖掘中关联规则的研究与应用 销非常巨大；对于不产生候选项的算法，当前比较成熟的是f p 增长算法，虽然 较a p r i o r i 类算法有较大性能的提高，但它仍然存在着一定的缺点；大量f p 树 结点链将增加数据结构的复杂度和资源的占用；树枝伸展的无序将降低模式检索 和挖掘的效率；通过条件模式基的分析产生频繁模式仍然需要大量的连接操作。 遗传算法是一种新不产生候选项的关联规则挖掘算法，但由于遗传算法目前许多 有意义的结论几乎全是试验结论，缺乏理论上的严格推导，目前用的不是很普遍。 关联规则挖掘的经典算法是a p r i o r i 算法( a g r a w a la n ds r i k a n t ，1 9 9 4 ) 。 a p r i o r i 算法通过多次迭代来找出所有的频繁项目集，在第k 次迭代过程中找出 所有的频繁k 项目集l k 。该算法使用如下启发式规则：一个项目集是频繁项目 集，则此项目集的所有子集构成的项目集也一定是频繁项目集；一个项目集是非 频繁项目集，则此项目集的所有超集( 即包含此项目集的项目集) 一定是非频繁 项目集。因此，第k 次迭代时的候选项目集可由第( k - 1 ) 次迭代时找出的所有频 繁( k 一1 ) 项目集之间通过连接运算得到。 此后，涌现出大量的a p r i o r i 的改进算法【1 9 抛】，如利用h a s h 表的d h p 算法 ( p a r k ，c h e na n dy u ，1 9 9 6 ) ，基于采样的算法( t o i v o n e n ，1 9 9 6 ) ，并行关联规则算法 ( a g r a w a la n ds h a f e r ，1 9 9 6 ) ，分布式关联规则算法，多层关联规则算法( h a na n d f u ，1 9 9 5 ) ，数值扩展的关联规则算法( s r i k a n ta n d a g r a w a l ，1 9 9 6 ) ，利用关联规则 进行分类( l i u ，h s ua n dm a ，1 9 9 8 ) ，具有限制条件的关联规则( b a y a r d o ，a g r a w a l a n dg u n o p u l o s ，1 9 9 9 ) 等等。由于典型的关联规则的算法会产生大量无意义的规 则，因此出现了基于兴趣度的规则后处理算法( k l e m e t t i n e na n dm a n n i l ae t a l ，1 9 9 4 ) 。 大多数此类算法利用a p r i o r i 性质对候选项集的数目进行压缩，虽然效果非 常明显，但在频繁模式较长时，候选频繁项集的数目仍然是十分惊人的；同时该 类算法还有两种丌销，一种是a p r i o r i - g e n 过程中要进行大量的自连接，还有就 是要重复扫描数据库，i o 开销非常巨大。 另外一些研究采用不同的数据结构进行关联规则的挖掘。例如( a n d e r s o n a n dm o o r e ，1 9 9 8 ) 采用一种a d t r e e 的数据结构，( a m i r ，f e l d m a na n dk a s h i ，1 9 9 7 ) 采用t r i e 树，( p a s q u i e ra n db a s t i d ee ta l ，1 9 9 9 ) 使用项目格。( z a k i ，2 0 0 0 ) 也采用一种类似格的形式。( h u ，l ua n ds h i ，1 9 9 9 ：h u ，l u ，z h o ua n ds h i ，1 9 9 9 ) 则采用概念格来挖掘关联规则。 在采用概念格【2 3 】进行关联规则挖掘方面，已有不少作者讨论了从形式背景 建造概念格、从概念格上提取规则或函数依赖的问题。由于建格算法在概念格中 具有重要的地位，产生了许多概念格的生成算法，这些算法可分为两类：批处理 算法和增量算法。批处理算法根据其构造格的不同方式，可分为三类，即从顶向下 6 数据挖掘中关联规则的研究与应用 算法，自底而上算法，枚举算法。 从顶向下算法，首先构造格的最上层节点，再逐渐往下，例如b o r d a t 的算 法，o s h a m 算法( h o ，1 9 9 5 ) 。自底而上算法则相反，首先构造底部的节点，再向上扩 展，如c h e i n 的算法( g o d i n1 9 9 5 ) 。枚举算法则是按照一定顺序枚举格的所有节 点，然后再生成h a s s e 图，即各节点之间的关系，此类算法如g a n t e r 的算法( g o d i n 1 9 9 5 ) ，n o u r i n e 的算法( n o u r i n ea n dr a y n a u d ，1 9 9 9 ) 等。增量算法的思想都是大 同小异的。基本思想都是将当前要插入的对象和格中所有的概念交，根据交的结 果采取不同的行动，典型的算法有( g o d i n ，1 9 9 5 ) 和( c a r p i n e t oa n dr o m a n o ，1 9 9 3 ) 的算法。 1 4 本文的工作 本文在介绍数据挖掘领域的现状、任务，以及关联规则的挖掘情况后，详细 介绍的内容主要包括数据挖掘领域的现状、任务，概念格和粗糙集，以及时间序 列和f c m 聚类的相关理论以及关联规则的挖掘情况。 本文组织结构如下： 第一章绪论，简单介绍了数据挖掘任务和进展、关联规则研究现状和本文的 组织结构。 第二章介绍了概念格及粗糙集基本理论。 第三章介绍了时间序列及f c m 聚类算法。 第四章定义了属性和概念的支持度，然后给出了一种挖掘关联规则的新方 法。为了得到有效的关联规则，对于给定的阈值，该方法首先对形式背景进行约 化和对属性进行了过滤，减少了属性的个数，从而减少了建格的复杂度和搜索 概念的时间。同时，利用概念格的信息，还计算出了关联规则的支持度和信任 度。 第五章提出了时间序列的模糊关联规则的并行挖掘算法。算法首先采用f c m 算法对清洗后的时间数据进行模糊离散化处理，将每一个局部序列软化到代表形 态中。而后用改进布尔型属性关联规则的并行算法来发现频繁模糊属性集。 7 数据挖掘中关联规则的研究与应用 概念格及粗糙集基本理论 2 1 概念格基本理论 下面我们介绍一下关于概念格理论的基本知识，更为详细内容请参见文献 2 1 1 形式概念分析 一个信息表由非空的有限对象集、非空的有限属性集和对象在属性上的取值 构成的。一个二元信息表指的是这些取值是o 或者是1 ，例如表2 1 。一个非二元 的信息表可以转换成二元的信息表。 表2 1 形势背景 abcde f g 定义2 1 ：一个形式背景是一个三元组( g ，m ，i ) ，其中g 是对象的集合：m 是属 性的集合：，g x m 是g 和 l 上的二元关系。对于v g g ，v m m ，若g 具有属 性m ，记为gim 或者( g ，m ) i 。 假设( g ，m ，i ) 是一个形式背景，对于a c g ，b c m ，定义 a7 = m em iv g eg ：( g ，m ) i ) b7 = g g ivm em ：( g ，m ) i ) 定义2 2 ：形式背景( g ，m ，i ) 的一个形式概念( 简称概念) 是一个二元组( a ， b ) ，它满足a = b 且b = a ，其中ac g ，b m 。a 是概念( a ，b ) 的外延，b 是 概念( a ，b ) 的内涵。 图2 1 中概念# 1 - # 1 2 分别是： # 1 ：( 1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 ) ， ) ) ：# 2 ：( 1 ，5 ， d ) ； 8 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 l 1 0 0 0 1 0 o 0 0 0 1 1 0 0 1 0 0 1 1 1 o 0 1 0 0 1 l 0 o l 1 0 1 1 1 0 0 1 l 1 1 2 3 4 5 6 7 8 数据挖掘中关联规则的研究与应用 # 3 ：( l ，2 ，3 ，6 ，7 ，8 ) ， a ) ： # 5 ：( 8 ) ， a ，f ) ) ： t t 7 ：( 2 ，3 ，6 ，7 ， a ，b ) ) ： # 9 ：( 3 ，4 ，7 ) ， c ，d ) ： # 11 ：( 3 ，7 ， a ，b ，c ，d ) ： # 4 ：( 2 ，3 ，4 ，7 ) ， c ) ： # 6 ：( l ， a ，e ) ： # 8 ：( 5 ， e ，g ) ： # 1 0 ：( 2 ，3 ，7 ) ， a ，b ，c ) ) ： # 1 2 ：( ， a ，b ，c ，d ，e ，f ，g ) ) 图2 1 表2 1 所对应的概念格 形式背景( g ，m ，i ) 中的概念可以用超概念和子概念的关系定义他们之间 的序关系：( a l ，b 1 ) ( a 2 ，b 2 ) a 1c _ a 2 ( 营b 2 b 1 ) ，( a 1 ，b 1 ) 是( a 2 ， b 2 ) 的子概念，( a 2 ，b 2 ) 是( a 1 ，b 1 ) 的超概念：( g ，m ，i ) 的所有概念的偏 序集记为l ( g ，m ，i ) ，称之为6 a l o i s 概念格，简称概念格。根据偏序关系可生 成概念格的h a s s e 图，h a s s e 图生动形象地再现了概念之间的关系( 如图2 1 ) 。 定义2 3 ：若一个四元组满足下列条件：他a 杉若( 0 ，口，1 ，) i ，则 ( 0 ，口，w ) ij ，= w ，其中0 ，a ，v 为集合，分别对应于对象，多值属性和 属性值，f 是0 ，a ，v 之间的三元关系，0xaxv ，则称该四元组为一 个多值形式背景，如表2 2 。 表2 2 多值形式背景 9 数据挖掘中关联规则的研究与应用 l 234 a la 2a 3a 4a 5a 6a 7a 8 a 9 axxxx bxxxx cxx xx dxxxx 在定义2 3 中， ( o ，a ，) i 表示对象o 相对于属性口的属性值为v ，定义 中的条件则保证了对于每个对象o ，属性口至多对应一个属性值y 。多值形式背 景的一个属性口可以认为是o 到a 的一个部分映射，记作a 俐= i ，用来代替 ( d ，a ，v ) i 。 表2 2 所对应的h a s s e 图如下： ( ( a jb ，c ，d 】，( ) ) ( ( c ， ( ( c ) a 9 ) ) a g ) 图2 2 表2 2 所对应的h a s s e 图 对多值形式背景的处理，通常采用的方法是将其转换为单值形式背景后，再 数据挖掘中关联规则的研究与应用 进行应用。一般采用的方法是对多值属性进划分处理，即：每一个属性a 么， 选择a 的一个划分品，令s 。：= ( d 。，彳。，厶) ，且a ( d ) d n ，则称品是属性 a 的一个划分，d 口是属性值v 的划分集合，a 口是属性a 的划分集合。 定义2 4 ：对于一个三元组他 ，刀，满足 ： n ：= y a ) x 彳n 且 a 一 ( d ，( 口，z ) ) j ：( d ，a ，) i ，( ，刀) 厶，则称他 ，为导出背景【2 4 1 。 2 1 2 概念格的构造 文献 2 5 于1 9 8 2 年提出形式概念分析以来，概念格作为形式概念分析理论 中的一种核心数据结构，已经在知识发现领域、软件工程领域【2 6 】【2 7 1 、知识工程领 域、经济分析及w e b 挖掘【2 8 】等众多领域取得了广泛应用。然而在应用概念格时， 概念格的构造效率始终是一大难题。它的构造过程实际上是概念聚类的过程，是 应用形式概念分析的前提。通常，概念格的大小是在指数量级上的，而且要处理 的数据又多数是海量的，因此概念格构造算法的研究是形式概念分析中的一个主 要问题。 目前，构造算法主要可分为两大类：渐进式算法，批处理算法。 2 1 2 1 渐进式算法 渐进式算法的基本思想是将当前要插入的对象与格中所有的概念求交，根据 交的结果进行不同的操作。典型的算法有：g o d i n 算法【2 们、c a p i n e t o 算法【3 0 】、 a d d i n t e n t 算法【3 l 】。h o 掣3 2 1 也提出了一个渐进算法，但和g o d i n 算法的思想基本 相同。下面简单介绍几个这类算法。 g o d i n 算法在插入一个新实例时，格中的节点被分为三类：一类是不变节点， 这些节点的内涵和要插入实例的特征集没有交集，它们将新格保持不变；第二类 是更新节点，这些节点的内涵包含于要插入实例的特征集，因此只需将其外延更 新，包括要插入实例即可；第三类是新增节点，当所有要插入的实例的特征集与 原来格中某个节点的内涵交集在格中没有出现过时，需要增加新的节点，该新节 点的内涵即为该交集。可以证明，新增节点的父节点必然是某个新增节点或者更 新节点，这使得连接过程很容易实现。g o d i n 还给出了一个改进算法，当一个新 实例插入时，不必对格中所有节点进行检查，只需检查那些和新实例有共同属性 的节点。可以用通过维护记录每个属性首次在格中出现的指针来实现。 c a p i n e t o 算法与g o d i n 算法的基本思想类似，它将生成新概念的条件分为： “交为空”、“交已经存在 和“交包含在已有概念中 。主要的不同处出现在连 接过程中。c a p i n e t o 算法是找到该新节点的最小上界和最大下界，删除它们之间 的边，并将其连接到新概念。 1 1 数据挖掘中关联规则的研究与应用 a d d i n t e n t 算法不但生成概念集，也生成概念的格结构。算法渐进地将下一 个对象合并到前面对象已生成的图结构中。