无监督学习与生成式人工智能（MEAP）（二）（2）

无监督学习与生成式人工智能（MEAP）（二）（1）https://developer.aliyun.com/article/1522535

4.5 等价类聚类和自底向上格遍历(ECLAT)

接下来我们会在这一节学习等价类聚类和自底向上格遍历算法，或者称之为 ECLAT，有人认为这个算法在速度和实现的方便性方面比 Apriori 更好。

ECLAT 使用深度优先搜索方法。这意味着 ECLAT 沿着数据集以纵向方式进行搜索。它从根节点开始。然后进入更深的一层，并继续直到达到第一个终端注释。假设终端节点在 X 级。一旦到达终端节点，算法然后返回一步，并到达级别（X-1），并继续直到再次找到终端节点。让我们通过表 4.6 中显示的树状图来理解这个过程。

图 4.6 ECLAT 算法过程的树状图。 它从 1 开始，直到 16 结束。

ECLAT 将采取以下步骤：

1. 算法从根节点 1 开始。
   
2. 然后它向根节点 2 深入一层。
   
3. 然后它会继续向更深的一层，直到达到终端节点 11。
   
4. 一旦它到达终端注释 11，然后退回一步，到达节点 5。
   
5. 然后算法搜索是否有可用的节点。在节点 5 处，我们可以看到没有可用的节点。
   
6. 因此，算法再次退回一步，它达到了节点 2。
   
7. 在节点 2 处，算法再次探索。它发现可以到达注释 6。
   
8. 因此，算法进入节点 6，并开始探索，直到达到终端节点 12。
   
9. 这个过程会一直持续，直到所有组合耗尽。
   

显然，计算速度取决于数据集中存在的不同项目的总数。这是因为不同项目的数量定义了树的宽度。每笔交易中购买的商品将定义每个节点之间的关系。

在执行 ECLAT 时，将分析每个商品（单独或成对）。让我们使用我们已经用于 Apriori 的相同示例来更好地理解 ECLAT，如表 4.5 所示。

表 4.5 我们将用来理解 ECLAT 的数据集。 第一张发票 1001 有牛奶、鸡蛋和面包，而奶酪没有购买。

ECLAT 将经历以下步骤来分析数据集：

1. 在第一次运行中，ECLAT 将找到所有单个商品的发票号。换句话说，它会找到所有商品的个别发票号。可以在下面的表 4.6 中显示，其中牛奶在发票号 1001 和 1003 中出现，而鸡蛋出现在所有发票中。

表 4.6 每个商品所在的相应发票。牛奶出现在 1001 和 1003 号发票中，而鸡蛋出现在五张发票中。

1. 现在在下一步中，所有两个项目数据集都将如下所示地进行探索，如表 4.7 所示。例如，牛奶和鸡蛋出现在发票号码 1001 和 1003 中，而牛奶和奶酪没有出现在任何发票中。

表 4.7 现在探索了两个项目数据集。牛奶和鸡蛋出现在发票号码 1001 和 1003 中，而没有牛奶和奶酪的发票。

1. 在接下来的步骤中，所有三个项目数据集都将如表 4.8 所示进行探索。

表 4.8 在这一步中分析了三个项目数据集。我们只有两个组合。

1. 在我们的数据集中没有包含四个项目的发票。
   
2. 现在根据我们设置的支持计数值的阈值，我们可以选择规则。因此，如果我们希望使规则为真的最小交易次数等于三，那么只有一个规则符合条件，即{鸡蛋，面包}。如果我们将最小交易次数的阈值设定为两，则诸如{牛奶，鸡蛋，面包}，{牛奶，鸡蛋}，{牛奶，面包}，{鸡蛋，面包}和{鸡蛋，奶酪}等规则都符合条件。
   

现在我们将为 ECLAT 创建一个 Python 解决方案。

4.5.1 Python 实现

现在我们将使用 Python 进行 ECLAT 的执行。我们在这里使用 pyECLAT 库。数据集如下所示：

步骤 1： 我们将在这里导入库。

import numpy as np
import pandas as pd
from pyECLAT import ECLAT

步骤 2： 现在导入数据集

data_frame = pd.read_csv('Data_ECLAT.csv', header = None)

