关联规则ASSOCIATION RULE

目录

关联规则

衡量指标

关联规则挖掘子任务

先验演算法APRIORI

两个原则:

频繁项集的计算:

频繁模式增长法Frequent Pattern-growth

1. 建立FP-tree

2. 挖掘FP-tree


关联规则

关联规则又称购物篮分析,指从看似相关却又不相同的交易记录中找出潜在有用的关联规则。

衡量指标

  • 支持度support:频率,表示某个或某些购买商品与总体购买商品之间的关系;如果某个项原本的支持度很低,即使关联性很强,也没有太多实际意义;实际使用时可以指定X的出现次数作为阈值。
    • 利用minimum support(min sup)最小支持度作为门槛来删除不重要的关联规则。
    • 关联规则ASSOCIATION RULE

  • 信赖度confidence:条件概率,买了X的人又买了Y的比例有多少,表示关联性的强弱,或者说是规则的可靠性。
    • 衡量关联规则是否具有可信度的指标,利用minimum confidence(min conf)最小信赖度作为门槛(一般选0.5),删除正确率较低的关联规则。
    • 关联规则ASSOCIATION RULE

  • 增益lift:增益值至少要大于1,表示该关联规则的预期结果比原本的表现好。

关联规则挖掘子任务

  • 频繁项集产生
  • 规则产生

先验演算法APRIORI

两个原则:

  • 如果一个集合是频繁项集,则其所有子集都是频繁项集。
  • 如果一个集合不是频繁项集,则其所有超集都不是频繁项集。

频繁项集的计算:

如图所示,设min sup=3,求出最长的频繁项目集。

关联规则ASSOCIATION RULE

  1. 将上图的交易信息转化为二元资料表

    二元资料表

    A蛋糕

    B奶茶

    C可乐

    D饼干

    E巧克力

    1

    0

    1

    1

    1

    1

    2

    0

    1

    1

    1

    0

    3

    1

    1

    0

    1

    0

    4

    1

    1

    1

    1

    1

    5

    1

    1

    1

    0

    0

    6

    0

    1

    0

    0

    1

  2. 统计出每个项目item出现的频次,并删除频次小于min sup的项目

    B奶茶

    C可乐

    D饼干

    A蛋糕

    E巧克力

    6

    4

    4

    3

    3

  3. 将上个步骤保留下来的项目组成集合,求每个项目集的出现频次,并删除频次小于min sup的项目集

    BC

    BD

    BA

    BE

    CD

    CA

    CE

    DA

    DE

    AE

    4

    4

    3

    3

    3

    2

    2

    2

    2

    1

  4. 重复上个步骤,直到求出最长的频繁项目集

    BCD

    BCA

    BCE

    BDA

    BDE

    BAE

    BACD

    BECD

    3

    2

    2

    2

    2

    1

    1

    2

综上所述,最长的频繁项目集为BCD。

频繁模式增长法Frequent Pattern-growth

目前最有效率的关联规则算法。将数据库内的频繁项目集压缩到一颗频繁模式树(FP-tree)之中,保留项目集之间的重要关联信息。此方法不需要大量的候选项目集,可大幅减少运算时间,并且只需要扫描资料库2次。

1. 建立FP-tree

min_sup:最小支持度,门槛值,

step1:统计所有项目item出现的次数,并删除次数小于min_sup的项目,然后降序排序(次数);

step2:根据上一步排序后的项目表,依序读取每一条资料,同时建立FT-tree;

FP-tree建立过程如下所示:

某超市之事物数据库(min sup=2)
交易记录 商品交易项目
1

A,B

2 B,C,D
3 A,C,D,E
4         A,D,E
5 A,B,C
6 A,B,C,D
7 A
8 A,B,C
9 A,B,D
10 B,C,E
  1. 统计项目频次
    项目 A B C D E
    频次 8 7 6 5 3
  2. 删除次数小于min sup=2的项目,并降序排列
    项目 A B C D E
    频次 8 7 6 5 3
  3. 根据上一步排序后的项目表,依序读取每一条资料,同时建立FP-tree关联规则ASSOCIATION RULE

2. 挖掘FP-tree

step1:根据上一步建立的FP-tree,分别以结点E、D、C、B、A作为结尾来挖掘;

