数据挖掘算法之-关联规则挖掘(Association Rule)

在数据挖掘的知识模式中,关联规则模式是比较重要的一种。关联规则的概念由Agrawal、Imielinski、Swami 提出,是数据中一种简单但很实用的规则。关联规则模式属于描述型模式,发现关联规则的算法属于无监督学习的方法。

一、关联规则的定义和属性
 
考察一些涉及许多物品的事务:事务1 中出现了物品甲,事务2 中出现了物品乙,事务3 中则同时出现了物品甲和乙。那么,物品甲和乙在事务中的出现相互之间是否有规律可循呢?在数据库的知识发现中,关联规则就是描述这种在一个事务中物品之间同时出现的规律的知识模式。更确切的说,关联规则通过量化的数字描述物品甲的出现对物品乙的出现有多大的影响。
 
现实中,这样的例子很多。例如超级市场利用前端收款机收集存储了大量的售货数据,这些数据是一条条的购买事务记录,每条记录存储了事务处理时间,顾客购买的物品、物品的数量及金额等。这些数据中常常隐含形式如下的关联规则:在购买铁锤的顾客当中,有70 %的人同时购买了铁钉。这些关联规则很有价值,商场管理人员可以根据这些关联规则更好地规划商场,如把铁锤和铁钉这样的商品摆放在一起,能够促进销售。
 
有些数据不像售货数据那样很容易就能看出一个事务是许多物品的集合,但稍微转换一下思考角度,仍然可以像售货数据一样处理。比如人寿保险,一份保单就是一个事务。保险公司在接受保险前,往往需要记录投保人详尽的信息,有时还要到医院做身体检查。保单上记录有投保人的年龄、性别、健康状况、工作单位、工作地址、工资水平等。这些投保人的个人信息就可以看作事务中的物品。通过分析这些数据,可以得到类似以下这样的关联规则:年龄在40 岁以上,工作在A 区的投保人当中,有45 %的人曾经向保险公司索赔过。在这条规则中,“年龄在40 岁以上”是物品甲,“工作在A
区”是物品乙,“向保险公司索赔过”则是物品丙。可以看出来,A 区可能污染比较严重,环境比较差,导致工作在该区的人健康状况不好,索赔率也相对比较高。
 
设R= { I1,I2 ……Im} 是一组物品集,W 是一组事务集。W 中的每个事务T 是一组物品,T R。假设有一个物品集A,一个事务T,如果A T,则称事务T 支持物品集A。关联规则是如下形式的一种蕴含:A→B,其中A、B 是两组物品,A I,B I,且A ∩B=。一般用四个参数来描述一个关联规则的属性:
 
1 .可信度(Confidence)
 
设W 中支持物品集A 的事务中,有c %的事务同时也支持物品集B,c %称为关联规则A→B 的可信度。简单地说,可信度就是指在出现了物品集A 的事务T 中,物品集B 也同时出现的概率有多大。如上面所举的铁锤和铁钉的例子,该关联规则的可信度就回答了这样一个问题:如果一个顾客购买了铁锤,那么他也购买铁钉的可能性有多大呢?在上述例子中,购买铁锤的顾客中有70 %的人购买了铁钉, 所以可信度是70 %。
 
2 .支持度(Support)
 
设W 中有s %的事务同时支持物品集A 和B,s %称为关联规则A→B 的支持度。支持度描述了A 和B 这两个物品集的并集C 在所有的事务中出现的概率有多大。如果某天共有1000 个顾客到商场购买物品,其中有100 个顾客同时购买了铁锤和铁钉,那么上述的关联规则的支持度就是10 %。
 
3 .期望可信度(Expected confidence)
 
设W 中有e %的事务支持物品集B,e %称为关联规则A→B 的期望可信度度。期望可信度描述了在没有任何条件影响时,物品集B 在所有事务中出现的概率有多大。如果某天共有1000 个顾客到商场购买物品,其中有200 个顾客购买了铁钉,则上述的关联规则的期望可信度就是20 %。
 
4 .作用度(Lift)
 
作用度是可信度与期望可信度的比值。作用度描述物品集A 的出现对物品集B 的出现有多大的影响。因为物品集B 在所有事务中出现的概率是期望可信度;而物品集B 在有物品集A 出现的事务中出现的概率是可信度,通过可信度对期望可信度的比值反映了在加入“物品集A 出现”的这个条件后,物品集B 的出现概率发生了多大的变化。在上例中作用度就是70 %/20 %=3.5。
 
