ICDE 2023 探索并行过滤图：革新层次聚类算法

ICDE 2023 | 探索并行过滤图，革新层次聚类算法

机器学习中的无监督学习方法现在已经被广泛运用，特别是聚类算法被广泛运用于经济、生物以及机器视觉等多种领域之中。而聚类算法中也包含许多方向，如基于密度聚类，基于划分聚类以及基于度量聚类。传统的基于度量聚类在一个包含n个数据点的数据集上运行的时候，往往需要Θ(n²)计算复杂度，这在大型数据集上运行是不现实的，所以，提升效率是重中之重，方法之一便是创建过滤图和基于图聚类算法搭配使用。常用的方法包括Planar Maximally filtered graphs(PMFG), Triangulated Maximally Filtered Graph(TMFG)搭配着Directed Bubble Hierarchy Tree(DBHT)使用。

但是，以上组合算法都是顺序性的。为了进一步提升效率，数据库国际顶级会议ICDE2023上的论文《Parallel Filtered Graphs for Hierarchical Clustering》介绍了一种用于构建TMFG的并行算法，并设计了一种新的并行构建DBHT的算法。通过实验表明，使用新构建的算法能够更快和更高质量的聚类。

1. 背景介绍

在这一部分将解释顺序构造PMFG和TMFG，以及接下来要使用的记号和相关术语。

• 1. PMFG

为了顺序构建PMFG，首先需要将所有的边权升序排序，然后在不违背平面性的原则下，从边权大到小插入构建的图中，其中的平面性指的是能够画在平面之上且各边之间不相交的性质。可以看出，这样的计算复杂度是Θ(n²)。

• 1. TMFG

为了降低构建PMFG的计算复杂度，TMFG便应运而生。它与一次只插入一条边的PMFG构建方式不同，顺序构建的TMFG一次插入一个节点以及从该节点引出的3条边。这种方法是不用做平面性检验的，因为平面性的定义中已经规定在平面绘制的时候边不能相交，所以TMFG的构建仅需要Θ(n)的计算复杂度就可以完成。

• 1. DBHT

在获取到PMFG或者TMFG之后，便是从DBHT算法中生成用于层次聚类的树状图。

构建树状图的步骤分为三步：1、构建无向Bubble Tree（以下成为气泡树）；2、构建有向气泡树；3、使用完全链接聚类（complete-linkage clustering）生成层次结构；

其中气泡树中节点关联的是PMFG或着TMFG中的一个平面子图，边关联的是分割两个节点代表的平面子图的三角形，示例如下图所示：

图 1 TMFG 和无向气泡树

上图中便是一个TMFG和一颗气泡树。在气泡树中，b₁和b₂便是平面子图，而t₁便是分割这两个子图的三角形Triangle(0, 1, 2)。

无向气泡树向有向气泡树转换依据的是方向确定函数，这个接下来会涉及。重要的是完全链接聚类，为了让读者不感到突兀，下面重点解读一下：

完全链接聚类算法是一种层次聚类算法，其核心原则是在每一步聚类过程中考虑聚类内最不相似（即距离最远）的成员。在这个算法中，两个聚类的距离被定义为这两个聚类中最远的两个点之间的距离。当这个距离最小时，两个聚类合并。随着算法的进行，这种方法逐步构建出一个层次结构，其中每个层级代表了不同的聚类粒度。

• 1. Other Terminology

Outer face（以下称为外部面）和Inner face（以下称为内部面）是两个相对的概念。值得注意的是，外部面是没有边界限制的，而相对的，有边界的面被称为内部面。如上面的图1所示，面{0, 3, 6}便是一个外部面，而面{1, 2, 5}便是一个内部面。

Parallel Primitives（以下称为并行原语）是指在并行计算中使用的一组基本操作或函数，具体如图2所示：

图 2 并行原语

其中值得注意的是WRITEADD操作，它是一种优先级并发写操作，允许在多个线程或进程中同时对同一位置进行安全的增量更新。

1. 算法解释

在解释具体的算法之前，为了方便读者理解，如果必须，会预先给出算法的示例，让读者在示例中总览算法的全貌。

2.1 Parallel TMFG

