基于约束的关联规则挖掘

第二章　关联规则挖掘研究综述

随着数据库技术的成熟和数据库应用的日益普及，人们积累的数据量正在以指数级的速度增长。全世界每天新存入数据库的数据量数以千万兆字节。数据“洪流”正向人们汹涌而来。例如，现在的超市大多通过条形码扫描，把每一笔商品交易数据输入到数据库中。一个中等规模的超市所经营的商品有数万种，每天的交易量高达数万笔。这样一个月下来的数据量就会有几个G。如此大规模的数据在传统的数据库中并不能很好地回答经理人员关心的问题：商品在不同季节或一天的不同时间内的销售量有何变化规律？商品A销售量的增加是否会同时带动商品B的销售？如何调整商品的资金占用以达到最佳的资源配置？如何合理地安排商品的陈列以促进商品的销售？

近年来，数据挖掘，也称数据库中的知识发现，受到了国际人工智能界与数据库界研究人员的广泛关注。关联规则挖掘是数据挖掘研究中一个十分重要的研究课题。该问题首先由美国IBM Almaden研究中心的Rakesh Agrawal等人提出来的，其目的是要在交易数据库中发现各项目之间的相互关系。

与关联规则有关的最典型的事例就是著名的“尿布与啤酒”的故事。在一家超市里，有一个有趣的现象：尿布和啤酒赫然摆在一起出售。但是这个奇怪的举措却使尿布和啤酒的销量双双增加了。这不是一个笑话，而是发生在美国沃尔玛（WalMart）连锁超市的真实案例，并一直为商家津津乐道。沃尔玛拥有世界上最大的数据仓库系统，为了能够准确了解顾客在其门店的购买习惯，沃尔玛对其顾客的购物行为进行购物篮分析，以了解顾客经常一起购买的商品有哪些。沃尔玛数据仓库里集中了其各门店的详细原始交易数据。在这些原始交易数据的基础上，沃尔玛利用数据挖掘方法对这些数据进行分析和挖掘。一个意外的发现是：“跟尿布一起购买最多的商品竟是啤酒！”经过大量实际调查和分析，揭示了一个隐藏在“尿布与啤酒”背后的美国人的行为模式：在美国，一些年轻的父亲下班后经常要到超市买婴儿尿布，而他们中有30%～40%的人同时也为自己买一些啤酒。产生这一现象的原因是，美国的太太们常叮嘱她们的丈夫下班后为小孩买尿布，而丈夫们在买尿布后又随手带回了他们喜欢的啤酒。

按常规思维，尿布与啤酒两者风马牛不相及，若不是借助数据挖掘技术对海量交易数据进行挖掘和分析，沃尔玛是不可能发现数据内在的这一有价值的规律的。

数据关联是数据库中存在的一类重要的可被发现的知识。若两个或多个变量的取值之间存在某种规律性，就称为关联。关联可分为简单关联、时序关联、因果关联等。关联分析的目的是找出数据库中隐藏的关联网。有时并不知道数据库中数据的关联函数，即使知道也是不确定的，因此关联分析生成的规则带有可信度。关联规则挖掘是为了在海量数据集中发现各数据项集之间有趣的关联或相关联系。R．Agrawal等人于1993年首先提出了挖掘顾客交易数据库中项集间的关联规则问题，以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。他们的工作包括对原有算法进行优化，如引入随机采样、并行的思想等，以提高算法挖掘规则的效率，以及对关联规则的应用进行推广。

关联规则挖掘在数据挖掘中是一个重要的课题，最近几年已被业界广泛研究。关联规则在分类设计、商店布局、隶属邮寄、产品排放和市场分析等多个方面有着十分广阔的应用前景。

一、关联规则的定义

关联规则挖掘可以发现交易数据库中各项目（Items）或属性（Attributes）之间的有趣联系，这些联系是预先未知的，不能通过数据库的逻辑操作或统计方法得到，因为它们不是基于数据自身的固有属性，而是基于数据项目的同时出现的特征。关联规则的特点是形式简洁、易于解释和理解，并可以有效地捕捉数据间的重要关系。

理论上，关联规则挖掘是指从一个大型数据集（Data set）中发现有趣的关联（Association）或相关（Correlation）关系，即从数据集中识别出频繁出现的属性值集（Sets of Attribute value），也称为频繁项集（Frequent Itemsets，简称频繁集），然后再利用这些频繁集创建描述关联关系的规则过程。

关联规则挖掘问题可以形式化描述如下：

事务：设I＝｛i1，i2，…，im｝是由m个不同项目（属性）组成的集合，ik（k＝1，2，…，m）称为项目（Item）。DB为针对I的事务数据库，其中每个事务T是I中一组属性的集合，即T≤I，并有一个唯一的顾客标识符TID。

项集X的支持度Support（X）：项集X的支持度表示项集X的重要性。若项集X≤I且X≤T，则称事务T支持项集X或包含项集X。事务数据库DB中支持项集X的事务数称作项集X的支持数，我们用X．Count表示。设｜DB｜为事务数据库中记录的总数，则项集X的支持度为：Support（X）＝X．Count／｜DB｜。

最小支持度：发现任务所要求的最小支持度，只有满足最小支持度的项集才有可能在关联规则中出现，这些项集称为频繁项集或大项集（Large Itemset）。设｜DB｜为事务数据库中记录的总数，对于长度为k的项集X，如果X．Support≥Smin×｜DB｜，则称项集X为大k－项集，否则为弱k项集。所有大k－项集的集合称为大项集，而所有的弱k项集的集合称为弱项集。

