关联算法综述.txt

这是对数据挖掘中的关联算法总的综述

摘  要  本文介绍了关联规则的基本概念和分类方法，列举了一些关联规则挖掘算法并简要分析了典型算法，展望了关联规则挖掘的未来研究方向。

1 引言



关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。它在数据挖掘中是一个重要的课题，最近几年已被业界所广泛研究。

关联规则挖掘的一个典型例子是购物篮分析。关联规则研究有助于发现交易数据库中不同商品（项）之间的联系，找出顾客购买行为模式，如购买了某一商品对购买其他商品的影响。分析结果可以应用于商品货架布局、货存安排以及根据购买模式对用户进行分类。

Agrawal等于1993年首先提出了挖掘顾客交易数据库中项集间的关联规则问题[AIS93b]，以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。他们的工作包括对原有的算法进行优化，如引入随机采样、并行的思想等，以提高算法挖掘规则的效率；对关联规则的应用进行推广。

最近也有独立于Agrawal的频集方法的工作[HPY00]，以避免频集方法的一些缺陷，探索挖掘关联规则的新方法。也有一些工作[KPR98]注重于对挖掘到的模式的价值进行评估，他们提出的模型建议了一些值得考虑的研究方向。





2 基本概念

         

设I={i1,i2,..,im}是项集，其中ik(k=1,2,…,m)可以是购物篮中的物品，也可以是保险公司的顾客。设任务相关的数据D是事务集，其中每个事务T是项集，使得TÍI。设A是一个项集，且AÍT。

       关联规则是如下形式的逻辑蕴涵：A Þ B，AÌI, AÌI，且A∩B=F。关联规则具有如下两个重要的属性：

支持度: P(A∪B)，即A和B这两个项集在事务集D中同时出现的概率。

置信度: P(B｜A)，即在出现项集A的事务集D中，项集B也同时出现的概率。

同时满足最小支持度阈值和最小置信度阈值的规则称为强规则。给定一个事务集D，挖掘关联规则问题就是产生支持度和可信度分别大于用户给定的最小支持度和最小可信度的关联规则，也就是产生强规则的问题。



3 关联规则种类



1) 基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。

布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的关系。

数值型关联规则可以和多维关联或多层关联规则结合起来，对数值型字段进行处理，将其进行动态的分割，或者直接对原始的数据进行处理，当然数值型关联规则中也可以包含种类变量。



2) 基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。

在单层关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同的层次的。

在多层关联规则中，对数据的多层性已经进行了充分的考虑。



3) 基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。

在单维关联规则中，我们只涉及到数据的一个维，如用户购买的物品

在多维关联规则中，要处理的数据将会涉及多个维。





4 算法综述

4.1 经典的频集算法



Agrawal等于1994年提出了一个挖掘顾客交易数据库中项集间的关联规则的重要方法 [AS94a, AS94b]，其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。

所有支持度大于最小支持度的项集称为频繁项集，简称频集。



4.1.1 算法的基本思想

首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度。

  挖掘关联规则的总体性能由第一步决定，第二步相对容易实现。



4.1.2 Apriori核心算法分析

为了生成所有频集，使用了递推的方法。其核心思想简要描述如下：

(1)     L1 = {large 1-itemsets};

(2)     for (k=2; Lk-1¹F; k++) do begin

(3)         Ck=apriori-gen(Lk-1);   //新的候选集

(4)         for all transactions tÎD do begin

(5)                  Ct=subset(Ck,t);    //事务t中包含的候选集

(6)           for all candidates cÎ Ct  do

(7)           c.count++;

(8)         end

(9)        Lk={cÎ Ck |c.count³minsup}

(10)    end

(11)                   Answer=∪kLk;

首先产生频繁1-项集L1，然后是频繁2-项集L2，直到有某个r值使得Lr为空，这时算法停止。这里在第k次循环中，过程先产生候选k-项集的集合Ck，Ck中的每一个项集是对两个只有一个项不同的属于Lk-1的频集做一个(k-2)-连接来产生的。Ck中的项集是用来产生频集的候选集，最后的频集Lk必须是Ck的一个子集。Ck中的每个元素需在交易数据库中进行验证来决定其是否加入Lk，这里的验证过程是算法性能的一个瓶颈。这个方法要求多次扫描可能很大的交易数据库，即如果频集最多包含10个项，那么就需要扫描交易数据库10遍，这需要很大的I/O负载。

可能产生大量的候选集,以及可能需要重复扫描数据库，是Apriori算法的两大缺点。



4.1.3 算法的优化

为了提高算法的效率，Mannila等引入了修剪技术来减小候选集Ck的大小[MTV94]，由此可以显著地改进生成所有频集算法的性能。算法中引入的修剪策略基于这样一个性质：一个项集是频集当且仅当它的所有子集都是频集。那么，如果Ck中某个候选项集有一个(k-1)-子集不属于Lk-1，则这个项集可以被修剪掉不再被考虑，这个修剪过程可以降低计算所有的候选集的支持度的代价。





4.2 改进的频集算法



4.2.1散列

该算法由Park等在1995年提出[PCY95b]。通过实验发现寻找频繁项集的主要计算是在生成频繁2项集L2上，Park就是利用这个性质引入散列技术来改进产生频繁2项集的方法。

    其基本思想是：当扫描数据库中每个事务，由C1中的候选1项集产生频繁1项集L1时，对每个事务产生所有的2项集，将它们散列到散列表结构的不同桶中，并增加对应的桶计数，在散列表中对应的桶计数低于支持度阈值的2项集不可能是频繁2项集，可从候选2项集中删除，这样就可大大压缩了要考虑的2项集。



4.2.2 事务压缩

Agrawal等提出压缩进一步迭代扫描的事务数的方法[AS94b, HF95]。因为不包含任何K项集的事务，不可能包含任何（K+1）项集，可对这些事务加上删除标志,扫描数据库时不再考虑。



4.2.3 杂凑

一个高效地产生频集的基于杂凑的算法由Park等提出[PCY95a]。通过实验我们可以发现寻找频集主要的计算是在生成频繁2-项集Lk上，Park等就是利用了这个性质引入杂凑技术来改进产生频繁2-项集的方法。