关联规则挖掘综述
蔡伟杰 张晓辉 朱建秋 朱扬勇（复旦大学计算机科学系 上海200433）摘要：本文介绍了关联规则挖掘的研究情况，提出了关联规则的分类方法，对一些典型算法进行了分析和评价，指出传统关联规则衡量标准的不足，归纳出关联规则的价值衡量方法，展望了关联规则挖掘的未来研究方向。关键词：数据挖掘，关联规则，频集，OLAP1 引言数据挖掘（Data Mining），又称数据库中的知识发现（Knowledge Discovery in Database），在最近几年里已被数据库界所广泛研究，其中关联规则（Association Rules）的挖掘是一个重要的问题。关联规则是发现交易数据库中不同商品（项）之间的联系，这些规则找出顾客购买行为模式，如购买了某一商品对购买其他商品的影响。发现这样的规则可以应用于商品货架设计、货存安排以及根据购买模式对用户进行分类。Agrawal等于1993年首先提出了挖掘顾客交易数据库中项集间的关联规则问题，以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。他们的工作包括对原有的算法进行优化，如引入随机采样、并行的思想等，以提高算法挖掘规则的效率；对关联规则的应用进行推广。最近也有独立于Agrawal的频集方法的工作，以避免频集方法的一些缺陷，探索挖掘关联规则的新方法。同时随着OLAP技术的成熟和应用，将OLAP和关联规则结合也成了一个重要的方向。也有一些工作注重于对挖掘到的模式的价值进行评估，他们提出的模型建议了一些值得考虑的研究方向。本文第二部分是对关联规则基本概念的介绍，提出了关联规则的分类方法；第三部分是对挖掘算法的介绍，从经典的apriori开始，然后描述了对该算法的优化拓展，接着讲述脱离apriori算法的方法，最后是多层、多维的关联规则挖掘；第四部分归纳出关联规则价值衡量方法，主要从两个方面进行考虑：系统客观层面和用户主观层面；最后展望了关联规则挖掘的未来研究方向。2 关联规则的基本概念2.1 基本概念和问题描述设I={i1, i2,…, im}是二进制文字的集合，其中的元素称为项(item)。记D为交易(transaction)T的集合，这里交易T是项的集合，并且TI 。对应每一个交易有唯一的标识，如交易号，记作TID。设X是一个I中项的集合，如果X吀，那么称交易T包含X。一个关联规则是形如X夀萀瑶涵式，这里XI, YI，并且X夀=F。规则X夀在交易数据库D中的支持度（support）是交易集中包含X和Y的交易数与所有交易数之比，记为support(X夀)，即support(X夀)=|{T:X夀吀，TD}|/|D|规则X夀在交易集中的可信度（confidence）是指包含X和Y的交易数与包含X的交易数之比，记为confidence(X夀)，即confidence(X夀)=|{T: X夀吀，TD}|/|{T:X吀，TD}|给定一个交易集D，挖掘关联规则问题就是产生支持度和可信度分别大于用户给定的最小支持度(minsupp)和最小可信度(minconf)的关联规则。2.2 关联规则的种类我们将关联规则按不同的情况进行分类：1. 基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的关系；而数值型关联规则可以和多维关联或多层关联规则结合起来，对数值型字段进行处理，将其进行动态的分割，或者直接对原始的数据进行处理，当然数值型关联规则中也可以包含种类变量。例如：性别=“女”=>职业=“秘书” ，是布尔型关联规则；性别=“女”=>avg（收入）=2300，涉及的收入是数值类型，所以是一个数值型关联规则。2. 基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。在单层的关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同的层次的；而在多层的关联规则中，对数据的多层性已经进行了充分的考虑。例如：IBM台式机=>Sony打印机，是一个细节数据上的单层关联规则；台式机=>Sony打印机，是一个较高层次和细节层次之间的多层关联规则。3. 基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。在单维的关联规则中，我们只涉及到数据的一个维，如用户购买的物品；而在多维的关联规则中，要处理的数据将会涉及多个维。换成另一句话，单维关联规则是处理单个属性中的一些关系；多维关联规则是处理各个属性之间的某些关系。例如：啤酒=>尿布，这条规则只涉及到用户的购买的物品；性别=“女”=>职业=“秘书”，这条规则就涉及到两个字段的信息，是两个维上的一条关联规则。给出了关联规则的分类之后，在下面的分析过程中，我们就可以考虑某个具体的方法适用于哪一类规则的挖掘，某类规则又可以用哪些不同的方法进行处理。3 关联规则挖掘的算法3.1 经典频集方法Agrawal等于1993年首先提出了挖掘顾客交易数据库中项集间的关联规则问题，其核心方法是基于频集理论的递推方法。以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。他们的工作包括对原有的算法进行优化，如引入随机采样、并行的思想等，以提高算法挖掘规则的效率；提出各种变体，如泛化的关联规则、周期关联规则等，对关联规则的应用进行推广。3.1.1 核心算法Agrawal等在1993年设计了一个基本算法，提出了挖掘关联规则的一个重要方法 — 这是一个基于两阶段频集思想的方法，将关联规则挖掘算法的设计可以分解为两个子问题：
[*]找到所有支持度大于最小支持度的项集（Itemset），这些项集称为频集（Frequent Itemset)。
[*]使用第1步找到的频集产生期望的规则。
这里的第2步相对简单一点。如给定了一个频集Y=I1I2...Ik，k2，Ij∈I，产生只包含集合{I1，I2，...，Ik}中的项的所有规则(最多k条)，其中每一条规则的右部只有一项，(即形如Ii，"1椀欀)，这里采用的是中规则的定义。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。对于规则右部含两个以上项的规则，在其以后的工作中进行了研究，本文后面考虑的是这种情况。为了生成所有频集，使用了递推的方法。其核心思想如下：
[*]L1 = {large 1-itemsets};
[*]for (k=2; Lk-1F; k++) do begin
[*]Ck=apriori-gen(Lk-1); //新的候选集
[*]for all transactions tD do begin
[*]Ct=subset(Ck,t); //事务t中包含的候选集
[*]for all candidates c Ctdo
[*]c.count++;
[*]end
[*]Lk={c Ck |c.count洀椀渀猀甀瀀紀
[*]end
[*]Answer=欀Lk;
首先产生频繁1-项集L1，然后是频繁2-项集L2，直到有某个r值使得Lr为空，这时算法停止。这里在第k次循环中，过程先产生候选k-项集的集合Ck，Ck中的每一个项集是对两个只有一个项不同的属于Lk-1的频集做一个(k-2)-连接来产生的。Ck中的项集是用来产生频集的候选集，最后的频集Lk必须是Ck的一个子集。Ck中的每个元素需在交易数据库中进行验证来决定其是否加入Lk，这里的验证过程是算法性能的一个瓶颈。这个方法要求多次扫描可能很大的交易数据库，即如果频集最多包含10个项，那么就需要扫描交易数据库10遍，这需要很大的I/O负载。在论文中，Agrawal等引入了修剪技术（Pruning）来减小候选集Ck的大小，由此可以显著地改进生成所有频集算法的性能。算法中引入的修剪策略基于这样一个性质：一个项集是频集当且仅当它的所有子集都是频集。那么，如果Ck中某个候选项集有一个(k-1)-子集不属于Lk-1，则这个项集可以被修剪掉不再被考虑，这个修剪过程可以降低计算所有的候选集的支持度的代价。文中，还引入杂凑树（Hash Tree）方法来有效地计算每个项集的支持度。3.1.2 频集算法的几种优化方法
虽然Apriori算法自身已经进行了一定的优化，但是在实际的应用中，还是存在不令人满意的地方，于是人们相继提出了一些优化的方法。1. 基于划分的方法。
Savasere等设计了一个基于划分(partition)的算法，这个算法先把数据库从逻辑上分成几个互不相交的块，每次单独考虑一个分块并对它生成所有的频集，然后把产生的频集合并，用来生成所有可能的频集，最后计算这些项集的支持度。这里分块的大小选择要使得每个分块可以被放入主存，每个阶段只需被扫描一次。而算法的正确性是由每一个可能的频集至少在某一个分块中是频集保证的。上面所讨论的算法是可以高度并行的，可以把每一分块分别分配给某一个处理器生成频集。产生频集的每一个循环结束后，处理器之间进行通信来产生全局的候选k-项集。通常这里的通信过程是算法执行时间的主要瓶颈；而另一方面，每个独立的处理器生成频集的时间也是一个瓶颈。其他的方法还有在多处理器之间共享一个杂凑树来产生频集。更多的关于生成频集的并行化方法可以在中找到。2. 基于hash的方法。
一个高效地产生频集的基于杂凑(hash)的算法由Park等提出来。通过实验我们可以发现寻找频集主要的计算是在生成频繁2-项集Lk上，Park等就是利用了这个性质引入杂凑技术来改进产生频繁2-项集的方法。3.基于采样的方法。
基于前一遍扫描得到的信息，对此仔细地作组合分析，可以得到一个改进的算法，Mannila等先考虑了这一点，他们认为采样是发现规则的一个有效途径。随后又由Toivonen进一步发展了这个思想，先使用从数据库中抽取出来的采样得到一些在整个数据库中可能成立的规则，然后对数据库的剩余部分验证这个结果。Toivonen的算法相当简单并显著地减少了I/O代价，但是一个很大的缺点就是产生的结果不精确，即存在所谓的数据扭曲(data skew)。分布在同一页面上的数据时常是高度相关的，可能不能表示整个数据库中模式的分布，由此而导致的是采样5%的交易数据所花费的代价可能同扫描一遍数据库相近。Lin和Dunham在中讨论了反扭曲(Anti-skew)算法来挖掘关联规则，在那里他们引入的技术使得扫描数据库的次数少于2次，算法使用了一个采样处理来收集有关数据的次数来减少扫描遍数。Brin等提出的算法使用比传统算法少的扫描遍数来发现频集，同时比基于采样的方法使用更少的候选集，这些改进了算法在低层的效率。具体的考虑是，在计算k-项集时，一旦我们认为某个(k+1)-项集可能是频集时，就并行地计算这个(k+1)-项集的支持度，算法需要的总的扫描次数通常少于最大的频集的项数。这里他们也使用了杂凑技术，并提出产生“相关规则”（Correlation Rules）的一个新方法，这是基于他们的工作基础上的。4. 减少交易的个数。
减少用于未来扫描的事务集的大小。一个基本的原理就是当一个事务不包含长度为k的大项集，则必然不包含长度为k+1的大项集。从而我们就可以将这些事务移去，这样在下一遍的扫描中就可以要进行扫描的事务集的个数。这个就是AprioriTid的基本思想。3.2 其他的频集挖掘方法上面我们介绍的都是基于Apriori的频集方法。即使进行了优化，但是Apriori方法一些固有的缺陷还是无法克服：
[*]可能产生大量的候选集。当长度为1的频集有10000个的时候，长度为2的候选集个数将会超过10M。还有就是如果要生成一个很长的规则的时候，要产生的中间元素也是巨大量的。
[*]无法对稀有信息进行分析。由于频集使用了参数minsup，所以就无法对小于minsup的事件进行分析；而如果将minsup设成一个很低的值，那么算法的效率就成了一个很难处理的问题。
下面将介绍两种方法，分别用于解决以上两个问题。在中提到了解决问题1的一种方法。采用了一种FP-growth的方法。他们采用了分而治之的策略：在经过了第一次的扫描之后，把数据库中的频集压缩进一棵频繁模式树（FP-tree），同时依然保留其中的关联信息。随后我们再将FP-tree分化成一些条件库，每个库和一个长度为1的频集相关。然后再对这些条件库分别进行挖掘。当原始数据量很大的时候，也可以结合划分的方法,使得一个FP-tree可以放入主存中。实验表明，FP-growth对不同长度的规则都有很好的适应性，同时在效率上较之apriori算法有巨大的提高。第二个问题是基于这个的一个想法：apriori算法得出的关系都是频繁出现的，但是在实际的应用中，我们可能需要寻找一些高度相关的元素，即使这些元素不是频繁出现的。在apriori算法中，起决定作用的是支持度，而我们现在将把可信度放在第一位，挖掘一些具有非常高可信度的规则。在中介绍了对于这个问题的一个解决方法。整个算法基本上分成三个步骤：计算特征、生成候选集、过滤候选集。在三个步骤中，关键的地方就是在计算特征时Hash方法的使用。在考虑方法的时候，有几个衡量好坏的指数：时空效率、错误率和遗漏率。基本的方法有两类：Min_Hashing(MH)和Locality_Sensitive_Hashing(LSH)。Min_Hashing的基本想法是：将一条记录中的头k个为1的字段的位置作为一个Hash函数。Locality_Sentitive_Hashing的基本想法是：将整个数据库用一种基于概率的方法进行分类，使得相似的列在一起的可能性更大，不相似的列在一起的可能性较小。我们再对这两个方法比较一下。MH的遗漏率为零，错误率可以由k严格控制，但是时空效率相对的较差。LSH的遗漏率和错误率是无法同时降低的，但是它的时空效率却相对的好很多。所以应该视具体的情况而定。最后的实验数据也说明这种方法的确能产生一些有用的规则。3.3 多层和多维关联规则的挖掘随着数据仓库和OLAP技术研究的深入，可以预见大量的数据将经过整合、预处理，从而存入数据仓库之中。在当前，大多数的数据仓库的应用都是进行统计、建立多维以及OLAP的分析工作。随着数据挖掘研究的深入，已经有了OLAP和数据挖掘相结合的方法。首先一个有效的数据挖掘方法应该可以进行探索性的数据分析。用户往往希望能在数据库中穿行，选择各种相关的数据，在不同的细节层次上进行分析，以各种不同的形式呈现知识。基于OLAP的挖掘就可以提供在不同数据集、不同的细节上的挖掘，可以进行切片、切块、展开、过滤等各种对规则的操作。然后再加上一些可视化的工具，就能大大的提高数据挖掘的灵活性和能力。接着，我们来看一下多层和多维关联规则的定义。多层关联规则：对于很多的应用来说，由于数据分布的分散性，所以很难在数据最细节的层次上发现一些强关联规则。当我们引入概念层次后，就可以在较高的层次上进行挖掘。虽然较高层次上得出的规则可能是更普通的信息，但是对于一个用户来说是普通的信息，对于另一个用户却未必如此。所以数据挖掘应该提供这样一种在多个层次上进行挖掘的功能。多层关联规则的分类：根据规则中涉及到的层次，多层关联规则可以分为同层关联规则和层间关联规则。多层关联规则的挖掘基本上可以沿用“支持度-可信度”的框架。不过，在支持度设置的问题上有一些要考虑的东西。同层关联规则可以采用两种支持度策略：
[*]统一的最小支持度。对于不同的层次，都使用同一个最小支持度。这样对于用户和算法实现来说都比较的容易，但是弊端也是显然的。
[*]递减的最小支持度。每个层次都有不同的最小支持度，较低层次的最小支持度相对较小。同时还可以利用上层挖掘得到的信息进行一些过滤的工作。
层间关联规则考虑最小支持度的时候，应该根据较低层次的最小支持度来定。多维关联规则：以上我们研究的基本上都是同一个字段的值之间的关系，比如用户购买的物品。用多维数据库的语言就是单维或者叫维内的关联规则，这些规则一般都是在交易数据库中挖掘的。但是对于多维数据库而言，还有一类多维的关联规则。例如：年龄（X，“20...30”）职业（X,“学生”）==> 购买(X，“笔记本电脑”)在这里我们就涉及到三个维上的数据：年龄、职业、购买。根据是否允许同一个维重复出现，可以又细分为维间的关联规则（不允许维重复出现）和混合维关联规则（允许维在规则的左右同时出现）。年龄（X，“20...30”）购买(X，“笔记本电脑”) ==> 购买(X，“打印机”)这个规则就是混合维关联规则。在挖掘维间关联规则和混合维关联规则的时候，还要考虑不同的字段种类：种类型和数值型。对于种类型的字段，原先的算法都可以处理。而对于数值型的字段，需要进行一定的处理之后才可以进行。处理数值型字段的方法基本上有以下几种：
[*]数值字段被分成一些预定义的层次结构。这些区间都是由用户预先定义的。得出的规则也叫做静态数量关联规则。
[*]数值字段根据数据的分布分成了一些布尔字段。每个布尔字段都表示一个数值字段的区间，落在其中则为1，反之为0。这种分法是动态的。得出的规则叫布尔数量关联规则。
[*]数值字段被分成一些能体现它含义的区间。它考虑了数据之间的距离的因素。得出的规则叫基于距离的关联规则。
[*]直接用数值字段中的原始数据进行分析。使用一些统计的方法对数值字段的值进行分析，并且结合多层关联规则的概念，在多个层次之间进行比较从而得出一些有用的规则。得出的规则叫多层数量关联规则。
在OLAP中挖掘多层、多维的关联规则是一个很自然的过程。因为OLAP本身的基础就是一个多层多维分析的工具，只是在没有使用数据挖掘技术之前，OLAP只能做一些简单的统计，而不能发现其中一些深层次的有关系的规则。当我们将OLAP和DataMining技术结合在一起就形成了一个新的体系OLAM（On-Line Analytical Mining）。4 关联规则价值衡量的方法当我们用数据挖掘的算法得出了一些结果之后，数据挖掘系统如何知道哪些规则对于用户来说是有用的、有价值的？这里有两个层面：用户主观的层面和系统客观的层面。4.1 系统客观层面：很多的算法都使用“支持度-可信度”的框架。这样的结构有时会产生一些错误的结果。看如下的一个例子：假设一个提供早餐的零售商调查了4000名学生在早晨进行什么运动，得到的结果是2200名学生打篮球，2750名学生晨跑，1800名学生打篮球、晨跑。那么如果设minsup为40%，minconf为60%，我们可以得到如下的关联规则：打篮球栀跑 （1）这条规则其实是错误的，因为晨跑的学生的比例是68%，甚至大于60%。然而打篮球和晨跑可能是否定关联的，即当我们考虑如下的关联时：打篮球（不）晨跑 （2）虽然这条规则的支持度和可信度都比那条蕴涵正向关联的规则（1）低，但是它更精确。 然而，如果我们把支持度和可信度设得足够低，那么我们将得到两条矛盾的规则。但另一方面，如果我们把那些参数设得足够高，我们只能得到不精确的规则。总之，没有一对支持度和可信度的组合可以产生完全正确的关联。于是人们引入了兴趣度，用来修剪无趣的规则，即避免生成“错觉”的关联规则。一般一条规则的兴趣度是在基于统计独立性假设下真正的强度与期望的强度之比，然而在许多应用中已发现，只要人们仍把支持度作为最初的项集产生的主要决定因素，那么要么把支持度设得足够低以使得不丢失任何有意义的规则，或者冒丢失一些重要规则的风险；对前一种情形计算效率是个问题，而后一种情形则有可能丢失从用户观点来看是有意义的规则的问题。在中作者给出了感兴趣的规则的定义（R-interesting），在中他们又对此作了改进。在中把事件依赖性的统计定义扩展到兴趣度的定义上来；定义了否定关联规则的兴趣度。除了把兴趣度作为修剪无价值规则的工具，现在已有许多其他的工作来重新认识项集，如Brin等考虑的相关规则。在中讨论了蕴涵规则(implication rule)，规则的蕴涵强度在另一个度量值——“收集强度”(collective strength)在中被定义，他们设想使用“大于期望值”来发现有意义的关联规则。项集的“收集强度”是中找到。4.2 用户主观层面：上面的讨论只是基于系统方面的考虑，但是一个规则的有用与否最终取决于用户的感觉。只有用户可以决定规则的有效性、可行性。所以我们应该将用户的需求和系统更加紧密的结合起来。可以采用一种基于约束(consraint-based)的挖掘。具体约束的内容可以有：
[*]数据约束。用户可以指定对哪些数据进行挖掘，而不一定是全部的数据。
[*]指定挖掘的维和层次。用户可以指定对数据哪些维以及这些维上的哪些层次进行挖掘。
[*]规则约束。可以指定哪些类型的规则是我们所需要的。引入一个模板（template）的概念，用户使用它来确定哪些规则是令人感兴趣的而哪些则不然：如果一条规则匹配一个包含的模板（inclusive template），则是令人感兴趣的，然而如果一条规则匹配一个限制的模板（rextrictive template），则被认为是缺乏兴趣的。
其中有些条件可以和算法紧密的结合，从而即提高了效率，又使挖掘的目的更加的明确化了。其他的方法还有：Kleinberg等人的工作是希望建立一套理论来判断所得模式的价值，他们认为这个问题仅能在微观经济学框架里被解决，他们的模型提出了一个可以发展的方向。他们引入并研究了一个新的优化问题——分段(Segmentation)问题，这个框架包含了一些标准的组合分类问题。这个模型根据基本的目标函数，对“被挖掘的数据”的价值提供一个特殊的算法的视角，显示了从这方面导出的具体的优化问题的广泛的应用领域。在中Korn等就利用猜测误差(这里他们使用“均方根”来定义)来作为一些从给定的数据集所发现的规则的“好处”(goodness)的度量，他们所定义的比例规则就是如下的规则：顾客大多数分别花费 1 : 2 : 5的钱在“面包”:“牛奶”:“奶油”上通过确定未知的(等价的，被隐藏的，丢失的)值，比例规则可以用来作决策支持。如果数据点线性地相关的话，那么比例规则能达到更紧凑的描述，即关联规则更好地描述了相关性。5. 结论与展望本文讨论了数据挖掘中产生关联规则的方法以及它的应用，这方面一些研究成果已取得很大的成绩，并已被集成在一些系统中，如IBM的Quest项目，Simon Farse大学的DBMiner等。具体的内容有经典频集算法，对频集算法的优化，扩展。然后讨论了在OLAP下进行数据挖掘的一些内容。接着是对规则价值的一些评价方法。对于关联规则的发展，我们觉得可以在下面一些方向上进行近一步的深入研究。在处理极大量的数据时，如何提高算法效率的问题；对于挖掘迅速更新的数据的挖掘算法的进一步研究；在挖掘的过程中，提供一种与用户进行交互的方法，将用户的领域知识结合在其中；对于数值型字段在关联规则中的处理问题；生成结果的可视化方面等等。
页:
[1]