基于约束的关联规则挖掘方法

第四章　基于项约束的关联规则挖掘

自IBM Almaden研究中心的R．Agrawal等人提出了关联规则挖掘问题之后，关联规则挖掘的研究受到越来越多研究人员的关注。目前，关联规则挖掘已经逐步应用于商业、金融服务、政府机构、医药和科学研究等多个领域。眼下不少学者提出了多种多样的关联规则挖掘算法，但绝大多数算法都缺乏用户的主动参与，特别是在导航系统和用户控制方面的效率不高。在数据挖掘系统中，只有当计算机和用户分别承担其最擅长的工作的情况下，挖掘系统才有可能最大限度地发挥其效率。

传统的关联规则挖掘算法的一般过程是：针对给定的交易数据库DB，用户在挖掘的初始阶段设定最小支持度Smin和最小置信度Cmin，然后利用选定的挖掘算法对交易数据库DB进行挖掘。在整个挖掘过程中，用户需要面对的是百无聊赖的等待、等待、再等待。在对交易数据库DB进行了无数次扫描、匹配计算之后会得到大量的关联规则，但遗憾的是用户在经过痛苦而漫长的等待之后却又往往大失所望。这是因为挖掘结果中往往只有很少一部分是用户期望得到的，而其他很大一部分对用户而言可能没有太大的意义和价值。这正是由于在挖掘过程中缺乏用户的主动参与和引导，整个挖掘过程在很大程度上进行着暗箱作业造成的结果。如果整个挖掘过程的运行时间很短，这样的暗箱作业似乎还可以接受。但事实并非如此。由于关联规则挖掘的对象十分庞大，挖掘所需要的时间动辄几小时，甚至几天，这显然是用户难以容忍的。

实际上，在系统进行挖掘以前，用户往往在头脑中已经有了某种初始的想法。通常总希望了解关于某一特定方面的相关信息或知识。比如超市管理人员希望了解与某一特定商品相关的销售信息，而不是泛泛地发现全部商品的规则。另外，管理人员对不同商品的关注程度也不尽相同，他们通常对某些特定商品的销售，如新推广商品、高利润商品或滞销商品特别关注。这就要求关联规则挖掘能够满足用户的这一需要。我们称这一类挖掘问题为基于项约束的关联规则挖掘问题。基于项约束的关联规则挖掘问题是对一般关联规则挖掘问题的扩展。由于在挖掘过程中，用户对挖掘目标进行了相应的限制和约束，从而使挖掘更加具有针对性，挖掘得到的结果也更有价值。

一、项约束条件分类

确切地说，项约束条件可以分为两类。

一类是用户只对一部分规则感兴趣。比如规则中包含（不包含）某一特定项目或是概念层次树中某一特定项及其子项。对于这一类基于项约束的关联规则挖掘问题，我们可以利用原有的关联规则挖掘算法进行挖掘，然后通过后置处理对挖掘结果进行过滤。但是，如果能够有效地利用项约束条件约减数据库中事务的数量，并将约束条件结合到挖掘过程中，将会大幅度地提高算法的运行效率。

另一类项约束条件可以用如下的例子进行说明。形如关联规则：面包→牛奶（18%，75%），表示在所有的销售记录中，有18%的记录同时包含面包和牛奶，另外在所有购买了面包的销售记录中有75%的销售记录同时包含牛奶。在这种情况下，规则的兴趣度取决于面包和牛奶出现次数的多少。但在实际中，超市的管理人员往往对某些特定的商品，比如正在促销和新推广的商品、某些高利润商品或是某些滞销商品特别关注。我们可以通过给不同的项目（商品）设定不同的权值以表示用户对该项目（商品）的关注程度或是该项目（商品）的重要性程度。如在超市的日化经营部，洗发液的销售利润要比香皂的销售利润高，所以在“牙膏→洗发液”、“牙膏→香皂”这样两条关联规则中，显然管理人员对前者的兴趣度要高于后者。这就是第二类项约束条件的关联规则挖掘问题。我们也称这一类项约束条件的关联规则挖掘问题为加权关联规则挖掘。在这一类基于项约束条件的关联规则挖掘过程中不但需要考虑规则的支持度，同时还需要考虑各项目加权因子的影响。

我们分别对这两类项约束条件的关联规则挖掘问题进行分析，重点对第一类项约束条件下的关联规则挖掘问题进行深入的研究，在分析R．Srikant提出的MultipleJoins、Reoder和Direct算法的基础上，给出解决第一类基于项约束条件的关联规则挖掘的ARMIC算法，然后对第二类项约束条件下的关联规则挖掘问题（加权关联规则挖掘问题）进行分析。

二、第一类项约束问题

