关联规则学习 (ARL)：第一部分 - Apriori 算法
4.95/5 (8投票s)
如何使用可扩展的优化 Apriori 算法执行 ARL
目录
引言
在计算机科学和信息技术领域中，在进行大数据分析时，未分类数据分类是最复杂的工程问题之一。为了对潜在海量的未分类数据进行分类，目前使用了各种方法和模式。具体来说，这些模式基本包括许多计算机算法，例如 k-means 聚类过程、朴素贝叶斯算法、人工神经网络 (ANN) 等。这些方法中的每一种都只允许对特定类型的数据进行分类。例如，k-means 和 CLOPE 聚类可用于对表示为数值参数 n 维向量的数据进行分类。反过来，朴素贝叶斯算法旨在用于分类数值或其他类型的数据，仅当已预定义离散的类别元组（例如，主要是“两个”类的集合）时。此外，ANN 主要能够执行分类和泛化，这使其非常适合解决我们主要处理典型少量数据分类的任何现有问题。
不幸的是，由于其性质，上述方法均不能用作分类各种结构数据（尤其是必须排列成一个或多个层次结构的数据）的单一算法。
此外，在对事务数据量急剧增长的动态数据流进行实时处理时，使用这些算法也存在许多问题。在使用 k-means 聚类时，我们通常需要为发送到动态数据流的每批新数据重新计算数据模型。您可能已经知道，k-means 是一项复杂的计算任务，其复杂度高于 NP 难题，会消耗大量的 CPU 和系统内存资源。类似地，ANN 在接收到来自动态数据流的新事务量后也必须重新训练，这会导致与使用 k-means 或 CLOPE 聚类算法时相同的问题。
这是一个分类问题的生动例子，解决此问题时，k-means 和朴素贝叶斯分类器均无用武之地。假设我们处理一个动态实时处理流，其中所有数据都排列成事务 $\begin{aligned}T=\{t_1,t_2,t_3,…,t_{n-1},t_n\}\end{aligned} $。每个事务 $\begin{aligned}∀t_s\end{aligned} $ 都是一组项目，其值可以是数值、字符串、对象或任何其他现有数据类型。此外，我们给定一组（即多于“两个”）预定义类别 $\begin{aligned}C=\{c_1,c_2,c_3,…,c_{m-1},c_m\}\end{aligned} $。在这种情况下，我们的目标是通过将从事务集中检索到的特定项目 $\begin{aligned}\forall i_k \in I \end{aligned}$ 分配到这些特定类别 $\begin{aligned}C\end{aligned} $ 之间来执行一个简单的分类。
显然，在这种情况下，我们需要一种完全不同的方法来对各种未分类数据进行分类，而不是传统的 k-means 聚类或朴素贝叶斯分类。
在数据挖掘和人工智能机器学习中，有许多算法允许通过执行关联规则学习 (ARL) 来快速轻松地分类排列成事务集的各种类型的未分类数据。这些算法基本包括著名的暴力算法及其一系列优化修改，如 Apriori、ECLAT 和 FPGrowth。以下算法属于关联规则学习 (ARL) 和大数据处理算法的整个家族。
与其他分类算法不同，这些算法允许执行的分类主要依赖于确定特定数据之间关联关系的过程，包括它们的层次关系，这些关系在表示为输入事务集的整个数据集上显现出来。
本文将介绍并阐述著名的 Apriori 算法，它是在处理各种类型大数据时替代任何其他现有分类算法的良好选择，并为原始的暴力关联挖掘算法提供了有效的优化。我们将讨论基于 Apriori 算法对给定集合中的字符串数据类型项目进行分类，根据从给定事务集中学习到的统计数据，创建属于每个特定类别的项目组。
在本文的背景部分，我们将讨论关联规则学习 (ARL) 过程的基础知识，以便更好地理解作为关联规则挖掘问题定义一部分的特定术语。之后，我们将逐步介绍并阐述 Apriori 算法。最后，我们将详细讨论使用 Intel C++ Compiler 19.0 和 OpenMP 性能库实现 Apriori 算法。在讨论结束时，我们将评估 Apriori 算法并仔细研究使用此算法可以实现哪些特定结果。
背景
关联规则学习基础
关联规则学习（ARL）是数据挖掘和大数据分析过程中最重要的策略之一。当我们遇到需要处理通常以字符串格式表示的巨量数据且没有提供其他信息时，它变得非常有用和高效。采用关联规则挖掘方法的另一个好处是它具有对通常巨大的动态数据流进行优化处理的“才能”，从而以接近实时的方式获取对所分析数据的洞察、趋势和知识。
数据流是来自一个或多个提供商生成的各种数据的海量集合。在大多数情况下，数据流是执行一系列由特定数据处理和流功能提交的实时事务的结果。一旦事务被提交并处理，我们通常会收到发送到数据流的最终数据集，这也称为“事务”。事务有各种含义，例如金融、交易或游戏。例如，我们收到执行交易事务后从百货商店购买商品数量的特定数据。在这种情况下，这些数据表示为 `itemset`，其中每个项目都是一个实体，包含有关所购买特定产品名称及其价格的信息，例如
| ID | 产品 | 价格 |
| 1 | 面包 | $2.00 |
| 2 | 牛奶 | $5.99 |
| 3 | 蜂蜜 | $6.79 |
| 4 | 沙拉 | $4.67 |
通常，一家普通百货商店会提交数十亿笔事务到数据流。庞大的事务数据量使得实时收集的数据中揭示出大量的洞察和趋势成为可能。
例如，通过使用大数据分析算法，我们可以根据挖掘出的某些统计数据之间的关系，找出特定产品的受欢迎程度以及确定哪些特定产品最常一起购买。关联规则学习算法最常被推荐用于此目的，而不是简单的频率测试或其他分类算法。
“1992 年，由 Thomas Blishock 领导的 Teradata 零售咨询小组对 Osco Drug 零售商的 25 家商店的 120 万笔交易进行了研究。在分析了所有这些交易后，最强的规则是“下午 5:00 到 7:00 之间，啤酒和尿布最常一起购买”。不幸的是，这样的规则对 Osco Drug 的领导层来说似乎如此违反直觉，以至于他们没有把尿布放在啤酒旁边的货架上。尽管啤酒-尿布这对组合的解释很容易找到，当年轻家庭的两位成员下班回家（大约下午 5:00）时，妻子通常会派丈夫去最近的商店买尿布。而丈夫们毫不犹豫地将愉快与有用结合起来——他们按照妻子的指示购买尿布，并为自己的晚上消遣购买啤酒。”
在下一段中，我们将介绍项集和事务，并仔细研究在整个数据流中数据可能呈现出哪些具体的洞察和趋势。
事务集
此时，让我们解释一些术语，这些术语对于更好地理解关联规则挖掘过程是必需的。
一个“项集” $\begin{aligned}I=\{i_1,i_2,i_3,…,i_{n-1},i_n\}\end{aligned} $ 是一个项目序列 $\begin{aligned}\forall i_k \in I \end{aligned} $，其字符串值代表特定实体。例如：$\begin{aligned}I=\{"Computer" ,"Office" ,"Vehicle" ,"Beer" ,…,"Bread" ,"Diapers" \}\end{aligned} $。单个项集中的数据项目可能相关也可能不相关。具体来说，项集仅仅是数据的“原始”集合。如果一个项集包含 k 个项目，则称之为 k 项集。
“事务”（已定义）∀t 是在事务提交和处理后发送到数据流的最终项集。事务指一个项集，其中包含的项目中某些数量可能存在关联。在上面列出的示例中，“Computer”和“Office”、“Bread”、“Beer”和“Diapers”是关联项目，而“Vehicle”和“Diapers”不关联。
“事务集”（已定义）——数据流的一个片段，包含在特定时间段内提交的所有事务的项集序列。集合中特定事务的项集可能包含或不包含具有相同值的项。特定事务项集中的每个项也可能出现在其他事务的项集中。同样，相同的项关联可能包含在多个事务中。如果给定集合中的一对事务包含相同的关联，则这些事务也可能存在关联。下面的示例说明了一个正在讨论的简单事务集
| TID | 事务 |
| 1 | 发动机、车辆、转向、CPU、刹车、主板、机器、电器 |
| 2 | CPU、车轮、油箱、主板、座椅、摄像头、散热器、电脑、机器、电器 |
| 3 | 主板、转向、显示器、刹车、发动机、车辆、机器、电器 |
| 4 | CPU、转向、刹车、散热器、显示器、GPU、电脑、机器、电器 |
| 5 | 车辆、散热器、CPU、转向、刹车、车轮、油箱、发动机、机器、电器 |
| 6 | 电脑、CPU、主板、GPU、散热器、发动机、机器、电器 |
| 7 | 刹车、车辆、油箱、发动机、CPU、转向、机器、电器 |
| 8 | 钢笔、墨水、铅笔、书桌、打字机、刷子、办公室、电器 |
| 9 | 墨水、打字机、铅笔、书桌、办公室、电器 |
如您在上述示例中可能已注意到，在特定的事务集中，某些项目及其关联出现的频率或多或少。此外，至少有一个项目出现在集合中的所有事务中。
在本文的后续段落中，我们将详细讨论如何利用事务集中项目及其关联出现频率的数据进行关联规则挖掘。
为了能够执行关联规则学习 (ARL)，整个事务数据集必须至少满足三个要求
- 每个事务的项集必须包含一定数量属于特定“类别”的项，以及少量来自一个或多个不同于特定类别的项；
- 每个项集中的项目总数必须包含代表特定“类别”或“分类”的项目；
- 所有事务项集中必须包含一个代表最顶层“根”类别的项；
根据层次结构原理，出现在所有事务项集中的项实际上是树的“根”，每个代表类别的项是“内部”节点，连接特定的同级（即分支）。此外，那些不代表任何现有类别的项是树的“叶”节点。
在接下来的段落中，我们将详细讨论如何根据关联规则挖掘过程中获得的结果数据构建各种层次结构。
关联规则
“关联规则”（已定义）——两个项集的蕴含关系，这两个集合中的特定项之间存在直接、明确和不模糊的关系。这个蕴含关系中的第一个项集称为“前件”，代表某个“条件”，而第二个项集则称为“后件”。从逻辑上讲，关联规则可以表示如下：如果“条件”为“真”，则“结果”也为“真”。同样，关联规则也可以解释为“从一者可以推断出另一者”。例如，我们有一个简单的关联规则
{"电脑", 显示器}→{CPU, 主板}
上面列出的表达式代表了特定项目（即“实体”）之间的关系。在这种情况下，如果 {“电脑”、“显示器”} 相互关联，那么 {“电脑”、“CPU”}、{“电脑”、“主板”}、{“显示器”、“CPU”}、{“显示器”、“主板”} 等特定项目也具有完全相同的关系。此外，这些特定项目对之间也存在关系。我们认为这些对中的每一对都是与相似规则及其祖先规则相关的关联规则。而且，关联规则的“前件”本身也是一个规则，被认为是上面所示关联规则派生出的所有后续规则变体的“父规则”。
在代数上，关联规则可以用蕴含运算符 A→B 表示，其中 A 为前件，B 为特定后件项集。同样，A 和 B 是等价的，这意味着 A→B≡B→A。集合论中的许多运算符，如 ∪、∩、⊆、∈、∉ 都可以应用于任何关联规则。以下是一些例子
{电脑, 显示器}∩{CPU, 主板}=∅
上面这个例子表明，这两个项集的交集正好是一个空集 ∅。这意味着规则的前件和后件项集永远不能相交。这是生成新规则候选的必要条件。
{电脑, 显示器}∪{CPU, 主板}={电脑, 显示器, CPU, 主板}
上面的第二个例子展示了规则前件或后件的并集。以下技术主要用于新规则的生成过程。
{显示器,CPU}⊆{电脑,显示器,CPU,主板},
{电脑,主板}⊆{电脑,显示器,CPU,主板},
正如您从上面的例子中可以看出，2 项集 {显示器, CPU} 包含在另一个 4 项集 {电脑, 显示器, CPU, 主板} 中。这实际上表明这两个项集之间存在逻辑关系。
电脑∈{电脑,显示器,CPU,主板},
啤酒∉{电脑,显示器,CPU,主板}
最后两个例子说明了项目“Computer”属于 4 项集，并与该项集中的其他项目具有关联关系。同时，项目“Beer”不包含在该项集中。这就是为什么它与这些项目中的任何一个都没有关系的原因。
有各种方法，例如穷举法或优化法，用于生成新的规则集。无论采用何种方法挖掘这些规则，关联规则概念都保持其逻辑和数学意义。
既然我们已经详细讨论了关联规则术语及其定义，现在让我们仔细研究生成新规则的过程。以下示例将说明一种常见于大多数关联规则挖掘算法的方法，该方法允许基于给定集合中已有的规则对生成全新的规则。
假设我们已经有一对 N 项集 $\begin{aligned}I^{'}\end{aligned} $ 和 $\begin{aligned}I^{''}\end{aligned} $，每个项集都由从特定事务的项集中提取的一定数量的唯一项组成，因此 $\begin{aligned}I=\{ \forall i_k | \forall i_k \in t_s, t_s \in T\}\end{aligned} $。要生成新的规则候选，我们只有在满足以下条件时才能合并项集：$\begin{aligned}I^{'}\end{aligned} $ 项集中的任何项目都不包含在第二个项集 $\begin{aligned}I^{''}\end{aligned} $ 中（$\begin{aligned}I^{'} \notin I^{''} \end{aligned} $）。这里有两个例子，说明何时可以或不可以生成新规则
{电脑, 显示器}⊎{CPU, 主板}→{电脑, 显示器, CPU, 主板},
{主板, 尿布}⊎{CPU, 主板}→∅,
{电脑, 显示器}⊎{面包, 尿布}→{电脑, 显示器, 面包, 尿布},
在第一个例子中，我们可以生成一个新规则，因为项集 $\begin{aligned}I^{'}\end{aligned} $ 中的任何项都不包含在项集 $\begin{aligned}I^{''}\end{aligned} $ 中。相反，第二个例子说明，在这种情况下，我们通常无法生成新规则，因为项“主板”包含在两个项集 $\begin{aligned}I^{'}\end{aligned} $ 和 $\begin{aligned}I^{''}\end{aligned} $ 中。
至于第一个例子中的规则，我们还可以生成一组它的同级规则，例如
{电脑, 显示器}⊎{CPU, 主板}→{电脑, 显示器, CPU, 主板},
{电脑, 显示器}⊎{面包, 尿布}→{电脑, 显示器, 面包, 尿布},
{电脑,显示器}→{CPU,主板},
{电脑,CPU}→{主板,显示器},
{主板,显示器}→{CPU},
{CPU,显示器}→{电脑},
{面包,电脑}→{显示器},
{尿布,显示器}→{电脑},
.....
正如我们已经讨论过的，所有这些规则都分别与父规则有关联。
“有趣”规则挖掘
上一段中生成的每条规则都可能或多或少“有趣”，这取决于规则项集中特定项之间关系的潜在“强度”。在本段中，我们将讨论如何评估对规则的兴趣及其重要性。
形式上，生成的每条规则的项集似乎都是一个子集，同时出现在一个或多个事务项集（$\begin{aligned}I \subseteq t_s\end{aligned}$）中，如上所示。我们可能从以下事务集中揭示的第一个趋势是，第一个规则的项集作为特定事务项集的子集出现的“频率”高于第二个规则。根据关联规则挖掘原理，第一个规则的项集更有可能成为潜在的规则“候选”。
至少有两个主要参数可以用于量化和衡量对新生成规则的兴趣，例如“支持度”或“置信度”指标。“支持度”指标是第一个参数，通过它我们可以确定特定规则的兴趣和重要性。
要计算支持度指标值，我们必须首先找到新规则的项集出现的事务项集数量 $\begin{align}count(I \subseteq t_s | t_s \in T)\end{align}$，然后，将此数量除以事务总数 |T|
事实上，支持度指标值实际上是规则项集在事务集 T 中出现的概率。具有最高概率值的规则被认为是最有趣和最重要的，而具有最小概率值的规则则微不足道。
“置信度”指标是衡量规则兴趣和重要性的另一个有用指标。正如我们之前已经讨论过的，为了生成新规则，我们必须在特定条件下合并两个规则。置信度实际上是两个依赖规则在事务集中一起出现的概率。为了获得置信度值，我们必须首先分别找到第一个规则 $\begin{aligned}supp(I^{'})\end{aligned} $ 和第二个规则 $\begin{aligned}supp(I^{''})\end{aligned} $ 的支持度值。之后，我们必须将第一个规则的支持度值除以第二个规则的支持度值
与支持度指标本身相比，使用置信度指标可以提供更灵活的兴趣计算。与支持度指标相比，置信度指标允许通过消除支持度值不显著的情况来解决所谓的“稀有项问题”，因为有趣且重要的规则偶尔会出现频率较低的情况。
此外，在 Apriori 算法讨论中，我们将找出如何使用上面列出的这些公式来挖掘有趣且有意义的规则。
反单调性原理
上一段讨论的支持度（support）和置信度（confidence）指标都满足“向下封闭引理”，这意味着给定项集的支持度值和置信度值不能分别超过其所有子集的支持度最小值和置信度最小值。正因为如此，根据反单调性（anti-monotonicity）属性，一个有趣规则项集的所有可能子集都被认为是有趣的规则。换句话说，如果一个项集是频繁的，那么它的所有子集也是频繁的。例如：如果两条规则是有趣的，那么生成的新规则也是有趣的。既然我们已经讨论了关联规则，现在是时候讨论一下特定算法了，它能让我们快速可靠地在通常巨大的事务数据集上执行关联规则学习（ARL）。
Apriori 算法
在本段中，我们将介绍并阐述 Apriori 算法，该算法允许我们执行可扩展的优化关联规则学习。在开始之前，让我们仔细看看使用经典暴力算法执行的关联规则查找过程。根据暴力算法和数据的格结构，我们必须基于通常很大的 1-项集 I（包含从 T 中每个事务的项集 $\begin{align}t_s\end{align}$ 中提取的所有项）生成长度从 2 到 N 的所有可能的项集。N 是生成的规则的最大长度。此值通常等于 I 中项的总数。最初，我们将这些 k-项集中的每一个都视为潜在的规则候选。这是一个复杂的迭代过程，在每次迭代中，我们通常通过将 I 中的每个项 $\begin{align}I (\forall i_k \in I)\end{align}$ 附加到从集合中检索到的当前规则的现有 k-项集来生成多个 (k+1)-项集。以下过程从规则开始，其 1-项集只包含一个项，并且具有最大出现频率。在此过程中，我们将初始规则的 1-项集与 I 中的每个项合并，以获得一组 2-项集规则。之后，我们需要将 I 中的每个项附加到所有后续的 2-项集，以获得多个 3-项集规则，依此类推，直到最终得到一个巨大的规则候选集。由于我们已经生成了最终的规则候选集，我们必须计算每个规则候选的支持度和置信度值，然后只过滤掉那些支持度值大于最小支持度值 ($\begin{align}supp(I)>min\_supp\end{align}$) 且置信度值大于最小置信度值 ($\begin{align}conf(I)>min\_conf\end{align}$) 的规则候选。对于通常巨大的数据集，以下过程可能会变得“浪费”，对 CPU 和系统内存使用产生很大影响。
Agrawal 和 Srikant 提出的 Apriori 过程提供了一种不同于暴力算法本身的规则候选生成方法。根据 Apriori 算法，我们将主要执行“广度优先”搜索，生成新规则并仅为那些支持度和置信度指标值超过最小阈值的候选计算支持度和置信度值。这完全符合前面讨论的反单调性原理。具体来说，如果两个规则候选具有足够的支援度和置信度度量值，则生成的新规则具有完全相同或更高的这些度量值。以下方法可以大大减少计算量和系统内存消耗。在规则挖掘过程结束时，我们最终将得到一个所谓的“截断”的新规则集，因为我们不再需要像使用经典暴力方法那样生成所有可能的规则候选变体。
下面列出了提供 Apriori 算法一般理解的伪代码
$\begin{aligned} I = \{ \forall i_n | \forall i_n \in t_s, t_s \in T \}\end{aligned}$
$\begin{aligned} R_1\leftarrow I, k\leftarrow2\end{aligned}$
$\begin{aligned} while \ R_{k-1}\neq \oslash \ do \end{aligned}$
$\begin{aligned} \quad R_k\leftarrow \{ r_i \cup \{r_j\}|(r_i,r_j) \in R_k, r_i\notin r_j \} \end{aligned}$
$\begin{aligned} \quad foreach \ transaction \ t_s \in T \ do \end{aligned}$
$\begin{aligned} \quad \quad R_t\leftarrow \{r_z | r_z\in R_k, r_z \subseteq t_s\} \end{aligned}$
$\begin{aligned} \quad R_k\leftarrow \{r_s|r_s \in R_t, conf(r_s) > min\_conf\} \end{aligned}$
$\begin{aligned} \quad k \leftarrow k + 1 \end{aligned}$
$\begin{aligned} return \bigcup_k R_k\end{aligned}$
，其中 I - 初始 1-项集，包含从 T 中每个事务 $\begin{aligned}t_s\end{aligned}$ 中提取的所有唯一项，$\begin{aligned}R_1\end{aligned}$ - 包含所有待分析 1-项集的规则集，k - 每次迭代的项集长度，$\begin{aligned}R_k\end{aligned}$ - 第 k 次迭代期间生成的 k 大小规则候选集，$\begin{aligned}R_t\end{aligned}$ - 满足指定条件 ($\begin{aligned}\forall r_z \subseteq t_s \end{aligned}$) 的新规则候选子集，$\begin{aligned}r_z\end{aligned}$ - 包含在事务 $\begin{aligned}t_s\end{aligned}$ 中的 $\begin{aligned}R_k\end{aligned}$ 中的 k-项集，$\begin{aligned}r_s\end{aligned}$ - 满足指定条件 ($\begin{aligned}conf(\forall r_s) > min\_conf\end{aligned}$) 的 $\begin{aligned}R_t\end{aligned}$ 中的 k-项集。
步骤 1：初始化
初始化是 Apriori 算法的第一个阶段，在此阶段我们将创建一个初始的大型 1-项集 $\begin{aligned}R=\{ \forall i_k | \forall i_k \in t_s, t_s \in T\}\end{aligned} $，由从每个事务的项集 $\begin{aligned}t_s\end{aligned} $ 中提取的项组成。为此，我们必须应用以下简单的算法。对于 T 中的每个事务，我们遍历项集，对于每个特定项 $\begin{aligned}\forall i_n\end{aligned} $，执行一个简单的检查，看该项是否已存在于结果项集 R 中。如果不存在，我们需要将此项附加到结果集 R 中，以便在执行特定计算后，我们得到一个唯一项集 $\begin{aligned}R = \{\forall i_n | count(\forall i_n) = 1\}\end{aligned} $。在后续阶段，我们将使用这个 1-项集 R 作为规则候选的初始集合。
步骤 2：生成潜在规则候选集
生成规则候选集是 Apriori 算法的主要阶段。在此阶段，我们将根据先前迭代获得的现有 (k-1) 项集迭代生成各种 k 项集。项集大小的初始值为 k = 2。在每次迭代中，我们将为 k 从 2 到 N 的每个值生成一组规则候选。为此，我们需要从前一次迭代（大小等于 (k – 1)）生成的子集中提取已有的规则。之后，我们通过执行一系列嵌套迭代来生成特定对的规则候选项集。在每次迭代中，我们简单地将当前 (k-1) 项集 $\begin{aligned}R_i\end{aligned}$ 与所有后续 (k-1) 项集 $\begin{aligned}R_j\end{aligned}$ 结合，从而生成每个新的规则候选。Apriori 算法的一个非常重要的优化是，我们不再需要将 (k-1) 项集 $\begin{aligned}R_i\end{aligned}$ 与所有其他可能的 (k-1) 项集 $\begin{aligned}R_j\end{aligned}$ 结合，因为我们对等效规则的生成不感兴趣。这反过来又可以大大减少结果规则集的潜在大小并优化性能。
对于每对规则，我们执行验证，检查第一个项集 $\begin{aligned}R_i\end{aligned}$ 是否不包含在第二个项集 $\begin{aligned}R_j\end{aligned}$ 中 (R_i∉R_j)。如果不是，我们执行第二次验证，检查两个项集的置信度值是否都超过最小阈值 ($\begin{aligned}conf(R_i) > min\_conf\end{aligned}$,$\begin{aligned}conf(R_j) > min\_conf\end{aligned}$)。如果是，我们将这两个 (k-1) 项集合并以生成新的规则候选。对于新的规则候选，我们也计算置信度值。最后，我们需要将新生成的候选附加到正在生成的新规则候选集，并继续进行下一次迭代以生成新的 (k+1) 项集规则候选集。我们通常继续进行以下计算过程，直到最终获得一组新的规则，其项集大小等于 N (k=N)。
请注意，在这种特殊情况下，我们不使用支持度值来确定新规则的兴趣，而是使用置信度指标的度量，这可以增加挖掘过程的灵活性（有关此主题的更多信息，请参阅本文的“有趣规则挖掘”段落）。
根据上面提到的许多优化，我们不再需要估计最小置信度阈值。此值为常数，等于 min_conf=0.45，这意味着我们期望找到兴趣概率大于 45% 的新规则。此外，我们不需要像 Agrawal 和 Srikant 最初建议的那样，为每个新规则增加计数并将其用于规则兴趣估计。最小置信度阈值等于 0.45 是大多数现有关联规则挖掘算法的样本常数值。
第 3 步：寻找潜在有趣且有意义的规则
执行上述计算的结果实际上是一个规则集。此时，我们的目标是筛选出其中最有趣和最有意义的规则。为此，我们需要执行一个简单的线性搜索，以找到所有项集大小最大的规则。具体来说，我们将遍历在上一步中获得的新规则集，并对每个规则的项集执行检查，看计算出的置信度值是否超过最小置信度阈值。如果是，我们将此类规则添加到结果的有趣规则集中。
第 4 步：执行数据分类
数据分类是 Apriori 算法的最后阶段，非常简单。在此阶段，我们将找到集合 R 中所有项集包含类别值的规则。为此，我们将使用与我们在上面简要讨论的第 3 步中已经完成的相同简单的线性搜索。假设我们给定一组类别 $\begin{aligned}C=\{c_1,c_2,c_3,…,c_{m-1},c_m\}\end{aligned} $。对于每个类别，$\begin{aligned}\forall c_q\end{aligned}$，我们将在规则集 R 中执行线性搜索，以找到其项集包含当前类别值的规则。我们将把这些规则中的每一个添加到与特定类别值相关联的结果集中。
评估与性能优化
正如我们已经讨论过的，与传统的暴力算法和其他类似算法相比，使用 Apriori 算法带来了更高的性能和效率。具体来说，暴力算法初始变体的复杂度可以估计为 $\begin{aligned}p=O(2^i * N)\end{aligned}$，其中 i - 算法每次 k 迭代期间的规则候选数量，N - 迭代总次数。
Agrawal 和 Srikat 在 1994 年提出的 Apriori 算法能够执行与暴力算法相同的关联规则挖掘，同时将复杂度降低到 $\begin{aligned}p=O(i^2 * N)\end{aligned}$。具体来说，Apriori 算法的以下实现至少具有以下计算复杂度
此外，如果您仔细查看实现 Apriori 算法的 C++11 代码，您会注意到一些执行新规则候选生成的顺序代码片段可以并行运行。为此，我们将使用 Intel C++ 19.0 编译器和 OpenMP 性能库，这可以大大提高在对称多核 Intel CPU 上执行以下代码时的性能加速，为执行中的 Apriori 算法的传统顺序代码提供了足够的扩展性。
使用代码
Apriori 算法的实现
由于 Apriori 算法基本上依赖于执行一系列集合论操作，我们实现了一些函数，允许我们对用于存储正在处理的项集的向量对执行并集、交集、附加和其他比较操作。以下是实现这些函数的 C++ 代码片段
以下函数实现了基本的集合并集操作
std::vector<std::string> union_vec(
const std::vector<std::string>& v1,
const std::vector<std::string>& v2)
{
// Declare a resultant union vector
std::vector<std::string> union_vector;
// Iterate through the input vector v1
for (auto it = v1.begin(); it != v1.end(); it++)
// For each element in v1, find an element
// with the same value in the input vector v2
if (std::find_if(v2.begin(), v2.end(), \
[&](const std::string& str) { return str == *it; }) != v2.end())
// If value of the current element in v1 is found in v2,
// then add this value to the resultant union vector
union_vector.push_back(*it);
// Return the vector of union elements
return union_vector;
}
执行交集操作的函数主要基于执行上面列出的 union_vec 函数
std::vector<std::string> intersect_vec(
const std::vector<std::string>& v1,
const std::vector<std::string>& v2)
{
// Declare a resultant intersection vector
std::vector<std::string> intersect_vector;
// Find a union of two vectors v1 and v2
std::vector<std::string> union_vector = union_vec(v1, v2);
// Declare vector v and fill it with element of vector v1
std::vector<std::string> v(v1);
// Insert elements of vector v2 into vector v
v.insert(v.end(), v2.begin(), v2.end());
// Sort elements of the vector v
std::sort(v.begin(), v.end());
// Prune all duplicate elements in vector v
v.erase(std::unique(v.begin(), v.end()), v.end());
// Iterate through the vector v
for (auto it = v.begin(); it != v.end(); it++)
// For each element in v, find an element
// with the same value in the union vector
if (std::find_if(union_vector.begin(), union_vector.end(),
[&](const std::string& str)
{ return str == *it; }) == union_vector.end())
// If value of the current element in v is found
// in the union vector then add this value to
// the resultant intersection vector
intersect_vector.push_back(*it);
// Return the intersection vector
return intersect_vector;
}
还有一个基本函数允许合并两个项集向量
std::vector<std::string> append_vec(
const std::vector<std::string>& v1,
const std::vector<std::string>& v2)
{
// Declare vector v and fill it with element of vector v1
std::vector<std::string> v(v1);
// Insert elements of vector v2 into vector v
v.insert(v.end(), v2.begin(), v2.end());
// Sort elements of the vector v
std::sort(v.begin(), v.end());
// Prune all duplicate elements in vector v
v.erase(std::unique(v.begin(), v.end()), v.end());
// Return the resultant vector v
return v;
}
为了比较两个项集向量并检查第一个向量是否不包含在第二个向量中，我们必须实现下面列出的特定函数
bool compare_vec(
const std::vector<std::string>& v1,
const std::vector<std::string>& v2)
{
// Declare vector v and assign it vector v2
std::vector<std::string> v = v2;
// Find union vector based on values from v1 and v2
std::vector<std::string> v_u = union_vec(v1, v2);
// If the union vector is not empty, return "true", otherwise "false"
return (v_u.size() != 0) ? true : false;
}
此外，还有几个函数允许验证第一个向量是否包含第二个向量，以及项集是否包含特定项
bool contains(const std::vector<std::string>& v,
const std::string& value)
{
// Find the value in vector v
// Return "true" if the value is found, otherwise "false"
return std::find_if(v.begin(), v.end(),
[&](const std::string& s) { return s == value; }) != v.end();
}
bool contains_vec(const std::vector<std::string>& v1,
const std::vector<std::string>& v2)
{
bool found = false;
// Iterate through the vector v2,
// until an element contained in both v1 and v2 is found
for (auto it = v2.begin(); it != v2.end() && !found; it++)
// For each element of v2, perform a check
// if the current element of v2 is found in v1
// As the result, assign found to "true" if the current
// element is found and "false" unless otherwise
found = contains(v1, *it) ? true : false;
// Return the value of found variable
return found;
}
为了从集合中的每个事务中提取所有唯一项，我们实现了以下函数
std::vector<std::string> get_items(
const std::vector<std::vector<std::string>>& T)
{
// Declare a vector of items
std::vector<std::string> items;
// Iterate through the vector of transactions T
for (auto it = T.begin(); it != T.end(); it++)
// Insert each element from current
// transaction itemset into the following items vector
items.insert(items.end(), it->begin(), it->end());
// Sort vector of items
std::sort(items.begin(), items.end());
// Prune all duplicate items
items.erase(std::unique(items.begin(), items.end()), items.end());
return items;
}
为了将一个项转换为一个单项向量，我们编写了以下杂项函数
std::vector<std::string> vec1d(const std::string& str) {
// Return vector containing one element equal to str
return std::vector<std::string>(1, str);
}
为了能够读取类别数据和事务集，我们实现了以下用于从特定文件流读取数据的函数
std::vector<APR_ENTITY>
read_sl_csv_file(const std::string filename)
{
// Create an file input stream
std::ifstream ifs(filename, \
std::ifstream::in | std::ifstream::ate);
// Declare a vector of entities
std::vector<APR_ENTITY> v_ent;
// Get the file size
std::size_t file_size = (std::size_t)ifs.tellg();
// Allocate a buffer to store the data from file
char* buf = (char*)malloc(++file_size);
// Read a single-line data from file
ifs.seekg(ifs.beg); ifs.getline(buf, ++file_size);
// Declare an entity object
APR_ENTITY apr_ent;
std::memset((void*)& apr_ent, 0x00, sizeof(APR_ENTITY));
const char* delim = ",";
// Find first token in buffer
char* token = std::strtok(buf, delim);
// Extract all tokens separated by ',' character
while (token != nullptr)
{
std::uint32_t ci = 0L;
// Allocate buffer to store an entity data
char* m_value_buf = (char*)malloc(256 * sizeof(char));
// Extract the data from the entity formatted string
if (sscanf(token, "%[^:]:%d", m_value_buf, &ci) > 0)
{
// Assign the values extracted to the specific variables of entity object
apr_ent.m_value = std::string(m_value_buf); apr_ent.m_ci = ci;
// Add the entity object to the vector of entities
// and extract the next token from the string data
v_ent.push_back(apr_ent); token = std::strtok(nullptr, delim);
}
}
// Deallocate buffer and close the input file stream
free(buf); ifs.close();
// Return the resultant vector of entities
return v_ent;
}
std::vector<std::vector<std::string>> \
read_data_from_csv_file(const std::string filename)
{
// Declare a vector of transactions
std::vector<std::vector<std::string>> trans_v;
// Create an input file stream
std::ifstream ifs(filename, std::ifstream::in);
// Allocate buffer for each line of file
char* buf = (char*)malloc(sizeof(char) * 4096);
// Perform a check if this is not the end of file
while (ifs.eof() == false && ifs.peek() >= 0)
{
// Declare a tokens buffer
std::vector<std::string> tokens_v;
// Read the current line from file
const char* delim = ","; ifs.getline(buf, 4096);
// Extract the first token from the current string
char* token = std::strtok(buf, delim);
// Extract all tokens separated by ',' character
while (token != nullptr)
{
// Add the current token (i.e. item) to the vector of tokens
tokens_v.push_back(std::string(token));
// Extract the next token
token = std::strtok(nullptr, delim);
}
// Add all items in the current vector to the vector of transactions
trans_v.push_back(tokens_v);
}
// Deallocate buffer and close the input file stream
free(buf); ifs.close();
// Return the vector of transactions
return trans_v;
}
在执行关联规则挖掘之前，我们必须通过实现以下函数来初始化数据模型
void init(const std::vector<std::string>& items,
std::vector<ASSOC_R_CAND>& R)
{
// Declare a rule candidate object
ASSOC_R_CAND asr_item;
std::memset((void*)& asr_item, 0x00, sizeof(ASSOC_R_CAND));
// Iterate through the vector of items
for (auto it = items.begin(); it != items.end(); it++) {
// For each item, assign the value of confidence equal to .0f
asr_item.m_conf = .0f;
// Create a single-element vector and assign it to the itemset variable
asr_item.m_itemset = utils::vec1d(*it);
// Add the current rule candidate object to the vector of rule candidates
R.push_back(asr_item);
}
}
std::double_t get_conf_rule(
const std::vector<std::vector<std::string>>& T,
std::vector<std::string>& rule)
{
// Declare a count variable and assign it to 0
std::double_t count = 0L;
// Iterate through the vector of transactions
for (auto tran_it = T.begin(); tran_it != T.end(); tran_it++)
// For each current transaction itemset, perform a check
// if the union vector of the current itemset and the itemset of
// the input rule has the same size as the input rule itemset vector
if (utils::union_vec(*tran_it, rule).size() == rule.size())
// If so, increment the count variable by 1
count++;
// Return the value of count variable
return count;
}
void get_conf(
const std::vector<std::vector<std::string>>& T,
std::vector<ASSOC_R_CAND>& R)
{
// Declare a count variable and assign it to 0
std::double_t count = 0L;
// Iterate through the vector of rule candidates
for (auto asr_it = R.begin(); asr_it != R.end(); asr_it++)
// Compute the value of count for the current rule candidate
if ((count = get_conf_rule(T, asr_it->m_itemset)) > 0)
// If the value of count is greater than 0, then
// divide this value by the value of the overall transactions count
// assign it to the current rule candidate m_conf member variable
asr_it->m_conf = count / (std::double_t)T.size();
}
此外，为了能够操作规则项集，我们还必须实现一些辅助函数，允许我们执行搜索以查找其项集满足特定条件的规则
template<typename Predicate>
std::vector<ASSOC_R_CAND> find_rules(std::vector<ASSOC_R_CAND>& R, Predicate pred)
{
// Declare a vector of rule candidates iterator
// Declare a resultant vector of rule candidates
// that satisfy a condition specified as lambda expression
auto it = R.begin(); std::vector<ASSOC_R_CAND> ret_v;
// Find each item in the vector of rule candidates that
// satisfies a certain condition, and add it to the resultant
// vector of rule candidates found
while ((it = std::find_if(it, R.end(), pred)) != R.end())
ret_v.push_back(*it++);
// Return the resultant vector of rule candidates
return ret_v;
}
bool contains_rule(const std::vector<ASSOC_R_CAND>& R,
std::vector<std::string>& rule)
{
bool found = false;
// Declare a rule candidates vector iterator
auto asr_it = R.begin();
// Perform a search to find the first occurrence
// of a rule candidate object contained in the
// vector of rule candidates R
while (asr_it != R.end() && !found)
// For each rule candidate object, perform a check
// if a union vector of both the current rule candidate itemset
// and the input rule candidate itemset has the same size as the
// input rule itemset. If so, assign the value of "true" to the found
// variable, and assign "false", unless otherwise
found = utils::union_vec((asr_it++)->m_itemset,
rule).size() == rule.size() ? true : false;
// Return the value of found variable
return found;
}
基于 Apriori 算法执行关联规则学习的函数实现如下
std::vector<APR_RULE> \
apriori(const std::vector<APR_ENTITY>& C,
const std::vector<std::vector<std::string>>& T, bool thorough = false)
{
// Declare a mutex lock object
omp_lock_t s_lock;
// Init the mutex lock object
omp_init_lock(&s_lock);
// Retrieve the vector of items
std::vector<std::string> \
items = utils::get_items(T);
// Assign the value of the rooted class
std::string rooted = C[0].m_value;
// Declare a vector of rule candidates
std::vector<ARL::ASSOC_R_CAND> rules_cand_v;
// Init the vector of rule candidates and compute
// the confidence value for each specific rule candidate
ARL::init(items, rules_cand_v); ARL::get_conf(T, rules_cand_v);
// For each itemset of size k, generate rule candidates
// and estimate the value of confidence of each new rule
for (std::uint64_t k = 2; k <= items.size(); k++)
{
// Find all rule candidates which itemset size is equal to (k-1)
std::vector<ARL::ASSOC_R_CAND> k_rule_cand_v = \
ARL::find_rules(rules_cand_v, \
[&](const ARL::ASSOC_R_CAND asr) { \
return asr.m_itemset.size() == (k - 1); });
// Declare a vector of new rule candidates
std::vector<ARL::ASSOC_R_CAND> rules_cand_new_v;
// Get the value of rule candidates vector size
std::size_t k_rule_cand_v_size = k_rule_cand_v.size();
// Generate pairs of new rule candidates
// (Note: This code is executed in parallel)
#pragma omp parallel for collapse(2) schedule(guided, 4)
for (std::uint64_t i = 0; i < k_rule_cand_v_size; i++)
for (std::uint64_t j = 0; j < k_rule_cand_v_size; j++)
{
// Perform a check if the value of j is greater than the value of i
// and we're not generating redunant equivalent rule candidates
if (j <= i) continue;
// For each pair of the rule candidates, perform a check
// if the rooted item is not contain in either first or second
// rule candidate itemset
if ((utils::contains(k_rule_cand_v[i].m_itemset, rooted)) ||
(utils::contains(k_rule_cand_v[j].m_itemset, rooted))) continue;
// Perform a check if the value of confidence
// for both the first and second
// rule candidate is greater than the specific
// confidence threshold value, or
// if we're processing the 1 or 2-itemset rule candidates
if ((k_rule_cand_v[i].m_conf > min_conf) &&
(k_rule_cand_v[j].m_conf > min_conf) || ((k - 1) <= 2))
{
// Spawn a parallel task
#pragma omp task
{
// If both rule candidates satisfies the condition above,
// then perform a check if the first rule candidate does not
// contain the second rule candidate.
if ((!utils::compare_vec(k_rule_cand_v[i].m_itemset,
k_rule_cand_v[j].m_itemset)) || ((k - 1) <= 2))
{
// Declare a new rule candidate object
ARL::ASSOC_R_CAND asr_rule;
// If the condition above is true or
// we're still processing the 1 or 2-itemset candidates,
// then merge both first and
// second rule candidates itemset
asr_rule.m_itemset = utils::append_vec(\
k_rule_cand_v[i].m_itemset,
k_rule_cand_v[j].m_itemset);
// Compute the value of support for the first candidate
std::double_t rule_supp = \
ARL::get_conf_rule(T, k_rule_cand_v[i].m_itemset);
// Compute the value of support for
// the new rule candidate
std::double_t rule_new_supp = \
ARL::get_conf_rule(T, asr_rule.m_itemset);
// Compute the value of confidence for
// the current new rule candidate
asr_rule.m_conf = rule_new_supp / rule_supp;
// Synchronize the following code
// by setting the mutex lock
omp_set_lock(&s_lock);
// Perform a check if the new rule candidate
// is not in the vector of new rule candidates
// and the value of confidence
// exceeds the specified confidence threshold
if ((!ARL::contains_rule(rules_cand_new_v, \
asr_rule.m_itemset)) && (asr_rule.m_conf > min_conf))
// If so, add the rule candidate to the vector
// of new rule candidates
rules_cand_new_v.push_back(asr_rule);
// Unset the mutex lock
omp_unset_lock(&s_lock);
}
}
}
}
// Insert the vector of new candidates produced into
// the rule candidates vector
rules_cand_v.insert(rules_cand_v.end(), \
rules_cand_new_v.begin(), rules_cand_new_v.end());
}
// Declare an output vector
std::vector<APR_RULE> output_v;
// Iterate through the vector of classes
// (Note: This code is executed in parallel)
#pragma omp parallel for schedule(dynamic, 4)
for (auto c_it = C.begin() + 1; c_it != C.end(); c_it++)
{
// For each class value, find all rule candidates produced,
// for which value of confidence exceeds the threshold specified
// and an itemset each rule candidate contains a class value
std::vector<ARL::ASSOC_R_CAND> rules_assoc_v = \
ARL::find_rules(rules_cand_v, [&](const ARL::ASSOC_R_CAND& asr) { \
return asr.m_conf > min_conf && \
utils::contains(asr.m_itemset, c_it->m_value);
});
if (rules_assoc_v.size() > 0)
{
// Declare a vector of hold string values of
// items from each rule candidate itemset that
// satisfies the condition above
std::vector<std::string> \
merged(rules_assoc_v.begin()->m_itemset);
// Iterate through the resultant vector of rule
// candidates (Note: This code is executed in parallel)
#pragma omp parallel for schedule(dynamic, 4)
for (auto rl_it = rules_assoc_v.begin() + 1;
rl_it != rules_assoc_v.end(); rl_it++)
// Append all items in the itemset of each rule candidate
// to the vector of items for the current class value
merged = utils::append_vec(merged, rl_it->m_itemset);
// Declare an association rule object
APR_RULE apr_rule;
std::memset((void*)& apr_rule, 0x00, sizeof(APR_RULE));
// Assign the m_cs variable to a class name value
apr_rule.m_cs = std::string(c_it->m_value);
// Assign the m_itemset variable to the vector of merged items
apr_rule.m_itemset = std::vector<std::string>(merged);
// Remove an item, which value is equal to the value of class name
apr_rule.m_itemset.erase(std::remove_if(\
apr_rule.m_itemset.begin(), apr_rule.m_itemset.end(), \
[&](const std::string s) { return s == c_it->m_value; }));
// Add the rule to the output vector
output_v.push_back(apr_rule);
}
}
// Return the output vector
return output_v;
}
}
Apriori 事务数据集生成器
为了能够评估本文讨论的 Apriori 算法的实现，我们还必须实现一段 C++11 代码，用于生成各种事务数据集以供测试。
以下是实现数据集生成器功能的代码片段
std::vector<APR_ENTITY>
read_sl_csv_file(const std::string filename)
{
// Create an input file stream
std::ifstream ifs(filename, \
std::ifstream::in | std::ifstream::ate);
// Declare a vector of entities
std::vector<APR_ENTITY> v_ent;
// Get the file size
std::size_t file_size = (std::size_t)ifs.tellg();
// Allocate a buffer to store the data from file
char* buf = (char*)malloc(++file_size);
// Read a single-line data from file
ifs.seekg(ifs.beg); ifs.getline(buf, ++file_size);
// Declare an entity object
APR_ENTITY apr_ent;
std::memset((void*)& apr_ent, 0x00, sizeof(APR_ENTITY));
const char* delim = ",";
// Find first token in buffer
char* token = std::strtok(buf, delim);
// Extract all tokens separated by ',' character
while (token != nullptr)
{
std::uint32_t ci = 0L;
// Allocate buffer to store an entity data
char* m_value_buf = (char*)malloc(256 * sizeof(char));
// Extract the data from the entity formatted string
if (sscanf(token, "%[^:]:%d", m_value_buf, &ci) > 0)
{
// Assign the values extracted to the specific variables of entity object
apr_ent.m_value = std::string(m_value_buf); apr_ent.m_ci = ci;
// Add the entity object to the vector of entities
// and extract the next token from the string data
v_ent.push_back(apr_ent); token = std::strtok(nullptr, delim);
}
}
// Deallocate buffer and close the input file stream
free(buf); ifs.close();
// Return the resultant vector of entities
return v_ent;
}
std::vector<std::double_t> \
get_classes_dist(const std::uint64_t c_max_count)
{
std::double_t cr_start = 0, \
cr_end = cr_start + 1;
// Declare a vector of ratio values
std::vector<std::double_t> r_vals;
// Declare a count variable and assign it the
// value of the number of ratio values
std::int64_t count = c_max_count;
// Find each ratio value
while (--count >= 0)
{
// Create a real values distribution in the
// interval from cr_start to cr_end
std::uniform_real_distribution<
std::double_t> c_dice(cr_start, cr_end);
// Generate a real pseudo-random value
std::double_t value = c_dice(g_mersenne);
// If the count value is greater than 0, then
// compute a length of interval from the cr_start to value,
// otherwise compute the length from cr_start to 1
r_vals.push_back(((count > 0) ? \
(value - cr_start) : (1 - cr_start)));
// Compute the new values of cr_start equal to value
// and cr_end as the cr_start incremented by the value of
// division of the length of the remaining interval by
// the overall number of remaining items to generate
cr_start = value; cr_end = \
cr_start + (1 - value) / (std::double_t)count;
}
// Return vector of ratios
return r_vals;
}
void apriori_gen(const std::uint64_t g_t_size,
const std::string cs_filename,
const std::string ent_filename,
const std::string out_filename)
{
// Create an output file stream
std::ofstream ofs(out_filename, std::ofstream::out);
// Read class entities from file
std::vector<APR_ENTITY> classes = \
read_sl_csv_file(cs_filename);
// Read item entities from file
std::vector<APR_ENTITY> entities = \
read_sl_csv_file(ent_filename);
// Declare a maxima transaction length value
const std::uint64_t t_length_max = entities.size();
// Declare a maxima number of classes per each transaction
const std::uint64_t c_max_count = classes.size() - 2;
// Declare a count variable and assign it to
// the value of the overall number of transactions
std::int64_t count = g_t_size - 1;
// Generate each transaction
while (count >= 0)
{
// Declare a vector of items
std::vector<std::string> trans_v;
// Create an integer random distribution in
// the interval from 2 to a transaction's maxima length
std::uniform_int_distribution<
std::uint64_t> tl_dice(2, t_length_max);
// Declare c_size variable and assign it to the maxima number of classes
std::uint64_t c_size = c_max_count;
// Generate a pseudo-random value of transaction size
std::uint64_t t_size = tl_dice(g_mersenne);
// Get entropy distribute of items containment ratios
// for each specific class
std::vector<std::double_t> cr_ratio_v = \
get_classes_dist(c_size);
// Sort the vector of ratio values in the descending order
std::sort(cr_ratio_v.begin(), cr_ratio_v.end(),
[&](std::double_t v1, std::double_t v2) { return v1 > v2; });
// Create an integer random distribution
std::uniform_int_distribution<
std::uint64_t> cr_dice(0, classes.size() - 1);
// Declare a vector of classes
std::vector<std::uint64_t> cs_v;
// Generate a vector of class identifier random values
for (std::uint64_t i = 0; i < c_size; i++)
{
std::uint64_t ci = 0L;
// Preserve the values duplicates
do {
// Generate a random class identifier value
ci = (classes.begin() + cr_dice(g_mersenne))->m_ci;
} while ((std::find(cs_v.begin(), cs_v.end(), ci) != cs_v.end()));
// Add the value generated to the vector of class identifiers
cs_v.push_back(ci);
}
// Add the class value to the itemset of the current transaction
trans_v.push_back((classes.begin() + cs_v[0])->m_value);
// Iterate through the vector of class identifiers
for (std::uint64_t i = 0; i < c_size; i++)
{
// Declare a vector of items
std::vector<APR_ENTITY> ent_v;
// Declare an entities vector iterator
auto ent_it = entities.begin();
// Find each item in the entities vector, which class identifier
// is equal to the class identifier for the current class value
while ((ent_it = std::find_if(ent_it, entities.end(),
[&](const APR_ENTITY& apr_ent)
{ return apr_ent.m_ci == cs_v[i]; })) != entities.end())
ent_v.push_back(*(ent_it++));
// Determine the number of items belonging to a current class
// based on the class ratio value
std::uint64_t cr_size = \
((std::uint64_t)std::ceil(ent_v.size() * cr_ratio_v[i]));
// Create an integer random distrubution
std::uniform_int_distribution<
std::uint64_t> cr_dice(0, ent_v.size() - 1);
std::int64_t cr_count = cr_size;
// Produce a set of random items
while (--cr_count >= 0)
{
std::string value = "\0";
// Preserve duplicates
do {
// Get the value of a random item
value = (ent_v.begin() + \
cr_dice(g_mersenne))->m_value;
} while (std::find(trans_v.begin(),
trans_v.end(), value) != trans_v.end());
// Add the random item value to the vector of items
trans_v.push_back(value);
}
}
// Find a rooted class object
auto c_it = std::find_if(classes.begin(), classes.end(),
[&](const APR_ENTITY& apr_ent) { return apr_ent.m_ci == 0; });
// Find the current transaction's itemset in the set of transactions
// If this itemset is not found, then add it to the vector of transactions
if (std::find_if(trans_v.begin(), trans_v.end(),
[&](const std::string& s) {
return s == c_it->m_value; }) == trans_v.end())
trans_v.push_back(c_it->m_value);
// Avoid generating short transactions
if (trans_v.size() > 2)
{
std::string transaction = "\0"; count--;
// Convert an itemset vector into a comma-separated string
for (auto it = trans_v.begin(); it != trans_v.end(); it++)
transaction += *it + ((it == trans_v.end() - 1) ?
((count != -1) ? '\n' : '\0') : ',');
// Write the current string to file stream
std::size_t ts_length = transaction.length();
ofs.write(transaction.c_str(), (count != -1) ? ts_length : ts_length - 1);
}
}
// Close the output file stream
ofs.close();
}
兴趣点
很长一段时间以来，我一直在寻找一种算法，它能执行数据分类，并提供比常用的 k-means 聚类和朴素贝叶斯分类器更好的结果。最终，我读了一系列文章，其中作者介绍了关联规则学习的概念，用于对各种数据进行分类，包括经典的暴力算法和可扩展的优化 Apriori 算法，这些算法可用于关联规则挖掘。最后，我印象深刻的是，与使用人工神经网络和其他人工智能机器学习算法相比，关联规则学习和基于此过程执行分类从未如此简单。Apriori 算法也“非常适合”执行数据分类，并将这些数据排列成层次数据结构，例如从动态流中实时获取的数据构建各种类别分类。
历史
- 2019年7月3日 - 发布本文第一版