规则置信度：规则置信度表示规则的可靠性程度。对于关联规则规则R的置信度Confidence（R）＝Support（X∪Y）／Support（X）。

关联规则的挖掘问题就是在事务数据库DB中找出所有满足用户给定的最小支持度Smin和最小置信度Cmin条件的关联规则。一条关联规则就是形如

关联规则成立的条件是：

（1）它具有支持度s，即事务数据库DB中至少有s%的事务包含X∪Y；

（2）它具有置信度c，即在事务数据库DB中包含X的事务至少有c%同时也包含Y；习惯上我们将关联规则表示为Y（s%，c%）。

挖掘关联规则问题可以分解为以下两个子问题：

（1）找出事务数据库DB中的大项集，用L表示；

（2）利用大项集L生成关联规则。对于任意大k－项集A，若有则有关联规则

由于第（2）个问题相对比较简单和直观，R．Agrawal等人已经提出了很好的算法，而问题（1）是关联规则挖掘的核心所在，目前大多数的研究工作主要都集中在这一子问题上。

二、关联规则的分类

按照不同情况，关联规则可以进行如下分类。

1．基于规则中所处理变量的类别

根据规则中所处理变量的类别，关联规则可以分为布尔（Bool）型关联规则和数值型关联规则。布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的关系；而数值型关联规则可以和多维关联规则或多层关联规则结合起来，对数值型字段进行处理，将其进行动态分割，或者直接对原始的数据进行处理。当然，数值型关联规则中也可以包含种类变量，例如：性别“秘书”是布尔型关联规则；性别涉及的收入是数值类型，所以是一个数值型关联规则。

2．基于规则中数据的抽象层次

根据规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。在单层关联规则中，所有的变量都没有考虑到现实数据是具有多个不同的层次的；而在多层关联规则中，对数据的多层性已经进行了充分考虑。例如：IBM台式机打印机，是一个细节数据上的单层关联规则；台式机打印机则是一个较高层次和细节层次之间的多层关联规则。

3．基于规则中所涉及数据的维数

根据规则中所涉及数据的维数，关联规则可以分为单维的和多维的。在单维的关联规则中，我们只涉及数据的一个维，如用户购买的物品。例如：下面这条规则只涉及用户购买的物品，是单维关联规则而在多维的关联规则中，要处理的数据将会涉及多个维，要处理多维数据，涉及多个变量。例如下面这条关联规则同时涉及三个维，分别为年龄维、收入维和购买物品维，因而是一条多维关联规则：“年龄20—30，月收入由此可见，单维关联规则用来处理单个属性中的一些关系，而多维关联规则用来处理各个属性之间的某些关系。

三、关联规则的发现步骤

关联规则的发现问题实质上是在满足用户给定的最小支持度的大项集中，找出所有满足最小置信度要求的关联规则。当事务数据库DB非常大的情况下，这一问题显得十分复杂。所有的发现算法无论其采用何种数据结构、其复杂程度以及效率如何，它们都可以分为以下六个步骤。

1．预处理与发现任务有关的数据

这个阶段也称为数据过滤阶段。知识发现的第一步就是选择合适的目标数据集。用户可以通过使用知识模板或数据选择与可视化工具来引导该过程。系统因此可将学习过程聚焦在与发现目标相关的数据上，筛选掉不必要的数据。由于所涉及的数据集往往十分庞大，数据采样在许多情况下是对数据进行初步处理的一种有效方法。如果需要，在采样基础上所发现的结果可以在整个数据集上进行验证测试。数据过滤阶段的输出是用于数据测试的数据子集和约简了的规则空间。根据具体问题的要求对事务数据库进行相应的过滤操作，从而构成规格化后的事务数据库DB。

2．规则约束条件的设定

也称为模式过滤，是知识发现的第二阶段。知识发现系统在该阶段借助模板或其他类型的选择工具来定义待发现规则的类型。这些工具通常以适当的用户交互界面面向用户提供可用的规则类型和属性值等形式协助用户构造模式。实际上，大多数系统只能学习有限个不同类型的规则。所以规则类型可进一步优化以符合系统的限制。可以在规则的前件和后件中指示肯定包含或肯定不包含的属性值，或可能包含的最大合取项的个数。

3．统计过滤

规则空间在数据挖掘的第三阶段是根据统计方法进一步过滤。尽管从数据库中发现的规则也许能满足用户指定的模式，但其中相当一部分规则在统计意义上可能并不重要。因此，统计过滤阶段的目标是删除那些在统计意义上不重要的规则。用户可以通过设置适当的统计参数或选择适当的技术来参与该阶段。传统的统计技术是评价规则的基础。在关联规则的挖掘过程中，这一阶段就是针对给定的目标数据集DB，发现满足用户设定的最小支持度阈值的大项集L。在一般情况下，由于目标数据集相当庞大，因而统计过滤阶段是整个数据挖掘系统的核心。

4．语义过滤

通过前面数据过滤、模式过滤和统计过滤三个阶段后，用户可以生成所有满足最小置信度的关联规则，形成规则集。但是其中相当一部分从语义上看可能并没有什么意义或不太令人感兴趣，甚至是冗余的。例如规则：任何男性从不怀孕。该规则显然满足所要求的模式，并且具有很强的统计支持，但它是人人皆知的常识，因而对决策没有任何特别的价值。语义过滤就是要设法删除在语义上没有意义的规则。语义过滤主要是用于决策支持和知识库构造这些强调语义的领域。