可信度是对关联规则的准确度的衡量,支持度是对关联规则重要性的衡量。支持度说明了这条规则在所有事务中有多大的代表性,显然支持度越大,关联规则越重要。有些关联规则可信度虽然很高,但支持度却很低,说明该关联规则实用的机会很小,因此也不重要。
 
期望可信度描述了在没有物品集A 的作用下,物品集B 本身的支持度;作用度描述了物品集A 对物品集B 的影响力的大小。作用度越大,说明物品集B 受物品集A 的影响越大。一般情况,有用的关联规则的作用度都应该大于1,只有关联规则的可信度大于期望可信度,才说明A 的出现对B 的出现有促进作用,也说明了它们之间某种程度的相关性,如果作用度不大于1,则此关联规则也就没有意义了。
 
二、关联规则的挖掘
 
在关联规则的四个属性中,支持度和可信度能够比较直接形容关联规则的性质。从关联规则定义可以看出,任意给出事务中的两个物品集,它们之间都存在关联规则,只不过属性值有所不同。如果不考虑关联规则的支持度和可信度,那么在事务数据库中可以发现无穷多的关联规则。事实上,人们一般只对满足一定的支持度和可信度的关联规则感兴趣。因此,为了发现有意义的关联规则,需要给定两个阈值:最小支持度和最小可信度,前者规定了关联规则必须满足的最小支持度;后者规定了关联规则必须满足的最小可信度。一般称满足一定要求的(如较大的支持度和可信度)的规则为强规则(Strong
rules)。
 
在关联规则的挖掘中要注意以下几点:
 
1、充分理解数据。
 
2、目标明确。
 
3、数据准备工作要做好。能否做好数据准备又取决于前两点。数据准备将直接影响到问题的复杂度及目标的实现。
 
4、选取恰当的最小支持度和最小可信度。这依赖于用户对目标的估计,如果取值过小,那么会发现大量无用的规则,不但影响执行效率、浪费系统资源,而且可能把目标埋没;如果取值过大,则又有可能找不到规则,与知识失之交臂。
 
5、很好地理解关联规则。数据挖掘工具能够发现满足条件的关联规则,但它不能判定关联规则的实际意义。对关联规则的理解需要熟悉业务背景,丰富的业务经验对数据有足够的理解。在发现的关联规则中,可能有两个主观上认为没有多大关系的物品,它们的关联规则支持度和可信度却很高,需要根据业务知识、经验,从各个角度判断这是一个偶然现象或有其内在的合理性;反之,可能有主观上认为关系密切的物品,结果却显示它们之间相关性不强。只有很好的理解关联规则,才能去其糟粕,取其精华,充分发挥关联规则的价值。
 
发现关联规则要经过以下三个步骤:
 
1、连接数据,作数据准备;
 
2、给定最小支持度和最小可信度,利用数据挖掘工具提供的算法发现关联规则;
 
3、可视化显示、理解、评估关联规则。
 
三 、关联规则挖掘的过程
 
关联规则挖掘过程主要包含两个阶段:
 
第一阶段必须先从资料集合中找出所有的高频项目组(Frequent Itemsets),
 
第二阶段再由这些高频项目组中产生关联规则(Association Rules)。
 
关联规则挖掘的第一阶段必须从原始资料集合中,找出所有高频项目组(Large Itemsets)。高频的意思是指某一项目组出现的频率相对于所有记录而言,必须达到某一水平。一项目组出现的频率称为支持度(Support),以一个包含A与B两个项目的2-itemset为例,我们可以经由公式(1)求得包含{A,B}项目组的支持度,若支持度大于等于所设定的最小支持度(Minimum Support)门槛值时,则{A,B}称为高频项目组。一个满足最小支持度的k-itemset,则称为高频k-项目组(Frequent k-itemset),一般表示为Large
k或Frequent k。算法并从Large k的项目组中再产生Large k+1,直到无法再找到更长的高频项目组为止。
 
关联规则挖掘的第二阶段是要产生关联规则(Association Rules)。从高频项目组产生关联规则,是利用前一步骤的高频k-项目组来产生规则,在最小信赖度(Minimum Confidence)的条件门槛下,若一规则所求得的信赖度满足最小信赖度,称此规则为关联规则。
 
