Aphros的博客
文章 标签 分类
Aphros的博客

Contents

   1679 words   4 minutes 

关联规则

Apriori 算法

FP-growth 算法

FP树时一种输入数据的压缩表示，它通过逐个读入事务，并把事务映射到FP树中的一条路径来构造。

  • 由于不同的事务可能会有若干个相同的项，因此它们的路径可能部分重叠。

  • 路径相互重叠越多，使用FP树结构获得的压缩效果越好

  • 如果FP树足够小，能够存放在内存中，就可以直接从这个内存中的结构提取频繁项集，而不必重复地扫描存放在硬盘上的数据

算法描述

通过一个实例来说明 FP-growth 算法的挖掘过程，数据集中有 10 个事务，最小支持度为 2

  • 对数据集进行第一次扫描，得到它们的支持度计数，将支持度小于最小支持度 2 的元素消除（本例中无支持度小于2的元素）
  • 对数据集的每一条事务进行排序，保证项是有序的
  • 构建FP树，每个树节点都包含一个计数器和一个指针，计数器表示以此元素为头元素的事务总数，指针指向下一个同项节点
  • 初始，FP树仅包含一个根节点，用符号null标记
  • 对于每一条事务，按照项的顺序依次为FP树增加节点或者节点的计数，构建FP树
  • FP-growth以一种以自底向上的分治策略探索树，先查找以 e 结尾的频繁项集，接下来是d、c、b、a，
  • 以查找以 e 结尾的频繁项集为例：
    • 通过上述的FP树构造以e结尾的FP子树
    • 对子树进行第一次扫描，得到它们的支持度计数，将支持度小于最小支持度 2 的元素消除（b不满足支持度小于2，消除）
    • 首先检查项集{e}本身是否频繁
    • 如果它是频繁的，则考虑发现以de结尾的频繁项集子问题，接下来是 ce 和 ae
      • 对上述构造的FP子树分别以d、c、a结尾递归，再次构造FP子树，直到检查项集本身非频繁为止
      • 例如，在构造de子树时，发现a依然是频繁的，继续构造ade子树，无频繁集，终止递归
    • 每一个子问题可以进一步划分为更小的子问题，通过合并这些子问题的结果，就可以找到所有以e结尾的频繁项集

Relim 算法

Relim 算法是在FP-growth算法的基础上提出的一种新的不需要候选项集的频繁项集挖掘算法。

  • 它具有算法结构简单，空间利用率高，易于实现等显著优点

  • Relim 算法的主要思想和 FP-growth 相似，也是基于递归搜索(Recursive Exploration)

  • Relim 算法在运行时不必创建频繁模式树，而是通过建立一个事务链表组(transaction lists)来找出所有频繁项集

Relim 算法和 FP-growth 算法的性能比较

  • 算法结构：Relim 算法的结构比 FP-growth 算法简单。没有复杂的数据结构，易于实现。
  • 空间利用率：Relim 算法当一个事务链表中的关联项集被挖掘完后，此事务链表就被删除，所占的内存空间也就被释放，算法的空间利用率比 FP-growth 算法要高很多。
  • 运行速度：Relim 算法的运行速度与 FP-growth 算法相比并不慢，而且当对最小支持度高或者频繁规则比较少的数据集进行挖掘时，Relim 算法的运行速度往往比 FP-growth 算法要快。
  • 计算复杂度：Relim 算法在挖掘长模式的数据库时计算复杂，因此，只适合于挖掘短模式的数据库。

算法描述

通过一个实例来说明 Relim 算法的挖掘过程，数据集中有 10 个事务，最小支持度为 3

  • 对数据集（表1）进行第一次扫描，得到它们的支持度计数，按照支持度计数递增排序（表2）
  • 将支持度小于最小支持度 3 的元素消除，根据元素的支持度计数递增地将表一中的事务重新进行排列(表3)
    • 比如$(b,c,e,g)=>(b,c,e)=>(e,c,b)$
    • ==排列顺序不会影响挖掘结果，但对运行速度有影响。递增排列，运行速度最快，反之则最慢。==
  • 按照支持度由小到大创建单向数据链表，使每个元素的数据链表都包含一个计数器和一个指针，计数器表示以此元素为头元素的事务总数

http://192.168.0.103:7788/images/2022/08/21/image-20220821183123017.png

  • 检查e元素的支持度是否大于3，扫描以e元素为头元素的事务链表，将其作为新的数据集递归调用本算法，输出支持度大于 3 的项集{e}
  • 除去以e元素为头元素的事务链表，将其后继元素作为头元素加入到后面的事务链表中（图中灰色部分）

http://192.168.0.103:7788/images/2022/08/21/image-20220821183733906.png

  • 重复以上两个步骤，直到事务链表为空

工具包

  • 安装

    • pip install pymining

  • 挖掘频繁项集

from pymining import itemmining
transactions = (('a', 'b', 'c'), ('b'), ('a'), ('a', 'c', 'd '), ('b', 'c'), ('b', 'c')) 

# 使用 relim 方法
relim_input = itemmining.get_relim_input(transactions) 
report = itemmining.relim(relim_input, min_support=2)
# 使用 FP-growth 方法
fptree = itemmining.get_fptree(transactions) 
report = itemmining.fpgrowth(fptree, min_support=2)
# 使用 sam 方法
sam_input = itemmining.get_sam_input(transactions) 
report = itemmining.relim(sam_input, min_support=2)

print(report)
  • 挖掘关联规则
from pymining import itemmining, assocrules, perftesting
transactions = (('a', 'b', 'c'), ('b'), ('a'), ('a', 'c', 'd '), ('b', 'c'), ('b', 'c')) 
# 先挖掘频繁项集
relim_input = itemmining.get_relim_input(transactions)
report = itemmining.relim(relim_input, min_support=2)
# 再挖掘关联规则
rules = assocrules.mine_assoc_rules(report, min_support=2, min_confidence=0.5)
print(rules)
  • 挖掘频繁序列
from pymining import seqmining
seqs = ( 'caabc', 'abcb', 'cabc', 'abbca')
freq_seqs = seqmining.freq_seq_enum(seqs, 2)
sorted(freq_seqs)
Updated on 0001-01-01
Back | Home