5．规则的评估和解释

通常用户可以在经过上述几个阶段后所生成的规则集中选择感兴趣的规则，然后以适当的形式或方法表达所选择的规则，形成最后的规则集。

6．规则的用户化呈现

该阶段主要采用可视化工具面向用户可视地显示数据挖掘的最终结果。

或者也可以将关联规则的挖掘过程分为三个相对简单的过程：预处理阶段、规则发现阶段和后处理阶段。

1．预处理阶段

该阶段主要负责理解用户的发现意图，为进一步的规则发现活动准备好相关的数据。它包括接收并理解用户的发现要求，描述用户的发现任务，利用数据库和系统字典提取出所有相关的数据并加以整理，形成初始知识模板。预处理阶段相当于前面的数据过滤和模式过滤阶段。

2．规则发现阶段

规则发现阶段对应于前面的统计过滤阶段，是整个挖掘过程的核心部分。

3．后处理阶段

后处理阶段包括了语义过滤阶段、规则评估阶段和规则的可视化呈现阶段。后处理阶段的结果是以多种面向用户的形式输出用户关心的关联规则，包括数据表格、各种统计图形和准自然语言的发现报告等。关联规则挖掘步骤可以用图2－1来表示。

图2－1　关联规则挖掘步骤

如前所述，R．Agrawal等人将关联规则挖掘问题分解为两个子问题，但我们可以看到将关联规则按上述五个阶段进行划分更加合理。数据过滤和模式过滤为规则的挖掘进行了有效的数据准备，从而避免了盲目的挖掘。规则的评估和解释使用户能够更加容易地理解和应用挖掘得到的规则。而规则的用户化呈现则是通过可视化的形式向用户显示最终的挖掘结果。

四、关联规则挖掘算法的分类

R．Agrawal等人于1993年首先提出了挖掘顾客交易数据库中项集间的关联规则问题，其核心方法是基于频繁集理论的递推方法。在此之后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。他们的工作包括对原有的算法进行优化，如引入随机采样、并行计算等方法，以提高算法挖掘关联规则的效率。同时也提出了各种变体，如泛化的关联规则、周期性关联规则等，并对关联规则的应用进行积极探索。

关联规则的挖掘算法主要可以分为以下几个方面。

1．利用频繁项集向下封闭性质（Apriori性质）的Apriori系列算法。主要有：经典关联规则挖掘算法Apriori算法；对事务项集进行重组预选的AprioriTid算法；用Hash表进行事务项集重组的DHP算法等。

2．利用对事务数据库划分来提高效率算法。包括基于采样的算法；基于分割（Partition）方法；R．Agrawl等人提出的并行算法CD（Count Distribution）、Cad（Candidate Distribution）、DD（Data Distribution）等；Cheng等人提出的DMA算法等。

3．利用各种数据结构进行数据挖掘的算法。例如Anderson和Moore采用一种Adtree的数据结构，Amir、Feldman和Kashi采用trie树，Pasquirer和Bastide等使用项目格，胡可云等采用概念格来挖掘关联规则。

4．适应挖掘内涵和外延扩展的算法。如Han等人提出的基于概念分层的关联规则算法，Bayardo等人提出的受限关联规则挖掘算法等。

5．挖掘全部频繁项集而不产生候选的算法。当前主要是频繁模式增长算法（Frequent－Pattern Growth）。它通过FP树来存储所有的频繁模式信息，通过分析FP树路径的条件模式基来得到所有的频繁项集。

6．遗传算法。这是一种崭新的数据挖掘算法，但它是针对具体问题的。处理每一个具体问题都必须设计合理的编码策略和适应度函数等。

不论关联规则算法有多少，都可以归纳为两类：一类是产生频繁集候选项的算法；另一类是不产生频繁集候选项的算法。对于前者，大多数算法利用Apriori性质对候选项集的数目进行压缩，虽然效果非常明显，但在频繁模式较长时，候选频繁项集的数目是十分惊人的。同时，该类算法还有两种开销，一是Apriori＿gen过程中要进行大量的自连接，二是要多次重复扫描数据库，I／O开销非常巨大。对于不产生候选项集的算法，如当前比较成熟的FP增长算法，虽然较Apriori类算法有较大性能的提高，但它仍然存在着一定的缺点：大量FP树结点链接增加数据结构的复杂度和资源的占用，树枝伸展的无序将降低模式检索和挖掘的效率，通过条件模式基的分析产生频繁模式仍然需要大量的连接操作。

遗传算法是一种不产生候选项的关联规则挖掘算法，但由于遗传算法目前许多有意义的结论几乎全是试验结论，缺乏理论上的严格推导，目前用得不是很普遍。

五、Apriori算法分析

（一）Apriori算法简介

在已经提出的诸多关联规则挖掘算法中，R．Agrawal和R．Srikant提出的Apriori算法是最有影响的。Apriori使用一种称为逐层搜索的迭代方法，频繁k－项集用于探索（k＋l）－项集。首先，找出频繁1－项集的集合，记作L1，L1的作用是用以产生候选频繁2－项集C2，从而产生频繁2－项集L2。同样频繁2－项集L2的作用是用以产生候选频繁3－项集，如此重复下去，直到找不到频繁k－项目集Lk。这样，每次迭代查找过程都需要扫描一次数据库。

