《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树中的每个节点表示一个项目以及从根节点到该节点的路径,即节点列表表示一个项集。这个项集以及项集的支持信息包含在每个节点中。

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

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

随着将每个项集添加到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。

时间: 2024-10-02 16:39:54

《R语言数据挖掘》——2.2 购物篮分析的相关文章

《R语言数据挖掘》----导读

Preface 前 言 世界各地的统计学家和分析师正面临着处理许多复杂统计分析项目的迫切问题.由于人们对数据分析领域的兴趣日益增加,所以R语言提供了一个免费且开源的环境,非常适合学习和有效地利用现实世界中的预测建模方案.随着R语言社区的不断发展及其大量程序包的不断增加,它具备了解决众多实际问题的强大功能. R编程语言诞生已经有数十年了,它已经变得非常知名,不但被社区的科学家而且被更广泛的开发者社区所熟知.它已经成长为一个强大的工具,可以帮助开发者在执行数据相关任务时生成有效且一致的源代码.由于R

R语言数据挖掘

数据分析与决策技术丛书 R语言数据挖掘 Learning Data Mining with R [哈萨克斯坦]贝特·麦克哈贝尔(Bater Makhabel) 著 李洪成 许金炜 段力辉 译 图书在版编目(CIP)数据 R语言数据挖掘 / (哈)贝特·麦克哈贝尔(Bater Makhabel)著:李洪成,许金炜,段力辉译. -北京:机械工业出版社,2016.9 (数据分析与决策技术丛书) 书名原文:Learning Data Mining with R ISBN 978-7-111-54769-

《R语言数据挖掘》----第2章 频繁模式、关联规则和相关规则挖掘 2.1关联规则和关联模式概述

本节书摘来自华章出版社<R语言数据挖掘>一书中的第2章,第2.1节,作者[哈萨克斯坦]贝特·麦克哈贝尔(Bater Makhabel),李洪成 许金炜 段力辉 译,更多章节内容可以访问"华章计算机"公众号查看. 第2章 频繁模式.关联规则和相关规则挖掘 本章中,我们将首先学习如何用R语言挖掘频繁模式.关联规则及相关规则.然后,我们将使用基准数据评估所有这些方法以便确定频繁模式和规则的兴趣度.本章内容主要涵盖以下几个主题: 关联规则和关联模式概述 购物篮分析 混合关联规则挖掘

《R语言数据挖掘》——2.8 总结

本节书摘来自华章出版社<R语言数据挖掘>一书中的第2章,第2.8节,作者[哈萨克斯坦]贝特·麦克哈贝尔(Bater Makhabel),李洪成 许金炜 段力辉 译,更多章节内容可以访问"华章计算机"公众号查看. 2.8 总结 本章主要学习了以下内容: 购物篮分析. 作为关联规则挖掘的第一步,频繁项集是一个主要因素.除算法设计外,定义了闭项集.最大频繁项集. 作为关联规则挖掘的目标,通过支持计数.置信度等度量来挖掘关联规则.除支持计数外,使用相关公式挖掘相关规则. 频繁项集的

R语言数据挖掘第2章 频繁模式、关联规则和相关规则挖掘

第2章 频繁模式.关联规则和相关规则挖掘 本章中,我们将首先学习如何用R语言挖掘频繁模式.关联规则及相关规则.然后,我们将使用基准数据评估所有这些方法以便确定频繁模式和规则的兴趣度.本章内容主要涵盖以下几个主题: 关联规则和关联模式概述 购物篮分析 混合关联规则挖掘 序列数据挖掘 高性能算法 关联规则挖掘算法可以从多种数据类型中发现频繁项集,包括数值数据和分类数据.根据不同的适用环境,关联规则挖掘算法会略有差异,但大多算法都基于同一个基础算法,即Apriori算法.另一个基础算法称为FP-Gro

R语言数据挖掘导读

Preface 前 言 世界各地的统计学家和分析师正面临着处理许多复杂统计分析项目的迫切问题.由于人们对数据分析领域的兴趣日益增加,所以R语言提供了一个免费且开源的环境,非常适合学习和有效地利用现实世界中的预测建模方案.随着R语言社区的不断发展及其大量程序包的不断增加,它具备了解决众多实际问题的强大功能. R编程语言诞生已经有数十年了,它已经变得非常知名,不但被社区的科学家而且被更广泛的开发者社区所熟知.它已经成长为一个强大的工具,可以帮助开发者在执行数据相关任务时生成有效且一致的源代码.由于R

《R语言数据挖掘》——2.7 练习

本节书摘来自华章出版社<R语言数据挖掘>一书中的第2章,第2.7节,作者[哈萨克斯坦]贝特·麦克哈贝尔(Bater Makhabel),李洪成 许金炜 段力辉 译,更多章节内容可以访问"华章计算机"公众号查看. 2.7 练习 为加强对本章内容的掌握,这里给出一些有助于更好理解相关概念的实践问题. 编写R程序,寻找给定的样本购物篮事务文件中包含了多少唯一的项名.将每个项的名字映射为一个整数ID.找出所有的频繁闭项集.找出所有最大频繁项集和它们的支持计数.你自己将支持计数阈值设

《R语言数据挖掘》----1.13 数据降维

本节书摘来自华章出版社<R语言数据挖掘>一书中的第1章,第1.13节,作者[哈萨克斯坦]贝特·麦克哈贝尔(Bater Makhabel),李洪成 许金炜 段力辉 译,更多章节内容可以访问"华章计算机"公众号查看. 1.13 数据降维 在分析复杂的多变量数据集时,降低维度往往是必要的,因为这样的数据集总是以高维形式呈现.因此,举例来说,从大量变量来建模的问题和基于定性数据多维分析的数据挖掘任务.同样,有很多方法可以用来对定性数据进行数据降维. 降低维度的目标就是通过两个或者多

《R语言数据挖掘》----1.3 数据挖掘

本节书摘来自华章出版社<R语言数据挖掘>一书中的第1章,第1.3节,作者[哈萨克斯坦]贝特·麦克哈贝尔(Bater Makhabel),李洪成 许金炜 段力辉 译,更多章节内容可以访问"华章计算机"公众号查看. 1.3 数据挖掘 数据挖掘就是在数据中发现一个模型,它也称为探索性数据分析,即从数据中发现有用的.有效的.意想不到的且可以理解的知识.有些目标与其他科学,如统计学.人工智能.机器学习和模式识别是相同的.在大多数情况下,数据挖掘通常被视为一个算法问题.聚类.分类.关联