K-Means聚类与Bagging和MapReduce外文翻译资料

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

K-Means聚类与Bagging和MapReduce

Hai-Guang Li1, Gong-Qing Wu1, Xue-Gang Hu1, Jing Zhang1, Lian Li1,Xindong Wu1, 2

1计算机科学与信息工程学院

2佛蒙特州大学计算机科学系,伯灵顿,VT 50405,美国

lee.haiguang@gmail.com,wugongqing@gmail.com,jsjxhuxg@hfut.edu.cn,

hfzj870608@126.com, llian@hfut.edu.cn, xwu@cs.uvm.edu

摘要

聚类是最广泛使用的技术之一用于探索性数据分析。在所有学科，从社会科学到生物学到计算机科学，人们试图通过获得他们的数据的第一直觉识别数据对象中的有意义的组。K-means是最有名的聚类之一算法。它的简单性和速度允许它运行大数据集。但是，它也有几个缺点。首先，这种算法不稳定对离群值敏感。二，其性能会在处理大数据集时效率低下。在这里提出了一种解决这些问题的方法，其使用集合学习方法克服对异常值的不稳定性和敏感性，同时使用分布式计算框架MapReduce来解决无效率问题聚类在大数据集上。 广泛的实验已经表明我们的方法是高效的。

1. 介绍

聚类是最重要的之一无监督学习方法[1]。松散的定义的聚类可以是“组织的过程对象分组，其成员在某些类似办法”[2]。所以，聚类的目标是确定内在组在一组未标记的数据集群是因此一组在其间“相似”的对象它们与属于的对象“不相似”其他集群。集群有很多应用程序许多领域，如市场研究，图像分析，生物信息学，计算生物学，机器学习，数据挖掘，知识发现，模式识别和模式分类。K-means是一个着名的聚类算法，即一个最简单的无监督学习算法，它通常非常快[3]。它也是数据挖掘中前10个算法之一[4]。然而，不能保证其将收敛到全局最优，因为它是一个启发式算法，并且有不同的选择的初始簇可能产生不同的结果。近年来，聚类分析已经进行蓬勃发展。有几个变体k-means算法：EM算法维护概率分配到集群，而不是k-均值中的确定性分配; K-means 寻求选择更好的起始集群 - 一种避免的方式有时较差的聚类通过标准kmeans算法找到; 过滤算法加速每个k-means步骤使用kd-trees [5]，而一些其他方法采用coreset [6]或三角形不等式[7]; 甚至在之间交换对象簇被用来逃避局部最优[8]。

同时，仍然有几个问题变化算法。一个重要的问题关注的是k均值的不稳定性和敏感性异常值。 此外，处理高维度并且大数据集可能由于时间而成问题复杂。

在机器学习中，组合是一种技术其使用模型的集合以便获得比集合中的任何模型更好的结果[9]。Bagging是最受欢迎的合奏之一技术。MapReduce是一个编程模型和用于处理的相关实现生成大数据集[10]。

为了解决上述问题，本文提出了一种名为MBK-means的方法，采用袋装提高稳定性k-means的精度，并使用MapReduce来解决在大数据集上聚类的低效率问题。

本文的主要贡献可以总结如下：

1. 克服不稳定性和敏感性到k-均值的异常值，集合学习方法包装进行改进稳定性和准确性。
2. 聚类中的无效率问题大数据集通过使用分布式解决计算框架MapReduce。
3. 已经进行了广泛的实验上述问题以显示我们的方法在解决方面是高效的。

本文的其余部分组织如下。第2节讨论相关工作。MBK-means算法详见第3节。第4节显示性能评价和比较实验结果。 最后，本文以一个结论结束第5节。

1. 背景

在本节中，介绍算法并提出了本文所采用的技术。 一个关于k-means的概述在第2.1节中给出，bagging 在第2.2节和MapReduce在第2.3节。

• 1. K-means

詹姆斯·麦克奎恩首先使用了“k-means”一词1967年，虽然这个想法可以追溯到雨果Steinhaus在1956年[3]。斯图尔特·劳埃德首先提出标准算法在1957年，虽然不是发表于1982年[11]。

K均值聚类是一种聚类分析方法其目的是将非对象分为k个簇其中每个对象都属于集群最近质心。 它试图找到的中心在数据集中的自然群集[12]

给定一组对象（x₁，x₂，...，x_n），其中每个对象是一个d维向量，k均值聚类旨在将无对象划分为k个集合（k lt;n）S = {S₁，S₂，...，S_k}。k均值算法是由以下步骤组成：

1. 给定k mean m₁^（1）的初始集合，...，m_k^（1），其可以随机地或由一些指定启发式。
2. 分配步骤：将每个对象分配给组具有最接近的质心。

1. 更新步骤：当所有对象都已经分配，重新计算k的位置质心。

重复步骤2和3，直到平均值不再存在移动。 这产生对象的分离划分为从中获得度量

的组最小化可以计算。

k-means算法通常是有效的，特别是当群集是紧凑的和分离的，但它是不太有效的群集嵌套。 产生的结果取决于初始值值的手段，它经常发生次优分区。

关于计算复杂性，如果k 和 d是固定的，问题可以及时解决上O（n^{(dk 1)}logn），其中n是要对象的数量聚类和d 是对象的向量维度。

• 1. Bagging

集合方法使用多个学习者和结合他们的预测，一起解决问题，其可以获得比任何一种更好的性能组成模型[3]。

Bagging，一个从bootstrap派生的名称聚集，由Leo Breiman在1994年提出是集成学习的第一个有效方法改进模型的稳定性和准确性，以及减少方差并帮助避免过度拟合[13]。 并且它也是最简单的拱形方法之一。

