Apriori算法

2018/08/30 Machine Learning

这个算法有点慢,但是人家是数据挖掘十大算法之一,很多关联规则挖掘的方法都是其衍生方法,所以需要理解一下。Apriori并不是一个机器学习算法,即没有训练出模型,它是一个统计学的数据挖掘方法。

先验算法(Apriori)采用广度优先搜索算法进行搜索并采用树结构来对候选项目集进行高效计数。它通过长度为k-1的候选项目集来产生长度为k的候选项目集,然后从中删除包含不常见子模式的候选项。根据向下封闭性引理,该候选项目集包含所有长度为k的频繁项目集。之后,就可以通过扫描交易数据库来决定候选项目集中的频繁项目集。

问题描述

还是举经典的尿布与啤酒的例子。超市的收银台每天有大量的购物记录,每条记录是一人次购买的物品清单,我们想根据这些历史数据来挖掘出某些物品之间的关联关系,例如买尿布的人大概率还会买啤酒,这种分析对超市的销售策略制定十分有帮助。

令$I={i_1,i_2,⋯,i_d}$是购物篮数据中所有项的集合,而$T={t_1,t_2,⋯,t_N}$是所有交易的集合。包含0个或多个项的集合被称为项集(itemset)。如果一个项集包含k个项,则称它为k-项集。显然,每个交易$t_i$包含的项集都是$I$的子集。

关联规则是形如$X\rightarrow Y$的蕴涵表达式,其中X和Y是不相交的项集,即$X\cap Y=\emptyset$。例如${Milk,Diaper}\rightarrow{Beer}$。关联规则的强度可以用它的支持度(support)和置信度(confidence)来度量。支持度确定规则可以用于给定数据集的频繁程度,而置信度确定Y在包含X的交易中出现的频繁程度。支持度(s:Fraction of transactions that contain both X and Y)和置信度(c:How often items in Y appear in transactions that contain X)这两种度量的形式定义如下:

支持度类似于概率$P(X,Y)$的定义,置信度类似于条件概率$P(Y\vert X)$的定义。

基于这两个定义,一般关联规则挖掘算法可以分成两个子任务:

  1. 寻找频繁项集:发现满足最小支持度阈值(minsup)的所有项集,这些项集被称为频繁项集(frequent itemset)。
  2. 寻找关联规则:从频繁项集中提取满足最小置信度阈值(minconf)的规则,这些规则成为强规则(strong rule)。

所以Apriori要解决的问题就是,给定由项集组成的交易集$T$和阈值$minsup$和$minconf$,挖掘出所有满足条件的强规则。

先验原理

要发现频繁项集,Brute-force的方法是每个项集都检查一遍,这需要遍历$2^N$次数据集,显然是不现实的。

Apriori之所以叫先验算法,是因为它在Brute-force的基础上根据先验知识进行了剪枝,避免了不必要的计算。

  • 先验知识1:如果一个集合是频繁项集,则它的所有子集都是频繁项集。
  • 先验知识2:如果一个集合不是频繁项集,则它的所有超集都不是频繁项集。

通过这两个知识可以对频繁项集的搜索进行剪枝。

算法

下面是一个具体的例子下面是一个具体的例子,最开始数据库里有4条交易,{A、C、D},{B、C、E},{A、B、C、E},{B、E},使用min_support=2作为支持度阈值,最后我们筛选出来的频繁集为{B、C、E}。

上述例子中,最值得关注的就是$L_2$到$C_3$的过程,即从$L_k$生成$C_{k+1}$的过程。C表示Candidate。它使用的策略为:

  1. 对于两个前k-1个项相同的项集,与它们两个的第k个项组合成一个k+1项集
  2. 找出所有满足上述条件的k+1项集,组成新的$C_{k+1}$
  3. 对于一个位于$C_{k+1}$中的项集c,s是c的大小为k的子集,如果s不存在于$L_k$中,则将c从$C_{k+1}$中删除(即查找$L_k$中是否包含所有c中任意去掉一项组成的项集)
  4. 删除所有满足上述条件的项集,即得到最后的$C_{k+1}$

如何扫描数据库计算支持度也是这个算法可以优化的部分,这里不详细说明。

关于发现规则的部分,对于每个频繁项集,先从右边为一个项开始,用之前算过的每个频繁项集及其子集的支持度来计算置信度,考虑先验知识以同样的方法筛选候选集得到$C_{k+1}$,过程中记录所有满足最小置信度的关联规则即可,详细过程略。

总结

Apriori是关联规则挖掘的核心算法,但因为此算法要多次扫描数据库,实际执行效果会很慢,也因此产生了基于分治法的新算法FP-growth。

如果超市的记录加入了时间因素,即每个人不同时间的交易作为一个带有时序关系的项集,则是序列模式挖掘的研究领域。例如,小乐的购买记录为{<书,薯片>,<电视>,<游戏,专辑>},每个小项集是有先后顺序的。据此可以挖掘出带有时序性的关联关系,例如<电视>$\rightarrow$<游戏>。

序列模式挖掘的算法有:

  • 基于Apriori的方法:AprioriAll, AprioriSome, GSP, SPADE等
  • 基于分制思想的方法:FreeSpan, PrefixSpan等、

Search

    Table of Contents