数据挖掘算法——关联规则挖掘算法

1基本概念1.1引入：购物篮分析假定作为超市的销售经理，你想更多地了解顾客的购物习惯，尤其是，你想知道“顾客可能会在一次购物同时购买哪些商品？”经常同时购买的商品可以摆放的近一些，以便进一步刺激这些商品同时销售。也可以将硬件和软件摆放在商店的两头，可能诱发买这些商品的顾客一路挑选其它的商品。1.2 一个购物篮实例TID

Instant_

16982人浏览 · 2015-04-18 15:51:51

Instant_ · 2015-04-18 15:51:51 发布

1基本概念

1.1引入：购物篮分析

假定作为超市的销售经理，你想更多地了解顾客的购物习惯，尤其是，你想知道“顾客可能会在一次购物同时购买哪些商品？”经常同时购买的商品可以摆放的近一些，以便进一步刺激这些商品同时销售。也可以将硬件和软件摆放在商店的两头，可能诱发买这些商品的顾客一路挑选其它的商品。

1.2 一个购物篮实例

TID	项集
1	{ 面包，牛奶}
2	{面包，尿布，啤酒，鸡蛋}
3	{ 牛奶，尿布，啤酒，可乐}
4	{ 面包，牛奶，尿布，啤酒}
5	{ 面包，牛奶，尿布，可乐}

其中 TID为事务的标号，可以理解为顾客的一次购买行为，例如TID=1表示，某一次一位顾客同时购买了面包与牛奶。

项集是项的集合，包含k个项的集合称为k项集，例如{面包，牛奶}为2项集，{面包，尿布，啤酒，鸡蛋}为4项集。

1.3 关联规则的表示方式

例如：购买计啤酒的人趋向于同时购买尿布

啤酒=> 尿布[ support = 60% ; confidence = 100% ]

Support：支持度百分之60显示所有事务中有百分之60显示啤酒和尿布被同时购买。

confidence：置信度百分之100表明所有购买啤酒的顾客有百分之100同时购买了尿布。

规则的支持度和规则的置信度是规则度量的两种方式。

支持度：确定规则可以用于给定数据集的频繁程度，给定一个最小支持度阈值，若一个项集的支持度大于阈值，则可以把此项集叫做频繁项集。

置信度：确定B在包含A的事务中出现的频繁程度。

1.4 支持度和置信度的计算方式

Support（ A=> B ) = P ( A U B )

support(A U B ) support_count(A U B )

Confidence( A => B )＝Ｐ（Ｂ｜Ａ）＝　—————————= ———————————

support( A ) support_count(A )

其中support_count是支持度计数，和支持度的区别在于，支持度是支持度计数和所有事务的比值，

即： support_count(A )

support(A ) = ———————————— ，其中U为全集。

support_count(U )

1.5 关联规则的产生方式

（1）在所有项集中找出满足最小支持度阈值的所有项集，这些项集称作频繁项集。

（2）从上一步找到的频繁项集中提取所有高置信度的规则，这些规则称作强规则。

1.6 查找频繁项集的原始方法

采用原始方法查找上面购物篮实例里的频繁项集：示例中所有的事务产生的项的集合为{面包、牛奶、尿布、啤酒、鸡蛋、可乐}，设最小支持度阈值为60%。

