面向大数据的并行聚类算法

刘解放，张志辉

(1.湖北交通职业技术学院 交通信息学院，湖北 武汉 430079； 2.武汉科技大学 计算机科学与技术学院，湖北 武汉 430081)

0 引 言

大数据对社会具有潜在价值，它正在推动行业研究人员重新思考计算方案来获取有用信息。但由于高计算成本，使得分析和检索操作非常耗时。因此，高性能计算，如并行计算[1]、分布式计算[2]、云计算[3]和网格计算[4]等无疑是未来解决上述问题的重要手段。

聚类本质上是一种典型的“无监督”数据分析方法，但到目前为止，已提出的所有经典算法都需要用户的大量指导，例如K-means需要预先指定聚类个数和终止条件。最近提出的CLUBS[5]，是一种非常有效的聚类算法，无需用户任何指导，通过4个阶段的不断完善，自动完成聚类任务。它不但能够容忍一定程度的过度分割，而且能够处理异常点的检测及椭圆簇的生成。遗憾的是，该算法针对大数据应用场景无能为力。

本文结合高性能计算提出了CLUBS的并行版本，称为CLUBS‖，类似CLUBS，CLUBS‖时间复杂度关于数据集大小线性缩放，并基于Ad-hoc消息传递实现了所提聚类算法。实验结果表明，随着越来越多的并行节点加入运算，加速比几乎是线性的。CLUBS‖的特性使它可以有效聚类大规模数据，且不要求节点间交换原始数据，仅需交换摘要信息。

1 相关工作

大数据的出现重新激发了研究人员对数据挖掘基础工具的兴趣，例如聚类。为克服聚类的计算复杂度，研究人员已经提出许多方法，无论是单机还是联机方案。

单机版的大数据聚类经典方法大都基于采样、降维和分块技术，例如，文献[6]提出了一种基于加速比和势分布的采样方法，通过使用采样技术减少求解搜索空间，极大地提高了大数据处理的性能；文献[7]基于随机投影技术降低数据维度提出了一种聚类方法WOMP-GS-FIS，该方法尽可能保持了样本点间的距离；文献[8]通过将贝叶斯模糊聚类与分块技术相结合，提出了一种面向大规模数据的快速单趟贝叶斯模糊聚类算法SPBFC。

尽管以上方法显著减少了大规模数据聚类的计算时间，但是，在给定的时间内，数据量的增长远远快于单机处理能力的增长。这使得必须使用并行技术，但是，并行技术由于某些关键因素而带来极大挑战，例如协同工作、网络通信、资源共享和容错能力等，实现难度较大。目前，有些经典算法被改写实现了并行化，其中K-means‖[9]是一个非常成功的案例，它采用播种算法，即使在单机上运行，也优于K-means。

2 CLUBS

最近提出的CLUBS[5]是一种基于快速分层的无参数中心聚类算法。它融合了分裂和凝聚两种优点。首先，使用二叉空间分割技术对数据集进行定义，并生成一系列的初始簇，其次，对生成的簇进行调整，然后，对簇进行凝聚，最后再完善。在完善阶段，异常点被标记，其余的点被分配到最近的簇。图1展示了CLUBS在二维数据上的执行过程，图1(a)为原始图，图1(b)～图1(e)为各步骤的执行结果。下面简要介绍它4个核心步骤。

图1 CLUBS在二维数据上的执行过程

2.1 分裂阶段

CLUBS采用自顶向下二叉空间分割技术将数据集分割成为一系列的超矩形块，使得各块内部点尽可能靠近，这等价于最小化簇内平方和(WCSS)。CLUBS要求分割的超平面正交与坐标轴，并使用贪婪准则，块被迭代分割为成对的簇。

给定一个数据集，该算法将其作为一个簇S，S进入优先级队列Q，Q包含所有迭代分割的块。如果Q非空，从中出队一个块B， 并将其划分为一对块，如果划分有效，该对块替代B并进入队列，否则，B成为最终的块。

将所有属于块B， 且第i维坐标值等于x的点p求和，该函数可以表示为图或数组。文献[5]表明最小化WCSS的分割可以通过图或数组的线性扫描产生。