1．利用两个性质，减小搜索空间

为提高频繁项集逐层产生的效率，Apriori算法利用了如下两个重要的性质，用于减小搜索的空间。

（1）若X为频繁模式，则X的所有子集都是频繁模式

证明：设X是频繁项集，即有且 Y≠Φ。数据库DB为事务数据库，对事务T∈DB，如果有显然有即包含项集X的事务同时一定包含项集Y，则Support（X）≤Support（Y），因此有Support（Y）≥Smin，所以项集Y是频繁的，证毕。

（2）若X为非频繁模式，则X的所有超集均为非频繁模式

证明：设X是非频繁项目集，即有Support（X）≤Smin，项集Y且Y≠Φ，数据库DB为事务数据库，设事务T支持项集X的支持数为X．Count，支持Y的支持数为Y．Count，根据项集支持数的定义，可知支持项集Y的事务T必支持项集X，即Y．Count≤X．Count，由于Support（X）≤Smin，很显然有Support（Y）≤Support （X）≤Smin，证毕。

算法体现出十分重要的剪枝性质：频繁项集的所有非空子集都是频繁的。该性质用于缩减候选项集的大小，压缩搜索空间。目前，绝大多数的大项集发现算法都以Apriori算法为核心，或是其变体，或是其扩展。

2．Aprioro算法的过程

Apriori算法实际上是一种宽度优先算法，该算法将关联规则的发现分为两部分：

第一步是识别目标数据集中所有的频繁大项集，即支持度不低于用户设定的最小支持度的项集。

第二步是从频繁大项集中构造所有置信度不低于用户设定的最小置信度的关联规则。如果有m个项目，则有2　m个可能的频繁大项集。由此可见，识别或发现所有的频繁大项集是关联规则挖掘算法的核心所在，它也是整个关联规则挖掘算法中计算量最大的部分。

Apriori算法通过对数据库的多次扫描来发现所有的频繁大项集。在第一次扫描中，Apriori算法计算I中所有单个项目的支持度，取其中支持度不低于最小支持度的项集构成频繁1－项集L1，然后两两连接频繁1－项集L1，（L1×L1）生成候选2－项集C2。再次遍历数据库，计算候选2－项集C2中各元素的支持度，取其中支持度不低于最小支持度的项集构成频繁2－项集L2。在后续的第k（k＞1）次扫描时，首先利用前一次扫描时所发现的频繁（k－1）－项集Lk－1为基础，生成候选k－项集Ck，Ck是频繁k－项集的超集。然后再次扫描事务数据库计算候选k－项集Ck中每个元素的支持度，最后确定候选k－项集Ck中哪一些真正成为频繁k－项集Lk。重复上述过程，直到再也发现不了新的频繁项集为止。

如前面所述，如果有m个项目，则有2m个可能的频繁项集。数据库中的事务可能很多，所以对所有项集都进行支持度计算几乎是不可能的。目前，有关关联规则发现算法的研究主要集中在如何能快速有效地生成所有的大项集。主要的焦点有两方面：

能否对项集进行充分剪枝，尽可能地最小化候选项集的大小；(www.xing528.com)

能否通过最少次数的事务数据库DB扫描，达到提高算法效率的目的。

Apriori算法利用了“所有大项集的任意子集也必是大项集，所有弱项集的任意超集都是弱项集”的剪枝原则对候选项集进行有效的剪枝，从而提高了频繁项集的发现效率。

3．实例分析

下面以一个超市销售系统中顾客购物情况的例子进行分析。为简单起见，以数字代表不同类型的商品。超市经理希望了解不同类型商品之间的关联，要求列出那些同时购买的、支持度大于40%的商品的名称，则我们可以利用Apriori算法对交易数据库进行多次扫描得到所有的大项集。

图2－2　Apriori算法实例分析

Apriori算法实例运行分析：

首先，扫描交易数据库DB，确定I中所有单个项目为候选1－项集C1，并计算其中各元素的支持度，如图2－2（2）所示。由于商品4只在TID＝100的交易中出现过一次，其支持度小于40%，因而略去。最后得到频繁1－项集L1，如图2－2（3）所示。

其次，根据Apriori算法的候选项集生成函数Apriori＿gen将频繁1－项集L1两两连接生成候选2－项集C2，如图2－2（4）所示。再次扫描数据库，计算候选2－项集C2中所有元素的支持度，由于候选2－项集C2中的｛1　2｝、｛1　5｝的支持度均小于40%，因而也略去，从而得到频繁2－项集L2。

最后，继续上述过程，最后得到频繁3－项集L3｛2　3　5｝，由于不可能再生成新的候选项集，于是循环结束。

（二）Apriori算法的基本框架

输入：事务数据库DB和最小支持度Smin。

输出：事务数据库DB中所有的频繁项集L。

Apriori＿gen函数以频繁（k－1）－项集Lk－1为参数，返回所有大k－项集Lk的超集（Superset）。首先，在两两连接（Join）时，如果p，q ∈Lk－1的前k－2个项目完全相同，则把两者的并集p∪q插入Ck，得到大k－项集Lk的一个超集Ck，然后利用大项集的任意子集也必是大项集的剪枝原则对Ck进行剪枝，最后得到候选k－项集Ck。

