关联规则
- 提出者
- Agrawal, R., Imielinski, T., & Swami, A.
- 年份
- 1993
- 类型
- Unsupervised pattern discovery
- 类别
- Machine learning
本文为机器翻译,尚未经过审校。 阅读英文原文
它有什么作用?
关联规则学习是一种无监督技术,用于发现大型事务数据集中共现模式——“如果X则Y”的蕴含关系。它最初由Agrawal、Imielinski和Swami(1993)为超市购物篮分析正式提出,现已广泛应用于电子商务推荐、健康信息学、生物信息学和行为研究。
方法背后的直觉
想象一下扫描数百万张购物小票,并问:哪些产品组合倾向于一起出现?关联规则挖掘通过计算项集共现的频率(支持度)、一个项目预测另一个项目的可靠性(置信度)以及共现是否比偶然性更强(提升度)来回答这个问题。像“纸尿布→啤酒”这样具有高置信度和提升度的规则揭示了真实的のではなく偶然的,使其成为拥有无监督结果变量时的强大探索工具。
历史学
关联规则学习由Agrawal、Imielinski和Swami于1993年在ACM SIGMOD会议上正式提出,其动机是挖掘超市交易数据库的挑战。他们随后在1994年的论文中引入了Apriori算法,提供了一种高效的计算方法。该领域在20世纪90年代和21世纪初迅速发展,后来FP-growth(Han等人,2000)提供了进一步的速度改进。关联规则仍然是数据挖掘课程中的基础技术,并在零售、医疗保健和网络分析中得到常规应用。
何时使用
当您的目标是在事务数据或二元编码数据中探索性地发现共现模式时,请使用关联规则——购买篮子、临床共诊断、点击流、调查项目集或基因表达谱。该方法是无监督的,不需要结果标签,非常适合生成假设。当您有一个确定的结果变量并寻求预测它时(请使用监督分类或回归);当您的数据是连续的且未进行有意义的离散化时;当样本量很小时(稀疏项集会产生不可靠的支持度估计);或者当规则输出被误解为因果推断时——关联规则纯粹是相关性的——请不要使用它。
局限与注意事项
- 需要数据是事务性的或离散化的二元数据;连续特征需要分箱,这会引入任意选择。
- 规则数量可能非常庞大;必须进行事后过滤和按提升度或其他有趣性度量进行排序。
- 研究人员必须设置最小支持度和置信度阈值;结果对这些选择很敏感。
- 规则纯粹是相关性的——因果声明需要额外的研究设计(例如,实验或准实验)。
- 即使经过修剪,在具有非常大项集的数据集上计算成本也很高。
来源中的条件不能替代独立的科学审查或分析引擎的验证。
优势
- 完全无监督:不需要标记的结果变量,能够进行开放式模式发现。
- 可解释的输出:每条规则都是人类可读的“如果–则”语句,并量化了支持度、置信度和提升度。
- 通过修剪启发式(Apriori、FP-growth)可扩展到非常大的事务数据集。
- 适用于任何地方共现二元编码记录有意义的领域。
- 假设生成:揭示意外的共现,可以指导后续的确认性分析。
应用
- 市场篮子分析:识别经常一起购买的产品,以指导产品布局和促销。
- 电子商务推荐:生成“购买了X的客户也购买了Y”的建议。
- 临床共病发现:查找患者记录中共同出现的诊断、药物或症状集。
- 生物信息学:检测样本之间共同表达的基因或共同出现的基因变异。
- 网络使用挖掘:揭示网站上常见的点击流模式和导航序列。
- 调查和行为研究:查找跨受访者共同出现的问卷项目或行为集。
使用方式
使用方式
数据集表示为二元事务矩阵:每一行是一个事务,每一列是一个可能的项目,1表示该项目存在。这种稀疏、宽泛的表示是核心输入格式;非二元或定量项目必须在此步骤之前进行离散化。
识别出在事务数据库中频率满足用户设定的最小支持度阈值的所有项目组合(项集)。先验性原理——任何频繁项集的子集也必然频繁——极大地修剪了组合搜索空间,使得即使在大目录上进行枚举也是可行的。
公式
\text{support}(X) = \frac{|\{t \in T : X \subseteq t\}|}{|T|} \geq \text{min\_sup}对于每个频繁项集,生成所有可能的先决条件-后件拆分(X → Y,其中X和Y是不相交的非空子集)作为候选规则。候选数量可能很大,因此后续的过滤步骤至关重要。
公式
X \Rightarrow Y, \quad X \cap Y = \emptyset
评估每个候选规则的置信度:给定X存在时Y存在的条件概率。仅保留超过最小置信度阈值的规则,过滤掉仅比基本比率略好地预测后件的先决条件。
公式
\text{confidence}(X \Rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X)} \geq \text{min\_conf}保留的规则按提升度排序,即观测到的联合支持度与独立性下预期支持度的比率。提升度大于1表示真实的正面关联;提升度接近1表示项目共现的频率不超过偶然;提升度小于1表示负面关联。按提升度排序可以找出最有用和非平凡的规则。
公式
\text{lift}(X \Rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X) \cdot \text{support}(Y)}常见陷阱
- 将最小支持度设置得太低,导致输出充斥着不真实、低频且无法泛化的规则。
- 忽略提升度并报告所有高置信度规则,其中许多可能仅仅反映了高基数项目。
- 将发现的规则视为因果关系而未进一步验证(例如,混淆“啤酒和纸尿布共现”与“啤酒导致纸尿布购买”)。
- 在没有原则性离散化的情况下将关联规则应用于连续数据,产生完全依赖于任意分箱边界的规则。
- 在生成并选择性突出显示数千条规则时,忽略多重比较问题。
常见问题
如何选择最小支持度和置信度阈值?
没有普遍规则。首先探索单个项目的支持度分布,然后设置最小支持度,使其足够低以捕获感兴趣的模式,但又足够高以确保项集至少出现在有意义的绝对数量的事务中。最小置信度0.6–0.8是常见的起始范围,但领域知识和基于提升度的排序应指导最终选择。
置信度和提升度有什么区别,应该优先考虑哪个?
置信度衡量在包含X的事务中Y跟随X的频率,但它忽略了Y的基础比率。提升度通过将置信度除以Y的边际支持度来纠正这一点。具有高置信度但提升度接近1的规则,除了知道Y很常见之外,几乎没有增加信息。在过滤真正非平凡的关联时,优先考虑提升度。
关联规则可用于预测吗?
它们主要是描述性和探索性的,而非预测性的。虽然可以使用具有固定后件(单个目标项)的规则进行分类——一种称为关联分类的技术——但标准的关联规则学习不优化预测损失函数,并且在有标记结果可用时,不应取代监督模型。
我的数据集包含连续变量。我还能使用关联规则吗?
只能在离散化之后。连续变量必须在编码为二元项之前分箱为类别区间(例如,年龄组、五分位数)。分箱边界的选择会显著影响哪些规则出现,因此离散化决策应具有理论依据并透明地报告。
关联规则与相关性分析有何不同?
相关性(例如,皮尔逊r)衡量两个连续变量之间的线性关系。关联规则在事务数据中发现二元项集——任何组合大小——之间的共现模式。度量(支持度、置信度、提升度)是基于频率而非矩,输出是一组人类可读的“如果–则”规则,而不是单个数值系数。
相关方法
参考文献
Agrawal, R., Imielinski, T., & Swami, A. (1993). Mining association rules between sets of items in large databases. Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, 207–216.
打开 DOI 文献已复制。Tan, P.-N., Steinbach, M., Karpatne, A., & Kumar, V. (2018). Introduction to Data Mining (2nd ed., Ch. 5). Pearson.
ISBN:978-0-13-312890-1已复制。