该阶段选择了CH指标[10]评估聚类质量。每次分割之后，都会重新计算CH值，如果CH值增加，则分裂阶段有效并继续，若降低到70%以下，则停止本次分割。

2.2 调整阶段

分裂阶段结束后，整个数据空间被分割为两类块：一类是每块仅含有一个簇，另一类是每块仅含噪声。调整阶段，CLUBS力求实现两个任务：①将含有簇的块分离出来；②将分离出来的块生成一个椭圆簇。

因仅含有噪声块的密度较低，因此可以通过观察实施第一个任务。CLUBS首先基于密度对所有块进行递增排序，并检测相邻块间的密度跳跃，从而确定噪声块的候选子集。然后，测试候选子集，例如，在块的中心生成一个较小的超立方体，如果超立方体的密度明显大于整个块的密度，则表明该块属于异常块，否则属于簇块。例如，图1中J、K、L和M都是异常块。

2.3 凝聚阶段

凝聚阶段，通过合并上一阶段产生的簇，改进聚类质量。如果合并一对簇导致WCSS较小增加，而CH指标显著增加，实施合并，并将合并后的簇替代原有的两个簇。如果合并导致CH指标严重降低，则取消，凝聚阶段结束。实际上，仅有相邻簇才考虑是否合并，因为相邻簇的合并才有可能导致WCSS较小增加和CH指标显著增加。图1(d) 展示了簇B是由图1(c)中簇B和簇I合并而成。

2.4 完善阶段

由于前期采用了近似和贪婪准则，凝聚阶段通常会产生形状稍不规则的簇。例如，图1(d)中簇B，它是由图1(c) 中簇B和簇I合并而成。由于调整阶段，图1(b)中块K被认定为异常块，其左上角的点被块B和I非对称吸附，因此导致明显不对称。完善阶段重构椭圆簇，不仅提高了聚类质量，并且还确定了最终异常点。

3 CLUBS‖∶CLUBS的并行化

假设有N个从节点，它们都具有相同的硬件特性，并具有本地存储和计算能力，数据分布在从节点上，能存储在分布式文件系统上或本地文件系统上。

多个从节点高效运行的关键问题是如何协同访问数据，其中包括：①分裂阶段边缘分布的计算；②调整阶段候选离群块的局部密度计算；③完善阶段将点分配给最近簇计算。

下面将重点分析上述3个关键计算的并行化，关于其它计算，如摘要信息的计算，则使用CLUBS原有方法通过主节点处理。

3.1 边缘分布的并行计算

边缘分布的并行计算，也即是向量C和S的计算，它们是分裂阶段唯一需要访问数据的计算。由于计数运算和求和运算的结合性和可交换性，该计算可高效地并行执行。因此，给定一个数据集的块划分 {B1,…,Bk}， 可独立计算各块Bk上C和S向量，最终，求和各块上的向量得到数据集的全局向量。根据MapReduce范式，各块Bk被映射为一系列向量对，表示各块每个维度的C和S， 通过求和相同维度的向量，这些向量随后被约简。

3.2 块局部密度的并行计算

为实现调整阶段第一个任务，需计算块的局部密度。在分裂阶段，主节点获得所有划分块的信息，因此，主节点可以获得各块的全局密度和范围。为检查块质心附近的局部密度是否明显高于全局密度，需要计算质心附近小范围内的局部密度(例如，整块的1/10)，然后并行计算落入“受限”范围内的点数。尽管在这种情况下，该计算涉及到的唯一数学运算是求和，因此，计算完全可并行化。实际上，对于数据块的各个部分，都可以独立计算点数，然后，将各部分的点数相加求和即可得到总的点数。因此，主节点可以计算局部密度。

3.3 点到簇的并行分配计算

将点分配给最近的簇或者将其作为异常点，每一个从节点在调整和完善阶段都可以独立执行该操作。首先主节点将关于簇的摘要信息发送给每一个从节点，并要求它们计算点到簇的距离。至此，每个从节点都能计算摘要信息，然后，综合来自从节点的所有数据，主节点即可获得簇中心的全局值、各簇的点个数、簇的半径，并更新簇的信息。

下面，针对所提并行算法CLUBS‖，提出一种基于Ad-hoc消息传递的实现。

4 基于Ad-hoc消息传递实现CLUBS‖