对于第一类项约束问题，我们通常以布尔表达式的形式来表示约束条件C，如（1∧2）∨（3∧4）是表示同时包含项目1和2或包含项目3和4的关联规则。对于这一类项约束条件的关联规则挖掘问题，有一种比较简单的处理方法，是采用现有的关联规则挖掘算法进行挖掘，然后通过后置处理对挖掘结果进行过滤，最后保留所有满足约束条件C的结果。下面以Apriori算法作为关联规则挖掘算法说明这样的处理过程。

输入：交易数据库DB

最小支持度Smin和最小置信度Cmin

项约束条件C

输出：满足约束条件C的关联规则R

算法基本步骤：

（1）利用Apriori算法生成所有的频繁项集；

（2）根据（1）得到的频繁项集和最小置信度生成所有的关联规则；

（3）对由（2）得到的关联规则利用Rules＿Pruning（R，C）进行剪枝，删除所有不满足给定项约束条件C的关联规则；

（4）得到所有满足约束条件C的关联规则。

虽然可以通过后置处理对挖掘结果进行过滤来达到规则约减的目的，但是我们在前期规则挖掘过程中需要计算交易数据库DB中所有的频繁项集并产生所有的关联规则，因而执行时间的消耗是相当可观的。其实我们可以充分利用项约束条件来约减交易数据库中事务记录的大小，并将项约束条件与候选频繁项集及关联规则的生成相结合，从而可以较大程度地提高算法的运行效率。

（一）问题定义

定义4．1　基于项约束条件C的关联规则就是形如的蕴涵式，其中成立的条件是：

（1）它具有支持度s，即交易数据库中至少有s%的记录包含X ∪Y；

（2）它具有置信度c，即在交易数据库中包含X的记录至少有c%同时也包含Y；

（3）它必须满足项约束条件C。

设C为I上的一个布尔表达式，将C转化为DNF形式，形如：d1∨d2∨…∨dn，其中每个di形如：di＝ai1∧ai2∧…∨aim，aij＝lij或者aij＝﹁lij。对于给定交易数据库DB和项约束条件布尔表达式C的关联规则挖掘问题来说，就是在给定交易数据库DB中发现所有满足用户设定的最小支持度Smin、最小置信度Cmin和项约束条件C的关联规则。

由于涉及的交易数据库中数据量往往十分庞大，而关联规则的挖掘需要对交易数据库进行多次扫描，因而算法的时间消耗很大。其实在增加项约束条件C后再寻找满足约束条件的频繁大项集时，我们只需要考虑交易数据库DB中与项约束条件C相关的一个数据子集，而不需要重复扫描全部数据集合。也就是说，可以利用项约束条件C对交易数据库DB进行过滤，只保留与项约束条件C相关的数据集合。设过滤后生成的数据库为DB′，DB′为DB中所有符合项约束条件C的事务的集合。

引理4．1　在交易数据库DB中满足项约束条件C的频繁项集在约减后的交易数据库DB′中也是频繁项集，且该频繁项集在两个数据集合中的支持数相同。

证明：假设有项集X满足项约束条件C，而且项集X在DB中为频繁项集，而在DB′中为弱项集。设最小支持度为Smin，根据假设有：在DB中，Support（X）≥Smin，而在DB′中，Support（X）＜Smin。

这说明符合项约束条件C的项集在DB和DB′中的支持数不同，即DB中有事务支持项集X但该事务却不属于DB′。这显然与DB′是所有符合项约束条件C的事务的集合相矛盾，因而假设不成立；由于包含项集X的事务都在DB′中，所以项集X在DB和DB′中的支持数必定相同，其对应于DB的支持度也必相同。需要指出的是，项集的支持度为项集的支持数与交易数据库DB中事务总量｜DB｜的比值。

设经过过滤后的约减数据库为DB′，｜DB′｜为DB′中交易事务的数量。

我们可以用数据约减率来表示利用项约束条件C对交易数据库DB进行数据过滤的效率。数据约减率Fil＿Ratio＝（｜DB｜－｜DB′｜）／｜DB｜，其中｜DB｜和｜DB′｜分别为交易数据库DB和过滤后的约减数据库DB′的记录数。从前面的数据约减过程可以得到，约减数据库的记录数｜DB′｜≤support（d1）＋support（d2）＋…＋support（dn），即取决于各di的支持度。例如项约束条件C为1∧2 ∧3，则约减后的交易数据库的记录数｜DB′｜＝Support（｛1　2　3｝），如果｛1　2　3｝在交易数据库DB中的支持度为10%，则约减率为90%。即通过数据约减可以过滤掉90%的事务记录。因而极大地减少了目标数据集合的大小，从而使提高算法的效率成为可能。

设读取一条事务记录并进行项集支持数计数的时间为τ，符合约束条件C的频繁项集的最大长度为λ，直接扫描交易数据库DB的使用时间为t，相对应的扫描约减数据库DB′的时间为t′，则我们分别可以得到：

t＝｜DB｜×（λ＋1）×τ＋｜DB｜×τ

