管理案例网站,手机界面设计,字体设计软件 免费,电子商务网站建站流程转载自 推荐算法-关联分析#xff08;关联规则#xff09;关联分析又称关联挖掘#xff0c;就是在交易数据、关系数据或其他信息载体中#xff0c;查找存在于项目集合或对象集合之间的频繁模式、关联、相关性或因果结构。或者说#xff0c;关联分析是发现交易数据库中不…转载自 推荐算法-关联分析关联规则关联分析又称关联挖掘就是在交易数据、关系数据或其他信息载体中查找存在于项目集合或对象集合之间的频繁模式、关联、相关性或因果结构。或者说关联分析是发现交易数据库中不同商品项之间的联系。关联分析是一种简单、实用的分析技术就是发现存在于大量数据集中的关联性或相关性从而描述了一个事物中某些属性同时出现的规律和模式。关联分析是从大量数据中发现项集之间有趣的关联和相关联系。关联分析的一个典型例子是购物篮分析。该过程通过发现顾客放人其购物篮中的不同商品之间的联系分析顾客的购买习惯。通过了解哪些商品频繁地被顾客同时购买这种关联的发现可以帮助零售商制定营销策略。其他的应用还包括价目表设计、商品促销、商品的排放和基于购买模式的顾客划分。可从数据库中关联分析出形如“由于某些事件的发生而引起另外一些事件的发生”之类的规则。如“67%的顾客在购买啤酒的同时也会购买尿布”因此通过合理的啤酒和尿布的货架摆放或捆绑销售可提高超市的服务质量和效益。又如“C语言课程优秀的同学在学习‘数据结构’时为优秀的可能性达88%”那么就可以通过强化“C语言”的学习来提高教学效果。何为关联分析定义1、事务每一条交易称为一个事务例如示例1中的数据集就包含四个事务。2、项交易的每一个物品称为一个项例如Cola、Egg等。 3、项集包含零个或多个项的集合叫做项集例如{Cola, Egg, Ham}。4、k−项集包含k个项的项集叫做k-项集例如{Cola}叫做1-项集{Cola, Egg}叫做2-项集。5、支持度计数一个项集出现在几个事务当中它的支持度计数就是几。例如{Diaper, Beer}出现在事务 002、003和004中所以它的支持度计数是3。6、支持度支持度计数除于总的事务数。例如上例中总的事务数为4{Diaper, Beer}的支持度计数为3所以它的支持度是3÷475%说明有75%的人同时买了Diaper和Beer。关联规则A-B的支持度supportP(AB)指的是事件A和事件B同时发生的概率。7、频繁项集支持度大于或等于某个阈值的项集就叫做频繁项集。例如阈值设为50%时因为{Diaper, Beer}的支持度是75%所以它是频繁项集。8、前件和后件对于规则{Diaper}→{Beer}{Diaper}叫做前件{Beer}叫做后件。9、置信度对于规则{Diaper}→{Beer}{Diaper, Beer}的支持度计数除于{Diaper}的支持度计数为这个规则的置信度。例如规则{Diaper}→{Beer}的置信度为3÷3100%。说明买了Diaper的人100%也买了Beer。置信度confidenceP(B|A)P(AB)/P(A),指的是发生事件A的基础上发生事件B的概率。10、强关联规则大于或等于最小支持度阈值和最小置信度阈值的规则叫做强关联规则。关联分析的最终目标就是要找出强关联规则。1.Apriori算法电子商务中常用的一种数据挖掘方法就是从用户交易数据集中寻找商品之间的关联规则。关联规则中常用的一种算法是Apriori算法。该算法主要包含两个步骤首先找出数据集中所有的频繁项集这些项集出现的频繁性要大于或等于最小支持度然后根据频繁项集产生强关联规则这些规则必须满足最小支持度和最小置信度。上面提到了最小支持度和最小置信度事实上在关联规则中用于度量规则质量的两个主要指标即为支持度和置信度。那么什么是支持度和置信度呢接下来进行讲解。给定关联规则XY即根据X推出Y。形式化定义为定义算法步骤1.找出出现频率最大的一个项L1。2.根据L1找频繁“2项集”的集合C2.3.并剪掉不满足支持度阈值的项得到L2。4.根据L2找频繁“3项集”的集合C3。假设D表示交易数据集K为项集即包含k个项的集合Lk表示满足最小支持度的k项集Ck表示候选k项集。Apriori算法的参考文献描述如下。在该算法中候选集的计算过程如下所示候选集的计算过程例如: L2 {{A,C},{B,C},{B,E}{C,E}}那么 C3 {{A,B,C},{A,C,E},{B,C,E}}5.根据性质和支持度阈值进行剪枝得到L3。Apriori性质一个频繁项集的任一子集也应该是频繁项集。也就是生成一个k-itemset的候选项时如果这个候选项有子集不在(k-1)-itemset(已经确定是frequent的)中时那么这个候选项就不用拿去和支持度判断了直接删除。Apriori性质6.循环上述过程直到得到空集C即直到不能发现更大的频集L。7.计算最大频集L的非空子集两两计算置信度得到大于置信度阈值的强关联规则。举个栗子假设给定如下电子商务网站的用户交易数据集其中定义最小支持度为2/9即支持度计数为2最小置信度为70%现在要计算该数据集的关联规则如图所示。用户交易数据集步骤1根据Apriori算法计算频繁项集。1计算频繁1项集。扫描交易数据集统计每种商品出现的次数选取大于或等于最小支持度的商品得到了候选项集。频繁1项集2根据频繁1项集计算频繁2项集。首先将频繁1项集和频繁1项集进行连接运算得到2项集如下所示2项集扫描用户交易数据集计算包含每个候选2项集的记录数。候选2项集根据最小支持度得到频繁2项集。频繁2项集3根据频繁2项集计算频繁3项集。首先将频繁2项集进行连接得到{{I1I2I3}{I1I2I5}{I1I3I5}{I2I3I4}{I2I3I5}{I2I4I5}}然后根据频繁项集性质进行剪枝第一种剪枝即频繁项集的非空子集必须是频繁的。{I1I2I3}的2项子集为{I1I2}{I1I3}{I2I3}都在频繁2项集中则保留{I1I2I5}的2项子集为{I1I2}{I1I5}{I2I5}都在频繁2项集中则保留{I1I3I5}的2项子集为{I1I3}{I1I5}{I3I5}由于{I3I5}不是频繁2项集移除该候选集{I2I3I4}的2项子集为{I2I3}{I2I4}{I3I4}由于{I3I4}不是频繁2项集移除该候选集{I2I3I5}的2项子集为{I2I3}{I2I5}{I3I5}由于{I3I5}不是频繁2项集移除该候选集{I2I4I5}的2项子集为{I2I4}{I2I5}{I4I5}由于{I4I5}不是频繁2项集移除该候选集。通过剪枝得到候选集{{I1I2I3}{I1I2I5}}扫描交易数据库计算包含候选3项集的记录数第二种阈值剪枝。频繁3项集4根据频繁3项集计算频繁4项集。重复上述的思路得到{I1I2I3I5}根据频繁项集定理它的子集{I2I3I5}为非频繁项集所以移除该候选集。从而频繁4项集为空至此计算频繁项集的步骤结束。步骤2根据频繁项集计算关联规则。这里以频繁3项集{I1I2I5}为例计算关联规则。{I1I2I5}的非空子集为{I1I2}、{I1I5}、{I2I5}、{I1}、{I2}和{I5}。规则1{I1I2}{I5}置信度为{I1I2I5}的支持度除以{I1I2}的支持度即2/450%因其小于最小置信度所以删除该规则。同理最后可以得到{I1I5}{I2}{I2I5}{I1}和{I5}{I1I2}为3条强关联规则。缺点(1)在每一步产生侯选项目集时循环产生的组合过多没有排除不应该参与组合的元素;(2)每次计算项集的支持度时都对数据库D中的全部记录进行了一遍扫描比较如果是一个大型的数据库的话这种扫描比较会大大增加计算机系统的I/O开销。而这种代价是随着数据库的记录的增加呈现出几何级数的增加。因此人们开始寻求更好性能的算法。改进1基于划分的方法。该算法先把数据库从逻辑上分成几个互不相交的块每次单独考虑一个分块并对它生成所有的频繁项集然后把产生的频繁项集合并用来生成所有可能的频繁项集最后计算这些项集的支持度。这里分块的大小选择要使得每个分块可以被放入主存每个阶段只需被扫描一次。而算法的正确性是由每一个可能的频繁项集至少在某一个分块中是频繁项集保证的。上面所讨论的算法是可以高度并行的。可以把每一分块分别分配给某一个处理器生成频繁项集。产生频繁项集的每一个循环结束后处理器之间进行通信来产生全局的候选是一项集。通常这里的通信过程是算法执行时间的主要瓶颈。而另一方面每个独立的处理器生成频繁项集的时间也是一个瓶颈。其他的方法还有在多处理器之间共享一个杂凑树来产生频繁项集更多关于生成频繁项集的并行化方法可以在其中找到。2基于Hash的方法。Park等人提出了一个高效地产生频繁项集的基于杂凑Hash的算法。通过实验可以发现寻找频繁项集的主要计算是在生成频繁2—项集Lk上Park等就是利用这个性质引入杂凑技术来改进产生频繁2—项集的方法。3基于采样的方法。基于前一遍扫描得到的信息对它详细地做组合分析可以得到一个改进的算法其基本思想是先使用从数据库中抽取出来的采样得到一些在整个数据库中可能成立的规则然后对数据库的剩余部分验证这个结果。这个算法相当简单并显著地减少了FO代价但是一个很大的缺点就是产生的结果不精确即存在所谓的数据扭曲Dataskew。分布在同一页面上的数据时常是高度相关的不能表示整个数据库中模式的分布由此而导致的是采样5%的交易数据所花费的代价同扫描一遍数据库相近。4减少交易个数。减少用于未来扫描事务集的大小基本原理就是当一个事务不包含长度为志的大项集时则必然不包含长度为走k1的大项集。从而可以将这些事务删除在下一遍扫描中就可以减少要进行扫描的事务集的个数。这就是AprioriTid的基本思想。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算法伪码如下输入:一个交易数据库DB和一个最小支持度threshold.输出:它的FP-tree.步骤:1.扫描数据库DB一遍.得到频繁项的集合F和每个频繁项的支持度.把F按支持度递降排序,结果记为L.2.创建FP-tree的根节点,记为T,并且标记为’null’.然后对DB中的每个事务Trans做如下的步骤.根据L中的顺序,选出并排序Trans中的事务项.把Trans中排好序的事务项列表记为[p|P],其中p是第一个元素,P是列表的剩余部分.调用insert_tree([p|P],T).函数insert_tree([p|P],T)的运行如下.如果T有一个子结点N,其中N.item-namep.item-name,则将N的count域值增加1;否则,创建一个新节点N,使它的count为1,使它的父节点为T,并且使它的node_link和那些具有相同item_name域串起来.如果P非空,则递归调用insert_tree(P,N).挖掘频繁模式对FP-Tree进行挖掘算法如下输入:一棵用算法一建立的树Tree输出:所有的频繁集步骤:调用FP-growth(Tree,null).procedure FP-Growth ( Tree, x){(1)if (Tree只包含单路径P) then(2) 对路径P中节点的每个组合记为B(3) 生成模式B并x支持数B中所有节点的最小支持度(4) else 对Tree头上的每个aido{(5) 生成模式B ai 并 x支持度ai.support(6) 构造B的条件模式库和B的条件FP树TreeB(7)if TreeB ! 空集(8)**then **call FP-Growth ( TreeB , B )}}举个栗子构建FP-tree FP-growth算法通过构建FP-tree来压缩事务数据库中的信息从而更加有效地产生频繁项集。FP-tree其实是一棵前缀树按支持度降序排列支持度越高的频繁项离根节点越近从而使得更多的频繁项可以共享前缀。根据上面的例子构建FP-tree。频数得到新的顺序用户交易排序数据集FP-tree的根节点为null不表示任何项。接下来对事务型数据库进行第二次扫描从而开始构建FP-tree 第一条记录I2,I1,I5对应于FP-tree中的第一条分支(I2:1)(I1:1)(I5:1)第一条记录由于第二条记录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的节点可以定义为class TreeNode { private: String name; // 节点名称 int count; // 支持度计数 TreeNode *parent; // 父节点 VectorTreeNode * children; // 子节点 TreeNode *nextHomonym; // 指向同名节点 ... }从FP-tree中挖掘频繁模式Frequent Patterns 我们从头表的底部开始挖掘FP-tree中的频繁模式。在FP-tree中以I5结尾的节点链共有两条分别是(I2:7)(I1:4)(I3:2)(I5:1)和(I2:7)(I1:4)(I5:1)。其中第一条节点链表表示客户购买的物品清单I2I1I3I5在数据库中共出现了1次。需要注意到是尽管I2I4在第一条节点链中出现了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-treeI5的条件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)。最后计算关联。引用:http://baike.baidu.com/link?url3LCct6owUbtQJp8m-y5F-8VfpnRroF1-gVijGeI8J9znoZS1cWHxv2Z9kubuBMwDTIY5YUGm-8u0AhPO1xeU9lTFasXq0JiRuXmrMenhQm5bFxBpNrWOswuMO-kPx0je备注http://www.cnblogs.com/datahunter/p/3903413.html