本节基于Ad-hoc消息传递实现了CLUBS‖算法，并基于标准Java套接字的信息交换实现网络节点间的通信。

该算法实现如下：

步骤1 聚类开始时，主节点向从节点发送LoadDataSetRequest，为加载的数据集指定标识符。各从节点将数据加载到内存中，并通过LoadDataSetResponse答复主节点，该响应消息包含自身加载数据的范围。当主节点收到所有从节点的答复时，即可计算全局数据集的范围。

步骤2 主节点向从节点发送InitRootRequest，指定全局域。每个从节点计算本地数据边缘分布，并通过InitRoo-tResponse答复主节点，该消息包含本地数据的C和S。 主节点即可计算全局数据集的C和S， 以及WCSS，从而实现块的分割，并将块初始化划队列。当队列非空时，出队一个块，开始计算它的全局边缘分布。通过将所有节点本地边缘分布分别相加求和即可获得全局边缘分布。

首先，假设全局边缘分布在N个从节点间传递。主节点选择一半的从节点发送它的边缘分布给其余从节点，然后迭代累加边缘分布。当全局边缘分布被传递到N/2个从节点上，主节点再次选择一半的从节点发送边缘分布给其余从节点。这个操作被重复，直到整个边缘分布被存储在一个节点上。图2展示了边缘分布的计算过程，图2(a)每个从节点wi计算它本地的边缘分布mi； 图2(b)从节点w2发送m2到从节点w1， 从节点w4发送m4到从节点w3； 图2(c)w1和w3分别将收到的边缘分布和自身的边缘分布相加，然后，w3发送m3+m4到w1上；图2(d)w1再次将收到的边缘分布和自身当前的边缘分布相加，从而获取了全局边缘分布。

图2 边缘分布计算过程

为了平衡负载，将分别计算各维度的边缘分布，统筹各维度，整体考虑各节点的负载。该过程形式化如下，假设 (w1,w2,…,wN) 是一组从节点，对于第i维，从i-1的位置左旋转初始化从节点。因此，对于第i维，从节点的列表可表示为li=(wi,…,wN,w1,…,wi-1)。

然后，主节点发送ComputeBestSplitRequest给节点wi， 该节点通过扫描第i维的边缘分布，即可独立计算出第i维最好的分割。节点wi通过ComputeBestSplitResponse答复主节点，消息中包含分割位置和WCSS下降值。

当主节点获取各维度ComputeBestSplitResponse后，即可优选全局分割。此时，通过CH指标判断分割是否有效，如果有效，则主节点发送SplitRequest到每个从节点，含有划分维度和位置；当从节点收到SplitRequest时，生成两个新块，相应的数据也被划分到两个块中，然后，计算边缘分布，并向主节点发送SplitResponse，该消息含有两个新块的C和S， 当主节点收到了SplitResponse，计算两个块的WCSS，并将其加入队列；如果无效，将该块添加到最终块列表中。然后，再从队列中移出一块，开始计算其全局边缘分布。如果队列为空，开始调整阶段。

步骤3 此时主节点有一个列表，其含有划分好的块和块的摘要信息。主节点存有每块的范围和包含的点数，因此，能够计算块的密度，通过密度即可检测出候选异常块。对于这些块，需计算受限密度。为此，一个包含候选受限块标识、相应受限范围的RestrictedCountRequest发送给所有从节点，从节点在指定块中扫描本地数据，并计算每个受限范围的点数，然后将计算结果通过RestrictedCountResponse发送给主节点。

当主节点收到所有从节点发来的RestrictedCountResponse，即可确定哪些是异常块。然后，主节点向从节点发送RefinementRequest，它包含簇的中心和半径。从节点扫描所有样本点，并将其分配到最近的簇中，否则，标记异常点。同时更新每个簇的C和S，并将结果通过RefinementResponse发送给主节点。

步骤4 当主节点收到所有从节点发来RefinementResponse后，即可计算全局C和S。此消息为凝聚阶段奠定基础，合并形成新簇。

步骤5 然后，主节点向从节点发送PerfectRequest消息，并包含新簇的中心和半径。完善阶段，每个从节点进行再调整处理，类似首次调整阶段，通过PerfectResponse向主节点发送更新后的C和S。 当主节点收到来自从节点的所有消息后，聚类完成。