t′＝｜DB｜×τ＋｜DB′｜×（λ＋1）×τ＋｜DB｜×τ

为了使t′小于t，需要：

整理后可以得到：

上式表明，当数据约减率大于1／（λ＋1）时，扫描约减后的交易数据库DB′比直接扫描交易数据库DB花费时间要少。随着λ的增大，上式较容易得到满足。

另外在数据存储方面，由于对交易数据库DB进行过滤后得到约减交易数据库DB′需要占用额外的存储空间，占用的空间与约减数据库DB′中的事务数量成正比。当交易数据库DB很大时，我们可以认为符合约束条件C的事务均匀分布在交易数据库DB中，则当扫描了交易数据库DB中的一部分事务后，就可以估计出约减率和约减数据库DB′所需要的存储空间，从而决定是否生成约减数据库DB′。如果交易数据库DB′中的事务不是均匀分布的，则可以采用抽样的方法，随机抽取部分事务判断是否满足数据约减率的要求。

所以根据上述分析，设用户设定的最小约减率为Fil＿Ratiomin，确定生成DB′前需要扫描交易数据库DB中事务百分比为ρ，我们可以将数据约减过程改为如下形式：

引理4．2　设项集X是约减数据库DB′中的弱项集，则即使项集X在交易数据库DB中是频繁项集，它也不可能是任何符合项约束条件C的频繁项集的子集。

证明：设有项集X在交易数据库DB中的支持度为Support （X）DB≥Smin，而在约减数据库DB′中的支持度为Support（X）DB′＜Smin。如果X为DB中某个满足项约束条件C的频繁项集的子集，则根据引理4．1，该频繁项集也一定是约减数据库DB′中的频繁项集，即有Support（X）DB′≥Smin，显然与前面的假设矛盾，所以项集X不是符合项约束条件C的频繁项集的一个子集。

所以，我们可以首先通过数据约减减小交易数据库DB中事务的数量，然后从约减数据库DB′中挖掘满足用户设定的最小支持度Smin、最小置信度Cmin和项约束条件C的关联规则。

（二）ARMIC算法分析

一般地，关联规则挖掘算法将挖掘问题分解为以下两个子问题：

☆　找出交易数据库DB中的频繁项集

☆　根据频繁项集和最小置信度生成关联规则

我们以Apriori算法为例简单说明一般关联规则的挖掘过程。Apriori算法在每次扫描过程中，首先利用上一次扫描得到的结果，即频繁（k－1）－项集Lk－1和Apriori＿gen函数生成候选频繁k－项集Ck，Ck是所有频繁k－项集Lk的超集；然后再次扫描数据库，将候选k－项集Ck中满足最小支持度的项集记入Lk，其余的予以剪枝；继续上述循环，直到不能生成新的候选项集时结束；Apriori算法通过对交易数据库的多次扫描最后得到交易数据库中所有的频繁项集；然后根据返回的频繁项集和最小置信度利用ap＿genrules生成所有的关联规则。

Apriori＿gen函数以频繁（k－1）－项集Lk－1为参数，首先把前（k－2）项完全相同的频繁（k－1）－项集Lk－1两两链接以获得候选k项集Ck的超集。然后根据“频繁项集的任意子集也必是频繁项集”的原则对候选项集Ck的超集进行剪枝，最后得到候选项集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｝｝，在剪枝阶段由于项集｛1　3　4　5｝的子集｛1　4　5｝不在L3中，所以删除项集｛1　3　4　5｝，最后得到的C4中仅保留项集｛1　2　3　4｝。

但是当存在项约束条件C的时候情况就要复杂得多。仍然以刚才的例子为例，假定我们希望得到所有包含项目2的关联规则，令L2为｛｛1　2｝，｛2　3｝｝，为了生成候选项集C3为｛1　2　3｝，则必须存在频繁2－项集｛｛1　2｝，｛1　3｝｝才能利用Apriori＿gen函数生成C3。但由于项集｛1　3｝不满足项约束条件C，因而在频繁2－项集生成结果中并不包含项集｛1　3｝，根据原有的候选项集生成算法就无法生成候选3－项集C3：｛1　2　3｝。为了解决这样的问题，R．Srikant提出了第一类项约束条件下的关联规则挖掘算法：MultipleJoins、Reorder和Direct算法。在给出我们的改进算法ARMIC之前，我们先简单分析这三种算法的基本框架。

为了叙述方便，我们分别定义各符号，如表4－1所示。

表4－1　基于项约束的关联规则挖掘相关的符号及含义

为简单起见，我们首先不考虑概念层次树的情况。R．Srikant将基于项约束条件的关联规则挖掘过程分为三个阶段。