步骤 3： 这里我们正在生成一个 ECLAT 实例。

eclat = ECLAT(data=data_frame)

在上一步生成的 ECLAT 实例 eclat 中有一些属性，如 eclat.df_bin 是一个二进制数据框，eclat.uniq_ 是所有唯一项目的列表。

步骤 4： 现在我们将适配模型。我们在这里给出了最小支持度为 0.02。之后我们将打印支持度。

get_ECLAT_indexes, get_ECLAT_supports = eclat.fit(min_support=0.02,
                                                           min_combination=1,
                                                           max_combination=3,
                                                           separator=' & ')
get_ECLAT_supports

输出是

我们可以根据支持度提供的结果进行解释。对于每个项目和项目组合，我们都得到了支持度的值。例如，对于炸薯条和鸡蛋，支持度的值为 3.43%。

ECLAT 相对于 Apriori 算法具有一些优势。由于它使用深度搜索方法，因此比 Apriori 更快，计算所需的内存更少。它不会迭代地扫描数据集，因此使其比 Apriori 更快。在我们学习了最后一个算法之后，我们将再次比较这些算法。

现在我们将转向第三个算法：F-P 生长算法。

4.6 频繁模式生长算法（F-P 算法）

F-P 算法或频繁模式增长算法是本章要讨论的第三个算法。它是对 Apriori 算法的改进。回想一下，在 Apriori 中，我们面临计算耗时和昂贵的挑战。FP 通过将数据库表示为一种名为频繁模式树或 FP 树的树来解决这些问题。因为这种频繁模式，所以没有必要像 Apriori 算法那样生成候选项。现在让我们详细讨论一下 FP。

FP 树或频繁模式树是一个树形结构，它挖掘数据集中最频繁出现的项。见图 4.7。

图 4.7 FP 算法可以用树状图结构表示。我们将逐步创建这个树。每个节点代表一个唯一的项。根节点为空。

每个节点表示数据集中的唯一项。树的根节点通常保持为空。树中的其他节点是数据集中的项。如果它们在同一发票中，则节点彼此连接。我们将逐步学习整个过程。

假设我们使用如表 4.9 所示的数据集。因此，我们有唯一的项：苹果，牛奶，鸡蛋，奶酪和面包。总共有 9 个交易，每个交易中的相应项如表 4.9 所示。

表 4.9 我们将使用的数据集，以了解 FP 算法的概念。这里有九个交易，例如在 T1 中我们有苹果，牛奶和鸡蛋。

现在让我们将 FP 算法应用于该数据集。

步骤 1： 就像 Apriori 算法一样，我们首先扫描整个数据集。记录每个项出现的次数并生成频率计数。结果如表 4.10 所示。我们按照整个数据集中各项的频率或对应的支持计数从大到小排列。

表 4.10 各项集的相应频率。例如，苹果已被购买了六次。

如果两个项的频率完全相同，则任何一个都可以排在前面。在上面的例子中，面包和苹果的频率相同。因此，我们可以将面包或苹果作为第一个。

步骤 2： 让我们开始构建 FP 树。我们从根节点开始创建，通常是图 4.8 中的空节点。

图 4.8 FP 树的根节点通常保持为空。

第 3 步： 现在分析第一个交易 T1。在这里，我们有苹果、牛奶和鸡蛋在第一笔交易中。其中牛奶有最高的支持计数，为 7。因此，从根节点延伸到牛奶的连接，并用 Milk:1 表示。我们在图 4.9 中展示了。

图 4.9 从根节点到牛奶的连接。牛奶有最高的支持，因此我们选择了牛奶。

第 4 步： 现在我们来看看 T1 中的其他项目。苹果的支持计数为 6，鸡蛋的支持计数为 2。所以，我们将从牛奶到苹果延伸连接，并命名为 Apple:1，然后从苹果到鸡蛋并称之为 Eggs:1。我们在图 4.10 中展示了。

图 4.10 过程的第 4 步，我们已经完成了 T1 中的所有项目。所有的项目牛奶、苹果和鸡蛋现在都彼此连接。

