所有文章 标签 分类

目录

目录

关联规则挖掘：Apriori 算法

MartinLwx  收录于  类别 ML-DL
     约 2450 字   预计阅读 11 分钟 

最近的工作中需要分析大量安卓 Apk 的特征关联，这些特征包括 IP 特征、URL 特征、权限特征等。特征关联指的是从数据中挖掘哪些特征之间存在关联，比如某些特征组合经常一起出现

如果依靠人工经验的话，数据量太大不大现实，就在这时我想起了以前数据挖掘课程上学过的一个算法：Apriori 算法 :)

Question

如何定义频繁呢？用 “支持度” 度量

Apriori 算法是一种关联规则挖掘算法，用于发现数据中的频繁项集（Frequent itemsets），这里频繁项集的意思就是经常一起出现的项集（Itemset）。基于频繁项集就可以发现一些关联规则

用一个具体的例子说明，你现在手头有很多用户的购物车清单，每个购物车里包含多件商品，Apriori 算法可以帮助你发现不同用户的购物车商品是否存在如下的关联：哪些商品经常会一起出现在同一个购物车里

在具体看 Apriori 算法是如何工作之前，有必要了解下面几个相关的指标

$$ Support(A) = \frac{\texttt{Count(records contains item A) }}{\texttt{Count(records)}} $$

从概率论的角度来看，$Support(A)$ 就是无条件概率 $P(A)$

$$ Confidence(A\rightarrow B)= \frac{\texttt{Count(records contains item A and item B)}}{\texttt{Count(records contains item A)}} $$

从概率论的角度来看，$Confidence(A\rightarrow B)$ 就是条件概率 $P(B|A)$。因此，这里的 $A\rightarrow B$ 就是关联规则，$Confidence(A\rightarrow B)$ 表示 $A$ 出现的情况下 $B$ 出现的概率

$$ \begin{split} Lift(A\rightarrow B)&= \frac{\texttt{Count(records contains item A and item B)}}{\texttt{Count(records contains item A)}\times\texttt{Count(records contains item B)}}\times{\texttt{Count(records)}}\\\ &=\frac{Confidence(A\rightarrow B)}{Support(B)} \end{split} $$

提升度本质上衡量的是规则 $A\rightarrow B$ 的有效性（即 $A$ 的出现对 $B$ 的出现是否有提升作用）

  • 如果 $A$ 出现和 $B$ 出现是独立的，那么显然 $Lift(A\rightarrow B)=1$
  • 如果 $A$ 出现和 $B$ 出现是正相关，那么显然 $Lift(A\rightarrow B)>1$
  • 如果 $A$ 出现和 $B$ 出现是反相关，那么显然 $Lift(A\rightarrow B)<1$

Apriori 算法有 2 个主要步骤

Tip

为了方便描述问题，下面称大小为 $k$ 的项集为 $k$-itemset

挖掘频繁项集是一个比较复杂的任务，因为可能的项集太多了，根据集合论的知识，如果一个项集有 $n$ 项，那么它会有 $2^n-1$ 个可能的非空项集组合。当 $n$ 的时候，暴力算法肯定要运行很久，那么有更好的办法吗？

Apriori 算法注意到了一点：频繁项集的子集肯定也是频繁项集，这句话可以反过来运用：如果一个项集不是频繁项集，那么它的超集也不是频繁项集。这样就可以在构造频繁项集的时候进行剪枝，这叫做 Apriori 性质

Apriori 提取频繁项集的算法如下所示

输入：原始数据（假设一共有 $n$ 个不同的项）、最小支持度 $\epsilon_{support}$

输出：频繁项集

算法流程：

  1. 构造 $n$ 个 $1$-itemset，每个项集都会计算对应的支持度
  2. 检查每个候选 $1$-itemset，如果发现支持度 $<\epsilon_{support}$，那么就去掉这个项集。过滤之后的 $1$-itemset 就是频繁 $1$-itemset
  3. 构造 $2$-itemset，办法就是用频繁 $1$-itemset 两两组合（大小不为 $2$ 的项集不在考虑范围之内）
  4. （Apriori 性质）检查每个候选 $2$-itemset 的 $1$-itemset，如果发现支持度 $<\epsilon_{support}$，那么就去掉这个候选 $2$-itemset
  5. 检查上一步留下的候选 $2$-itemset 并计算支持度，如果发现支持度 $<\epsilon_{support}$，那么就去掉这个项集。过滤之后的 $2$-itemset 就是频繁 $2$-itemset
  6. 构造 $3$-itemset，办法就是用频繁 $2$-itemset 两两组合（大小不为 $3$ 的项集不在考虑范围之内）
  7. （Apriori 性质）检查每个候选 $3$-itemset 的 $2$-itemset，如果发现支持度 $<\epsilon_{support}$，那么就去掉这个候选 $3$-itemset
  8. 检查上一步留下的候选 $3$-itemset 并计算支持度，如果发现支持度 $<\epsilon_{support}$，那么就去掉这个项集。过滤之后的 $3$-itemset 就是频繁 $3$-itemset
  9. …

