本节书摘来自华章出版社《R语言数据挖掘》一书中的第2章，第2.2节，作者［哈萨克斯坦］贝特·麦克哈贝尔（Bater Makhabel），李洪成 许金炜 段力辉 译，更多章节内容可以访问云栖社区“华章计算机”公众号查看。

2.2　购物篮分析

购物篮分析（Market basket analysis）是用来挖掘消费者已购买的或保存在购物车中物品组合规律的方法。这个概念适用于不同的应用，特别是商店运营。源数据集是一个巨大的数据记录，购物篮分析的目的发现源数据集中不同项之间的关联关系。

2.2.1　购物篮模型

购物篮模型是说明购物篮和其关联的商品之间的关系的模型。来自其他研究领域的许多任务与该模型有共同点。总言之，购物篮模型可作为研究的一个最典型的例子。

购物篮也称为事务数据集，它包含属于同一个项集的项集合。

Apriori算法是逐层挖掘项集的算法。与Apriori算法不同，Eclat算法是基于事务标识项集合交集的TID集合交集项集的挖掘算法，而FP-Growth算法是基于频繁模式树的算法。TID集合表示交易记录标识号的集合。

2.2.2　Apriori算法

作为常见的算法设计策略，Apriori算法挖掘关联规则可以分解为以下两个子问题：

频繁项集生成

关联规则生成

该分解策略大大降低了关联规则挖掘算法的搜索空间。

2.2.2.1　输入数据特征和数据结构

作为Apriori算法的输入，首先需要将原始输入项集进行二值化，也就是说，1代表项集中包含有某项，0代表不包含某项。默认假设下，项集的平均大小是比较小的。流行的处理方法是将输入数据集中的每个唯一的可用项映射为唯一的整数ID。

项集通常存储在数据库或文件中并需要多次扫描。为控制算法的效率，需要控制扫描的次数。在此过程中，当项集扫描其他项集时，需要对感兴趣的每个项集的表示形式计数并存储，以便算法后面使用。

在研究中，发现项集中有一个单调性特征。这说明每个频繁项集的子集也是频繁的。利用该性质，可以对Apriori算法过程中的频繁项集的搜索空间进行剪枝。该性质也可以用于压缩与频繁项集相关的信息。这个性质使频繁项集内的小频繁项集一目了然。例如，从频繁3项集中可以轻松地找出包含的3个频繁2项集。

当我们谈论k项集时，我们指的是包含k个项的项集。

购物篮模型表采用水平格式，它包含一个事务ID和多个项，它是Apriori算法的基本输入格式。相反，还有另一种格式称为垂直格式，它使用项ID和一系列事务ID的集合。垂直格式数据的挖掘算法留作练习。

2.2.2.2　Apriori算法

在Apriori算法频繁项集产生过程中，主要包含以下两种操作：连接和剪枝。
一个主要的假定是：任何项集中的项是按字母序排列的。

连接：给定频繁k-1项集Lk-1，为发现频繁k项集Lk，需要首先产生候选k项集（记为Ck）。

剪枝：候选项集Ck通常包含频繁项集LkCk，为减少计算开销。这里利用单调性质对Ck进行剪枝。

以下是频繁项集产生的伪代码：

2.2.2.3　R语言实现

这里给出Apriori频繁项生成集算法的R语言代码。记事务数据集为D，最小支持计数阈值为MIN_SUP，算法的输出为L，它是数据集D中的频繁项集。

Apriori函数的输出可以用R添加包arules来验证，该包可以实现包含Apriori算法和Eclat算法的模式挖掘和关联规则挖掘。Apriori算法的R代码如下：

为了检验上面的R代码，可以应用arules添加包对算法输出进行验证。

Arules添加包（Hahsler et al.，2011）提供了挖掘频繁项集、最大频繁项集、封闭频繁项集以及关联规则等功能。可用的算法包含Apriori算法和Eclat算法。此外，arulesSequence添加包（基于arules添加包）中还包含cSPADE算法。

给定项集：

首先，利用预先定义的排序算法将D中的项组织为有序列表，这里，简单地根据字母顺序将各项进行排序，可得到：

假定最小支持计数为5，输入数据如下表所示：

在对数据集D的第一次扫描中，可以得到每个候选1项集C1的支持计数。候选项集及其支持计数为：

在将支持计数与最小支持计数比较后，可以得到频繁1项集L1：

通过L1，产生候选项集C2，C2={{I1, I2}, {I1, I4}, {I2, I4}}。

将支持计数与最小支持数比较后，可以得到L2=?。然后，算法终止。

2.2.2.4　Apriori算法的变体

为提升Apriori算法的效率和可扩展性，人们提出了Apriori算法的一些变体。下面介绍几种比较代表性的Apriori改进算法。

2.2.3　Eclat算法

Apriori算法循环的次数与模式的最大长度是一样的。Eclat（Equivalence CLASS Transformation）算法是为了减少循环次数而设计的算法。在Eclat算法中，数据格式不再是（<事务编号，项ID集合>），而是（<项ID，事务编号集合>）。Eclat算法的数据输入格式是样本购物篮文件中的垂直格式，或者从事务数据集中发现频繁项集。在该算法中，还使用Apriori性质从k项集生成频繁k+1项集。

通过求集合的交集来生成候选项集。正如前文所述，垂直格式结构称为事务编号集合（tidset）。如果与某个项目I相关的所有事务编号都存储在一个垂直格式事务集合中，那么该项集就是特定项的事务编号集合。

