关联规则挖掘——Apriori算法

1、关联规则Apriori挖掘,1.1 概述,关联规则(Association Rule Mining)挖掘是数据挖掘中最活跃的研究方法之一 最早是由R.Agrawal等人提出的 其目的是为了发现超市交易数据库中不同商品之间的关联关系。 一个典型的关联规则的例子是：70%购买了牛奶的顾客将倾向于同时购买面包。 经典的关联规则挖掘算法：Apriori算法和FP-growth算法,1.2 引例,假定某超市销售的商品包括：bread、bear、cake、cream、milk和tea,1.2 引例,定义1.1 项目与项集 设I=i1,i2,im是m个不同项目的集合，每个ik(k=1，2，m)称为一个项目(

2、Item)。 项目的集合I称为项目集合(Itemset)，简称为项集。其元素个数称为项集的长度，长度为k的项集称为k-项集(k-Itemset)。,1.2 引例,定义1.2 交易 每笔交易T(Transaction)是项集I上的一个子集，即TI，但通常TI。 对应每一个交易有一个唯一的标识交易号，记作TID 交易的全体构成了交易数据库D，或称交易记录集D，简称交易集D。 交易集D中包含交易的个数记为|D|。,1.2 引例,定义1.3 项集的支持度 对于项集X，XI，设定count(XT)为交易集D中包含X的交易的数量 项集X的支持度support(X)就是项集X出现的概率，从而描述了X的重要性

3、。,1.2 引例,定义1.5 关联规则 关联规则(Association Rule)可以表示为一个蕴含式： R：XY,1.2 引例,定义1.6 关联规则的支持度 对于关联规则R：XY，其中XI,YI，并且XY=，规则R的的支持度(Support)是交易集中同时包含X和Y的交易数与所有交易数之比。,1.2 引例,定义1.7 关联规则的可信度 对于关联规则R：XY，其中XI,YI，并且XY=，规则R的可信度(Confidence)是指包含X和Y的交易数与包含X的交易数之比,1.2 引例,定义1.8 关联规则的最小支持度和最小可信度 关联规则的最小支持度也就是衡量频繁集的最小支持度(Minimum

4、Support)，记为supmin，它用于衡量规则需要满足的最低重要性。规则的最小可信度(Minimum Confidence)记为confmin，它表示关联规则需要满足的最低可靠性。,1.2 引例,定义1.9 强关联规则 如果规则XY满足：support(XY)supmin且confidence(XY)confmin，称关联规则XY为强关联规则，否则称关联规则XY为弱关联规则。在挖掘关联规则时，产生的关联规则要经过supmin和confmin的衡量，筛选出来的强关联规则才能用于指导商家的决策。,1、Apriori算法,Apriori算法命名源于算法使用了频繁项集性质的先验（Prior）知识。

5、 Apriori算法将发现关联规则的过程分为两个步骤： 通过迭代，检索出事务数据库中的所有频繁项集，即支持度不低于用户设定的阈值的项集； 利用频繁项集构造出满足用户最小信任度的规则。 挖掘或识别出所有频繁项集是该算法的核心，占整个计算量的大部分。,Apriori的性质：,性质1：频繁项集的所有非空子集必为频繁项集。 性质2：非频繁项集的超集一定是非频繁的。,Apriori的步骤：,连接步：为找Lk ，通过将Lk-1与自身连接产生候选k项集的集合 剪枝步：Ck是Lk 的超集，也就是说，Ck的成员可以是也可以不是频繁的，但所有的频繁k项集都包含在Ck中。 任何非频繁的（k-1）项集都不是频繁k项集

6、的子集。,4.3.1 Apriori算法,1.3.1 Apriori算法,apriori_gen(Lk-1, supmin)算法,1.3.1 Apriori算法,has_infrequent_subset(c, Lk-1)算法,Apriori算法实例,现有A、B、C、D、E五种商品的交易记录表，试找 出三种商品关联销售情况(k=3)，最小支持度=50%。,实例解答,K=1,支持度50,Apriori算法的不足,可能产生大量的候选集 需要重复扫描数据库,自己对Apriori小改进,在拼接存储时采用前缀树Trie 优点：在拼接和剪枝时节约寻找时间。,Trie,一个节点的所有子孙节点拥有与该节点相同的字符串前缀，根节点与空字符串相关联。并不是每个节点都与值关联，仅叶节点和部分内部节点与值关联。,Trie,性质：根节点不包含字符，除根节点外每一个节点都只包含一个字符； 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串； 每个节点的