Skip to content
返回搜索结果

关联规则挖掘(Apriori)

提出者
Rakesh Agrawal & Ramakrishnan Srikant
年份
1994
类型
Unsupervised pattern discovery algorithm
类别
Pattern mining

本文为机器翻译,尚未经过审校。 阅读英文原文

字号

它有什么作用?

关联规则挖掘是一种无监督数据挖掘技术,用于发现交易型数据集中项之间的共现模式。它由Agrawal、Imieliński和Swami于1993年正式提出,并由Agrawal和Srikant于1994年通过里程碑式的Apriori算法进行改进,识别形式为X ⇒ Y的规则——表示包含项集X的交易也倾向于包含项集Y——通过支持度、置信度和提升度进行量化。

方法背后的直觉

想象一下超市的收据日志:如果成千上万的顾客在购买面包和黄油的同时也购买牛奶,那么这种模式就值得关注。关联规则挖掘就像一位一丝不苟的图书管理员,仔细梳理每一张收据,计算项组合出现的频率,并找出超出最小频率的组合。一旦找到频繁项集,算法就会问:鉴于你已经拥有这些物品,这能在多大程度上预测下一件物品?这种先计数后评估置信度的两阶段逻辑是Apriori的核心。

历史学

Agrawal、Imieliński和Swami(1993)的奠基性论文在超市交易数据的背景下定义了关联规则问题。Agrawal和Srikant于1994年在VLDB上发表的论文介绍了Apriori算法及其高效的剪枝策略,使得大规模挖掘成为可能。后续工作产生了FP-Growth(Han等,2000),它完全避免了候选生成,以及ECLAT,它以垂直数据格式进行挖掘——建立了一个现已成为数据挖掘课程核心的丰富算法家族。

何时使用

关联规则挖掘适用于大型交易型数据集,其目标是在没有预定义目标变量的情况下发现共现模式。它假设项在每次交易中是二元的(存在/不存在)。它适用于购物篮分析、推荐系统、网页点击流分析和医学共诊断发现。它不适用于连续或有序数据(除非预先离散化),不适用于维度非常高的数据集(候选空间呈指数级增长),或者当需要因果推断而非关联推断时。替代方法包括用于更快频繁项集枚举的FP-Growth,以及在考虑时间顺序时使用的序列挖掘。

局限与注意事项

  • 指数级候选空间:规则数量随不同项的数量呈组合式增长。
  • 支持度-置信度框架在项的基数变化很大时可能产生误导性规则(需要提升度调整)。
  • 二元交易模型需要对连续变量进行离散化,引入信息损失。
  • 过高的最小支持度阈值会错过稀有但有价值的规则;过低的阈值会生成数千条琐碎的规则。

来源中的条件不能替代独立的科学审查或分析引擎的验证。

优势

  • 完全无监督:无需标记数据或预定义目标。
  • 可解释的输出:规则是人类可读的“如果-那么”语句,并量化了支持度和置信度。
  • 可通过Apriori剪枝进行扩展;FP-Growth变体完全消除了重复的数据库扫描。
  • 领域无关:应用于零售、医疗保健、网络分析和生物信息学。

应用

  • 零售:从销售点交易日志中进行产品布局和交叉销售推荐。
  • 医疗保健:电子健康记录中诊断、手术或药物的共现分析。
  • 网络分析:发现点击流模式以进行页面推荐和导航优化。
  • 生物信息学:识别共表达基因集和蛋白质相互作用基序。
  • 网络安全:检测指示入侵模式的相关网络事件。

使用方式

使用方式

1

该算法扫描交易数据库D,计算每个项集X出现的频率。只有当项集的支撑度(包含该项集的交易所占的比例)达到或超过用户定义的最小支撑度阈值σ_min时,该项集才被声明为频繁项集,并放入L_k。该过程从单个项(k=1)开始,并迭代地构建更大的候选集。

公式
L_k = \{ X \subseteq I \mid |X| = k,\; \text{support}(X) = \frac{|\{t \in D : X \subseteq t\}|}{|D|} \geq \sigma_{\min} \}
2

支撑度的反单调性性质表明,任何频繁项集的子集本身也必须是频繁的。Apriori利用这一点,通过修剪所有其(k-1)子集均不在已验证的频繁集L_{k-1}中的候选k项集来达到目的。这极大地减少了搜索空间,避免了对不可能成为频繁项集的项集进行昂贵的数据库扫描。

公式
\forall X \in C_k,\; \forall Y \subset X,\; |Y| = k-1 : Y \notin L_{k-1} \Rightarrow X \notin L_k
3

从每个频繁项集X ∪ Y中,算法生成规则X ⇒ Y,其中X和Y是互斥的子集。只有当规则的置信度——给定X时出现Y的条件概率,计算为support(X ∪ Y) / support(X)——达到或超过最小置信度阈值γ_min时,该规则才被保留。此步骤将原始的共现转换为有方向的预测语句。

公式
X \Rightarrow Y \text{ where } X \cap Y = \emptyset,\quad \text{confidence}(X \Rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X)} \geq \gamma_{\min}
4

保留的规则通过提升度进行排序和过滤,提升度衡量Y与X一起出现的可能性是否高于偶然发生的可能性。提升度 > 1 表示正相关超出独立性;提升度 = 1 表示独立性;提升度 < 1 表示负相关。诸如信念度和杠杆率等额外的有趣度度量可以进一步优化规则集以供实际部署。

公式
\text{lift}(X \Rightarrow Y) = \frac{\text{confidence}(X \Rightarrow Y)}{\text{support}(Y)} = \frac{\text{support}(X \cup Y)}{\text{support}(X) \cdot \text{support}(Y)}

常见陷阱

  • 设置过低的最小支持度会使分析师淹没在虚假规则中;阈值选择需要领域知识或交叉验证。
  • 混淆统计关联与因果关系:高提升度并不意味着X导致Y。
  • 忽略项频率分布:常见项主导规则并挤占有意义的稀有项关联。
  • 将置信度单独作为质量指标;具有高置信度但低提升度的规则可能表现不比随机猜测好。

常见问题

支持度、置信度和提升度之间有什么区别?

支持度衡量项集在整个数据集中出现的频率。置信度衡量前提项集出现时,结论项集出现的条件概率。提升度通过结论项集的边际频率对置信度进行归一化,揭示共现是否超出独立性预期。所有这三个度量都需要结合起来进行稳健的规则评估。

Apriori算法如何降低计算成本?

Apriori利用反单调性:如果一个项集不频繁,那么它的所有超集也必定不频繁。通过丢弃所有其子集均未经验证为频繁的候选集,该算法在计数之前就剪枝了搜索空间的大部分,与暴力枚举相比,大大减少了所需的数据库扫描次数。

何时应使用FP-Growth而非Apriori?

当数据集很大且最小支持度阈值较低时,首选FP-Growth,因为它将交易数据库压缩成紧凑的FP树结构,并直接在树上挖掘模式,而无需生成显式候选集。这消除了重复的完整数据库扫描,使其在具有许多频繁项集的密集数据集上比Apriori快得多。

相关方法

参考文献

  1. Agrawal, R., Imieliński, T., & Swami, A. (1993). Mining association rules between sets of items in large databases. ACM SIGMOD, 207–216.

    打开 DOI 文献
    已复制。
  2. Agrawal, R., & Srikant, R. (1994). Fast algorithms for mining association rules. Proceedings of the 20th VLDB Conference, 487–499.

    打开出版物文献
    已复制。