基于MapReduce的并行K-means聚类外文翻译资料

 2021-11-26 22:14:07

英语原文共 6 页

基于MapReduce的并行K-means聚类

摘要 数据聚类在许多应用中受到了相当多的关注，例如数据挖掘，文档检索，图像分割和模式分类。随着技术进步而不断增加的信息量使得大规模数据聚类成为一项具有挑战性的任务。为了解决这个问题，许多研究人员试图设计出高效的并行聚类算法。在本文中，我们提出了一种基于MapReduce的并行K-means聚类算法，这是一种简单但功能强大的并行编程技术。实验结果表明，该算法能够很好地拓展，并且能够有效地处理商用硬件上的大型数据集。

关键词：数据挖掘；并行聚类；K-means；Hadoop；MapReduce

  1. 绪论

随着信息技术的发展，许多应用处理的数据量将经常超过千兆级，这反过来会增大计算要求。高效的并行聚类算法和实现技术是满足此类科学数据分析所需拓展性和性能要求的关键。到目前为止，一些研究人员已经提出了一些并行聚类算法。所有这些并行聚类算法都有以下缺点：a)他们假设所有对象可以同时驻留于主存储器内；b)他们的并行系统提供了受限制的编程模型，并使用这些限制自动地并行化计算。对于具有数百万个对象的巨大数据集，这两个假设都是被禁止的。因此，应该开发面向数据集的并行聚类算法。

MapReduce是一个编程模型，也是一个用于处理和生成适用于各种实际任务的大型数据集的相关的实现。用户根据map和reduce函数对计算进行指定，底层运行时系统自动地并行化大型机器集群的计算、处理机器故障并安排机器间通信，以便有效地使用网络和磁盘。Google和Hadoop都为MapReduce运行时提供容错和动态灵活性支持。

在本文中，我们在MapReduce框架中实现k-means算法，该框架由Hadoop实现以使得聚类方法适用于大规模数据。通过使用适当的键值对，所提出的算法可以被有效地并行执行。我们进行了全面的实验来评估所提出的算法。结果表明，我们的算法可以有效地处理大规模数据集。

本文的其余部分安排如下。在第2节中，我们提出了基于MapReduce框架的并行k-means算法。第3节显示了实验结果，并在加速效果、运行规模和处理数据集大小方面评估了们的并行算法。最后，我们在第4节中给出结论。

  1. 基于MapReduce的并行K-means算法

在本节中，我们将介绍基于MapReduce的Parallel K-Means（PKMeans）的主要设计。首先，我们简要概述了k-means算法，并对算法中的并行部分和序列部分进行了分析。然后我们详细说明了如何将必要的计算形式化为map和reduce操作。

    1. K-means算法

K-means算法是最著名和最常用的聚类方法。它获取输入参数k，并将一个含n个对象的集合的划分为k个簇，使得到的簇内相似性高，而簇间相似性低。簇的相似性是根据簇中对象的平均值来度量的，可以将其视为群集的“重心”。

该算法的执行过程如下：首先，它从表示初始聚类中心的所有对象中随机选择k个对象。根据对象与簇中心之间的距离，将每个剩余对象分配给与其最相似的簇。然后计算每个簇的新均值。该过程迭代直到标准函数收敛。

在k-means算法中，最为密集的计算是对距离的计算。在每次迭代中，它将需要总共（nk）次距离计算，其中n是对象的数量，k是正在创建的簇的数量。显然，一个对象与中心之间的距离计算与具有相应中心的其他对象之间的距离计算无关。因此，不同对象与中心点之间的距离计算可以并行执行。在每次迭代中，应更新在下一次迭代中使用的新中心。因此，迭代过程必须连续执行。

    1. 基于MapReduce的PKMeans

综上所述，PKMeans的实现需要用到一种MapReduce作业。Map函数执行将每个样本分配到距其最近的中心的过程，而reduce函数则执行更新新中心的过程。为了降低网络通信的成本，combine函数被开发出来以处理同一map任务内拥有相同键值的中间值的部分组合。

Map函数 输入数据集作为键值对的序列文件存储在HDFS中，每个键值对都对应数据集中的一条记录。键代表此纪录到数据文件起始点的以字节为单位的偏移量，值是该记录内容的字符串。数据集被拆分并全局广播到所有mapper。因此，距离计算是并行执行的。对于每一个map任务，PKMeans构建全局变量中心，该中心是一个包含簇中心信息的数组。通过给定信息，mapper可以计算出每个样本的最近中心点，然后，中间值由两部分组成：最近中心点的索引和样本信息。Map函数的伪代码如算法1所示。

算法1. map(key, value)

输入：全局变量中心，表示偏移的键(key)，样本值(value)

输出：键值对（lt;keyrsquo; , valuersquo;gt;），其中keyrsquo;表示最近的中心点的索引而valuersquo;是一个包含样本信息的字符串

  1. 根据value构造样本实例；
  2. minDis = Double.MAX_VALUE
  3. index = 1;
  4. for i = 0 to centers.length do

dis = ComputerDist( instance, centers[i]);

if dis lt; minDis {

minDis = dis;

index = i;

}

  1. End for
  2. 将index作为keyrsquo;;
  3. 构造valuersquo;作为一个包含不同维度的值的字符串
  4. 输出键值对；
  5. End

注意 步骤2和步骤3初始化辅助变量minDis和index;步骤4计算距离样本最近的中心点，其中函数ComputeDist（instance，centers [i]）返回实例与中心点centers [i]之间的距离; 步骤8输出在后续过程中使用的中间数据。

