关联规则挖掘Apriori算法

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