第一阶段：发现所有满足项约束条件C的频繁项集。在这个过程中包括候选项集的生成和支持数的计数。前面的例子说明在有项约束条件的情况下候选项集生成方法与以往一般的关联规则挖掘算法中的候选项集生成方法有所不同。针对项约束条件下的候选项集的生成，R．Srikant给出了三种不同的算法：MultipleJoins、Reorder 和Direct算法。其中MultipleJoins和Reorder算法所生成的候选项集数目相同，效率也十分接近。其基本思想是首先构造入选项集合S，任何满足项约束条件C的项集至少包含入选项集合S中的一入选项，然后生成所有包含入选项的候选项集并对其支持数进行计数，并去除候选项集中所有不满足项约束条件C的频繁项集。而Direct算法则是直接利用项约束条件布尔表达式生成所有满足项约束条件C的候选项集，然后对候选项集中的元素进行支持数计数。

第二阶段：根据第一阶段得到的频繁项集和用户设定的最小置信度Cmin生成相应的关联规则。为了生成关联规则，我们需要知道频繁项集中所有子集的支持数。形如“AB→CD”这样的关联规则，由于需要知道项集AB的支持度才可以确定该规则的置信度，但由于项集AB可能并不满足项约束条件C，所以在第一阶段候选项集生成过程中根本没有生成项集AB，也就根本不可能清楚其支持数。因而必须再次扫描交易数据库DB，对各频繁项集的所有子集进行支持数计数。

第三阶段：根据前两阶段得到的频繁项集和最小置信度，生成所有的关联规则。

MultipleJoins和Reorder算法都是首先利用项约束条件C生成入选项集合S，使得任何满足项约束条件C的项集至少包含入选项集合S中的一项。如I＝｛1　2　3　4　5｝，C＝（1∧2）∨3，则S可以是｛1 3｝、｛2　3｝或｛1　2　3　4　5｝。我们可以利用如下的方法得到入选项集合S：

通过上式得到的入选项集合S将会满足：任何符合项约束条件C的非空项集至少包含S中的一项。

对于给定的项约束条件C可以有不同形式的入选项集合S。比如选择集合中各项目支持度总和最小的项目集合为入选项集合S，因为入选项集合S中项目的支持度直接与包含入选项的频繁项集的计算量有关，所以入选项集合的选择将会直接影响算法的执行时间。

另外，在项约束条件C中存在项不包含约束时I），由于这种约束具有很强的不确定性，如果以I－iij来替换﹁iij将会使符合项约束条件C的项集变得很大，从而降低了算法的效率。所以我们的方法是先忽略项不包含约束条件，然后在后续的过程中再对项不包含约束条件进行处理。

1．MultipleJoins算法

引理4．3　假定项集X是频繁（k＋1）－项集，其中k≥2。

（1）如果X的前（k－1）项中包含入选项，则存在两个前（k－1）项与X的前（k－1）项完全相同的频繁k－项集。

（2）如果X在后min（k－1，2）中包含入选项，则存在两个后（k －1）项与X的后（k－1）项完全相同的频繁k－项集。

（3）如果X是3－项集，而中间项为入选项，则存在两个频繁2－项集，其中X的中间项既是第一个频繁2－项集的后项，又是另一频繁2－项集的前项。

与引理相对应的是如下的三种连接方式，其中Join1与Apriori算法中的Apriori＿gen相同。

2．算法Reorder

Reorder算法首先利用生成然后对项集中的项目进行如下排序：项集中包含的入选项集合S中的项目总在其他非入选项的项目之前，而对于项集中相同类别（同属于入选项集合S或同不属于入选项集合S）的项目则按照其字典顺序进行排列；然后直接利用Apriori＿gen函数生成，从而简化了整个候选项集的生成过程。对于任意k＋1候选项集X，至少存在X的两个频繁k－项集子集，并且这两个频繁k－项集的前（k－1）项与X完全相同。表4－2和表4－3分别为Multiplejoins算法和Reorder算法的执行情况。

表4－2　MultipleJoins算法的执行情况

图4－3　Reorder算法的执行情况

3．Direct算法

算法Direct的过程可以简单描述如下：

我们以如下的例子说明Direct的执行情况：令I＝｛1，2，3，4，并且假设所有的1项集均为频繁项集。由算法Direct可以得到｛2　4｝，｛3　4｝，｛4　5｝｝，项集｛4　5｝由于不满足约束条件C而被剪枝。另外，由于项约束条件C中的项集｛1　2｝的支持度满足最小支持度要求，所以将项集｛1　2｝增加到当中，最后得到｛2　4｝，｛3　4｝｝。

4．ARMIC算法

与前面相对应，我们定义各符号如表4－4所示。

表4－4　ARMIC算法相关符号及含义

