关联规则数据挖掘算法浅析

《关联规则数据挖掘算法浅析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、关联规则数据挖掘算法浅析2009年08月24日星期一03:23IT168.COM旗下网站文章编号：1005-6033（2006）19-0206-03收稿F1期：2006-08-16摘要：简要介绍了关联规则的概念及其基本思想，重点分析和讨论了两个挖掘关联规则的经典算法，即Apriori算法和分段算法。关键词：关联规则；数据挖掘；频繁项集中图分类号：TP274文献标识码：A随着现代科学技术和数据库技术的迅速发展，人们积累的数据越来越多，激增的数据背后隐藏着许多重要的信息，人们希望能够对英进行更高层次的分析，以便更好地利用这些数据

2、。目前的数据库系统可以高效地实现数据的录入、查询、统计等功能，但无法发现数据屮存在的关系和规则，无法根据现有的数据预测未来的发展趋势。为此，人们需要冇新的、更为冇效的手段对各种信息资源进行挖掘以发挥其应用潜能。数据挖掘正是在这样的应用需求背景下产生并迅速发展起來的一门技术。所谓数据挖掘（DataMining，简称DM）是从大量数据中鉴别出有效模式（Pattern）的非平凡过程。该模式是新的，可能有用的和最终可理解的，又可称为数据采掘。DM的定义还冇一些不同的表达形式，但其本质都是一样的，即从数据库中提出隐含的、高水平的模式，

3、其目的是为数据库理解与应用捉供自动化、智能化的手段。关联规则是数据挖掘的一个重要课题，目前已受到越来越多研究者的关注。1关联规则及其基木思想关联规则是数据挖掘过程中所能挖掘的一类重要的模式或知识，可以用來描述事物Z间在特定条件卜•存在的某种强度的联系。例如，在购买铁锤的顾客当中，有70%的人同时购买了铁钉。这些关联规则很冇价值，商场管理人员可以根据这些规则更好地进行规划，如把铁锤和铁钉这样的商品摆放在一起，能够促进销售。关联规则的基木思想:一是找到所有支持度大于最小支持度的频繁项集，即频集。二是使用第一步找到的频集产生期望的

4、规则。其核心方法是基于频集理论的递推方法。2挖掘关联规则的基本算法挖掘关联规则，就是在大型数据库中发现所有可能有用的或者用户感兴趣的强关联规则的过程。按照它的基木思想，挖掘关联规则一般可以分为以下两个步骤。（1）求出支持度项集的集合（FrequentSets）,即找出目标数据库中包含的所有频度项集。（2）使用各频度项集生成相应的强关联规则。不难看出，在上述两步中，第二步的工作是比较简单直接的。具体来说，若已知所有频度项集的集合为F,X为F屮的任一频度项集，设项集Y真包含于X,测试C（Y>X-Y）是否大于设定的最小置信度门限，

5、若是，则规则Y>X-Y是强关联规则。按此方法即能将F中所能构造的所有强关联规则找出來。因此，挖掘关联规则算法的主要工作应集屮在第一步，即设法高效地发现目标数据库屮包含的所有频度项集。为了测试某些特定项集是否是频度项集，不可避免地需要扫描整个数据库。如果目标数据库很大，应设法尽可能减少扫描数据库的次数。考虑一种极端的情况：只需扫描数据库一次，但要检测R的所有子集(若R中包含m个项，则共冇2m个子集)。显然，这种指数级数数据检测方法是不可行的，除非m的值很小。支持度和置信度是描述关联规则的两个重要概念，前者用于衡量关联规则在整个

6、数据集中的统计重要性，后者用于衡量关联规则的可信程度。支持度和置信度均高的关联规则才是有用的关联规则。3挖掘关联规则的经典算法3.1Apriori算法Apriori算法基于这样的一个原则：如果某一项不是频度集，那么它的所冇超集也都不口J能是频度集。反过来说，就是任一频度集的所冇子集一定都是频度集。算法采用逐维扩展(Level—wiseExtention)的方法，从求1一维频度集的集合开始，依次生成2—维频度集的集合、3—维频度集的集合……，直到所有维的频度项集都生成为止。具体算法如下：输入：6屮的值，目标数据库D,D的大小d

7、bsize。输出：D上的所有频度项集。算法流程：PROCEDUREAprioriA1g()Begin〃算法中的LK表示k—维的所冇频度项集组成的集合//CK表示k—维的所有候选项集组成的集合Ll={Frequent1—ItemSets}For(k=2；1(k—1)<>0；k++)dobeginCK=Apriori_gen(L(k—1))；〃利用L(k一1)生成CKFora11transactionstEDdobeginCt=subset(CK,t)；〃找illCK屮包含于t的所有项集Fora11candidatesetscW

8、Ctdoc・count++；endLK={cWCkc.count/bdsize>=o}EndAnswer=UkLkEnd算法首先计算单元素项集的支持度，生成所有1—维频度项集构成的集合L1,然后，利用L1构造2—维候选项集的集合C2,再去扫描数据库，并根据设定的最小支持度门限值筛选出2—维