《R语言数据挖掘》——2.2 购物篮分析-白红宇

本节书摘来自华章出版社《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树中的每个节点表示一个项目以及从根节点到该节点的路径，即节点列表表示一个项集。这个项集以及项集的支持信息包含在每个节点中。