关联规则学习是数据挖掘和机器学习中的一类方法,用于发现形如“当这些项出现时,那些项往往也会出现”的关系。其经典应用场景是一组交易记录,例如购物篮数据,其中每笔交易都包含所有可选项中的一个子集。例如,一条规则可能指出,含有意大利面和番茄酱的购物篮中也经常含有奶酪。这条规则描述的是观察到的关联,而非逻辑上的必然联系或因果关系。
这一领域既涉及定义严谨的搜索问题,也涉及实用性和解释方面的实际问题。算法先找出出现频率足够高的项组合,再据此生成有方向性的规则,并使用支持度、置信度和提升度等指标评估这些规则。计算上的主要难点在于,可能的项组合数量随项数的增加呈指数增长。解释上的主要难点则在于,如何将有价值的关系与偶然巧合、常见项所带来的显而易见的结果,以及数据采集过程造成的假象区分开来。
20 世纪 90 年代,对零售交易数据库的研究推动关联规则学习成为一个重要的研究领域。如今,这类方法已应用于推荐、工业监测、网络使用分析以及探索性科学分析。尽管通常被归为无监督学习,但当规则被限定为预测某个指定类别时,关联规则学习也能用于有监督分类。
数学形式化与事务表示
设 为一个有限项集, 为一个事务集合,其中每个 。事务需要用索引区分,因为两个不同的事务可能包含完全相同的项。项集是 的任意子集; 项集包含 个项。在经典的二元表示中,一个项在某个事务中要么出现,要么不出现。除非显式编码,否则不考虑其数量、购买价格以及在事务中的位置。
关联规则的形式为 ,其中 和 是非空且不相交的项集。左侧称为前件,右侧称为后件。后件包含多个项的规则表示这些项共同出现,而不是其中任意一项出现即可。例如, 涉及的是同时包含牛奶和鸡蛋的购物篮。因此,它不同于分别以这两个项为后件的任何一条单后件规则。
项集 的支持计数为
其相对支持度为
规则 的支持度通常指 。如果一个项集的支持度达到指定的最小值(通常记为 ),就称其为频繁项集。经典的规则挖掘旨在找出同时满足最小支持度和最小置信度阈值的所有规则。
这种表示方式并不限于购买行为。关系数据库中的一行可以转化为一个事务,其项为属性—值对,例如“地区=北方”或“设备=移动设备”。通过这种编码,事务挖掘算法便可处理任意类别型记录。同时,这种编码也引入了逻辑约束:同一单值属性的两个互斥取值不能同时出现在一条有效记录中。
界定事务的边界是定义问题的一部分。即使源自相同的实际活动,一个购物篮、一位顾客一个月的购买记录以及一次浏览会话,也会产生不同的关联。将较长时间跨度内的记录合并,会增加无关项共同出现的机会。将记录划分得过细,则可能丢失有意义的关系。同样,分母 决定了支持度所对应的总体。仅根据有购买行为的顾客计算出的规则,不能直接解读为适用于所有访客的结论。
支持度、置信度与关联度量
规则的置信度用于估计在前件成立的条件下,后件成立的条件概率:
只有当前件的支持度大于零时,置信度才有定义。置信度具有方向性: 和 的置信度通常不同,尽管两者的支持度相同。这种不对称性反映的是作为条件的群体不同,并不一定意味着影响具有方向性。
假设有 1,000 个购物篮,其中 200 个含有咖啡,300 个含有饼干,120 个同时含有两者。规则“咖啡 饼干”的支持度为 ,置信度为 。反向规则的置信度为 。两条规则的置信度都高于各自后件的无条件出现频率,但仅凭置信度本身无法体现这一比较。如果饼干出现在全部购物篮的 90% 中,那么一条以 60% 的置信度预测饼干出现的规则,描述的反而是负关联。
兴趣度度量从不同角度处理这一问题。提升度将实际观察到的共同出现频率与独立假设下的期望值进行比较:
咖啡与饼干这一例子的提升度为 。尽管采用了规则的表示形式,提升度仍是对称的。值为 表示这两个出现事件在经验数据中相互独立;高于或低于 的值则分别表示正关联或负关联。高提升度本身并不能证明关联可靠:极其罕见的共同出现也可能产生很大的比值。
杠杆率衡量的是相对于独立情形的绝对偏离,而非相对偏离:
在上述例子中,杠杆率为 ,相当于共同出现的次数比独立模型下的期望次数多 60 次。确信度则比较有向规则被违反的期望频率与实际观察频率:
当置信度为 ,且后件并非在所有记录中都成立时,确信度通常视为无穷大。退化情形需要单独处理。
没有任何单一度量能够同时涵盖出现频率、预测精确性、对独立性的偏离、不确定性和实际价值。常见的后件可能带来很高的置信度,却几乎不提供新信息;罕见的后件可能产生很高的提升度,却只有少量观测记录作为支撑。因此,规则评估通常会同时报告多种度量及其所依据的计数。选择不同的排序度量,改变的是所回答的问题,而不只是对某个固定不变的质量概念换一种呈现方式。
历史发展与频繁项集框架
现代关联规则挖掘由拉凯什·阿格拉瓦尔、托马什·伊梅林斯基和阿伦·斯瓦米在其 1993 年的论文《挖掘大型数据库中项集之间的关联规则》中奠定基础。他们提出的方法面向零售业务产生的交易数据,以用户指定的支持度和置信度阈值来界定发现任务。这项工作与 IBM公司的研究有关,并推动模式发现成为面向数据库的数据挖掘中的核心问题。
最初的 AIS 算法在扫描交易记录时生成候选项集。它证明了从大型数据库中提取关联关系的可行性,但其候选生成策略可能带来大量不必要的计算。1994 年,阿格拉瓦尔和拉马克里希南·斯里坎特提出了 Apriori 算法,利用支持度的数学性质,给出了一种系统的逐层搜索方法。Apriori 的剪枝规则简单、通用,且不依赖于特定的零售应用,因此成为影响深远的基准算法。
概念上的一个关键进展,是将规则发现分成两个任务。第一个任务是枚举频繁项集。第二个任务是从每个频繁项集中生成规则,并保留满足置信度阈值的规则。如果一条规则满足最小支持度要求,那么其并集 必然已经是频繁项集。因此,第一个任务为第二个任务提供了完整的搜索空间。这种分解也使频繁项集挖掘能够独立于规则发挥作用,例如寻找反复出现的组合,或为交易记录集合提供紧凑描述。
此后的研究从多个方向着手降低频繁项集枚举的成本。垂直方法用包含某个项的交易标识符集合来表示该项。模式增长方法则压缩交易记录的公共前缀,避免显式生成庞大的候选集合。韩家炜、裴健和尹义文于 2000 年提出的 FP-growth 算法,成为后一类方法的代表。关于闭项集和紧凑规则基的研究则针对另一个问题:如何在不逐一列出所有频繁组合的情况下表示规模庞大的结果。
这一领域也逐步超越了二元、无权重的交易数据。定量关联规则引入了数值区间;多层关联规则纳入了分类层次;序列模式挖掘考虑了先后顺序;面向效用的方法则将数量和经济价值纳入考量。这些扩展在改变有意义模式的判定标准的同时,也保留了原始搜索问题的部分特征。
关联规则不同于人工编写的专家系统规则。其经验上的强度根据观测数据估计;除非在观测数据中的置信度恰好为 1,否则出现例外是预料之中的事。关联规则也不同于因果规则:这一领域最初的目标是高效发现共现结构,而不是识别干预所产生的效应。
Apriori 算法与逐层候选剪枝
Apriori 算法依赖于支持度的向下封闭性。如果 ,那么每条包含 的事务也都包含 ,因此
所以,频繁项集的每个子集都是频繁的,而非频繁项集的每个超集都是非频繁的。这种反单调性使算法能够直接舍弃搜索空间中的整个分支,而无须逐一统计这些项集出现的事务数。这是支持度的性质,并非所有规则质量度量都具备的一般性质。
算法首先统计单个项的出现次数,保留其中的频繁项,通常记为 。接着,用这些频繁项构造候选二项集,统计其出现次数,并保留频繁二项集,记为 。在一般步骤中,通过连接频繁 项集来生成候选 项集。如果某个候选项集的任意一个 项子集不在 中,就将该候选项集舍弃。随后扫描数据库,统计剩余候选项集的出现次数;当无法再找到频繁项集时,算法结束。
假设 和 都是频繁项集。将两者取并集,可得到候选项集 。但如果 不是频繁项集,那么在统计支持度之前,就会排除该候选项集,因为它不可能达到阈值。高效的实现会按照固定顺序排列各项,以便有条理地执行连接并避免重复。可以使用哈希表、前缀树或其他索引结构来组织候选项集,从而加快查找每条事务所包含的候选项集。
规则生成采用一种相关但不同的剪枝原则。对于固定的频繁项集 ,每个非空真子集 都可以作为后件,生成规则 。该规则的置信度为 。随着 增大,前件缩小,其支持度不会降低,因此置信度不会增加。所以,如果某个后件对应的规则未达到置信度阈值,那么在针对同一个并集 生成规则时,就可以剪去该后件的所有超集。
当事务相对较短,且最小支持度足够高、能在早期排除大部分组合时,Apriori 算法尤其有效。当大量项都是频繁项,或存在较长的频繁模式时,算法就会遇到困难。候选项集的数量可能极其庞大,而且每一层都可能需要再次扫描数据库。对于包含 个项的频繁项集,可能的非空有向划分共有 种。因此,即使能够高效地枚举项集,也仍然无法消除规则输出数量过于庞大的风险。
模式增长与垂直挖掘
FP-growth 将事务压缩为 FP 树(频繁模式树),从而避免了 Apriori 显式地逐层生成候选项集的过程。首先扫描数据库,确定各项的支持度,并剔除支持度低于最小阈值的项。随后,将每个事务中剩余的项按统一顺序排列,通常按支持度降序排列,再插入树中。排序后具有相同前缀的事务共享树节点;节点计数记录沿各个前缀经过的事务数量。一个头表结构将包含同一项的节点链接起来。
挖掘过程以某一项为条件展开。通向该项各节点的路径构成条件模式基,并可据此构建规模更小的条件 FP 树。递归挖掘这些条件结构,就能枚举出包含所选项的频繁模式。如果某棵条件树只有一条路径,就可以直接根据这条路径及其计数生成频繁组合。原始构建过程通常需要完整扫描数据库两次,不过后续的条件挖掘仍然需要大量计算和内存访问。
压缩程度取决于数据本身。如果事务排序后共享许多前缀,FP 树可能远小于原始事务列表。如果重叠较少,树的规模可能仍然很大。因此,避免生成候选项集并不意味着能够避免组合爆炸:算法仍须枚举它承诺返回的所有模式。紧凑的输入结构也可能对应规模呈指数级增长的输出。
Eclat 采用另一种表示方式。它不再以各事务所包含的项来存储事务,而是将每个项集与一个事务标识符集合(简称 tidset)一起存储。对于项集 和 ,
支持度计数由此转化为集合求交。Eclat 通常使用深度优先搜索探索项集,用可兼容的项扩展前缀,并对相应的事务标识符集合求交。有序标识符列表、位向量和压缩位图在时间与内存之间提供了不同的权衡。差集(diffset)变体存储相关事务集合之间的差异;当扩展操作排除的事务相对较少时,这种表示可以很紧凑。
这些方法体现了一条更普遍的原则:数据表示方式可能与抽象的搜索策略同样重要。横向事务扫描利用一种访问模式,前缀树利用共享结构,而垂直方法则利用快速集合运算。数据集密度、事务长度、内存容量和支持度阈值都会影响性能。不存在一种普适的排名,能让某种方法在所有数据集上都占据优势;比较时还必须考虑各实现是否生成了相同且完整的模式集合。
闭模式、极大模式与紧凑规则基
频繁项集的集合可能包含大量冗余。如果一个包含十个项的集合是频繁的,那么它的所有子集也都是频繁的,无论这些子集是否提供了独立的信息。紧凑的模式表示旨在保留有用信息,而不必显式存储每一个频繁项集。两种主要的表示方式是闭项集和极大频繁项集,二者保留的信息量不同。
对于支持度为正的项集 ,其闭包是所有包含该项集的事务的交集:
闭包会纳入在所观测数据库中始终与 一同出现的所有项。当 时,项集就是闭的;等价地说,不存在与它具有相同支持度的真超集。如果每个包含咖啡的购物篮也都包含滤纸,那么“咖啡”和“咖啡与滤纸”的支持度相同;只含咖啡的项集不是闭的,必须将滤纸也纳入其中。
所有频繁闭项集及其支持度构成的完整集合,保留了每个频繁项集的支持度。对于频繁项集 ,其支持度等于 的所有频繁闭超集中的最大支持度;它自身的闭包就具有这一支持度。因此,闭模式是频繁项集支持度信息的一种无损压缩表示,不过,查询任意项集的支持度可能需要额外的索引或计算。
相比之下,极大频繁项集不存在频繁的真超集。每个极大频繁项集都是闭的,但频繁闭项集不一定是极大的。极大模式刻画了频繁区域的边界:一个项集是频繁的,当且仅当它是至少一个极大频繁项集的子集。然而,极大频繁项集的支持度并不能确定其所有子集的支持度。因此,仅凭极大模式通常不足以计算任意规则的置信度。
紧凑规则基又引入了另一种区分。闭项集的极小生成元,是指闭包为该闭项集、且不存在具有相同闭包的更小子集的子集。如果 生成 ,那么规则 在所观测数据库中的置信度为一。基于闭包的方法可以利用这种关系表示精确蕴含,并组织近似规则。置信度为一仍然只是一种经验性质,并不保证未来的记录也会遵循这一蕴含关系。
其他冗余判据则考察:向前件添加项是否能实质性地提高置信度,或者某条规则是否仅仅是从更一般的关系中继承而来。消除冗余并不等同于只保留得分最高的规则。紧凑的结果也可以着重保留覆盖范围、支持度信息、逻辑结构,或按指定要求重建被省略规则的能力。
超越普通共现关系的扩展
经典关联规则将项视为二元变量,并将事务视为无序集合。许多应用需要更丰富的描述。定量关联规则包含数值条件,例如“年龄在 30 至 39 岁之间”或“购买金额超过某个阈值”。数值属性可以在挖掘前离散化为区间,也可以直接搜索区间。区间边界的选择既影响支持度,也影响规则表现出的强度:较窄的区间可能筛出强度高但支持度低的关系,而较宽的区间可能掩盖有意义的差异。
多层关联规则利用项的分类层级。一条包含某品牌茶叶的事务,也可以被视为包含茶叶、饮料和食品杂货。高层类别的支持度通常高于具体产品,因此在整个层级中采用统一的支持度阈值往往并不合适。挖掘时可以针对不同层级设置不同阈值,也可以限制哪些抽象层级能够同时出现。分类层级还会产生平凡规则,例如由某种产品推出其所属类别;这些规则需要与真正具有信息价值的关联区别处理。
序列模式挖掘保留事件之间的顺序,而不只是记录集合中包含哪些项。“顾客购买打印机,之后购买墨水”与“打印机和墨水出现在同一个购物篮中”并不相同。序列方法基于序列定义支持度,并可对时间间隔、事件窗口或序列长度施加约束。一旦事务数据丢弃了时间顺序,普通关联规则就无法将其恢复。仅凭规则的方向性表示,并不能推断前件发生得更早。
高效用项集挖掘将数量以及单位利润等各项特有的数值纳入考虑。这样,低频组合也可能因其总效用而具有重要性。与支持度不同,一般的正值事务效用在项集扩展时通常不具有反单调性:添加一个项可能使效用增加。因此,算法会使用适当的上界,例如在适用假设下的事务加权效用,以确保安全剪枝。仅在 Apriori 算法中用利润替换支持度,并不能保持算法的正确性。
负关联规则描述缺失关系,例如 。其含义取决于某项的缺失是否确实经过观察,而非仅仅未被记录。例如,缺少某个诊断编码,并不一定能证明相应病症不存在。由于大多数事务都不包含绝大多数可能的项,负模式的数量也可能急剧膨胀。
类关联规则将后件限定为类别标签。在关联分类中,这类规则经过筛选和组织,构成预测模型,因此这项任务属于监督学习。这需要相应的处理流程来解决规则冲突,并评估模型对未见案例的预测表现。更一般地说,基于约束的挖掘可以限制前件长度、允许使用的项、分类层级组合或后件属性,使输出更贴合明确的分析问题。
应用与实际业务中的解读
购物篮分析仍是最典型的应用。规则可以描述经常被一同购买的商品,为研究商品组合、促销或交叉销售提供参考。规则在实际业务中的含义取决于背后的过程:以同一个包装标识销售的捆绑商品、必须配套购买的附件,或临时折扣,都可能出于不同原因形成很强的共现关系。交易记录能够说明在既有条件下哪些商品被一同购买,但仅凭这些记录,无法确定改变陈列方式或价格会如何影响购买行为。
在推荐系统中,用户已选择的项可以与规则前件匹配,而后件则提供候选推荐项。规则具有可解释性,而且无需显式用户画像也能发挥作用。然而,关联强度并不等同于推荐相关性。某个项可能已被购买、无法供应,或不适合重复推荐。实用系统必须将规则评分与推荐资格约束、库存信息,以及排序质量或转化率等评估目标结合起来。
网站与应用使用分析将页面访问、操作或会话属性视为项。一条关联可能将某项功能的使用与某个工作流程的完成联系起来。会话的划分至关重要,因为自动化流量、共享账号以及因不活跃而结束会话的时间阈值,都可能改变哪些事件被归入同一组。当顺序很重要时,例如需要区分放弃操作之前发生的错误与执行另一项任务之后遇到的错误,基于序列的分析比普通的共现挖掘更合适。
在制造与维护领域,事务可以表示检查记录、设备配置或传感器状态的时间窗口。规则可能揭示与缺陷相关的设置组合,或反复一同出现的告警组。这类发现有助于调查,但告警往往具有共同的根本原因,或反映了故障在同一系统中的传播。在网络安全领域,类似方法可以识别反复出现的事件组合,或帮助刻画异常偏离;结果的可靠性在很大程度上取决于事件规范化处理和背景活动。
科学数据集也可以用事务形式表示。分子测量数据可以转换为类别状态,也可以在观测记录中搜索反复出现的组合。在这类应用中,离散化、批次效应和比较次数成为需要重点关注的问题。发现的规则只是一种候选的描述性关系,而不是经过独立验证的机制。
在上述各类应用中,实际价值并不由基本的支持度—置信度问题本身决定。一条规则可能在统计上很强,却早已显而易见、无法据此采取行动,或不具备经济价值。反过来,一种出现频率不算高的关系,如果揭示了代价高昂的失效模式,也可能十分重要。因此,评估时需要区分计算上的有效性、实证上的可复现性、对该领域而言的新颖性,以及在实际运行系统中使用规则所带来的后果。
统计验证与解释的局限
关联挖掘是在众多可能的关系中进行的自适应搜索。即使各项在生成数据的总体中彼此独立,某些组合在有限样本中仍可能呈现出很强的关联。考察数百万个候选关系,却只报告其中最显著的关系,会造成多重比较问题。最小支持度可以限制搜索范围,排除出现次数极少的组合,但仅凭支持度或置信度阈值,都无法在统计上保证避免假发现。
对于一对固定的发生事件,可以用一个 列联表表示二者的关系:两者均发生、仅前件发生、仅后件发生,或两者均不发生。统计检验可以评估它们偏离独立性模型的程度。然而,抽样假设是否成立至关重要。同一客户的重复交易、相互重叠的传感器时间窗口,或同一站点内彼此相关的观测,都不能视为独立抽样。此外,交易数量极大时,即便偏离程度很小、在实际业务中无关紧要,也可能达到统计显著性。
多重检验方法可以控制一组假设的特定错误率。在模式挖掘中使用这些方法时需要谨慎,因为假设集合可能极其庞大,而且搜索本身依赖于观测到的支持度。利用可检验性界限、重采样或精心界定的候选集合的方法,可以减轻检验负担。在不受限制的搜索之后计算出的显著性数值,不应被解读为该规则是在独立于数据的情况下选定的。
独立验证解决的是另一个与之互补的问题。可以在训练数据中发现规则,使用验证集筛选规则,最后在预留的测试集上评估规则。这样可以减少对偶然组合的过拟合。对于涉及时间的应用,采用较早时段发现规则、较晚时段评估规则的方式,往往比随机划分更能反映实际部署情况。还可能需要按客户或设备划分数据,以防止同一实体反复出现而造成数据泄漏(机器学习)。
关联也不能确立因果关系。促销可能促使两种商品被一起购买;季节性因素可能使两者的购买量同时增加;而样本被选入数据集的过程,也可能产生在更广泛总体中并不存在的关联。条件关系可能因子群体而异,也可能在汇总后发生反转,这种现象与辛普森悖论有关。以更多属性为条件进行分析可以揭示结构,但也会减少样本量并扩大搜索空间。
最后,规则表面上的稳定性可能在分布偏移下消失。商品目录、用户行为、日志记录系统和机构的运作方式都会发生变化。因此,要确保结果可复现,就需要明确说明总体、观测时段、交易定义、预处理、阈值和评估流程,而不只是报告一条规则及其置信度。
可扩展性、数据治理与可复现的实现
搜索空间构成了一项根本限制。对于 个项,共有 个非空项集。即使是理想的实现,也无法在少于输出所需的时间内显式返回规模呈指数增长的结果。这使关联挖掘与计算复杂性联系起来,也使输出控制成为设计中必须优先考虑的问题。最小支持度、最大模式长度、受限的规则后件、闭合表示以及 top- 目标,分别应对这一问题的不同形式。对于不受限制的挖掘任务,最大长度限制会使结果不完整,但对于定义明确的特定任务,这种限制可能是恰当的。
大规模实现利用分区和分布式计算来分担计数与搜索工作。在一种简单的分布式计数方案中,各工作节点在本地分区内对候选项集计数,再在全局汇总计数。任何达到全局相对支持度阈值的项集,都必然在至少一个分区中达到同一相对阈值,这为基于分区发现候选项集提供了依据。不过,各分区局部候选项集的并集仍可能很大,而且全局验证依然需要付出数据访问或通信成本。
模式增长方法可以按后缀或前缀划分工作,但各任务的规模可能极不均衡。一个十分常见的项所产生的条件子问题,可能远大于一个罕见项所产生的条件子问题。因此,基于 MapReduce编程模型 或 Apache Spark 构建的系统,不仅要处理算术运算,还必须管理通信、数据复制、内存使用和数据倾斜。对集合求交进行硬件加速有助于垂直方法,但即使计数更快,也无法消除枚举海量输出的成本。
数据质量同样重要。重复导入会抬高支持度;项标识符不一致会将同一概念拆分为多个项;商品目录的变化会造成虚假的缺失;遗漏事务则会改变分母。在事务挖掘中,“事务”指一条分析记录,不一定与数据库并发控制和恢复语境中的数据库事务相对应。可复现的实现会保留这一区别,并记录源记录如何转化为用于分析的购物篮。
即使没有直接标识符,关联结果仍可能泄露敏感信息。罕见的项组合可能对应人数很少的群体,而规则可能揭示涉及敏感属性的关系。因此,数据隐私既涉及输入数据的访问,也涉及对外发布的模式。差分隐私提供了一个形式化框架,用于限制输出对单个受保护单元的依赖程度。保护隐私的频繁模式挖掘必须妥善处理带噪计数、候选选择以及搜索空间规模。受保护单元是一条事务,还是某个个体的全部历史记录,会实质性地改变隐私保障。
为确保可复现性,实现中应记录绝对阈值和相对阈值、项映射、缺失值处理方式、事务边界、软件版本以及规则筛选标准。在报告衍生度量的同时给出支持计数,可以让舍入方式和分母选择清晰可见。当记录随时间演变时,数据血缘能够将报告中的关联与产生该关联的源数据及其转换过程联系起来。