文章目录
一、基本概念与解决方法
1. 事务数据库
交易数据库又称事务数据库，尽管它们英文名词一样，但事务数据库更具有普遍性。
-
一个事务数据库中的关联规则挖掘可以描述如下：
设 I = { i1,2,i3...,im}是一个项目集合 ，事务数据库D ={t1,t2,...tn}是由一系列具有唯一标识的TID事务组成。每一个事务ti(i =1,2,...,n)都对应I上的一个子集。
-
2. 定义
-
定义3.1：支持度（集合在 I 中出现的次数）
-
定义3.2：频繁项目集
对于项目集I，在事务数据库D中所有满足用户指定的最小支持度(Minsupport) 的项目集，即不小于Minsupport的I的非空子集，称为
频繁项目集（Frequest Itemsets）或大项目集
-
定义3.3：可信度（比例）
-
定义3.4：强关联规则
-
D在I上满足
最小支持度和最小置信度
的关联规则称为
强关联规则
。 -
通常说的关联规则一般是指强关联规则
-
关联规则挖掘定义：给定一个事务数据库，通过用户指定的最小支持度和最小置信度来寻找强关联规则的过程。
-
D在I上满足
3. 解决方法
关联规则挖掘可以划分为
两个子问题
-
发现频繁项目集：
通过用户给定的最小支持度，寻找所有的频繁项目集，即满足支持度Support不小于Minsupport的所有项目子集。
发现所有频繁项目子集是形成关联规则的基础。
-
生成关联规则：
通过用户给定的最小可信度，在每个最大频繁项目子集中寻找
置信度不小于MInconfidence的关联规则。
-
发现频繁项目子集是近年来的研究重点
二、经典的频繁项目集生成算法分析
1. 项目集空间理论
频繁项目集的子集仍是频繁项目集；非频繁项目集的超集仍是非频繁项目集。
2. Apriori算法
1. 算法的基本思想
基于频繁项目集性质的先验知识，使用由下到上逐层搜索的迭代方法，k项集用于搜索K+1项集。
2.步骤：
-
首先扫描数据库，统计每一个项发生的数目，
找出满足最小支持度的项，
找出
频繁1项集，记作L1
- 然后，**基于L1找出频繁2项集的集合L2，基于L2找出频繁3项集的集合L3，**如此下去，直到不能找到频繁K项集LK。找每一个Lk需要一次数据库全扫描。
3. 核心步骤
Apriori算法的核心由连接步和剪枝步组成。
-
连接步：
为找频繁项集Lk（k > 2），先通过将Lk-1于自身连接产生 候选K项集Ck。
-
剪枝步：
由候选K项集的集合Ck产生频繁项集Lk，Ck是Lk的超集。从Ck中确定Lk。为了压缩Ck，可以利用先验知识：
任何非频繁的（k-1）项集都不是频繁K项集的子集。
4. 伪代码
5. 例题
-
例题1
-
解释：
我们的数据集D有4条记录，分别是134,235,1235和25。现在我们用Apriori算法来寻找频繁k项集，最小支持度设置为50%。首先我们生成候选频繁1项集，包括我们所有的5个数据并计算5个数据的支持度，计算完毕后我们进行剪枝，数据4由于支持度只有25%被剪掉。我们最终的频繁1项集为1235，现在我们链接生成候选频繁2项集，包括12,13,15,23,25,35共6组。此时我们的第一轮迭代结束。
进入第二轮迭代，我们扫描数据集计算候选频繁2项集的支持度，接着进行剪枝，由于12和15的支持度只有25%而被筛除，得到真正的频繁2项集，包括13,23,25,35。现在我们链接生成候选频繁3项集,123, 125，135和235共4组，这部分图中没有画出。通过计算候选频繁3项集的支持度，我们发现123,125和135的支持度均为25%，因此接着被剪枝，最终得到的真正频繁3项集为235一组。由于此时我们无法再进行数据连接，进而得到候选频繁4项集，最终的结果即为频繁3三项集235。 -
例题2
3. 关联规则的生成
1. 步骤
得到了所有的频繁项目集后，可以按照下面的步骤生成关联规则。
-
对于每一个频繁项目集Lk，生成其所有的非空子集。
-
对于Lk的每一个非空子集x，计算Cnference(x -> (Lk – x))
-
如果Conference(x – > (Lk – x)) = support(Lk) / support(x) >= minconfidence ，那么x -> (Lk – x) 成立
上述算法的核心是genrules递归过程，它实现一个频繁项目集中所有强关联规则的生成。
2. 例题
3. 关联规则优化
设频繁项目集I，项目集 x 属于 I，x1为x的一个子集。如果 x ->(Lk - x)不是强关联规则，那么 x1->(Lk-x1) 一定不是强关联规则。
设项目集X，X1是X的一个子集，如果规则Y-> X是强规则，那么规则 Y -> X1 一定是强规则。