通过求事务编号集合的交集来计算支持计数。给定两个tidset X和Y，X∩Y交集的支持计数是X∩Y的基数。伪代码是F←, P←{|i∈I, |t(i)|≥MIN_SUP}。

R语言实现

下面给出Eclat算法挖掘频繁模式的R语言代码。在调用该函数前，需要将f设为空，而p是频繁1项集。

这里给出一个例子的运行结果。其中，I={beer,chips,pizza,wine}。与之对应的水平和垂直格式的事务数据集如下表所示。

该信息的二进制格式为：

在调用Eclat算法之前，设置最小支持度MIN_SUP=2, F={}，则有：

算法运行过程如下图所示。经过两次迭代后，可以得到所有的频繁事物编号集合，{,,,,<{beer, chips}, 1 2>}。

可以使用R添加包arules对Eclat函数的结果进行验证。

2.2.4　FP-growth算法

FP-growth算法是在大数据集中挖掘频繁项集的高效算法。FP-growth算法与Apriori算法的最大区别在于，该算法不需要生成候选项集，而是使用模式增长策略。频繁模式（FP）树是一种数据结构。

2.2.4.1　输入数据特征和数据结构

算法采用一种垂直和水平数据集混合的数据结构，所有的事务项集存储在树结构中。该算法使用的树结构称为频繁模式树。这里，给出了该结构生成的一个例子。其中，I={A,B,C,D,E,F}，事务数据集D如下表所示。FP树的构建过程如下表所示。FP树中的每个节点表示一个项目以及从根节点到该节点的路径，即节点列表表示一个项集。这个项集以及项集的支持信息包含在每个节点中。

排序的项目顺序如下表所示。

根据这个新的降序顺序，对事务数据集进行重新记录，生成新的有序事务数据集，如下表所示：

随着将每个项集添加到FP树中，可生成最终的FP树，FP树的生成过程如下图所示。在频繁模式（FP）树生成过程中，同时计算各项的支持信息，即随着节点添加到频繁模式树的同时，到节点路径上的项目的支持计数也随之增加。

将最频繁项放置在树的顶部，这样可以使树尽可能紧凑。为了开始创建频繁模式树，首先按照支持计数降序的方式对项进行排序。其次，得到项的有序列表并删除不频繁项。然后，根据这个顺序对原始事务数据集中的每个项重新排序。

给定最小支持度MIN_SUP=3，根据这个逻辑可以对下面的项集进行处理。

下面是执行步骤4和步骤7后的结果，算法的过程非常简单和直接。

头表通常与频繁模式树结合在一起。头指针表的每个记录存储指向特定节点或项目的链接。

作为FP-growth算法的输入，频繁模式树用来发现频繁模式或频繁项集。这里的例子是以逆序或从叶子节点删除FP树的项目，因此，顺序是A, B, C, D, E。按照这种顺序，可以为每个项目创建投影频繁模式树。

2.2.4.2　FP-growth算法

这里是递归定义的伪代码，其输入值为：R←GenerateFPTree(D), P← , F←

2.2.4.3　R语言实现
FP-growth算法的主要部分的R语言实现代码如下所示。

2.2.5　基于最大频繁项集的GenMax算法

GenMax算法用来挖掘最大频繁项集（Maximal Frequent Itemset，MFI）。算法应用了最大性特性，即增加多步来检查最大频繁项集而不只是频繁项集。这部分基于Eclat算法的事物编号集合交集运算。差集用于快速频繁检验。它是两个对应项目的事物编号集合的差。

可以通过候选最大频繁项集的定义来确定它。假定最大频繁项集记为M，若X属于M，且X是新得到频繁项集Y的超集，则Y被丢弃；然而，若X是Y的子集，则将X从集合M中移除。

下面是调用GenMax算法前的伪代码，
M← ，且P←{|Xi∈D, support_count(Xi)≥MIN_SUP}
其中，D是输入事务数据集。

R语言实现

GenMax算法的主要部分的R语言代码如下所示：

2.2.6　基于频繁闭项集的Charm算法

在挖掘频繁闭项集过程中，需要对项集进行封闭检查。通过频繁闭项集，可以得到具有相同支持度的最大频繁模式。这样可以对冗余的频繁模式进行剪枝。Charm算法还利用垂直事物编号集合的交集运算来进行快速的封闭检查。
下面是调用Charm算法前的伪代码，
C← ，且P←{|Xi∈D, support_count(Xi)≥MIN_SUP}
其中，D是输入事务数据集。

R语言实现

Charm算法的主要部分的R语言实现代码如下：

2.2.7　关联规则生成算法

在根据Apriori算法生成频繁项集的过程中，计算并保存每个频繁项集的支持计数以便用于后面的关联规则挖掘过程，即关联规则挖掘。

为生成关联规则X→Y，l=X∪Y，l为某个频繁项集，需要以下两个步骤：

首先，得到l的所有非空子集。

然后，对于l的子集X，Y=l-X，规则X→Y为强关联规则，当且仅当confidence（X→Y）≥minimumconfidence。一个频繁项集的任何规则的支持计数不能小于最小支持计数。
关联规则生成算法的伪代码如下所示。

R语言实现

生成Apriori关联规则的算法的R语言代码如下所示：

为了验证上述R语言代码，可以使用Arules和Rattle添加包验证它的输出。

Arules（Hahsler et al., 2011）和Rattle添加包提供了对关联规则分析的支持。对于输出规则的可视化，可利用AruleViz。