ARMIC算法在初始阶段也生成入选项集合S。然后利用生成最初的候选项集，并进行支持数计数，得到频繁项集。在后续的迭代过程中，候选项集的生成分为两部分：一部分是以算法Direct的方式生成候选项集；另外一部分则是首先对前一次循环得到的频繁项集进行排序，然后利用算法Reorder的候选项集生成方式生成新的候选项集。而在maxLen次迭代后直接利用算法Reorder求取新的候选项集和频繁项集。由于算法ARMIC在初始阶段直接利用项约束条件C生成候选项集，而不是像Reorder算法一样首先生成包含入选项的候选项集，所以ARMIC算法生成的候选项集要小于Reorder算法生成的候选项集。另外，由于在第maxLen次迭代后利用Reorder算法的生成方法生成候选项集和频繁项集，从而避免了Direct算法中的不必要的候选项集的扩散。后面的例子说明ARMIC算法的执行效率比Reorder和Direct算法都要高一些。

ARMIC算法（Association Rules Mining based Item Constraints）

输入：交易数据库DB

最小支持度Smin和最小置信度Cmin

项约束条件C

输出：满足项约束条件C的关联规则R

／／首先生成频繁1项集和di中的频繁项集

ARMIC算法将Reorder算法和Direct算法的优点结合在一起，从而使候选项集生成的初始阶段避免了Reorder算法中大量的初始项集计算，在中间阶段，则是将两者结合在一起，在候选项集生成的最后阶段又不至于像Direct算法那样迅速地扩张。在整个过程中候选项集都保持在最小的程度，从而提高了算法的效率。

Direct算法直接利用约束条件C生成候选项集，通过dk＋1生成候选项集，其中Reorder算法是根据项约束条件C首先生成入选项集合S，然后生成包含入选项集合S中某项的候选项集，接着对候选项集进行剪枝。而ARMIC算法则是将Direct算法与Reorder算法相结合。首先利用Direct算法生成最初的候选项集，然后在后续的迭代过程中候选项集的生成分为两部分：一部分是以Direct算法的方式生成候选项集；另外一部分则是首先对前一次循环得到的频繁项集进行排序，然后利用Reorder的候选项集生成方法生成新的候选项集。与Direct算法相比，ARMIC算法由于在后期避免了候选项集的快速扩张，因而产生的候选项集要小于利用Direct产生的候选项集。另外，由于在初始阶段采用了生成候选项集，从而避免了Reorder算法在前期候选项集生成时间上的消耗，所以ARMIC算法的效率比Direct算法和Reorder算法都有一定程度的提高。

我们以下面的例子来说明三种不同算法生成的候选项集大小的比较。设C＝1∧2∧3，入选项集合S＝｛1｝，F＝｛｛1｝，…，｛100｝｝，含入选项1的大2－项集、大3－项集分别为：L2＝｛｛1　2｝，…，｛1　10｝｝，L3＝｛｛1　2　3｝，…，｛1　5　6｝｝，L4＝｛｛1　2　3　4｝，…，｛1　3　4　5｝｝，L5＝｛｝。

表4－5　ARMIC算法的执行效率分析(www.xing528.com)

（三）第一类项约束问题的扩展

特别地，当约束条件C引入了多层次概念树后，项约束条件C就发生了变化。在引入多层次概念树之前，项约束条件C的形式是d1∨d2∨d3∨…∨dn，表达式在每个di的形式为ii1∧ii2∧…∧iim，iij可以是iij或﹁iij，iij∈I。由于多层次概念树的引入，iij还可以是Descendant（iij）或Anscestor（iij）或﹁Descendant（iij）或﹁Anscestor （iij）。这时可将Descendant（iij）扩展为iij∨i′ij∨i″ij∨…，将﹁Descendant（iij）扩展为﹁（iij∨i′ij∨i″ij∨…），其中i′ij，i″ij，…为iij的子孙；可以将Anscestor（iij）扩展为iij∨i′ij∨i″ij∨…，将﹁Anscestor（iij）扩展为﹁（iij∨iij∨i′ij∨i″ij∨…），其中i′ij，i″ij，…为iij的祖先。

当然，我们完全可以扩展前面的基于项约束条件的关联规则挖掘算法来解决引入多层次概念树之后的项约束条件下的关联规则挖掘问题。也可以将上述算法与Cumulate算法相结合来实现基于项约束条件的多层次关联规则的挖掘。

三、第二类项约束问题

前面我们已经简单介绍了第二类项约束条件下的关联规则挖掘问题。仍然以超市日化经营部的销售为例，由于洗发液的销售利润要高于香皂的销售利润，所以管理人员对关联规则“牙膏→洗发液”的关注程度比关联规则“牙膏→香皂”显然要高一些。在实际中，用户对不同的项目并非是一视同仁的。用户往往会对某些特定的项目特别感兴趣，而对另外一些项目则相对关心得较少。因此，要求关联规则的挖掘过程能够体现并满足用户的这一需要。在挖掘的初始阶段，用户通过给不同的项目设定不同的加权值以表示用户对不同项目的关注程度或者说明不同项目的重要性程度。我们也称这一类项约束条件的关联规则挖掘问题为加权关联规则挖掘问题。在加权关联规则挖掘过程中不但需要考虑规则的支持度，同时还需要考虑各项目加权因子的影响。

