（计算机应用技术专业论文）基于fpgrowth关联规则挖掘算法的研究与应用.pdf

摘要 摘要 关联规则揭示项集间有趣的相联关系，可广泛应用于市场营销、医学、金 融、生物、电信、农业等领域，是数据挖掘的重要研究课题。自1 9 9 3 年r a g r a w a l ， r s d k a n t 首次提出该问题以来，已出现了许多关联规则挖掘算法。 其中最经典的关联规则挖掘算法是a p f i o d 算法和f p g r o w t h 算法，而 f p g r o w t h 算法是当前挖掘频繁项集算法中应用最广，并且不需要产生候选项集 的关联规则挖掘算法。但是f p g r o w t h 算法并不能有效的挖掘大型数据库，并且 时间和空间复杂度较高。为了克服这两处不足，本文对f p g r o w t h 算法进行了改 进，提出了d c f p m i n e 算法。d c f p m i n e 算法首先采用分解数据库的方法，克服 了f p g r o w t h 算法不能在大型数据库中进行有效挖掘的问题；其次，d c f p m i n c 算法在挖掘过程中采用了基于约束子树的方法，提高了算法在时间和空间方面 的效率。实验表明d c f p m i n c 算法无论在时间和空间效率方面，都优于f p g r o w t h 算法。 关键词l 关联规则；a p r i o r i 算法；f p g r o w t h 算法；d c f p m i n e 算法 a b s t r a c t a b s t r a c t m i n i n ga s s o c i a t i o nr u l e sf r o ml a r g ed a t a s e t s ，w h i c hi so n eo f t h em o s ti m p o r t a n t r e s e a r c hf i e l d si nd a t am i n i n g , c a nr e v e a lt h ei n t e r e s t i n gr e l a t i o n s h i p sb e t w e e n i t e m s e t s ，t h e r e f o r ei sw i d e l ya p p l i e dt om a n yf i e l d ss u c ha sm a r k e t i n ga n ds a l e s ， m e d i c i n e ，f i n a n c e ，b i o l o g y , t e l e c o m m u n i c a t i o n s , a g r i c u l t u r e s i n c e1 9 9 3r a g r a w a l a n dr s r i k a r af i r s t l yp r o p o s e dt h ec o n c e p to fa s s o c i a t i o nr u l e s ，al o to fa l g o r i t h m s h a v eb e e nd e v e l o p e df o rm i n i n ga s s o c i a t i o nr u l e s t h em o s tc l a s s i ca s s o c i a t i o nr u l em i n i n ga l g o r i t h m sa l et h ea p r i o r ia l g o r i t h m a n dt h ef p - g r o w t ha l g o r i t h m f p - g r o w t ha l g o r i t h mi so n eo ft h ec u r r e n t l ym o s t p o p u l a ra l g o r i t h m s f o ra s s o c i a t i o nr u l e m i n i n gw i t h o u t c a n d i d a t eg e n e r a t i o n h o w e v e r , f p - g r o w t ha l g o r i t h m c a l ln o tm i n ee f f e c t i v e l yt h e l a r g ed a t a b a s e s ， m o r e o v e r , t h et i m e - c o m p l e x i t ya n dt h es p a c e - c o m p l e x i t yi st oh i g h t oo v e r c o m e t h e s ed r a w b a c k s ，t h i sp a p e rp r o p o s e dt h ed c f p m i n ea l g o r i t h mw h i c hi m p r o v e do n f p g r o w t ha l g o r i t h m f i r s t ，t h ed c f p m i n ea l g o r i t h ma d o p tt h et e c h n o l o g yo f d i v i d i n gt h el a r g ed a t a b a s ei n t om a n ys u b d a t a b a s e ，i tc a no v e r c o m et h eq u e s t i o no f e f f e c t i v em i n el a r g ed a t a b a s e sf o rt h ef p g r o w t ha l g o r i t h m s e c o n d , t h ed c f p m i n e a l g o r i t h ma d o p tt h ec o n s t r a i n e d - t r e et e c h n o l o g yo nm i n i n gp r e e d u r e ，w h i c hc 加 i m p r o v ee f f i c i e n c yo nt h et i m e - c o m p l e x i t ya n d t h es p a c e - c o m p l e x i t y e x p e r i m e n t a l r e s u l t ss h o wt h a tt h ed c f p m i n ea l g o r i t h ma r es u p e r i o rt ot h ef p - g r o w t ha l g o r i t h m b o t hi nt i m ea n ds p a c ee f f i c i e n c y k e yw o r d s ：a s s o c i a t i o nr u l e s ；t h ea p r i o r ia l g o r i t h m ；t h ef p - g r o w t ha l g o r i t h m ；t h e d c f p m i n ea l g o r i t h m 学位论文独创性声明 学位论文独创性声睨 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得直昌太堂或其他教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 学位论文作者签名( 手写) ：缘滂签字日期：砌年月7 日 学位论文版权使用授权书 本学位论文作者完全了解直昌太堂有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权直昌太堂可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 。 等复制手段保存、汇编本学位论文。同时授权中国科学技术信息研究 所将本学位论文收录到中国学位论文全文数据库，并通过网络向 社会公众提供信息服务。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：屎墉 签字日期：少户年j 7 日 导师签名： 刁( 哆、够 签字日期：肋年1 月7e l 第l 章绪论 第1 章绪论 随着信息社会的发展，计算机在商业活动、科学计算和工程设计等领域得 到了越来越广泛的应用，伴随着这些应用的深入，产生了大量的历史数据。这 些历史数据被收集并存储在众多数据库中。随着时间的增长，存储在数据库中 的数据越来越庞大，使得人们在不借助专门的工具下就不能正确的分析、理解 和处理这些历史数据。由于缺乏有效的分析工具，在大部分情况下，这些数据 很难再有被访问和利用的机会，结果，造成存储在众多数据库中的历史数据不 能被开发利用，而仅仅是存储在介质中，人们称这中现象为“数据坟墓一。 在日常决策过程中，由于缺乏从数据库中提取有用知识的工具，人们往往 是根据直觉或经验，而不是基于数据库中信息丰富的数据来做出决策【l 】，因此， 有时做出不够正确决策的可能性大大的增加。然而，保存在众多数据库中的历 史数据蕴含了大量不为人知的、却非常有用的知识和信息，如果能很好的利用 这些有用的知识和信息，对人们的商业活动、科学研究和市场分析的决策可以 起到很好的指导作用。所以，人们迫切需要开发一种能从海量数据中提取有价 值的知识或信息的技术，以支持人们决策活动。正是由于以上原因，产生了数 据挖掘( d a t am i n i n g ) 技术，目前数据挖掘技术在各领域中已得到了广泛的应 用和发展。 1 1 数据挖掘的定义 挖掘( m i n i n g ) 这个单词在英语中的意思是指将矿石或矿物从土中提取出来， 加以冶炼并提取出金属的过程。在信息领域，与此相对应的是数据挖掘这个概 念，数据挖掘是指从存放在数据库、数据仓库或其他信息库中的大量数据中“挖 掘”有趣知识的过程。 数据挖掘从不同的方向有不同的定义，在此指出一种有代表性的定义。数 据挖掘( d a t a m i n i n g ) ：就是从大量数据中获取有效的、新颖的、潜在有用的、 最终可理解的模式的非平凡过程。在许多数据挖掘文献中，数据挖掘常常被视 为数据库中的知识发现( 1 d ) 的同义词。 对数据库进行数据挖掘，目的是提取出其中有价值的信息和知识。这些提 第1 章绪论 取出的信息，除了一般狭义上的数据或信息以外，还包括更加广义意义上的内 容。比如，如果对数据库进行关联规则方面的挖掘，可以得出规则、模式或约 束之类的信息。因此，数据挖掘从功能上以及可以发现的模式上分，包括概念 类描述【2 捌、关联分槲4 - 5 1 、分类和预测睁7 】、聚类分析【删等内容。 数据库中存储的历史数据，大致可分为三大类：从数据来源上分，可分为 工业、农业，商业等领域的数据；从数据的保存形态上分，可分为字符型、多 媒体型数据等；从数据的组织方式上分，可分为结构型、半结构型和非结构型 数据等【1 m 。数据挖掘需要从这些不同类型的数据中挖掘出有用的知识，它必然 涉及到不同领域和学科之间的交叉，因此数据挖掘是一门交叉学科目前，数 据挖掘已引起不同领域的研究人员的关注，尤其是数据库应用方面的研究人员 的关注。 1 2 数据挖掘的基本步骤 在许多数据挖掘文献中，数据挖掘和数据中的知识发现( k d d ) 是同义词， 而在另外一些文献中，数据挖掘被视为k d d 的个基本步骤。在本论文中，取 第一种说法。知识发现( 数据挖掘) 包含以下几个基本步骤或以下步骤的迭代 序列【1 】： 1 ) 数据清理 2 ) 数据集成 3 ) 数据选择 4 ) 数据变换 5 ) 数据挖掘 6 ) 模式评估 7 ) 知识表示 1 3 数据挖掘的主要任务 数据挖掘有下列几种常见的任务，它们分别是数据预处理、关联规则、分 类和预测、聚类分析。下面分别加以介绍【1 0 1 ： 2 第1 章绪论 1 3 1 数据预处理 在进行数据挖掘前，由于所挖掘的数据库中的数据可能包含许多无关的信 息，因些在挖掘过程前，有必要对数据进行数据预处理，以获得需要处理的数 据的总体印象。描述性数据汇总技术可以实现此目地。目前描述性数据汇总技 术可分为均值、中位数、方差值、直方图等。利用这些技术，可以得到数据的 紧凑性描述。数据预处理技术还包括数据泛化，数据泛化是指将数据库中低层 次的数据抽象到高层次的技术。存储在数据库中的原始数据，有时这些数据只 是描述了对象的最原始的基本信息，人们有时希望从高层次上观察这些数据， 此时就要用到数据泛化技术，将原始数据抽象到高层次上。目前有两种数据泛 化技术：它们分别是多维数据分析和面向属性的归纳。下面分别加以介绍。 数据仓库是一种面向主题的、集成的和时变的数据集合，它支持管理部门 的决策。而多维数据分析就是一种数据仓库技术。数据分析技术要用到一些如 求平均值、开方、平方等计算量很大的操作。由于这些操作过于费时，人们将 这些操作结果预先存储在数据库中，这种数据库称为多维数据库。目前有很多 著名的多维分析数据库系统，比如国际商用计算机公司的决策分析工具就使用 了此种技术。 目前数据仓库中一般存储是过去的历史数据，它是一种静态的脱机数据。 为了处理动态的联机数据，人们使用了数据泛化中的另外一种技术面向属 性的归纳。其基本思想是利用s q l 查询语句，查询出用户感兴趣的数据，相比 多维数据分析方法，面向属性的归纳法更直接快捷的得出想要的结果。通过以 上介绍的数据泛化技术，可以将数据库中的原始数据抽象到较高层次，再通过 其它数据挖掘技术，比如关联规则挖掘、分类分析等技术，就可以得到隐藏在 数据中的有用知识。 通过上面的介绍，我们可以得知数据预处理在数据挖掘中是最基本且十分 重要的操作。数据库中的数据通过数据预处理后，在后续的挖掘中才能更有效 的发现数据中隐藏的有用知识。 1 3 2 关联规则 在大型数据库系统中，存储了海量的数据。这些数据可能来商业、科学研 究等应用中。如何从这些海量数据中发现规律，指导人们的生产、生活实践就 很重要了。关联规则挖掘就是这方面的典型应用。关联规则挖掘是指从海量的 3 第1 章绪论 数据中找出数据项之间的联系，并生成它们之间规则的过程。随着关联规则在 相芳领域特别是商业活动中的成功运用，人们对关联规则的挖掘研究越来越 感兴趣。 关联规则挖掘最早是由a g r a w a l 等人在研究超市购物篮分析中提出的，这项 研究是从商品销售的历史数据库中找出顾客的购买习惯，进而指导超市的货架 摆放，促进商品的销售关联规则可以发现数据库中数据项或属性之间的某种 联系，一般这种联系表现出来的特征是某些数据项频繁的同时出现。这种联系 仅仅通过观察数据或数据库的逻辑操作是不能得到的。通过关联规则挖掘得出 的结果可以生成数据项之间的联系公式，这些公式对于人们进行商业活动和市 场决策是非常有用的。 关联规则挖掘可运用到许多不同的领域，目前关联规则挖掘运用的范围越 来越广泛。在信息学科领域，它已引起了数据库、信息检索等领域学者的重视， 在该方向上的研究的成果越来越多。关联规则挖掘生成的结果是一系列的关系 公式，这些公式易于理解并且人们很容易发现数据项之间的关系，因此，关联 规则挖掘越来越引起人们的重视，近年来，关联规则挖掘成为了一个热点问题。 1 3 3 分类和预测 在“数据中的知识发现一的几种任务中，分类是很重要的一部分。分类需 要构造一个模型或分类器来进行预测，通过分类操作，将数据库中的各数据项 映射到各自特定的类别上。除了分类可以进行预测，回归分析也可以达到预测 的效果。通过分类或回归分析操作，人们可以从存储在数据库中的历史数据导 出对特定数据的特定描述，这样就可以预测将来的数据趋势分类和回归分析 处理的数据类型不相同，分类处理的是离散的数据，而回归处理的是连续数据。 分类需要构造分类器，回归分析需要预测器。构造分类器的方法是，首先要有 一个训练样本数据集，将训练样本输入进分类器，根据训练样本的类别标记， 对该样本集的所有样本进行分类，通过这样的处理，可以将具有相同特征的样 本归为一类，并且输出这一类的样本特征。 在分类处理过程中，构造分类器是关键步骤，目前，有三种不同的分类器 评判标准，它们分别是：时间和空间复杂度、模型描述简洁度和预测精确度。 分别对这三种评判标准做简单的介绍。由于分类所用的样本集都是海量的数据 库，因此分类器的时间和空间复杂度是重要的考虑因素，但是，分类器的时间 4 第1 章绪论 和空间复杂度又依赖于其软件和硬件环境；模型描述简洁度一般用于描述型的 分类任务，根据分类任务类型的特点，选定的分类器越简单越蚵：最后君预测 的准确度，它是目前用的最多的一种分类器比较尺度，对构造预测型任务的分 类器，它是效果比较好的一种评价尺度。 需要注意的是，分类的效果与样本数据有很大的关系，有些样本数据的不 相关数据太多，有些样本数据集中存储的数据类型值不统一等等，因此，不能 找到一种普遍适用的方法用于处理各种类型的数据。 1 3 4 聚类分析 在上面1 3 3 节中，构造分类器的样本集是经过类别标定的，与之对应的是， 聚类分析中样本集是未经过标定的，也就是说样本集没有进行分类。分类是通 过标定类别的样本集将样本分成不同的类别，聚类则是根据相似性划分为不同 的类别。划分的结果是使同一类别的数据之间的距离尽可能小，反之，不同类 别的数据之间的距离尽可能的大。 分类是将样本数据集预先进行标定，最后通过分类器的处理得到该样本数 据集中各个类别的详细描述。对于聚类分析，人们一般是将前面得到的分类结 果直接应用于待聚类的样本数据集，对样本数据集进行划分，然后才进行聚类 分析，这样分类和聚类分析方法交叉使用，可以获得更加精确的处理结果。 目前聚类分析有多种技术，根据样本数据集的不同，有神经网络技术、统 计分析技术和机器学习技术三种主要技术。聚类分析主要是利用数据集间的几 何距离对数据进行聚类，这种聚类对有些数据集处理的不是很精确。下面简要 的介绍下上文所述的三种主要聚类技术。 神经网络技术中，自组织神经网络是最常用的技术，它的特点是无监督学 习，目前比较成熟的是多层反馈神经网络技术，利用该技术可以有效的对大型 数据库进行聚类；统计分析技术是一种从全局上考虑的聚类分析技术，它是一 种静态的分析技术，也就是说，它所考察的样本数据集在处理过程中是不能动 态的改变的，通过处理所有的样本数据才能对样本数据集进行聚类划分。因此 这种技术的时间复杂度是非线性的，不适合处理大型数据库，常用的统计分析 技术有模糊聚类、有序聚类等。机器学习技术与神经网络技术类似，它也是一 种无监督或归纳的聚类分析技术，它的特点是利用机器学习算法对没有标记的 样本数据集进行标记以实现数据间的聚类。 5 第1 章绪论 1 4 数据挖掘的研究现状 在许多数据挖掘文献中，数据挖掘中的知识发现( k d d ) 与数据挖掘是同 义词，k d d 最早可以追溯到1 9 8 9 年1 1 月举行的第十一届国际联合人工智能会 议上，这次会议提出了数据中的知识发现这一概念。由于数据挖掘技术在数据 库中发现隐藏知识过程中的重要作用。该技术已引起人们越来越多的重视。目 前为止，已经举办了7 次数据挖掘的国际研讨会，会议规模由原来的专题讨论 发展到国际间的学术大会。比如1 9 9 5 年召开的第一届知识发现与数据挖掘国际 学术大会。 各领域与数据挖掘相关的学术期刊也相继出现，如数据库、人工智能、信 息处理等领域。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 就出版了数据 挖掘技术方面的专刊，当时发表的五篇数据挖掘方面的论文，较全面的论述了 数据挖掘的系统方法论、发现结果的评价以及数据挖掘系统设计的逻辑方法， 代表了当时最新的研究成果。1 9 9 8 年美国的数据挖掘与知识发现协会建立了 a c m s i g m o d 学术组织，该组织专门用于研究在数据库中的知识发现。这些是 国外的研究情况。在国内，数据挖掘的研究机构在主要几所大学也相继建立， 比如清华大学的数据挖掘研究中心，随着数据挖掘技术受到越来越多的重视， 国内其它大学也建立了相关的研究机构。 1 5 数据挖掘未来的研究方向和热点 鉴于数据挖掘技术在知识发现过程中的重要作用，数据挖掘已经成为学者 研究的一个热点问题，本文简要概括下数据挖掘未来的研究方向【l o l ： 1 ) 数据仓库与联机处理系统的集成：联机处理系统( o l a p ) 与数据仓库 相互集成可以提高数据挖掘工作的实用价值。数据仓库集成了o l a p 后，能利用o l a p 中丰富的分析工具，在数据立方体的任何维上进行数 据挖掘，也可以通过数据抽象，达到发现知识的目的。两者结合后，可 以更加有效的发现数据仓库中的知识。 2 ) 数据挖掘过程和结果的可视化：可视化技术在软件方面已经发展的很成 熟，可视化能使用户所见既所得，易于用户的理解因此，未来可视化 是数据挖掘发展的一个方向，通过可视化技术，对交互式数据挖掘尤其 有用。 6 第1 章绪论 3 ) 对复杂的数据进行数据挖掘：当前，主要是在关系数据库和事务数据库 上进行数据挖掘。然而，在现实世界，无组织结构类型的势据占了大部 分，如何从这些非结构化的数据中发现知识就成为数据挖掘中的很重要 的问题。近年来，这方面的研究也相继展开，比如从超文本中进行数据 挖掘。 4 ) 数据挖掘查询语言：近年来开发的数据挖掘系统中，如数据仓库中，出 现了类似于s q l 查询语言的数据挖掘语言，该挖掘语言能实现用户和 系统间的交互，用户通过编写查询语句，可以很方便的得到自己想要的 知识。 5 ) 对文本数据进行挖掘：文本数据是所有数据类型中占有的比例比较多的 一种数据类型，如何对文本数据进行挖掘也是数据挖掘的一个研究方 向，常用的方法有两种，一是基于内容的方法，二是基于协同的方法。 6 ) 可伸缩的数据挖掘方法：数据挖掘所处理的对象是海量历史数据，因此 数据挖掘算法的时间和空间效率就很重要，目前，已出现了很多数据挖 掘算法的改进算法，有些改进算法在时间和空间效率方面有了很大的提 高。 7 ) 对移动数据库进行挖掘：随着信息技术的发展，尤其在移动计算领域( 如 3 g ) 的发展。移动数据库越来越庞大，如何对这种数据库进行挖掘已经 成为一个重要的问题，目前这方面的研究还是刚刚起步，但是它已是数 据挖掘中的一个研究热点。 8 ) 分布式数据挖掘：随着信息社会的发展，人们在各种应用中产生了大量 的数据，这些数据可能存放在不同的数据库中，这些数据库可能同构， 也可能异构，研究如何从这些分布式的数据库中挖掘知识( 即分布式数 据挖掘) 就相当重要了，近年来，发展迅速的云计算就是这方面的典型 例子。 9 ) w e b 数据挖掘：信息社会的发展是伴随着互联网技术的发展而发展起来 的，在互联网中，一项重要的应用即电子商务。如果对w e b 数据进行 挖掘，就能更好的了解客户的需求，设计出满足不同客户的网站，这样， 在激烈的竞争中可以处于有利的地位。 l o ) 数据挖掘技术集成进多种数据库系统：数据库做为数据存储的主要载 体，如果将数据挖掘模块集成进数据库系统，这将对数据挖掘工作将十 7 第1 章绪论 分有利。集成后的系统不论在多维数据分析方面，还是在信息处理方面 都十分方便。目前已出现了这方面的系统，如i b m 的数据仓库系统。 1 1 ) 数据挖掘在不同应用中的研究：数据挖掘最初应用在分析超市顾客习 惯，进而采取相应的货贺摆放，达到提高销售的目的。随着数据挖掘的 研究深入，人们已将数据挖掘应用到不同领域，如金融和军事领域等。 这些领域有着不同的数据结构及特点，因此很难开发出通用的数据挖掘 系统来处理所有领域的应用，所以，未来的研究方向是开发针对不同应 用的数据挖掘系统。 1 2 ) 在隐私数据中进行数据挖掘：随着人们的法律观念的增加，如何在数据 挖掘中保护个人隐私数据就很重要了，此外，在数据挖掘的其他应用中， 保护所挖掘数据的信息安全也成为一个重要的问题，目前这方面的研究 还是刚起步。 1 6 本文的主要工作 本文主要讨论关联规则挖掘算法f p g r o w t h 算法的改进，首先分析f p g r o w t h 算法的缺点，然后根据缺点提出相应的改进方案，最后将相关的改进方法结合， 提出了基于f p g r o w t h 算法的改过算法d c f p m i n e ，具体工作如下： 1 ) 介绍数据挖掘中关联规则挖掘方向的基本概念，对经典的关联规则挖掘 算法a p r i o r i 算法和f p g r o w t h 算法进行详细的分析 2 ) 详细讨论f p g r o w t h 算法的缺陷，给出相应的解决方案，最后提出一种 基于f p g r o w t h 算法的改进算法d c f p m i n e 。 3 ) 通过实验，对比验证d c f p m i n e 算法和经典的f p - g r o w t h 算法。 4 ) 给出d c f p m i n e 算法的一个应用实例； 5 ) 对d c f p m i n e 算法进行总结，最后指出仍需完善的方向 1 7 论文结构 论文结构安排如下。 第l 章绪论 介绍数据挖掘的概念、主要任务及国内外研究现状。 第2 章关联规则及其挖掘算法 s 第1 章绪论 介绍关联规则挖掘的概念、研究现状和关联规则挖掘的经典算法。 第3 章基于f p g r o w t h 算法的关联规则改进算法 分析f p g r o w t h 算法的缺陷，提出一种基于f p g o r w t h 算法的关联规则挖掘改 进算法d c f p m i n e 。 第4 章d c f p m i n e 算法的应用 给出d c f p m i n e 算法的一个应用实例。 第5 章总结与展望 对本文的工作进行总结，并提出了需要完善的地方和进一步的工作展望。 9 第2 章关联规则及其挖掘算法 第2 章关联规则及其挖掘算法 从第一章的讨论可知，数据挖掘有四个主要的研究方向，关联规则挖掘目 前应用的比较广泛，对它的研究成果比较多。关联规则最初由a g r w a l 等人在研 究购物篮分析中提出州一2 1 ，由于它生成的规则简洁易懂，并且在商业数据分析 中得到了成功的应用，因此受到了广大研究人员的重视。 关联规则挖掘有以下两大研究方向：第一是从一维关联规则挖掘发展到多 维关联规则挖掘，比如数据仓库中，对数据立方体从多维上进行数据抽象，然 后进行挖掘。第二是研究改进算法，数据挖掘处理的都是海量数据，因此挖掘 算法的效率很重要，目前，已提出很多关联规则改进算法。 2 1 基本概念和问题描述 关联规则最初用于超市购物篮分析，它通过挖掘事务数据库中数据项之间 的联系，得出哪些数据项频繁的出现，最后根据所挖掘的频繁项导出规则，通 过这些规则，可以得知顾客的购买习惯，据此设计货架中货物的摆放，达到促 销的目的 抽象的数据挖掘定义如下设i = ( i l ，i 2 ，i n ) 是项( i t e m ) 的集合向量待挖 掘的数据集合为d ，数据库中每条记录记为兀它是由项组成，可知7 。c ，。每 条记录都有唯一标识符t i d 。设a 是一个项集，如果a ，则记录r 包含项 集a 。关联规则的一般形式为ajb ，该公式满足下列条件；ac ，bc ， 并且ac - 、b = o 。规则ajb 成立，它的其中一个度量是支持度( s u p p o r t ) s ，s 表示概率p ( au a ) ，即数据库d 中包含au b ( 即同时包含a 和b 二者) 的百 分比。规则ajb 的另一个度量是置信度( c o n f i d e n c e ) c ，c 表示条件概率p ( bi 舢，即数据库d 中包含a 的记录同时也包含b 记录的百分比。用数学公式描述 如下： s u p p o r t ( ajb ) = p ( a l a b ) ( 2 1 ) c o n f i d e n c e ( a j l 5 ) t p ( bla )( 2 2 ) 关联规则挖掘得出的结果是项集，项集即项的集合，如果项集中包含k 个 项，则称该项集为k 项集项集有一个很重要的指标，项集在数据库记录中出 1 0 第2 章关联规则及其挖掘算法 现的频率，如果一个项集出现的频率满足大于或等于最小支持度计数，则称它 为频繁项集。关联规则挖掘就是从数据库d 中频繁项集，然后根据这些频繁项 集得出关联规则公式。由于所挖掘的项集是频繁项集，因此导出的关联规则公 式都满足最小支持度和最小置信度。 由式( 2 2 ) ，可得到 c o n f i d e n c e ( a b ) = p ( bia ) =s u p p o r t ( au b ) 一s u p p o r tc o 删丛垒! 璺 ( 2 3 ) 式( 2 3 ) 表明规则a j b 的置信度容易从a 和a u b 的支持度计数推出。因 此，如果得到a ，b 和a u b 的支持度计数，导出对应的关联规则公式a j b 和 b j a ，并检查它们是否满足给定的最小支持度( m i ns u p p ) 和最小置信度 ( m i n e o n f ) 是很容易的。所以，挖掘关联规则的问题可以归结为挖掘频繁项集。 通过前面介绍的关联规则相关概念的定义，我们可以得出关联规则挖掘分 为两个步骤： 1 ) 挖掘出数据库中的频繁项集：首先根据数据库中数据的特点，选择合适 的关联规则挖掘算法，对数据库进行挖掘，一般来说，得出的结果为频 繁项集的集合。 2 ) 由频繁集导出关联规则：利用第一步产生的频繁项集及其支持度计数， 可以很容易的推导出相关的关联规则公式。 一般来说，步骤二的开销远低于步骤一，因此，关联规则挖掘主要由步骤 一决定。 2 2 关联规则的分类 由上节的讨论可知，关联规则挖掘实际上是频繁模式挖掘，根据以下标准， 频繁模式挖掘有多种分类方法【1 1 ： 1 ) 根据挖掘的模式的完全性分类 给定最小支持度阈值，可以挖掘频繁项集的完全集、闭频繁项集和极大频 繁项集。也可以挖掘被约束的频繁项集( 即满足用户指定的一组约束的频繁项 集) 、近似的频繁项集( 即只推导被挖掘的频繁项集的近似支持度计数) 、接近 匹配的频繁项集( 即与接近或几乎匹配的项集的支持度计数相符合的项集) 、最 频繁的k 个项集( 即对于用户指定的k ，k 个最频繁的项集) 等等。 2 ) 根据规则集所涉及的抽象层分类 第2 章关联规则及其挖掘算法 有些挖掘关联规则的方法可以发现不同的抽象层规则。例如，假定挖掘的 关联规则集包含下面规则： b t g , s ( x , c o m p u t e r ”) j6 垆( x ，”h p p r i n t e r ”) 但4 ) b u y s ( x , 却印一c o m p u t e r 一) jb u y s ( x , h p p r i n t e r 什) r 25 、 其中x 是变量，代表顾客。在规则( 2 4 ) 和规则( 2 5 ) 中，商品抽象在不 同的层次中( 例如，。c o m p u t e r 一在比。l a p t o pc o m p u t e r 一高的抽象层) 。我们称 之为多层关联规则( m u l t i l e v e la s s o c i a t i o nr u l e ) 。反之，如果在给定的规则集中， 规则只涉同一抽象层的项或属性，则称之为单层关联规9 i j j ( s i n g l e 1 e v e la s s o c i a t i o n r o l e ) 。 3 ) 根据规则中涉及的数据维数分类 如果关联规则中的项或属性只涉及一个维，则它是单维关联规则 ( s i n g l e - d i m e n s i o n a la s s o c i a t i o nr o l e ) 。 b u y s ( x , c o m p u t e r ”) j6 垆( x ，”a n t i v i r u s s o f t w a r e ”) ( 2 6 ) 规则( 2 6 ) 就是一个单维关联规则，因为它只涉及一个维b u y s 。 如果规则涉及两个或多个维，如涉及维a g e ，i n c o m e 和b u y s ，则它是多维关 联规则( 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 nr u l e ) 。式( 2 7 ) 是一个多维关联规则的例 子 a g e ( x , “3 0 3 9 竹) i n c o m e ( x , ”4 2 k 4 8 k 什) jb u y s ( x , h i g hr e s o l u t i o n t v ”) f 27 、 4 ) 根据规则中所处理的值类型 如果规则考虑的关联为项是否出现，则它是布尔关联规则( b o o l e a n a s s o c i a t i o nr o l e ) 规则( 2 4 ) 是由购物篮分析得到的布尔关联规则。 描述量化的项或属性之间的关联称之为量化关联规则( q u a n t i t a t i v e a s s o c i a t i o nr u l e ) 。在这种规则中，项或属性的量化值分为区间。规则( 2 7 ) 也 可以看作量化关联规则。 5 ) 根据所挖掘的模式类型分类 从不同类型的数据集中可以挖掘不同类型的频繁模式如从事务或关系数 据集挖掘频繁项集称为频繁项集挖掘，从序列数据集中搜索频繁子序列称为序 列模式挖掘在结构化数据集中搜索频繁子结构称为结构模式挖掘。 1 2 第2 章关联规则及其挖掘算法 2 3 关联规则的研究现状 数据挖掘四种主要任务中，关联规则挖掘是应用的最广泛的数据挖掘技术。 关联规则这一概念最早是由a g r a w a l 在s i g m o d 9 3 国际会议上提出的，它主要 是找出数据库中数据项之间的联系。目前，关联规则挖掘已经成功的用于分析 商业数据中，并且已经推广到其它领域的数据分析当中。 当前，关联规则挖掘常见的研究方向有：层次挖掘算法【l3 1 、增量式挖掘算 法【1 4 】、基于概念格的关联规则挖掘算法【1 5 1 6 】等等。下面简要的对这些算法进行 介绍。层次挖掘算法的核心思想是将挖掘过程分成几个层次，先对每个层次进 行挖掘，然后将各层挖掘的结果进行整合，最后得出总的结果。这是最常见的 关联规则挖掘算法。这类算法中比较有代表性的是a g a r w a l 等人提出的a p r i o r i 算法，p a r k 等人提出的d h p 算法f 1 7 1 剐，t o i v o n e n 提出的抽样算法【1 9 1 ，以及h a n 等人提出的f p g r o w t h 算法1 2 0 - 2 8 1 。这些层次挖掘算法中，最著名的是a p r i o r i 算 法和f p g r o w t h 算法。由于关联挖掘算法所处理的数据量很大，当数据库大小发 生改变，如果利用层次挖掘算法，就需要重新进行挖掘，这样挖掘效率低下， 在此情况下，研究人员开发出增量式挖掘算法，当数据库大小发生改变时，该 算法只需要对新增加的数据进行挖掘，而不必重新对整个数据库进行挖掘。典 型的算法是c h e n g 等人提出的f u p 和f u p 2 算法。基于概念格的关联规则挖掘 算法是概念格这一概念在数据领域的推广应用。目前，已取得了丰硕的研究成 果。比如p e t k o 等人提出的基于概念格的频繁闭项集挖掘算法。 关联规则挖掘技术除了以上介绍的三种研究方向外，还包括其它的研究方 向，比如多层次关联规则挖掘算法、多维关联规则挖掘算法。这方面的算法很 多，如h a n 等人提出的m lt 2 l 1 算法、s r i k a n t 等人提出的c u m u l a t e 算法等等。 从上面的介绍来看，关联规则挖掘算法在当前的数据挖掘研究中是一个热点方 向。 2 4 经典的a p r i o r i 算法及其改进算法 2 4 1a p r i o r i 算法， a p d o r i 算法【1 1 是r a g r a w a l 和r s r i k a n t 于1 9 9 4 年提出的为布尔关联规则挖 掘频繁项集的原创性算法。由2 3 节的讨论可知，a p r i o d 算法是一种层次挖掘算 法。算法的处理过程如下：首先扫描数据库，统计l - 项集的支持度计数，将满 1 3 第2 章关联规则及其挖掘算法 足最小支持度计数的1 项集归为一个集合三，。然后集合，与集合，之间做连接 操作，再次扫描数据库，找出满足最小支持度计数的频繁2 项集集合，记为幻。 依次类推，找出频繁k 项集集合厶，在每一次迭代过程中，a p r i o r i 算法都要扫 描数据库一次。 在每一层的迭代过程中，产生的候选项集数量很大，a p r i o r i 算法利用频繁 项集及其子集之间的关系( 称之为a p r i o r i 性质) ，压缩了算法的搜索空间，使得 算法发现频繁项集的效率得到了很大的提高。 性质2 1a p r i o r i 性质【1 l ：频繁项目集的所有非空子集都必须是频繁的。 a p d o r i 算法在第肛j 次到第七次的迭代过程中，使用了a p r i o r i 性质。具体 的过程分两步：连接步和剪枝步。 连接步：为了找到频繁缸项集的集合厶，首先在频繁似项集k ，之间 做迪卡尔乘积，得到候选“项集集合g 。两个频繁( k - 1 ) 项集k ，之间 做连接操作，必须保证满足以下条件 ( 1 】= 乞【l 】) ( 【2 】= ，2 【2 】) ( 1 ， k - 2 】= 1 2 k - 2 1 ) a ( 1 ， k 一1 】 如【七一1 】) ， 其中，和1 2 是k ，中的项集，记号厶阴表示厶的第j 项。 剪枝步：显然，厶是g 的子集，即g 中所有的成员不一定全是频繁项 集，但是所有的频繁如项集必然包含在q 中如何确定这些频繁缸项 集呢? a p r i o r i 算法通过扫描数据库，得出q 中每个候选项集的支持度 计数，支持度大于或等于最小支持度计数的项集即为频繁项集，这些项 集的集合即为厶。但是g 可能很大，确定厶所需要的计算量很大，因 此可以利用a p r i o r i 性质对q 进行剪枝。剪枝的原理是：任何非频繁的 似纠项集都不可能是频繁k 项集的子集这样对q 进行压缩，达到加 快求值的目的。 a p r i o r i 算法挖掘过程如下： 第一次扫描数据库，统计各1 项集出现的次数，将所有出现次数大于或 等于最小支持度计数的1 项集组成一个集合，即为频繁1 项集的集合，。 在所有满足连接条件的频繁1 项集三，之间做连接操作，得到候选2 项集 的集合o ，根据a p r i o r i 性质对g 进行剪枝。 第二次扫描数据库，统计g 中每个候选2 项集出现的次数，将所有出 现次数大于或等于最小支持度计数的2 项集组成一个集合，即为频繁2 - 项集的 集合2 1 4 第2 章关联规则及其挖掘算法 在所有满足连接条件的频繁2 项集三2 之间做连接操作，得到候选3 一项集 的集合o ，。根据a p r i o r i 性质对。进行剪枝。 第三次扫描数据库，统计g 中每个候选3 项集出现的次数，将所有出 现次数大于或等于最小支持度计数的3 项集组成一个集合，即为频繁3 项集的 集合3 。 依次类推，直到新的候选项集g 为空，此时算法执行结束，找出了所有的 频繁项集。由上面的挖掘过程可知，a p r i o r i 算法需对数据库进行多次扫描，并 且在每次扫描前都需要做连接和剪枝操作。 a p r i o r i 算法和它的相关过程的伪代码【1 】如下所示： 输入： d ：事务数据库： r a i ns u p ：最小支持度计数阈值。 输出：工：d 中的频繁项集。 ( 1 ) 三，= f i n d f r e q u e n t _ 1 - i t e m s e t s ( d ) ； ( 2 ) f o r ( 足- 2 ；如，o ；j b h ) ( 3 )c k = a p r i o r i g e n ( l k t ) ； ( 4 ) f o re a c h 事务t e d i i 扫描d 用于计数 ( 5 )c ，= s u b s e t ( c , , f ) ； 得到t 的子集 ( 6 )f o r e a c h 候选c e g ( 7 )c c o u n 什+ ； ( 8 ) ( 9 ) l k = c ec k ic c o u n t 耋r a i n _ s u p ( 1 0 ) ) ( 1 1 ) r e t u ml = u k l k ； p r o c e d u r ea p r i o r i g e n ( 如，) ( 1 ) f o re a c h 项集1 1 l k t ( 2 ) f o re a c h 项集：e l k _ ， 0 ) i f ( 1 。 1 】= 乞【1 】) ( 厶【2 】= 厶【2 】) ( 【七一2 】= 如【七一2 】) ( ，l 【j i 一1 】 之【七一1 】) t h e n ( 4 ) 萨厶q 厶；连接步 ( 5 ) i fh a s l n f r e q u e n t s u b s e t ( c ，l k - , ) t h e n 1 5 第2 章关联规则及其挖掘算法 ( 6 ) d e l e t e c ；“剪枝步 ( 7 ) e l s ea d dc t o