（管理科学与工程专业论文）关联规则算法及其应用研究.pdf

摘要 随着数据库应用的不断深化，数据库的规模急剧膨胀，人们需要 对这些数据进行分析，从中发现有价值的信息。但是数据库管理系统 本身却没有提供有效的工具和方法来利用这些数据，因此数据挖掘成 为当今研究的热点。数据挖掘中关联规则的挖掘获得了广泛的关注， 它是从历史数据中发现项集之间的相互联系，提取出有用的和感兴趣 的模式。本文即对数据挖掘中的关联规则进行系统研究。 作者综述了国内外关联规则的研究现状和应用成果，深入分析了 关联规则的基本理论和分类方法，介绍了经典的a p r i o r i 算法，并提 出了关联规则的价值衡量方法。在基本理论分析的基础上，深入探讨 了多维关联规则和序列模式关联的研究成果和应用情况，并针对研究 中的重点提出了改进算法，即基于垂直数据分布和等价类的多维关联 规则算法和带时间约束的序列模式关联算法。改进算法比原算法提高 了挖掘效率，同时更加灵活，并能适应实际数据挖掘中用户的特定需 求。 最后，作者将改进的多维关联规则算法应用于移动公司流失客户 的特征分析中，详细阐述了客户特征数据挖掘的流程设计、数据选取 和具体实施，最后对挖掘的规则进行了分析，并对模型提出了改进设 想。 关键词数据挖掘，多维关联规则，序列模式，电信，客户流失 a b s t r a c t w i t ht h e d e 印e n i n g o ft h e 印p l i c a t i o no fd a t a b a s e ，m e s i z eo f d a t a b a s ee x p a n d sq u i c k l y ；p e o p l en e e dt oa n a l y s et h e s ed a t aa n df i n dt h e w o r t h yi n f o m a t i o n s b u t t h ed a t a b a s e m a n a g e m e n ts y s t e m s d on o t p r o v i d ea v a i l a b l e t o o l st o a n a l y s ea n du s et h e s ed a t a ，s od a t am i n j n g a p p e a r s a n db e c o m e st h e h o t s p o t p e o p l ep a y m u c ha t t e n t i o n t o a s s o c i a t i o nr u l e si nd a t am i n i n g i tf i n d sm er e l a t i o n sb e t w e e ni t e m s e t s a m o n gh i s t o r i c a l d a t aa n dp i c ku pu s e f - u la n di n t e r e s t i n gm o d e l s t h i s t h e s i sr e s e a r c h sa s s o c i a t i o nr u l e sb yt h en u m b e r s t h ea u t h o rs u m m a r i z e st h er e s e a r c h i n ga c t u a l i t ) ra f l dm e p r o d u c t i o n o f a p p l i c a t i o n ，t h e na n a l y s e st h e s t a n d a r dm e o r i e sa i l dm em e a s u r eo f s o r t i n g t h et 1 1 e s i sa i l a l y s e st 1 e c l a s s i ca p r i o r ia l g o r i t h m ，a n dp r o v i d e s t h em e a s u r eo fs c a l i n gt h ev a l u eo fa s s o c i a t i o nm l e s a tm eb a s eo f a 1 1 a l y s i s o fm e o r i e s ，w ea 1 1 a l y s et h e a l g o r i t h m o fm u l t i - d i m e n s i o n a l a s s o c i a t i o nr u l e sa n d s e q u e n c ep a t t e m w ep r o v i d et h e i m p r o v i n g a l g o r i t h m sa r e rw ea n a l y s et h es t a n d a r dt h e o r i e sa 1 1 da l g o r i t l l m sa b o u t t h e m t h e ya r e m u l t i d i m e n s i o n a la s s o c i a t i o nm l ea l g o r i t h mb a s e do n v e r t i c a ld a t al a y o u ta n de q u i v a l e n c ec l a s sc l u s t e r i n g ，s e q u e n c ep a t t e m a l g o r i t h n lw i t hc o n s t r a i n to f t i m e t h ei m p r o v i n g a l g o r i t l l i n sh a v eb e t t e r e m c i e n c y t h a no r 蟛n a lo n e sa n dc a na d 印to nt l l eu s e r ss p e c i a ld e m a n d s i na c t u a la p p l i c a t i o no fd a t am i n i n g l a t e r ，m ea u t h o rp u t st h ei m p r o v i n gm u l t i - d e m e n s i o n a la s s o c i a t i o n n l l e a l g o r i t l l i n i n t ot h e a i l a l y s i s o ft h e l o s i n g c u s t o m e r si nm o b i l e t e l e c o m m u n i c a t i o nc o i p o m t i o n t h em e s i sa n a l y s e st 1 1 ed e s i g no fn o w ， s e l e c t i o no fd a t aa n dc o n c r e t ea p p l y o ft h e m i n i n g i n 也ed a t ao f c h a r a c t e r so fc u s t o m e r s a t1 a s t ，w ea n a l y s em e m i n e dr u l e sa i l dg i v et h e a d v i c e so f i m p r o v i n g t h em o d e l k e yw o r d s d a t am i n i n g ，m u l t i d i m e n s i o na s s o c i a t i o nm l e s ，s e q u e n c e p a t c e m s ，t e l e c o m n u n i c 砒i o n ， c u s t o m e r1 0 s s 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：式苟日期：堕年旦月笪日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位 论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论 文：学校可根据国家或湖南省有关部门规定送交学位论文。 作者签名：盛笪导师签名 h z 卜 月一日 堡圭堂堡笙塞 篓二童量丝 1 1 引言 第一章导论 1 1 1 问题的提出 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的数 据越来越多。激增的数据背后隐藏着许多重要的信息，人们希望能够对其进行 更高层次的分析，以便更好地利用这些数据。目前的数据库系统可以高效地实 现数据的录入、查询、统计等功能，但无法发现数据中存在的联系和规则，无 法根据现有的数据预测未来的发展趋势。缺乏挖掘数据背后隐藏知识的手段， 导致了“数据爆炸但知识贫乏”的现象。正是在这种情况下，数据挖掘( d a t a m i n i n g ) 技术应运而生。 有关调查显示，数据挖掘市场是目前数据库市场中最重要和发展最快的部 分。据国外专家预测，在今后的5 1 0 年内，随着数据量的日益积累以及计算 机的广泛应用，数据挖掘将在中国形成一个产业“。2 0 0 0 年7 月i d c 发布了关 于信息存取工具市场的报告，其中1 9 9 9 年的数据挖掘的市场大概是7 5 亿美元， 估计在下个5 年内市场的年增长率( c o m p o 蚰d a n n u a lg r o w t l l r 丑t e ) 为3 2 4 ， 其中亚太地区为2 6 6 ，并且预测此市场在2 0 0 3 年时会达到2 2 亿美元“。随着 数据挖掘应用领域的发展和成熟，市场份额将继续加速增长。 在数据挖掘中，关联分析( a s s o c i a t i o na i l a l y s i s ) 是其中十分重要的组成部分。 关联分析的主要目标是发现关联规则。自从a 擎a w a l 在1 9 9 3 年提出挖掘关联规 则的问题后，关联规则的研究出现了一个热潮。它最早解决的问题是购物篮分 析，就是在超市的交易数据库中发现顾客购买物品间的相关性。但是关联规则 算法仍然存在着一些问题：第一，关联规则的发现算法主要集中在事务数据库 的应用上，但是目前数据库系统中应用最广泛的是关系数据库，它和事务数据 库的结构和处理方法存在着相当大的区别，事务数据库上关联规则算法如何改 进以应用到关系数据库中急待解决。第二，传统的关联规则挖掘研究集中在事 务项集的基础上，它主要是布尔型或类别型属性，对于关系数据库中大量存在 的多维属性，传统的关联规则挖掘算法对它们的处理仍显得薄弱。关联分析中 另一个挖掘的主要目标是序列模式的挖掘，它是发现时序基础的模式关联。随 着应用的深入，它逐渐得到了人们的重视，目前的序列模式挖掘算法数据域过 于宽泛，需要引入必要的约束条件进行限制。本论文就是基于关联规则中多维 硕士学位论文 第一章导论 关联和序列模式关联这两个重要的应用领域进行研究的。 1 ，1 ，2 本文的研究背景 本文的主要研究背景如下： 1 计算机技术的飞速进步 自从1 9 4 6 年世界上第一台计算机问世以来，计算机的硬件发展迅速，从最 初的电子管到随后的晶体管，直到目前的大规模集成电路芯片的应用，硬件性 能成级数增长。 硬件的发展也同样促进了软件的发展。过去的3 0 年中，计算机稳定的、令 人吃惊的进步导致了功能强大的计算机、数据收集设备和存储介质的大量供应。 这些技术推动了数据库和信息产业的发展，大量数据库信息被用于事务管理、 信息检索和数据分析。因为计算能力的大幅度提升，数据挖掘所需的大量计算 和实时分析成为可能。人们可以利用先进的计算机软件及硬件技术发现数据问 感兴趣的隐含联系。 2 数据库技术的迅速发展 自2 0 世纪6 0 年代以来，数据库技术得到迅速发展，新的数据库系统层出 不穷，从早期的层次数据库到后来的网状数据库，直到目前广泛应用的关系数 据库。系统和数据建模工具、索引和数据组织技术不断进步，数据库存储、统 计和分析数据的能力大大增强。用户通过查询语言、用户乔面、优化的查询处 理和事务管理，可以方便、灵活地访问数据。 8 0 年代中期以来，数据库技术的特点是广泛吸收关系技术，研究和开发新 的、功能强大的数据库系统。这些系统使用了先进的数据模型，如扩充关系模 型、面向对象模型和演绎模型等：主动数据库、科学数据库、知识库和办公信 息库在内的面向应用的数据库系统广泛出现。上世纪末发展起来的联机分析处 理f o l a p ) 和数据仓库的应用，使数据的存储和分析更加迅速、便捷。凭借这些 技术和设备，人们存储了海量的数据，这就要求提供更加高效的数据分析处理 工具。 3 各类数据挖掘技术的出现和发展 数据挖掘技术主要分为基于统计的方法和基于知识发现的方法。从2 0 世纪 6 0 年代以来，基于统计思想的聚类和时间序列技术得到了迅速的发展i 随着人 工智能的出现和计算技术的长足进步，自学习的知识发现技术得到了人们的重 视，并被应用到生产实践中，这类技术主要有神经网络、遗传算法、关联规则 等。各类数据挖掘技术的出现和发展，为本文随后的研究提供了坚实的理论基 础和丰富的应用实例。 2 硕士学位论文 第一章导论 1 1 3 本文研究的目的和意义 1 分析目前关联规则技术发展的热点和应用问题 目前，商业数据库正在以一个空前的速度增长，并且数据仓库正在广泛地 应用于各种行业；对计算机硬件性能提出了越来越高的要求，现在开始使用并 行多处理机来满足需求。为了不至于淹没在海量的数据中，入们开始使用数据 挖掘技术来及时、有效地对数据进行分析，找出其中的联系和规则，并通过分 析这些联系和规则来指导商务活动的开展。这其中关联规则的挖掘成为必不可 少的重要组成部分。本文旨在分析关联规则的大量文献资料和关联规则具体应 用的基础上，提出改进的算法并用于企业实践。 2 分析和改进部分算法以适用于目前的数据挖掘 关联规则可以发现数据库中数据间的联系和相互的影响，并形成直观的规 则以指导人们在商务活动中的具体决策。关系数据库的大量应用，多维型数据 和数值型数据大量出现，对于关联规则的发展提出了新的课题。必须考虑如何 对关联规则的挖掘算法加以变化来挖掘这些数据类型之间的联系和规则。这些 方面的关联规则挖掘算法在考虑传统的支持度和置信度来形成规则的同时，必 须引入新思路。关联规则其它方面的研究可以给予我们启示。本文正是在这； 中 情况下，对部分关联规则算法进行改进，来更好地挖掘这方面数据的联系。改 进算法可以根据应用的实际环境加以变化。 3 将关联规则算法用于企业实际数据库中，根据挖掘的规则指导企业的商 务决策。 现代企业的数据正在实现由商业数据向商业信息化转变的过程，数据挖掘 是其中最具革命性的一次变革。因为这一阶段的数据库技术已经可以回答人们 的许多问题了。现代企业更加重视客户关系管理的建设，对客户行为的关注胜 过以往任何时期。关联规则就可以用来发现企业客户数据库中隐藏的客户行为 模式信息，如简单关联、序列模式关联等。在此基础上，对客户行为做深层次 分析，对企业的广告、一对一营销等商务决策大有帮助，从而实现企业数据库 的黄金价值。本文的应用实例也是基于客户数据的挖掘来发现其中的关联规则。 1 2 国内外研究现状 关联规则作为一个研究领域仅仅是最近几年的事情，但是在出现后的几年 里已经成为数据库界广泛研究的热点。关联规则的概念最早是由a g r a _ w a l 等人提 出的，随后，诸多的研究入员对其进行了大量研究。他们的工作包括对原有的 硕士学位论文 第章导论 算法进行优化，如引入随机采样、并行的思想等，以提高算法挖掘的效率；还 有就是对关联规则的应用进行推广等。关联规则的研究主要是算法和实施，理 论上的研究主要是针对不同数据形式的最优算法，实际应用则强调关联规则与 数据库技术的紧密配合及实施方法的选择。 a g r a w a l 于1 9 9 3 年在文献“。中第一次提出了关联规则的基本概念，并且给出 了一个初始的a i s 算法；a g r a w a l 又于1 9 9 5 年在文献“1 中提出了经典的a p r i o r i 算 法，这个算法奠定了关联规则挖掘算法的基础，该算法中所使用的思想在其它 多个算法中被使用。同时，在文献”1 中还提出了一个改进的算法- a 鲥o r i t i d 算 法和两个算法的结合a p r i o r i h y b r i d 算法。随后，许多人对a p r i o r i 算法进行了改 进。p a r k 等人在文献。1 。提出了d h p 算法。它使用h a s h 树的方法来高效地产生频 繁集。j i a w e ih a n 在文献中提出了f p g m 、v t h 算法，它不需要产生候选频繁集； 通过将数据库压缩进一棵频繁模式树来产生条件模式基并最终生成频繁集。文 献”。中设计了一个基于划分( p a n i t i o n ) 的算法，通过将数据库划分为不相连的几 个子块，对每一个子块独立求取频繁集，最后再产生全局频繁项集。文献1 中提 出了基于采样的算法，他们从数据库中抽取采样得到规则然后得到在全局数据 库中的规则。文献“中提出了一种动态扫描数据库来产生频繁集的d i c 算法。它 在第一次扫描数据库时，动态地开始对数据库的各次扫描，求解各个长度频繁集 的过程同时进行，有效地减少了对数据库的扫描次数。 随着数据仓库和联机分析处理( o l a p ) 的发展，逐渐形成了多层和多维关联 规则的挖掘算法。文献“中提出了属性概念分层的概念，在文献。中，h a i l 根 据概念分层的定义，提出了多层关联规则的挖掘算法。文献“提出了多维关联 规则挖掘的基本思想：将其转化为布尔型关联规则求解。文中提出了挖掘二维 关联规则的算法：应用桶结构存储划分的数据，加快关联规则的挖掘。为了加 强关联规则的通用性，人们对其中的部分概念进行了发展。文献。中对兴趣度 进行了发展，提出了基于兴趣度的关联规则算法。在文献“中提出了强集合项 集的概念。文献“”1 提出了基于约束的关联规则挖掘算法，利用规则模板和设 置初始值对规则进行过滤。以上三者的目标都是要挖掘有效的强规则，但侧重 点各有不同。 在挖掘关联规则时考虑时间因素在最近几年才逐渐发展成熟，并形成了序 列模式的挖掘算法。文献9 叼提出了0 s p 算法，它借鉴a p r i o r i 算法的思想来进行 序列模式的挖掘。在文献。钔中，h a i l 等人提出了p r e 做s p a n 算法，它是应用模式 增长来挖掘数据库中的序列模式。 关联规则在国外已进入了产品化阶段，主要有i b m 公司的q u e s t ，加拿大 硕士学位论文 第一章导论 f r c s a r 大学的d b m i n e r ，以及用于图像处理的s k i c a t “。关联规则挖掘的研究在 我国起步较晚，目前研究的重点仍集中在对国外算法的理解和改进上，以适合 中国数据库系统的实际情况。对于数据挖掘( 包括关联规则的挖掘) 的实际应用 研究得相对较少，到2 0 0 0 年国内开发出了第一套主要针对关联规则挖掘的产品 d m i n e r s “，它是基于c s 规范的。最近几年，国内更全面的数据挖掘产品正在 研究和开发之中，但是还没有出现很好地适用于多平台的产品。目前数据挖掘 在我国的应用主要集中在一些信息化建设比较好的行业和部门，包括银行、金 融、电信等。更深层次的应用和对复杂问题的解决方案还有待进一步地研究和 实践。 1 3 本文的研究内容 1 31 本文的研究思路 本文遵循从理论到实践的研究思路。 首先根据实际应用提出问题。从企业目前处理和分析数据的前景和数据挖 掘中关联规则的应用现状，提出本文将要研究的主要内容，即改进关联规则算 法并应用于企业的商务决策中。 然后从理论上分析关联规则的基本理论和各类规则算法，并深入分析了多 维关联规则的挖掘算法和带时间约束的序列模式算法，从而为随后的实证分析 打下基础。 最后，本文再次着重于实际应用，在前文深入研究的多维关联规则算法的 基础上，将关联规则挖掘算法运用到企业客户数据分析中，并作出评价。 1 3 2 本文的主要内容 首先介绍了本文的研究背景，即近年来计算机软、硬件技术飞速进步，数 据库技术迅速发展，各类数据挖掘算法的发展和成熟，但是以前使用的数据仓 库和联机分析处理( o l a p ) 中简单的数据分析和处理不能从海量数据中提取隐含 的规则，不能满足人们从数据中获取利益的目的，不能对市场环境的变化做出 快速反应。因此，数据挖掘技术应运而生。随后，作者指出了本文研究的目的 和意义，并给出了研究思路和结构安排。 接着本文深入分析了数据挖掘中的关联规则。从基本概念入手，介绍了关 联规则的基本概念及定理，随后分析了关联规则经典的蜘。再算法，并分析了 关联规则的价值衡量方法。 再次，本文重点分析了多维关联规则和序列模式关联的挖掘算法，针对多 硕士学位论文第一章导论 维关联规则挖掘算法和序列模式算法存在的问题，提出了改进算法，旨在提高 算法效率，并更适用于企业的数据挖掘。 最后，本文用一个移动公司的实例对改进的多维关联规则算法进行实证分 析，论述了关联规则在企业商务决策中的应用。通过计算机程序实现这一算法， 使算法更具实用性和操作性。 1 3 3 本文的结构安排 本文的行文结构如下： 第一章，介绍了数据挖掘的产生背景以及关联规则的问题，然后分析了关 联规则在国内外的研究现状，在此基础上提出了本文的研究内容a 第二章，介绍关联规则的定义和分类，分析了关联规则中的经典算法，分 析了关联规则的价值衡量方法。 第三章，在上一章研究的基础上，详细讨论了多维关联规则挖掘算法和序 列模式关联挖掘算法，并在原有算法基础上提出了基于等价类和垂直数据分布 的多维关联规则改进算法和带时间约束的序列模式算法，并用实例阐明了改进 的算法。 第四章，将多维关联规则算法应用于移动公司的业务分析中，挖掘企业流 失客户的特征信息，并对规则进行了总结和评价。 第五章，结束语。 6 堡主堂堡丝苎 蔓三童差壁塑型堡堡皇丝墨竺鲨塑窒 第二章关联规则理论与经典算法研究 2 1 关联规则的基本概念 2 1 1 关联规则问题的提出 数据关联是数据库中存在的一类重要的可被发现的知识。若两个或多个变 量的取值之间存在某种规律性，就称为关联。关联规则侧重于确定数据中不同 领域之间的联系，即寻找给定数据集中的有趣联系。有时并不知道数据库中数 据的关联函数，即使知道也是不确定的。因此关联规则挖掘是一个自学习的过 程，通过它可以发现人们不知道的、或者是出乎人们预料的规则。 a g m w a l 等人于1 9 9 3 年首先提出了挖掘顾客交易数据库中项集间的关联规 则问题，他提出的关联规则是发现交易数据库中不同商品( 项) 之间的联系， 并通过这些规则找出顾客的购买行为模式，如购买了某一商品的同时会购买其 它的商品，以及购买后对其他商品的影响。发现这样的规则可以应用于商品货 架设计、库存安排以及根据购买模式对用户进行分类。 2 1 2 基本概念和描述 为了准确描述关联规则挖掘问题，需要给出关联规则挖掘问题的正式定义， 下面用事务数据库来定义关联规则。 定义2 1 “记| d 为交易( t r a i l s a c t i o n ) 丁的集合。d = f l ，r 2 ，f 。 ，这里交易 7 1 是项的集合，可以表述为：r = “f 2 “，f 。) ，并且丁d 。r 中的元素 i ，( 产1 ，2 ，p ) 称为项。对应每一个交易有唯一的标识，如交易号，记作t i d 。 定义2 2 ”设，= f ，f ：，) 是数据集中所有项的集合，是二进制文字 的集合。，中的任何子集称为项目集( i t c m s e t ) ，若x p 七，则称集合x 为一项集。 设和x 分别为d 中的事务和项目集，如果x ，称事务包含项目集x 。 数据集d 中包含项目集x 的事务数称为项目集j 的支持数，记为盯。项目 集x 的支持率，记作：s u p p o ，r ( x ) 。 s u p p o ，f ( x ) = 二生1 0 0 公式( 2 1 ) ld l 其中l d i 是数据集d 中的事务数。若s u p p o 呱x ) 不小于用户指定的最小支持 率( 记作：i n i n s u p p o r t ) ，则称x 为频繁项目集，否则称x 为非频繁项目集a 定理2 1 ( 向下封闭定理) 幢阳设工、y 是数据集d 中的项目集 1 若x y ，则s u p p o n ( x ) s u p p o n ( y ) ： 公式( 2 2 ) 7 硕士学位论文第二章关联规则理论与经典算法研究 2 若z y ，如果z 是非频繁项目集，则y 也是非频繁项目集； 3 若工y ，如果王，是频繁项目集，则x 也是频繁项目集。 一个关联规则是形如z y 的蕴涵式，这里x 、】，都是项目集，且爿c j ，c ，并且x n y = o 。x 、y 分别称为关联规则z j y 的前提( l h s ) 和结论 ( r h s ) 。 一般使用以下几个参数来描述关联规则的属性”： 1 支持度( s u p p o r t ) 规则工j y 在数据库d 中的支持度( s u p p o r t ) 是交易集中同时包含x 和y 的 事务数与所有事务数之比，记为s u p p o ( z y ) 。设i d i 为交易数据库中交易总 数，即 s u p p o ( x j 】，) = i 丁：u y 量r ，r d ) l 卅d 户s u p p d 一( u y ) 公式( 2 _ 3 ) 支持度描述了和】，这两个项集在所有事务中同时出现的概率。 2 置信度( c o n f i d e n c e ) 规则j y 在事务集中的置信度( c o n f i d e n c e ) 是指同时包含x 和y 的事务数 与包含的事务数之比，它用来衡量关联规则的可信程度。记为 c o 研出h c e ( z jj ，) ，即： c o 够出”卯( x = y ) = i r ：x uy 7 1 ，r d 1 小r ：x r ，r d ) i ：! 塑旦! ! ! 墨! 兰! s u p p d ，f ( x ) 公式( 2 - 4 ) 通常用户根据挖掘需要指定的最小置信度记为m i n c o n 矗d e n c e 。 3 期望置信度( e x p e c t e dc o n f i d e n c e ) 设事务集d 中有e 的事务支持项目集r ，e 称为关联规则x j y 的期望 置信度。期望置信度描述了在没有任何条件影响时，物品l ，在所有事务中出现的 概率有多大。即： e x p p c f 耐妒如”c p ( x j y ) = s u p p o 一( 1 ，) 公式( 2 5 ) 4 ，兴趣度( i n t e r e s t ) 兴趣度是景信度与期望置信度的比值，即：置信度期望置信度。兴趣度又 叫做提升度( l i 、相关度( c o 盯e l a t i o n ) 。兴趣度描述项目集x 的出现对项目集y 的出现有多大的影响。因为项目集y 在所有事务中出现的概率是期望置信度：而 物品集l ，在有项目集x 出现的事务中出现的概率是置信度，置信度对期望置信 度的比值反映了在加入“项目集x 出现的这个条件后，项目集】，的出现概率发生 了多大的变化。 8 硕士学位论文 第二章关联规则理论与经典算法研究 i n t 盯酗“x j y 产五i 蓑暑岌等薹：；：；未丽 公式q ， s u p p d 玎 五) s u d p d r ，( 。 般情况，有用的关联规则的兴趣度都应该大于l ，只有关联规则的置信度 大于期望可信度，才说明x 的出现对y 的出现有促进作用，也说明了它们之间 的某种程度的相关性。给定一个事务集d ，挖掘关联规则的问题就是产生支持 度和置信度分别大于用户事先给定的最小支持度( r n j i l s u p p o n ) 和最小置信度 ( m i n c o n 醐e n c e ) 的关联规则。 支持度、置信度、期望置信度和兴趣度构成了关联规则的四个评价度量标 准。其中支持度和置信度能够比较直观地描述关联规则的性质。从关联规则定 义可以看出，任意绘出事务中的两个项目集，它们之间都存在关联规则，只不 过属性值有所不同。如果不考虑关联规则的支持度和置信度，那么在事务数据 库中可以发现无穷多的关联规则。事实上，人们一般只对满足一定的支持度和 置信度的关联规则感兴趣。因此，为了发现有意义的关联规则，需要给定两个 阈值：最小支持度和最小置信度。 如果s u p p d ( x l ，) m i n s u p p d ，且c d 研如甩c e ( xjy ) m i n c d 够如月础，称关联规则葛y 为强规则，否则称关联规则x j y 为弱规 则。 用尸( x ) 表示事务中出现项目集z 的概率，尸( y ) 表示事务中出现项目集j ， 的概率，尸( ，i 卫) 表示在出现物品集x 的事务中，出现物品集l ，的概率，则以 上四个参数可用公式表示，见表2 1 “。 表2 一l 关联规则的概率表示 名称描述公式 支持度( s u p p o 哟 物品集z 、y 同时出现的概率 尸( z u y ) 置信度( c o n f i d e n c e )物品集x 出现时。j ，出现的概率p ( r f 石) 期望置信度 物品集y 出现的概率p ( y ) ( e x p e c t e dc o n f i d e n c e ) 兴趣度( i n t e r 。s t )置信度与期望置信度之比p ( yj 爿) 尸( y ) 2 1 3 关联规则的分类 可以将关联规则按不同的情况进行分类： l 。基于规则中处理的变量的类别，关联规则可以分为布尔型关联规则和数 值型关联规则。 如果考虑的是项存不存在，则它是布尔型关联规则。布尔型关联规则处理 的值都是离散的、种类化的。如果考虑的是量化的项或属性之间的关联，则是 9 硕士学位论文第二章关联规则理论与经典算法研究 数值型关联规则。 例如： 性别= “女”j 职业= “秘书”，是布尔型关联规则； 性别= “女”j 收入= “2 3 0 0 ”，涉及的收入是数值类型，是一个数值型关 联规则。 2 基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。 在单层的关联规则中，所有的变量都没有涉及不同抽象层的项或属性；而 在多层的关联规则中，对数据的多层性已经进行了充分的考虑。 例如： b u y ( x ，“台式机”) j b u y ( x ，“打印机”) ，是一个购买层次上的单层关联 规9 l i j ： b u y ( x ，“台式机) j b u y ( z ，“s o n y 打印机”) ，是一个较高层次和细节 层次之间的多层关联规则，其中s o n y 打印机是打印机类别中的一个细化子类别。 3 基于规则中涉及到的数据的维数，关联规则可以分为单维关联规则和多 维关联规则。 若规则只涉及到数据的一个维，则它是单维关联规则；如用户购买的物品： 若规则要处理的数据涉及多个维，则它是多维关联规则。换一句话说，单维关 联规则是处理单个属性中的某些关系：多维关联规则是处理多个属性之间的某 些关系。 例如： b u “x ，t c 啤酒”) jb u y ( x ，“尿布”) ，这条规则只涉及到用户的购买行 为，是购买维上的关联规则； 性别；“女”j 职业= “秘书”，这条规则就涉及到“性别”和“职业”两个 字段的信息，是两个维上的关联规则。 4 根据关联规则是否考虑时间因素，关联规则可以分为简单关联和序列关 联。 简单关联规则不考虑数据项之问的时间关系，默认所有的关联都是发生在 相同的时间维度上；序列模式关联则充分考虑时间的先后顺序，挖掘出时间维 度上的频繁序列。 例如： b u y ( z ，“计算机”) jb u y ( x ，“杀毒软件”) ，这是一个简单关联规则， 它不考虑客户何时购买以上两种产品； b u y ( x ，“计算机”) j 3 个月后b u y ( x ，“杀毒软件7 ) ，这是序列关联， 1 0 硕士学位论文 第二章关联规则理论与经典算法研究 购买软件的行为发生在初次购买的三个月后。 2 2 关联规则挖掘问题的分解 关联规则挖掘的任务就是要挖掘出d 中所有的强规则。强规则xjy 对应 的项目集( xu y ) 必定是频繁项目集( 由公式( 2 3 ) 和定义2 5 可知) ，由定理2 1 和公式2 4 可知：频繁项目集( x uy ) 导出的关联规则x j l ，的置信度可由 频繁项目集和( xu y ) 的支持度计算。因此，可以把关联规则划分为两个 子问题”。： 1 根据最小支持度找出数据集d 中的所有频繁项目集； 2 根据频繁项目集和最小置信度产生关联规则。 第一个子问题的任务是迅速高效地找出d 中全部频繁项目集，它是关联规 则挖掘的中心问题，是衡量关联规则挖掘算法的标准，目前大多数关联规则挖 掘问题的研究就是针对第一个子问题展开的；第二个子问题相对简单。 2 2 1 根据频繁项目集产生强关联规则 强关联规则的产生过程如下： ( 1 ) 每个频繁项目集厂，产生，的所有非空真子集； ( 2 ) 对于厂的每个非空子集m ，如果型鲍! ! ! 黑l o o m i n c d 移斑h c p ， s u p j ，d ，l t m j 则输出强关联规则“肌等厂一埘”： 推论2 1 盈“：对项目集厂和其子集m 和脚，若m ，则关联规则 研。j 厂一脚。的置信度不可能大于关联规则埘等厂一m 的置信度。 在根据频繁项目集产生强规则时，利用推论可以减少计算量，进一步提高 强规则的产生效率。 2 2 2 关联规则的分析 从关联规则的挖掘过程，可知关联规则的优缺点如下： 1 优点： ( 1 ) 它可以产生清晰有用的结果； ( 2 ) 支持间接数据挖掘； ( 3 ) 可以处理变长的数据； ( 4 ) 它的计算消耗量是可以预见的。 2 缺点： ( 1 ) 当问题变大时，计算量迅速增长； 硕士学位论文 第二章关联规则理论与经典算法研究 ( 2 ) 难以决定正确的数据： ( 3 ) 容易忽略稀有的数据。 2 3 关联规则经典算法分析 a g r a w a l 等人提出的a p r j o r j 算法是最著名、最有影响的关联规则挖掘算法， 它是按项目集从小到大的顺序寻找频繁项集，是布尔关联规则挖掘算法中最成 功的一类算法。它是层次算法的基础，是最典型的层次算法，其核心技术为其 它种类的布尔关联规则算法所广泛采用，所以有必要先对其进行介绍和分析， 以作为后续研究的基础。 2 ，31a p r i o r i 算法的理论基础 a 州d r i 算法使用了定理2 1 中的结论，即频繁项集的向下封闭性。如果项 集是频繁项集，则其所有的子集部是频繁项集；如果是菲频繁项集，贝其 所有的超集( s u p e r s c t ) 都是非频繁项集。该性质可以用来有效地修剪候选项集。 由此，可以采用迭代方式按项目集从小到大的顺序寻找频繁项目集，按这 种方法设计的布尔关联规则算法称为层次算法。设数据集d 中的最大频繁项集 包含的项目数为k ，层次算法在第( 1 s 女k ) 次迭代时先产生所有大小为七的 候选项目集c “然后扫描数据集计算c 。中所有项的支持度，并根据最小支持度 确定所有频繁女项目集，记作丘，即大项集。 为了提高算法效率，一般采用更为简洁的推论对候选项集进行修剪。 推论2 2 “：若x 是一个七一项目集，如果x 是频繁项目集，则石中所有包 含项目数为k 一1 的子集都是频繁项目集， 根据摧论2 2 ，a p r i o r i 算法由频簸( 女一1 ) 一项目集的集合t 一，产生候选项 集的集合c 。，c 。中任何一个候选女一项集中包含项目数为一l 的子集必须包含 在三。中。这样产生的候选七一项目集的集合q 与所有七一频繁项目集的集合。 满足c 。t ，即不可能有频繁七一项目集被漏掉。 2 3 2a p r ；o r i 算法分析 1 生成频繁项目集 第一，事务数据库的事务都以 的形式存储，并且每一个事 务中包括的项都按词典顺序进行排列，即按a 、b 、c 的字母顺序排列a 第二，通过第一遍扫描数据库。生成频繁卜项集。生成的步骤是：( 1 ) 扫描 每一条事务，确定每一个项的支持度：( 2 ) 把事务数据库中每一个项的计数与事 先指定的最小支持度( m i n s u p p d ，f ) 进行比较，保留计数大于最小支持度的项。 硕士学位论文 第二章关联规则理论与经典算法研究 第三，通过频繁( t 1 ) 一项集生成频繁j 】 一项集。生成的步骤是：( 1 ) 连接步。 假定生成了频繁( 七一1 ) 一项集，则通过频繁( t 一1 ) 一项集的自连接生成侯选的频 繁七一项集。( 2 ) 剪枝步。对候选集进行修剪，候选七一项集的子集必须包含在频 繁( 一1 ) 项集中；( 3 ) 确定候选| 】 一项集的支持度。将所有支持度大于用户给定 的最小支持度的七一项集加入频繁七一项集的集合中。 2 生成关联规则 如果给定了一个频繁集y = “，f ：，) ，j 】 2 ，f ，f ，只需产生包含集合 0 f ：，屯 中的项的所有规则：j y 。z 和r 都是，中项的一个子集。 通过上面的步骤，可能生成大量的关联规则，所以当规则生成后，需对生 成的规则进行筛选。 ( 1 ) 校验关联规则的置信度，矽如九c 口= s u p p d r f ( j u 】，) s u p p d ( 工) ； 只有那些大于用户给定的最小置信度( m i n 驴如 c p ) 的规则才被保留下来。即： c d 堤，姚一c p m i nc o 研d 叠九c p ( 2 ) 输出关联规则j j y( 支持度，置信度) 。 3 a p r i o r i 算法的表述 算法：a p r i o r i 2 8 3 输入：事务数据库d ： 输出：d 中所有强关联规则的集合月。 ( 1 ) 厶= n d 一夕p g “e m _ 1 一抛棚j e r ( d ) 计算d 中的频繁1 - 项集 ( 2 ) 上= o ； ( 3 ) 如r ( 七= 2 ；工女一l m ；七+ + ) ( 4 ) c k = q p ，f d 九一班( - l ，m i n s u p p d m ； ( 5 ) 加r p 口c 彘f ，口九舳c f 如”r 上) ( 6 ) e = s “6 s “( c i ，f ) ； q 、 如r e n c hc a 耐i m ec c c ( 8 )c c d “小+ + ； 计算c 的支持度 ( 9 ) ( 1 0 ) t 砷g l 寄呼s m ； ( 1 1 ) ) 硕士学位论文第二章关联规则理论与经典算法研究 ( 1 2 ) 阳r “m 工= u 。t ；得到频繁世一项集 ( 1 3 ) r = 移船阳耙一，“如犯) ； ( 1 4 ) r p ，泖月( 尺) ； 从频繁( k 一1 ) 一项集中生成候选k 一项集的过程如下： p 阳c p 砒r e 印r f d h 一n ( 厶一1 ：夕叼“p ( 七一1 ) 一j 把p f ； m i n s u p p d ，f ) ( 1 5 ) c = o ； ( 1 6 ) 弦r 。自妇垅j p f 厶 ( 1 7 ) 加，p 口c 打p m s p f 上2 三i l ( 1 8 ) s e l e c t p f 耙朋l ，p 打e m 2 ，p f f p m h ，g 把m i l ( 1 9 )f r o m t lp ，如一jg ( 2 0 )w h e r e p f 阳聊1 = g f 把m l ，p j 旭m 2 = g f f p m 2 ，p f 耙i 一2 = q f 陀m 一2 ( 2 1 )p f 陀珊 一1 g 眈m h ； 对候选足一项集进行剪枝的过程如下： ( 2 2 ) 扣，“盯f ，已，硝s p 船c i 咖 ( 2 3 ) 力阳( 七一1 ) 一s “加哟c 如 ( 2 4 ) 矿( s 正三女一1 ) f 矗p ( 2 5 )如k 陀c 加珊c 2 4 关联规则价值衡量的方法 当我们用关联规则算法得出了一些规则之后，数据挖掘系统如何知道哪些 规则对于用户来说是有用的、有价值的? 这里有两个层面：用户主观层面和系 统客观层面。 2 4 1 系统客观层面 很多的算法都使用“支持度一置信度”的框架，这样的框架有时会产生一 些错误的结果。当事务4 并不蕴涵b 时，利用该算法却可能会识别出4 等口是 有趣的关联规则，也就是说会生成一些虚假的关联规则。可以用一个超市中购 1 4 硕士学位论文 第二章关联规则理论与经典算法研究 买商品的例子来说明这个问题，事务数据库d 见表2 2 胁3 。 表2 2事务数据库d t i d 项目集 t i d 项目集 五 牛奶、面包 瓦 纯净水 瓦 牛奶、面包、纯净水 瓦 纯净水 t 牛奶、纯净水l纯净水 五 牛奶、纯净水 五 纯净水 在给定m i n s u p p o r t = 2 5 和m i n c o n f i d e n c e = 5 0 时，根据a p r i o r i 算法。得到 如下规则：“牛奶面包”( s u p p o r t = 2 5 ，c o n f i d e n c e = 5 0 ) 和“牛奶纯净水” ( s u p p o n = 3 7 5 ，c