CLUS：基于Spark集群的并行子空间聚类算法外文翻译资料

 2022-09-22 10:25:23

英语原文共 11 页，剩余内容已隐藏，支付完成后下载完整资料

CLUS：基于Spark集群的并行子空间聚类算法

Bo Zhu, Alexandru Mara, and Alberto Mozo

Universidad Politacute;ecnica de Madrid, Madrid, Spain

bozhumatias@ict-ontic.eu, alexandru.mara@alumnos.upm.es, a.mozo@upm.es

摘要：子空间聚类技术的提出是为了发现那些只存在某些完整功能空间子集的隐藏集群。然而，这种算法的时间复杂度至多是关于数据集维数的指数，而且，在当前数据场景下，数据通常太大从而难以适应单个机器的情况。极高的计算复杂度导致了这些数据集在大小和纬度上的极差的可扩展性，因此，提出一个并行的子空间聚类算法去处理大维度的数据对我们来说就显得尤为必要。我们知道的是，没有其他的并行子空间聚类算法运行在像MapReduce和Spark这样的新一代大数据分布式处理平台上。在本文中，我们介绍了CLUS：一个基于SUBCLU算法的新颖的并行子空间聚类算法。CLUS使用了一个新的动态数据分区方法，该方法是专门设计用来不断优化每个迭代器所需要的不同大小和内容的数据，从而达到最大化利用Spark基于内存计算的优势。这种方法最大限度地减少了节点之间的交流成本，最大化利用了CPU使用率，并且平衡了它们之间的负载，因此执行时间明显减少。最后，我们用一系列的真实和合成数据集通过在几个节点上的实现进行了几个实验来证实算法在可扩展性、准确性和近线性加速上面的优势。

关键字：子空间、并行、聚类、Spark、大数据

1.引言

聚类是一种从未标记的数据集中发现的无监督的主要技术知识。这种技术使用了和从被称为集群的实体聚集数据点相似的概念。传统的聚类算法如：基于分区方法(e.g. K-Means[1])，基于密度的方法(e.g. DBSCAN[2])和分层的方法(e.g .D IANA[3])，考虑完整的特征空间。然而，随着现在的数据集变得越来越大而且维数更高，由于无关的特性和维度的灾难的存在使这些算法未能发现有意义的集群[4]。

在许多应用领域，如传感器网络、生物信息学，以及网络流量，对象通常是由数以百计的特征描述的。自从数据收集和存储变得更便宜、更方便，更大的数据集生成没有相关性的分析。因此，许多技术开始深入研究并学习解决由高维数据集组成的集群任务。降维技术如：主成分分析[5]，特征选择如：mRMR特征选择算法[6]，生成一个包含最相关的最优的特征子集信息。考虑到集群可以找到不同的特征子集,这些技术不能为每个集群检测局部相关特性[4]。

一个来自频繁模式挖掘领域的特定系列算法[7]，快速的形成了一个新的领域并命名为子空间聚类。这些集群算法旨在找到隐藏在原始特征空间的子集，因此避免了维度的灾难。然而，据我们所知这些技术在关于数据集的大小上都没有良好的可扩展性。他们通常假设整个数据集可以运行在一台机器上。SUBCLU[8]，一种基于子空间聚类的算法使用传统的DBSCAN实现，它用来在每个子空间上聚集数据从而产生一个低效且无扩展性的解决方案。在这种情况下，并行化出现在人们的视野中，它作为一个自然的解决方案来提高现有的子空间聚类算法的效率和可伸缩性。然而，在我们的研究中，我们发现在当前热门的大数据分布式平台上，对于高维度数据的子空间聚类算法还是缺少可扩展性。最近，MapReduce[9]和Hadoop框架[10]已经成为大数据分布式框架的潮流。不过，MapReduce自身的局限和缺乏对迭代的机器学习算法的适用性促使研究者提出不同的方案，其中Spark[11]最具代表性。因此,在当前热门的Spark平台上设计可扩展的子空间聚类算法是一个值得且有趣的挑战。

Contributions. 在本文中，我们提到了CLUS，一个基于SUBCLU的Spark平台上的新的并行算法，它克服了SUBCLU在使用动态数据分区方法上的限制。CLU S通过在不同的节点上并行聚类任务从而降低了SUBCLU的维数和时间复杂度。通过分布在节点和在需要的时候溢出到磁盘，CLUS也消除了集中算法的数据集大小限制得到在一台机器上可用的RAM。

为了发展CLUS，Spark被使用，因为如果被恰当的使用它会潜在的提高性能。不像MapReduce，Spark提供了更高的灵活性，它允许用户管理内存、磁盘和网络从而提高更有效的算法。而且，不像MapReduce把中间生成结果写到磁盘，Spark把结果存在内存中。正因为Spark是基于内存计算的，所以它比其他的大数据处理平台表现更优[24]。

