第3章 关联规则挖掘
(1) 发现频繁项目集：通过用户给定的最小支持度， 寻找所有频繁项目集，即满足支持度Support不小于 Minsupport的所有项目子集。发现所有的频繁项目集是形 成关联规则的基础。
(2) 生成关联规则：通过用户给定的最小可信度， 在 每个最大频繁项目集中，寻找置信度不小于Minconfidence 的关联规则。
第3章 关联规则挖掘
按假设， 项目集X是非频繁项目集， support(X)<minsupport
所以support (Z)≤support (X)<minsupport，因此Z不是 频繁项目集。
1993年，Agrawal等人在提出关联规则概念的同时， 给出了相应的挖掘算法AIS，但性能较差。1994年，他们 依据上述两个定理，提出了著名的Apriori算法， Apriori算 法至今仍然作为关联规则挖掘的经典算法，其他算法均是 在此基础上进行改进的。
定义3.3 一个定义在I和D上，形如I1 I2的关联规 则通过满足一定的可信度、信任度或置信度(Confidence) 来定义的。所谓规则的可信度，是指包含I1和I2的事务数 与包含I1的事务数之比， 即
confidence(I1
I2)
support(I1 I2 ) support(I1)
(3.2)
第3章 关联规则挖掘
定义3.4 D在I上满足最小支持度和最小置信度 (Minconfidence)的关联规则称为强关联规则 (Strong Association Rules)。
通常所说的关联规则一般是指强关联规则。 一般地，给定一个事务数据库，关联规则挖掘问题就是 通过用户指定最小支持度和最小可信度来寻找强关联规则的 过程。 关联规则挖掘问题可以划分成两个子问题。
第3章 关联规则挖掘
3.1 基 本 概 念
交易数据库又称为事务数据库， 尽管它们的英文名词一 样， 但是事务数据库更具有普遍性。例如，病人的看病记录、 基因符号等用事务数据库更贴切。因此，下面的叙述更多使 用事务数据库这一名词，而不用交易数据库这个名词。
第3章 关联规则挖掘
一个事务数据库中的关联规则挖掘可以描述如下： 设I= {i1, i2, …, im} 是一个项目集合， 事务数据 库D= {t1, t2, …, tn} 是由一系列具有惟一标识的TID事务组成。 每一个事务ti (i=1, 2, …, n)都对应I上的一个子集。 定义3.1 设I1 I，项目集(Itemsets)I1在数据集D上的 支持度(Support)是包含I1的事务在D中所占的百分比，即
第3章 关联规则挖掘
定理3.2 如果项目集X是非频繁项目集，那么它的所 有超集都是非频繁项目集。
证明 设事务数据库D中支持X的元组数为S。设X的任
一超集Z X， 事务数据库D中支持Z的元组数为S2。
根据项目集支持度的定义， 很容易知道t(Z)≤support(X)
证明 设X是一个项目集，事务数据库D中支持X的元组 (记录)数为S。设X的任一非空子集Y X，事务数据库D中支 持Y的元组(记录)数为S1。
根据项目集支持度的定义，很容易知道支持X的元组一 定支持Y，所以S1≥S，
support (Y)≥support (X) 按假设，项目集X是频繁项目集，
support(X)≥minsupport 所以support (Y)≥support (X)≥minsupport， 因此Y是频繁 项目集。
第3章 关联规则挖掘
3.2 关联规则挖掘算法
3.2.1 项目集空间理论
Agrawal等人建立了用于事务数据库挖掘的项目集空间 理论。理论的核心为：频繁项目集的子集仍是频繁项目集； 非频繁项目集的超集是非频繁项目集。 这个理论一直作为经 典的数据挖掘理论被应用。
第3章 关联规则挖掘
定理3.1 如果项目集X是频繁项目集，那么它的所有非 空子集都是频繁项目集。
第3章 关联规则挖掘
第3章 关联规则挖掘
3.1 基本概念 3.2 关联规则挖掘算法 3.3 Apriori改进算法 3.4 不候选产生挖掘频繁项集 3.5 使用垂直数据格式挖掘频繁项集 3.6 挖掘闭频繁项集 3.7 挖掘各种类型的关联规则 3.8 相关分析 3.9 基于约束的关联规则 3.10 矢量空间数据库中关联规则的挖掘
(3.1)
式中： ||·||表示集合中元素数目。
第3章 关联规则挖掘
定义3.2 对项目集I，在事务数据库D中所有满足用 户指定的最小支持度 (Minsupport) Minsupport的I的非空子集，称为频繁项目集 (Frequent Itemsets) 或大项目集(Larg Itemsets)。
第3章 关联规则挖掘
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来表示。
第3章 关联规则挖掘
如果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］。
第3章 关联规则挖掘
3.2.2
Apriori算法是R.Agrawal和R.Strikant于1994年提出的布 尔关联规则挖掘频繁项集的原创性算法。算法的基本思想： 基于频繁项目集性质的先验知识，使用由下到上逐层搜索的 迭代方法，k项集用于搜索k+1项集。首先，扫描数据库， 统计每一个项发生的数目，找出满足最小值支持度的项， 找出频繁1项集，计作L1； 然后，基于L1找出频繁2项集的集 合L2， 基于L2找出频繁3项集的集合L3，如此下去，直到不 能找到频繁k项集Lk。找每一个Lk需要一次数据库全扫描。