step2:以step1选定的结点为条件,其余结点为结尾,分别进行挖掘;

重新设定路径数字:指从tree的叶子结点(频次不变)到NULL结点,逐一更新路径上结点的频次。

FP-tree挖掘过程如下所示:

  1. E作为结尾来挖掘,并重新设定路径数字关联规则ASSOCIATION RULE
  2. 删除频次小于min sup的项目,更新tree关联规则ASSOCIATION RULE
  3. {D,E}表示以E为条件下、D结尾,并重新设定路径数字关联规则ASSOCIATION RULE
  4. 删除频次小于min sup的项目,更新tree关联规则ASSOCIATION RULE
  5. {A,D}表示以D为条件下、A结尾                     关联规则ASSOCIATION RULE
  6. {C,E}表示以E为条件下、C结尾,并重新设定路径数字关联规则ASSOCIATION RULE
  7. 删除频次小于min sup的项目,更新tree关联规则ASSOCIATION RULE
  8. {A,E}表示以E为条件下、A结尾,并重新设定路径数字关联规则ASSOCIATION RULE

E为结尾的挖掘结果:

一阶 二阶 三阶
E D A
E C
E A

关联规则ASSOCIATION RULE

 以E为结尾的高频项目集:{E}、{D,E}、{C,E}、{A,E}、{A,D,E}。

同理:

  1. D作为结尾来挖掘,并重新设定路径数字关联规则ASSOCIATION RULE
  2. {C,D}表示以D为条件下、C结尾,并重新设定路径数字关联规则ASSOCIATION RULE
  3. {B,C}表示以C为条件下、B结尾,并重新设定路径数字关联规则ASSOCIATION RULE
  4. 删除频次小于min sup的项目,更新tree关联规则ASSOCIATION RULE
  5. {A,C}表示以C为条件下、A结尾,并重新设定路径数字(由于树中只有A,所以A仍然是2)关联规则ASSOCIATION RULE
  6. {B,D}表示以D为条件下、B结尾,并重新设定路径数字关联规则ASSOCIATION RULE
  7. {A,B}表示以B为条件下、A结尾,并重新设定路径数字(由于树中只有A,所以A仍然是2)关联规则ASSOCIATION RULE
  8. {A,D}表示以D为条件下、A结尾,并重新设定路径数字(由于树中只有A,所以A仍然是4)关联规则ASSOCIATION RULE 

D为结尾的挖掘结果:

一阶 二阶 三阶
D C B
D C A
D B

A

D A

关联规则ASSOCIATION RULE

 以D为结尾的高频项目集:{D}、{D,C}、{D,B}、{D,A}、{D,C,B}、{D,C,A}、{D,B,A}。

同理:

  1. C作为结尾来挖掘,并重新设定路径数字关联规则ASSOCIATION RULE
  2. {B,C}表示以C为条件下、B结尾,并重新设定路径数字关联规则ASSOCIATION RULE
  3. {A,B}表示以B为条件下、A结尾,并重新设定路径数字(由于树中只有A,所以A仍然是3)关联规则ASSOCIATION RULE
  4. {A,C}表示以C为条件下、A结尾,并重新设定路径数字(由于树中只有A,所以A仍然是4)关联规则ASSOCIATION RULE

C为结尾的挖掘结果:

一阶 二阶 三阶
C B A
C A

关联规则ASSOCIATION RULE

 以C为结尾的高频项目集:{C}、{C,B}、{C,A}、{C,B,A}。

同理:

  1. B作为结尾来挖掘,并重新设定路径数字关联规则ASSOCIATION RULE
  2. {A,B}表示以B为条件下、A结尾,并重新设定路径数字(由于树中只有A,所以A仍然是5)关联规则ASSOCIATION RULE

B为结尾的挖掘结果:

一阶 二阶 三阶
B A

关联规则ASSOCIATION RULE

 以B为结尾的高频项目集:{B}、{B,A}。

同理:

  1. A作为结尾来挖掘,并重新设定路径数字(由于树中只有A,所以A仍然是8)关联规则ASSOCIATION RULE

A为结尾的挖掘结果:

一阶 二阶 三阶
A

关联规则ASSOCIATION RULE

 以A为结尾的高频项目集:{A}。

上一篇:以太坊Geth RLP编码源码解析


下一篇:第10篇 geth命令参数详解