关联规则挖掘算法.ppt

文档介绍：关联规则挖掘算法演示文稿
第一页，共二十四页。
关联规则挖掘算法
第二页，共二十四页。
概述
关联规则(Association Rule Mining)挖掘是数据挖掘中最活跃的研究方法之一

第一页，共二十四页。
关联规则挖掘算法
第二页，共二十四页。
概述
关联规则(Association Rule Mining)挖掘是数据挖掘中最活跃的研究方法之一

其目的是为了发现超市交易数据库中不同商品之间的关联关系。
一个典型的关联规则的例子是：70%购买了牛奶的顾客将倾向于同时购买面包。
经典的关联规则挖掘算法：Apriori算法和FP-growth算法
第三页，共二十四页。
引例
假定某超市销售的商品包括：bread、bear、cake、cream、milk和tea
交易号TID
顾 客 购 买 商 品Items
T1
bread cream milk tea
T2
bread cream milk
T3
cake milk
T4
milk tea
T5
bread cake milk
T6
bread tea
T7
beer milk tea
T8
bread tea
T9
bread cream milk tea
T10
bread milk tea
第四页，共二十四页。
引例
项目与项集
设I={i1,i2,…,im}是m个不同项目的集合，每个ik(k=1，2，……，m)称为一个项目(Item)。
项目的集合I称为项目集合(Itemset)，简称为项集。其元素个数称为项集的长度，长度为k的项集称为k-项集(k-Itemset)。
第五页，共二十四页。
引例
交易
每笔交易T(Transaction)是项集I上的一个子集，即TI，但通常TI。
对应每一个交易有一个唯一的标识——交易号，记作TID
交易的全体构成了交易数据库D，或称交易记录集D，简称交易集D。
交易集D中包含交易的个数记为|D|。
第六页，共二十四页。
引例
项集的支持度
对于项集X，XI，设定count(XT)为交易集D中包含X的交易的数量
项集X的支持度support(X)就是项集X出现的概率，从而描述了X的重要性。
第七页，共二十四页。
引例
关联规则
关联规则(Association Rule)可以表示为一个蕴含式：
R：XY
第八页，共二十四页。
引例
关联规则的支持度
对于关联规则R：XY，其中XI,YI，并且XY=，规则R的的支持度(Support)是交易集中同时包含X和Y的交易数与所有交易数之比。
第九页，共二十四页。
引例
关联规则的可信度
对于关联规则R：XY，其中XI,YI，并且XY=，规则R的可信度(Confidence)是指包含X和Y的交易数与包含X的交易数之比
第十页，共二十四页。
引例
关联规则的最小支持度和最小可信度
关联规则的最小支持度也就是衡量频繁集的最小支持度(Minimum Support)，记为supmin，它用于衡量规则需要满足的最低重要性。规则的最小可信度(Minimum Confidence)记为confmin，它表示关联规则需要满足的最低可靠性。
第十一页，共二十四页。
引例
强关联规则
如果规则XY满足：support(XY)supmin且confidence(XY)confmin，称关联规则XY为强关联规则，否则称关联规则XY为弱关联规则。在挖掘关联规则时，产生的关联规则要经过supmin和confmin的衡量，筛选出来的强关联规则才能用于指导商家的决策。
第十二页，共二十四页。
1、Apriori算法
Apriori算法命名源于算法使用了频繁项集性质的先验（Prior）知识。
Apriori算法将发现关联规则的过程分为两个步骤：
通过迭代，检索出事务数据库中的所有频繁项集，即支持度不低于用户设定的阈值的项集；
利用频繁项集构造出满足用户最小信任度的规则。
挖掘或识别出所有频繁项集是该算法的核心，占整个计算量的大部分。
第十三页，共二十四页。
Apriori的性质：
性质1：频繁项集的所有非空子集必为频繁项集。
性质2：非频繁项集的超集一定是非频繁的。
第十四页，共二十四页。
Apri