全球零售巨头沃尔玛分析消费者购物行为时偶然发现男性顾客同时购买啤酒和尿布的比例较高,于是通过将啤酒和尿布捆绑销售的方式提高了两者的销量。这种用于发现隐藏在大型数据集中的有意义联系的分析方法即是关联分析association analysis
,所发现的规则可以用关联规则association rule
或频繁项集的形式表示:
许多企业在日复一日的运营中积累了大量的数据,比如商店收银台每天收集的大量顾客购物数据。有一类数据,每一行对应着一个事务,这类数据通常被称为购物篮数据market basket transactiontcd
购物篮数据可以用二元形式表示,其中每个事务中有多个项。项可以用二元变量表示,如果项在事务中出现则它的值为1,否则为0。
因为通常认为项在事务中出现比不出现更重要,所以项是非对称
asymmetric
二元变量。
典型的购物篮数据及其二元表示如下:
购物篮数据
令
是购物篮数据中所有项的集合,而
是所有事务的集合。在关联分析中,包含
个或多个项的集合被称为项集itemset
。如果一个项集包含
个项则称为
项集。 如果项集
是事务
的子集,则称事务
包含项集
。项集的一个重要性质就是它的支持度计数,即包含特定项集的事务个数。数学上,项集
的支持度计数
表示为:
关联规则association rule
指的是形如
的蕴涵表达式,其中
。衡量关联规则强度可以用它的支持度support
和置信度confidence
来表示:
在
中出现的频繁程度
支持度主要是用于删去无意义的规则(说明这些规则可能是偶然出现),置信度衡量推理出的规则的可靠性。对于给定的规则
,置信度越高,
包含在
中的可能性也就越大。置信度可以估计
在
给定情况下的条件概率。
给定事务的集合
,关联规则发现指的是找出支持度大于等于minsup
并且置信度大于等于minconf
的所有规则。
挖掘关联规则的原始做法是:计算每个可能规则的支持度和置信度。但是从数据集提取的规则的数目达指数级别(包含
个项的数据集提取的可能规则总数为
),因此这种做法的代码极高。
一种可靠的提高关联规则算法性能的方法将关联规则挖掘任务拆分为如下的两个子任务:
frequent itemset
strong rule
通常频繁相机产生所需的计算开销远大于产生规则所需的计算开销
一般包含
个项的数据集可能产生
个频繁项集(不包括空集)。当
足够大时,需要搜索的项集空间是指数规模的。下图展示了
的项集格结构lattice structure
。
频繁项集的产生
最笨的方法是挨个确定格结构中每个候选项集candidate itemset
的支持度计数,需要进行
次比较,其中
表示事务数,
表示候选项集数,
是事务的最大宽度。
有如下方法可以降低产生频繁项集的计算复杂度:
,比如下文介绍的先验apriori
原理,可以不用计算支持度值而删除某些候选项集
先验原理:如果一个项集是频繁的,则它的所有子集都是频繁的;如果一个项集是非频繁的,则它的所有超集也一定是非频繁的。
基于先验原理的剪枝
Apriori
算法的频繁项集产生令
为候选
项集的集合,而
为频繁
项集集合,先验算法可表示为:
项集的集合
项集产生新的候选
项集
minsup
的所有候选项集时算法结束
Apriori算法
Apriori
算法的计算复杂度受如下因素影响:
Hash
树的遍历次数忽略前件或者后件为空的规则(
或
),每个频繁项集可以产生多达
个关联规则。关联规则可以这样提取:将项集
划分为两个非空的子集
和
,使得
满足置信度阈值即可。
如果规则
不满足置信度阈值,则形如
的规则也一定不满足置信度阈值,其中
是
的子集。
定理:如果
不满足置信度阈值,则形如
的规则也一定不满足置信度阈值,其中
是
的子集。
Apriori
算法中规则的产生Apriori
算法采用一种逐层方法来产生关联规则,其中每层对应于规则后件中的项数。首先提取规则后件只含一个项的所有高置信度规则,使用这些规则来产生新的候选规则,如下图所示:
Apriori算法中规则产生
[1] 数据挖掘导论