关联规则挖掘——Apriori算法PPT课件

.,1,关联规则Apriori挖掘,.,2,1.1概述,关联规则(AssociationRuleMining)挖掘是数据挖掘中最活跃的研究方法之一最早是由R.Agrawal等人提出的其目的是为了发现超市交易数据库中不同商品之间的关联关系。一个典型的关联规则的例子是：70%购买了牛奶的顾客将倾向于同时购买面包。经典的关联规则挖掘算法：Apriori算法和FP-growth算法,.,3,1.2引例,假定某超市销售的商品包括：bread、bear、cake、cream、milk和tea,.,4,1.2引例,定义1.1项目与项集设I=i1,i2,im是m个不同项目的集合，每个ik(k=1，2，m)称为一个项目(Item)。项目的集合I称为项目集合(Itemset)，简称为项集。其元素个数称为项集的长度，长度为k的项集称为k-项集(k-Itemset)。,.,5,1.2引例,定义1.2交易每笔交易T(Transaction)是项集I上的一个子集，即TI，但通常TI。对应每一个交易有一个唯一的标识交易号，记作TID交易的全体构成了交易数据库D，或称交易记录集D，简称交易集D。交易集D中包含交易的个数记为|D|。,.,6,1.2引例,定义1.3项集的支持度对于项集X，XI，设定count(XT)为交易集D中包含X的交易的数量项集X的支持度support(X)就是项集X出现的概率，从而描述了X的重要性。,.,7,1.2引例,定义1.5关联规则关联规则(AssociationRule)可以表示为一个蕴含式：R：XY,.,8,1.2引例,定义1.6关联规则的支持度对于关联规则R：XY，其中XI,YI，并且XY=，规则R的的支持度(Support)是交易集中同时包含X和Y的交易数与所有交易数之比。,.,9,1.2引例,定义1.7关联规则的可信度对于关联规则R：XY，其中XI,YI，并且XY=，规则R的可信度(Confidence)是指包含X和Y的交易数与包含X的交易数之比,.,10,1.2引例,定义1.8关联规则的最小支持度和最小可信度关联规则的最小支持度也就是衡量频繁集的最小支持度(MinimumSupport)，记为supmin，它用于衡量规则需要满足的最低重要性。规则的最小可信度(MinimumConfidence)记为confmin，它表示关联规则需要满足的最低可靠性。,.,11,1.2引例,定义1.9强关联规则如果规则XY满足：support(XY)supmin且confidence(XY)confmin，称关联规则XY为强关联规则，否则称关联规则XY为弱关联规则。在挖掘关联规则时，产生的关联规则要经过supmin和confmin的衡量，筛选出来的强关联规则才能用于指导商家的决策。,.,12,1、Apriori算法,Apriori算法命名源于算法使用了频繁项集性质的先验（Prior）知识。Apriori算法将发现关联规则的过程分为两个步骤：通过迭代，检索出事务数据库中的所有频繁项集，即支持度不低于用户设定的阈值的项集；利用频繁项集构造出满足用户最小信任度的规则。挖掘或识别出所有频繁项集是该算法的核心，占整个计算量的大部分。,.,13,Apriori的性质：,性质1：频繁项集的所有非空子集必为频繁项集。性质2：非频繁项集的超集一定是非频繁的。,.,14,Apriori的步骤：,连接步：为找Lk，通过将Lk-1与自身连接产生候选k项集的集合剪枝步：Ck是Lk的超集，也就是说，Ck的成员可以是也可以不是频繁的，但所有的频繁k项集都包含在Ck中。任何非频繁的（k-1）项集都不是频繁k项集的子集。,.,15,4.3.1Apriori算法,.,16,1.3.1Apriori算法,apriori_gen(Lk-1,supmin)算法,.,17,1.3.1Apriori算法,has_infrequent_subset(c,Lk-1)算法,.,18,Apriori算法实例,现有A、B、C、D、E五种商品的交易记录表，试找出三种商品关联销售情况(k=3)，最小支持度=50%。,.,19,实例解答,K=1,支持度50,.,20,.,21,Apriori算法的不足,可能产生大量的候选集需要重复扫描数据库,.,22,自己对Apriori小改进,在拼接存储时采用前缀树Trie优点：在拼接和剪枝时节约寻找时间。,.,23,Trie,一个节点的所有子孙节点拥有与该节点相同的字符串前缀，根节点与空字符串相关联。并不是每个节点都与值关联，仅叶节点和部分内部节点与值关联。,.,24,Trie,性质：根节点不包含字符，除根节点外每一个节点都只包含一个字符；从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；每个节点的