Skip to content
返回搜索结果

Apriori算法

提出者
Agrawal, R. & Srikant, R.
年份
1994
类型
Frequent itemset and association rule mining algorithm
类别
Machine learning

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

字号

它有什么作用?

Apriori算法由Agrawal和Srikant于1994年提出,是发现事务数据库中频繁项集和关联规则的基础方法。它采用广度优先、逐层搜索策略,并利用支持度的反单调性(anti-monotone property)高效枚举所有共同出现频率高于用户设定最小阈值的项组合,然后从这些模式中提取可解释的“if-then”规则。

方法背后的直觉

以超市购物小票数据库为例。Apriori算法的核心洞见是反单调性:如果一对产品很少一起购买,那么任何包含这对产品的更大项集也不可能是频繁的。这使得算法能够通过逐层构建候选集(从单个项开始,然后是成对项,再是三元组)来修剪呈指数级增长的可能项组合搜索空间。在对数据进行计数之前,算法会丢弃任何已知其子集不频繁的候选集。

历史学

Rakesh Agrawal和Ramakrishnan Srikant于1994年在VLDB会议上介绍了Apriori算法,该算法建立在Agrawal等人1993年提出的关联规则挖掘问题公式之上。其名称反映了其关键洞见:利用频繁(k)项集的先验知识来剪枝k+1级的候选集。它成为衡量所有后续频繁项集算法(包括FP-Growth (2000)和Eclat)的规范基准,并且仍然是数据挖掘和机器学习教科书中的标准章节。

何时使用

当目标是发现事务性或二元项存在数据中的共现模式或“if-then”关系时,例如市场篮子分析、调查项共同认可、医学诊断共现或文本术语关联,请使用Apriori算法。它适用于中等规模的数据集,其中输出规则的透明度和可解释性是优先考虑的。当事务数据库非常大(数百万行且项目录广泛)时,请勿使用Apriori算法,因为其重复的完整数据库扫描使其与FP-Growth相比速度较慢;在这种情况下,FP-Growth是首选。它也不适用于未经离散化的连续数值数据,并且不模拟方向性或因果关系。

局限与注意事项

  • 重复的完整数据库扫描使其在大型数据集上速度较慢——在规模化应用中通常首选FP-Growth。
  • 降低支持度阈值可能会产生指数级数量的候选项集和规则,从而使解释变得困难。
  • 不捕捉项之间的时间顺序、方向性或因果关系。
  • 结果对支持度和置信度阈值的选择敏感,这需要领域知识或系统性调整。

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

优势

  • 生成完全可解释的“if-then”规则,并量化支持度、置信度和提升度。
  • 反单调剪枝特性使得原本呈指数级增长的搜索变得可行。
  • 无需对数据进行预先标记;它完全是无监督的。
  • 阈值参数(支持度、置信度)使分析师能够直接控制规则的粒度。
  • 输出规则具有可操作性,并且可以传达给没有算法背景的非技术利益相关者。
  • 开创性的、被大量引用,并且几乎在每个主要数据挖掘库中都有实现。

应用

  • 市场篮子分析:发现哪些产品经常一起购买,以指导货架布局和促销活动。
  • 医学信息学:识别患者记录中共同出现的症状、诊断或药物处方。
  • 网络使用挖掘:发现用户倾向于一起访问或激活哪些页面或功能。
  • 调查和问卷分析:检测哪些项或量表响应系统性地共同被认可。
  • 推荐系统引导:在部署协同过滤之前生成候选项关联。
  • 欺诈检测:揭示交易日志中偏离正常购物篮的异常共现模式。

使用方式

使用方式

1

分析师在运行算法前需要选择两个阈值:最小支持度(min_support,即项集必须在多少比例的事务中出现才被认为是频繁的)和最小置信度(min_confidence,即“if-then”规则被保留所需的条件概率)。这两个值控制着输出规则的数量和特异性,应通过领域知识或探索性运行进行校准。