该方法使用训练集的多个版本通过使用引导程序，并使用每个数据集训练不同的模式。这些模型的输出是通过平均或投票结合获得单一输出。
Bagging是模型平均的一个特例，是最初设计用于分类，并可以使用与任何类型的模型，虽然它通常应用到决策树模型。

• 1. MapReduce

MapReduce是一个编程模型和相关实现进行处理和生成大数据集，这是由介绍Google解决某些类型的可分发问题。用MapReduce的函数式编写的程序可以自动并行化和高执行性能计算集群大量低成本的普通个人电脑。它的灵感来自map和reduce函数，用户指定地图函数，用于处理（键，值）对以生成一组中间（键，值）对和一个reduce函数，合并所有中间值相关联与相同的中间密钥[10]。

主要优点是map和reduce允许MapReduce的功能分布式处理。每个映射操作独立于其他。 因此，可以执行所有的映射操作并行，并且一组reduce操作可以并行执行。同样，一组reduce操作可以执行缩减阶段独立地。

由用户写的映射函数取一个在数据域中具有类型的数据对，并返回一个在相同或不同域中的对的列表。它是并行应用于每个（k₁，v₁）对，并产生一个每个映射调用的中间（k₂，v₂）对的列表。

之后，MapReduce框架收集所有中间（k₂，v₂）对与来自所有的相同的键列出并将它们组合在一起，从而创建一个组为每个不同的生成的密钥，并通过他们到reduce函数。reduce函数，也由用户写，是然后并行应用于每个组，并产生a在同一域中的值的集合。 它接受一个中间密钥k₂和用于k₂的值列表（v₂）的列表。它将这些值合并在一起以形成可能更小的值值列表列表（v₃）。 每个reduce调用通常产生一个或一个空的返回。 回报所有呼叫都将收集为所需的结果列表。

因此MapReduce框架转换列表（键，值）对转换为值列表。Apache Hadoop是一个允许的软件平台用户编写和运行处理浩大的应用程序数据量很容易[15]。Hadoop实现MapReduce与HDFS（Hadoop分布式文件系统）。 HDFS被设计为在商品上运行硬件。 它与现有的有很多相似之处分布式文件系统。

1. MBK均值算法

MBK均值框架如图1所示。在步骤1中，它产生已知的训练集合D _i（i = 1，...，k）从给定的标准训练集D（第3.1节）。步骤2聚类D_i使用k-means和MapReduce框架（第3.2节）。 获得质心后质心s_i的D_i，我们组合质心 s_i（i = 1，...，k）和

更新质心3步骤（3.3节）。

图1. MBK-means框架

3.1 数据分割和距离测量

给定尺寸为n的标准训练集D，bagging生成新的训练集D _i尺寸nrsquo;le;n（i = 1，...，k），通过从Uniformly和with的抽样例子替代。在本文中，n被设置为n，而m

被设置为k，其是k均值中的簇的数量。

因为相似性是一个定义的基础簇，两者之间的相似性的度量对象是大多数聚类过程的关键。它是共同计算两者之间的差异对象使用距离测量。距离是一个对象间隔多远的数字描述。在物理或日常讨论，距离可以参考物理长度或基于其他标准的估计。在数学，距离函数或度量物理距离的概念的概括。在本文采用闵可夫斯基距离进行测量两个对象之间的相似性或不相似性，其定义为：

其中obj_i =（x_i1，x_i2，...，x_id）和obj_j =（x_j1，x_j2，...，x_jd） 是两个d维数据对象，q是正整数。在本文中，q被设置为2.因此，闵可夫斯基距离演变成欧氏距离。距离函数可以在中计算O（d）。

3.2 K-means与MapReduce

k均值算法花费大多数执行时间计算对象之间的距离聚类质心。 对于非常大的数集，迭代计算对象之间的距离常常导致一个系统过载。然而，这个过程，为算法本身所必需，因此我们必须考虑提高效率算法从其他方面。 因此，加强性能的距离计算是关键提高算法的时间性能。然而，这个过程，为算法本身所必需，因此我们必须考虑提高效率算法从其他方面。 因此，加强性能的距离计算是关键提高算法的时间性能。

显示了具有MapReduce的k-means框架在图2中的细节如下：

1. 将kpoint放入由正在集群的对象。这些点代表初始组的质心。
2. 将每个对象分配给具有的集群最近质心：此步骤对映射器操作如图2所示，图3

概述了kmeans_in_Map算法。

1. 当所有对象都已分配，重新计算k个质心的位置：此步骤正在运行如图2和图4

所示k-means_in_Reduce算法。

重复步骤2和3，直到质心不再移动。 这产生物体的分离要从其最小化的度量可以是

哪个簇计算。

图2.带有MapReduce的K-means框架

k-means算法的映射函数使用MapReduce如图3所示，并且这个函数在集群中的每个映射器上运行。此函数将对象分配给最近的质心。

此函数使用距离法计算对象和每个质心之间的距离在步骤3中。在找到与对象最近的质心之后，此函数将对象放入集群其包含质心步骤8。k-means算法的reduce函数使用

MapReduce如图4所示，并且这个函数在集群上的每个reducer上运行。 这个功能计算群集的新质心。

此函数首先获取此集群中的所有对象步骤3，然后使用reCalCentroid函数重新计算集群中对象的质心在获得聚类的新质心之后，此函数返回步骤6中的质心。

函数K-means_in_Map

输入：质心，输入//输入的键是原始文本中输入段的偏移量（数据设置），并且输入的值是对象聚类。 质心是原始质心，并通过MapReduce的JobConf提供给map函数。

输出：输出。 //输出的关键是最接近该对象的簇，输出的值为物体。

图3. K-means_in_Map算法

函数K-means_in_Red

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

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