例如L3为｛｛1　2　3｝，｛1　2　4｝，｛1　3　4｝，｛1　3　5｝，｛2　3　4｝｝。在两两连接步骤之后，C4为｛｛1　2　3　4｝，｛1　3　4　5｝｝。在剪枝（prune）步骤将删除项集｛1　3　4　5｝，这是因为项集｛1　4　5｝不在L3中。所以最后得到的候选4－项集C4中仅有｛1　2　3　4｝。剪枝步骤需要测试一个新产生的候选k－项集Ck的所有长度为k－1的子集是否在Lk－1中。为了使得判断更加快速，可以将大项集存储在一个hash表中。

候选项集Ck存储在一棵hash树中，hash树的一个节点包含了组成该项集元素的链表（一个叶节点）或包含了一个hash表（一个内节点）。在内节点中，hash表的每个bucket都指向另一个节点。hash树的根的深度定义为1。在深度为d的一个内节点指向深度d＋1的节点，项集存储在叶子中。要加载一个项集c时，从根开始向下直到一个叶子。在深度为d的一个内节点上，要决定选取哪个分枝，可以对此项集的第d个项目使用一个hash函数，然后跟随相应bucket中的指针。所有的节点最初均创建成叶节点。当一个叶节点中项集数量超过某个指定的阈值时，此叶节点就转为一个内节点。

从根节点开始，subset函数寻找所有包含在某个事务t中的候选大项集。方法如下：若处于一个叶子节点，就寻找此叶子中的哪些项集是包含在事务t中的，并对它们附加引用指向答案集合。若处于一个内节点，而且是通过hash项目i从而到达此节点的，那么就对t中第i个项目之后的每个项目进行hash，并对相应bucket中的节点递归地应用这个过程。对于根节点，就对t中的每个项目进行hash。

为了了解为什么subset函数返回的就是所想要的集合，可以考虑在根节点所发生的情况。对于事务t中包含的任何项集c，c的第一个项目必须在t中。在根节点，对t中的每个项目进行hash，我们确信仅仅忽略了那些第一个项目不在t中的项集。类似的讨论适用于较低的深度。唯一的附加因素是，因为任何项集的项目是有序的，如果对项目i进行hash从而达到当前节点，那么我们就只需要考虑t中排在i之后的项目。

（三）Apriori算法的不足

作为最为经典的关联规则算法，尽管采用了对候选频繁项集剪枝的方法提高了效率，但还是存在一些不足的，主要体现在：

1．Apriori算法会产生大量的候选项集，并呈现组合式的增长

造成这种情况的主要原因，是在每一步产生候选项集时循环产生的组合过多，没有排除不应该参与组合的元素。若频繁1－项集的个数为10000，则候选2－项集的个数将达到107个；若要发现长度为100的频繁项集，则必将产生多达2100个候选项集。

2．需要多次扫描事务数据库

在Apriori算法中每生成一个候选项集，就需要遍历一次事务数据库。由于事务数据库都非常庞大，而且数据不可能直接保存在内存中，因此对数据库的多次扫描会造成很大的I／O负载，每次扫描时间很长，算法效率会非常低下。

3．在频繁项集长度增大时，算法运行时间显著增加

当频繁项集长度变大时，支持该频繁项集的事务会减少，从理论上讲，计算其支持度所需的时间不会明显增加。但Apriori算法在计算事务数据库对长频繁项集的支持度时，由于每个频繁项集的项目变多了，所以在确定每个频繁项集是否被事务支持的开销也增大了。事务数据库的事务总量并没有减少，因此频繁项集长度增加时，运算时间显著增加。

4．算法的适应面窄

该算法只考虑了单维布尔关联规则的挖掘，但在实际应用中，可能出现多维的、数值的、多层的关联规则。这时，该算法就需要进行改进。

六、典型的改进算法

为了提高频繁项集的发现效率，Park等人提出了直接hash剪枝的DHP算法。由于在生成和发现频繁2－项集上耗费的时间是最为可观的，DHP算法试图通过直接hash剪枝技术快速地发现频繁2－项集，从而达到提高关联规则发现效率的目的。

Brin等人提出了动态项集技术DIC算法。其基本思想是在对k－项集进行支持数计数的同时，也对某些（k＋1）－项集进行支持数计数，以此来提高每次事务数据库遍历的效率，从而减少对交易数据库的遍历次数。在大多数频繁项集发现算法中，（k＋1）－项集的支持数计数要在k－项集的支持数计数完成之后再进行。但是DIC算法只要能初步确定某（k＋1）－项集潜在频繁，就开始对其进行支持数计数。这样就能够尽可能早地在完成k－项集的支持数计数之前开始对某些（k＋1）－项集的支持数进行计数。一般地，该算法所需的遍历次数要少于Apriori算法需要的遍历次数，一定程度上提高了算法的效率。

分治法是一种常见而有效的算法设计思想。基于此，Savasere等人提出了一种发现频繁项集的划分算法。该算法分为两个阶段：在第一阶段，算法将事务数据库划分为n个互不相交的部分，每个划分的大小以其全部事务数据可以在内存中进行处理为原则，然后在每个划分中独立地生成所有长度的局部频繁项集，令Pi为第i个划分，在其中所发现的局部大项集记为表示划分，j为项集的长度，k为该划分中局部频繁项集的最大长度；在第二阶段，归并全部n个划分中相同长度的局部频繁项集，从而生成所有的全局候选项集，长度为j的候选项集的集合为接着再次遍历事务数据库DB，收集中每个候选元素的支持度。该算法的核心是基于这样一个观察：如果某项集是全局频繁的，则该项集必至少属于某局部频繁项集该算法具有良好的可并行性。例如为每个划分均指派一个处理器来生成局部频繁项集频繁项集生成算法的每次循环结束时，各处理器需要彼此通信以计算候选k－项集的全局支持数。这一通信过程在算法运行方面有可能会成为瓶颈。

