Apriori算法

 


 

介绍

Apriori算法是Agrawal
R.Srikant1994年提出的,为布尔关联规则挖掘频繁项集的原创性算法。算法使用频繁项集性质的先验知识。

算法描述

Apriori算法使用一种称为逐层搜索的迭代方法,其中K项集用于探索(K1)项集。首先,通过扫描数据库,累计每个项的计数,并收集满足最小支持度的项,找出频繁1项集的集合。该集合记为L1。然后,使用L1找出频繁2项集点集合L2,使用L2找出L3,如此下去,直到不能再找到频繁K项集。

 

1、Apriori算法伪代码

输入:

        D:事务数据库

        min_sup: 最小支持度阈值

输出:

        L,D中的频繁项集

方法:

    

 

2、实例

表1:某分店的事物数据

TID

商品ID的列表

TID

商品ID的列表

T100

I1,I2,I5

T600

I2,I3

T200

I2,I4

T700

I1,I3

T300

I2,I3

T800

I1,I2,I3,I5

T400

I1,I2,I4

T900

I1,I2,I3

T500

I1,I3

  

  

 

某分店的事务数据库D,该数据库有9个事务。{ D }=9。使用Apriori算法发现D中的频繁项集。假设最小支持度计数为2,即min_sup=2



算法使用L3 ⋈ L3产生4相集的集合C4。连接产生结果{ I1,I2,I3,I5 },支持度1< min_sup=2,该相集被裁减掉,C4=⊘,因此算法终止,找出了所有的频繁项集{ I1,I2,I3 },{ I1,I2,I5 }。



分类: 算法

1 条评论

剪枝搜索策略 – Christopher · 2019年1月1日 下午12:09

[…]    剪裁搜索算法实例-Apriori算法 […]

发表评论

电子邮件地址不会被公开。 必填项已用*标注