当前位置: 首页 > >

数据挖掘算法学*之Apriori算法

发布时间:

频繁模式:


??????? 频繁出现在数据集中的模式


??????? 譬如,一个商场一天出售的商品(大米,油,等)是一个数据集。频繁模式是一个子序列,如牙膏和牙刷总是在一起出现,则课看做一个频繁模式。




关联规则:


??????? 频繁模式可以使用关联规则表示,如:


??????? 牙刷=>牙膏


??????? 表示一个人买了牙刷后很可能买牙膏。




频繁项集:???


??? 项的集合称为项集。


??? 包含k个项的项集称为k项集


??? 项集出现的频数是包含项的事务数,称为支持度计数


??? 如果一个项集的支持度计数大于预定义的最小支持度计数,则称该项集为频繁项集




Apriori算法就是从数据集中找出所有的频繁项集,再产生所有的关联规则,计算其置信度,从而挖掘出需要的关联模式。


?????? 在介绍算法前先明确一个性质:任一频繁项集的所有非空子集也必须是频繁的。因为假如P(I)

?????? Apriori算法有两个主要步骤:连接步和剪枝步。


?????? 连接步


????? 为找出Lk(所有的频繁k项集的集合),通过将Lk-1(所有的频繁k-1项集的集合)与自身连接产生候选k项集的集合。候选集合记作Ck。设l1和l2是Lk-1中的成员。记li[j]表示li中的第j项。假设Apriori算法对事务或项集中的项按字典次序排序,即对于(k-1)项集li,li[1]


????? 剪枝步


????? CK是LK的超集,也就是说,CK的成员可能是也可能不是频繁的。通过扫描所有的事务(交易),确定CK中每个候选的计数,判断是否小于最小支持度计数,如果不是,则认为该候选是频繁的。为了压缩Ck,可以利用Apriori性质:任一频繁项集的所有非空子集也必须是频繁的,反之,如果某个候选的非空子集不是频繁的,那么该候选肯定不是频繁的,从而可以将其从CK中删除。

?????


???? Apriori算法的实例:


???? 下表为某商场交易事务记录,使用Apriori算法寻找频繁项集(假设最小支持度计数为2)

?????

?????? 先将所有单独商品出现的次数列出来为C1,去除所有支持度计数小于2的的到L1


???????


???????? 根据L1建立C2项集,找出他们的支持度计数,去除小于最小支持度的项


??????? 最后的到支持度为2的项集


??????? 所以,{I1,I2,I3},{I1,I2,I5}为满足条件的频繁项集。


???????


??????? 由频繁项集产生关联规则。


??????? 以上文中的频繁项集L = {I1,I2,I5}为例:L有非空子集{I1},{I2},{I5},{I1,I2},{I1,I5},{I2,I5},关联规则如下,其置信度为:??????


?????? 如果设置最小置信度为70%,那么只有第2,3和最后一个可以输出。

????? 这就是Apriori算法的主要过程。



友情链接: year2525网 工作范文网 QS-ISP 138资料网 528200 工作范文网 baothai 表格模版