首先，找到在输入的相似矩阵S中每一行中总和最大的四个顶点C{v₁, v₂, v₃, v₄}，然后将这四个顶点形成的边{(v₁, v₂), (v₁, v₃), (v₁, v₄), (v₂, v₃), (v₂, v₄), (v₃, v₄)}总共6条边加入ξ中，这也形成了四个面{(v₁, v₂, v₃), (v₁, v₂, v₄), (v₂, v₃, v₄), (v₁, v₃, v₄)}，然后将其加入Ϝ中，然后将剩下的节点划分给V之中。

初始化之后，便是将剩下的节点插入到构建的图中。为了提高效率，算法中的传入了一个批大小参数Prefix，每次插入时先计算批处理节点中插入某个平面后的Gain（以下称为收益函数），然后将节点插入收益函数最大的平面之中，不断迭代，直至没有节点可以插入。

以上便是该算法的解释，算法的伪代码如图3所示：

图 3 Parallel TMFG Algorithm

值得注意的是，图中算法的蓝色标注代码端没有解释，因为这涉及到无向气泡树的构建，这部分将与下一部分以一个示例具体说明。

2.2 Parallel DBHT for TMFG

为了让读者更好地理解相关算法，在这里先给出一个示例，如图4所示：

图 4 算法相关示例

图中（a）表示已经构建出来的TMFG，（b）表示在构建TMFG过程中构建出的无向气泡树。

在示例中，图中最初存在4个节点，分别是{0，1，2，4}，当需要插入节点3的时候，通过收益函数计算出来的最佳插入面是{0，1，2}，显而易见，这是一个外部面，所以当节点3插入时，气泡b₂={0, 1, 2, 3}将成为气泡b₁={0, 1, 2, 4}的父亲节点；当需要插入节点5的时候，通过收益函数计算出来的最佳插入面是{1, 2, 3}，这是一个内部面，所以气泡b₄={1, 2, 3, 5}将会成为气泡b₂={0, 1, 2, 3}的儿子；插入节点6也类似。

通过上述案例可以知道，构建无向的气泡树是在构建TMFG的并行化过程之中的，这就比原来算法的效率高很多。

算法1的UpdateBubbleTree函数部分如图5所示：

图 5 UpdateBubbleTree Function

构建完无向气泡树之后便是确定气泡树中边的方向，这一次先给出该函数的伪代码，因为这是一个递归函数，具体如下图所示：

图 6 computeDirection Function

首先需要明确的是，方向的确定是通过计算TMFG中连接三角形与其内部INVAl（以下成为内部值）和外部OUTVAL（以下称为外部值）的边的权重之和比较来决定的。在原来的算法之中，计算这两个值是通过BFS算法经过Θ(n²)时间复杂度得出，但是，在气泡树中，分割三角形（即树边）的子树包含了所有的内部顶点，而树边所指的父亲包含了所有的外部顶点。利用这个特性，可以通过上图的递归函数在Θ(n)计算复杂度内实现以上两个值的计算。

从给的示例图4中（c）可以演示上述算法的执行过程：

首先，从根节点b₃开始，由于根气泡没有父节点，所以递归到子节点b₂，即b = b₂，该节点与其父节点分割面为t₂ = {0, 1, 3}，剩下的顶点v = 2，所以，初始化r[0] = w(0, 2), r[1] = w(1, 2), and r[3] = w(3, 2)，接下来便是向下递归b₂的子节点b_1，b₄。由于b_1，b₄操作是一致的，以下仅示例b₁相关。

对于b₁来说，r^*[0] = w(0, 4), r^*[1] = w(1, 4), and r^*[2] = w(2, 4)。因为v_x^* = 0 ∈ r and v_y^* = 1 ∈ r，所以r[0] += w(0, 4), r[1] += w(1, 4)。对b₄做一样的操作之后，得到：r[0] = w(0, 4)+w(0, 2)，r[1] = w(1, 4)+w(1, 2)+w(1, 5)以及r[3] = w(3, 2)+w(3, 5)。得到以上结果之后，按照算法中的公式得到内部值和外部值，通过比较之后，得到b₃指向b₂。

完成有向气泡树构建之后便是Assigning Vertices（以下称为顶点分配）和构建树状图。其中重要相关的术语为converging bubble（以下称为收敛气泡），它是指在气泡中只有入边没有出边的节点。具体伪代码如下图所示：

图 7 Parallel DBHT for TMFG

