（计算机应用技术专业论文）负关联规则增量更新技术的研究.pdf

山东轻工业学院硕士学位论文 摘要 近几年来，随着计算机技术和互联网技术的普及以及数据库技术的发展，各 个应用领域的数据库中都积累了大量的数据，通过数据挖掘技术分析和理解这些 数据，揭示其中隐藏的有用信息，已成为当前最为活跃的研究领域之一。其中关 联规则挖掘是数据挖掘的一个重要模式，具有重要的理论价值和广泛的应用前景。 关联规则就数据项之间的相关性来说，可以有正负关联规则之分。当前，正 关联规则的挖掘受到了广泛的关注，而对于包含负属性或负项目的关联规则并未 给予足够的重视。然而在很多应用领域中，事物的否定因素也是非常重要的信息 来源，因此有必要研究事物负属性之间的关联关系。 另一方面，随着时间的流逝，数据库中的数据也将会发生变化，这就是我们 所说的增量更新问题。一般意义上的增量更新问题可以理解为：在数据库中增加 或者减少数据后，在新的数据库中更新关联规则的问题。 目前对于关联规则增量更新问题的研究主要是针对正关联规则的，例如 a g r a w a lr 和s r i k a n tr 提出的r 腰更新算法；b r i ns ，m o t w a n ir 和s i l v e r s t e i nc 提出的f u p 2 算法；国内的冯玉才、冯剑琳提出的i u a 和p i u a 算法等。对于负 关联规则增量更新的研究相对较少。而广义上的增量更新可分为：数据库的变化 和最小支持度、最小置信度的变化问题。 负关联规则的增量更新与正关联规则的增量更新有所不同，具体表现在： 正关联规则仅存在于频繁项集中，而负关联规则不仅存在于频繁项集中， 更多的是存在于非频繁项集中： 正关联规则仅有a - - b 这一种形式，而负关联规则则有：1 彳= 曰，彳= b ，7 彳= b 三种形式； 在解决正关联规则增量更新问题时，只需求出更新后数据库中所有频繁项 集，再利用公式求出正关联规则即可；而在解决负关联规则增量更新问题时，要 求解出所有的频繁与非频繁项集，还要再利用算法挖掘正负关联规则。 本文论述的内容主要分为以下几部分：数据挖掘技术，正负关联规则，经典 关联规则挖掘算法的研究，正负关联规则的更新算法研究。 本文的研究工作对进一步进行关联规则的研究以及关联规则的维护和更新等 提供了一定的方法和理论依据。 关键词：数据挖掘；正、负关联规则；最小支持度：最小置信度；频繁、非频繁 项集 山东轻工业学院硕士学位论文 a b s t r a c t r e c e n ty e a r s ，w i t ht h ep o p u l a r i t yo fc o m p u t e r , t h ei n t e r a c ta n dt h ed e v e l o p m e n t o fd a t a b a s e ，t h ed a t a b a s e si nv a r i o u sa p p l i c a t i o nf i e l d sh a v ea c c u m u l a t e dl o t so fd a t e t h r o u g hd a t am i n i n ga n a l y s i sa n du n d e r s t a n d i n go ft h e s ed a t a , w h i c hr e v e a l st h e h i d d e nu s e f u li n f o r m a t i o n , a n db e c o m et h em o s ta c t i v ea r e a so fr e s e a r c h m i n i n g a s s o c i a t i o nr u l e so fd a t am i n i n gi sa ni m p o r t a n tm o d e l ，a n dh a s i m p o r t a n tt h e o r e t i c a l v a l u ea n dp r o s p e c t sf o raw i d cr a n g eo fa p p l i c a t i o m a s s o c i a t i o nr u l e so nt h ed a t ac a nh a v ep o s i t i v ea n dn e g a t i v ea s s o c i a t i o nr u l e so n t h ec o r r e l a t i o n r e c e t l y , m i n i n gp o s i t i v ea s s o c i a t i o nr u l e sh a saw i d e s p r e a dc o n c e m i t d i dn o tg i v es u f f i c i e n ta t t e n t i o nf o rc o n t a i nn e g a t i v eo rn e g a t i v ea t t r i b u t e so ft h e p r o j e c ta s s o c i a t i o nr u l e s h o w e v g r , i nm a n ya p p l i c a t i o na r e a s ，t h en e g a t i v et h i n g sa r o a l s ov e r yi m p o r t a n tf a c t o r so ft h es o u i c e so fi n f o r m a t i o n , t h e r e f o r e ，i ti sn e c e s s a r yt o s t u d yt h i n g sb e t w e e nt h en e g a t i v ea n da s s o c i a t e da t t r i b u t e sr e l a t i o n s o nt h eo t h e rh a n d , w i t ht h et i m ef l 如n ad a t ai nt h ed a t a b a s ew i l lc h a n g e t h i si s w h a tw ec a l li n c r e m e n t a lu p d a t i n gp r o b l e m s g e n e r a ls a i s co ft h ei n c r e m e n t a l u p d a t i n gp r o b l e mc a nb eu n d e r s t o o da s t oi n c r e a s eo rr e d u c ed a t ai nt h eo r i g i n a l d a t a b a s e ，a n dt h e nt ou p d a t et h er u l e so fa s s o c i a t i o ni nt h en o wd a t a b a s e a tp r e s e n t , t h er e s e a r c ho nt h ei n c r e m e n t a lu p d a t i n gf o ra s s o c i a t i o nr u l e si s m a i n l yf o rt h en e g a t i v ea s s o c i a t i o nr u l e s f o re x a m p l e ，a g r a w a lr a n ds r i k a n tr p r o p o s e dn j pa l g o r i t h m ；b r i ns ，m o t w a n i a n ds i l v e r s t e i ncp r o p o s e df u p 2 a l g o r i t h m ；f e n gy u c a ia n df e n gj i a n g l i np r o p o s e di u aa n dp i u aa l g o r i t h m si nt h e h o m e l a n d t h er e s e a r c ho nt h ei n c r e m e n t a lu p d a t i n gf o rn e g a t i v ea s s o c i a t i o nr u l e si s r e l a t i v e l ys m a l l a n dt h eg e n e r a l i z e di n c r e m e n t a lu p d a t i n gi sd i v i d e di n t o ：c h a n g e si n t h ed a t a b a s ea n dt h ec h a n g e so fm i n - s u p p o r ta n dt h em i n - c o n f i d e n c e t h e r ea r es o m ed i f f e r e n c e sb e t w e e nt h ei n c r e c m e n t a lu p d a t i n gf o rt h ep o s i t i v e a n dn e g a t i v ea s s o c i a t i o nr u l e s s p e c i f i cp e r f o r m a n c e sa r et h ef o l l o w i n g ： p o s i t i v ea s s o c i a t i o nr u l e so n l ye x i s ti nt h ef r e q u e n ti t e m s t e s ，b u tt h en e g a t i v e a s s o c i a t i o nr u l e sn o to n l ye x i s ti nt h ef i c q u e n ti t e m s e t s ，b u tm o r ee x i s ti nt h e i n f r e q u e n ti t e m s e t s ； p o s i t i v ea s s o c i a t i o nr o l e so n l yh a v eo n ef o r m ( a = 丑) ，b u tt h en e g a t i v e a s s o c i a t i o nr u l e sh a v et h r e ef o r m s ( 7 4 = 曰、么= 7 b 、7 彳= 7 曰) ； i nr e s o l v i n gt h ep o s i t i v ea s s o c i a t i o nr u l e s ，i ti sn e c 髑s a r yt ou p d a t et h e f r e q u e n ti t c m s e t si nt h en e wd a t a b a s e ，a n dt h ep o s i t i v ea s s o c i a t i o nr u l e sc a nb e c a l c u l a t e db yt h ef o r m u l a ；w h e nr e s o l v i n gt h ei s s u eo fi n c r e m e n t a lu p d a t e i n gf o rt h e n e g a t i v ea s s o c i a t i o nr u l e s ，i ti sn e c e s s a r yt of i n da l lo ft h ef r e q u e n ta n di n f r e q u e n t i t c m s e t s ，a n dm i n i n ga l g o r i t h m sw i l lh a v et ou s et om i n et h en e g a t i v ea s s o c i a t i o n r u l e s i t i sm a i n l yi n t r o d u c e di nt h et h e s i st h a td a t am i n i n gt h e o n o l o g y , a s s o c i a t i o n r u l e s ，t h er e s e a r c ho nt h ec l a s s i ca l g o r i t h m so fa s s o c i a t i o nr u l e sa n di n c r e m e n t a l u p d a t i n g t h er e s e a r c hw o r ko ft h i st h e s i so f f e r sc e r t a i nt h e o r e t i c a lf o u n d a t i o na n dm e t h o d s e f f e c t i v e l yf o rf u r t h e rr e s e a r c ht ot h ee x i s t i n ga s s o c i a t i o nr u l e sa n di n c r e m e n t a l u p d a t i n gf o ra s s o c i a t i o nr u l e s k e yw o r d s ：d a t am i n i n g ，p o s i t i v ea n dn e g a t i v ea s s o c i a t i o nr u l e s ，m i n s u p p o r t ，r a i n c o n f i d e n c e ，f r e q u e n ta n di n f r e q u e n ti t e m s e t s i i 学位论文独创性声明 本人声明，所呈交的学位论文系在导师指导下本人独立完成的研究成果。文 中引用他人的成果，均已做出明确标注或得到许可。论文内容未包含法律意义上 已属于他人的任何形式的研究成果，也不包含本人已用于其他学位申请的论文或 成果，与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示谢意。 论文作者签名：煎：堂屋 学位论文知识产权权属声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归属山东轻工 业学院。山东轻工业学院享有以任何方式发表、复制、公开阅览、借阅以及申请 专利等权利，同意学校保留并向国家有关部门或机构送交论文的复印件和电子 版，本人离校后发表或使用学位论文或与该论文直接相关的学术论文或成果时， 署名单位仍然为山东轻工业学院。 论文作者签名：盘! 室蕴 导师签名：兰企 日期：上孕- 年月上日 日期：4 年上月粤日 山东轻工业学院硕士学位论文 1 1 引言 第1 章绪论 随着社会的不断发展，信息已成为人类社会中除物质和能量之外的第三大资 源，同时，互联网的快速发展，使人类社会已经处于数据爆炸的状态下。面对如 此大量的信息，数据库技术的快速发展对数据的基本处理功能有了很大的提高， 如对数据的增加、删除、修改、数据查询和统计处理功能已经成为任何一个管理 系统所必备的功能。随着数据在日常决策中的重要地位越来越重要，人类对数据 处理技术的要求也因此不断提高，需要能够对数据进行更深层次处理，从而得到 关于数据的总体特征的认识，以便于达到对事物发展趋势的预测，而传统的数据 库管理系统是无法做到这些功能要求的。同时，数据量爆炸性的增长也使得传统 的手工处理方法变得不能符合实际的需要，假设这些天体数据由人们手工处理， 则需要几十年甚至上百年，所以急需要采用一种自动化程度相对更高、效率更好 的数据处理方法来帮助人们更好地进行数据分析，从而帮助人们更有效地收集、 选择以及存储所感兴趣的信息，更关键的是怎么帮助用户在日益增多的信息中发 现新概念和它们之间的关系，以及如何更高效的管理公司和企业运营过程中产生 的大量数据和信息，使之能做到信息处理的自动化，以便用于决策支持，这无疑 就需要一种强有力的工具对这些数据进行分析，从中得到有价值的信息，从而更 好地支持决策，数据挖掘( d a t am i n i n g ，d m ) 【l 】技术就在这样的背景下产生了。 从第一届知识发现( k n o w l e d g ed i s c o v 哪) 【z 1 国际研讨会吲于1 9 8 9 年8 月在美 国底特律举行到2 0 0 2 年7 月第八界a c m s i g k d d 知识发现和数据挖掘国际会议 在加拿大埃德蒙顿举行，由美国人工智能协会主办的k d d 国际研讨会已经召开 了8 次，规模由原来的专题讨论会发展到国际学术大会，人数由二三十人上升到 七八百人，论文收录比例大幅增加，并且研究重点也逐渐从发现方法转向系统应 用，更注重发现策略和技术的集成，以及多种学科之间的互相渗透。亚太地区在 北京召开的第三届p a k d d 会议收1 6 0 篇论文，2 0 0 3 年8 月，第九届a c m s i g k d d 知识发现和数据挖掘国际会议在美国的华盛顿举行。还有一些其他国际或者地区 性数据挖掘会议，如“知识发现和数据挖掘太平洋亚洲会议( p a k d d ) 【4 】 ；“数 据库中知识发现原理与实践欧洲会议( p k d d ) 嘲 ，数据仓库与知识发现国际会 议( d a w a k ) 等【6 。 2 0 0 1 年，g a r t t m g r o u p 的一次高级技术调查将数据挖掘和人工智能列为“未 来三到五年内将对工业产生深远影响的五大关键技术一之首，并且还将并行处理 第l 章绪论 体系和数据挖掘列为未来五年内投资焦点的十大新兴技术前两位。与国外相比， 国内对数据挖掘的研究开始较晚。虽然目前已经有很多优秀的数据挖掘软件已经 被开发并投入使用，但是总体上对数据挖掘的研究还不成熟，其应用还有较大的 局限性【引，其中提到的一点就是关于知识的维护和增量更新【9 】问题。正是这些局 限性，促使未来的数据挖掘技术的发展趋势【1o 1 1 1 。 1 2 研究的目的和意义 在实际应用中，遇到的情况可能是：随着时间的推移，数据库并不是静止的， 它会随着数据记录的增加而不断地改变，挖掘数据库的规模可能不断膨胀或需要 删除一部分记录，或需要对最小支持度进行调整从而逐步聚集到我们感兴趣的频 繁项目集上。因而根据用户需要，如何从数据发生变动后的数据库中高效地对已 经推导出的关联规则进行更新，具有为决策支持，企业管理提供理论依据的重要 的应用价值。这就是所谓的增量式关联规则挖掘的问题。 而传统的关联规则挖掘算法仅能用来发现那些具有高频率和强相关的显式模 式。但在现实中，数据库中还存在着许多采用目前挖掘技术所不能发现的隐式模 式，这些重要的隐士模式之一便是负关联规则，即两件事情很少同时出现，这些 隐式规则告诉我们哪些数据项目较少的一起发生，但它们却包含了非常有价值的 信息，因此发现负关联规则具有十分重要的意义。例如在销售和投资中，需要涉 及到一些有利因子和不利因子。为了将不利的因素最小化以及将有利因素最大化， 我们有必要考虑有利因子出现的概率，又要考虑不利因子出现的概率，以及有利 因子与不利因子之间的负关联关系。因此，识别负关联规则在应用中是有重要意 义的。发掘负关联规则是一个很重要的方面，而当事务数据库在发生改变后，关 联规则的更新则是另一个重要的方面。 1 3 国内外研究现状 1 3 1 国外研究现状 关联规则挖掘的概念及其算法最早是由m ma l m a d e nr e s e a r c hc e n t e r 的 a g r a w a l 等人提出的。自1 9 9 3 年以来，数据挖掘领域的研究人员对关联规则挖掘 的研究作了大量的工作，使其成为一种具有实际意义的数据挖掘技术。目前，一 般关联规则挖掘算法就是从大量的数据中挖掘关联规则，以此来体现一个数据库 中的数据项间彼此相联系的规律。a g r a w a l 等提出的a p r i o r i 算法【1 2 】是通过对数据 库进行多次扫描，反复连接直至产生数据项集的全部频繁项集。挖掘基于约束的 关联规则是关联规则挖掘发展的一个重要方向【1 3 l ，例如在科学研究、银行、电信、 保险、交通、零售等行业的应用。 2 山东轻工业学院硕士学位论文 关联规则挖掘技术的另外一个方向是增量更新问题。c h e u g 等首先提出了关 联规则的更新问题，提出了f u p 算法，在最小支持度不变的情况下，f u p 算法能 很好的解决事务数据库中增加数据时关联规则的更新问题。 1 3 2 国内研究情况 目前国内对关联规则挖掘所涉及的研究领域不是很多，多数集中于算法的研 究、关联规则挖掘的实际应用以及关联规则挖掘理论方面的研究。大多数研究项 目是由政府出资资助的，例如有中科院计算机研究所的智能信息处理重点实验室 研制开发的多策略数据挖掘平台m s m i n e r 系统，该系统集成了关联规则挖掘算 法：复旦大学的a r m i n c r 系统，此系统采用的关联规则挖掘算法是基于a p r i o r i 的改进算法。虽然已经取得了相当的成功，但是目前在处理极大规模的数据时， 如何提高算法效率，如何提供一种与用户交互的方法，以及如何将用户的领域知 识结合在其中等都是尚待解决的问题。 目前的增量式更新关联规则挖掘算法存在多次读取未变动之前的原始数据库 内容及产生大量的候选项目集过于庞大等问题，如i u a r 算法，用于解决元组数 和最小支持度发生变化时关联规则增量式更新问题，该算法是通过修正候选项目 集来进行挖掘；算法i u a 和p i u a ，主要考虑当最小支持度( m i n s u p ：m i n i m u m s u p p o r t ) 和最小可信度( m i n c o n f ：m i n i m u mc o n f i d e n c e ) 发生变化时，当前交易数据库 中关联规则的更新问题，利用从旧的频繁项目集所获得的信息来高效发现所有新 的频繁项目集。还有一些关联规则更新算法，也都以冯玉才等的砌a 算法为基础， 在此算法的基础上进行分析、修改，从而提出了一些改造方法，例如：宋海生的 u a 算法，皋军等提出的m y算法，周海岩提出的算法，钱进等提i u a n e w i u a 出的砌璩算法等。 上述对增量更新及算法的研究都是针对于正关联规则的，相对于正关联规则， 对负关联规则增量更新的研究，无论在国内还是国外，还没有相关的参考文献表 明有学者从事这方面的研究。 1 4 本文工作及创新点 1 4 1 本文的工作和内容组织 本课题在数据挖掘研究和关联规则挖掘研究的背景下，展开了对关联规则挖 掘方法及其增量更新技术的研究工作。在对关联规则挖掘知识进行了归纳和总结 的基础上，针对已有评价标准中存在的问题和传统频繁项集挖掘算法及其增量更 新中存在的不足，提出了新的解决方案。研究内容主要以下四个方面： 对关联规则的种类进行了系统地分类、归纳和总结，对关联规则典型挖掘 算法及其基本思想进行了详细地分析和研究。 3 第1 章绪论 对目前基于支持度置信度框架的关联规则挖掘算法进行了分析和研究。 为了解决发现仅仅利用支持度、置信度这两个标准来衡量关联规则经常会使 用户挖掘到虚假的、无效的规则这个问题，引入了相关支持度这个新的度量标准， 将置信度、支持度和相关支持度同时作为有效关联规则的评价标准。当挖掘出一 条关联规则的支持度、置信度、相关支持度同时满足最小支持度、最小置信度、 最小相关支持度的时候，才能被认为是有意义的规则。 经典a p r i o r i 算法会产生大量的候选项集，且算法在每二个阶段循环都需要 重复进行数据库存取，这对系统来说是一个巨大的负担。本文首先给出t a p r i o r i 算法的分析，进而对其进行了优化处理。 从研究正关联规则的增量式更新算法的基础上出发，首先改进了一种正关 联规则的增量更新算法。 在研究正关联规则增量更新的基础上，深入研究负关联规则，提出负关联 规则的增量更新的概念，以及展示了负关联规则增量更新技术的研究成果。 本论文的组织如下：， 第一章，介绍了数据挖掘与关联规则问题的研究背景，由此引出关联规则的 增量更新问题，并对关联规则的增量更新技领域进行了客观地总结和探讨，为本 文的全面展开作好铺垫。 第二章，在提出正关联规则基本概念的基础上，对正关联规则的种类进行了 全面的总结，重点对正关联规则的经典挖掘算法及其基本思想进行了详细的分析 和研究。提高算法效率的各种优化技术也在这里进行了讨论。 第三章，在提出负关联规则基本概念的基础上，从最小支持度、最小置信度 等方面对负关联规则进行了全面的分析，对负关联规则的挖掘算法也进行了分析 和研究。 第四章，对j 下关联规则的更新进行全面的分析与总结，分析了国内外对关联 规则挖掘算法及其更新的研究现状及研究中存在的问题，同时改进了一种正关联 规则的增量更新算法，最后指出了本课题的研究内容及研究意义。 第五章，在第四章对正关联规则的更新进行全面的分析与总结的基础上，对 负关联规则的更新进行全面的分析，并提出对负关联规则的更新的概念，同时对 其进行深入研究，提出一有效的更新算法。 第六章，最后是对全文的总结，首先对关联规则挖掘问题以及更新问题进行 总结，并指出了本文的工作需进一步完善和深入研究的地方。 1 4 2 本文的创新点 传统的关联规则挖掘都是考虑如何利用频繁项集挖掘有效的关联规则，而没 有挖掘非频繁项集的算法。现有的挖掘频繁项集的算法已经不能满足要求。而随 4 山东轻工业学院硕士学位论文 着数据库内数据的不断增加，需要对数据库进行更新。目前对数据库的更新主要 是针对正关联规则，而负关联规则具有同样的甚至比正关联规则更重要的作用。 本文的创新点如下： 本文在现有的正关联规则增量更新算法的基础上，针对现有的f u p 算法 的进行了改进，提出了一种新的增量更新算法- n f u p 算法； 针对目前国内外缺少对负关联规则增量更新算法研究的问题，本文对负关 联规则增量更新技术进行了深入研究，并提出了一种负关联规则的增量更新算法。 5 山东轻工业学院硕士学位论文 2 1 问题的阐述 第2 章关联规则挖掘 关联规贝l j ( a s s o c i a t i o nr u l e ，简称a r ) ，最初是由r a g r a w a l 、i m i e l i n s k 和s w a m 于1 9 9 3 年首先提出的有关概念，并且提出了a p r i o r i 算法，用于挖掘事务数据库 中项集之间的关联规则问题，并且于1 9 9 4 提出了一种快速算法【l 。在数据挖 掘中，关联规则的挖掘是一个很重要的研究课题。关联规则的挖掘就是从大量 数据中挖掘出事先未知的、有潜在价值的规则。这些规则蕴含了数据库中一些 数据项之间的特定关系，揭示了一些有用的信息。关联规则的挖掘对市场营销、 经营策略等具有重要的意义。 2 1 1 关联规则的概述 它的形式化描述如下： 设卢 f ，屯，) 是m 个不同项目的集合给定一个事务数据库d ，其中d 中每 一个事务r 是，中一组项目的集合，即r e 厶t 有一个唯一的标志符t i d 。如果 对于，中的_ 个子集z 有埏l 我们就说一个事务r 包含瓜关联规则“香烟 j 啤酒( s u p p o r t = 3 0 ，c o n f i d e n c e = 9 0 ) ，说明在所有的顾客事务中，有3 0 的顾客同时购买了香烟和啤酒，其支持度s u p p o r t = 3 0 ，而购买了香烟的顾客 中有9 0 的顾客也购买了啤酒，其置信度c o n f i d e n c e = 9 0 刀，这就是有名的支 持度一置信度框架( s u p p o r t c o n f i d e n c ef r a m e w o r k ) 。 下面用两个实例进一步说明关联规则【i 列。 实例1 c o n t a i n s ( t , “电脑”) = c o n t a i n s ( t , “软件 ) s u p p o r t - - - - 4 ，c o n f i d e n c e = 6 0 】 在这里，嘿表示事务记录( t r a n s a c t i o nr e c o r d ) 的变量。该规则表明，如果 事务砷包含“电脑”，则它同时包含“软件”的可能性为6 0 ，并且所有事务 中有4 包含了两者。 实例2 ： a g e ( t , “2 5 4 5 ) a b u y s ( t , “笔记本 ) = b u y s ( t , “打印机”) s u p p o r t = 1 ，c o , , f i d e n c e = 6 0 】 以上规则说明，年龄在2 5 - 4 5 之间并且购买笔记本的人，其购买打印机的可能 性是6 0 。 关联规则挖掘就是从事务数据库中找出上述形式的规则。 7 第2 章关联规则挖掘 定义2 1 关联规则谢= f ，2 , ， 是数据库中所有不同项目的集合。关联规 则是形如释蹦蕴涵式，其中x 】，t ，耐ny - 口。脉为规则前件，琳为规则 后件，关联规则x = y 在事务数据库d 中的支持度是d 中事务包机踊百分比， 它是概率p ( x u 功，记作s u p p o r t ( x - - - y ) 郴uy ) = ix uy | p i 。 定义2 2 可信度关联规则謦i 难事务数据库d 中的可信度是d 中包含的牌 务同时也包含】，的百分比，它是条件概率p ( ，记作c o n f i d e n c e ( x = d - - p ( y i x ) = l x u y | 闳。 定义2 3 强关联规则如果事务数据库d 上的关联规贝i l 净 啪支持度和可信度 分别大于等于最小支持度阀值m i n - s u p 和最小可信度阀值m i n c d 斫则称此关联规则 为强关联规则。最小支持度表示项集在统计意义上的最低重要性，最小可信度表 示规则的最低可靠性。 关联规则成立的条件是：它具有最小支持度s ，即事务数据库d 中至少有s 的事务包机y 它具有最小可信度c ，即在事务数据库d 中包含x 的事务中至 少有c 同时也包含】，。同时满足最小支持度阈值和最小置信度阈值的规则称为强规 则。给定一个事务集d ，挖掘关联规则问题就是产生支持度和可信度分别大于用户 给定的最小支持度和最小可信度的关联规则，也就是产生强规则的问题。 定义2 4 如果一个项目集么满足最小支持度阀值m i n - s u p ，即 s u p p o r t ( x ) _ m i n - s u p ，则称它为频繁项集。频繁项集通常记为( f r e q u e n t i t e m s e t ) 。反 之，如果一个项目集a 不满足最小支持度，则称为非频繁项集。 定义2 5 候选项集是潜在的频繁项集的集合，是频繁k - 1 项集的超集，含有k 项的候选项集表示为q ，由它构成频繁卜项靴七。 性质频繁项集的任何非空子集必定是频繁的，即：任何非频繁项集的超集 必定不是频繁的。 比如：如果项集 f ，0 ，妇，是频繁的，那么项集( f ，如 ， f ，白 也是频繁的。 如果项集 f ，f 2 是非频繁项集，那么包含i t 和i z 的项集 f ，i 2 , i j ， i t , i z , h 都是非频 繁项集。 2 1 2 关联规则的分类 关联规贝l j 可以分为以下几种f 1 6 】： 基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。 基于规则中涉及到的数据的维数，可以分为单维关联规则和多维关联规 则。 基于规则中数据的抽象层次，关联规则可以分为单层的和多层的。 8 山东轻工业学院硕士学位论文 2 2 关联规则的扩展模型 自关联规则提出以来，学术界已经提出了许多推广和改进模型，下面介绍有 代表性的几种。 ( 1 ) 加权( w e i g h t e d ) 关联规则【1 7 ，1 明 一般的挖掘关联规则算法中隐含了一个约定，即记录集中的数据库的各属性 和各交易对关联规则挖掘的作用基本都是相同的。实际上，不同的项目常常有着 不同的重要性，这几乎是现实世界数据库的内在特征。比如，商场中不同商品之 间的利润是不同的，有的商品可能处于热销中等等。如对待所有的交易不加区分， 就有可能生成大量对低利润、高销售量的商品的关联规则，无疑会对商家产生误 导。为了反映各个项目的不同重要性，引入项目权重的概念，从而扩展了现有的 关联规则模型，成为所谓加权关联规则模型。 ( 2 ) 时态似i m p o r a l ) 关联规则【1 9 刎 在现实世界中，由于时间是数据本身固有的因素，例如超市交易记录中的交 易时间，病历中的检查和诊断时间等，因此在数据中常常会发现时态语义问题。 时态数据的出现使我们有必要在数据挖掘中考虑时间因素，在现实中，附加上某 种时态约束的规则将可以更好地描述客观现实情况，因而也会更有价值，称这样 的规则为时态关联规则。 ( 3 ) 约束( c o 璐廿a i n e d ) 关联规则【2 l l 经典的关联规则挖掘算法，一般是给定了支持度和置信度，算法自动实现关 联规则的挖掘过程，最后给出挖掘结果。 无法进一步介入挖掘过程，而在实际中， 给定了支持度和置信度阈值后，用户便 用户希望参与到挖掘的全过程中来，以 对挖掘过程进行控制。另外，用户有可能只想知道关于某些方面的关联规则，而 不是泛泛地发现全部规则。为了解决上述两个问题，人们提出了约束关联规则模 型，它将约束条件结合到挖掘算法过程中，从而提高了规则的有用性和挖掘效率。 ( 4 ) 多支持度( m u l t i s u p p o r t ) 关联规则僻1 在实际的关联规则采集中，最关键的因素是最小支持度，它用来缩减搜索空 间和限制生成规则的数目。然而仅用单个最小支持度，隐含地假设了数据库中的 子项集有相同的性质或相似的出现频率。而在实际应用中有些子项集可能出现很 频繁，另外一些子项集却很少出现。若子项集的出现频率差别很大，却只用一个 最小支持度，如果最小支持度设置过高，很多有价值的规则就会被遗漏；如果最 小支持度设置过低，就会生成大量无用的关联规则。为了解决这样的问题，有学 者开始研究多支持度关联规则。在多支持度模型中，关联规则的定义同基本模型 是一致的，但对最小支持度的定义作了改变。例如，对数据库中每个子项集有一 个最小子项支持度( m i s ) 。用户可以根据出现的频繁程度为每个子项集指定不同的 9 第2 章关联规则挖掘 m i s 值。规则的最小支持度定义为在规则中出现的所有子项集的m i s 的最小值。 ( 5 ) 负关联规则 传统的关联规则是形如胎】，这样的表达式，它用于发现大量数据中项集之 间有意义的关联。通过传统的关联规则我们只能使交易中出现的项集发生正面关 联，无法发现数据中隐藏的另一种关系：负关联关系，即某数据项集x 的出现会 减少另一数据项集y 的出现机会，甚至使得y 不出现。而在实际的应用中，负关 联关系对于决策的作用也是不可忽视的。这种反映负关联关系的规则称为负关联 规则，它是形如。特 y ，7 糙y ，1 抽，y 的蕴涵式。目前对负关联规则的研究还 比较少，主要有s n a ( s t r o n gn e g a t i v ea s s o c i a t i o n s ) 算法【2 引，p n r ( p o s i t i v ea n dn e g a t i v e a s s o c i a t i o n sr u l e s ) 算法 2 4 1 ，s r m ( s u b s t i t u t i o nr u l e sm i n i n g ) 算法【2 5 】。 2 3 关联规则的挖掘 关联规则挖掘( a s s o c i a t i o nr u l e sm i n i n g ) 是数据挖掘研究中的一个重要分支。 关联规则是数据挖掘的众多知识类型中最为典型的一种，该问题是a g r a w a l 等在 1 9 9 3 年在对市场购物篮问题( m a r k e tb a s k e ta n a l y s i s ) 2 6 】进行分析后首次提出的， 用以发现商品销售中的顾客购买模式。 关联规则挖掘可以发现交易数据库中项目( i t e m s ) 或属性( a t t r i b u t e s ) 之间的有 趣联系，这些联系是预先未知的，不能通过数据库的逻辑操作( 如表的联接) 或统 计的方法得出。这说明它们不是基于数据自身的固有属性( 如函数依赖关系) ，而 是基于数据项目的同时出现的特征。最为典型的例子是“在购买面包的顾客中有 8 0 也购买了黄油 。大型商场和超市的数据库中保存了大量的顾客的购买信息， 从中发掘黄油一面包这类有趣的关联关系，可以指导商家制定正确的销售决策， 如交叉购物、贱卖分析、目录设计、商品陈列等，从而使他们在市场竞争中取得 更大的主动权。其实，关联规则的应用不仅仅局限于市场菜篮分析，它有着广泛 的应用领域，如商业与金融、人口普查数据分析、工程技术数据分析、医疗、财 政、宏观决策支持、电子商务、c r m 、网站设计、互联网等等。 2 3 1 关联规则挖掘 关联规则的挖掘是对给定的一个交易数据库，求出所有满足最小支持度和最 小可信度的关联规则的过程。关联规则的挖掘问题可以分解为以下两个问题： 找出事务数据库中所有具有用户最小支持度的项目集。具有用户指定最小 支持度的项目集称为频繁项目集1 2 7 】，反之称为非频繁项目集。一个项目中所含项 目的个数称为该项目的长度： 利用频繁项目集生成关联规则。对于每一个频繁项目集五若y c x , 】，矽， 且s u p p o r t ( x ) s u p p o r t ( y ) m i n c o n f , 则有关联规则b ( x - 功。 1 0 山东轻工业学院硕士学位论文 目前大多数的研究主要集中在第一个问题上面。 2 4 关联规则挖掘算法 2 4 1 经典a p r i o r i 算法 其核心是基于两阶段频集思想的递推算法。 首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一 样。然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度。 挖掘关联规则的总体性能由第一步决定，第二步相对容易实现。 a p r i o r i 核心算法分析： 为了生成所有频集，使用了递推的方法。其核心思想简要描述如下： ( 1 ) l l = f r e q u e n tl - i t e m s e t s ( 2 ) f o r ( 七= 2 ；“l ；j b h ) d ob e g i n ( 3 ) c k - - - a p r i o r i j e n ( l 七i ) ，新的候选集 ( 4 ) f o ra l lt r a n s a c t i o n st e dd ob e g i n ( 5 )c t = s u b s e t ( c k ，t ) ( 6 ) f o ra l lc a n d i d a t e sc gd o ( 7 ) c c 口“刀件+ ( 8 ) e n d ( 9 ) l k = c eq l c c o u n t m i n s u p p i d i ( 1 0 ) e n d ( 1 1 ) a n s w e r = u 南l k a p r i o r i g e n 函数的功能是从第k 次遍历数据库后找出的频繁项集集合厶 中产生第k + 1 次遍历所要计数的长度为k + l 的候选项集集合q + ，并且要保证 q + ，中项集的所有肛项子集都是频繁项集。 a p r i o r i _ g e n 函数分为两步，连接步：将l k - 做自身连接；剪枝步：对于q 中任意候选项集c ，如果c 的某个长度为肛j 的子集不属于三纠，则将c 从q 中删除，函数h a si n f r e q u e n t用于完成剪枝功能。 两个函数如下： s u b s e t f u n c t i o na p r i o r i - g e n ( l k 1 ：f r e q u e n t ( k - 1 ) - i t e m s e t s ) ( 1 ) f o re a c hi t e m s e t l t 1 ( 2 ) f o re a c hi t e m s e tl 2e l k q ( 3 )i f i 1 = l 2 1 1 ) a 但i 2 】屯2 2 】) 八八犯i k - 2 = l 2 k - 2 ) 八犯i k - 1 】 j ) 。例如，当扫描数据库中每个事务， 由c ，中的候选1 项集产生频繁l 一项集三，时，可以将每个事务产生所有的2 一 项集散列( 即，映射) 到散列表结构的不同桶中，并增加相应的桶计数。当散列表 中对应的桶计数低于支持度阀值的2 项集时，此项集不可能是频繁2 一项集，因而 应当由候选项集中删除。 ( 3 ) 划分 使用划分技术，要挖掘频繁项集，只需要扫描两次数据库。第l 遍，算法将 事务划分成刀个非重叠的部分。如果d 事务的最小支持度为m i n - s u p ，则每个部 分的最小支持度计数为r a i n - s u p 。对每一部分，找出该部分内的频繁项集。这些称 作局部频繁项集。该过程采用一种特殊的数据结构，对每个项集，记录包含项集 中项的事务的t i d 。这使得对于k = l ，2 ，找出所有的局部频繁厶项集只需要扫描 一次数据库。 ( 4 ) 选样方法 选取给定数据库的随机样本s ，然后，在s 中搜索频繁项集。用这