目前，绝大多数关联规则发现算法均具有一个共同的特点，即都是Apriori算法所提出的“自底向上”的方法。数据库中的频繁项集有多长，对数据库的遍历就有多少次。因而这些算法的计算代价一般较高，其成功的关键在于数据库中的频繁项集通常较短。

另外，Bayardo提出了一种令人感兴趣的频繁项集生成算法。为了尽早发现较长的模式，该算法明智地采用了“向前看”技术，使这些较长模式的子集不必进一步考察，就可以删除。试验结果表明该算法较之Apriori算法在性能上有实质性的改进。

事务数据库的规模通常都很大，为了提高频繁项集的生成效率，Toivenen提出了采用随机采样的技术，这样就可以减少相当可观的I／O负载。由于数据分布往往不均衡，随机采样可能会引起数据倾斜（Data Skew），因而该方法的不足在于它有可能导致不精确的结果。为此，Lin和Dunham提出了反数据倾斜的关联规则发现算法，将数据库的遍历次数降低为最多两次。

七、关联规则的生成算法

从前一阶段得到的频繁大项集中生成关联规则十分直观、简单。R．Agrawal等人提出了很好的解决方法。

对于任意大k－项集Lk∈L，设A＞Lk，A≠Φ，如果是一条关联规则，则其必满足：ConfidenceSupport（Lk）／Support（A）≥Cmin。如果存在A的非空子集则有Support（A），因此Confidence例如：给定大项集ABCD，如果不满足最小置信度，根据上述的引理则根本不必去考察是否满足最小置信度。

基于这一原理可以给出生成关联规则的简单算法。

输入：频繁项集L和最小置信度Cmin

输出：关联规则集合R

如果有Confidence（（Lk－A）→A）＝Support（Lk）／Support（Lk－A）≥Cmin，则必有ConfidenceSupport（Lk）／Support是一条关联规则，则也必定是一条关联规则。在上例中如果条关联规则，即满足用户设定的最小置信度，则C也必满足用户设定的最小置信度。这一特性与Apriori算法中的大项集的任意子集也必是大项集的剪枝原则十分相似，所以可以利用这一原理来提高关联规则的生成效率。对于每个大项集l∈L，它首先用l生成后件具有一个项目的关联规则，并将这些规则的后件存入集合Hl中，然后利用Apriori＿gen函数生成具有两个项目的后件集合H2，对于H2中的任一元素h，如果≥Cmin成立，则输出关联规则否则从H2删除该元素。然后继续利用Apriori＿gen函数生成H3，即：H3＝Apriori＿gen（H2），以此类推。

算法2．2关联规则生成算法

输入：频繁项集L和最小置信度Cmin

输出：关联规则集合R

在前面的超级市场销售系统例子中，利用规则生成算法2．3得到所有满足最小置信度的关联规则，如图2－3所示。

图2－3　关联规则生成实例

与算法2．2中的关联规则生成算法相比，算法2．3的效率更高。比如给定大项集ABCDE，假定ABCE→D和ACDE→B满足最小置信度条件，则如果利用算法2．2的关联规则生成算法，则我们必须反复调用genrules（ABCDE，ACDE）和genrules（ABCDE，ABCE），前者必须验证ABC→DE、BCE→DA、ABE→DC和ACE →DB是否满足最小置信度条件，而后者必须验证DCE→BA、ADE →BC、ACE→BD和ABC→BE是否满足最小置信度条件。用算法2．3的关联规则生成算法则只需要验证ACE→BD是否满足最小置信度，很显然算法2．3的关联规则生成算法的效率要高很多。

八、基于约束的关联规则挖掘

自从R．Agrawal等人提出了关联规则的挖掘问题之后，关联规则的挖掘就逐渐成为众多研究人员关注的焦点。在许多研究方向，诸如挖掘一般或多层次关联规则、挖掘多值属性关联规则、并行挖掘和分布式挖掘、增量式挖掘算法以及基于约束的关联规则挖掘等，都取得了长足的发展。

在绝大多数挖掘系统中，通常是首先由用户确定挖掘的目标数据集，并设定最小支持度和最小置信度阈值，然后系统利用用户选定的挖掘算法对目标数据集进行挖掘。在经过大量的计算和漫长的等待之后，用户却经常是大失所望。因为在经过百无聊赖的等待之后，用户往往不得不面对大量的垃圾规则或信息。由此用户对数据挖掘系统的效能产生了怀疑。究竟数据挖掘系统能给用户带来什么，是效益还是累赘？

实际上，用户在借助挖掘系统以前，通常在头脑中有了对问题的最初想法，总是希望了解关于某一特定方面的信息。比如超市管理人员希望了解与某一特定商品相关的销售信息，而不是泛泛地发现全部商品的规则。基于约束的关联规则挖掘问题的提出在很大程度上缓解了这一矛盾，约束条件的提出使得原来挖掘系统中缺乏用户的主动参与和控制的弊端得以减轻，使得整个挖掘过程更加具有针对性，挖掘的性价比也得到了大幅度的提高，也能使用户获得更有趣的、更实用的和更具针对性的关联规则。