第 5 步： 现在让我们看看 T2。它有牛奶和奶酪。牛奶已经连接到根节点。所以，牛奶的计数变成 2，变成了 Milk:2。我们接下来会从牛奶到奶酪创建一个分支，并称之为 Cheese:1。增加的部分显示在图 4.11 中。

图 4.11 过程的第 5 步，我们开始分析 T2。牛奶已经连接，所以它的计数增加了 2，同时奶酪被添加到树中。

第 6 步： 现在轮到 T3。T3 有牛奶和面包。所以，类似于第 5 步，牛奶的计数是 3，变成了 Milk: 3。与第 5 步类似，我们从牛奶到面包添加另一个连接，称为 Bread:1。更新后的树显示在图 4.12 中。

图 4.12 在第 6 步，现在分析 T3。牛奶的计数增加了一个，变成了 3，而面包被添加为一个新的连接。

第 7 步： 在 T4 中，我们有苹果、牛奶和奶酪。牛奶的计数现在变成了 4，苹果现在是 2。然后我们创建了一个从苹果到奶酪的分支，称之为 Cheese:1。我们在图 4.13 中展示。

图 4.13 在过程的第 7 步中，正在分析 T4。牛奶的计数变成了 4，苹果的计数增加到了 2，并添加了一个新的从苹果到奶酪的分支。

第 8 步： 我们可以在 T5 中发现，我们有苹果和面包。两者都不直接连接到根节点，频率相等为 6。因此，我们可以任选其一连接到根节点。图更新为图 4.14。

图 4.14 在分析完 T5 之后，图示如下所示发生了变化。我们有苹果和面包被添加到树中。

第 9 步： 这个过程会继续，直到我们耗尽所有的交易，最终的图形如图 4.15 所示。

图 4.15 一旦我们耗尽了所有可能的组合，最终的树就是这样。但是在此之后还有更多的步骤。到目前为止，我们只创建了树。现在我们需要生成数据集，如表 4.11 所示。

到目前为止，做得很棒！但是，过程还没有结束。我们刚刚建立了数据集中项目之间的连接。现在我们需要填写一个看起来像表 4.11 的表。

表 4.11 FP 算法要完成的表。这是我们希望生成的输出。

也许你会想为什么只列出了 4 个项目。由于牛奶直接源自根节点，没有其他到达它的方式，我们不需要为牛奶单独设置一行。

第 10 步： 在继续之前，我们将最小支持计数固定为 2，以便接受任何规则。由于数据集相当小，我们这样做是为了简单起见。

对于现实生活中的业务问题，建议您尝试多个甚至更高的支持计数值，否则生成的规则数量可能会非常多。

让我们从奶酪作为第一个项目开始。我们可以通过{NULL-牛奶-奶酪}和{NULL-牛奶-苹果-奶酪}到达奶酪。对于这两条路径，奶酪的计数为 1。因此，（如果我们忽略 NULL）我们的条件模式基为{牛奶-奶酪}或{牛奶:1}和{牛奶-苹果-奶酪}或{牛奶-苹果:1}。完整的条件模式基变为{{牛奶:1},{牛奶-苹果:1}}。这些信息添加到表 4.12 的第二列。

表 4.12 过程的第 10 步，我们已经填写了奶酪的第一个单元格。我们填写了奶酪的第一个单元格。

第 11 步： 现在，如果我们在条件模式基中添加两个值，我们会得到牛奶为 2，苹果为 1。由于我们已经为频率计数设置了 2 的阈值，我们将忽略苹果的计数。条件 FP 树的值，即表中的第三列，变为{牛奶:2}。现在我们只需将原始项目添加到此项中，变为频繁模式生成或第 4 列。现在表是 4-13。

表 4.13 过程的第 11 步，在这一步中我们完成了奶酪项目的详细信息。同样，所有其他项目都将被分析并添加到表中。

第 12 步： 以类似的方式填写表中的所有其他单元格，最终表为表 4.14。

我们分析了所有项目的组合后，表 4.14 是最终表。

这确实是一个复杂的过程。但是一旦步骤清晰，就会变得非常简单。

通过这个练习，我们已经得到了最终的规则集，如最后一列频繁模式生成所示。

请注意，所有的规则都彼此不同。

我们将使用最后一列“频繁模式生成”作为我们数据集的规则。

