目录
概述
本文是对R中arules包[1]的随包文档“Introduction to arules – A computational environment for mining association rules and frequent item sets”的意译。源文档采用R Markdown撰写，并按如下流程生成本页面：
重要词语英汉对照表：
| 英文 | 汉译 |
|---|---|
| support | 支持度 |
| confidence | 置信度 |
| lift | 提升度 |
| interestingness | 兴趣度 |
| transaction | 事务 |
| item | 项 |
| superset | 超集 |
| subset | 子集 |
| itemset／item set | 项集 |
| association | 关联信息 |
| association rule | 关联规则 |
| frequent itemset | 频繁项集 |
| maximal frequent itemset | 最大频繁项集 |
| frequent closed itemset | 频繁闭项集 |
| sample with replacement | 放回抽样 |
基础知识
基本定义
- $\mathcal I=\{i_1, i_2,\ldots, i_n\}$：$n$个二值属性项（item）构成的集合。
- $\mathcal D=\{t_1,t_2,\ldots,t_m\}$：$m$个事务构成的集合，称为数据库（database），每个事务拥有唯一的ID并包含$\mathcal I$的一个子集。
- $X\rightarrow Y$：表示规则（rule），其中$X,Y\subseteq I$并且$X\cap Y=\emptyset$，项集（itemset）$X$和$Y$分别称为规则的前提（antecedent）和结论（consequent），或者分别称为左手边（LHS，left-hand-side）和右手边（RHS，right-hand-side）。
- $supp(X)$：项集$X$的支持度，$conf(X\rightarrow Y)$：规则$X\rightarrow Y$的置信度1。
频繁项集与关联规则的挖掘是一种流行的并经过深入研究的方法，用于发现大规模数据库中变量之间的有趣关系。本文展示了R的arules包，它提供了一种基本工具，用于创建和处理输入数据集，分析输出数据集和输出规则。该包还提供了调用两种快速挖掘算法的接口，它们是Apriori和Eclat算法的流行的C语言版本，由Christian Borgelt实现。这些算法可用于挖掘频繁项集、最大频繁项集、闭频繁项集以及关联规则。
Piatetsky-Shapiro[2]利用不同兴趣度度量，分析和表示从数据库发现的强规则。Agrawal等[3]在强规则的基础上，提出了从事务数据中挖掘关联规则的问题。以超市为例，交易数据集中的规则$\{milk, bread\}\rightarrow\{butter\}$表示：若顾客购买了$milk$和$bread$，也会购买$butter$。
为了从包含所有可能规则的集合中抽取出感兴趣的规则，可以利用基于各种显著性和兴趣度的度量作为约束条件。最著名约束条件就是支持度和置信度的最小阈值。
发现频繁项集（frequent itemset）可视为非监督学习问题的一种简化形式，称之为模型发现（mode finding）或块搜索（bump hunting）[4]。在这些问题中，每个项视为一个变量。它们的目标是找到模型值（prototype value），使得概率密度估值在取这些值时足够大。然而，对于变量众多的实际应用，概率估计不一定可靠，且计算太复杂。这就是在实际应用中用频繁项集代替概率估计的原因。置信度可解释为概率$P(Y|X)$的一种估计，它表示事务包含规则的LHS时，从事务中找到规则的RHS的概率[5]。
关联规则（association rule）需要同时满足最小支持度和最小置信度的约束。在支持度的中间值到最低值范围内，通常可从数据库找出大量的频繁项集。支持度的定义保证了频繁项集的所有子集也必是频繁的。因此，只挖掘所有的最大频繁项集（maximal frequent itemset）就够了，这些频繁项集不是其它任何频繁项集的子集[6]。另一种减少挖掘项集数目的方法是只挖掘频繁闭项集（frequent closed itemset）2。若包含项集的所有事务都不包含与该项集相适的超集，则称该项集是闭的。频繁闭项集是最大频繁项集的一个超集（superset）。最大频繁项集的优势不仅在于它可生成所有的频繁项集，而且它们还包含了所有频繁项集的支持度信息，这些信息在数据挖掘过程完成后，对计算额外的兴趣度量（interest measure）起着至关重要的作用（例如，计算所得项集生成的规则的置信度、全置信度[7]）。
当挖掘到过多满足支持度和置信度约束的关联规则时，解决该问题切实可行的方法是利用额外的兴趣度量，进一步过滤或排列这些规则。基于此的一个流行度量是提升度（lift）[8]。规则的提升度定义为
\begin{equation} lift(X\to Y)={supp(X\cup Y)\over supp(X)supp(Y)}， \end{equation}
它可认为是整条规则的支持度与LHS和RHS支持度相互独立时规则支持度之间的偏差。更大的提升度意味着更强的关联性。
近十年，关于解决频繁项集问题的算法研究已经十分丰富。Goethals等对比了目前最快的算法[9]。这些算法包括Apriori和Eclat的实现，Borgelt将它们接入到了arules环境[10]。这两种算法采用了很不相同的挖掘策略。Agrawal等开发的Apriori是一种分级的广度优先算法，它对事务计数；相比之下，Eclat利用等价类（equivalence classes）、深度优先搜索和交集运算代替计数。它们可用于挖掘频繁项集、最大频繁项集和闭频繁项集。Apriori还额外实现了生成关联规则。
本文描述的arules是R的扩展包，它提供了一种基础架构，创建和操作挖掘算法的输入数据集，分析输出项集和输出规则。该包常用于处理很大的规则和项集的集合，因此采用稀疏矩阵使内存占用最小化。该包的架构也非常便于扩展，包括接入新的算法和加入新的兴趣度量类型和关联规则。
数据结构
在R中，为了用户表示和操作关联规则挖掘算法的输入输出数据，需要设计良好的（数据）结构，高效处理大规模的稀疏二值数据（sparse binary data）。arules中的S4类的（数据）结构实现如下：
arules为输入数据提供了transactions和tidLists类（事务ID的列表，另一种表示事务数据的方法）。挖掘算法的输出包含itemsets和rules类，分别表示项集和规则的集合。这两个类直接扩展通用虚类associations，该虚类提供了通用接口。在这种结构下，通过加入扩展associations的新类，很容易加入新的关联规则类型。associations和transactions中的项由itemMatrix类实现，该类提供了访问ngCMatrix的接口，它是R的Matrix包中的稀疏矩阵。
ASparameter和AScontrol两个类控制挖掘算法的表现。由于每个算法能够采用与算法相关的额外参数，我们为每个接入的算法实现了自己的控制类集。我们用AP前缀表示Apriori算法，用EC前缀表示Eclat算法。按这种方式，接入新算法时易于扩展控制类。
项集矩阵
根据关联规则挖掘问题的描述，我们发现事务数据库和关联规则集的共同之处在于它们都包含项集以及附加信息。例如：数据库中的一条事务包含一个事务ID和一个项集；挖出的关联规则集中的一条规则包含两个项集，一个表示LHS，另一个表示RHS，以及附加的品质信息（比如各种兴趣度量的值）。
二值索引矩阵可表示事务数据库中项集的集合以及关联规则集，矩阵的列对应着项，矩阵的行对应着项集。矩阵的元素表示项在某个项集中出现（1）还是未出现（0）。二值索引矩阵的示例如下：
注意，我们可能需要存储的集合包含相同元素（相同的行）的项集，也就是项集的项完全相同。 这是必要的，因为事务数据库可以包含具有相同项的不同事务。由于每个事务也包含唯一的事务ID，这样的数据库仍是事务的集合。
与所有可用项的数量比起来，典型的频繁项集或典型的事务（比如超市的事务）只使用了少部分项，因此二值索引矩阵通常非常稀疏，占用了许多项和大量行。这样的数据，自然适合采用稀疏矩阵的格式表示。我们选择Matrix包中定义的ngCMatrix类来实现。ngCMatrix是紧凑的稀疏逻辑列导向的矩阵，该矩阵包含了TRUE行的索引，以及矩阵每列元素初始索引的“指针”。尽管ngCMatrix沿列方向，使用行导向的索引矩阵更方便。这使得最重要的操作——从数据集中抽取用于挖掘的事务子集——更加便捷高效。因此，我们实现了itemMatrix类，它提供了到行导向的转置索引矩阵ngCMatrix的接口。在稀疏表示中，上例项集的集合需要保存的信息包括：一个非0元素的索引向量（按行从第1行开始）1, 2, 2, 4, 1, 2, 3, 3，以及每行在索引向量起始位置的“指针”1, 3, 5, 8。开始的两个“指针”1, 3表明矩阵第1行包括索引向量的第1和第2个元素1, 3，即矩阵(1, 1)和(1, 2)两个元素非0，也就是第1个项集包含$milk$和$bread$两项。这两个向量存储在ngCMatrix中。注意，ngCMatrix的索引从0而非1开始，因此实际存储的向量为0, 1, 1, 3, 0, 1, 2, 2和0, 2, 4, 73。然而，ngCMatrix类的数据结构并非是为arules的终端用户直接访问而设计的。其接口能在不知道数据内部表示如何工作的情况下调用。然而，若有必要，开发者可通过给arules增加功能直接访问ngCMatrix（比如，开发新的关联规则类型或兴趣度量，或者高效计算用于聚类的项集的距离矩阵）。在这种情况下，这通过as()，借助itemMatrix到ngCMatrix的类型转换机制，能够访问ngCMatrix。
除稀疏矩阵外，itemMatrix还存储项标签（比如项的名称），以及处理项标签和索引矩阵相应列号之间的必要映射。作为可选功能，itemMatrix还能存储项的附加信息。例如，可以存储超市类别层次结构，这使得能够
只选择包含特定类别（例如，所有乳制品）的项的事务（也可以是规则或项集）进行分析。
itemMatrix的基本操作包括：
dim()和[：第1个元素对应项集或事务，第2个元素对应项（列）。例如，在变量x的事务数据集上，子集选择x[1:10, 16:20]抽取出一个包含前10条事务和16到20项的矩阵。length()：获得itemMatrix的项集数量（行数目），等价于dim()返回的第1个元素。duplicated()：找出相同的项集。unique()：移除重复的项集。match()：找出两个项集的集合之间匹配的元素。c()：当几个itemMatrix对象兼容时（列数相同且项的顺序相同），按行相继连接。recode()：参与c()操作的两个对象，若包含相同的项（项标签）但排列顺序不同，或其中一个存在缺失项，那么可用recode()重排项和插入列，使二者兼容。size()：获取itemMatrix中实际存储的项集包含项的数目，它返回一个向量，其每个元素表示集合中项（1）的数目（矩阵的行和）。利用该信息可过滤掉那些太长或太短的异常事务。itemFrequency()：计算itemMatrix中每个项出现的频率，也就是二值矩阵列元素之和。该元素可用于计算兴趣度量，还可用于itemFrequencyPlot()绘制项数目频率或支持度的条形图。通过该图，可以快速预览项集集合和展示按出现频率标准哪些是最重要的项。as()：进行矩阵（matrix）和列表(list)元素之间的类型转换，其中名字和维名字（dimname）用作项标签。从itemMatrix到list的转换有两种可能：通常采用as()进行转换，得到字符串向量的列表，其每个元素包含itemMatrix中相应行的项标签，实际转换通过调用默认参数的LIST()（参数decode设为TRUE）完成；若反过来，调用LIST()时的参数decode设为FALSE，将返回项的列号构成的整数向量列表，而非项标签。decode()可用于将列号解码为项标签。image()：可用于生成itemMatrix的等级图，这对快速可视化探测有用。对事务数据集，这样的图对检查数据集是否包含结构性的变化很有用（比如，没提供项、观察期内脱销），或者找出异常事务（例如，包含几乎所有项的事务可能表明录入有问题）。准备数据时，发现数据中的那些问题非常有用。
事务数据
市场购物篮分析是关联规则的主要应用，它需要对大规模的事务数据集进行挖掘。在这种情况下，每条事务表示一次光顾购买商品的记录[11]。事务数据通常由销售点的扫码器纪录，常常由如下形式元素构成：
\[ <transaction\;ID,\;\;item\; ID,\ldots>。 \]
所有具有相同事务ID的元素构成一条事务，它包括元素中由事务ID确定的所有项。用省略号标记的地方可能会提供附加信息，例如：可能通过超市的积分程序提供顾客ID，还可能提供更多信息，包括：事务相关的（交易时间、地点等），商品相关的（类别、价格等）或顾客相关的（年龄、性别等社会背景资料）。
对数据挖掘，事务数据首先被转换为二值购买索引矩阵，其列对应不同商品（项），其行对应不同事务。矩阵元素用于表达某个事务中出现（1）或缺失（0）了某项。这种格式通常称之为水平数据库布局。此外，事务数据可用垂直数据库布局，按事务ID列表的形式表示[12]。在这种格式下，对于每项，保存了那些包含该项的事务的ID构成的列表。前例的水平和垂直风格的数据库分别如下左右所示：
采用何种布局的数据库由算法确定。在arules中，两种布局都由transactions和tidLists类实现了。类似于transactions，tidLists类也采用了稀疏表示以高效存储其列表。transactions和tidLists类的对象之间可利用类型转换直接相互转换。
transactions类直接扩展了itemMatrix，并继承了其基本功能（比如，子集抽选、获得项集大小、绘制项频率）。此外，transactions拥有一个data.frame格式的槽（slot），用以存储每条事务的更多信息。槽可以容纳和已保存事务数量长度相同的任意命名的向量。在arules中，该槽目前用于存储事务ID，然而它也可用于存储用户ID、总收入或利润，或者每条事务的其它信息。利用这些信息，可以抽取出事务的子集（比如，特定用户的事务或者超出规定利润水平的事务）。
通过类型转换，易于从matrix和list创建transactions类的对象。若这些数据结构有名字或维名字可用，它们分别被用于项标签和事务ID。read.transactions()函数被用于从文件导入数据。该函数读入的文件具有上例所示的结构，它也是一种很常用的格式，每行记录一条事务，项被预定义的字符分割。最后，inspect()可用于审查事务（比如，通过抽取子集得到的有趣事务）。
Piatetsky-Shapiro[2]和Srikant[13]等人提出了关联规则挖掘的另一个重要应用，发现类别价值和量化属性之间的有趣关系。为了挖掘关联规则，非二值属性必须映射为二值属性。最直接的映射方法是创建类别，将量化属性转为$k$个有序属性（比如，收入属性可转换为具有低中高三个类别的有序属性）。然后，在第二步中，每个拥有$k$个类别的类别属性用$k$个二值伪属性表示，这些伪属性相当于挖掘中使用的项4。
R表示拥有类别属性和量化属性数据的典型方法是采用data.frame：
- 第一步：领域专家必须为所有的量化属性创建有意义的类别。arules中的
discretize()等函数对该任务提供了支持，该函数实现了按相同区间长度、相同频率，以及基于聚类和用户自定义区间的离散化。在离散化后，data.frame的所有列须是逻辑或因子类型。 - 第二步：arules包通过
data.frame到transactions的类型转换，自动生成二值伪项。在该过程中，原始属性名和类别作为附加项信息被保留。默认情况下缺失值不带信息，因此所有相应的伪项都被置为0。若实际上，当特定属性的值缺失提供了信息时（比如，采访中受访者拒绝回答某个问题），领域专家要为该属性创建一个表示缺失值的类别，该类别将以伪项的形式包含在事务中。
关联信息
arules挖掘事务数据得到的是关联信息（association）。从概念上说，关联信息是描述某些项（例如，作为项集或作为规则）之间关系的对象构成的集合，它们为不同的质量度量赋了值。这些度量可以作为显著性度量（比如，支持度），或者感兴趣度量（比如，置信度、提升度），或者其它度量（比如，关联信息涉及的收入）。arules中的所有关联信息类型都拥有如下方法提供的功能：
summary()：展示集合的概述；inspect()：展示单独的关联信息；length()：获得集合中元素的个数；items()：获得每条关联信息包含的项的集合（例如，每条规则的LHS和RHS中项的并集）；sort()：按不同质量的度量对集合排序；subset()：抽取子集；union(), intersect(), setequal()：集合操作；match()：匹配两个集合的元素；write()：将关联信息以人可读的格式写入磁盘；save(), load()：base包提供提供的以紧凑形式保存、加载关联信息；write.pmml(), read.pmml()：通过pmml包，按PMML（predictive model markup language）格式写入、读取关联信息。
arules包目前实现的关联信息是项集的集合（例如，用于频繁项集的项集的最大或闭子集），以及规则的集合（例如，关联规则）。itemsets和rules两种类，直接扩展了associations虚类，并提供了上述功能。
itemsets类包含一个用于将项存储为二值矩阵的itemMatrix对象，其中矩阵的每行表示一个项集。此外，它还可以将事务ID列表按tidLists类的对象形式包含其中。值得注意，当表示事务时，tidLists为每个项存储一个事务列表，此处为每个项集存储一个该项集出现过的事务ID的列表5。目前只有eclat()返回该列表。
rules类由两个itemMatrix对象构成，分别表示规则的LHS和RHS。
关联信息中的项和质量度量，能以一种安全的方式使用items, lhs, rhs, quality的访问和替换方法，进行访问和操作。此外，关联信息类拥有内建的有效性校验机制，这保证了所有的元素拥有兼容的维。
为已有的关联信息加入新的质量度量很简单。由于quality槽有一个data.frame，可以加入具有新的质量度量的附加列。然后，这些新的度量可通过sort()和subset()对关联信息排序或筛选。为arules加入新的关联信息类型也同样直接。为了做到这些，开发者须创建新的类以扩展associations虚类，并实现上述通用功能。
算法接口
在arules包中，我们接入了Christian Borgelt提供的Apriori和Eclat的免费的参考实现。这些代码可以通过R的apriori()和eclat()直接调用，并且数据对象可以在R和C代码之间直接传递，而不需写入外部文件。这些实现可挖掘频繁项集、以及闭的和最大的频繁项集。此外，apriori()还能挖掘关联规则。
输入apriori()和eclat()函数的数据必须是transactions或者能被转换成transactions的数据（比如，matrix和list）。算法的参数分为两组，用parameter和control参数表示。挖掘参数（parameter）改变挖掘到的项集或规则的特征（比如，最小支持度）；控制参数（control）影响挖掘算法的性能（比如，是否按频率对项进行初始排序）。apriori()函数的这些参数必须是APparameter和APcontrol类的实例；eclat()函数的参数必须是ECparameter和ECcontrol类的实例。另外，那些可被转换为这些类的数据（比如，NULL表示默认参数，与槽名称一致的列表改变参数默认值），也能作为参数。在这些类中，每个槽确定一个不同的参数与取值。参数的默认值与独立C程序的默认值相同，除非要求规则支持度的标准定义用于指定的最小支持度（Borgelt将规则前提的支持度定义为规则的支持度）。
Christian Borgelt实现的显现特征（appearance feature）也能用于apriori()[14]。apriori()函数的appearance参数可指定哪些项必须或不必出现在项集或规则中。关于该特征的更多信息，我们可参考Apriori手册[14]。
apriori()和eclat()函数的输出是一个associations扩展类的对象，它包含挖掘到的关联信息集，并且可利用针对这些类的函数对它作进一步分析。
许多不同的算法采用索引矩阵或事务ID列表的表示形式作为输入，解决频繁项集和闭的频繁项集问题。每个算法拥有专门的能力，能在超大规模数据库中发挥重要作用，Goethals等[15]对这类算法，比如kDCI、LCM、FP-Growth和Patricia，进行了讨论。大多数算法的源代码都可通过互联网获取，并且当需要某个算法时，接入到arules也很简单，必要的步骤包括：
- 为算法添加接口代码，推荐直接调用原生实现语言（而非利用文件通信），并且添加R函数调用该接口；
- 实现对
ASparameter和AScontrol的扩展。
辅助函数
arules实现了几个有用的函数用以支持度计算、规则推导，采样等。接下来我们将讨论其中的几个函数。
支持度的计算
在挖掘数据库的过程中，通常在最小支持度约束条件下计算项集的支持度。在此过程，计算了所有的频繁项集外加一些非频繁候选项集（或者支持度通过其它方式确定）。特别是当数据库项很多且最小支持度值很小时，该过程在最坏的情况下可能非常耗时，频繁项集的数目按项的数目以指数形式增长。
当仅需要一个或少许项集的支持度信息时，我们可能不想挖掘数据库得到所有频繁项集。我们事先也不知道最小支持度设为多高（或多低），仍需得到了问题中（所有）项集的支持度信息。针对该问题，arules包含的support()能确定给定项集集合（以itemMatrix形式）的支持度。
为了计数，我们使用一颗前缀树（prefix tree）[16]组织计数器，所使用的前缀树类似Borgelt描述的项集树[17]。尽管这样，我们不会按层生成树，我们会首先生成一颗只包含必要节点的前缀树，这些节点拥有所有需要计数的项集的计数器。只采用该树的节点，我们为每条事务递归的对项集计数。完成计数后，每个项集的支持度包含在前缀和项集相同的节点中[18]。Hahsler等描述了具体过程[18]。
除了能在不挖掘所有频繁项集时确定少数项集的支持度，support()也能用于找出支持度很低的非频繁项集，支持度过低会导致组合爆炸使得挖掘不可行。
规则的推导
为了方便，我们将长度为$l$的项集的集合记为$\mathcal X=\{X_1, X_2,\ldots,X_l\}$。类似地，我们将规则的集合记为$\mathcal R$。部分关联规则挖掘问题就是从频繁项集$\mathcal X$中生成（或推导）出规则的集合$\mathcal R$。arules中实现的Apriori算法已包含了规则生成引擎，并默认返回$X\to Y$形式的关联规则集合，该关联规则满足最小支持度和最小置信度条件。根据Agrawal等的定义[3]，$Y$被限制为单个项。
某些情况下，有必要将挖掘项集和从项集生成规则分开。例如，用户可能只对所有频繁项集的一个子集生成的规则感兴趣。Apriori通过重用挖掘频繁项集时建立的数据结构，高效的生成规则。然而，如果Apriori只用于返回项集，或者采用Eclat等其它算法挖掘项集，规则推导所需的数据结构不再能用于计算规则的置信度。
如果规则需从项集的任意集合推导，计算置信度所需的支持度值通常缺失。例如，若所有可用的信息是一个包含5个项的项集，并且我们期望推导出规则，我们需要项集的支持度（我们可能知道），也需要知道所有长度为4的所有子集的支持度。缺失的支持度信息必须从数据库计算。最终，为了高效的从项集给定的集合推导规则，我们还须将支持度值存储在合适的数据结构中，在计算规则置信度时可对该结构高效的查找。
给定置信度，arules中的ruleInduction()函数采用一颗前缀树从项集$\mathcal X$的任意集合按如下方式推导规则：
- 计算每个项集$X\in \mathcal X$及子集$\{X\not \{x\}: x\in X \}$的支持度值。这些值用于规则生成，它们通过对数据库单轮扫描得到，存储在恰当的数据结构中。
- 利用上一步创建的数据结构中的支持度信息，只选择性的生成满足条件的规则，为项集$\mathcal X$产生集合$\mathcal R$。
前文介绍的方法完成了高效的支持度计算。经过计算，所有必要的支持度包含在前缀树中。我们能很容易的取回所需的支持度值。Hahsler等描述了具体过程[18]。
事务的抽样
从大规模数据库中抽取用于挖掘的样本是一种强大的技术，它在原始数据库无法放入主存（main memory）而样本集可放入时尤其有用。然而，就算数据库能放入主存，抽样能在只牺牲很少精度时极大的加速挖掘。
Mannila等[19]提出了用于关联规则挖掘的放回抽样方法，并对抽样导致的误差进行了量化估计。基于二项分布（包含样本中给定项集的事务的数量）的Chernov界，作者认为即使比较小的样本集在理论上也能很好的估计支持度。在此理论基础上，Zaki等[6]认为对于持度为$\tau =supp(X)$的项集$X$，在给定置信水平$1-c$下可接受的支持度相对误差为$\epsilon$时，抽样数据集所需的大小$n$可以计算，
\begin{equation} n={-2\ln(c)\over \tau\epsilon^2}。 \label{eq:sample-sizez-evaluation} \end{equation}
对于每个项集，恰当的方法是依据其支持度确定不同的样本集大小。 抽样数据集的大小由支持度确定。作为启示6，作者建议将用户设定的最小支持度阈值作为$\tau$。这意味着对于接近最小支持度的项集，满足给定的误差和置信水平，而更频繁项集的错误率会更低。然而，在该启发式方法下，小于最小支持度的项集的错误率，在给定的置信水平会超过$\epsilon$，因此一些非频繁项集可能作为频繁项集出现在样本中。
Zaki等[20]还通过实践对几个数据集的抽样进行了评估，他们认为抽样不仅显著加速了挖掘，误差也明显低于Chernov界给出的那些误差，因此小于公式\eqref{eq:sample-sizez-evaluation}给定大小的样本集通常也够用。
另一种获得关联规则挖掘所需样本集大小的方法是逐步抽样（progressive sampling）[21]。该方法从一个小的样本集开始，使样本集逐步增大，直到模型精度不再明显提高。Parthasarathy通过度量两个项集的集合之间相似性，为模型精度提升定义了一个代理。基本思想是：由于更大的样本集会产生更高精度的结果，若精度提升高，并且精度按精度提升递减的方式增加，那么两个连续样本集的关联信息的集合的相似度就低。因此，若连续样本集之间的相似性到达了一个稳定区域，样本集大小的增加就可以停止了。
Toivonen[22]提出了运用采样，降低无法放入主存的大规模数据库所需的I/O开销。 其基本思想是：利用数据库的随机样本集，按低于集合最小支持度的一个支持度阈值，挖掘频繁项集。然后，在整个数据库计算这些项集的支持度，并且丢弃非频繁的项集。若挖掘样本集的支持度阈值选取得足够低，遍历一轮这个大数据库，几乎可得所有的频繁项集和它们的支持度。
在arules中，sample()实现抽样，它提供了R标准抽样函数的所有功能（比如，放回、非放回和按概率权值的抽样）。
事务的伪造
伪造的数据可用于估计和对比不同的挖掘算法，以及研究兴趣度度量的表现。
arules中的random.transactions()函数可用于创建伪造的事务数据。目前有两种可行方法：
子集、超集、最大集与闭集
对某些计算，有必要找出项集集合中特定项集的所有子集或超集。该功能通过is.subset()和is.superset()实现。例如，is.subset(x, y, proper = TRUE)从y中找出x中项集的所有合适的子集。输出是行length(x)列length(y)的逻辑矩阵。每个逻辑行向量表示y中哪些元素是x中相应元素的子集。如果忽略参数y，返回集合x中的子集或超集结构。
类似的方法，is.maximal()和is.closed()，可用于从集合中找出所有的最大项集和闭项集。若集合没有项集合适的超级，那么项集在集合中是最大的[25]。若项集是它自身的闭，那么项集是闭的（也就是，对于项集不存在同样支持度的超级）[26]。
需要注意，当集合包含很多项集时，这些方法可能很慢并且内存消耗高。
其它的兴趣度量
arules提供的interestMeasure()可计算项集和规则的各种各样的兴趣度量。为了加速计算，我们尽量重用项集集合和规则集提供的质量信息（比如，支持度、置信度、提升度）。只在必要时，才从挖掘关联信息的事务中获取缺失信息。
例如，项集可用的度量包括：
对于规则，如下度量可行：
- 卡方度量（chi square measure）[28]；
- 确信度（conviction）[8]；
- 置信度（confidence）；
- 置信度差（DOC，difference of confidence）[29]；
- 超提升度和超置信度（hyper-lift and hyper-confidence）[30]；
- 杠杆作用（leverage）[2]；
- 改进度（improvement）[31]；
- 支持度（support）；
- 其它度量，包括余弦（cosine）、基尼系数（gini index）、$\phi$系数（$\phi$-coefficient）、奇异率（odds ratio）等[32]。
事务和关联的聚类
为了实现基于距离的聚类，arules提供了dissimilarity()，它能用于计算事务和关联信息（也就是，项集和规则）之间的相异度和交叉相异度（cross-dissimilarity）[33]。目前，可用的二值数据的标准度量包括：Jaccard系数、简单的匹配系数以及骰子系数。此外，事务之间的相异度可基于项之间的亲和度（affinity）计算[34]。
dissimilarity()的结果要么是dist对象——它可以直接用于R中的大多数聚类算法（比如，用于层次聚类的hclust），要么是ar_cross_dissimilarity类的对象。
由于事务和关联信息的数量通常太大，而无法高效的计算相异度矩阵和使用聚类算法。sample()可用于只在事务（关联信息）的子集上聚类。为了将余下的事务（关联信息）分配到类中，predict()实现了用于预测新数据成员关系的最近邻方法[35]。
一个简单的例子可从Hahsler等人的文献中找到[35]。
应用示例
例一：事务数据集的准备和分析
通过本例，我们展示在关联信息挖掘之前如何分析和处理数据集。发现数据集中存在的问题至关重要，这些问题可能导致挖掘到的关联信息无用，或者至少会比在恰当准备的数据集上，挖掘到更差的关联信息。作为例子，我们看看arules包中的Epub事务数据集。该数据集包含了2003年1月到2008年12月间，维也纳金融大学电子出版平台文档的下载信息。
首先，我们加载arules包和数据集：
library("arules")## Loading required package: Matrix
## Loading required package: methods
##
## Attaching package: 'arules'
##
## The following objects are masked from 'package:base':
##
## %in%, writedata("Epub")
Epub## transactions in sparse format with
## 15729 transactions (rows) and
## 936 items (columns)我们看到该数据集由15729条事务构成，它用15729个行和936个表示项的列的稀疏矩阵表示。接下来，我们利用summary()获得关于数据集的更多信息：
summary(Epub)## transactions as itemMatrix in sparse format with
## 15729 rows (elements/itemsets/transactions) and
## 936 columns (items) and a density of 0.001758755
##
## most frequent items:
## doc_11d doc_813 doc_4c6 doc_955 doc_698 (Other)
## 356 329 288 282 245 24393
##
## element (itemset/transaction) length distribution:
## sizes
## 1 2 3 4 5 6 7 8 9 10 11 12
## 11615 2189 854 409 198 121 93 50 42 34 26 12
## 13 14 15 16 17 18 19 20 21 22 23 24
## 10 10 6 8 6 5 8 2 2 3 2 3
## 25 26 27 28 30 34 36 38 41 43 52 58
## 4 5 1 1 1 2 1 2 1 1 1 1
##
## Min. 1st Qu. Median Mean 3rd Qu. Max.
## 1.000 1.000 1.000 1.646 2.000 58.000
##
## includes extended item information - examples:
## labels
## 1 doc_11d
## 2 doc_13d
## 3 doc_14c
##
## includes extended transaction information - examples:
## transactionID TimeStamp
## 10792 session_4795 2003-01-02 09:59:00
## 10793 session_4797 2003-01-02 20:46:01
## 10794 session_479a 2003-01-02 23:50:38summary()展示了数据集中最频繁的项、事务长度分布信息，以及数据集中包含的一些扩展的事务信息。我们看到数据集包含事务ID以及附带的时间戳（采用POSIXct类的格式），这些额外的信息可用于分析数据集：
year <- strftime(as.POSIXlt(transactionInfo(Epub)[["TimeStamp"]]), "%Y")
table(year)## year
## 2003 2004 2005 2006 2007 2008 2009
## 986 1376 1610 3010 4052 4692 3对2003年，数据集中的第一年，我们拥有986条事务。我们能够选择相应的事务，并且通过等级图探查其结构：
Epub2003 <- Epub[year == "2003"]
length(Epub2003)## [1] 986image(Epub2003)
该图是二值索引矩阵的直接可视化，其中黑点表示矩阵中的1。从图中我们可看出数据集中的项不是均匀分布的。实际上，靠近右边的大部分白色区域表示在2003年初只有很少的项可用（不足50）；然后这一年中，加入了更多的项，直到项的数目接近300。从图还我们还可知数据集中有些事务包含非常多的项（更稠密的水平线）。这些事务需要进一步考察，因为它们可能源于数据收集的问题（比如，网络爬虫从出版网站下载了很多文档）。我们可以利用size()查找出很长的事务，并筛选出很长的事务（包含20个以上的项）：
transactionInfo(Epub2003[size(Epub2003) > 20])## transactionID TimeStamp
## 11092 session_56e2 2003-04-30 01:30:38
## 11371 session_6308 2003-08-18 06:16:12我们发现了3条很长的事务，并打印了相应的事务信息。当然，按相似的方式，size()可用于移除长的或短的事务。inspect()可用于检测事务。因为上面确定的事务会导致打印结果很长，我们可以检测2003年子集的前5条事务：
inspect(Epub2003[1:5])## items transactionID TimeStamp
## 1 {doc_154} session_4795 2003-01-02 09:59:00
## 2 {doc_3d6} session_4797 2003-01-02 20:46:01
## 3 {doc_16f} session_479a 2003-01-02 23:50:38
## 4 {doc_11d,
## doc_1a7,
## doc_f4} session_47b7 2003-01-03 07:55:50
## 5 {doc_83} session_47bb 2003-01-03 10:27:44多数事务包含一项。仅有第4条事务包含3项。为了进一步探测，事务可转换为列表：
as(Epub2003[1:5], "list")## $session_4795
## [1] "doc_154"
##
## $session_4797
## [1] "doc_3d6"
##
## $session_479a
## [1] "doc_16f"
##
## $session_47b7
## [1] "doc_11d" "doc_1a7" "doc_f4"
##
## $session_47bb
## [1] "doc_83"最后，按水平布局的事务数据，能被转换为垂直布局的事务ID列表：
EpubTidLists <- as(Epub, "tidLists")
EpubTidLists## tidLists in sparse format with
## 936 items/itemsets (rows) and
## 15729 transactions (columns)由于性能的原因，事务ID列表也存储在稀疏矩阵中。为了获得列表，可采用到列表的类型转换：
as(EpubTidLists[1:3], "list")## $doc_11d
## [1] "session_47b7" "session_47c2" "session_47d8"
## [4] "session_4855" "session_488d" "session_4898"
## [7] "session_489b" "session_489c" "session_48a1"
## [10] "session_4897" "session_48a0" "session_489d"
## [13] "session_48a5" "session_489a" "session_4896"
## [16] "session_48aa" "session_48d0" "session_49de"
## [19] "session_4b35" "session_4bac" "session_4c54"
## [22] "session_4c9a" "session_4d8c" "session_4de5"
## [25] "session_4e89" "session_5071" "session_5134"
## [28] "session_51e6" "session_5227" "session_522a"
## [31] "session_5265" "session_52e0" "session_52ea"
## [34] "session_53e1" "session_5522" "session_558a"
## [37] "session_558b" "session_5714" "session_5739"
## [40] "session_57c5" "session_5813" "session_5861"
## [43] "session_wu48452" "session_5955" "session_595a"
## [46] "session_5aaa" "session_5acd" "session_5b5f"
## [49] "session_5bfc" "session_5f3d" "session_5f42"
## [52] "session_5f69" "session_5fcf" "session_6044"
## [55] "session_6053" "session_6081" "session_61b5"
## [58] "session_635b" "session_64b4" "session_64e4"
## [61] "session_65d2" "session_67d1" "session_6824"
## [64] "session_68c4" "session_68f8" "session_6b2c"
## [67] "session_6c95" "session_6e19" "session_6eab"
## [70] "session_6ff8" "session_718e" "session_71c1"
## [73] "session_72d6" "session_7303" "session_73d0"
## [76] "session_782d" "session_7856" "session_7864"
## [79] "session_7a9b" "session_7b24" "session_7bf9"
## [82] "session_7cf2" "session_7d5d" "session_7dae"
## [85] "session_819b" "session_8329" "session_834d"
## [88] "session_84d7" "session_85b0" "session_861b"
## [91] "session_867f" "session_8688" "session_86bb"
## [94] "session_86ee" "session_8730" "session_8764"
## [97] "session_87a9" "session_880a" "session_8853"
## [100] "session_88b0" "session_8986" "session_8a08"
## [103] "session_8a73" "session_8a87" "session_8aad"
## [106] "session_8ae2" "session_8db4" "session_8e1f"
## [109] "session_wu53a42" "session_8fad" "session_8fd3"
## [112] "session_9083" "session_90d8" "session_9128"
## [115] "session_9145" "session_916e" "session_9170"
## [118] "session_919e" "session_91df" "session_9226"
## [121] "session_9333" "session_9376" "session_937e"
## [124] "session_94d5" "session_9539" "session_9678"
## [127] "session_96a0" "session_9745" "session_97b3"
## [130] "session_985b" "session_9873" "session_9881"
## [133] "session_9994" "session_9a20" "session_9a2f"
## [136] "session_wu54edf" "session_9af9" "session_9b69"
## [139] "session_9ba4" "session_9c27" "session_9c99"
## [142] "session_9ce8" "session_9de3" "session_9e8a"
## [145] "session_9ebc" "session_a051" "session_a16e"
## [148] "session_a19f" "session_a229" "session_a24a"
## [151] "session_a328" "session_a340" "session_a3ab"
## [154] "session_a3ee" "session_a43a" "session_a4b2"
## [157] "session_a515" "session_a528" "session_a555"
## [160] "session_a5bb" "session_a62d" "session_a77a"
## [163] "session_ab9c" "session_abe9" "session_ac0e"
## [166] "session_ad30" "session_adc9" "session_af06"
## [169] "session_af4a" "session_af8d" "session_b0b7"
## [172] "session_b391" "session_b6d3" "session_b807"
## [175] "session_b8c7" "session_b91f" "session_bb0b"
## [178] "session_bb8a" "session_bc3d" "session_bc40"
## [181] "session_bceb" "session_bea7" "session_bf9f"
## [184] "session_c359" "session_c3c2" "session_c442"
## [187] "session_c62d" "session_c6ba" "session_c936"
## [190] "session_ca81" "session_cad3" "session_cbd4"
## [193] "session_cbe1" "session_cd63" "session_d14f"
## [196] "session_d370" "session_d69f" "session_d815"
## [199] "session_d82e" "session_d849" "session_d8b5"
## [202] "session_da68" "session_db51" "session_db75"
## [205] "session_dbcd" "session_dde2" "session_deac"
## [208] "session_dfb7" "session_dfe9" "session_e00a"
## [211] "session_e2ad" "session_e3c7" "session_e7d2"
## [214] "session_e7e5" "session_e7f2" "session_ea38"
## [217] "session_edbc" "session_edf9" "session_edfc"
## [220] "session_f0be" "session_f2d9" "session_f2fe"
## [223] "session_f39b" "session_f5e9" "session_f650"
## [226] "session_f853" "session_f989" "session_fab1"
## [229] "session_fcef" "session_fd0e" "session_fe49"
## [232] "session_fe4f" "session_ffa0" "session_10057"
## [235] "session_1019a" "session_1028a" "session_10499"
## [238] "session_10513" "session_105e3" "session_10b03"
## [241] "session_10b53" "session_10c0c" "session_10cb2"
## [244] "session_10e4d" "session_10e67" "session_10e92"
## [247] "session_10fbd" "session_10fcc" "session_114f1"
## [250] "session_116fb" "session_11822" "session_1185e"
## [253] "session_118d0" "session_11b0d" "session_12182"
## [256] "session_121af" "session_121ee" "session_12405"
## [259] "session_126db" "session_12825" "session_12896"
## [262] "session_12a0b" "session_12c7c" "session_12e21"
## [265] "session_1346d" "session_13622" "session_13886"
## [268] "session_13d33" "session_140bd" "session_14428"
## [271] "session_14b8a" "session_14e58" "session_14fdc"
## [274] "session_1517f" "session_151b2" "session_15549"
## [277] "session_155a9" "session_1571b" "session_15b18"
## [280] "session_15b99" "session_15d2c" "session_15e0c"
## [283] "session_15f75" "session_15fbf" "session_16621"
## [286] "session_16691" "session_16f0d" "session_17027"
## [289] "session_173fe" "session_17eaf" "session_17ecd"
## [292] "session_180dd" "session_18641" "session_187ae"
## [295] "session_18a0b" "session_18b18" "session_18db4"
## [298] "session_19048" "session_19051" "session_19510"
## [301] "session_19788" "session_197ee" "session_19c04"
## [304] "session_19c7a" "session_19f0c" "session_1a557"
## [307] "session_1ac3c" "session_1b733" "session_1b76a"
## [310] "session_1b76b" "session_1ba83" "session_1c0a6"
## [313] "session_1c11c" "session_1c304" "session_1c4c3"
## [316] "session_1cea1" "session_1cfb9" "session_1db2a"
## [319] "session_1db96" "session_1dbea" "session_1dc94"
## [322] "session_1e361" "session_1e36e" "session_1e91e"
## [325] "session_wu6bf8f" "session_1f3a8" "session_1f56c"
## [328] "session_1f61e" "session_1f831" "session_1fced"
## [331] "session_1fd39" "session_wu6c9e5" "session_20074"
## [334] "session_2019f" "session_201a1" "session_209f9"
## [337] "session_20e87" "session_2105b" "session_212a2"
## [340] "session_2143b" "session_wu6decf" "session_218ca"
## [343] "session_21bea" "session_21bfd" "session_223e1"
## [346] "session_2248d" "session_22ae6" "session_2324d"
## [349] "session_23636" "session_23912" "session_23a70"
## [352] "session_23b0d" "session_23c17" "session_240ea"
## [355] "session_24256" "session_24484"
##
## $doc_13d
## [1] "session_4809" "session_5dbc" "session_8e0b" "session_cf4b"
## [5] "session_d92a" "session_102bb" "session_10e9f" "session_11344"
## [9] "session_11ca4" "session_12dc9" "session_155b5" "session_1b563"
## [13] "session_1c411" "session_1f384" "session_22e97"
##
## $doc_14c
## [1] "session_53fb" "session_564b" "session_5697" "session_56e2"
## [5] "session_630b" "session_6e80" "session_6f7c" "session_7c8a"
## [9] "session_8903" "session_890c" "session_89d2" "session_907e"
## [13] "session_98b4" "session_c268" "session_c302" "session_cb86"
## [17] "session_d70a" "session_d854" "session_e4c7" "session_f220"
## [21] "session_fd57" "session_fe31" "session_10278" "session_115b0"
## [25] "session_11baa" "session_11e26" "session_12185" "session_1414b"
## [29] "session_14dba" "session_14e47" "session_15738" "session_15a38"
## [33] "session_16305" "session_17b35" "session_19af2" "session_1d074"
## [37] "session_1fcc4" "session_2272e" "session_23a3e"在这种表现方式下，每项拥有一个条目，它是该项出现过的所有事务构成的向量。tidLists可以直接作为输入，用于那些使用这类垂直数据库布局的挖掘算法，挖掘关联信息。
在下一个例子中，我们将看到如何创建数据集，以及规则是如何被挖掘的。
例二：调查问卷数据的挖掘
作为第二个例子，我们准备和挖掘调查问卷数据。我们采用源自UCI机器学习源的Adult数据集[36]，它由arules包提供。这个数据集，类似于Hastie等人在关联规则挖掘章节使用的市场数据集[4]。该数据来源于美国人口普查局数据库，它包含48842个例子，并拥有年龄、工作类别、受教育程度等14个属性。数据最早用于通过这些属性预测个人的收入水平。我们加入了income属性，它具有等级small和large，分别表示收入不高于5万美元和高于5万美元。该数据作为数据集AdultUCI包含在arules包中：
data("AdultUCI")
dim(AdultUCI)## [1] 48842 15AdultUCI[1:2,]## age workclass fnlwgt education education-num marital-status
## 1 39 State-gov 77516 Bachelors 13 Never-married
## 2 50 Self-emp-not-inc 83311 Bachelors 13 Married-civ-spouse
## occupation relationship race sex capital-gain capital-loss
## 1 Adm-clerical Not-in-family White Male 2174 0
## 2 Exec-managerial Husband White Male 0 0
## hours-per-week native-country income
## 1 40 United-States small
## 2 13 United-States smallAdultUCI混合了类别属性和量化属性，在它能转换成适合关联规则挖掘的事务数据前，需要一些预处理。首先，我们移除fnlwgt和education-num两个属性：
AdultUCI[["fnlwgt"]] <- NULL
AdultUCI[["education-num"]] <- NULL第一个属性是权重数据，它是数据集的创建者通过美国人口普查局人口司提供的控制数据计算而得。第二个移除的属性只是属性education的数值表示，该属性也是数据集的一部分。
接下来，我们需要将4个余下的量化数据（age、hour-per-week、capitcal-gain和capital-loss），通过建立合适的类别映射为有序属性。我们借助关于典型的年龄组和工作小时数的知识，将属性age和hour-per-week分为合适的类别。对于资本相关的两个属性，我们为没有收益（损失）的情况创建称为None的类别。然后，我们按它们的中位数，进一步将收入（损失）组分为Low和High两个类别：
AdultUCI[["age"]] <-
ordered(cut(AdultUCI[["age"]],
c(15,25,45,65,100)),
labels=c("Yong", "Middle-aged", "Senior", "Old"))
AdultUCI[["hours-per-week"]] <-
ordered(cut(AdultUCI[["hours-per-week"]],
c(0, 25, 40, 60, 168)),
labels=c("Part-time", "Full-time", "Over-time", "Workaholic"))
AdultUCI[["capital-gain"]] <-
ordered(cut(AdultUCI[[ "capital-gain"]],
c(-Inf,0,median(AdultUCI[["capital-gain"]][AdultUCI[["capital-gain"]]>0]),Inf)),
labels = c("None", "Low", "High"))
AdultUCI[["capital-loss"]] <-
ordered(cut(AdultUCI[[ "capital-loss"]],
c(-Inf,0,median(AdultUCI[["capital-loss"]][AdultUCI[["capital-loss"]]>0]),Inf)),
labels = c("none", "low", "high"))现在，通过数据集到transactions的类型转换，数据能被自动重编码为二值索引矩阵。
Adult <- as(AdultUCI, "transactions")
Adult## transactions in sparse format with
## 48842 transactions (rows) and
## 115 items (columns)剩下的115个类别属性，被自动重编码为115个二值项。在编码过程中，项标签按<variable name>=<category label>的形式生成。注意，对于有缺失值的情况，有缺失值的属性对应的所有项被设为0。
summary(Adult)## transactions as itemMatrix in sparse format with
## 48842 rows (elements/itemsets/transactions) and
## 115 columns (items) and a density of 0.1089939
##
## most frequent items:
## capital-loss=none capital-gain=None
## 46560 44807
## native-country=United-States race=White
## 43832 41762
## workclass=Private (Other)
## 33906 401333
##
## element (itemset/transaction) length distribution:
## sizes
## 9 10 11 12 13
## 19 971 2067 15623 30162
##
## Min. 1st Qu. Median Mean 3rd Qu. Max.
## 9.00 12.00 13.00 12.53 13.00 13.00
##
## includes extended item information - examples:
## labels variables levels
## 1 age=Yong age Yong
## 2 age=Middle-aged age Middle-aged
## 3 age=Senior age Senior
##
## includes extended transaction information - examples:
## transactionID
## 1 1
## 2 2
## 3 3事务数据集的摘要给出了一个粗糙的预览，展示了最频繁的项、事务的长度分布，以及扩展的项信息，它展示了每个二值项由哪些变量和哪些值创建。在例一中，我们看到标签为age=Middle-aged的项由变量age和等级middle-aged产生。
为了看到哪些项在数据集中重要，我们可以使用itemFrequencyPlot()。为了减少项的数目，我们只绘出支持度大于$10\%$（利用参数support）的那些项的项频率。为了标签更好的可读性，我们通过参数cex.names减小了标签大小：
itemFrequencyPlot(Adult, support = 0.1, cex.names=0.8)
接下来，我们按最小支持度$1\%$、置信度$0.6$，调用apriori()函数找出所有的规则（apriori()默认的关联信息类型）：
rules <- apriori(Adult,
parameter = list(support = 0.01, confidence = 0.6))##
## Parameter specification:
## confidence minval smax arem aval originalSupport support minlen maxlen
## 0.6 0.1 1 none FALSE TRUE 0.01 1 10
## target ext
## rules FALSE
##
## Algorithmic control:
## filter tree heap memopt load sort verbose
## 0.1 TRUE TRUE FALSE TRUE 2 TRUE
##
## apriori - find association rules with the apriori algorithm
## version 4.21 (2004.05.09) (c) 1996-2004 Christian Borgelt
## set item appearances ...[0 item(s)] done [0.00s].
## set transactions ...[115 item(s), 48842 transaction(s)] done [0.03s].
## sorting and recoding items ... [67 item(s)] done [0.01s].
## creating transaction tree ... done [0.03s].
## checking subsets of size 1 2 3 4 5 6 7 8 9 10 done [0.79s].
## writing ... [276443 rule(s)] done [0.04s].
## creating S4 object ... done [0.23s].rules## set of 276443 rules首先，函数打印出采用的参数。除了设定最小支持度和最小置信度外，所有参数都使用默认值。值得一提的是参数maxlen，挖掘出频繁项集的大小，默认被限定为5。若将maxlen设为更大的值，更长的关联规则才能被挖掘。设定了参数之后，C实现的算法的输出和时间信息会被显示。
挖掘算法的结果是276443条规则构成的集合。summary()可用于显示挖掘到的规则的摘要信息：
summary(rules)## set of 276443 rules
##
## rule length distribution (lhs + rhs):sizes
## 1 2 3 4 5 6 7 8 9 10
## 6 432 4981 22127 52669 75104 67198 38094 13244 2588
##
## Min. 1st Qu. Median Mean 3rd Qu. Max.
## 1.000 5.000 6.000 6.289 7.000 10.000
##
## summary of quality measures:
## support confidence lift
## Min. :0.01001 Min. :0.6000 Min. : 0.7171
## 1st Qu.:0.01253 1st Qu.:0.7691 1st Qu.: 1.0100
## Median :0.01701 Median :0.9051 Median : 1.0554
## Mean :0.02679 Mean :0.8600 Mean : 1.3109
## 3rd Qu.:0.02741 3rd Qu.:0.9542 3rd Qu.: 1.2980
## Max. :0.95328 Max. :1.0000 Max. :20.6826
##
## mining info:
## data ntransactions support confidence
## Adult 48842 0.01 0.6它展示了规则数量，LHS和RHS中最频繁的项和它们分别的长度分布，以及挖掘算法返回的用于质量度量的统计信息的摘要。
作为典型的关联规则挖掘，找到的规则数量大。为了分析这些规则，比如，subset()可为每个项产生独立的规则子集，其项从规则的RHS的income变量而来，同时我们要求提升度的度量超过1.2：
rulesIncomeSmall <- subset(rules, subset = rhs %in% "income=small" & lift > 1.2)
rulesIncomeLarge <- subset(rules, subset = rhs %in% "income=large" & lift > 1.2)我们现在分别得到了低收入和高收入人群的规则集。为了比较，我们考察两个集合置信度最高的3条规则：
inspect(head(sort(rulesIncomeSmall, by = "confidence"), n = 3))## lhs rhs support confidence lift
## 1 {workclass=Private,
## marital-status=Never-married,
## relationship=Own-child,
## sex=Male,
## hours-per-week=Part-time,
## native-country=United-States} => {income=small} 0.01074895 0.7104195 1.403653
## 2 {workclass=Private,
## marital-status=Never-married,
## relationship=Own-child,
## sex=Male,
## hours-per-week=Part-time} => {income=small} 0.01144507 0.7102922 1.403402
## 3 {workclass=Private,
## marital-status=Never-married,
## relationship=Own-child,
## sex=Male,
## capital-gain=None,
## hours-per-week=Part-time,
## native-country=United-States} => {income=small} 0.01046231 0.7097222 1.402276inspect(head(sort(rulesIncomeLarge, by = "confidence"), n = 3))## lhs rhs support confidence lift
## 1 {marital-status=Married-civ-spouse,
## capital-gain=High,
## native-country=United-States} => {income=large} 0.01562180 0.6849192 4.266398
## 2 {marital-status=Married-civ-spouse,
## capital-gain=High,
## capital-loss=none,
## native-country=United-States} => {income=large} 0.01562180 0.6849192 4.266398
## 3 {relationship=Husband,
## race=White,
## capital-gain=High,
## native-country=United-States} => {income=large} 0.01302158 0.6846071 4.264454从规则中，我们看出私营部门工作的的工人、兼职工作或在服务业工作7收入偏低，然而那些出生在美国的资本收益高的人收入偏高。这个例子展示了使用子集抽取和排序，挖掘到的关联信息集合就算很大也能被分析。
最后，找出的规则可被写入磁盘与其它应用共享。write()函数可将规则保存为纯文本格式。如下命令，按逗号分隔值（CSV）格式，将规则集合存为名为“data.csv”的文件：
write(rulesIncomeSmall, file = "data.csv", sep = ",", col.names = NA)另外，利用pmml包，规则还能存为PMML（predictive modelling markup language）格式[37]：
write.PMML(rulesIncomeSmall, file = "data.xml")## [1] "data.xml"这是一种基于XML的标准化表示方式，被许多数据挖掘工具采用。注意，pmml需要XML包，该包可能不是在所有操作系统中都可用。
其它程序现在能容易的分享和使用保存的数据。项集（事务用write()也可）可按同样的方式写为文档。
例三：兴趣度量的扩展
在本例中，我们展示加入新的兴趣度量——使用Omiecinski提出的全置信度（all-confidence）[7]——多么的容易。项集$X$的全置信度定义为
\begin{equation} all\mbox{-}confidence(X) = {supp(X)\over \max_{I\subset X}supp(I)}。 \label{eq:all-confidence} \end{equation}
该度量拥有这样的特性：对所有$I\subset X$，都有$conf(I \to X\not I) \geq all\mbox{-}confidence(X)$。这意味着从项集$X$产生的所有可能规则，必须至少拥有一个置信度，该置信度由项集的全置信度给定。Omiecinski指出公式\eqref{eq:all-confidence}分母的支持度一定来自于单个的项，因此能简化为$\max_{i\subset X}supp(\{i\})$。为了获得计算全支持度的项集，我们使用Eclat算法，从先前用过的Adult数据挖掘频繁项集：
data("Adult")
fsets <- eclat(Adult, parameter = list(support = 0.05),
control = list(verbose=FALSE))为了得到全置信度的分母，我们需要找出全部挖掘到的单个项集，以及它们对应的置信度值。我们创建一个以项的列号命名的向量，并将项的支持度作为向量的元素：
singleItems <- fsets[size(items(fsets)) == 1]
## Get the col numbers we have support for
singleSupport <- quality(singleItems)$support
names(singleSupport) <- unlist(LIST(items(singleItems), decode = FALSE))
head(singleSupport, n = 5)## 66 63 111 60 8
## 0.9532779 0.9173867 0.8974243 0.8550428 0.6941976接下来，我们可用公式\eqref{eq:all-confidence}计算所有项集的全支持度。作为分母的单个项的支持度从带命名的向量singleSupport中查找，最终得到的度量加入到（衡量）集合质量的数据框：
itemsetList <- LIST(items(fsets), decode = FALSE)
allConfidence <- quality(fsets)$support /
sapply(itemsetList, function(x) max(singleSupport[as.character(x)]))
quality(fsets) <- cbind(quality(fsets), allConfidence)
summary(fsets)## set of 8496 itemsets
##
## most frequent items:
## capital-loss=None native-country=United-States
## 4082 3973
## capital-gain=None race=White
## 3962 3781
## workclass=Private (Other)
## 3142 21931
##
## element (itemset/transaction) length distribution:sizes
## 1 2 3 4 5 6 7 8 9 10
## 36 303 1078 2103 2388 1689 706 171 21 1
##
## Min. 1st Qu. Median Mean 3rd Qu. Max.
## 1.000 4.000 5.000 4.811 6.000 10.000
##
## summary of quality measures:
## support allConfidence
## Min. :0.05002 Min. :0.05247
## 1st Qu.:0.06038 1st Qu.:0.06597
## Median :0.07546 Median :0.08428
## Mean :0.10124 Mean :0.11667
## 3rd Qu.:0.11279 3rd Qu.:0.12711
## Max. :0.95328 Max. :1.00000
##
## includes transaction ID lists: FALSE
##
## mining info:
## data ntransactions support
## Adult 48842 0.05新的质量度量现在是项集集合的一部分。
该度量可用于操作集合。例如，我们可以查找哪些包含一个与受教育程度相关的项的项集（采用部分匹配%pin%），并且将它们按全支持度排序（我们首先过滤掉长度为1的项集，因为它们的的全支持度为1）：
fsetsEducation <- subset(fsets, subset = items %pin% "education")
inspect(sort(fsetsEducation[size(fsetsEducation)>1],
by = "allConfidence")[1 : 3])## items support allConfidence
## 1 {education=HS-grad,
## hours-per-week=Full-time} 0.2090209 0.3572453
## 2 {education=HS-grad,
## income=small} 0.1807051 0.3570388
## 3 {workclass=Private,
## education=HS-grad} 0.2391794 0.3445408最终得到的项集表明：高中毕业（没有受更高程度的教育）项与全职工作、低收入和私营企业工作高度相关。在arlues中，全支持度和其它一些兴趣度的度量方法通过interestMeasure()函数的形式已经实现了。
例四：事务数据的抽样
通过本例，我们展示抽样如何被用于arules。我们仍采用Adult数据集：
data("Adult")
Adult ## transactions in sparse format with
## 48842 transactions (rows) and
## 115 items (columns)我们采用公式\eqref{eq:sample-sizez-evaluation}计算可行的样本集大小$n$。我们将最小支持度设为$5\%$。我们将可接受的支持度的错误率$\epsilon$设为$10\%$，作为置信水平（$1-c$）我们设为$90\%$）：
supp <- 0.05
epsilon <- 0.1
c <- 0.1
n <- -2 * log(c) / (supp * epsilon^2)
n## [1] 9210.34结果的抽样数据集的大小比原始数据库小得多。我们使用sample()对原始数据库进行放回抽样，生成大小为$n$的抽样数据集：
AdultSample <- sample(Adult, n, replace = TRUE)使用项的频率图，可以对样本集和数据库（总体）进行对比：
itemFrequencyPlot(AdultSample, population = Adult, support = supp,
cex.names = 0.7)
样本集的项频率显示为长条，原始数据库的项频率表示为线。为了标签的可读性更好，我们在图中只显示了频繁的项，并且采用参数cex.names减小了标签的大小。
另外，样本可以通过提升率（lift ratio）将样本集与population进行比较：
itemFrequencyPlot(AdultSample, population = Adult,
support = supp, lift = TRUE,
cex.names = 0.7)
另外，可通过提升率（设置lift=TRUE）比较样本与总体。每个项$i$的提升率（lift ration）定义为${P(i|sample)\over P(i|population)}$，其中概率通过项的频率估计。提升率为1表示项在样本集中出现的比例与在总体中出现的一样；提升率大于1表示项在样本集中被过度表示，反之亦然。采用该图，较小频率项的大的相对偏差可以直观的辨识。
为了比较通过采样获得的性能提升，我们采用Eclat算法在数据库和样本集上挖掘频繁项集，并且对比挖掘耗费的系统时间（以秒计）：
time <- system.time(itemsets <- eclat(Adult,
parameter = list(support = supp), control = list(verbose = FALSE)))
time## user system elapsed
## 0.190 0.002 0.193timeSample <- system.time(itemsetsSample <- eclat(AdultSample,
parameter = list(support = supp), control = list(verbose = FALSE)))
timeSample## user system elapsed
## 0.043 0.001 0.046system.time()返回向量的第1个元素，给出了用于执行其参数中语句的（用户）CPU时间。因此，在抽样数据集而非全部数据库上挖掘获得的提速因子为：
time[1] / timeSample[1]## user.self
## 4.418605为了评估在样本集上项集挖掘的精度，我们分析在两个集合上（表现）的差异：
itemsets## set of 8496 itemsetsitemsetsSample## set of 8585 itemsets以上两个集合大小差不多。为了检查集合是否包含相似的项集，我们匹配集合，并且查看在数据库中出现的频繁项集也在样本集中出现的比率：
match <- match(itemsets, itemsetsSample, nomatch = 0)
## remove no matches
sum(match>0) / length(itemsets)## [1] 0.9679849使用样本集，几乎所有的频繁项集都找到了。如下展示了那些没有在样本集中找到的频繁项集的支持度摘要信息，以及在样本中频繁但在数据库中非频繁的项集的支持度摘要信息：
summary(quality(itemsets[which(!match)])$support)## Min. 1st Qu. Median Mean 3rd Qu. Max.
## 0.05002 0.05051 0.05104 0.05162 0.05223 0.05823summary(quality(itemsetsSample[-match])$support)## Min. 1st Qu. Median Mean 3rd Qu. Max.
## 0.05005 0.05071 0.05136 0.05170 0.05244 0.05755以上信息表明只有那些支持度非常接近最小支持度的项集，错误的缺失或错误的找到了。
通过从数据库和样本找到的频繁项集，我们可以通过错误率计算精度：
supportItemsets <- quality(itemsets[which(match > 0)])$support
supportSample <- quality(itemsetsSample[match])$support
accuracy <- 1 - abs(supportSample - supportItemsets) / supportItemsets
summary(accuracy)## Min. 1st Qu. Median Mean 3rd Qu. Max.
## 0.8398 0.9478 0.9697 0.9643 0.9861 1.0000以上摘要信息表明抽样可获得项集高精度的支持度。 这个简单的例子表明对于很大的数据库或看重挖掘时间的应用，抽样可作为一种强大技术。
结论与展望
通过arules包，我们提供了基础架构，它使我们能挖掘关联信息以及分析和处理挖掘结果。在此之前，R中并无这类的架构可用。arules的主要特性包括：
- 利用稀疏矩阵高效的实现；
- 供了简单和直观的接口处理和分析事务数据提、以及具有子集抽取和排序功能的项集和规则的集合；
- 接入了两个快速的挖掘算法；
- 能够灵活的增加新的质量度量、额外的项以及事务描述，这可用于选取事务和分析所得的关联信息；
- 提供了可扩展的数据结构，能容易实现新的关联信息类型和接入新的算法。
这里存在几个arules的有趣的可行扩展方案，比如，接入那些使用统计量发现有趣项集的算法会十分有用（不必是关联规则相关的频繁项集）。这类算法包括实现基于$\mathcal X^2$测试的算法[38]，或者基线频率方法（baseline frequency approach）[39]，还可以实现arules中基于距离的聚类以用于关联信息的可视化[40]。
参考资料
- [1]M. Hahsler, B. Gruen, and K. Hornik, “arules – A Computational Environment for Mining Association Rules and Frequent Item Sets,” Journal of Statistical Software, vol. 14, no. 15, pp. 1–25, Oct. 2005. [Online]
- [2]G. Piatetsky-Shapiro, “Discovery, analysis, and presentation of strong rules,” Knowledge discovery in databases, pp. 229–238, 1991.
- [3]R. Agrawal, T. Imieliński, and A. Swami, “Mining Association Rules Between Sets of Items in Large Databases,” Sigmod Record, vol. 22, no. 2, pp. 207–216, Jun. 1993. [Online]
- [4]T. Hastie, R. Tibshirani, and J. Friedman, The elements of statistical learning. Springer.
- [5]J. Hipp, U. Güntzer, and G. Nakhaeizadeh, “Algorithms for association rule mining—a general survey and comparison,” ACM sigkdd explorations newsletter, vol. 2, no. 1, pp. 58–64, 2000.
- [6]M. J. Zaki, “Mining non-redundant association rules,” Data mining and knowledge discovery, vol. 9, no. 3, pp. 223–248, 2004.
- [7]E. R. Omiecinski, “Alternative interest measures for mining associations in databases,” Knowledge and Data Engineering, IEEE Transactions on, vol. 15, no. 1, pp. 57–69, 2003.
- [8]S. Brin, R. Motwani, J. D. Ullman, and S. Tsur, “Dynamic itemset counting and implication rules for market basket data,” in ACM SIGMOD Record, 1997, vol. 26, no. 2, pp. 255–264.
- [9]N. Govindaraju and M. Zaki, “Advances in Frequent Itemset Mining Implementations,” 2003.
- [10]C. Borgelt, “Efficient implementations of apriori and eclat,” in FIMI’03: Proceedings of the IEEE ICDM workshop on frequent itemset mining implementations, 2003.
- [11]M. J. Berry and G. Linoff, Data mining techniques: for marketing, sales, and customer support. John Wiley & Sons, Inc., 1997.
- [12]M. J. Zaki, “Scalable algorithms for association mining,” IEEE Transactions on Knowledge and Data Engineering, vol. 12, no. 3, pp. 372–390, 2000.
- [13]R. Srikant and R. Agrawal, “Mining quantitative association rules in large relational tables,” in ACM SIGMOD Record, 1996, vol. 25, no. 2, pp. 1–12.
- [14]C. Borgelt, “Finding association rules/hyperedges with the apriori algorithm.” Working Group Neural Networks and Fuzzy Systems, Otto-von-Guericke-University of Magdeburg, Universitätsplatz, 2004.
- [15]B. Goethals and M. J. Zaki, “FIMI’03: Workshop on frequent itemset mining implementations,” in Third IEEE International Conference on Data Mining Workshop on Frequent Itemset Mining Implementations, 2003, pp. 1–13.
- [16]D. E. Knuth, The art of computer programming: sorting and searching, vol. 3. Pearson Education, 1998.
- [17]C. Borgelt and R. Kruse, “Induction of association rules: Apriori implementation,” in Compstat, 2002, pp. 395–400.
- [18]M. Hahsler, C. Buchta, and K. Hornik, “Selective association rule generation,” Computational Statistics, vol. 23, no. 2, pp. 303–315, 2008.
- [19]H. Mannila, H. Toivonen, and A. I. Verkamo, “Efficient algorithms for discovering association rules,” in KDD-94: AAAI workshop on Knowledge Discovery in Databases, 1994, pp. 181–192.
- [20]M. J. Zaki, S. Parthasarathy, W. Li, and M. Ogihara, “Evaluation of sampling for data mining of association rules,” in Research Issues in Data Engineering, 1997. Proceedings. Seventh International Workshop on, 1997, pp. 42–50.
- [21]S. Parthasarathy, “Efficient progressive sampling for association rules,” in Data Mining, 2002. ICDM 2003. Proceedings. 2002 IEEE International Conference on, 2002, pp. 354–361.
- [22]H. Toivonen and others, “Sampling large databases for association rules,” in VLDB, 1996, vol. 96, pp. 134–145.
- [23]R. Agrawal, R. Srikant, and others, “Fast algorithms for mining association rules,” in Proc. 20th int. conf. very large data bases, VLDB, 1994, vol. 1215, pp. 487–499.
- [24]M. Hahsler, K. Hornik, and T. Reutterer, “Implications of probabilistic data modeling for rule mining,” 2005.
- [25]M. J. Zaki, S. Parthasarathy, M. Ogihara, W. Li, and others, “New Algorithms for Fast Discovery of Association Rules.,” in KDD, 1997, vol. 97, pp. 283–286.
- [26]N. Pasquier, Y. Bastide, R. Taouil, and L. Lakhal, “Discovering Frequent Closed Itemsets for Association Rules,” in International Conference on Database Theory, 1999, pp. 398–416.
- [27]H. Xiong, P.-N. Tan, and V. Kumar, “Mining strong affinity association patterns in data sets with skewed support distribution,” in Data Mining, 2003. ICDM 2003. Third IEEE International Conference on, 2003, pp. 387–394.
- [28]B. Liu, W. Hsu, and Y. Ma, “Pruning and summarizing the discovered associations,” in Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, 1999, pp. 125–134.
- [29]H. Hofmann and A. Wilhelm, “Visual comparison of association rules,” Computational Statistics, vol. 16, no. 3, pp. 399–415, 2001.
- [30]M. Hahsler and K. Hornik, “New probabilistic interest measures for association rules,” Intelligent Data Analysis, vol. 11, no. 5, pp. 437–455, 2007.
- [31]R. J. Bayardo Jr, R. Agrawal, and D. Gunopulos, “Constraint-based rule mining in large, dense databases,” in Data Engineering, 1999. Proceedings., 15th International Conference on, 1999, pp. 188–197.
- [32]P.-N. Tan, V. Kumar, and J. Srivastava, “Selecting the right objective measure for association analysis,” Information Systems, vol. 29, no. 4, pp. 293–313, 2004.
- [33]A. Strehl, G. K. Gupta, and J. Ghosh, “Distance based clustering of association rules,” Proceedings ANNIE 1999, vol. 9, pp. 759–764, 1999.
- [34]C. C. Aggarwal, C. Procopiuc, and P. S. Yu, “Finding localized associations in market basket data,” Knowledge and Data Engineering, IEEE Transactions on, vol. 14, no. 1, pp. 51–62, 2002.
- [35]M. Hahsler and K. Hornik, “Building on the arules infrastructure for analyzing transaction data with R,” in Advances in Data Analysis, Springer, 2007, pp. 449–456.
- [36]A. Asuncion and D. Newman, “UCI repository of machine learning databases (2007).” [Online]
- [37]G. Williams et al., pmml: Generate PMML for various models. 2014. [Online]
- [38]C. Silverstein, S. Brin, and R. Motwani, “Beyond market baskets: generalizing association rules to dependence rules,” Data mining and knowledge discovery, vol. 2, no. 1, pp. 39–68, 1998.
- [39]W. DuMouchel and D. Pregibon, “Empirical bayes screening for multi-item associations,” in Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, 2001, pp. 67–76.
- [40]A. Strehl and J. Ghosh, “Relationship-based clustering and visualization for high-dimensional data mining,” INFORMS Journal on Computing, vol. 15, no. 2, pp. 208–230, 2003.
脚注
-
论文中为
0, 1, 1, 3, 0, 3, 3和0, 3, 4, 7，是否有误？ ↩ -
An example application using questionnaire data can be found in Hastie[4] in the chapter about association rule mining. ↩
-
Note that when representing transactions, tidLists store for each item a transaction list, but here store for each itemset a list of transaction IDs in which the itemset appears. ↩
-
As a heuristic, the authors suggest to use the user specified minimum support threshold for $\tau$. ↩
-
哪里看出服务业收入偏低？ ↩
