二、Apriori 算法

(一)相关概念 关联规则最常用的是 Apriori 算法,同时也是发现频繁项集的一种方法。所谓频繁项集,是指由独立事件组成的项目交集频繁发生且达到预期值的集合,其严谨的表述方法还需要如下几个概念的引入: 支持度:几个关联的项目组成的项集在总事项中出现的次数占总事项数量的比例。 以表 2-5-1 为例,设有规则{牛奶,尿布}→{啤酒},项集{牛奶,尿布,啤酒}在第 2、3事项中出现过,出现次数为 2,而总事项数为 5,则该规则的支持度为 。 置信度:一个项集出现后,另一个项集出现的概率,或者说前件与后件的条件概率。 仍以规则{牛奶,尿布}→{啤酒}为例,其置信度是指在{牛奶,尿布}出现的情况下,{啤酒}出现的概率,遍历整个事项集,{牛奶,尿布}这一项集共出现 3 次,分别在 3、4、5 事项,但既有{牛奶,尿布},又有{啤酒}的事项只有 2 次,分别在 3、4 事项,所以该规则的支持度为。 提升度:项集 X 的出现对项集 Y 的出现概率提升的程度。 :代表有提升。 :代表没有提升也没有下降。 :代表有下降。 仍以规则{牛奶,尿布}→{啤酒}为例,其置信度为 ,{啤酒}这一项集的支持度为 , 则其提升度为,说明{牛奶,尿布}这一项集对{啤酒}出现次数是有提升作用的。 频繁项集:支持度大于或等于某个阈值的项集。例如,阈值设为 50%时,因为{牛奶,尿布}的支持度是 60%,所以它是频繁项集。 项集的超集:包含某个项集的元素且元素个数更多的项集。比如{牛奶,尿布}这个项集,它的超集可以是{牛奶,尿布,啤酒},也可以是{牛奶,尿布,啤酒,可乐}。 项集的子集:与超集相反,子集是指包含某个项集的一部分,且元素个数更少的项集。 比如{牛奶,尿布,啤酒,可乐}这个项集,它的子集可以是{牛奶,尿布,啤酒},也可以是{牛奶,尿布}或{牛奶}。
(二)算法原理 有很多人经过以上介绍,直观的感觉是通过遍历法就可以解决问题。事实上,当项目足够多的时候,会产生组合爆炸,即两个两个组合,三个三个组合,四个四个组合等都要遍历一遍,对于数据库的压力是非常大的。一般包含 d 项的数据集中提取可能的规则总数有 个。比如表 2-5-1 的项集中 ,则会产生 条规则。对于成百上千个项目,其规则是天文数字,甚至是计算机无法完成的,这时候就需要采用 Apriori 算法。 Apriori 算法的核心思想: (1)频繁项的非空子集肯定频繁。 (2)如果一个项不频繁,那么它的超项肯定不频繁。 如图 2-5-1 所示,AB 是非频繁项,则 ABC、ABD、ABE、ABCD、ABCE、ABDE、ABCDE均为非频繁项。在数据库扫描寻找频繁项集的时候,就可以排除扫描非频繁项,从而减轻数据库的负担。 关联分析的目标: 发现频繁项集——发现满足最小支持度的所有项集; 发现关联规则——从频繁项集中提取所有高置信度的规则。
[center][size=100]图2-5-1 Apriori 算法核心示意图[/size][/center][center][/center]

图2-5-1 Apriori 算法核心示意图



(三)算法流程 输入:数据集合 D,支持度阈值 a。 输出:最大的频繁项集。 (1)扫描整个数据集,得到所有出现过的数据,作为候选频繁 1 项集。 ,频繁 0 项集为空集。 (2)挖掘频繁项集。 ① 扫描数据计算候选频繁项集的支持度。 ② 去除候选频繁项集中支持度低于阈值的数据集,得到频繁项集。如果得到的频繁项集为空,则直接返回频繁 项集的集合作为算法结果,算法结束。如果得到的频繁项集只有一项,则直接返回频繁项集的集合作为算法结果,算法结束。 ③ 基于频繁项集,连接生成候选频繁项集。 (3)令 ,转入步骤(2)。 以表 2-5-2 中的数据为例。

表2-5-2 示例数据集



① 设置支持度阈值,设最小支持度计数为 2。 ② 扫描集合 D,对每个候选项集的支持度计数,删除没有达到最小支持度计数的项集,即修剪非频繁项,形成 ,如表 2-5-3 所示。 表 2-5-3 ③ 由 产生候选集 (见表 2-5-4),并再次扫描 D,计算候选项集的支持度计数,修剪非频繁项,形成 ,如表 2-5-5 所示。 表 2-5-4 表 2-5-5 ④ 与步骤③相同,由 产生候选集 (见表 2-5-6)。值得注意的是,在 中已经产生非频繁项集,为{L1,L4}、{L3,L4}、{L3,L5}、{L4,L5},所以在产生 时,要注意修剪这些支项,形成 ,如表 2-5-7 所示,这也正是 Apriori 算法有价值的地方。 表 2-5-6 表 2-5-7 按照迭代方法,由 还可以产生新的项集{L1,L2,L3,L5},但{L3,L5}早就判定为非频繁集,所以{L1,L2,L3,L5}也是非频繁项。至此,迭代结束,找到的频繁项集为{L1,L2,L3}和{L1,L2,L5}。 频繁项已经找出,接下来就该由频繁项来导出关联规则。需要说明的是,遴选频繁项的指标是支持度,而导出关联规则的指标是置信度。 仍以上例来说明,频繁项集 l = {L1,L2,L3}能产生的非空子集为{L1,L2}、{L1,L3}、{L2,L3}、{L1}、{L2}和{L3},则其关联规则及置信度如表 2-5-8 所示。 表 2-5-8 关联规则及置信度 如果最小置信度阈值为 70%,则只有 2、3 和最后一个规则可以输出。