（一）问题描述

由于加权因子的影响，原来关联规则挖掘的评估参数（如最小支持度）就要做相应的改变，以能够满足加权关联规则挖掘的需要。

定义4．2　对于给定的项目I＝｛i1，i2，…，in｝，为每个项目ij设定加权值wj以表示用户对该项目的关注程度，有0≤wj≤1，j＝｛1， 2，…，n｝。与原来的关联规则支持度相对应，我们定义加权关联规则的加权支持度Swmin为：

当k项集X的加权支持度小于用户给定的最小加权支持度Swmin时，我们称该项集为弱项集，否则为频繁项集：

如果k项集X为频繁项集，则其支持数必满足：

下面以日化经营部的销售情况为例说明加权关联规则的挖掘。表4－6所示为不同类别的商品、每种类别商品的平均利润率及管理人员对每种类别商品销售情况关注程度的加权值。表4－7表示日化经营部的销售记录，每条销售记录都有唯一的交易TID及所购买的商品。

为简单起见，我们分别以数字代表不同类别的商品。管理人员希望了解不同商品之间的关联，要求列出那些加权支持度大于40%的关联规则。

表4－6　商品及其加权因子情况

表4－7　商品销售记录信息

在表4－6中有五种不同类别的商品，而在表4－7中有7条交易记录。设最小加权支持度Swmin为0．4，则根据前面加权关联规则的相关定义可以得到：项集｛2　5｝是频繁项集，这是因为项集｛2　5｝的加权支持度为：（0．3＋0．9）×5／7＝0．86≥0．4。同样的，项集｛4　5｝和｛2　4　5｝也是频繁项集。我们试图在加权因子与项集支持度之间谋求某种平衡。与原来的关联规则挖掘不同的是，我们必须面对各项目的加权因子、项集的支持度和规则置信度三个不同参数。如果我们将加权因子和项集的支持度割裂开来，则我们只能发现同时满足加权因子和项集支持度约束的频繁项集。正如我们前面提到的，加权因子是表现项目（商品）重要性程度的参数。例如某种正处于促销推广阶段的商品或是某种高利润的商品，即便这种商品的销售量不是很大（项集支持度较小），也是管理人员十分关注的对象。另一方面，用户虽然对某种商品的关注程度相对较低，但如果这种商品相当热销（项集支持度较大），这样的信息显然也是很有价值的。

（二）MINWAL系列算法

一种比较直观的方法是忽略加权值较小的项目。但实际上，关联规则往往是由加权值较大的项目和加权值较小的项目组成的。比如日化经营部的管理人员十分关注“洗发液”的销售，所以“洗发液”的加权值相对较大。与其相对的，由于“牙膏”的销售利润较低，所以其加权值也相对较小。通过挖掘后，我们发现“洗发液”的销售通常会受到“牙膏”销售情况的影响，即关联规则“牙膏→洗发液”具有很高的加权支持度，所以在挖掘过程中忽略加权值较小的项目是不可取的。这将会使我们失去很多相当有价值的规则。

现有的关联规则挖掘算法不能直接应用于加权关联规则的挖掘。因为绝大多数算法都是利用频繁项集的任意子集也必是频繁项集的剪枝原则对候选项集进行剪枝，缩减了候选项集的大小，减少了模式匹配的次数，从而提高了算法的挖掘效率。但是在考虑加权因子影响的情况时，上述的剪枝原则就不再适用了。例如前面表4－6和表4－7中，｛1　2　4　5｝的加权支持度为：

（0．1＋0．3＋0．8＋0．9）×2／7＝0．6

项集｛1　2　4　5｝的加权支持度大于最小加权支持度，所以项集｛1 2　4　5｝是频繁项集。项集｛1　2｝是频繁项集｛1　2　4　5｝的子集，但是我们可以得到项集｛1　2｝的加权支持度为：

（0．1＋0．3）×2／7＝0．11

可见项集｛1　2｝虽然是频繁项集｛1　2　4　5｝的子集，但其加权支持度小于最小加权支持度，因而项集｛1　2｝是弱项集。由此可见，原有的关联规则挖掘算法的剪枝原则不能直接应用于加权关联规则的挖掘。所以在加权关联规则的挖掘过程中，我们不但需要考虑项集的支持度而且需要关注不同项目加权因子的影响。

假定项集Y是q项集，其中q＜k。在其余的（I－Y）个项目中，按项目的加权值从大到小进行排序，则前（k－q）项目为我们可以得到包含项集Y的任意k项集的最大加权值为：

其中等式右边的第一项是项集Y各项目加权值的和，而第二项是其余（k－q）项中最大加权值的和。所以包含项集Y的频繁k－项集的最小支持数至少为：

