（计算机软件与理论专业论文）基于改进的互关联后继树模型的关联规则挖掘.pdf

摘要 摘要 当前，数据挖掘是数据库研究、开发和应用最活跃的分支之，；i 起了学术 界和产业界的广泛关注。而其中关联规则挖掘在商业等领域的成功应j = j ，使其成 为数据挖掘中最成熟、最重要、最活跃的研究内容。而频繁模式的挖掘是关联规 则挖掘的基本步骤。 本文在分析了在频繁模式挖掘领域经典的a 鲫o r i 算法、f p g r o w t h 算法与基 十互关联后继树的i r s t 算法的基础e ，针对频繁模式挖掘的特点对互关联后继 树模型进行了一定的改进，提出了间接红关联后继树簇模型( | l r s t c ) ，并提出 了基于1lr s t c 的频繁模式挖掘算法。通过和f p g r o w t h 算法及原有i r s t 算法 进行全方位的比较，可以发现间接互关联后继树簇模型在频繁项集挖掘任务中在 保留了原有i r s t 算法的优点的同时，又在效率上比原有i r s t 算法取得了很大 的进步，与f p g r o w t h 算法相当。l l r s t c 算法和前两者样都采用无需产生候选 项集，直接构造频繁项集的方法，并都充分利用a p f i o d 性质来提高挖掘效率。 它有其独特的优点：只需要扫描一遍事务库；频繁项的挖掘只局部关联于一棵根 树，内存需求小；算法简单容易理解；对l i r s t c 的更新操作简单易行。同时i l r s t c 模型也是一种索引事务库的通用模型，具有高效支持事务查询的能力。 关键词： 关联规则频繁项集a p r i o r i 算法f p g r o w t h 算法 互关联后继树( i n t e r - r e l e v a n ts u c c e s s i v et r e e s ，i r s t ) 间接互关联后继树簇( i n d i r e c ti n t e r - r e l e v a n ts u c c e s s i v et r e ec l u s t e r s ，i i r s t c ) a b s t r a c t a b s t r a c t n o w ，d a t am i n i n gh a sb e e no n eo ft h em o s ta c t i v es t u d yf i e l do ft h er e s e a r c h ， d e v e l o p m e n ta n da p p l i c a t i o no ft h ed a t a b a s e s b o t ht h ea c a d e m ea n dt h ei n d u s t r y h a v ep a i dm u c ha t t e n t i o nt od a t am i n i n g b e c a u s eo fm a n ys u c c e s s f u lc o m m e r c i a l a p p l i c a t i o n so f t h ea s s o c i a t i o nr u l e sm i n i n g ，i th a sb e c o m et h em o s tm a t u r e ，t h em o s t i m p o r t a n t ，t h em o s ta c t i v ef i l e do f d a t am i n i n gs t u d y m i n i n gf r e q u e n tp a t t e r n si st h e b a s eo ft h ea s s o c i a t i o nr u l e sm i n i n g i nt h i sp a p e r ，w ea n a l y s es o m ef e q u e n tp a u e m sm i n i n ga l g o r i t h m s ，s u c ha st h e c l a s s i c a la p r i o r ia l g o r i t h m ，f p g r o w t ha l g o r i t h ma n di r s ta l g o r i t h mb a s e do ni r s t a c c o r d i n gt ot h ec h a r a c t e r i s t i c so ft r a n s a c t i o nd a t a b a s e s ，w ea m e l i o r a t ea n dd e v e l o p i r s tm o d e l ，g i v eo u tt h ei n d i r e c ti n t e r - r e l e v a n ts u c c e s s i v et r e ec l u s t e r s m o d e l ( i i r s t c ) a n dg i v eo u ta na l g o r i t h m sb a s e do ni i r s t cf o rf r e q u e n tp a t t e r n s m i n i n g c o m p a r e dw i t hf p - g r o w t ha l g o r i t h ma n di r s ta l g o r i t h m ，i tc a nb ef o u n d t h a ti i r s t c a l g o r i t h m n o to n l yk e e p st h em e r i to fi r s t a l g o r i t h m ，b u ta l s oi m p r o v e s t h ee f f i c i e n c yg r e a t l yw h i c hi ss i m i l a rt of p g r o w t ha l g o r i t h m a st h es a m et ot h e o t h e rt w o ，i td o e s n tn e e dt og e n e r a t ec a n d i d a t e s i i r s t ca l g o r i t h mh a si t su n i q u e c h a r a c t e r i s t i c s ：i ts c a n st r a n s a c t i o nd a t a b a s eo n l yo n c e ；t h ep r o c e d u r eo ff r e q u e n t p a t t e mm i n i n g i so n l yb a s e do nar o o tt r e ep a n l ys ot h a tt h er e q u i r e m e n to f m e m o r yi s m o r el e s s ；t h ew h o l ea l g o r i t h mi sv e r ye a s yt ou n d e r s t a n d ；t h eu p d a t eo fi i r s t ci s c o n v e n i e n t a tt h es a m et i m e i i r s t cm o d e li sa l s oac o m m o nm o d e lo fi n d e x t r a n s a c t i o nd a t a b a s ea n dh a st h e c a p a b i l i t y o fq u e r y i n gt r a n s a c t i o n sw i t hh i i g h e f f i c i e n c y k e y w o r d s ： a s s o c i a t i o nr u l e ，f r e q u e n ti t e m s e t s ， i n t e r - r e l e v a n ts u c c e s s i v et r e e s ( i r s t ) i n d i r e c ti n t e r - r e l e v a n ts u c c e s s i v et r e e a p r i o f ia l g o r i t h m ，f p - g r o w t ha l g o r i t h m c l u s t e r s ( i i r s t c ) 4 第章绪论 第一章绪论 1 1 研究背景介绍 在过去的数十年中，人们产生和收集数据的能力已经迅速提高。起作用的因 素包括条形码在大部分商业产品中的广泛应用，许多商务、科学和行政事务的计 算机化，以及由文本和图像扫描平台到卫星遥感系统的数据收集工具的进步。此 外，作为全球信息系统的i n t e m e t 的流行，已经将人们淹没在数据和信息的汪洋 大海中。面对信息社会中数据和数据库的爆炸式增长，人们分析数据和从中提取 有用信息的能力，远远不能满足实际需要。缺乏挖掘数据背后隐藏的知识的手段， 导致了“数据丰富，但信息贫乏”的现象。 虽然目前的数据库系统( d b m s ) 可以高效地实现数据的录入、查询、统计 和维护等功能，但不能发现数据中存在的关联和规则也不能根据现有的数据预 测未来的发展趋势。所以，迫切需要一种能够自动地把数据转换成有用信息和知 识的技术和t 具。 电子数据处理的初期，人们就试图通过某些方法来实现自动决策支持，当时 机器学习成为人们关心的焦点。机器学习的过程就是将一些已知的并已被成功解 决的问题作为范例输入计算机，机器通过学习这些范例总结并生成相应的规则， 这些规则具有通用性，使用它们可以解决某一类的问题。随后，随着神经网络技 术的形成和发展，人们的注意力转向知识工程，知识丁程不同于机器学习那样给 计算机输入范例，让它生成出规则，而是直接给计算机输入己被代码化的规则， 而计算机是通过使用这些规则来解决某些问题。专家系统就是这种方法所得到的 成果，但它有投资大、效果不甚理想等不足。8 0 年代人们又在新的神经网络理 论的指导下，重新回到机器学习的方法上，并将其成果应用于处理大型商业数据 库。 需求是发展之母。用数据库管理系统来存储数据，用机器学习的方法来分析 数据，挖掘大量数据背后的知识，这两者的结合促成了数据库中的知识发现 f k d d ：k n o w l e d g ed i s c o v e r yi nd a t a b a s e s ) 的产生。1 9 8 9 年9 月在美国底特律召 丌的第1 1 届国际人工智能联合会议的专题讨论会上首次出现k d d 这个术语。 数据库中的知识发现是一门交叉性学科，涉及到机器学习、模式识别、统计学、 智能数据库、知识获取、数据可视化、高性能计算、专家系统等多个领域。从数 据库中发现出来的知识可以用在信息管理、过程控制、科学研究、决策支持等许 多方面。 第章绪论 1 1 1 数据挖掘 冈为k d d 涉及内容极为广泛，理论和技术难度很大，从而针对大型数据库 的k d d 技术一时还难以满足应用需要。于是1 9 9 5 年的( 美) 计算机学会( a c m ) 会议提出了数据挖掘( d a t a m i n i n g ) 概念，它形象地把大型数据库看成是存放有 价值信息的矿藏，通过有效的知识发现技术，从中挖掘或开采出有用的信息。 数据挖掘是k d d 中最核- t l , 的部分，是采用机器学习、统计等方法进行知识 学习的阶段。数据挖掘算法的好坏将直接影响到所发现知识的好坏。目前大多数 的研究都集中在数据挖掘算法和应用上。人们往往不严格区分数据挖掘和数据库 中的知识发现，把两者混淆使用。一般在科研领域中称为k d d ，而在工程领域 则称为数据挖掘。 数据挖掘技术是人们长期对数据库技术进行研究和开发的结果。起初各种商 业数据是存储在计算机的数据库中的，然后发展到可对数据库进行查询和访问， 进而发展到对数据库的即时遍历。数据挖掘使数据库技术进入了个更高级的阶 段，它不仅能对过去的数据进行查询和遍历，并且能够找出过去数据之间的潜在 联系，从而促进信息的传递。现在数据挖掘技术在商业应用巾已经可以马上投入 使用，因为对这种技术进行支持的三种基础技术已经发展成熟，它们是： 海量数据搜集 强大的多处理器计算机 数据挖掘算法 商业数据库现在正在以一个空前的速度增长，并且数据仓库正在广泛地应用 于各种行业：对计算机硬件性能越来越高的要求，也可以用现在已经成熟的并行 多处理机的技术来满足；另外数据挖掘算法经过了这l o 多年的发展也已经成为 种成熟，稳定，且易于理解和操作的技术。 从商业数据到商业信息的进化过程中，每一步前进都是建立在上一步的基础 上的，见表1 1 。从表1 1 中我们可以看到，第四步进化是革命性的，因为从用 户的角度来看，这一阶段的数据库技术已经可以快速地回答商业上的很多问题 了。 第一章绪论 进化阶段商业问题支持技术 产品厂家产品特点 数据搜集 “过去五年中我 计算机、磁带和磁 提供历史性 的总收入是多i b m 、c d c的、静态的 ( 6 0 年代)盘 少? ” 数据信息 数据访问 “在新英格兰的 关系数据库在记录级提 分部去年三月的 ( r d b m s ) ，结构 o r a c l e 、s y b a s e 、 供历史性 ( 8 0 年代)化查询语言( s q l ) ， i n f o r m i x 、i b m 、 的、动态数 销售额是多少? ”m i e r o s o r o d b c据信息 “在新英格兰的 在各种层次 数据仓库分部去年三月的联机分析处理p i l o t 、c o m s h a r e 、 上提供回溯 决策支持销售额是多少?( o l a p ) 、多维数a r b o r 、c o g n o s 、 的、动态的 。( 9 0 年代)波士顿据此可得据库、数据仓库m i c r o s t r a t e g y 数据信息 出什么结论? ” 数据挖掘 “下个月波士顿高级算法、多处理p i l o t 、l o c k h e e d 、 提供预测性 的销售会怎么器计算机、海量数i b m 、s g i 、其他 i 正在流行)哟信息 样? 为什么? ”据库初创公司 表1 1 数据挖掘的进化历程。 数据挖掘的核心模块技术历经了数十年的发展其中包括数理统计、人工智 能、机器学刊。今天，这些成熟的技术，加上高性能的关系数据库引擎以及广泛 的数据集成，让数据挖掘技术在当前的数据仓库环境中进入了实用的阶段。 数据挖掘的定义就是从大量的、不完全的、有噪声的、模糊的、随机的实 际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息 和知识的过程。 这个定义包括好几层含义：数据源必须是真实的、大量的、含噪声的；发 现的是用户感兴趣的知识；发现的知识要可接受、可理解，可运用：并不要求发 现放之四海皆准的知识，仅支持特定的发现问题。 数据挖掘的主要过程包括：确定业务对象清晰地定义出业务问题，认清 数据挖掘的目的是数据挖掘的重要一步：数据准备数据的选择、数据的预处 理、数据的转换：数据挖掘对所得到的经过转换的数据进行挖掘；结果分析 解释并评估结果；知识的同化将分析所得到的知识集成到、i k 务信息系统 的组织结构中去。 一般把知识表示成模式( p a t t e r n ) ，所谓模式是个用语言l 表示的表达 第一章绪沦 式e ，它可用来描述数据集f 中数据的特性，e 所描述的数据是集合f 的一个子 集f b ，它比枚举所有f e 中元素更简单。例如，“如果一个人的年龄在5 1 0 岁之 间，则他是一个儿童”可称之为一个模式，而“如果一个人的年龄是5 、6 、7 、 8 、9 或l o 岁，则他是一个儿童”就不能称之为一个模式。 数据挖掘功能用丁i 指定数据挖掘任务中要找的模式类型。数据挖掘任务散 u t 分为两类：描述和预测。描述性挖掘任务刻厕数据库中数据的一般特性。预测 性挖掘任务在当前数据上进行推断，以进行预测。 数据挖掘功能以及它们口j 以发现的模式类型有如下六种： 1 关联分析 关联分析是从数据库中发现知识的一类重要方法。若两个或多个数据项的取 值之间蕈复出现且概率很高时，就存在某种关联，可以建立起这些数据项的关联 规则。例如，买面包的顾客有9 0 的人还买牛奶，这是一条关联规则。若商店 中将面包和牛奶放在一起销售，将会提高它们的销量。 2 时序模式 通过时问序列搜索出重复发生概率较高的模式。这里强调的是时间序列的影 响。例如，在所有购买了激光打印机的人中，半年后8 0 的人再购买新硒鼓， 2 0 的人用旧硒鼓装碳粉；在所有购买了彩色电视机的人巾，三个月内有6 0 的人再购买了d v d 机。 3 聚类 数据库中的数据可以划分为一系列有意义的予集，即类。在同一类别中，个 体之问的距离较小，而不同类别的个体之间的距离偏大。聚类增强了人们对客观 现实的认识，即通过聚类建立宏观概念。例如鸡、鸭、鹅等都属于家禽。 4 分类 分类是找出一个类别的概念描述，它代表了这类数据的整体信息，即该类的 内涵插述。该模式能把数据库中的元组映射到给定类别中的某一个。类的内涵描 述分为：特征描述和辨别性描述。前者是对类中对象的共同特征的描述，后者则 是对两个或多个类之f 白j 的区别的描述。 5 偏差检测 数据库中的数据存在很多异常情况。从数据分析中发现这些异常情况也是很 重要的，应引起人们对它们更多的注意。偏差包括很多有用的知识，例如分类中 的反常实例、模式的例外、观察结果对模型预测的偏差与量值随时间的变化等等。 6 预测 预测是利用历史数据找出规律，建立模型，并用此模型来预测未米数据的种 类、特征等。典型的方法是回归分析，即利用大量的历史数据，以时间为变量建 第一章绪论 立线性或非线性到归方程。预测时，只要输入任意的时间值，通过列归方程就可 求出该时间的状态。 综上所述，数据挖掘是门交义学科，它把人们对数据的应用从低层次的简 单查询，提升到从数据中挖掘知识，提供决策支持。在这种需求牵引下，汇聚了 不同领域的研究者，尤其是数据库技术、人工智能技术、数理统计、可视化技术、 并行计算等方面的学者和_ t 程技术人员，投身到数据挖掘这一新兴的研究领域， 形成新的技术热点。 1 1 2 关联规则挖掘 关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。随着大量数 据不停地收集和存储，许多业界人十对于从他们的数据库中挖掘关联规则越来越 感必趣。从大量商务事务记录中发现有趣的关联关系，可以帮助许多商务决策的 制定，如分类设计、交叉购物和贱卖分析。 关联规则挖掘的。个典型例子是购物篮分析。该过程通过发现顾客放入其购 物篮中不同商品之间的联系，分析顾客的购买习惯。通过了解哪些商品频繁地被 顾客同时购买，这种关联的发现可以帮助零售商制定营销策略。例如，在同一次 去超级市场，如果顾客购买牛奶，他也购买面包( 和什么类型的面包) 的可能性 有多大? 通过帮助零售商有选择地经销和安排货架，这种信息可以引导销售。例 如，将牛奶和面包尽可能放近一些，可以进一步刺激一次去商店同时购买这些商 品。 关联规则挖掘技术目前在商业上已经有不少成功的范例。其实在日常生活中 我们也可以看到许多关联规则挖掘的应用。例如，如果你在肯德基或者麦当劳等 快餐店购买了一份薯条时，店员都会问你要不要再来一杯可乐，这是冈为店员们 在长期的t 作巾逐渐发现了“买薯条的人通常都会买一杯可乐”这条关联规则的 缘故。 正是冈为关联规则挖掘在商业等领域的成功应用，使得对关联规则挖掘的研 究已经成为数据挖掘领域中最成熟、最重要、最活跃的研究内容。 1 2 研究现状 自从数据库中知识发现( k d d ) 一词首次出现在1 9 8 9 年举行的第十一届国 际联合人t 智能学术会议上以来，到目前为止，由美国人工智能协会主办的k d d 国际研讨会已经召开了1 2 次，规模也由原来的专题讨论会发展到国际学术大会， 研究重点也逐渐从发现方法转向系统应用，注重多种发现策略和技术的集成，以 第一章绪论 及多种学科之间的相互渗透。1 9 9 9 年，距太地区在北京召j 1 的第三届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 年出版rk d d 技术专刊。并行计算、计算机网络和信息工程等其 他领域的国际学会、学刊也把数据挖掘和知识发现列为专题和专刊讨论甚至到 了脍炙人口的程度。 此外，在i n t e m e t 上还有不少k d d 电子出版物，其中以半月刊k n o w l e a g e d i s c o v e r yn u g g e t s ( h t t p ：w w w k d n u g g e t s c o r n s u b s c r i b e h t m l ) 最为权威。在网上 还有许多自由论坛，如d me m a i lc l u b 等。至于数据挖掘书籍，可以在任意一家 汁算机书店找到十多本。目前，世界上比较有影响的典型数据挖掘系统有：s a s 公司的e n t e r p r i s em i n e r 、i b m 公司的i n t e l l i g e n tm i n e r 、s g i 公司的s e t m i n e r 、 s p s s 公司的c l e m e n t i n e 、s y b a s e 公司的w a r e h o u s es t u d i o 、r u l e q u e s tr e s e a r c h 公司的s e e 5 、还有c o v e r s t o r y 、e x p l o r a 、k n o w l e d g ed i s c o v e r yw o r k b e n c h 、 d b m i n e r 、q u e s t 等。 在关联规则挖掘研究领域，a g r a w a i 等在1 9 9 3 年首先在文献 1 】中提出了挖 搁顾客交易数据库中项集间的关联规则问题，并在文献 2 】中提出了著名的 a p r i o r l 算法，其核心方法是基于频繁项集理论的递推方法。 以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。他们的丁作 包括对a p r i o r i 算法进行优化，如使用h a s h 表( 3 】) 、事务压缩技术( 3 ) 、 划分技术( 4 】) 、选样方法( 【5 】) 、动态项集计数( 6 】) 等技术以提高算法挖 捌规则的效率。 随后也有独立于a g r a w a i 的频繁项集方法的1 _ _ = 作，以克服a p r i o r i 方法的一 些缺陷，探索挖掘关联规则的新方法。其中最著名的就是j i a w e ih a n 等人提出 的一种基于f p t r e e 的关联规则挖掘算法f p g r o e t h 7 ，它采取“分而治之” 的策略，将提供频繁项集的数据库压缩成一颗频繁模式树f p - t r e e ，但是仍然保 留项集关联信息，然后将这种压缩后的数据库分成一组条件数据库并分别挖掘 每个数据库。理论和实验表明该算法优于a p r i o r i 算法。 互关联后继树( i n t e r - r e l e v a n ts u c c e s s i v et r e e s ，i r s t ) 是根据序列字符的 有序性和冗余性而提出的一种新型的海量全文存储、索引模型 8 】，它最早用于 全文数据库存储和索引，后来被应用到关联规则挖掘上，取得了良好的效果 9 1 。 i r s t 算法同样不需要多次扫描数据库而直接构造频繁项集，也充分利用a p r i o r i 性质来提高挖掘效率。但是实验表明它与f p g r o w t h 算法相比在效率上有比较明 显的差距。 0 第章绪论 1 3 本文的研究内容 如前所述，国内外已对关联规则挖拥有了相当的研究并提出了比较成熟的算 法。而本文在对现有关联规则挖掘算法的分析基础上，针对关联规则挖掘的特性 对互关联后继树( i r s t ) 模型进行了改进，我们将改进后的互关联后继树模型 称为间接互关联后继树簇模型( i n d i r e c ti n t e r - r e l e v a n ts u c c e s s i v et r e e c l u s t e r s ) ，简记为i i r s t c 。它保留了原有i r s t 的优点，但更适合表示关联规 则挖掘的事务数据库。我们提出利用i i r s t c 模型进行关联规则挖掘的算法，并 且与不需要产生候选集而直接产生频繁模式的i r s t 算法与f p g r o w t h 算法进行 比较，实验表明利用改进后的互关联后继树模型在产生频繁模式的效率与 f p g r o f c h 算法相当甚至更高，比原有i r s t 算法的效率有显著提高。 1 4 论文结构 本文共分为六章，第一章总体介绍数据挖掘的兴起和国内外对关联规则挖掘 进行的研究，论述了本论文的研究背景、研究现状和研究内容。第二章介绍一些 关联规则的基本知识，和著名的关联规则挖掘算法经典的a p f i o f i 算法和不 需要产生候选集而直接产生频繁模式的f p g r o w t l l 算法。第三章主要介绍互关联 后继树( i r s t ) 的基本概念以及利用互关联后继树模型进行关联规则挖掘的 | r s t 算法。第四章具体介绍针对关联规则挖掘而改进的互关联后继树模型 间接互关联后继树簇( i i r s t c ) 的基本概念以及用i i r s t c 产生频繁模式的算 法。第五章将i i r s t c 算法与f p g r o w t h 算法和i r s t 算法进行了诸方面的详细 的比较。第六章是一个总结，总结本文的1 二作并展望未来的研究方向。文后是参 考文献和致谢。 第。章关联规咀l 挖掘综述 第二章关联规则挖掘综述 关联规则是发现事务数据库中不同商品( 项) 之间的联系，这些规则找出顾 客购买行为模式如购买了某商品对购买其他商品的影响。发现这样的规则可 以应用r 商品货架设计、货存安排以及根据购买模式对用户进行分类。现实中， 这样的例子很多。最典型的例如超级市场利用前端收款机收集并存储了大量的售 货数据，这些数据是一条条的购买事务记录，每条记录存储了事务处理时间，顾 客购买的物品、物品的数量及金额等。这些数据中常常隐含形式如下的关联规则： 在购买铁锤的顾客当中，有7 0 的人同时购买了铁钉。这些关联规则很有价值， 商场管理人员可以根据这些关联规则更好地规划商场，如把铁锤和铁钉这样的商 品摆放在一起，能够促进销售。 有些数据不像售货数据那样很容易就能看出一个事务是许多物品的集合，但 稍微转换f 思考角度，仍然可以像售货数据一样处理。比如人寿保险，一份保 甲就是一个事务。保险公到在接受保险前，往往需要记录投保人详尽的信息有 时还要到医院做身体检查。保单上记录有投保人的年龄、性别、健康状况、 二作 单位、t 作地址、工资水平等。这些投保人的个人信息就可以看作事务中的物品。 通过分析这些数据，可以得到类似以下这样的关联规则：年龄在4 0 岁以上，工 作在a 区的投保人当中，有4 5 的人曾经向保险公司索赔过。在这条规则中， “年龄在4 0 岁以上”是物品甲，“工作在a 区”是物品乙，“向保险公司索赔过” 则是物品丙。可以看出来，a 区可能污染比较严重，环境比较差，导致工作在 该区的人健康状况不好，索赔率也相对比较高。 2 1 关联规则的基本概念 设卜t ，2 ，_ ) 是所有项的集合。设任务相关的数据d 是数据库事务的集 合，其中每个事务t 是项的集合并且t i 。每一个事务t 都有一个唯一的标识： t i d 。如果项集合x c _ i 且x c _ t ，我们就说事务t 包含x 。 一个关联规则就是形如x j y 的蕴涵式，其中x c i y c l 并且x n y 0 。规则 x j y 在事务数据库d 中的支持度( s u p p o r t ) 是事务集中包含x 和y 的事务数 与所有事务数之比，记为s u p p o r t ( x j y ) ，它是概率p ( x u y ) ，即 s u p p o r t ( x j y ) j t ：x u y t ，t e d v i d ) - - - - p ( x u y ) 规则x j y 在事务集中的置信度( c o n f i d e n c e ) 是指包含x 和y 的事务数与 包含x 的事务数之比，记为c o n f i d e n c e ( x j y ) ，它是条什概率p ( y i x ) ，即 c o n f i d e n c e ( x = y ) = l t ：x u y t ，t e d i l t ：x c _ t ，t e d i = p ( u i x ) 第二章关联规则挖掘综述 同时满足最小支持度闽值( m i n s u p ) 和最小置信度闽值( m i n c o n f ) 的规则 称作强规则。为方便计，一般用0 和1 0 0 之间的值而不是用0 到1 之间的值 表示支持度和置信度。 项的集合称为项集( i t e m s e t ) 。包含k 个项的项集称为项集。项集的出现 频率足包含项集的事务数，简称为项集的频率、支持计数或计数。项集满足最小 支持度m i ns u p ，如果项集的出现频率大于或等于r a i n 与 中事务总数的乘_ s u p d 积。如果项集满足最小支持度，则称它为频繁项集( f r e q u e n ti t e m s e t ) 。频繁缸 项集的集合通常记作厶。 如何由大型数据库挖掘关联规则，通常由两步骤来完成的。 步骤1 ：找出所有频繁项集：根据定义，这些项集出现的频繁性至少和预定 义的最小支持计数一样。 步骤2 ：由频繁项集产生强关联规则：根据定义，这些规则必须满足最小支 持度和最小置信度。 这两个步骤中，第二步最容易。挖掘关联规则的总体性能由第一步决定。 2 2 关联规则挖掘的分类 我们将关联规则按不同的情况进行分类： 1 根据规则中处理的变量的类别，关联规则可以分为布尔型和数值型。 布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的 关系：而数值型关联规则可以和多维关联或多层关联规则结合起来。对数值型字 段进行处理，将其进行动态的分割，或者直接对原始的数据进行处理，当然数值 型关联规则中也可以包含种类变量。 例如：性别= “女”。职业= “秘书”，是布尔型关联规则：。降别一女”= a v g ( 收入) = 2 3 0 0 ，涉及的收入是数值类型，所以是一个数值型关联规则。 2 根据规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。 在中层的关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同 的层次的：而在多层的关联规则中，对数据的多层性进行了充分的考虑。 例如：i b m 台式机= s o n y 打印机，是一个细节数据上的单层关联规则；台 式机= s o n y 打印机，是一个较高层次和细节层次之间的多层关联规则。 3 基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。 在单维的关联规则中，我们只涉及到数据的一个维，如用户购买的物品；而 在多维的关联规则叶1 ，要处理的数据将会涉及多个维。换成另一一句话，单维关联 规则是处理单个属性中的一些关系；多维关联规则是处理多个属性之间的某螳关 系。 第一审关联规则挖掘综述 例如：啤酒= ，尿粕，这条规则只涉及到用户的购买的物品；性别：“女”： 职业= “秘书”这条规则就涉及到两个字段的信息，是两个维上的一r 条关联规则。 2 3 关联规则挖掘的主要算法 在本文中，我们只研究对单维、单层、布尔关联规则的挖捌算法。因为它是 挖掘其它关联规则的基础。这些关联规则挖掘算法主要可以分为两大类：第一类 是a p r i o r i 算法以及它的各种变形，它主要思想是先产生侯选集，从中找出符合 最小支持度的频繁项集，再依据频繁项集产生关联规则：第二类则利用直接快速 的方法来缛到频繁项集，两不用产生候选集的方法。下面我们将分别介绍两类算 法中各自的代表a p r i o r i 算法和f p g r o w t h 算法。 2 3 1 a p r i o r i 算法及其改进 a p r i o r i 算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。算法的 名字基于这样的事实：算法使用频繁项集的先验知识。a p r i o r i 使用一种称作逐 层搜索的迭代方法，女一项集用于探索( 斛1 ) 项集。首先，找出频繁1 一项集的集合。 该集合记作t 。l 用于找频繁2 - 项集的集合l 2 ，而2 用于找l 3 ，如此下去，直 到不能找到频繁项集。找每个“需要一次数据库扫描。 为提高频繁项集逐层产生的效率，一种被称为a p r i o r i 性质的重要性质用于 骶缩搜索空阅。 a p r i o r i 性质：频繁项集的所有非空子集都必须也是频繁的。a p r i o r i 性质基 于如下观察：根据定义，如果项集i 不满足最小支持度r a i ns u p ，则i 不是频繁 的，即p ( 1 ) m i ns u p 。如果项a 添加到i ，则结果项集( 即i u a ) 不可能比i 更 频繁出现。囡此，i u a 也不是频繁的，即p ( i u a ) 2 r a i n s u p ； ( 1 0 ) ( 1 1 ) r e t u r nu i l k ： p r o c e d u r ea p r i o r l g e n 女一i ；m i n _ s u p ) ( 1 ) f o re a c hi t e m s e tl ie l k 1 ( 2 ) f o re a c hi t e m s e th l k - i ( 3 )i f ( 1 1 1 】= f 2 【1 1 ) ( 2 】_ b 【2 ) a ( 1 , k - 2 2 1 2 k 一2 】) 八( “1 ) ，扫描数据库时不再需要它们。 ( 3 ) 划分( 为找候选项集划分数据) ：可以使用划分技术，它只需要两次数据 库扫描，以挖掘频繁项集。它包含两遍。在第一遍，算法将d 中的事务划分为n 个非重叠的部分。如果d 中事务的最小支持度阈值为m i ns u p ，则每个部分的最 小度计数为m i ns u p ( 该部分中事务数) 。对每一部分，找出该部分内的频繁 项集。这些称作局部频繁项集( 1 0 c a lf r e q u e n ti t e m s e t ) 。该过程使用一种特殊的 数据结构，对于每个项集，记录包含项集中项的事务的t i d 。这使得对于女= 1 ， 2 ，找出所有的局部频繁项集只需要扫描一次数据库。局部频繁项集可能不 是整个数据库d 的频繁项集。d 的任何频繁项集必须作为局部频繁项集至少出 现在个部分中。这样，所有的局部频繁项集作为d 的候选项集。所有部分的 频繁项集的集合形成d 的全局候选项集。在第二遍，第二次扫描d ，评估每个 候选的实际支持度，以确定全局频繁项集。每一部分的大小和划分的数目这样确 定，使得每一部分能够放入内存，这样每遍只需要读一次。 f 4 ) 选样( 在给定数据的一个子集挖掘) ：选样方法的基本思想是：选取给定 数据库d 的随机样本s ，然后，在s 而不是在d 中搜索频繁项集。用这种方法， 牺牲了一些精度换取了有效性。样本s 的大小这样选取，使得可以在内存搜索s 中频繁项集；这样，总共只需要扫描一次s 中的事务。由于我们搜索s 中而不 是d 中的频繁项集，我们可能丢失+ 些全局频繁项集。为减少这种可能性，我 们使用比最小支持度低的支持度闽值来找出局部于s 的频繁项集( 极为l 8 ) 。然 后，数据库的其余部分用于计算l 8 中每个项集的实际频繁度。有一种机制可以 用来确定是否所有的频繁项集都包含在l 8 中。如果l s 实际包含了d 中的所有频 第二章关联规则挖掘综述 繁项集，只需要扫描一次d 。否则，可以做第二次扫描，以找l 山在第一次扫描时 遗漏的频繁项集。当效率最为重要h 寸，如计算密集的应用必须在频繁度不同的数 据上运行时，选样方法特别合适。 ( 5 ) 动态项集计数( 在扫描的不同点添加候选项集) ：动态项集训数技术将数 据库划分为标记开始点的块。不想a p r i o r i 仅在每次完整的数据库扫描之前确定 新的候选，在这种变形中，可以存任何开始点添加新的候选项集。该技术动态地 评估已被计数的所有项集的支持度，如果一个项集的所有子集已被确定为频繁 的，则添加它作为新的候选。结果算法需要的数据库扫描比a p f i o f i 少。 正如我们所看到的，在许多情况下，a p r i o r i 的候选产生一检查方法大幅度压 缩了候选项集的大小，并得到很好的性能。然后，它有两种开销u j 能并非是微不 足道的。 ( 1 ) 它可能需要产生大量候选项集。例如，如果由1 0 4 个频繁1 一项集，则a p r i o r i 算法需要产生多达1 0 7 个候选2 一项集，并累计和检鱼它们的频繁性。此外，为发 现长度为1 0 0 的频繁模式，如 a ，a “，a ，。) ，它必须产生多达2 o 约为l o ” 个候选。 ( 2 1 它可能需要重复地扫描数据库，通过模式匹配检查一个很大的候选集合。 对于挖掘长模式尤其如此。 因此目前的研究都不利用这种算法，而采用第二类算法，以直接快速的方法 不产生候选集而直接得到频繁项集。在第二类算法中，f p - g r o w t h 算法 7 】是目 前最快的算法之，且效率最高。实验表明，f p g r o w t h 对不同长度的规则都有 很好的适应性。在挖掘单一维度及布尔值关联规则方面，f p - t f e e 是相当有用的 结构。下面我们将介绍f p g r o w t h 算法并分析它的优缺点。 2 。3 2 f p g r o w t h 算法 f p g r o w t h 称作频繁模式增长( f r e q u e n t - p a t t e r ng r o w t h ) 。算法思想是采取分 治策略，从数据库中抽取出频繁项将其压缩到一棵频繁模式树( f p - t r e e ) ，但仍 保留项集关联信息，然后，将这种压缩后的频繁项集分成一组条件模式库( 一种 特殊类型的投影数据库) ，每一个条件模式库关联一个频繁项集。 f p t r e e 的结构包括一个标识成“n u l l ”的根、一个由频繁项组成的头表和一 组项的前缀子树组成了根的子孙。树中的每个节点包括3 个域：项名( i t e m n a m e ) 、 计数( c o u n t ) 年u 节点链( n o d e l i n k ) 。其中，项名记录了节点所代表的项；计数记录 了树中到达这个节点的路径所代表的事务处理的数目；节点链指向树中下一个同 名节点，如果没有同名节点则指向空。头表中的每条记录包含两个域：项名和节 点链的头。节点链的头指向树中第一个同名的节点。 第二：章关联规则挖掘综述 f p t r e e 中只保存了满足最小支持度的项的集合。所以，首先需要知道哪些 项符合条件，这就是构造头表的工作。对源数据进行第一次扫描得出满足最小支 持度的项并将它们按降序排列在头表中。在得到头表之后，对源数据进行第二次 扫描，对每个事务处理中包含的频繁项按照其在头表中的先后顺序插入到树中。 插入到树中的事务处理的频繁项自然足树的一个路径，但如果树中存在其它与新 路径完全相同或部分相同的路径，j l ! i j 需要将两个路径全部或部分合并。将事务处 理插入到f p t r e e 中的函数i n s e r tt r e e ( p i p ，t ) 是算法中一个非常关键的部分。 所以，f p t r e e 的一个重要属性为：树的大小不会超过它所对应的源数据。由于 在事务处理中通常会存在着大量的共享频繁项。所以树的大小通常比源数据小很 多。 f p t r e e 是个高度压缩的结构，它存储了用于频繁模式挖掘的全部信息由 丁一个以a i 作为前缀的单一路径“a ，一a 2 一a 。”代表了所有那些最大的频集 形式为“a l a 2 一一a k ”( 1 k n ) 的事务处理，所以f p t r e e 远远小于源数据的 大小和在关联规则挖掘过程中产生的候选项集的大小。同时，在频集中的项以支 持度降序排列，支持度越高的项与f p t r e e 的根越近，因此有更多的项是共享的 这进一步保证了f p t r e e 的高度压缩。 f p t r e e 挖掘进行如下：由长度为1 的频繁模式( 初始后缀模式) 开始，构 造它的条件模式基 c o n d i t i o n a lp a r e mb a s e ，一个“子数据库”，由f p t r e e 中与 后缀模式一起出现的前缀路径集组成) 。然后，构造它的( 条件) f p t r e e ，并递 归地在该树上进行挖掘。模式增长通过厉缀模式与条件f p t r e e 产生的频繁模式 连接实现。 下面给出详细的f p g r o w t h 算法。 算法2 2 ：f p g r o w t h 算法。使用f p t r e e ，通过模式增长，挖掘频繁模式。 输入：事务数据库d ：最小支持度阈值m i n s u p 输出：频繁模式的完全集 力法： ( 1 ) 按以下步骤构造f p t r e e ： ( a ) 扫描事务数据库d 遍。收集频繁项的集合f 和它们的支持度。把 f 按支持度递减排序，结果记为频繁项表l 。 ( b ) 创建f p t r e e 的根节点，记为t ，并且标记为“n u l l ”。然后对于d 中 的每个