搜索
一种基于Apriori算法的改进------close算法时间：2014.3Close算法原理Apriori算法核心回顾Apriori算法的瓶颈Close算法实现Apriori算法的改进主要内容1.算法设计目的：Apriori算法是数据挖掘中关联规则经典的算法之一，其设计目的找出数据库中两个看似无关的数据元素之间存在的隐藏的关联网。熟悉几个比较重要的概念：关联：若两个或多个变量的取值之间存在某种规律性，称之为关联。支持度：P(AUB)，即A和B这两个项集在事务集D中同时出现的概率，表示为support(A=B)，近似等于在D中A和B出现的次数/D中共有的元素总数．置信度：P(BIA)，即在出现项集A的事务集D中，项集B也同时出现的概率．表示为confidence（A=B),近似等价于在事物集D中出现A和B次数/A出现的次数。通过Apriori算法寻找：（1）所有的频繁项集。(2)在所获得的频繁项集中，产生相应的强关联规则。这样判断事物之间的关联关系。Apriori算法核心回顾2.算法实例分析：Apriori算法核心回顾TIDItemsT1I1,I3,I4T2I2,I3,I5T3I1,I2,I3,I5T4I2,I5原始事务集Support=2搜索过程Aprior运行过程图示扫描D对每个候选数据库计数3.总结算法运行过程进行多步处理：（1）简单统计所有含一个元素项目集出现的频率,并找出那些不小于最小支持度的项目集,即一维最大项目集.（2）~（k）：根据第（k-1）步生成的k-1为最大项目集产生k维侯选项目集,然后对数据库进行搜索,得到侯选项目集的项集支持度,与最小支持度比较,从而找到k维最大项目集.Apriori算法运行过程算法运行过程反应出：（1）在每一步产生侯选项目集时循环产生的组合过多，没有排除不应该参与组合的元素;（2）每次计算项集的支持度时，都对数据库D中的全部记录进行了一遍扫描比较，如果是一个大型的数据库的话，这种扫描比较会大大增加计算机系统的I/O开销。而这种代价是随着数据库的记录的增加呈现出几何级数的增加。对Apriori算法改进方向：探索新的理论和算法来减少数据库的扫描次数和侯选集空间占用，这里主要介绍：-------Close算法Apriori算法瓶颈1.Close算法改进方向：加速频繁项目集的生成，减少数据库库的扫描次数。2.Close算法改进基于的基本原理：一个频繁闭合项目集的所有闭合子集一定是频繁的；一个非频繁闭合项目集的所有闭合超集一定是非频繁的。3.基本概念（1）子集和超集：对于两个集合A与B，如果集合A的任何一个元素都是集合B的元素，而集合B中至少有一个元素不属于集合A，则称集合A是集合B的真子集，集合B为集合A的超集。Close算法原理（2）频繁项集若I={i1,i2,...,im}为项(Item)的集合,D={T1,T2,...,Tn},i∈[1,n]为事务数据集(TransactionDataItemsets),事务Ti由I中若干项组成。设S为由项组成的一个集合,S={i|i∈I}，简称项集(Itemset)。包含k个项的项集称为k-项集。S的支持度support(S)=（包含项集S的事务数量/D中总的事务数量的百分比）x100%若S的支持度≥给定最小支持度，称S为频繁项集(FrequentItemset)。t为一条事务,如果S⊆t,则称事务t包含S。（3）最大频繁项集如果频繁项集L的所有超集都是非频繁项集,那么称L为最大频繁项集Close算法原理（4）闭项集和频繁闭项集所谓闭项集，就是指一个项集X，它的直接超集的支持度计数都不等于它本身的支持度计数。如果闭项集同时是频繁的，也就是它的支持度大于等于最小支持度阈值，那它就称为频繁闭项集。例如，有交易数据库:因为项集{b,c}出现在TID为1,2,3的事务中，所以{b,c}的支持度计数为3。而{b,c}的直接超集：{a,b,c},{a,b,c,d}的支持度计数分别为2,1，都不等于{b,c}的支持度计数3，所以{b,c}为闭项集，如果支持度阈值为40%，则{b,c}也为闭频繁项集。项集{a,b}出现在TID为1,2的事务中，其支持度计数为2。而它的直接超集{a,b,c}支持度计数也为2，所以{a,b}不是闭项集。Close算法原理TIDitem1abc2abcd3bce4acde5de4.算法具体步骤：（1）查找频繁闭项集（2)生成频繁项目集（3）生成关联规则查找频繁闭合项集：利用频繁闭合i-项集为FCi，生成闭合（i+1）-项集，也就是FCi+1。基本过程大致描述为：首先找到候选1-项集，记为:FCC1，扫描数据库找到它的闭合以及support，得到候选闭合项集，修剪以后，得到FC1，与自身连接以后，得到FCC2，继续得到FC2…继续下去，知道FCCr为空，算法结束，得到频繁闭合项集。Close算法原理5.算法思想实例分析给出实例数据库，如下图所示：其中minsupport=2;Close算法原理TIDItemset123456789A，B，EB，DB，CA，B，DA，CB，CA，CA，B，C，EA，B，C（1）计算FCC1各个产生式的闭合与支持度。首先得到FCC1产生式：{A}、{B}、{C}、{D}、{E}。计算闭合集。1：{ABE}和{A}的闭合为：{ABE}4：现有A的闭合{ABE}和{ABD}取交集得到{A}闭合{AB}：5：现有A的闭合{AB}和{AC}取交集得到{A}的闭合：{A}7：现有A的闭合{A}和{AC}取交集得到{A}的闭合：{A}8：现有A的闭合{A}和{ABCE}取交集得到{A}的闭合：{A}9：现有A的闭合{A}和{ABC}取交集得到{A}的闭合：{A}5.算法思想实例分析同时计算{A}的支持度为6.同理得到{B}、{C}、{D}、{E}的闭合。列表如下：（2）进行修剪，减掉支持度小于2的，得到FC1，本例和FCC1相同。（3）利用FC1的产生项生成FCC2生成2-项目集，和apriori算法一样，然后将FC1中是FCC2的某个候选项选择出来，记为Sp，如果FCC1的这一项是Sp字母的闭合项则删除，得到FCC2。具体步骤如下：Close算法原理产生项闭合集支持度{A}{A}9{B}{B}7{C}{C}6{D}{BD}2{E}{ABE}25.算法思想实例分析计算中各式的闭合和支持度：Close算法原理2-项目集为：{AB}{AC}{AD}{AE}{BC}{BD}{BE}{CD}{CE}{DE}利用FC1筛选：{AE}和{BE}是{E}闭合{ABE}的子集，删除。得到FCC2：{AB,AC,AD,BC,BD,CD,CE,DE}产生项闭合集支持度{AB}{AB}4{AC}{AC}4{AD}{ABD}1{BC}{BC}4{BD}{BD}2{CE}{ABCE}15.算法思想实例分析(5)修剪得到FC2={AB,AC,BC,BD}(6)继续产生FCC3={ABC}，支持度为2.修剪以后得到FC3={ABC}.(7)生成FCC4，为空算法结束。得到所有不重复的闭合FC。FC={A,B,ABE,BD,C,AB,AC,BC,ABC}.(8)所有闭合集统计：L3={ABC,ABE},L2={AB,AC,BC,BD},L1={A,B,C}。最多的个数为3。L3频繁项分解，先分解{ABC}为{AB,AC,BC}全部在FC中，不用添加。然后分解{ABE}为{AB,AE,BE},将{AE,BE}加入L2。得到L2为={BD,AB,AC,BC,AE,BE}L2项分解：{A,B,C,D,E}，加入L1。得到的L1为={A,B,C,D,E};最终L3={ABC,ABE};Close算法原理6.Close算法与Apriori算法比较Apriori算法中，每个元素都需要扫描整个数据库来验证是否加入频繁项集。增加了I/o负载。close算法采用频繁闭合项目集来发现频繁项集，在一定程度上减少了数据库的扫描次数，减少了查找空间。Close算法原理本算法具体演示。Close算法演示