不难发现 Apriori 算法总是用频繁 $k-1$-itemset 生成候选 $k$-itemset。因此，当频繁 $k-1$-itemset 为空的时候，Apriori 算法也就停止了

我用 Mermaid 画了个图示

flowchart
    itemsets --> gen(Generate k-itemset candidates)
    gen --> prune1("Prune k-itemsets if ANY k-1-itemset < min_support")
    prune1 --> prune2(Prune k-itemsets if < min_support)
    prune2 -->freq(Get freq k-itemsets)
    freq --> |increase k| gen

输入：发现的频繁项集，最小置信度 $\epsilon_{conf}$

算法流程：

  • 对于每个频繁项集 $I$
    • 枚举除了 $I$ 自己以外的所有非空子集 $S$
    • 形成关联规则 $S\rightarrow I-S$，检查它的置信度 $Suport(I)/Support(S)$ 是否大于 $\epsilon_{conf}$

下面我用 efficient-apriori 算法的官方例子1推导一下

设定如下

  • 最小支持度为 2
  • 最小置信度为 0.8

原始数据如下

transactions = [('eggs', 'bacon', 'soup'),
                ('eggs', 'bacon', 'apple'),
                ('soup', 'bacon', 'banana')]

首先构造候选 $1$-itemset，并统计支持度

[
    ("apple", 1),
    ("bacon", 3),
    ("banana", 1),
    ("eggs", 2),
    ("soup", 2),
]

显然，apple, banana 的支持度小于 2，所以不是频繁项集，所以频繁 $1$-itemset 如下

[
    ("bacon", 3),
    ("eggs", 2),
    ("soup", 2),
]

接下来用上一步得到的频繁项集构造候选 $2$-itemset

[
    (("bacon", "eggs"), 2),
    (("bacon", "soup"), 2),
    (("eggs", "soup"), 1),
]

这里的每一个候选 $2$-itemset 的子集都是频繁项集，所以只需要看每个 $2$-itemset 的支持度，显然 ("eggs", "soup") 不满足，因此得到了如下的频繁 $2$-itemset

[
    (("bacon", "eggs"), 2),
    (("bacon", "soup"), 2),
]

接下来生成候选 $3$-itemset

[
    (("bacon", "eggs", "soup"), 1),
]

注意它的大小为 2 的子集是 ("bacon", "eggs"), ("bacon", "soup"), ("eggs", "soup") 里面，("eggs", "soup") 并不是频繁 $2$-itemset，所以这个候选 $3$-itemset 肯定不是频繁项集

整理一下，我们得到了如下的频繁项集

[
    ("bacon", 3),
    ("eggs", 2),
    ("soup", 2),
    (("bacon", "eggs"), 2),
    (("bacon", "soup"), 2),
]

下面尝试构造关联规则，根据前面的算法，只需要检查最后 2 个频繁项集即可

  • 对于频繁 $2$-itemset ("bacon", "eggs")，可能的规则有
    • "bacon" -> "eggs"，置信度是 2/3 = 0.67，❌
    • "eggs" -> "bacon"，置信度是 2/2 = 1，✅
  • 对于频繁 $2$-itemset ("bacon", "soup")，可能的规则有
    • "bacon" -> "soup"，置信度是 2/3 = 0.67，❌
    • "soup" -> "bacon"，置信度是 2/2 = 1，✅
Tip

推荐使用 efficient-apriori，mlxtend 的实现太慢了

用法如下（输入必须是 list[tuple]）

from efficient_apriori import apriori
transactions = [('eggs', 'bacon', 'soup'),
                ('eggs', 'bacon', 'apple'),
                ('soup', 'bacon', 'banana')]
                
itemsets, rules = apriori(transactions, min_support=0.5, min_confidence=1)

每一条 rule 都有如下的属性

  • confidence：置信度
  • lift：提升度
  • lhs 和 rhs，返回关联规则对应侧的项集
  • count_lhs 和 count_rhs，返回的是 lhs 和 rhs 出现的频率

如果你允许如上的代码的话，你可以得到如下的频繁项集

{1: {('eggs',): 2, ('bacon',): 3, ('soup',): 2},
 2: {('bacon', 'eggs'): 2, ('bacon', 'soup'): 2}}

以及如下的关联规则

[{eggs} -> {bacon}, {soup} -> {bacon}]

可以看到，和前面手动推导的结论是一致的 :)

  1. efficient-apriori ↩︎

更新于 2025-07-30
 Machine-Learning, Data Mining
 | 主页