2018-03-24 第六章：挖掘频繁模式、关联和相关性：基本概念
6.1 基本概念
6.1.1频繁模式与关联规则
频繁模式： 频繁地出现在数据集中的模式，包括：频繁项集、频繁序列模式、频繁结构模式
- 频繁项集：如频繁地同时出现在交易数据集中的商品的集合，如：面包和牛奶；
- 频繁序列模式：频繁地出现在数据集中的序列，如：用户先买数码相机，再买内存卡；
- 频繁结构模式：一个子结构可能涉及不同的结构形式，如子图、子树等，可能与项集或子序列结合在一起，频繁出现的子结构；
关联规则： 频繁模式可以用关联规则表示，如：A->B [support=s,confidence=c]
- 支持度：同时包含A和B的事务的个数（绝对支持度）或者比率（相对支持度）；
- 置信度：在包含项A的事务中，又包含B的事务的比率。
相对支持度： support(A->B)=P(A∪B) 绝对支持度：support(A->B)=count(A∪B)
置信度：confidence(A->B)=P(B|A)- 频繁项集：项集I的相对支持度满足预定义的最小支持度阀值（绝对支持度满足最小支持度计数阀值），则I是频繁项集
- 如果关联规则满足最小支持度阀值 和最小置信度阀值 ，则关联规则被认为是有趣、强关联的。
6.1.2关联规则的挖掘步骤：
- 找出所有的频繁项集 ：根据定义，这些项集的每一个频繁出现的次数要不小于预定义的最小支持度计数阀值；
- 由频繁项集产生强关联规则： 根据定义，这些规则必须满足最小支持度和最小置信度6.1.2关联规则的挖掘步骤：
6.1.3 闭频繁项集与极大频繁项集：
- 闭频繁项集： 项集X在数据集D中是闭的，如果不存在真超项集Y是使得Y与X在D中具有相同的支持度计数；（通俗地来说，就是项集X，只要再添加一项，支持度计数就会下降）
- 极大频繁项集： 如果X是频繁的，并且不存在超项集Y使得Y在D中是频繁的（通俗地来说，就是项集X，只要再添加一项，就不频繁了）
实例：假定事务数据库中有两个事务，{a1,a2,a3,......a99,a100}，{a1,a2,a3,......a49,a50}，设最小支持度计数阀值min_sup=1
则：闭频繁项集为{a1,a2,a3,......a49,a50}，极大频繁项集为{a1,a2,a3,......a99,a100}
6.2 频繁项集挖掘方法
6.2.1 Apriori算法：通过限制候选产生发现频繁项集
- 先验性质 ：频繁项集的所有非空子集也一定是频繁项集；非频繁项集的所有超集一定也是非频繁项集。
- 算法原理： 使用逐层搜索的迭代方法，通过连接步和剪枝步，使用K项集搜索（K+1）项集
- 算法步骤： 首先，扫描数据库，累计单项的计数，找出满足最小支持度阀值的单项集，记为L1；然后，使用L1找出频繁2项集的集合L2，使用L2找L3......直到不能再找出频繁K项集。
- 生成强关联规则： 对于之前得到的每一个频繁项集L，产生L的非空子集；对每一个非空子集，生成关联规则并且计算置信度，不小于置信度阀值的即为强关联规则。
- 应用案例：
注意：该过程每一步得到的LK都是频繁项集；根据频繁项集后续可以计算强关联规则。
- 算法改进： Aprioir算法每一次都需要扫描整个数据集，所以效率很低。有以下几种变形：
- 基于散列的技术：散列项集到对应的桶中；
- 事务压缩：不包含任何频繁K项集的事务不可能包含任何频繁（K+1）项集，利用这个将事务加上标记或删除，下次扫面跳过这些事务；
- 划分：为找候选项集划分数据。首先将事务分区，扫描一次，展出每个分区的局部频繁项集，组合所有的局部频繁项集形成候选集，之后再找出候选项集中的全局频繁项集
- 抽样：对给定数据集的一个子集上挖掘；
- 动态项集技术：在扫描的不同点添加候选项集
6.2.2 FP-growth算法（频繁模式增长）：发现频繁模式而不产生候选
- 算法步骤： 首先，数据库的第一次扫描与Apriori相同，导出频繁1项集；然后根据支持度技术的递减顺序将频繁1项集排序；其次构造FP树；最后挖掘FP树得到频繁模式。
- 应用案例：
FP树挖掘： 由长度为1的频繁模式开始，构造它的条件模式基（由FP树与该后缀模式一起出现的前缀路径组成）进而生成条件FP树
**
**
对每一个1项集，都按照这个操作，最后找到频繁模式。
6.2.3 使用垂直数据格式挖掘频繁项集
Apriori算法和FP-growth算法都是从TID项集格式（{TID：itemset}）的事务集中挖掘频繁模式，其中TID是事务标识符，而itemset是事务TID中的元素。这种数据格式称为水平数据格式。
数据用项-TID集格式（{itemset：TID}）表示，这种格式称为垂直数据格式。
- 算法步骤： 首先扫描一次数据库，将水平格式的数据转换成垂直格式；然后，从K=1开始，根据先验性质，使用频繁K项集来构造候选（K+1）项集，通过取频繁K项集的TID集的交，计算对应的（K+1）项集的TID集。重复该过程，直到不能再找到频繁项集或候选项集。
- 应用实例
取交集：
最后结果：
6.3 模式评估方法
大部分关联规则挖掘算法都使用支持度-置信度框架。尽管最小支持度和置信度阀值有助于排除大量无趣规则的探查，但仍然会产生一些用户不感兴趣的规则。强规则不一定是有趣的，甚至会误导。
如：假设有10000个事务中，数据显示6000个顾客事务包含计算机游戏，7500个事务包含录像，而4000个事务同时包含计算机游戏和录像，预定义最小支持度30%，最小置信度60%。考虑如下关联规则：computer games->videos，该关联规则是强关联规则，因为支持度为4000/10000=40%，置信度为4000/6000=66%，满足阀值。因此会得到：买计算机游戏的顾客还有66%的可能性会购买录像。然而，实际情况是，在所有的事务中，购买录像的概率是75%，比66%还高，说明购买计算机游戏和录像是负相关的。
因此，规则A->B有一定的欺骗性。它并不度量A和B之间相关和蕴含的实际强度，因此需要一些相关性度量标准。
6.3.1 从关联分析到相关分析：
- 提升度（lift）： lift（A,B）=P(AB)/P(A)P(B)
lift=1，表示A与B独立，没有相关性；lift<1，表示A与B负相关；lift>1，表示A与B正相关
- 卡方度量：
- 还有其他的一些度量方法，自行查阅。