首先，第一级聚类将每个顶点分配给唯一的收敛气泡。如果一个顶点至少在一个收敛气泡中，那么它将被分配给具有最强连接的收敛气泡。对于TMFG，所有的泡泡都有6条边，因此可以简化为将顶点分配给具有最大连接权重的收敛气泡。对于那些不在任何收敛气泡的顶点，它们将被分配给具有最小平均最短路径距离的收敛气泡。具体而言，对于每个顶点v，计算它与收敛气泡b之间的平均最短路径距离，然后将v分配给具有最小平均最短路径距离的收敛气泡b。

然后，第二级聚类将每个顶点分配给唯一的气泡，但不一定是收敛气泡。对于每个顶点v，将其分配给最大连接得分的气泡b。其中连接得分χ'(v, b）：

即是气泡b中所有边的权重之和除以气泡b中所有边的数量之和。

顶点分配之后便是使用Complete Linkage算法构建树状图。该算法被用于构建三个层次的树状结构：intra-bubble、inter-bubble和inter-group。首先，对于每个intra-bubble，即同一个收敛气泡中的顶点，运行Complete Linkage算法，得到一个intra-bubble的树状结构。然后，对于每个inter-bubble，即不同收敛气泡中的顶点，运行Complete Linkage算法，得到一个inter-bubble的树状结构。最后，对于所有的inter-group，即不同分组中的顶点，运行Complete Linkage算法，得到最终的树状结构。

1. 实验验证

3.1 实验环境

实验环境设置在在Amazon EC2的c5.24xlarge机器上进行实验，该机器配备了2个Intel Xeon Platinum 8275CL（3.00GHz）CPU，共48个超线程核心和192GB的RAM。默认情况下使用所有带有超线程的核心。对于C++编码的代码，使用版本为7.5的g++编译器，使用O₃加速和ParlayLib库进行并行编程。

3.2 数据集设置

实验用于测试的数据总共包含18个，如下图所示：

图 8 Data Sets used in Testing

3.3 效果评估

3.3.1 Runtime

为了展示算法的优越性，将所有的层次聚类算法与Prefix = 1和Prefix = 10的并行化算法（下图分别为PAR-TDBHT-1，PAR-TDBHT-10）作比较，结果如下图所示：

图 9 Runtime

从上图可以看出，Sequential PMFG-DBHT在单线程的情况下比PAR-TDBHT-1慢458-15586倍，比PAR-TDBHT-10慢414-14254倍。Sequential TMFG-DBHT在单线程的情况下比PAR-TDBHT-1慢56-276倍，比PAR-TDBHT-10慢50-235倍。在48核超线程的情况下，Sequential TMFG-DBHT分别慢136-2483倍，226-4487倍。

值得注意的是，PAR-TDBHT-1和PAR-TDBHT-10在大多数数据集上比AVG和COMP要慢一些，但是这是符合预期的，因为算法本身是Complete Linkage。但是，随后可以看到，PAR-TDBHT-1和PAR-TDBHT-10在大多数的数据集上的聚类效果比AVG和COMP都要好。

3.3.2 Clustering Quality

为了评估聚类效果，这里采用的是ARI指数，该指数越大，表示聚类效果越好。正如上文提及的那样，PAR-TDBHT-1和PAR-TDBHT-10在大多数的数据集上的聚类效果比AVG和COMP都要好，具体结果如下图所示：

图 10 聚类效果——ARI

由上图所示，尽管在一个AVG和COM难以聚类的数据集之上，PAR-TDBHT-1和PAR-TDBHT-10都能够做到良好的聚类效果。这充分说明了该算法的优越性。

3.3.3 True Data Set Cluster

为了展示该算法在真实数据集中的聚类的优越性，论文还在真实的股票数据集进行演示，聚类结果如下图所示：

由上图所示，它准确地将股票分为“金融”、“医疗保健”、“消费者自由裁量权”等类别。聚类结果的ARI得分为0.36，与精确的TMFG聚类的ARI得分0.28相比。由此可见，与人类专家的分类结果吻合的该算法取得了显著的效果。

1. 论文总结

该论文详细地介绍了算法的理论基础、设计原则和实现细节。通过一系列的实验评估，展示了该算法在不同数据集上的性能，特别强调了其在处理大数据时相比传统聚类算法的优势。这项研究对于理解和优化大规模数据集的层次聚类过程具有重要价值，对数据分析、机器学习等领域的进一步研究提供了新的思路和工具。