Apriori算法介绍PPT

Apriori算法最新研究进展Apriori算法背景1Apriori算法基本思想2Apriori算法的缺陷3Apriori算法的改进4关联规则算法的发展5Apriori算法代码实现6目录CONTENTS改进Apriori算法在股票分析中的应用研究7Apriori算法背景01Apriori算法背景自然界中的普遍性的形式就是规律--------马克思”“Apriori算法背景当我们从普遍发生的事件中，找到其中的关联和规律，那我们就能得到一些突破。在1993年，Agrawal等人针对购物篮问题进行分析提出了第一个关联规则挖掘算法----Apriori算法，其目的是为了发现交易数据库中不同商品之间的联系规则。这些规则刻画了顾客购买行为模式，可以用来指导商家科学地安排进货，库存以及货架设计等。“”算法的应用场景01Apriori算法背景1.Apriori算法广泛应用于商业中，应用于消费市场价格分析中它能够很快的求出各种产品之间的价格关系和它们之间的影响。通过数据挖掘，市场商人可以瞄准目标客户，采用个人股票行市、最新信息、特殊的市场推广活动或其他一些特殊的信息手段，从而极大地减少广告预算和增加收入。百货商场、超市和一些老字型大小的零售店也在进行数据挖掘，以便猜测这些年来顾客的消费习惯。2.Apriori算法应用于网络安全领域，比如网络入侵检测技术中早期中大型的电脑系统中都收集审计信息来建立跟踪档，这些审计跟踪的目的多是为了性能测试或计费，因此对攻击检测提供的有用信息比较少。它通过模式的学习和训练可以发现网络用户的异常行为模式。采用作用度的Apriori算法削弱了Apriori算法的挖掘结果规则，是网络入侵检测系统可以快速的发现用户的行为模式，能够快速的锁定攻击者，提高了基于关联规则的入侵检测系统的检测性。Apriori算法背景3.Apriori算法应用于高校管理中随着高校贫困生人数的不断增加，学校管理部门资助工作难度也越加增大。针对这一现象，提出一种基于数据挖掘算法的解决方法。将关联规则的Apriori算法应用到贫困助学体系中，并且针对经典Apriori挖掘算法存在的不足进行改进，先将事务数据库映射为一个布尔矩阵，用一种逐层递增的思想来动态的分配内存进行存储，再利用向量求与运算，寻找频繁项集。实验结果表明，改进后的Apriori算法在运行效率上有了很大的提升，挖掘出的规则也可以有效地辅助学校管理部门有针对性的开展贫困助学工作。4.Apriori算法被广泛应用于移动通信领域移动增值业务逐渐成为移动通信市场上最有活力、最具潜力、最受瞩目的业务。Apriori算法被很多公司应用。依托某电信运营商正在建设的增值业务Web数据仓库平台，对来自移动增值业务方面的调查数据进行了相关的挖掘处理，从而获得了关于用户行为特征和需求的间接反映市场动态的有用信息，这些信息在指导运营商的业务运营和辅助业务提供商的决策制定等方面具有十分重要的参考价值。5.在地球科学数据分析中关联模式可以揭示海洋、陆地和大气过程之间的有意义的关系。这些信息能够帮助地球科学家更好的理解地球系统中不同的自然力之间的相互作用。举一个例子02Apriori算法背景下面这个表格是代表一个事务数据库D，其中最小支持度为50%，最小置信度为70%，求事务数据库中的频繁关联规则。Apriori算法背景（1）生成候选项目集C1={{面包}，{牛奶}，{啤酒}，{花生}，{尿布}}。求解步骤如下：Apriori算法背景C1={{面包}，{牛奶}，{啤酒}，{花生}，{尿布}}(2)扫描事务数据库D，计算C1中每个项目集在D中的支持度。从事务数据库D中可以得出每个项目集的支持数分别为3,3,3,1,2，事务数据库D的项目集总数为4，因此可得出C1中每个项目集的支持度分别为75%，75%，75%，25%，50%。根据最小支持度为50%，可以得出频繁项目集L1={{面包}，{牛奶}，{啤酒}，{尿布}}。Apriori算法背景L1={{面包}，{牛奶}，{啤酒}，{尿布}}(3)根据L1自连接L1⋈L1生成候选项目集C2={{面包，牛奶}，{面包，啤酒}，{面包，尿布}，{牛奶，啤酒}，{牛奶，尿布}，{啤酒，尿布}}。Apriori算法背景C2={{面包，牛奶}，{面包，啤酒}，{面包，尿布}，{牛奶，啤酒}，{牛奶，尿布}，{啤酒，尿布}}(4)扫描事务数据库D，计算C2中每个项目集在D中的支持度。从事务数据库D中可以得出每个项目集的支持数分别为3,2,1,2,1,2，事务数据库D的项目集总数为4，因此可得出C2中每个项目集的支持度分别为75%，50%，25%，50%，25%，50%。根据最小支持度为50%，可以得出频繁项目集L2={{面包，牛奶}，{面包，啤酒}，{牛奶，啤酒}，{啤酒，尿布}}。Apriori算法背景L2={{面包，牛奶}，{面包，啤酒}，{牛奶，啤酒}，{啤酒，尿布}}(5)根据L2⋈L2生成候选项目集C3={{面包，牛奶，啤酒}，{面包，啤酒，尿布}，{牛奶，啤酒，尿布}}，由于C3中项目集{面包，啤酒，尿布}中的一个子集{面包，尿布}是L2中不存在的，因此可以去除。同理项目集{牛奶，啤酒，尿布}也可去除。因此C3={{面包，牛奶，啤酒}}。Apriori算法背景C3={{面包，牛奶，啤酒}}(6)扫描事务数据库D，计算C3中每个项目集在D中的支持度。从事务数据库D中可以得出每个项目集的支持数分别为2，事务数据库D的项目集总数为4，因此可得出C2中每个项目集的支持度分别为50%。根据最小支持度为50%，可以得出频繁项目集L3={{面包，牛奶，啤酒}}。Apriori算法背景(7)L=L1UL2UL3={{面包}，{牛奶}，{啤酒}，{尿布}，{面包，牛奶}，{面包，啤酒}，{牛奶，啤酒}，{啤酒，尿布}，{面包，牛奶，啤酒}}。Apriori算法背景(8)我们只考虑项目集长度大于1的项目集，例如{面包，牛奶，啤酒}，它的所有非真子集{面包}，{牛奶}，{啤酒}，{面包，牛奶}，{面包，啤酒}，{牛奶，啤酒}，分别计算关联规则{面包}—{牛奶，啤酒}，{牛奶}—{面包，啤酒}，{啤酒}—{面包，牛奶}，{面包，牛奶}—{啤酒}，{面包，啤酒}—{牛奶}，{牛奶，啤酒}—{面包}的置信度，其值分别为67%，67%，67%，67%，100%，100%。由于最小置信度为70%，可得}，{面包，啤酒}—{牛奶}，{牛奶，啤酒}—{面包}为频繁关联规则。也就是说买面包和啤酒的同时肯定会买牛奶，买牛奶和啤酒的同时也是会买面包。关联规则定义：给定一组事务，寻找预测“某些项将会随其他项的出现而出现”的规则。例如：{面包，啤酒}→{牛奶}注：蕴含符号“→”表现共现关系，而不是因果关系算法的基本概念03Apriori算法背景形如：X→Y，whereX∈I，Y∈IandX∩Y=∅项集K-项集一个或多个项的集合例如：{面包}、{面包、啤酒}包含K个项的项集例如：C1={{面包}，{牛奶}，{啤酒}，{花生}，{尿布}}就是一个5-项集Apriori算法背景候选项集频繁项集用来获取频繁项集的候选项集，候选项集中满足支持度条件的项集保留，不满足条件的舍弃。在所有训练元组中同时出现的次数超过人工定义的阈值的项集（支持度=最小支持度的集合）。Apriori算法背景候选项集：例如：C1={{面包}，{牛奶}，{啤酒}，{花生}，{尿布}}频繁项集：例如：根据最小支持度为50%，从C1可以得出频繁项目集L1={{面包}，{牛奶}，{啤酒}，{尿布}}。Apriori算法背景频繁项集——基本原则1.任意一个频繁项集，它所有的非空子集都必须是频繁的。2.如果一个项集是不频繁的，那他的超集一定是不频繁的。Apriori算法背景规则评估标准——支持度、置信度支持度（support）：关联数据在数据集中出现的次数或所占的比重。置信度（confidence）：置信度表示Y数据出现后，X数据出现的可能性，也可以说是数据的条件概率。Apriori算法背景强关联规则：满足最小支持度和最小置信度的关联规则。{面包}→{牛奶}support(面包→牛奶)=∣面包∪牛奶∣∣D∣=34confidence(面包→牛奶)=P(面包牛奶)P(面包)=3434=1举例Apriori算法背景Apriori算法背景买咖啡不买咖啡合计买牛奶20525不买牛奶70575合计9010100设定minsup=0.2，minconf=0.6，按照现有的挖掘算法可得到关联规则：规则一：买牛奶→买咖啡s=20/100=0.2c=20/25=0.880%的人买了牛奶就会买咖啡，但是90%的人肯定会买咖啡，即买牛奶对买咖啡这件事的刺激作用并没有想象中的大规则二：买咖啡→不买牛奶s=70/100=0.7c=70/90=0.78可以看出规则二更具有商业销售的指导意义关联规则的兴趣度04Apriori算法背景从上例可知，之前的挖掘算法只能挖掘出类似于规则一的规则，而对于类似规则二的带有类似于“不买牛奶”之类的负属性项的规则却无能为力，而这种知识往往具有更重要的价值。所以对于不购买商品的事务与购买商品的事务的关系的研究，引入兴趣度：𝐼𝐴→𝐵=𝑃(𝐴𝐵)𝑃𝐴𝑃(𝐵)𝐼(𝐴→𝐵)=1：A的出现和B的出现是相互独立的𝐼(𝐴→𝐵)1：A的出现和B的出现是负相关的𝐼(𝐴→𝐵)1：A的出现和B的出现是正相关的（A的出现蕴含Ｂ的出现）兴趣度的使用：一条规则的兴趣度越大于1，则其实际利用价值越大一条规则的兴趣度越小于1，则其反面规则的实际利用价值越大Apriori算法背景RulesSCI1买牛奶→买咖啡0.20.80.892买咖啡→买牛奶0.20.220.893买牛奶→不买咖啡0.050.224不买咖啡→买牛奶0.050.525不买牛奶→买咖啡0.70.931.0376买咖啡→不买牛奶0.70.781.0377不买牛奶→不买咖啡0.050.0670.678不买咖啡→不买牛奶0.050.20.87基于咖啡和牛奶的例子，列出所有可能的规则描述及其对应的支持度、可信度和兴趣度：在此只考虑第1、2、3、6四条规则，由于I1，I2＜1，因此在实际中它的价值不大，I3，I6＞1都可以列入进一步考虑的范围Apriori算法背景上述兴趣度的公式可以等价于：𝐼𝐴→𝐵=𝑃𝐴𝐵𝑃𝐴𝑃𝐵=𝐴𝐵𝐷𝐴𝐷·𝐵𝐷=𝑃(𝐵∣𝐴)𝑃(𝐵)有人也称上述公式为作用度（Lift），表示关联规则A→B的“提升”，所以I（A→B）也被称为提升度。如果作用度不大于1，则此关联规则就没有意义可信度：是对关联规则准确度的衡量兴趣度：是项集A对项集B的影响力的大小的衡量支持度：是对关联规则重要性的衡量兴趣度越大，说明项集B受项集A的影响越大Apriori算法基本思想02关于Apriori算法1，Apriori算法是Agrawal和R.Snikant于1994年提出的，为布尔关联规则挖掘频繁项集的原创性算法。2，Apriori算法的思想正如其名字那样，使用频繁项集的先验知识，使用的是一种称为逐层搜索的迭代方法，运用k-项集来生成k+1项集。”“算法的基本思想通过扫描数据库，累计每个项的计数，并收集满足最小支持度的项，找出频繁1项集的集合。记该集合为L1.然后，使用L1找出频繁2项集的集合L2，使用L2找出L3，如此类推，直到不能再找到频繁k项集为止。为了提高频繁项集逐层产生的效率，一种称为先验性质的重要性质用于压缩搜素空间。”“”“先验性质1，先验性质：频繁项集的所有非空子集也一定是频繁的。2，该性质表明，如果项集B不满足最小阈值min-sup，则B不是频繁的，即P(B)min-sup。如果项A添加到B，则结果项集（即B∪A）不可能比B更频繁的出现。因此B∪A也不是频繁的，即P（B∪A）min-sup连接步01剪枝步02如何进行迭代连接步连接步为找出Lk，通过将Lk-1与自身连接产生候选k项集的集合。该候选项集的集合记为Ck。