Contents

关联规则

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)