关联分析又称关联挖掘,就是在交易数据、关系数据或其他信息载体中,查找存在于项目集合或对象集合之间的频繁模式、关联、相关性或因果结构。 或者说,关联分析是发现交易数据库中不同商品(项)之间的联系。 关联分析是一种简单、实用的分析技术,就是发现存在于大量数据集中的关联性或相关性,从而描述了一个事物中某些属性同时出现的规律和模式。 关联分析是从大量数据中发现项集之间有趣的关联和相关联系。关联分析的一个典型例子是购物篮分析。该过程通过发现顾客放人其购物篮中的不同商品之间的联系,分析顾客的购买习惯。通过了解哪些商品频繁地被顾客同时购买,这种关联的发现可以帮助零售商制定营销策略。其他的应用还包括价目表设计、商品促销、商品的排放和基于购买模式的顾客划分。 可从数据库中关联分析出形如“由于某些事件的发生而引起另外一些事件的发生”之类的规则。如“67%的顾客在购买啤酒的同时也会购买尿布”,因此通过合理的啤酒和尿布的货架摆放或捆绑销售可提高超市的服务质量和效益。又如“C语言课程优秀的同学,在学习‘数据结构’时为优秀的可能性达88%”,那么就可以通过强化“C语言”的学习来提高教学效果。 何为关联分析定义: 关联分析的最终目标就是要找出强关联规则。 1.Apriori算法电子商务中常用的一种数据挖掘方法就是从用户交易数据集中寻找商品之间的关联规则。关联规则中常用的一种算法是Apriori算法。该算法主要包含两个步骤:首先找出数据集中所有的频繁项集,这些项集出现的频繁性要大于或等于最小支持度;然后根据频繁项集产生强关联规则,这些规则必须满足最小支持度和最小置信度。 定义 算法步骤:1.找出出现频率最大的一个项L1。 候选集的计算过程 例如: L2 = {{A,C},{B,C},{B,E}{C,E}} Apriori性质 6.循环上述过程,直到得到空集C,即直到不能发现更大的频集L。 举个栗子假设给定如下电子商务网站的用户交易数据集,其中,定义最小支持度为2/9,即支持度计数为2,最小置信度为70%,现在要计算该数据集的关联规则,如图所示。 用户交易数据集 步骤1,根据Apriori算法计算频繁项集。 频繁1项集 2)根据频繁1项集,计算频繁2项集。首先将频繁1项集和频繁1项集进行连接运算,得到2项集,如下所示: 2项集 扫描用户交易数据集,计算包含每个候选2项集的记录数。 候选2项集 根据最小支持度,得到频繁2项集。 频繁2项集 3)根据频繁2项集,计算频繁3项集。首先将频繁2项集进行连接,得到{{I1,I2,I3},{I1,I2,I5},{I1,I3,I5},{I2,I3,I4},{I2,I3,I5},{I2,I4,I5}},然后根据频繁项集性质进行剪枝(第一种剪枝),即频繁项集的非空子集必须是频繁的。 频繁3项集 4)根据频繁3项集,计算频繁4项集。重复上述的思路,得到{I1,I2,I3,I5},根据频繁项集定理,它的子集{I2,I3,I5}为非频繁项集,所以移除该候选集。从而,频繁4项集为空,至此,计算频繁项集的步骤结束。 步骤2,根据频繁项集,计算关联规则。 规则1,{I1,I2}=>{I5},置信度为{I1,I2,I5}的支持度除以{I1,I2}的支持度,即2/4=50%,因其小于最小置信度,所以删除该规则。 缺点(1)在每一步产生侯选项目集时循环产生的组合过多,没有排除不应该参与组合的元素; (2)每次计算项集的支持度时,都对数据库D中的全部记录进行了一遍扫描比较,如果是一个大型的数据库的话,这种扫描比较会大大增加计算机系统的I/O开销。而这种代价是随着数据库的记录的增加呈现出几何级数的增加。因此人们开始寻求更好性能的算法。 改进1)基于划分的方法。该算法先把数据库从逻辑上分成几个互不相交的块,每次单独考虑一个分块并对它生成所有的频繁项集,然后把产生的频繁项集合并,用来生成所有可能的频繁项集,最后计算这些项集的支持度。这里分块的大小选择要使得每个分块可以被放入主存,每个阶段只需被扫描一次。而算法的正确性是由每一个可能的频繁项集至少在某一个分块中是频繁项集保证的。 2.FP-growth算法由于Apriori方法的固有缺陷.即使进行了优化,其效率也仍然不能令人满意。2000年,Han Jiawei等人提出了基于频繁模式树(Frequent Pattern Tree,简称为FP-tree)的发现频繁模式的算法FP-growth。在FP-growth算法中,通过两次扫描事务数据库,把每个事务所包含的频繁项目按其支持度降序压缩存储到FP—tree中。在以后发现频繁模式的过程中,不需要再扫描事务数据库,而仅在FP-Tree中进行查找即可,并通过递归调用FP-growth的方法来直接产生频繁模式,因此在整个发现过程中也不需产生候选模式。该算法克服了Apriori算法中存在的问颢.在执行效率上也明显好于Apriori算法。 构造FP-Tree挖掘频繁模式前首先要构造FP-Tree,算法伪码如下: 挖掘频繁模式对FP-Tree进行挖掘,算法如下: 举个栗子构建FP-tree 根据上面的例子,构建FP-tree。 频数 得到新的顺序: 用户交易排序数据集 FP-tree的根节点为null,不表示任何项。接下来,对事务型数据库进行第二次扫描,从而开始构建FP-tree: 第一条记录 由于第二条记录<I2,I4>与第一条记录有相同的前缀<I2>,因此<I2>的支持度加一,同时在(I2:2)节点下添加节点(I4:1)。所以,FP-tree中的第二条分支是<(I2:2),(I4:1)>: 第二条记录 第三条记录<I2,I3>与前两条记录相比,只有一个共同前缀<I2>,因此,只需要在(I2:3)下添加节点<I3:1>: 第三条记录 第四条记录<I2,I1,I4>与之前所有记录共同前缀<I2,I1>,因此在<I2,I1>节点下添加节点<I4>: 第四条记录 类似地,将第五条记录<I1,I3>作为FP-tree的一个分支,更新相关节点的支持度: 第五条记录 以此类推的到最后的树: FP-tree 综上,FP-tree的节点可以定义为:
从FP-tree中挖掘频繁模式(Frequent Patterns) 其中,第一条节点链表表示客户购买的物品清单<I2,I1,I3,I5>在数据库中共出现了1次。需要注意到是,尽管<I2,I4>在第一条节点链中出现了4次,单个物品<I2>出现了7次,但是它们与I5一起出现只有1次,所以在条件FP-tree中将<(I2:7),(I1:4),(I3:2),(I5:1)>记为<(I2:1),(I1:1),(I3:1),(I5:1)>。 同理,第二条节点链表示客户购买的物品清单<(I2:7),(I1:4),(I5:1)>在数据库中只出现了一次。 我们将p的前缀节点链<(I2:1),(I1:1),(I3:1),(I5:1)>和<(I2:1),(I1:1),(I5:1)>称为I5的条件模式基(conditional pattern base)。 我们将I5的条件模式基作为新的事务数据库,每一行存储p的一个前缀节点链,根据第二节中构建FP-tree的过程,计算每一行记录中各种物品的支持度,然后按照支持度降序排列,仅保留频繁项集,剔除那些低于支持度阈值的项,建立一棵新的FP-tree,这棵树被称之为I5的条件FP-tree: I5的条件FP-tree 从图可以看到I5的条件FP-tree中满足支持度阈值的剩下2个节点,所以以I5结尾的频繁项集有(I5:2),(I1,I5 :2),(I2,I5 :2),(I1,I2,I5 :2)。 同理可得I3的条件FP-tree: I3的条件FP-tree 得到以I3结尾的频繁项集有(I3:4),(I1,I3 :4),(I2,I3 :4),(I1,I2,I3 :2)。 于是,以I4结尾的频繁项集有(I4:2),(I2,I4 :2),以I2结尾的频繁项集有(I2:7),以I1结尾的频繁项集有(I1:6),(I2,I1 :4)。 最后计算关联。 |
|
来自: 甯静1 > 《数据分析算法及模型》