总之，CLUS算法的主要作用如下：

1. 一个动态数据分区方法是精心设计的，它使用Spark的具体操作以诱导数据本地化。这种优化步骤通过避免不必要的数据缓慢转移降低了通讯成本，这在大多数的MapReduce和Spark程序中是很常见的。

2. CLUS避免在每个节点复制整个数据集从而使它们并行处理。基于Spark的具体操作，CLUS可以部署在商用机器组成的集群上并高效的处理大规模数据。

3. 通过使用索引使I /O成本最小化以达到访问和移动具体节点在每个迭代中必要的数据。这将导致更快的和更高效的数据管理和更好地利用可用的内存。

4. 从真实和合成数据集上实验结果可显示算法的可伸缩性和准确性。结果显示令人可观，CLUS的执行时间更短。

本文的结构组织如下：第二节介绍了相关工作的概述，。第三节简要介绍SUBCLU算法并提出了CLUS的实现。在第四节我们显示不同的数据集的实验结果。最后，第五节得出了我们的结论和对未来的展望。

2.相关工作

2.1 子空间聚类

最近的二十年内，许多研究都试图解决子空间聚类任务。有一些优秀的调查[4、12、13]，它们把理论或实验在不同的子空间聚类算法进行比较。考虑不同算法方面这些方法被分为几类。一些经典算法被分为自下而上和自上而下的组。

自底向上算法首先根据每一维度生成一维直方图信息，然后试图执行一个自底向上遍历来遍历子空间。因为自然的遍历子空间的时间复杂度是数据集维数的指数倍，大多数这些方法进行修剪步骤选择最好的结果。这个过滤过程是基于反单调的性质。

反单调性：如果没有集群存在子空间Sk ，那么也没有比子空间SK 1维数更高的集群。

exist;Sk,CSk =empty;rArr;forall;Sk 1sup;Sk,CSk 1=empty;.

通过从一个维度开始和每次添加另一个维度，自底向上的方法往往在相对较小的子空间能有效地工作。因此，当发现隐藏的低维子空间集群时他们通常显示更好的可伸缩性。然而，性能会随着候选子空间包含集群的大小而大幅减少[12]。自底向上算法有CLIQUE [14]，ENCLUS[15]等。

与自底向上的方法相比，自上而下的方法从等权重的特征空间开始并产生一个近似集群。初始化后，在每个集群上更新每个维度的权重和集群的再生是迭代进行的。最后，对聚类结果进行优化以实现更高质量的集群。因为聚类过程的多次迭代是在完整的特征空间上完成的，抽样技术通常以牺牲结果的准确性来提高效率。由于强制输入参数，以这种方式生成的集群是非重叠性且具有类似的维度。典型的自上而下算法有PROCLUS[16] 和ORCLUS[17]。

根据最近的研究工作可以总结出，子空间聚类算法可以根据底层集群的定义和参数化分为三个范式：Grid-based方法、 SCHISM[18]、MaxnCluster[19]，试着为不同的子空间寻找包含更多数据而不是密度阀值的网格箱。基于密度的方法如SUBCLU[8]， INSCY[20]，通过计算相关维度的距离来寻找密集区域而隔开稀疏的区域。面向聚类的方法如STATPC[21]，Gamer[22]，假设整个集群中的全局属性集和自上而下算法类似[12]。正如Emmanuel Muller总结的那样：“根据基本的聚类模型,算法总是致力于解决效率和运行时之间的权衡。一般来说，高质量的结果往往需要付出更高的运行时间。”在本文中，我们的努力是为了在保持高质量结果的同时，以并行化的方法得到更高的效率。

2.2 并行子空间聚类

在一个深入的调查中，我们发现一个缺乏并行化的子空间聚类算法，不管它是否具有潜在的性能都可以从并行化中得到性能提升。我们所知，到目前为止只有两种并行化的实现方法。它们采用特殊的架构如消息传送接口(MPI)和并行随机存储器(PRAM)。和现今的Spark框架相比，这些模型遭受不小的高沟通成本和复杂的故障恢复机制。而且，它们不像Spark具有可扩展性也不具备灵活性。

基于网格的并行MAFIA[23]算法作为CLIQUE的扩展被提出，MAFIA把每一个维度划分为具有不同密度和离散自适应的实体。为了使算法并行的运行，原始的数据集被随机的划分成几部分并且被不同的节点读取。数据并行处理基于无共享框架，它组成一个纯粹的MapReduce版本使它显著的减少执行时间。然而，生成的分区可以高度倾斜，极大地影响聚类结果的质量。