从上面的介绍还可以看出,关联规则挖掘通常比较适用与记录中的指标取离散值的情况。如果原始数据库中的指标值是取连续的数据,则在关联规则挖掘之前应该进行适当的数据离散化(实际上就是将某个区间的值对应于某个值),数据的离散化是数据挖掘前的重要环节,离散化的过程是否合理将直接影响关联规则的挖掘结果。
 
四、 关联规则的分类
 
按照不同情况,关联规则可以进行分类如下:
 
1.基于规则中处理的变量的类别,关联规则可以分为布尔型和数值型。
 
布尔型关联规则处理的值都是离散的、种类化的,它显示了这些变量之间的关系;而数值型关联规则可以和多维关联或多层关联规则结合起来,对数值型字段进行处理,将其进行动态的分割,或者直接对原始的数据进行处理,当然数值型关联规则中也可以包含种类变量。例如:性别=“女”=>职业=“秘书” ,是布尔型关联规则;性别=“女”=>avg(收入)=2300,涉及的收入是数值类型,所以是一个数值型关联规则。
 
2.基于规则中数据的抽象层次,可以分为单层关联规则和多层关联规则。
 
在单层的关联规则中,所有的变量都没有考虑到现实的数据是具有多个不同的层次的;而在多层的关联规则中,对数据的多层性已经进行了充分的考虑。例如:IBM台式机=>Sony打印机,是一个细节数据上的单层关联规则;台式机=>Sony打印机,是一个较高层次和细节层次之间的多层关联规则。
 
3.基于规则中涉及到的数据的维数,关联规则可以分为单维的和多维的。
 
在单维的关联规则中,我们只涉及到数据的一个维,如用户购买的物品;而在多维的关联规则中,要处理的数据将会涉及多个维。换成另一句话,单维关联规则是处理单个属性中的一些关系;多维关联规则是处理各个属性之间的某些关系。例如:啤酒=>尿布,这条规则只涉及到用户的购买的物品;性别=“女”=>职业=“秘书”,这条规则就涉及到两个字段的信息,是两个维上的一条关联规则。
 
5. 关联规则挖掘的相关算法
 
1.Apriori算法:使用候选项集找频繁项集
 
Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里,所有支持度大于最小支持度的项集称为频繁项集,简称频集。
 
该算法的基本思想是:首先找出所有的频集,这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则,这些规则必须满足最小支持度和最小可信度。然后使用第1步找到的频集产生期望的规则,产生只包含集合的项的所有规则,其中每一条规则的右部只有一项,这里采用的是中规则的定义。一旦这些规则被生成,那么只有那些大于用户给定的最小可信度的规则才被留下来。为了生成所有频集,使用了递推的方法。
 
可能产生大量的候选集,以及可能需要重复扫描数据库,是Apriori算法的两大缺点。
 
2.基于划分的算法
 
Savasere等设计了一个基于划分的算法。这个算法先把数据库从逻辑上分成几个互不相交的块,每次单独考虑一个分块并对它生成所有的频集,然后把产生的频集合并,用来生成所有可能的频集,最后计算这些项集的支持度。这里分块的大小选择要使得每个分块可以被放入主存,每个阶段只需被扫描一次。而算法的正确性是由每一个可能的频集至少在某一个分块中是频集保证的。该算法是可以高度并行的,可以把每一分块分别分配给某一个处理器生成频集。产生频集的每一个循环结束后,处理器之间进行通信来产生全局的候选k-项集。通常这里的通信过程是算法执行时间的主要瓶颈;而另一方面,每个独立的处理器生成频集的时间也是一个瓶颈。
 
3.FP-树频集算法
 
针对Apriori算法的固有缺陷,J. Han等提出了不产生候选挖掘频繁项集的方法:FP-树频集算法。采用分而治之的策略,在经过第一遍扫描之后,把数据库中的频集压缩进一棵频繁模式树(FP-tree),同时依然保留其中的关联信息,随后再将FP-tree分化成一些条件库,每个库和一个长度为1的频集相关,然后再对这些条件库分别进行挖掘。当原始数据量很大的时候,也可以结合划分的方法,使得一个FP-tree可以放入主存中。实验表明,FP-growth对不同长度的规则都有很好的适应性,同时在效率上较之Apriori算法有巨大的提高。
 
五、关联规则发掘技术在国内外的应用
 
就目前而言,关联规则挖掘技术已经被广泛应用在西方金融行业企业中,它可以成功预测银行客户需求。一旦获得了这些信息,银行就可以改善自身营销。现在银行天天都在开发新的沟通客户的方法。各银行在自己的ATM机上就捆绑了顾客可能感兴趣的本行产品信息,供使用本行ATM机的用户了解。如果数据库中显示,某个高信用限额的客户更换了地址,这个客户很有可能新近购买了一栋更大的住宅,因此会有可能需要更高信用限额,更高端的新信用卡,或者需要一个住房改善贷款,这些产品都可以通过信用卡账单邮寄给客户。当客户打电话咨询的时候,数据库可以有力地帮助电话销售代表。销售代表的电脑屏幕上可以显示出客户的特点,同时也可以显示出顾客会对什么产品感兴趣。
 
同时,一些知名的电子商务站点也从强大的关联规则挖掘中的受益。这些电子购物网站使用关联规则中规则进行挖掘,然后设置用户有意要一起购买的捆绑包。也有一些购物网站使用它们设置相应的交叉销售,也就是购买某种商品的顾客会看到相关的另外一种商品的广告。
 
但是目前在我国,“数据海量,信息缺乏”是商业银行在数据大集中之后普遍所面对的尴尬。目前金融业实施的大多数数据库只能实现数据的录入、查询、统计等较低层次的功能,却无法发现数据中存在的各种有用的信息,譬如对这些数据进行分析,发现其数据模式及特征,然后可能发现某个客户、消费群体或组织的金融和商业兴趣,并可观察金融市场的变化趋势。可以说,关联规则挖掘的技术在我国的研究与应用并不是很广泛深入。
 
近年来关联规则发掘技术的一些研究
 
由于许多应用问题往往比超市购买问题更复杂,大量研究从不同的角度对关联规则做了扩展,将更多的因素集成到关联规则挖掘方法之中,以此丰富关联规则的应用领域,拓宽支持管理决策的范围。如考虑属性之间的类别层次关系,时态关系,多表挖掘等。近年来围绕关联规则的研究主要集中于两个方面,即扩展经典关联规则能够解决问题的范围,改善经典关联规则挖掘算法效率和规则兴趣性。

时间: 2024-11-03 08:00:24

数据挖掘算法之-关联规则挖掘(Association Rule)的相关文章

数据挖掘系列(5)使用mahout做海量数据关联规则挖掘

上一篇介绍了用开源数据挖掘软件weka做关联规则挖掘,weka方便实用,但不能处理大数据集,因 为内存放不下,给它再多的时间也是无用,因此需要进行分布式计算,mahout是一个基于hadoop的分 布式数据挖掘开源项目(mahout本来是指一个骑在大象上的人).掌握了关联规则的基本算法和使用 ,加上分布式关联规则挖掘后,就可以处理基本的关联规则挖掘工作了,实践中只需要把握业务,理 解数据便可游刃有余. 安装mahout 骑在大象上的侠士必然需要一头雄纠纠的大象,不过本文不解绍大象hadoop,所

数据挖掘系列(4)使用weka做关联规则挖掘

前面几篇介绍了关联规则的一些基本概念和两个基本算法,但实际在商业应用中,写算法反而比较 少,理解数据,把握数据,利用工具才是重要的,前面的基础篇是对算法的理解,这篇将介绍开源利 用数据挖掘工具weka进行管理规则挖掘. weka数据集格式arff arff标准数据集简介 weka的数据文件后缀为arff(Attribute-Relation File Format,即属性关系文件格式),arff文 件分为注释.关系名.属性名.数据域几大部分,注释用百分号开头%,关系名用@relation申明,属

数据挖掘系列(1)关联规则挖掘基本概念与Aprior算法

我计划整理数据挖掘的基本概念和算法,包括关联规则挖掘.分类.聚类的常用算法,敬请期待. 今天讲的是关联规则挖掘的最基本的知识. 关联规则挖掘在电商.零售.大气物理.生物医学已经有了广泛的应用,本篇文章将介绍一些基本 知识和Aprori算法. 啤酒与尿布的故事已经成为了关联规则挖掘的经典案例,还有人专门出了一本书<啤酒与尿布>, 虽然说这个故事是哈弗商学院杜撰出来的,但确实能很好的解释关联规则挖掘的原理.我们这里以一 个超市购物篮迷你数据集来解释关联规则挖掘的基本概念: 表中的每一行代表一次购买

【Python数据挖掘课程】八.关联规则挖掘及Apriori实现购物推荐

        这篇文章主要介绍三个知识点,也是我<数据挖掘与分析>课程讲课的内容.         1.关联规则挖掘概念及实现过程:         2.Apriori算法挖掘频繁项集:         3.Python实现关联规则挖掘及置信度.支持度计算.         前文推荐:        [Python数据挖掘课程]一.安装Python及爬虫入门介绍        [Python数据挖掘课程]二.Kmeans聚类数据分析及Anaconda介绍        [Python数据挖掘

关联规则挖掘之Apriori算法实现超市购物

一.关联规则 关联规则(Association Rules)是反映一个事物与其他事物之间的相互依存性和关联性,是数据挖掘的一个重要技术,用于从大量数据中挖掘出有价值的数据项之间的相关关系.其中关联规则挖掘的最经典的例子就是沃尔玛的啤酒与尿布的故事,通过对超市购物篮数据进行分析,即顾客放入购物篮中不同商品之间的关系来分析顾客的购物习惯,发现美国妇女们经常会叮嘱丈夫下班后为孩子买尿布,30%-40%的丈夫同时会顺便购买喜爱的啤酒,超市就把尿布和啤酒放在一起销售增加销售额. 二.基本概念 关联规则挖掘

《Python数据挖掘:概念、方法与实践》关联规则挖掘

本节书摘来自华章出版社<SAFe 4.0参考指南:精益软件与系统工程的规模化敏捷框架>一书中的第1章,第节,作者[美] 梅甘·斯夸尔(Megan Squire)更多章节内容可以访问"华章计算机"公众号查看. 关联规则挖掘 在数据挖掘工具箱中,计量某个模式的频率是一项关键任务.在某些情况下,较频繁出现的模式可能最终成为更加重要的模式.如果我们可以发现经常同时出现的两个或者三个项目,就更为有趣了. 在本章中,我们开始研究频繁项集,然后将其扩展为称作关联规则的一类模式.我们将介绍

《R语言数据挖掘》——2.3 混合关联规则挖掘

本节书摘来自华章出版社<R语言数据挖掘>一书中的第2章,第2.3节,作者[哈萨克斯坦]贝特·麦克哈贝尔(Bater Makhabel),李洪成 许金炜 段力辉 译,更多章节内容可以访问"华章计算机"公众号查看. 2.3 混合关联规则挖掘 关联规则挖掘有两个有意义的应用:一是多层次和多维度关联规则挖掘:二是基于约束的关联规则挖掘. 2.3.1 多层次和多维度关联规则挖掘 对于给定的事务数据集,若数据集的某些维度存在概念层次关系,则需要对该数据集进行多层次关联规则挖掘.对事物数

weka –Apriori算法 关联规则挖掘实验

  一.Apriori算法参数含义 本次共进行了9组实验,使用了weka安装目录data文件夹下的contact-lenses.arff数据.     ToolsàArffViewer,打开contact-lenses,可以看到实验数据contact-lenses共有24条记录,5个属性值.具体内容如下:     结合实验结果阐释下列12个参数的含义 1.        car 如果设为真,则会挖掘类关联规则而不是全局关联规则. 2.        classindex 类属性索引.如果设置为-

《推荐系统:技术、评估及高效算法》一2.5 关联规则挖掘

2.5 关联规则挖掘 关联规则挖掘关注于规则的发现,其他能够根据事务中出现其他物品来预测出现某个物品.两个物品被发现相关只意味着共同出现,但是没有因果关系.注意不要将这种技术与在2.3.3节中提到的基于规则的分类混淆. 我们定义物品集为一个或多个物品的集合(例如,(牛奶,啤酒,尿布)).k-物品集是包含k个物品的集合.给定物品的频繁度称为支持量(比如,(牛奶,啤酒,尿布)=131).并且物品集的支持度是包含它的事务的比例(例如,(牛奶,啤酒,尿布)=0.12).频繁物品集是支持度大于或等于最小支