Combine函数 在每个map任务之后，我们应用combiner来组合同一map任务的中间数据。由于中间数据存储在主机的本地磁盘中，因此该过程不会产生通信成本。在组合函数中，我们部分地对分配给同一簇的点的值求和。为了计算每个簇中对象的平均值，我们应该在同一个map任务中记录同一簇中的样本数。Combine函数的伪代码如算法2所示。

算法2. combine(key, V)

输入：表示簇索引的key，表示属于同一簇的样本的列表的V

输出：键值对（lt;keyrsquo; , valuersquo;gt;），其中keyrsquo;表示簇的索引，valuersquo;表示一个包含同一簇中样本之和及样本数量的字符串

  1. 初始化一个数组来记录同一簇中样本各维度值的和，例如：列表V中的样本
  2. 初始化一个计数器num来从0开始记录同一簇中样本的数量
  3. While(V.hasNext()) {

根据V.next()构造样本实例；

将实例中各个维度的值添加进数组；

num ;

  1. }
  2. 将key赋值给keyrsquo;;
  3. 构造valuersquo;作为一个包含不同维度值之和及num的字符串；
  4. 输出键值对；
  5. End

Reduce函数 Reduce函数的输入是从各个主机的组合函数中所获得的数据。如Combine函数中所描述，数据包括相同簇中样本的部分和与样本的数量。在reduce函数中，我们可以对所有样本求和并计算分配给同一簇的样本总数。因此，我们可以获得用于下一次迭代的新中心。Reduce函数的伪代码如算法3所示。

算法3. reduce(key,V)

输入：表示簇索引的key和表示不同主机的部分和的列表V

输出：键值对（lt;keyrsquo; , valuersquo;gt;），其中keyrsquo;表示簇的索引，valuersquo;是一个代表新中心的字符串

  1. 始化一个数组来记录同一簇中样本各维度值的和，例如：列表V中的样本
  2. 初始化一个计数器NUM来从0开始记录同一簇中样本的数量
  3. While(V.hasNext()) {

根据V.next()构造样本实例；

将实例中各个维度的值添加进数组；

NUM = num;

  1. }
  2. 将数组条目除以NUM以获得新的中心坐标；
  3. 将key赋值给keyrsquo;;
  4. 构造valuersquo;作为一个包含中心坐标的字符串；
  5. 输出键值对；
  6. End
  1. 实验结果

在本节中，我们将评估我们提出的算法在加速效果、运行规模和处理数据集大小方面的性能。性能试验在一组计算机上进行，每台计算机都有两个2.8GHz的核心和4GB内存。对于所有实验，MapReduce系统均使用0.17.0版本的Hadoop和1.5.0_14版本的Java。

为了衡量加速效果，我们保持数据集不变并增加系统中计算机的数量。完美的并行算法将展现线性加速：计算机数量为m被的系统产生的加速效果为m。然而，线性加速是难以实现的，因为通信成本随着簇的数量的增大而增大。

图1 评估结果

我们对具有不同大小、基于不同系统的数据集进行了加速评估。计算机的数量为1到4不等。数据集的大小从1GB增大至8GB。图1.(a)展示了对不同数据集的加速效果。结果表明，PKMeans有很好的加速性能。具体来说，随着数据集大小的增长，加速效果也变得更好。因此，PKMeans算法能够有效地处理大型的数据集。

规模放大测试则评估算法在系统和数据集同时增大时的处理能力。规模放大测试定义为算法在使用m倍规模的系统，在与原始系统相同运行时间下处理m倍规模的任务时的表现。

为了展示PKMeans算法在有更多计算机可用时处理更大数据集的能力，我们进行了规模放大实验。实验中，我们增加了数据集的大小并使其与系统中的计算机数量成正比。1GB，2GB，3GB和4GB的数据集分别在1，2，3，4台计算机上进行处理。图1.(b)展示了数据集的处理结果。显然，PKMeans可以很好地扩展。

放大分析使系统中的计算机数量保持不变，并使数据集的大小增大系数m倍。放大测试将测量当数据集大小比原始大小大m倍时，系统执行需要的时间。

为了测试放大性能，我们将计算机的数量分别固定为1，2，3和4。图1.(c)显示了不同计算机的放大测试结果。图像显示PKMeans具有非常好的放大性能。

  1. 结论

数据聚类已经引起了大量的研究关注，过去几十年间，许多聚类算法被提出。然而，应用中不断增大的数据量使得非常大规模的数据聚类成为了一项具有挑战性的任务。在本文中，我们提出了一种基于MapReduce的快速并行k-means聚类算法，该算法已被学术界和工业界广泛接受。我们使用加速测试、规模增大测试和数据放大测试来评估我们提出的算法的性能。结果表明，该算法能够有效地处理商用硬件上的大型数据集。

致谢 这项工作得到了国家自然科学基金（No.60675010,60933004,60975039），863国家高技术计划（No.2007AA01Z132），国家基础研究重点项目（No.2007CB311004）和国家科技支撑计划No.200-6BAC08B06）的支持。

参考文献

1. Rasmussen, E.M., Willett, P.: Efficiency of Hierarchical Agglomerative Clustering Using the ICL Distributed Array Processor. Journal of Documentation 45(1), 1–24 (1989)

2. Li, X., Fang, Z.: Parallel Clustering Algorithms. Parallel Computing 11, 275–290 (1989)

3. Olson, C.F.: Parallel Algorithms for Hierarchical Clustering. Parallel Computing 21(8), 1313–1325 (1995)

4. Dean, J., Ghemawat, S.: MapReduce: Simplified Data Processing on Large Clusters. In: Proc. of Operating Systems Design and Implementation, San Francisco, CA, pp. 137–150 (2004) lt;/

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

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

您可能感兴趣的文章