约束条件可以是多种多样的，最常见的最小支持度和最小置信度阈值就是一种约束条件。除了最小支持度和最小置信度外，还有时间属性的约束、项约束条件、属性约束和元模式制导等多种约束条件。我们重点对周期性关联规则挖掘、基于约束的关联规则挖掘、基于属性约束的关联规则挖掘以及基于时间窗口的关联规则增量式更新问题进行分析。

周期性关联规则的挖掘充分考虑了挖掘对象数据中时间属性的影响，对事务数据库根据数据的时间属性进行不同的划分并分别进行相应的分析和研究，我们可以发现事务数据库中许多潜在的关联关系。比如对商场的销售数据按月划分后进行挖掘，也许就可以发现商品的销售会因为季节的变化而产生某种周期性的变化。所以在合适的时间单元内对数据进行分析，往往会发现某些事务经常在一些时间单元内周期性地重复发生，而在另外的时间单元中却很少发生。换句话说，当数据包含时间属性时，也许会存在某种周期性的变化规律。很显然，这样的研究将有助于确定销售趋势和用户需求模式的变化，从而为决策者提供决策依据，使决策者能够及时调整经营策略以适应市场的需要。如上所述，周期性关联规则挖掘是对关联规则挖掘研究的一个扩展，它主要是揭示数据随时间的变化呈周期性变化的规律。

项约束条件是很重要的一类约束条件，我们重点对两类项约束条件进行研究。第一类是以布尔表达式给出的项包含和不包含约束条件为前提，在分析Reorder算法和Direct算法的基础上，提出了基于第一类项约束条件的关联规则挖掘的ARMIC算法。算法ARMIC在初始阶段直接利用项约束条件C生成候选项集，而不是像Reorder算法那样首先生成包含入选项的候选项集，所以ARMIC算法生成的候选项集要小于Reorder算法生成的候选项集。另外，在后期迭代中需要利用Reorder算法的生成方法生成候选项集，从而避免了Direct算法中候选项集不必要的扩散。测试结果表明，ARMIC算法的执行效率比Reorder算法和Direct算法都要高一些。

在实际情况中，用户对不同的项目并非是一视同仁的，往往会对某些特定的项目特别感兴趣，其他一些项目则相对关心得较少。所以，关联规则的挖掘过程被要求能够体现并满足用户的这一需要。在挖掘的初始阶段，用户通过给不同的项目设定不同的加权值以表示对不同项目的关注程度或是说明不同项目的重要性程度。我们也称这一类基于项约束条件的关联规则挖掘问题为加权关联规则挖掘问题。在加权关联规则挖掘过程中，不但需要考虑规则的支持度，而且还需要考虑各项目加权因子的影响。

我们还对不同类型的属性约束条件进行了分析和归纳，讨论了在反单调性和简洁约束条件下的关联规则挖掘问题。

在实际的信息系统中，数据是随着时间的变化而不断变化的。因此某些已发现的规则可能不再有效，而某些原来非法的规则可能成为合法规则。因此在现实中，附加上某种时态约束的规则将可以得到更好的描述，也会更具有价值。我们针对这一情况，提出了基于时间窗口的关联规则增量式更新算法TW＿EIUP（Time window based Efficient Incremental Updating），该算法充分利用了以前的挖掘结果，并对候选大项集进行多重剪枝，有效地减少了模式匹配的次数，从而提高了关联规则更新的效率。

九、基于约束的挖掘系统模型

从以人为中心的挖掘系统角度来看，现有关联规则挖掘系统大都存在如下的问题。

1．缺乏用户的主动参与和控制

现有的关联规则挖掘系统大都只是允许用户在挖掘的初始阶段设定最小支持度和最小置信度参数来对整个挖掘过程进行控制。在挖掘过程中用户无从知晓挖掘进程的进展情况，也无法调整约束条件或最小支持度和最小置信度参数，从而实现对挖掘进程的控制。解决这一问题的办法就是打破黑箱作业，将原来的挖掘过程分为两个阶段。在挖掘过程中提供反馈信息和用户控制的切入点，使用户拥有控制全局的满足感。

2．挖掘过程缺少针对性，整个挖掘过程具有较大的盲目性

现有的关联规则挖掘系统由于控制参数过于简单，根本不可能更进一步表示用户关注的重点或焦点，也就无法提供所谓的焦点规则挖掘。所以我们希望为用户提供约束条件的输入界面，使用户可以输入不同类型的约束条件来表达其关注的焦点，避免系统不必要的时间消耗。另外，还可以利用约束条件对候选项集进行有效的剪枝，从而达到提高系统挖掘效率的目的。

3．控制参数过于简单

现有的关联规则挖掘系统中大都采用最小支持度和最小置信度参数对目标数据库进行挖掘。但在有些时候像相关性（Correlation）这样的参数约束更加适用。另外，对于某些规则如：“飘柔洗发液→牙膏”表示顾客购买“飘柔洗发液”经常同时购买“牙膏（不分品牌）”，由于规则的前件是具体的商品，而后件是某一类的商品，所以前后件的支持度约束应该是不一样的。而现有的关联规则系统很难将其进行区分。我们将基于约束的关联规则挖掘模型分为两个阶段：

图2－4　基于约束的挖掘系统模型

