关联分析

来自 搜狐网 的图片

关联分析是一个专用名词。

汉字(拼音:hàn zì，注音符号:ㄏㄢˋ ㄗˋ)，又称中文、中国字、方块字，是汉语的记录符号，属于表意文字的词素音节文字。世界上最古老的文字之一，已有六千多年的历史。在形体上逐渐由图形变为笔画，象形变为象征，复杂变为简单;在造字原则上从表形、表意到形声。除极个别汉字外(如瓩、兛、兣、呎、嗧等)，都是一个汉字一个音节。 需要注意的是，日本、韩国、朝鲜、越南等国在历史上都深受汉文化的影响，甚至其语文都存在借用汉语言文字的现象。

目录

名词解释

关联分析就是对数据集中反复出现的相关关系和关联性进行挖掘提取，从而可以根据一个数据项的出现预测其他数据项的出现。

关联分析的典型例子

啤酒和尿布案例，数据挖掘发现在大型超市中购买啤酒的男士经常同时购买小孩的纸尿裤，基于这一发现，超市把啤酒和纸尿裤摆放在一起，结果两种商品的销售量都有明显提升。消费者行为海量数据的关联分析在电商精准销售中得到广泛应用，对其货品种类、库存、仓储、物流和广告业务都有极大的效益回馈。

常见的关联分析方法

Apriori算法

Apriori算法是挖掘产生布尔关联规则所需频繁项集的基本算法，也是最著名的关联规则挖掘算法之一。Apriori算法就是根据有关频繁项集特性的先验知识而命名的。它使用一种称作逐层搜索的迭代方法，k—项集用于探索（k+1）—项集。首先，找出频繁1—项集的集合．记做L1，L1用于找出频繁2—项集的集合L2，再用于找出L3，如此下去，直到不能找到频繁k—项集。找每个Lk需要扫描一次数据库。

为提高按层次搜索并产生相应频繁项集的处理效率，Apriori算法利用了一个重要性质，并应用Apriori性质来帮助有效缩小频繁项集的搜索空间。

Apriori性质：一个频繁项集的任一子集也应该是频繁项集。证明根据定义，若一个项集I不满足最小支持度阈值min_sup，则I不是频繁的，即P（I）<min_sup。若增加一个项A到项集I中，则结果新项集（I∪A）也不是频繁的，在整个事务数据库中所出现的次数也不可能多于原项集I出现的次数，因此P（I∪A）<min_sup，即（I∪A）也不是频繁的。这样就可以根据逆反公理很容易地确定Apriori性质成立。

针对Apriori算法的不足，对其进行优化：

1）基于划分的方法。该算法先把数据库从逻辑上分成几个互不相交的块，每次单独考虑一个分块并对它生成所有的频繁项集，然后把产生的频繁项集合并，用来生成所有可能的频繁项集，最后计算这些项集的支持度。这里分块的大小选择要使得每个分块可以被放入主存，每个阶段只需被扫描一次。而算法的正确性是由每一个可能的频繁项集至少在某一个分块中是频繁项集保证的。

上面所讨论的算法是可以高度并行的。可以把每一分块分别分配给某一个处理器生成频繁项集。产生频繁项集的每一个循环结束后．处理器之间进行通信来产生全局的候选是一项集。通常这里的通信过程是算法执行时间的主要瓶颈。而另一方面，每个独立的处理器生成频繁项集的时间也是一个瓶颈。其他的方法还有在多处理器之间共享一个杂凑树来产生频繁项集，更多关于生成频繁项集的并行化方法可以在其中找到。

2）基于Hash的方法。Park等人提出了一个高效地产生频繁项集的基于杂凑（Hash）的算法。通过实验可以发现，寻找频繁项集的主要计算是在生成频繁2—项集Lk上，Park等就是利用这个性质引入杂凑技术来改进产生频繁2—项集的方法。

3）基于采样的方法。基于前一遍扫描得到的信息，对它详细地做组合分析，可以得到一个改进的算法，其基本思想是：先使用从数据库中抽取出来的采样得到一些在整个数据库中可能成立的规则，然后对数据库的剩余部分验证这个结果。这个算法相当简单并显著地减少了FO代价，但是一个很大的缺点就是产生的结果不精确，即存在所谓的数据扭曲（Dataskew）。分布在同一页面上的数据时常是高度相关的，不能表示整个数据库中模式的分布，由此而导致的是采样5%的交易数据所花费的代价同扫描一遍数据库相近。

4）减少交易个数。减少用于未来扫描事务集的大小，基本原理就是当一个事务不包含长度为志的大项集时，则必然不包含长度为走k+1的大项集。从而可以将这些事务删除，在下一遍扫描中就可以减少要进行扫描的事务集的个数。这就是AprioriTid的基本思想。

FP-growth算法

由于Apriori方法的固有缺陷．即使进行了优化，其效率也仍然不能令人满意。2000年，Han Jiawei等人提出了基于频繁模式树（Frequent Pattern Tree，简称为FP-tree）的发现频繁模式的算法FP-growth。在FP-growth算法中，通过两次扫描事务数据库，把每个事务所包含的频繁项目按其支持度降序压缩存储到FP—tree中。在以后发现频繁模式的过程中，不需要再扫描事务数据库，而仅在FP-Tree中进行查找即可，并通过递归调用FP-growth的方法来直接产生频繁模式，因此在整个发现过程中也不需产生候选模式。该算法克服了Apriori算法中存在的问颢．在执行效率上也明显好于Apriori算法。