使用 FP 增长算法的 Python 实现非常简单，并且使用库进行计算很容易。出于空间考虑，我们已将 Jupyter 笔记本上传到了本章的 GitHub 存储库中。

我们现在将探讨另一个有趣的主题，即序列规则挖掘。这是一个非常强大的解决方案，使企业能够根据客户的需求量身定制他们的营销策略和产品推荐。

4.7 序列规则挖掘

想象一下。Netflix 会有一个包含顾客随时间订购的所有电影的交易数据库。如果他们分析并发现 65%的购买了战争电影 X 的客户在接下来的一个月也购买了浪漫喜剧 Y，这是非常有见地和可操作的信息。这将使他们能够向客户推荐他们的产品，并且他们可以定制他们的营销策略。不是吗？

到目前为止，在这一章中，我们已经涵盖了三种关联规则算法。但是所有的数据点都限于相同的数据集，并且没有涉及到序列。序列模式挖掘允许我们分析一组事件发生的数据集。通过分析数据集，我们可以找到统计上相关的模式，这使我们能够解读整个事件序列。显然，事件序列是按照特定顺序排列的，这是序列规则挖掘过程中非常重要的一个属性。

序列规则挖掘不同于时间序列分析。要了解更多关于时间序列分析的信息，请参阅附录。

序列规则挖掘被应用于多个领域和功能。它可以在生物学中用于在 DNA 测序期间提取信息，也可以用于了解用户的在线搜索模式。序列规则挖掘将帮助我们了解用户接下来要搜索什么。在讨论关联规则时，我们使用了购买牛奶、面包、鸡蛋的同一交易中的交易。序列规则挖掘是对此的扩展，其中我们分析连续的交易，并试图解读是否存在序列。

在研究 SPADE 算法时，我们将学习构成该算法基础的数学概念。这些概念有点复杂，可能需要多次阅读才能掌握。

4.7.1 SPADE

我们现在正在使用等价类进行顺序模式挖掘（Sequential Pattern Discovery using Equivalence classes）或 SPADE 探索序列规则挖掘。这是由穆罕默德·J·扎基（Mohammed J. Zaki）提出的，文章链接在本章末尾。

我们了解到，我们希望分析事件的顺序。例如，顾客购买了手机和充电器。一周后买了耳机，两周后买了手机壳和手机屏幕保护壳。因此，在每次交易中都购买了项目。并且每次交易都可以称为一个事件。让我们更详细地了解一下。

假设我们有讨论所需的所有项目的完整列表。I 将包含像 i[1]、i[2]、i[3]、i[4]、i[5] 等项目。因此，我们可以写成

I = {i[1], i[2], i[3], i[4], i[5]………, i[n]}，其中我们总共有 n 个不同的项目。

项目可以是任何东西。如果我们考虑杂货店的例子，项目可以是牛奶、鸡蛋、奶酪、面包等等。

