淘先锋技术网

首页 1 2 3 4 5 6 7

一、Apriori算法简介:

关联规则挖掘是数据挖掘领域的热点,关联规则反映一个对象与其他对象之间的相互依赖关系,如果多个对象之间存在-定的关联关系,那么一个对象可以通过其他对象进行预测。

关联规则挖掘一般可分成两个步骤:
        ①找出所有支持度大于等于最小支持度阈值的频繁项集。
        ②由频繁模式生成满足可信度阈值的关联规则。

二、基本概念:

 1、事物和项:

数据挖掘用到的基本数据集记为D,它是由事务构成的,- -般多存储于事务数据库中,表示为D={t1, t2,..,tm,.., tq},tk(k=1,2,..,. n)称为事务(Transaction) 。每一个事务可再细分,表示为tk={i1,i2,.,. in, .,. ip}, im(m=1, 2, .,. p)称为项(item),即事务是由若干个项组成的集合。每个事务可以用唯一的标识符事务编号TID来标识。设I={i1,i2, .,. ip} 是D中全体数据项组成的集合,I的任意子集X称为D中的项集(itemset) 。若项集中项的个数为k,称为k项集(k-itemset)。频繁项集是指出现次数较多的项集。

TID

商品

001

豆奶,莴苣

002

莴苣,啤酒,尿布,甜菜

003

豆奶,尿布,啤酒,橙汁

004

莴苣,豆奶,尿布,啤酒

005

莴苣,豆奶,尿布,橙

2、关联规则:

若X,Y均为项集,且XcI, YcI,并且x∩Y= 0,用蕴含式X=>Y表示一个关联规则。它表示某些项(X项集) 在一个事务中的出现,可推导出另一些项(Y项集)在同一事务中也出现。这里,“=>” 称为“关联”操作,X称为关联规则的前提,Y称为关联规则的结果。

3、支持度:

支持度表示该数据项在事务中出现的频度。数据项集 X的支持度support(X)是D中包含X的事务数量与D的总事务数量之比,如下公式所示。
         Support(x)= count(x)/ count(D)
       关联规则X=>Y的支持度等于项集X∪Y的支持度,如下公式所示。
         Support(X=>Y)= Support(X∪Y)= count(X∪Y)/ count(D)
       如果support(X)大于等于用户指定的最小支持度minsup,则称X为频繁项目集,否则称X为非频繁项目集。

TID

商品

001

豆奶,莴苣

002

莴苣,啤酒,尿布,甜菜

003

豆奶,尿布,啤酒,橙汁

004

莴苣,豆奶,尿布,啤酒

005

莴苣,豆奶,尿布,橙汁

Support(豆奶)=4/5=0.8

Support(尿布=>啤酒)=Support(尿布∪啤酒)=3/5=0.6

4、置信度:

置信度也称为可信度,规则X=>Y的置信度表示D中包含X的事务中有多大可能性也包含Y。表示的是这个规则确定性的强度,记作confidence(X=>Y)。通常,用户会根据自己的挖掘需要来指定最小置信度阈值,记为minconf。
                                      confidence(X∪Y)= support(X∪Y)/support(X)
       如果数据项集X满足support(X)>=minsup,则X是频繁数据项集。若规则X=>Y同时满足confidence(X=>Y)>=minconf,则称该规则为强关联规则,否则称为弱关联规则。一般由用户给定最小置信度阈值和最小支持度阈值。发现关联规则的任务就是从数据库中发现那些置信度、支持度大于等于给定最小阈值的强关联规则。

TID

商品

001

豆奶,莴苣

002

莴苣,啤酒,尿布,甜菜

003

豆奶,尿布,啤酒,橙汁

004

莴苣,豆奶,尿布,啤酒

005

莴苣,豆奶,尿布,橙汁

Support(豆奶)=4/5=0.8

Support(尿布=>啤酒)=Support(尿布∪啤酒)=3/5=0.6

Confidence(豆奶=>莴苣)=Support(豆奶∪莴苣)/Support(豆奶)=0.75

5、关联规则性质:

从基本概念的定义中得到关联规则具有如下性质:
       性质1:非频繁项集的超集一定是非频繁的。即如果X是非频繁项集,且X是Y的子集,则Y也是非频繁项集。

性质2:频繁项集的所有非空子集都必须也是频繁的。即如果Y是频繁的,且X∈Y,X≠∅成立,则X也一定频繁项集。

性质3:任意-个项集的支持度不小于其超集的支持度。即如果X是Y的子集,则support(X)>=support(Y)。这是因为根据定义,假设项集I的支持度小于最小支持度阈值(minsup),则I不是频繁的,如果把项A添加到I,则结果项集(AUI) 不可能比I出现更频繁,因此,结果项集也不是频繁的。假设事务是频繁项集,则定得到support (I-A)>=support(I),即频繁项集的非空项集-定是频繁的。反之却不可能成立。