5 实验与分析

由于CLUBS‖和CLUBS采用了相同的理念，因此，CLUBS‖的精度等同于CLUBS。CLUBS的精度已经验证比现有的聚类方法优越，因此，这里不展示精度，而是重点验证并行聚类算法CLUBS‖应用于大数据场景的有效性。

5.1 数据集及参数设置

实验采用了3个合成数据集，其数据点个数分别为107，108和109，维度在 [2,4,…,12] 范围内，簇数在 [20,21,…,25] 范围内。各数据集根据域宽(如2000)、维度和簇数随机生成符合高斯分布的簇；为了测试算法的鲁棒性，数据集随机添加了噪声点，数量在总点数的0至0.1倍。实验运行环境包含16个计算机节点，节点配置为Intel Xeon 6230*2颗2.1 GHz CPU，64 GB内存。

实验每次仅改变一个参数，测试使用1、2、4、8或16个节点的运行时间。为了便于展示，在每次实验中，非变化参数默认设置为：总点数为108，维度为16，簇数为32，噪声比率为0.1，因为该设置被验证是最严格的测试。

5.2 参数敏感性及性能分析

图3展示了CLUBS‖算法的运行时间。正如预期，运行时间随着节点个数的增加而显著减少，并且加速比几乎与节点个数成线性关系，如运行时间曲线所示。

图3(a)展示了针对大规模数据，随着节点个数的增加，加速比几乎保持恒定。实际上，采用1至2个节点是无法运行109数据集，但是，在108规模上的结果清楚地表明了该算法针对相对较多的点具有很好的扩展性，相反，如果数据点不太多(例如107)，相比本地计算，网络通信对总开销的影响更大，因此，节点从8到16，加速比降低。

图3 CLUBS‖的敏感性测试

图3(b)表明随着节点个数的增加，加速比不受数据维度的影响，因为不同维度的曲线斜率几乎相同。但是，运行时间随着维数的增加而增加，这也符CLUBS算法，与现存许多其它聚类算法一样，计算成本随着维度线性增加。

图3(c)表明随着节点个数的增加，簇数对加速比影响不大。具体来说，簇数少的数据集，加速比效果稍好，这是因为簇数多的数据集在分裂阶段将花费更多时间，此外，分裂阶段也是节点间通信最多的阶段。因此，虽然节点的本地工作负载没有变化，但随着簇数的增加，交换边缘分布所需时间增加，因为必须进行更多的分割。此外，运行时间也随着簇数的增加而增加。

图3(d)展示了算法的抗噪能力非常优秀，且运行时间和加速比都对不同比例的噪声不敏感。这是因为加速比主要受节点间的通信影响，而节点间不需要交换数据，仅交换摘要信息(边缘分布)，因此，加速比不依赖于处理的数据(噪声或簇)。

5.3 CLUBS‖、K-means‖和Spark PIC的对比分析

为进一步验证CLUBS‖的性能，实验将其与经典的K-means 并行版K-means‖[9]和PIC的并行版Spark PIC[11]进行了比较分析。图4展示了3种算法处理大小不同数据集时的加速比。3个数据集均为16维，32簇，噪声比为0.1。

图4 CLUBS‖、K-means‖和Spark PIC的性能对比

如图4所示，CLUBS‖的扩展性更好，随着节点个数的增加其运行时间缩短得更快，也即加速比更大，尤其针对大数据集；并且CLUBS‖的表现总是优于K-means‖和Spark PIC。这主要因为CLUBS‖是基于Ad-hoc消息传递的算法，它通过使用针对该算法量身定制的协议，可以充分利用分布式计算资源。测试结果符合我们的理论目标。

6 结束语

由于现实世界的需求和并行计算的盛行，传统经典的单机版聚类算法已无法适应大数据时代的需要。因此，为了使得许多优秀的聚类算法可扩展并利用，本文基于并行计算和CLUBS算法提出了一种面向大数据的并行聚类算法CLUBS‖，并基于Ad-hoc消息传递给出了实现。结果表明所提改进算法具有很好的扩展性和鲁棒性。同时，它的改进超越经典的并行聚类算法K-means‖和Spark PIC。作为未来的一项工作，我们计划测试其它的高性能计算策略，以便进一步改善算法的性能。