一个事件将是在同一交易中的项目集合。一个事件可以包含像（i[1], i[5], i[4], i[8）这样的项目。例如，一个事件可以包含在同一交易中购买的项目（牛奶, 糖, 奶酪, 面包）。我们将用 ⍺ 表示一个事件。

接下来让我们了解一下序列。序列只是按顺序的事件。换句话说，⍺[1] -> ⍺[2] ->⍺[3] ->⍺[4] 可以被称为事件序列。例如，（牛奶, 奶酪）->（面包, 鸡蛋）->（奶酪, 面包, 糖）->（牛奶, 面包）是一系列交易。这意味着在第一次交易中购买了牛奶和奶酪。在接下来的交易中，购买了面包和鸡蛋，依此类推。

包含 k 个项目的序列是一个 k 项目序列。例如，序列（牛奶, 面包）->（鸡蛋）包含 3 个项目。

我们现在将逐步了解 SPADE 算法。

假设我们生成了以下序列。在第一个序列 1001 的交易中，第一个交易中购买了牛奶。第二个交易中购买了牛奶、鸡蛋和面包。紧随其后购买了牛奶和面包。在第四个序列中只购买了糖。在序列 1001 的第五个和最后一个交易中，购买了面包和苹果。并且这适用于所有相应的序列。

表 4.15 序列挖掘的数据集。在序列 ID 1001 中，我们有多个事件。在第一次购买中，购买了牛奶。然后购买了（牛奶, 鸡蛋, 面包）等等。

这个（表 4.15 ）可以转换成垂直数据格式，如表 4.16 所示。在这一步中，我们计算单个项目的频率，即仅包含一个项目的序列。这仅需要进行一次数据库扫描。

表 4.16 表 4.15 的垂直格式。我们只是得到了每个项目的序列 ID 和项目 ID，并在此处表示它。

表 4.16 只是表 4.15 的垂直制表符号表示。例如，在序列 ID 1001 中，元素 ID 1 是牛奶。对于序列 ID 1001，元素 ID 2 是牛奶，鸡蛋，面包等。

为了解释的目的，我们只考虑两个项目 0 牛奶和鸡蛋以及支持阈值为 2。

然后，在下一步中，我们将对每个项目进行分解。例如，牛奶出现在序列 ID 1001 和元素 ID 1，序列 ID 1001 和元素 ID 2，序列 ID 1001 和元素 ID 3，序列 ID 1002 和元素 ID 1 等中。它会产生类似表 4.17 的表格，我们在其中显示了牛奶和鸡蛋。它需要应用到数据集中的所有项目。

表 4.17 中相应的牛奶和鸡蛋序列 ID。同样的方法可以应用到所有项目和序列中。

现在，我们希望计算 2-序列或具有 2 项序列。我们可以有两个序列 - 要么是牛奶 -> 鸡蛋，要么是鸡蛋 -> 牛奶。让我们先来看看牛奶-> 鸡蛋。

对于牛奶 -> 鸡蛋，我们需要在鸡蛋前面放牛奶。对于相同的序列 ID，如果牛奶的元素 ID 小于鸡蛋的元素 ID，则它是一个合格的序列。在上面的示例中，对于序列 ID 1002，牛奶的元素 ID 是 1，而鸡蛋的元素 ID 是 2。因此，我们可以将其添加为第一个合格对，如下表 4.18 的第一行所示。对于序列 ID 1002 也是如此。在表 4.17 中，第 4 行我们有序列 ID 1002。牛奶的元素 ID 是 1，而第 2 行的鸡蛋的元素 ID 是 3。同样，牛奶的元素 ID 小于鸡蛋的元素 ID，因此它变为第二个条目。进程继续。

表 4.18 序列牛奶鸡蛋可以写在这里。关键点是在比较牛奶和鸡蛋的相应元素 ID 时具有相同的序列 ID。

使用相同的逻辑，我们可以创建表格，例如鸡蛋 -> 牛奶，如下所示在下表 4.19 中显示。

表 4.19：序列鸡蛋牛奶可以在此处写下。关键在于比较牛奶和鸡蛋的各自元素 ID 时保持相同的序列 ID。

可以对所有可能的组合都进行此操作。现在我们将转向创建 3 项序列，我们将创建 Milk，Eggs -> Milk。为此，我们必须合并这两个表。

表 4.20：结合序列，即牛奶->鸡蛋和鸡蛋->牛奶，以合并表格。

结合的逻辑是匹配序列 ID 和元素 ID。我们已经用红色和绿色分别突出显示匹配的部分。对于序列 ID 1001，左表中鸡蛋的元素 ID 和右表中鸡蛋的元素 ID 匹配，这成为表 4.21 的第一条目。同样对于序列 ID 1002，元素 ID 3 匹配。这导致了表 4.21 的生成。

表 4.21：在分析了所有物品的组合后的最终表。

这个过程将继续进行。当找不到频繁序列时算法停止。

我们将使用 Python 在数据集上实现 SPADE。我们使用pyspade库，因此我们必须加载数据集并调用函数。它会为我们生成结果。这里支持率设置为 0.6，然后我们打印结果。

from pycspade.helpers import spade, print_result
spade_result = spade(filename='SPADE_dataset.txt', support=0.6, parse=True)
print_result(spade_result)

这结束了我们在本章中要讨论的四种算法。现在我们将转向案例研究，为您提供真实的体验。

无监督学习与生成式人工智能（MEAP）（二）（3）https://developer.aliyun.com/article/1522539