另外一种并行算法是基于局部自适应聚类的(LAC)，LAC作为一种自上而下的方法被提出，目的是在相应的子空间集群基于维度的相关性为权重向量赋值。并行LAC算法在文献[26]中被提出，它是在一个n维的子空间转换集群任务来发现K形心得集群。鉴于共享全局内存的K x N处理器，PLAC把每个节点的整个数据集分布在一个K形心得网格上。在本实验中，他们用一台主机作为全局共享内存，假设整个数据集可以适应一个节点。这种结构设计严重的限制了PLA

C的可扩展性，因为数据集的最大值不能超过10000点[26]

3.CLUS：Spark上的并行子空间聚类算法

3.1 SUBCLU算法

SUBCLU遵循着自底向上模式和贪心策略，它通过使用DBSCAN算法来检测子空间上所有基于密度的集群。首先，在每一维度执行聚类过程从而产生一系列的一维子空间，然后，SUBCLU通过结合K维的候选集和K-1维的共享集群递归的生成K 1维的候选集群。反单调性用来删除无关的候选集。为了增加随后聚类过程的效率，拥有最小聚类数据的K维子空间被选作为最好来运行DBSCAN，当没有集群时递归终止。该算法同样需要两个参数：epsilon和minpts。关于SUB CLU更加详细的介绍可以查看文献[8]

3.2 CLUS算法

CLUS是Spark上的一个并行算法，它克服了SUBCLU的局限性。SUBCLU为每个子空间顺序地运行DBSCAN聚类，并等待为下一个维度生成候选集之前终止所有实例，CLUS可一次并行的执行多个DBSCAN聚类。候选集的生成和修剪步骤也以一个分布式的没有迭代数据集的形式表现。为了诱导数据本地化和提高整体性能，CLUS充分利用了Spark的优势，如ReduceByKey，AggregateByKey等

值得一提的是Spark能通过洗牌和重新分配操作独立的将数据放到所需要的节点中。然而，这些源数据的移动造成了缓慢的磁盘和RAM I/O操作甚至降低了网络I/O。此外，Spark尝试为了保证数据的本地性使用了前面提到的自治机制，可能导致效率低下，因为他们可能会进一步引发其他不必要的数据混乱。这些可有可无的耗时操作在大多数MapReduce平台上是一个非常普遍的问题并且应该尽可能避免。数据管理策略为了实现这一目标必须仔细考虑，为了在任何时刻提供精确的分区对实现负载均衡和提高性能具有重要意义。

CLUS算法的主要挑战是确保：1）每个节点有所需的数据去运行子空间聚类；2）为了确保子空间聚类的同时性部分数据的复制显得很必要；3）数据洗牌和重新分配的最小值；4）节点是平衡的并且只有特定的数据可以在它们间传输；5）没有空闲节点；6）这些信息总是以(KEY，Value)的结构存储和访问的。

Fig. 1.Pseudocode of CLUS algorithm

CLUS的伪代码如图1所示。算法遵循了和SUBCLU相同的理念，但设计的目的是为了减少数据的再分配和提高基于密度聚类任务的效率。CLUS通过列名/功能方式管理输入信息以便不同的列以键值对的形式存储在不同的机器上。算法首先运行并行的DBSCAN。维度和集群点被用作生成K 1维的候选集，这些候选集是在K维的子空间上增加一维不相交的维生成的，生成的K 1维子空间可能需要同样的列来呈现在不同的机器上，所以在数据复制时一个高效的flatMap-l eftOuterJoin-reduceByKey模式被运用。这种机制允许CLUS在每个子空间上同时的执行DBSCAN。基于密度的聚类在高维度的子空间上再次执行，但只使用那些在较低的子空间上没有被标记为噪声的点。在得到的结果上进行修剪步骤以删除重复的候选集。此外，基于反单调性，所有K 1维子空间包含一个K维子空间。为此，缺乏生成K 1维的子空间地集群将被淘汰。为了下一次的迭代，这些子空间从有效的K 1为子空间池中被移除。当没有更高的子空间生成时，CLUS算法也随之终止。

图2中阐明了CLUS算法数据工作流情况，为了更清晰一些操作被省略了，因此只展示了最重要的步骤。图的上部分展示了聚类在每一维是怎么运行的和任务是怎样分布在Spark的各个节点上的。如图所示，数据从HDFS上得到后通过键值对识别出行和列。每一个值有一个列和行的索引，它们形成RDD的数据格式。该RDD是分布在所有节点上的，所以每一个节点都有一列。DBSCAN以一种分布式的方式运行，并且一个新的带有集群索引的RDD被获取。RDD被进一步的用作生成K 1

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[148193]，资料为PDF文档或Word文档，PDF文档可免费转换为Word

原文和译文剩余内容已隐藏，您需要先支付 30元 才能查看原文和译文全部内容！立即支付

以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。

您可能感兴趣的文章