2

算法对事务数据库进行一次完整扫描,以统计每个独立项的出现频率。只有支持度达到或超过最小支持度阈值的项才被保留;其余的则被丢弃。这些频繁的单个项构成了第一级候选集。

公式
\text{support}(X) = \frac{|\{t \in T : X \subseteq t\}|}{|T|}
3

在第k级发现的频繁项集两两连接,形成大小为k+1的候选项集。只有共享相同前k-1个项的对才被连接,这一规则保持了候选集的紧凑性。然后,对数据库进行一次新的扫描,计算每个候选集的支持度。

4

在计数之前,每个大小为k+1的候选集都会对照其所有(k)个子集进行检查。如果任何子集在前一级别不频繁,则该候选集会立即被剪枝,无需读取数据,从而利用反单调性减少计算量。经过此剪枝步骤幸存下来的项集构成了下一级频繁项集。

5

从每个大小为两个或更多的频繁项集中,通过将项划分为前件(antecedent)和后件(consequent),生成所有可能的“if-then”规则。每条规则都根据置信度进行评估——即包含前件的事务中也包含后件的比例。低于最小置信度的规则将被丢弃。

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

幸存的规则按提升度(lift)进行排名,提升度将观察到的置信度与后件的基线频率进行比较。提升度大于1表明前件和后件的共同出现并非偶然;提升度接近1表示独立性;提升度小于1表示负相关。提升度最高的规则是最具可操作性的发现。

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

常见陷阱

  • 将最小支持度设置得过低,导致数千条低质量规则泛滥,而未通过提升度进行过滤。
  • 将高置信度解释为因果关系而非共现——一条高置信度但提升度接近1的规则是微不足道的。
  • 在未事先离散化的情况下将Apriori应用于连续特征,这会膨胀项空间并降低结果质量。
  • 在未检查项集样本量是否足够大以信任支持度估计的情况下报告规则。
  • 忽略移除无信息规则(例如,涉及普遍购买项的规则,如商店会员卡)。

常见问题

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

支持度是包含该项集的所有事务的比例——它衡量的是普遍性。置信度是给定前件出现时后件出现的条件概率——它衡量规则的可靠性。提升度是观察到的置信度与后件基线频率的比率;提升度大于1表明存在真正的正向关联,而非由项的流行度驱动的巧合。

我应该何时选择FP-Growth而不是Apriori?

FP-Growth将数据库压缩成树形结构,并在不重复完整扫描的情况下进行挖掘,这使得它在大型数据集或最小支持度较低时速度显著加快。Apriori更容易理解和实现,并且在运行时不是瓶颈的中小型数据集上表现良好。

我如何选择最小支持度和置信度?

没有普遍适用的规则。常见的做法是在几个支持度级别运行算法,绘制频繁项集数量与支持度的关系图,并在曲线的“拐点”处选择一个值。然后根据业务或研究问题设置置信度——对于关键任务规则设置更高的置信度,对于探索性发现设置较低的置信度。始终根据领域专业知识验证最重要的规则。

Apriori能否处理数值或连续数据?

Apriori需要二元项存在数据。连续变量必须先离散化为区间(例如,年龄分为低/中/高),然后编码为项。不良的离散化会严重扭曲发现的规则,因此分箱策略值得仔细考虑。

Apriori是否暗示项之间的因果关系?

不。关联规则捕捉的是共现,而不是因果关系或方向性。规则“面包 → 黄油”意味着它们经常出现在同一个购物篮中;这并不意味着购买面包会导致某人购买黄油,也不意味着这种关系在任何因果意义上都是不对称的。

相关方法

参考文献

  1. Agrawal, R. & Srikant, R. (1994). Fast algorithms for mining association rules. Proceedings of the 20th International Conference on Very Large Data Bases (VLDB), 487–499.

    打开出版物文献
    已复制。
  2. Apriori algorithm. Wikipedia.

    打开出版物文献
    已复制。