对于1项集{面包}，依次比较事务1至5，得出support({面包}）=80%；

对于2项集{啤酒、尿布}依次比较事务1至5得出support（{啤酒、尿布}）= 60%；

...

此6项集包含个1项集，个2项集，个3项集等，对于所有子集都采用以上方式去进行计算，然后我们找到所有的满足最小支持为60%阈值的项集。

1.7 原始方法查找频繁项集的缺点

（1）候选项集数目过大

上例中候选项集为++=2~6 - 1 =63，随着项的总数的增多，例如一家超市有一千种商品，则有2~1000 - 1 的候选项集，呈指数增长。

（2）比较次数过多

上例中每个项集都要和五个事务比较，随着事务数量的增大，计算次数会越来越多。

2 Apriori算法

2.1 先验定理

先验定理：如果一个项集是频繁的，则它的所有的子集一定也是频繁的。

逆否，如果一个项集是非频繁的，则它的所有超集也一定是非频繁的。

2.2 Apriori算法

开创性地使用基于支持度的剪枝技术，系统地控制候选项集指数增长。

基于先验定理的剪枝技术，仅通过频繁k-1项集来产生候选k项集。

例如：上面实例，假若支持度阈值为60%，则支持度计数阈值5*0.6=3

1项集，可乐，鸡蛋不是频繁的，则它们的超集必定不是频繁的；

2项集{啤酒，面包}、{啤酒、牛奶}不是频繁的，则它们的超级也必定不是频繁的。

2.3 Apriori算法伪代码描述

产生候选k项集的几种方式

1、初始单遍扫描数据集，确定每个项的支持度。得到所有频繁1项集F1；

2、使用上一次迭代发现的频繁(k-1）项集，产生新的候选k项集；

3、再次扫描数据集，确定候选k项集的支持度；

4、删除不是频繁的候选k项集；

5、循环2-3步，当没有新的频繁项集产生，则算法结束。

问题：如何通过频繁的候选（k-1）项集，产生候选k项集？

2.4 产生候选k项集的几种方式

1、蛮力法

先通过所有1项集产生所有的k项集，然后删除包含不频繁的（k-1）项集的k项集。

例：

频繁项集的格

2 F_(k-1) * F_（k）方法

用其它频繁项来产生候选k项集，然后候选剪枝掉非频繁3项集。

例：通过频繁2项集和频繁1项集来产生候选3项集

该方法存在的问题：

（1）在具体合并的时候，不同的项集合并可能产生相同的项集，例如{面包、尿布}和{牛奶}合并，与{面包、牛奶}和{尿布}合并会得到同样的{面包、尿布、牛奶}，解决此问题的方法：确保每个频繁项集中的项都以字典序存储，每个频繁（k-1）项集x，只用字典序比x中所有的项都大的频繁项进行合并。例如，可以用{牛奶（milk）}来拓展{面包（bread）、尿布（diapers）}，{面包、牛奶}不能用尿布拓展，因为m为首的单词在字典中的位置是在b和d后面。

假使上述单词用中文表示，{面包（mianbao）、尿布（niaobu）}，{牛奶（niunai）}，牛奶和尿布的首写字母一样，可以继续比较第二位都是i，再比较第三位u在a后面，以此类推，然后长度短放后面等等，即将集合通过某种方式进行序列化。

（2）尽管此方法优于蛮力法，但也同样产生许多不必要的候选k项集，然后需要剪枝进一步确定频繁k项集。

3 F_(k-1) * F_（k-1）方法

（1）通过合并两个候选k-1项集来产生候选k项集

合并规则：如果两个频繁k-1项集的前k-2项相同，则合并此两个候选k-1项集。

*注意，此合并方法在各向集都采用”字典序"存储的情况下使用较好。

（2）合并后产生候选k项集，然后通过剪枝方法产生频繁k项集

2.5 支持度计数的确定

通过理解了上面的几个算法，知道了产生候选k项集的几种常用方式，然后通过支持度阈值来剪枝掉低于支持度阈值的项集，从而产生频繁项集，那么如何得到一个项集的支持度计数？

方法一：将候选项集依次与每个事务做比较，然后更新包含在事务中的候选项集的支持度计数。

缺点：当事务和候选项集的数目都很大的时候开销过大。

方法二：枚举每个事务所包含的所有项集，并且更新它们所对应的候选项集的支持度，那些不与候选项集的事务对应的事务项集的自己可以忽略。

问题：为什么方法二优于方法一？

解答：以超市购物为例，顾客同一单购买的东西一般不会特别多，但是超市每天的交易单数会特别庞大。一个事物产生的项集不会特别多。

2.6 使用Hash数进行支持度计算，提高apriori效率

在Apriori算法中可以将候选集划分为不同的桶，并存放在对应的Hash树中。在支持度计数期间，包含在事务中的项集也散列到相应的桶中。此种方法可以不必要将事务产生的项集与所有的候选项集进行比较，而只需要和桶内的候选项集比较，从而节约了时间。

例如：上例中候选2项集通过字典序分到不同的桶中，然后通过遍历事务集来增加对应项的支持度计数。

2.7 由频繁项集产生关联规则

一旦由数据库D中的事务找出频繁项集，就可以直接由它们产生强关联规则（强关联规则满足最小支持度和最小置信度）。

通过频繁项集产生强关联规则的步骤如下：

1、对于每个频繁项集L，产生L的所有非空真子集。

2、对于每个非空真子集S，如果置信度大于最小置信度，则输出规则“S=> (L – S);

由于规则由频繁项集产生，则规则一定满足最小支持度，只用计算规则的最小置信度即可。

示例：上面最终产生的频繁3项集为{面包、尿布、牛奶}

该频繁项集的非空子集为{面包}，{尿布}，{牛奶}，{面包、尿布}，{面包、牛奶}，{尿布、牛奶}。

{面包}=> {尿布、牛奶} confidence= 3 / 4 = 75%

{尿布}=> {面包、牛奶} confidence = 3 / 4 = 75%

{牛奶}=> {面包、尿布} confidence = 3 / 4 = 75%

{面包、尿布}= > {牛奶}confidence = 3 / 3 = 100%

{面包、牛奶}=> {尿布}confidence = 3/3 = 100%

{尿布、牛奶}=> {面包}confidence = 3/3 = 100%

2.8 Apriori算法特点

Apriori算法在早期成功地处理了频繁项集产生的组合爆炸问题的算法之一。它通过使用先验定理对指数搜索空间进行剪枝，成功地处理了组合爆炸的问题。但是通过以上的讲解，我们可以知道该算法需要经常扫描数据集，对于每个事务的平均项集很大的数据集来说，由于每个事务项集的子集非常多，大大地降低了apriori算法的效率。

3 FP 增长算法

示例：

3.1 如何通过FP树提取规则

规则的提取由最后的结点e开始，按照与建树相反的顺序进行提取。（假定支持度计数为2）

以结点e为例：

1、收集包含e结点的所有路径，这些初始的路径称为前缀路径（prefixpath）。

2、如图所示的前缀路径，通过把与结点e相关联的支持度计数相加得到e的支持度计数。假定最小的支持度为2，因为{e}的支持度是3所以它是频繁项集。

3、由于{e}是频繁的，因此算法必须解决发现以de、ce、be和ae结尾的频繁项集的子问题。在解决这些子问题之前，必须先将前缀路径转换成条件fp树。除了用于发现以某特定后缀结尾的频繁项集之外，条件fp树的结果与fp树类似。

条件fp树通过以下步骤得到：

a、首先，必须更新前缀路径上的支持度计数。因为某些计数包含哪些不含项e的事务。例如图中最右边路径null->b:2->c:2->e:1,包含并不包含项e事务{b、c}。因此，必须将该前缀路径上的计数调整为1，以反映包含{b，c，e}的事务的实际个数。

b、删除e的结点，修剪前缀路径.删除这些结点是因为，沿这些前缀路径的支持度计数已经更新，以反映包含e的那些事务，并且以发现de、ce、be和ae结尾的频繁项集问题的子问题不再需要结点e信息。

c、更新沿前缀路径上的支持度计数后，某些项可能不是频繁的，删除那些不是频繁的项。

4、FP增长使用e的条件fp树来解决发现以de、ce、be和ae结尾的频繁项子问题。为了发现以de结尾的频繁项集，从项e的条件fp树来收集d的所有前缀路径。通过将与结点d相关联的频度计数求和，得到项集{d、e}的支持度计数。因为{d、e}支持度为2，是频繁的，保留。再构建{de}的条件FP树，该树只包含一个支持度等于最小支持度的项a，所以提取出{a、d、e}。用同样的方法去判断{c、e}、{b、e}、{a、e}。