Catalog
  1. 1. Apriori算法
    1. 1.1. 产生频繁项集
    2. 1.2. 示例
      1. 1.2.1. 分析
    3. 1.3. 从频繁项集产生关联规则
      1. 1.3.1. 分析
Apriori算法

Apriori算法

Apriori性质:

  • 频繁项集的所有非空子集也都必须是频繁的
  • 这是频繁项集的先验知识
  • 可以减少候选频繁项集的数量

Step1:通过迭代,检索出源数据中的所有频繁项集,即支持度不低于用户设定阈值的项集

Step2:利用第一步检索出的频繁项集构造出满足用户最小置信度的规则

产生频繁项集

算法

①k=1

②由(k-1)项集产生候选k-项集

③依据Apriori性质,对候选k-项集进行剪枝

④扫描数据库,统计各个项目的出现次数

⑤依据最小支持度,由候选k-项集中产生频繁k-项集

⑥K=k+1

⑦转②,直到k=n为止

约定

•Ck:第k次迭代产生的候选项集为候选k项集

•Lk:第k次迭代产生的频繁项集为频繁k项集

  1. 求频繁1项集L1

    以项目集合I作为候选1项集C1,扫描数据库1次,统计各个项目的出现次数,根据设定的最小支持度得出频繁1项集L1

  2. 求频繁k+1项集Lk+1

​ 对前k-1个项目相同的每两个k频繁模式执行join操作,得到候选k+1项集Ck+1

​ 根据Apriori性质,对Ck+1进行剪枝

  1. 扫描数据库一遍,确定每个c∈Ck+1的支持计数,据此得出频繁k+1项集Lk+1

    分析

    •每产生第K级的频繁项集,需要扫描数据库1次(计算支持度)

    •如何从k频繁项集得到候选k+1项集?

    –{a,b}+{a,c}=>{a,b,c}

    –{a,b}+{b,c}=>{}

    •通过k次迭代,可以产生长度从1到k的所有频繁项集

示例

看概念看得头痛,来个例子就很简单了,如下:

数据库

•D

事务

•T

项目

•{I1}、 {I2}、 {I3}、 {I4}、 {I5}

项目集合

•I={I1,I2,I3,I4,I5}

用户要求的最小支持度阈值

•s=20%

规则置信度

c=60%

这就是第一次迭代,产生频繁1-项集,说白了就是数次数

然后是第二次迭代,产生频繁2-项集,得出{I4,I5}不是频繁2-项集

再进行第三次迭代,产生频繁3-项集,得到要求结果。

分析
  • 先进行Apriori剪枝,再通过支持度删除
  • 负边界:所有非频繁,但符合Apriori性质的候选项集的集合
  • 负边界中的项集是非频繁的,但每个项集的所有子集都是频繁的
  • 负边界在改进算法中更为重要

从频繁项集产生关联规则

  1. 计算每一个频繁项集的子集

    如{I1,I2,I5}

    ​ {I1,I2}和{I5}

    ​ {I1,I5}和{I2}

    ​ {I2,I5}和{I1}

  2. 得到规则

    {I1,I2} →I5

    {I1,I5} →I2

    {I2,I5} →I1

  3. 计算规则的置信度

    比如c({I1,I2} →I5)=s({I1,I2,I5}/s{I1,I2} )=2/3

  4. 4.置信度c大于给定的阈值的规则为强关联规则

分析
  • 如何拆分并产生频繁项集的子集?

  • {a,b,c,d}

    {a,b,c} →d

    {a} →{b,c,d} ?

    {a,b} →{c,d} ?

  • 并不是所有被挖掘出的强关联规则都有意义

Author: Bbxren
Link: http://bbxren.site/2020/07/16/算法/Apriori算法/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Donate
  • 微信
  • 支付寶

Comment