我们称X（Y，k）．Supmin为包含项集Y的频繁k项集的最小支持数；

例：令Y＝｛2　4｝，则有：

也就是说如果项集｛2　4｝是频繁3项集的子集，则其支持数必须不小于2。根据这一性质，C．H．Cai等人提出了加权关联规则挖掘的MINWAL（O）和MINWAL（W）算法。

为了叙述方便，定义相关的符号如表4－8所示。

表4－8　加权关联规则相关符号及含义

算法MINWAL（O）

输入：交易数据库DB，最小加权支持度Swmin和最小置信度Cmin

各项目的加权因子wj

输出：用户关注的关联规则集R

Function MINWAL（DB，Swmin，Cmin，wj）

／／扫描目标数据集，确定频繁项集的最大长度；

Maxitemset＝Scan（DB）；

L＝｛｝；

for（i＝1；i≤Maxitemset；i＋＋｝do

Ci＝Li＝｛｝；

for all transanction t∈DB do｛

／／扫描目标数据集DB，计算所有1项集的支持数，并且计算包含1项集的所有大k（1＜k≤Maxitemset）项集的最小支持数；将支持数小于所有包含该项集的大k项集最小支持数的1项集进行剪枝；

MINWAL（0）算法的基本框架与Apriori算法十分相似，但实际上两者之间有着明显的差别。正如前面指出的加权关联规则挖掘中不能使用频繁项集的任意子集也必是频繁项集的剪枝原则进行剪枝，故而不能像Apriori算法那样生成候选项集。从前面的分析可以得到：如果项集X的支持数小于任何包含该项集的频繁k－项集的最小支持数，则项集X不可能是长度更长的频繁项集的子集。所以我们可以通过比较项集X的支持数与包含项集X的频繁k－项集的支持数对候选项集进行剪枝。

但是，如果进一步研究会发现，算法MINWAL（0）存在如下的问题：即便项集X中的项目的加权因子都很小，但如果项集X中的项目数足够大，加权因子之和也将会足够大。在很多时候，这样的情况并不值得关注，我们也可以通过对加权因子的标准化来解决这样的问题。因此，我们需要对加权关联规则的有关定义作相应的修改。

定义4．3　对于给定的所有项目I＝｛i1，i2，…，in｝，为每个项目ij设定加权值wj以表示用户对不同项目的关注程度，即0≤wj≤1，j＝｛1，2，…，n｝，则与原来的支持度定义相对应，我们可以定义相应的加权关联规则支持度为：

相对应地，当k项集X的加权支持度小于用户给定的最小加权支持度时，我们称该项集为弱项集，否则，则为频繁k－项集：

如果k项集X为频繁项集，则其支持数为：

假定项集Y是q项集，其中q＜k，在其余的（I－Y）个项目中，按加权值从大到小进行排序，则前（k－q）项目为ir1，ir2，…，irk－q，则我们可以得到包含项集Y的任意k项集的最大加权值为：

其中等式右边的第一项是项集Y各项目加权值的和，而第二项是其余（k－q）最大加权值的和。所以包含项集Y的大k项集的最小支持数至少为：

我们称X（Y，k）．Supmin为包含项集Y的频繁k－项集的最小支持数。

仍然可以利用前面的MINWAL（0）算法来处理加权因子标准化后的加权关联规则挖掘问题，针对这样的情况又给出了MINWAL（W）算法。

定义4．4　设项集X＝｛i1，i2，…，in｝中项目的最小加权因子为wj，如果项集Y＝X∪Z，并且Z中各项目的加权因子都小于wj，则称项集Y为项集X的低序超集；另外，如果Y＞X，而且Y中各项目的加权因子均不小于X－Y中项目的加权因子，则我们称项集Y为项集X的高序子集。

引理4．4　如果项集X是频繁项集，则X的所有高序子集都是频繁项集。

证明：设Y是X的高序子集，显然Y的支持度要大于X的支持度。另外，由于Y是X的高序子集，根据定义有Y的加权因子的平均值不小于X的加权因子的平均值，所以项集Y的加权支持度大于X的加权支持度，可见项集Y是频繁项集。

引理4．5　如果项集X是频繁（k＋1）－项集，则X一定是某些频繁k项集的低序超集。

证明：由于项集X是频繁项集，由引理4．4得到X的高序子集必是频繁项集。令X中加权值最小的项目为x，则Y＝X－x是X的高序子集，Y是频繁k－项集。也就是说，X是Y的低序超集。

根据上述引理我们可以对前面的算法进行修正，各符号含义与前面基本相同，只是最小加权支持度改为标准化后的最小加权支持度。

MINWAL（W）算法

输入：交易数据库DB，最小的加权支持度Swmin和最小置信度Cmin

各项目的加权因子wj

输出：用户关注的关联规则集R

