并联规则挖掘

关联规则种类

1、基于规则中处理的变量的类别

关联规则可以分为种类型和数值型

关联规则	内容
种类型	关联规则处理的值都是离散的、种类化的
数值型	可以和多维关联或多层关联规则结合起来，对数值型字段进行处理

2、基于规则中数据的抽象层次

可以分为单层关联规则和多层关联规则

关联规则	内容
单层关联规则	所有变量都没有考虑到现实数据是具有多个不同层次的
多层关联规则	对数据的多层性已经进行了充分的考虑

3、基于规则中涉及到的数据的维数

可以分为单维和多维

关联规则	内容
单维关联规则	涉及的数据只有一个维
多维关联规则	要处理的数据将会涉及到多维

关联规则挖掘算法

并联规则算法的设计可以分为分解为两个子问题

1、找到所有支持度大于最小支持度的项集，这些项集称为频集。

2、使用上一步找到的频集产生期望的规则。

基于Apriori频繁算法的几种优化方式

虽能Apriori算法自己已经进行了一定的优化，但是在实际应用中还是存在令人不满意的地方。

1、基于划分的方法：

为了降低算法对内存的需求同时提高并行性，基于划分（partition）的算法，该算法先把数据库从逻辑上分成几个互不相交的块，每次单独考虑一个分块（分块的大小选择要使得每个分块可以被放入主存）并对它生成所有的频集，然后把产生的频集合并，用来生成所有可能的频集，最后计算这些项集的支持度。

该算法可以高度并行，可以使每一个块分别分配给某个处理器生成频集。

2、基于hash的方法

通过实验可以发现寻找频集主要的计算是在生成频繁2-项集Lk上

3、基于采样的方法

从数据库中抽取出来的采样得到一些在整个数据库中可能成立的规则，然后对数据库的剩余部分验证这个结果。

4、减少交易个数

减少用于未来扫描的事务集的大小。一个基本原理就是一个事务不包含长度为k的大项集则必然不包含长度为k+1的大项集，从而就可以将这些事务移去，这样就可以在下一遍扫描中减少要扫描的事务集个数，这个也就是AprioyiTid的基本思想。

其它频集挖掘方法

虽能上述进行了Apriori算法的一些优化，但还是会有一些固有的缺陷还是无法克服

问题	内容
可能产生大量的候选集	当长度为1的频集有10000个的时候，长度为2的候选集个数将超过1000万。还有就是如果要生成一个很长的规则的时候，要产生的中间元素也是巨大量的。
无法对稀有信息进行分析	由于频集使用了参数minsup（最小支持度），所以就无法对小于minsup的事件进行分析，而如果将minsup设置成很低的值，那么算法的效率就成了一个很难处理的问题。

优化方法

方法	内容
FP-growth	使用分而治之的策略，在经过了第一次扫描之后，把数据库中的频集压缩进一颗频繁模式树（FP-tree），同时保留其中的关联信息，随后我们将FP-tree分化成一些条件库，每个库和一个长度为1的频集相关。然后再对这些条件库分别进行挖掘。当原始数据量很大的时候，可以结合划分的方法，使得一个FP-tree可以存放到主存中。
Min_hashing和Locality_Sensitive_Hashing	将可信度放在第一位，挖掘一些具有非常高可信度的规则。

信息来源：
关联规则挖掘综述
蔡伟杰 张晓辉 朱建秋 朱扬勇
复旦大学计算机科学系 复旦大学计算机科学系 上海200433