文档介绍：数据挖掘原理、 算法及应用第3章 关联规则挖掘
基 本 概 念
交易数据库又称为事务数据库， 尽管它们的英文名词一样， 但是事务数据库更具有普遍性。例如，病人的看病记录、基因符号等用事务数据库更贴切。因此，下面的叙述更多使用此下去，直到不能找到频繁k项集Lk。找每一个Lk需要一次数据库全扫描。
Apriori算法的核心由连接步和剪枝步组成。
(1) 连接步：为找频繁项集Lk(k≥2)，先通过将Lk-1与自身连接产生候选K项集的集合Ck。设l1和l2是Lk-1中的项集，即l1∈Lk-1，l2∈Lk-1。Apriori算法假定事务或
项集中的项按照字典顺序排列，设li［j］表示li中的第j项。 对于k-1项集li，对应的项排序为：li［1］＜li［2］＜…
＜li［k-1］。 Lk-1与自身连接使用Lk-1∞Lk-1来表示。
如果l1∈Lk-1，l2∈Lk-1中的前k-2个元素相同，则称l1、l2是可连接的，即l1［1］=l2［1］∧l1［2］=l2［2］∧…∧l1［k-1］<l2［k-1］。条件l1［k-1］<l2［k-1］可以保证不产生重复，而按照L1，L2， …，Lk-1，Lk， …，Ln次序寻找频繁项集可以避免对事务数据库中不可能发生的项集所进行的搜索和统计的工作。连接l1、l2的结果项集是l1［1］、l1［2］、 …、 l1［k-1］、l2［k-1］。
(2)剪枝步：由候选K项集的集合Ck产生频繁K项集Lk。 Ck是Lk的超集，也就是说Ck的成员可以不是频繁的，但所有的频繁项集Lk都包含在Ck中。扫描数据库D，统计Ck中每一个候选项集的计数，从而确定Lk。 然而Ck集合中元素数目可能很大，这样所涉及的计算量就很大。为压缩Ck，可以利用频繁项目集性质的先验知识：任何非频繁的(k-1)项集都不是频繁k项集的子集。
因此，如果候选k项集Ck的(k-1)项子集不在Lk-1中，则该候选不可能是频繁的，从而可以从Ck中删除。这种子集测试可以使用所有频繁项集的散列树快速完成。例如，如果2项目集C2={AB, AD, AC, BD}，而对于新产生3项目集中的元素ABC不需要加入到C3中，因为它的2项子集BC不在C2中。 而对于新产生的元素ABD应该加入到C3中，因为它的所有2项子集都在C2中。
【】 表3-1为某一超市销售事务数据库D，使用Apriori算法发现D中频繁项目集。
问题分析：事务数据库D中有9个事务， 即||D||=9。超市中有5件商品可供顾客选择， 即I=｛I1, I2, I3, I4, I5｝，且||I||=5。 设最小支持数minsup_count=2， 则对应的最小支持度为2/9＝%。
表3-1 某一超市销售事务数据库D
事务数据库D中候选项目集、 频繁项目集生成过程如下：
1) 候选1项目集C1的生成
I=｛I1, I2, I3, I4, I5｝中每一项都是候选1项目集合C1的成员，对候选1项目集C1=｛I1,I2,I3,I4,I5｝中的每一个1候选项目集，在数据库D进行扫描，统计它们的支持数。
2) 频繁1项目集L1的生成
在候选1项目集C1=｛I1, I2, I3, I4, I5｝中， 选取支持数不小于最小支持数minsup_count=2的候选1项目集作为频繁1项目集L1, L1=｛I1, I2, I3, I4, I5｝。
3)候选2项目集C2的生成
由频繁1项目集L1=｛I1, I2, I3, I4, I5｝生成候选2项目集C2。 由数学中组合知识和2候选项目集定义可知，2候选项目集C2是1频繁项目集L1=｛I1, I2, I3, I4, I5｝的全组合，共有C2 |L1|种组合，也就是说, 2候选项目集C2中共有C2|L1|个元素。为了提高算法效率，Apriori算法使用连接L1∞L1产生候选项目集C2。L1∞L1连接运算要求两个连接的项集共享0个项，Lk∞Lk运算中要求两个连接的项集共享k-1个项。对候选项目集C2中的每一个2候选项目集，在数据库D进行扫描，统计它们的支持数。
4) 2频繁项目集L2的生成
在2候选项目集C2中，选取支持数不小于最小支持数minsup_count=2的候选项目集作为2频繁项目集L2。
5) 3候选项目集C3的生成
由2频繁项目集L2生成3候选项目集C3。 首先按照连接步定义计算C3=L2∞L2={{I1, I2, I3}, {I1, I2, I5}, {I1, I3, I5}, {I2, I3, I4}, {I2, I3, I5}, {I2, I4, I5}}；然后按照剪枝步的方法，频繁项集的所有子集也必须是频繁的，可以确定后4个候选不可能是频