Function MINWAL（DB，Swmin，Cmin，wj）

／／扫描目标数据集，确定大项集的最大长度

Maxitemset＝Scan（DB）

L＝｛｝

for（k＝1；k≤Maxitemset；i＋＋）do

Ci＝Li＝｛｝

for all transanction t∈DB do｛

／／扫描目标数据集DB，计算所有1项集的支持数；并且计算包含1项集的所有大k（1＜k≤Maxitemset）项集的最小支持数；将支持数小于所有包含该项集的大k项集最小支持数的1项集进行剪枝；

与MINWAL（0）算法相比，MINWAL（W）算法在候选项集的生成方面有所不同。后者充分利用了前面的引理：任何频繁（k＋1）－项集必是某些频繁k－项集的超集。所以Candidate＿Gen充分利用这一性质生成候选项集。例如：项目｛1，2，3，4，5｝对应的加权因子序列为w1≤w2≤w3≤w4≤w5，项集｛3　5｝是频繁项集，则根据引理我们可以得到｛1　3　5｝和｛2　3　5｝是候选3－项集。而｛3　4　5｝不是候选3－项集，除非项集｛4　5｝是大频繁－项集。

为了测试加权关联规则挖掘算法MINWAL（O）和MINWAL （W）的性能，我们在一台主频为P4　3．0G、2G内存，运行Windows XP操作系统的计算机上进行了测试。为了比较两种算法的效率，我们用测试数据生成方法生成测试数据库，测试数据库的参数如表4－9所示。

表4－9　测试数据相关符号及含义

图4－1表示在不同的最小加权支持度条件下对加权因子进行标准化后的加权关联规则挖掘的执行情况，我们可以看出，随着最小加权支持度的增大，挖掘所需要的时间相应地减少。

图4－2表示随着测试数据库的变化算法执行时间的消耗情况。由图可以看出，随着测试数据库的增大，算法的执行时间也相应地增加。也就是说算法具有良好的可扩展性。

图4－1　加权因子标准化条件下的执行情况

图4－2　交易数据集变化条件下的执行情况

四、项约束关联规则的并行挖掘

由于数据库中数据量的快速增长以及分布式数据库应用的日益普及，用单一的计算机对庞大的数据库进行挖掘变得越来越困难。为了提高挖掘的效率，可以通过两种途径来加以解决。一种是产生高效率的挖掘算法，对经过集成的中心数据库进行挖掘，但这显然不是最理想的解决方案。另外一种是充分利用计算机网络技术和计算机系统结构的改进对中心数据库进行并行的挖掘。计算机网络、内外存和处理器的快速发展为我们对数据库进行并行挖掘创造了条件。我们可以通过多台计算机协同工作来发现所有满足约束条件的关联规则，从而使挖掘效率有较大程度的提高。

并行计算模型是建立在各工作站的局域网互联的基础上，每台工作站有各自的内存，数据库中数据储存在各计算机共享的存储器中。这样的计算模型在计算机网络互联高度发达，各高性能工作站通过网络互联而构成工作站集群系统的今天很有意义。

设有n台计算机参与整个并行挖掘过程，我们可以选择其中配置较好的计算机作为主控计算机，整个挖掘过程如下所示：

1．将数据库均匀地分为n个部分；

2．主控计算机生成所有的候选1－项集；

3．各台计算机并行地扫描对应的数据子集，计算所有候选1－项集支持数；

4．主控计算机计算包含候选1－项集的所有大k（1＜k≤Maxitemset）集的最小支持数，并对各台计算机的反馈结果进行汇总，然后对候选项集进行剪枝，删除那些不可能成为大k项集的元素；

5．循环（k＝2；Ck－1≠Φ；k＋＋）do begin；

6．主控计算机生成候选k－项集，然后各计算机各自扫描对应的数据子集，计算包含候选k－项集的所有频繁k（1＜k≤Maxitemset）项集的最小支持数，删除不可能成为频繁项集的元素；

7．循环结束，主控计算机返回最终结果。

由于各计算机并行地扫描各自对应的数据子集，所以从理论上讲，并行挖掘算法的效率是原来单机挖掘算法效率的n倍。但在实际的挖掘过程中，由于各计算机处理性能的不平衡性，往往会出现运算快的计算机等待运算较慢的计算机的情况，从而使并行挖掘的效率有所降低。另外，数据的网络传输也会降低算法的效率。我们可以通过合理的作业调度和数据库的划分，使各计算机的负载趋于平衡，减少数据的网络传输。比如某台计算机处于空闲状态时，可以让空闲的计算机去分担那些计算负荷较大的处理机的任务。

数据挖掘面临的最大挑战是计算效率问题。解决这一问题的途径是产生高效的数据挖掘算法或并行处理，而两者之间的结合更具有吸引力。随着信息数量的急剧膨胀，高效的并行挖掘算法的研究是十分重要的。