关联规则挖掘
关联规则挖掘综述转自：http://www.cnblogs.com/witxjp/archive/2003/09/23/1986213.html ? 摘??要??本文介绍了关联规则的基本概念和分类方法，列举了一些关联规则挖掘算法并简要分析了典型算法，展望了关联规则挖掘的未来研究方向。 ? 关键词??数据挖掘，关联规则，频集，Apriori算法，FP-树 ?? 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?T?B，Aì?I,?Bì?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-11F; 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?3?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-项集的方法。 4.2.4?划分 Savasere等设计了一个基于划分的算法[SON95]，这个算法先把数据库从逻辑上分成几个互不相交的块，每次单独考虑一个分块并对它生成所有的频集，然后把产生的频集合并，用来生成所有可能的频集，最后计算这些项集的支持度。这里分块的大小选择要使得每个分块可以被放入主存，每个阶段只需被扫描一次。而算法的正确性是由每一个可能的频集至少在某一个分块中是频集保证的。上面所讨论的算法是可以高度并行的，可以把每一分块分别分配给某一个处理器生成频集。产生频集的每一个循环结束后，处理器之间进行通信来产生全局的候选k-项集。通常这里的通信过程是算法执行时间的主要瓶颈；而另一方面，每个独立的处理器生成频集的时间也是一个瓶颈。其他的方法还有在多处理器之间共享一个杂凑树来产生频集。更多的关于生成频集的并行化方法可以在文献[AS96]中找到。 4.2.5?选样 基本思想是在给定数据的一个子集挖掘。对前一遍扫描得到的信息，仔细地组合分析，可以得到一个改进的算法，Mannila等先考虑了这一点[MTV94]，他们认为采样是发现规则的一个有效途径。随后又由Toivonen进一步发展了这个思想[Toi96]，先使用从数据库中抽取出来的采样得到一些在整个数据库中可能成立的规则，然后对数据库的剩余部分验证这个结果。Toivonen的算法相当简单并显著地减少了I/O代价，但是一个很大的缺点就是产生的结果不精确，即存在所谓的数据扭曲(data skew)。分布在同一页面上的数据时常是高度相关的，可能不能表示整个数据库中模式的分布，由此而导致的是采样5%的交易数据所花费的代价可能同扫描一遍数据库相近。 4.2.6?动态项集计数 Brin等人给出该算法[BMUT97]。动态项集计数技术将数据库划分为标记开始点的块。不象Apriori仅在每次完整的数据库扫描之前确定新的候选，在这种变形中，可以在任何开始点添加新的候选项集。该技术动态地评估以被计数的所有项集的支持度，如果一个项集的所有子集以被确定为频繁的，则添加它作为新的候选。结果算法需要的数据库扫描比Apriori?少。 4.3 FP-树频集算法? 针对Apriori算法的固有缺陷，J. Han等提出了不产生候选挖掘频繁项集的方法—FP-树频集算法[HPY00]。采用分而治之的策略，在经过第一遍扫描之后，把数据库中的频集压缩进一棵频繁模式树（FP-tree），同时依然保留其中的关联信息，随后再将FP-tree分化成一些条件库，每个库和一个长度为1的频集相关，然后再对这些条件库分别进行挖掘。当原始数据量很大的时候，也可以结合划分的方法,使得一个FP-tree可以放入主存中。实验表明，FP-growth对不同长度的规则都有很好的适应性，同时在效率上较之apriori算法有巨大的提高。? 4.4?多层关联规则挖掘? 对于很多的应用来说，由于数据分布的分散性，所以很难在数据最细节的层次上发现一些强关联规则。当我们引入概念层次后，就可以在较高的层次上进行挖掘[HF95,SA95]。虽然较高层次上得出的规则可能是更普通的信息，但是对于一个用户来说是普通的信息，对于另一个用户却未必如此。所以数据挖掘应该提供这样一种在多个层次上进行挖掘的功能。 多层关联规则的分类：根据规则中涉及到的层次，多层关联规则可以分为同层关联规则和层间关联规则。 多层关联规则的挖掘基本上可以沿用“支持度-可信度”的框架。不过，在支持度设置的问题上有一些要考虑的东西。 同层关联规则可以采用两种支持度策略： 1)??统一的最小支持度。对于不同的层次，都使用同一个最小支持度。这样对于用户和算法实现来说都比较的容易，但是弊端也是显然的。 2)??递减的最小支持度。每个层次都有不同的最小支持度，较低层次的最小支持度相对较小。同时还可以利用上层挖掘得到的信息进行一些过滤的工作。 层间关联规则考虑最小支持度的时候，应该根据较低层次的最小支持度来定。? 4.5?多维关联规则挖掘 对于多维数据库而言，除维内的关联规则外，还有一类多维的关联规则。例如： 年龄（X，“20...30”）?职业（X,“学生”）==>?购买(X，“笔记本电脑”) 在这里我们就涉及到三个维上的数据：年龄、职业、购买。 根据是否允许同一个维重复出现，可以又细分为维间的关联规则（不允许维重复出现）和混合维关联规则（允许维在规则的左右同时出现）。 年龄（X，“20...30”）?购买(X，“笔记本电脑”) ==>?购买(X，“打印机”) 这个规则就是混合维关联规则。 在挖掘维间关联规则和混合维关联规则的时候，还要考虑不同的字段种类：种类型和数值型。 对于种类型的字段，原先的算法都可以处理。而对于数值型的字段，需要进行一定的处理之后才可以进行[KHC97]。处理数值型字段的方法基本上有以下几种： 1)??数值字段被分成一些预定义的层次结构。这些区间都是由用户预先定义的。得出的规则也叫做静态数量关联规则。 2)??数值字段根据数据的分布分成了一些布尔字段。每个布尔字段都表示一个数值字段的区间，落在其中则为1，反之为0。这种分法是动态的。得出的规则叫布尔数量关联规则。 3)??数值字段被分成一些能体现它含义的区间。它考虑了数据之间的距离的因素。得出的规则叫基于距离的关联规则。 4)??直接用数值字段中的原始数据进行分析。使用一些统计的方法对数值字段的值进行分析，并且结合多层关联规则的概念，在多个层次之间进行比较从而得出一些有用的规则。得出的规则叫多层数量关联规则。? ?5?展望?对于关联规则挖掘领域的发展，笔者认为可以在如下一些方向上进行深入研究：在处理极大量的数据时，如何提高算法效率；对于挖掘迅速更新的数据的挖掘算法的进一步研究；在挖掘的过程中，提供一种与用户进行交互的方法，将用户的领域知识结合在其中；对于数值型字段在关联规则中的处理问题；生成结果的可视化，等等。 ?参考文献 [AIS93b] R. Agrawal,T. Imielinski,and A. Swami. Mining association rules between sets of items in large databases. Proceedings of the ACM SIGMOD Conference on Management of data,p.p. 207-216,May 1993. [AS94a] R. Agrawal,and R. Srikant.??Fast algorithms for mining association rules in large database. Technical Report FJ9839,IBM Almaden Research Center,San Jose,CA,Jun. 1994. [AS94b] R. Agrawal,and R. Srikant.??Fast algorithms for mining association rules. In?Proc. 1994 Int. Conf. Very Large Databases(VLDB’94),Sep. 1994. [AS96] R. Agrawal,and J. Shafer.??Parallel mining of association rules: Design,Implementation,and Experience.?IEEE Trans. Knowledge and data engineering,8:962-969,Jan. 1996. [BMUT97] S. Brin,R. Motwani,J. D. Ullman,and S. Tsur. Dynamic itemset counting and implication rules for market basket data. In?ACM SIGMOD International Conference On the Management of Data,p.p. 255-264,May 1997. [HF95] J,Han and Y. Fu. Discovery of multiple-level association rules from large databases. In?Proc. 1995 Int. Conf. Very Large Databases(VLDB’95),p.p. 402-431,Sep. 1995. [HPY00] J.Han,J.Pei,and Y.Yin.Mining. Frequent patterns without candidate generation.?In Proc. 2000 ACM-SIGMOD Int. Conf. Management of Data (SIGMOD’00),?p.p. 1-12,May 2000. ? [KHC97] M. Kamber,J. Han,J. Chang. Metarule-guided mining of multi-dimensional association rules using data cubes. In?Proc. 1997 Int. Conf. Khowledge Discovery and Data Mining(KDD’97),p.p. 207-210,Aug. 1997 [KPR98] J. Kleinberg,C. Papadimitriou,and P. Raghavan. Segmentation problems. Proceedings of the 30th?Annual Symposium on Theory of Computing,ACM. Sep. 1998. [MTV94] H. Mannila,H. Toivonen,and A. Verkamo. Efficient algorithm for discovering association??rules. AAAI Workshop on Knowledge Discovery in Databases,p.p. 181-192,Jul. 1994. [PCY95a] J. S. Park,M. S. Chen,and P. S. Yu. An effective hash-based algorithm for mining association rules. Proceedings of ACM SIGMOD International Conference on Management of Data,p.p. 175-186,May 1995. [PCY95b] J. S. Park,and P. S. Yu. Efficient parallel data mining of association rules. 4th?International Conference on Information and Knowledge Management,Baltimore,Maryland,Nov. 1995. [SA95] R. Srikant,and R. Agrawal. Mining generalized association rules. Proceedings of the 21st?International Conference on Very Large Database,p.p. 407-419,Sep.1995. [SON95] A. Savasere,E. Omiecinski,and S. Navathe. An efficient algorithm for mining association rules in large databases. Proceedings of the 21st?International Conference on Very Large Database,p.p. 432-443,57)">[Toi96] H. Toivonen. Sampling large databases for association rules. Proceedings of the 22nd?International Conference on Very Large Database,Bombay,India,p.p. 134-145,Sep. 1996. ? [相关资源] ·??bhw98的专栏：http://www.csdn.net/develop/author/netauthor/bhw98/ 关联规则挖掘（一）：基本概念 本文主要来自《数据仓库和数据挖掘》一书，这本书讲的和维基百科里的非常相似，怀疑是从某本外文书籍里翻译过来的。 关联规则挖掘（Association rule mining）是数据挖掘中最活跃的研究方法之一，可以用来发现事情之间的联系，最早是为了发现超市交易数据库中不同的商品之间的关系。 这里有一则沃尔玛超市的趣闻。沃尔玛曾今对数据仓库中一年多的原始交易数据进行了详细的分析，发现与尿布一起被购买最多的商品竟然是啤酒。借助数据仓库和关联规则，发现了这个隐藏在背后的事实：美国的妇女经常会嘱咐丈夫下班后为孩子买尿布，而30%~40%的丈夫在买完尿布之后又要顺便购买自己爱喝的啤酒。根据这个发现，沃尔玛调整了货架的位置，把尿布和啤酒放在一起销售，大大增加了销量。 这里借用一个引例来介绍关联规则挖掘[1]。 ????????????????????????????????????????????????????????????? 表1 某超市的交易数据库
定义一：设I={i1,i2,im}，是m个不同的项目的集合，每个ik称为一个项目。项目的集合I称为项集。其元素的个数称为项集的长度，长度为k的项集称为k-项集。引例中每个商品就是一个项目，项集为I={bread,beer,tea}，I的长度为6。 定义二：每笔交易T是项集I的一个子集。对应每一个交易有一个唯一标识交易号，记作TID。交易全体构成了交易数据库D，|D|等于D中交易的个数。引例中包含10笔交易，因此|D|=10。 定义三：对于项集X，设定count(X?T)为交易集D中包含X的交易的数量，则项集X的支持度为：
support(X)=count(X?T)/|D|
引例中X={bread,milk}出现在T1，T2，T5，T9和T10中，所以支持度为0.5。 定义四：最小支持度是项集的最小支持阀值，记为SUPmin，代表了用户关心的关联规则的最低重要性。支持度不小于SUPmin 的项集称为频繁集，长度为k的频繁集称为k-频繁集。如果设定SUPmin为0.3，引例中{bread,milk}的支持度是0.5，所以是2-频繁集。 R：X?Y 其中X?I，Y?I，并且X∩Y=?。表示项集X在某一交易中出现，则导致Y以某一概率也会出现。用户关心的关联规则，可以用两个标准来衡量：支持度和可信度。 定义六：关联规则R的支持度是交易集同时包含X和Y的交易数与|D|之比。即： support(X?Y)=count(X?Y)/|D| 支持度反映了X、Y同时出现的概率。关联规则的支持度等于频繁集的支持度。? 定义七：关联规则R的可信度是指包含X和Y的交易数与包含X的交易数之比。即： confidence(X?Y)=support(X?Y)/support(X) 可信度反映了如果交易中包含X，则交易包含Y的概率。一般来说，只有支持度和可信度较高的关联规则才是用户感兴趣的。 定义八：设定关联规则的最小支持度和最小可信度为SUPmin和CONFmin。规则R的支持度和可信度均不小于SUPmin和CONFmin ，则称为强关联规则。关联规则挖掘的目的就是找出强关联规则，从而指导商家的决策。
参考文献： [1] 韩慧等。数据仓库与数据挖掘。清华大学出版社，2009。 [2] Association rule mining.?http://en.wikipedia.org/wiki/Association_rule_mining,2011. 关联规则挖掘（二）：Apriori算法
1 算法简介在数据挖掘领域，Apriori算法是挖掘关联规则的经典算法。Apriori算法采用的是自底向上的方法，从1-频繁集开始，逐步找出高阶频繁集。 它的基本流程是：第一次扫描交易数据库D时，产生1-频繁集。在此基础上经过连接、修剪产生2-频繁集。以此类推，直到无法产生更高阶的频繁集为止。在第k次循环中，也就是产生k-频繁集的时候，首先产生k-候选集，k-候选集中每一个项集都是对两个只有一个项不同的属于k-1频繁集的项集连接产生的，k-候选集经过筛选后产生k-频繁集。 2 理论基础 首先来看一个频繁集的性质。 定理：如果项目集X是频繁集，那么它的非空子集都是频繁集。 根据定理，已知一个k-频繁集的项集X，X的所有k-1阶子集都肯定是频繁集，也就肯定可以找到两个k-1频繁集的项集，它们只有一项不同，且连接后等于X。这证明了通过连接k-1频繁集产生的k-候选集覆盖了k-频繁集。同时，如果k-候选集中的项集Y，包含有某个k-1阶子集不属于k-1频繁集，那么Y就不可能是频繁集，应该从候选集中裁剪掉。Apriori算法就是利用了频繁集的这个性质。 3 算法伪代码这是Apriori算法的主函数，它的输入是交易数据库D和最小支持度，最终输出频繁集L。函数第一步是扫描数据库产生1-频繁集，这只要统计每个项目出现的次数就可以了。然后依次产生2阶，3阶，……，k阶频繁集，k频繁集为空则算法停止。apriori_gen函数的功能是根据k-1频繁集产生k-候选集。接着扫描交易数据库里的每一笔交易，调用subset函数产生候选集的子集，这个子集里的每一个项集都是此次交易的子集，并对子集里的每一个项集的计数增一。最后统计候选集里所有项集的计数，将未达到最小支持度标准的项集删去，得到新的频繁集。 可以看到每一次循环，都必须遍历交易数据库；而且对于每一个交易，也要遍历候选集来增加计数，当候选集很大时这也是很大的开销。
apriori_gen的功能是根据k-1频繁集产生k-候选集。函数是一个二重循环，当遇到两个项集，它们的前k-2项都相同，只有最后一项不同时，就对它们进行连接操作，产生一个k阶的项集（这么做的理论依据如前所述，任何一个k阶的频繁集一定能找到两个满足此条件的k-1阶子频繁集）。新产生的k阶项集可能包含有不是频繁集的子集，遇到这样的情况应该将此项集从候选集中裁剪掉，避免无谓的开销，这就是has_infrequent_subset函数做的工作。 ?
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |