数据挖掘算法

《数据挖掘算法》由会员分享，可在线阅读，更多相关《数据挖掘算法（8页珍藏版）》请在金锄头文库上搜索。

1、数据挖掘算法之-关联规则挖掘(Association Rule)(2009-09-20 21:59:23)转载&标签：分类：DMdm在数据挖掘的知识模式中，关联规则模式是比较重要的一种。关联规则的概念由 Agrawal、Imielinski、Swami提出，是数据中一种简单但很实用的规则。关联 规则模式属于描述型模式，发现关联规则的算法属于无监督学习的方法。一、关联规则的定义和属性考察一些涉及许多物品的事务：事务1中出现了物品甲，事务2中出现了 物品乙，事务3中则同时出现了物品甲和乙。那么，物品甲和乙在事务中的出 现相互之间是否有规律可循呢？在数据库的知识发现中，关联规则就是描述这种 在一个事

2、务中物品之间同时出现的规律的知识模式。更确切的说，关联规则通过 量化的数字描述物品甲的出现对物品乙的出现有多大的影响。现实中，这样的例子很多。例如超级市场利用前端收款机收集存储了大量的 售货数据，这些数据是一条条的购买事务记录，每条记录存储了事务处理时间， 顾客购买的物品、物品的数量及金额等。这些数据中常常隐含形式如下的关联规 则：在购买铁锤的顾客当中，有70 %的人同时购买了铁钉。这些关联规则很有 价值，商场管理人员可以根据这些关联规则更好地规划商场，如把铁锤和铁钉这 样的商品摆放在一起，能够促进销售。有些数据不像售货数据那样很容易就能看出一个事务是许多物品的集合， 但稍微转换一下思考角度，

3、仍然可以像售货数据一样处理。比如人寿保险，一份 保单就是一个事务。保险公司在接受保险前，往往需要记录投保人详尽的信息， 有时还要到医院做身体检查。保单上记录有投保人的年龄、性别、健康状况、工 作单位、工作地址、工资水平等。这些投保人的个人信息就可以看作事务中的物 品。通过分析这些数据，可以得到类似以下这样的关联规则：年龄在40岁以上， 工作在A区的投保人当中，有45 %的人曾经向保险公司索赔过。在这条规则中，“年龄在40岁以上”是物品甲，“工作在A区”是物品乙，“向保险公司索赔 过”则是物品丙。可以看出来，A区可能污染比较严重，环境比较差，导致工作 在该区的人健康状况不好，索赔率也相对比较高。

4、设R= I1,I2Im是一组物品集，W是一组事务集。W中的每个事务T是一组物品，T R。假设有一个物品集A，一个事务T，如果A T，则 称事务T支持物品集A。关联规则是如下形式的一种蕴含：A-B，其中A、B是 两组物品，A I，B I，且A AB=。一般用四个参数来描述一个关联规则 的属性：1 .可信度(Confidence)设W中支持物品集A的事务中，有c %的事务同时也支持物品集B，c %称为 关联规则A-B的可信度。简单地说，可信度就是指在出现了物品集A的事务T 中，物品集B也同时出现的概率有多大。如上面所举的铁锤和铁钉的例子，该 关联规则的可信度就回答了这样一个问题：如果一个顾客购买了

5、铁锤，那么他也 购买铁钉的可能性有多大呢？在上述例子中，购买铁锤的顾客中有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的期望可信度 度。期望可信度描述了在没有任何条件影响时，物

6、品集B在所有事务中出现的 概率有多大。如果某天共有1000个顾客到商场购买物品，其中有200个顾客购 买了铁钉，则上述的关联规则的期望可信度就是20 %。4 .作用度(Lift)作用度是可信度与期望可信度的比值。作用度描述物品集A的出现对物品 集B的出现有多大的影响。因为物品集B在所有事务中出现的概率是期望可信 度；而物品集B在有物品集A出现的事务中出现的概率是可信度，通过可信度 对期望可信度的比值反映了在加入“物品集A出现”的这个条件后，物品集B的 出现概率发生了多大的变化。在上例中作用度就是70 %/20 %=3.5。可信度是对关联规则的准确度的衡量，支持度是对关联规则重要性的衡量。支 持

7、度说明了这条规则在所有事务中有多大的代表性，显然支持度越大，关联规则 越重要。有些关联规则可信度虽然很高，但支持度却很低，说明该关联规则实用 的机会很小，因此也不重要。期望可信度描述了在没有物品集A的作用下，物品集B本身的支持度；作 用度描述了物品集A对物品集B的影响力的大小。作用度越大，说明物品集B受 物品集A的影响越大。一般情况，有用的关联规则的作用度都应该大于1，只有 关联规则的可信度大于期望可信度，才说明A的出现对B的出现有促进作用， 也说明了它们之间某种程度的相关性，如果作用度不大于1，则此关联规则也就 没有意义了。二、关联规则的挖掘在关联规则的四个属性中，支持度和可信度能够比较直接

8、形容关联规则的性 质。从关联规则定义可以看出，任意给出事务中的两个物品集，它们之间都存在 关联规则，只不过属性值有所不同。如果不考虑关联规则的支持度和可信度，那 么在事务数据库中可以发现无穷多的关联规则。事实上，人们一般只对满足一定 的支持度和可信度的关联规则感兴趣。因此，为了发现有意义的关联规则，需要 给定两个阈值：最小支持度和最小可信度，前者规定了关联规则必须满足的最小 支持度;后者规定了关联规则必须满足的最小可信度。一般称满足一定要求的(如 较大的支持度和可信度)的规则为强规则(Strong rules)。在关联规则的挖掘中要注意以下几点：1、充分理解数据。2、目标明确。3、数据准备工作

9、要做好。能否做好数据准备又取决于前两点。数据准备将 直接影响到问题的复杂度及目标的实现。4、选取恰当的最小支持度和最小可信度。这依赖于用户对目标的估计，如 果取值过小，那么会发现大量无用的规则，不但影响执行效率、浪费系统资源， 而且可能把目标埋没；如果取值过大，则又有可能找不到规则，与知识失之交臂。5、很好地理解关联规则。数据挖掘工具能够发现满足条件的关联规则，但 它不能判定关联规则的实际意义。对关联规则的理解需要熟悉业务背景，丰富的 业务经验对数据有足够的理解。在发现的关联规则中，可能有两个主观上认为没 有多大关系的物品，它们的关联规则支持度和可信度却很高，需要根据业务知识、 经验，从各个角

10、度判断这是一个偶然现象或有其内在的合理性；反之，可能有主 观上认为关系密切的物品，结果却显示它们之间相关性不强。只有很好的理解关 联规则，才能去其糟粕，取其精华，充分发挥关联规则的价值。发现关联规则要经过以下三个步骤：1、连接数据，作数据准备；2、给定最小支持度和最小可信度，利用数据挖掘工具提供的算法发现关联 规则；3、可视化显示、理解、评估关联规则。三、关联规则挖掘的过程关联规则挖掘过程主要包含两个阶段：第一阶段必须先从资料集合中找出所有的高频项目组(Frequent Itemsets),第二阶段再由这些高频项目组中产生关联规则(Association Rules)。关联规则挖掘的第一阶段必

11、须从原始资料集合中，找出所有高频项目组 (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 的项目 组

12、中再产生Large k+1，直到无法再找到更长的高频项目组为止。关联规则挖掘的第二阶段是要产生关联规则(Association Rules)。从高频项目 组产生关联规则，是利用前一步骤的高频k-项目组来产生规则，在最小信赖度 (Minimum Confidence)的条件门槛下，若一规则所求得的信赖度满足最小信赖度， 称此规则为关联规则。从上面的介绍还可以看出，关联规则挖掘通常比较适用与记录中的指标取 离散值的情况。如果原始数据库中的指标值是取连续的数据，则在关联规则挖掘 之前应该进行适当的数据离散化(实际上就是将某个区间的值对应于某个值)， 数据的离散化是数据挖掘前的重要环节，离散化的过程是

13、否合理将直接影响关联 规则的挖掘结果。四、关联规则的分类按照不同情况，关联规则可以进行分类如下：1. 基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的 关系；而数值型关联规则可以和多维关联或多层关联规则结合起来，对数值型字 段进行处理，将其进行动态的分割，或者直接对原始的数据进行处理，当然数值 型关联规则中也可以包含种类变量。例如：性别=“女”=职业=“秘书”，是布尔 型关联规则；性别=“女”=avg（收入）=2300，涉及的收入是数值类型，所以是 一个数值型关联规则。2. 基于规则中数据的抽象层次，可以分为单层关联

14、规则和多层关联规则。在单层的关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同 的层次的；而在多层的关联规则中，对数据的多层性已经进行了充分的考虑。例 如：IBM台式机=Sony打印机，是一个细节数据上的单层关联规则；台式机 =Sony打印机，是一个较高层次和细节层次之间的多层关联规则。3. 基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。在单维的关联规则中，我们只涉及到数据的一个维，如用户购买的物品；而 在多维的关联规则中，要处理的数据将会涉及多个维。换成另一句话，单维关联 规则是处理单个属性中的一些关系；多维关联规则是处理各个属性之间的某些关 系。例如：啤酒。尿布，这

15、条规则只涉及到用户的购买的物品；性别=“女”=职 业=“秘书”，这条规则就涉及到两个字段的信息，是两个维上的一条关联规则。5.关联规则挖掘的相关算法l.Apriori算法：使用候选项集找频繁项集Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心 是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔 关联规则。在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。该算法的基本思想是：首先找出所有的频集，这些项集出现的频繁性至少和 预定义的最小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小 支持度和最小可信度。然后使用第1步找到的频集产生

16、期望的规则，产生只包含 集合的项的所有规则，其中每一条规则的右部只有一项，这里采用的是中规则的 定义。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才 被留下来。为了生成所有频集，使用了递推的方法。可能产生大量的候选集，以及可能需要重复扫描数据库，是Apriori算法的两 大缺点。2. 基于划分的算法Savasere等设计了一个基于划分的算法。这个算法先把数据库从逻辑上分成 几个互不相交的块，每次单独考虑一个分块并对它生成所有的频集，然后把产生 的频集合并，用来生成所有可能的频集，最后计算这些项集的支持度。这里分块 的大小选择要使得每个分块可以被放入主存，每个阶段只需被扫描一次。而算法 的正确性是由每一个可能的频集至少在某一个分块中是频集保证的。该算法是可 以高度并行的，可以把每一分块分别分配给某一个处理器生成