第一阶段，用户通过用户交互界面设定控制参数和各种不同的约束条件，然后系统根据用户设定的约束条件和控制参数进行挖掘。在第一阶段结束后用户可以根据得到的结果对原有的约束条件和控制参数进行修改，可以增加或删除某些约束条件，调整最小支持度参数。通过对约束条件的多次修正，系统挖掘的结果将逐步求精。如果用户对第一阶段得到的结果表示满意，可以引导系统进入第二阶段的挖掘。

第二阶段，用户确定最小置信度（Confidence）或是相关性（Correlation）等控制参数，也可以进一步对规则前后件设定约束条件。第二阶段结束后得到的就是所有满足用户设定约束条件的关联规则集合。理论上，这样的规则应该是用户希望得到的。挖掘模型如图2－4。

当然，十分重要的一点是图2－4所示的挖掘系统模型应该保持向下兼容性。即如果用户希望进行一般的关联规则挖掘，那么只要用户在初始阶段设定最小支持度和最小置信度参数，并关闭反馈信息和控制入口开关，系统就能毫无阻碍地进行关联规则的挖掘。由于第一阶段的工作是返回所有满足约束条件的频繁项集，所以第一阶段是系统计算的重点。只有提高满足约束条件的频繁项集的发现速度才能使系统的效率有较大程度的提高。这也已经成为关联规则挖掘领域中十分重要的研究方向之一。

十、关联规则的应用

尽管关联规则挖掘始源于商业上对市场购物篮数据进行分析的问题，但是它的应用却不止于此。概括起来，关联规则的应用领域包括：商业与金融、人口普查数据分析、工程技术数据分析、医疗保健、财政、宏观决策支持、电子商务、网站设计、通信和互联网等。以下是其几个典型的应用领域。

1．市场菜篮子分析

理解用户的购买习惯和喜好对于零售商作出相应的销售决策是十分重要的，这些决策包括销售哪些商品、如何设计商品的式样、如何设计目录及怎样陈列商品以达到促销的目的等，关联规则挖掘可以向用户提供上述信息。一个零售环境中的典型应用，便是市场菜篮子分析或称购物篮分析。由于条码技术的广泛应用，客户的购买信息可以完全自动化地以电子数据的形式记录在客户的数据库中，通过分析数据项目间的关系（这里的项目指的是顾客所购买的商品），可以利用所发现的关联规则指导商家的销售行为或广告行为等，例如，后项中包含“电视机”的规则将帮助用户决定怎样做才能促进电视机的销售。另外一个例子是：B商品经常和A商品一起被用户所购买，即存在规则A→B，由于B的价格远远小于A，因此为了促销A，可以将B作为与A一起销售的免费商品，进行捆绑销售。

2．交叉销售

在目前激烈的商业竞争中，留住现有的顾客，充分利用这些现有的顾客资源甚至比吸引更多的新顾客更为重要。许多公司提供了不止一项的服务或产品，公司可以通过对现有的客户数据进行分析而达到促销的目的。如向这些客户推销他们目前尚没有购买的商品（或服务），被认为是一种快速获取收益的好方法。交叉销售就是用于描述这类问题的一个专有词汇，它是指向公司的现有客户销售这些顾客尚未购买的商品（或服务）的销售行为。由于在大型的公司或组织里，其客户的数据库往往是非常庞大的，人工浏览这些数据库并加以分析显得十分困难，因此，自动化的关联规则挖掘技术便成为获取有用信息的强大工具。

3．金融服务

目前，关联规则挖掘在金融服务行业中的应用也正在不断推广和深入。安全分析人员利用它分析大量的金融数据，进而找到与开发投资策略有关的交易与风险模型：信用卡公司可以通过对客户数据的挖掘，找出信用模式；股票公司利用关联规则挖掘分析股票价格走势。国外的一些金融企业已经开始运用这些技术指导管理和决策。信用卡公司、保险公司、股票交易所、银行机构对防止金融诈骗和金融犯罪有极高的兴趣和热情，通过对这些公司数据的挖掘，可以使它们能够识别潜在的风险，进而控制可能发生的损失。当然，关联规则挖掘技术还可以应用于股票选择、信誉评估、风险投资等方面。

4．通信、互联网、电子商务

关联规则挖掘除了在上述领域中应用之外，还对通信、互联网及电子商务领域的发展具有重要的作用。典型的例子是，在通信领域中用于诊断入侵模式，通过采集路由器中存留的有关信息，判断Hack（网络黑客）对系统的攻击行为和习惯，以提高通信的安全性。利用关联规则挖掘技术对互联网上的丰富数据资源进行挖掘，是目前该领域中的一个热点问题。如利用Web内容挖掘的结果提高搜索引擎的性能；Web结构挖掘的结果可以帮助网站的经营者重新设计网站的结构；Web使用挖掘规则可以理解用户的浏览模式及需求，以便在网站中提供个性化的功能，以满足不同用户的需求。由于互联网与电子商务技术的紧密结合，关联规则挖掘对于电子商务的促进作用是不言而喻的。

5．医疗保健行业

关联规则另一十分重要的应用领域是医疗行业，它能够帮助诊断测试、药物治疗、手术过程中效率的预测、服务管理和过程控制等。例如，在疾病症状的研究过程中，人们也许会发现，某些症状的出现一定会伴随其他一些症状的出现，通过对这种现象的深入研究，将会有助于疾病的诊断。