基于MapReduce的ROCK聚类算法*

2014-03-02陈龙飞

河北科技师范学院学报 2014年1期

赵雪，陈龙飞

(1燕山大学信息科学与工程学院，河北秦皇岛，066004;2河北经贸大学信息技术学院)

“大数据”时代的到来改变了人们许多处理问题的思路和想法，因为数据的庞大，迫使人们不再单一追求处理数据的高精确率，而是要求快速;不再去对海量数据进行类似数学统计似的抽样处理，而是进行全面处理;不再专注于找出数据之间的因果关系，而是注重数据之间的相关性［1］，这对于聚类算法［2］来说是一个挑战。

传统的聚类算法通常是分析数据集中各个数据点的特征，从而将未知归属的各个数据点进行聚类。然而随着“大数据”时代［3］的到来，分析数据点特征的工作变得非常困难，因为数据点作为一个处理对象必然包含各种属性，原来的数据对象可能只包含几个属性或几层属性，而现如今的处理对象动辄包含几百上千的属性，其属性的层次或结构也变得多种多样，或者说数据对象内部本身是毫无结构的［4］，这对于传统聚类算法将是难以容忍的。它的主要障碍在于单个计算机的运算速度和内存容量不能处理这种数据大规模聚集的情况［5］，不管从处理速度还是效率都达不到大数据的处理要求。ROCK算法［6］是一个面向分类属性的聚类算法，它以公共邻居数作为评定数据点间相关性度量的标准，能够较好地处理多属性数据和无结构数据，如果在此基础上应用典型的“大数据”计算模型MapReduce［7］对其进行改良，将会在很大程度上提升对大数据进行聚类的能力。

1 ROCK聚类算法在MapReduce上的实现

1.1 ROCK 算法介绍

ROCK(Robust Clustering Using Links)算法是一种凝聚的层次聚类算法，是由Guha等在1999年提出的，适用于类别属性。

对于具有分类属性的数据，传统的聚类算法一般采用距离函数来度量数据对象间的相异度。然而，实验表明这种距离度量方法对具有分类属性的数据不能得到好的聚类结果。而且绝大多数聚类算法只考虑点与点之间的相似性，因此在聚类的每一步，具有最大相似度的点被合并到同一个簇中很容易导致错误的合并。例如，有几个点来自2个显著不同的簇，而这几个点非常接近，那么根据上述的点与点之间的相似度，这2个显著不同的簇将被错误地合并在一起。为了避免这种情况，ROCK采取了更加周全的方法，也即引入了邻居的概念［8］。如果2个点不仅它们本身相似，而且它们的邻居也相似，则这2个点可能属于同一个簇，因此被合并。

定义1 邻居:2个点Pi和Pj，如果满足sim(Pi，Pj)A，则称Pi和Pj为邻居。其中，sim是一个相似性度量函数，A是由用户给定的阈值。sim可以是一个距离度量甚至是由领域专家提供的非形式化的度量，只要它能够标准化为0和1之间的值，而且这种值越大，相应两点间的相似度越高。

定义2 连接:link(Pi，Pj)为2个数据点Pi和Pj的相同邻居数，值愈大表明Pi和Pj同一簇的几率愈大。

在聚类过程中，需要最大化簇内link(Pq，Pr)数量的同时最小化簇间link(Pq，Pr)的数量，即保证簇内尽量相似、簇间尽量不相似。此式子能够帮助找到簇内最多链接的同时尽量减少簇间链接数。其中，ni为簇Ci中数据点的总数，f(θ)是根据数据集设定的一个函数。

此优化函数用于合并相似簇，而且能够有效避免出现离群数据点时将所有簇都合并。其中为2簇中预期交叉链接个数。ni为簇Ci中数据点的总数，nj为簇Cj中数据点的总数，link［Ci，Cj］指簇 Ci和簇 Cj之间的链接数。

ROCK算法流程如下:

■输入参数:包含n个数据点的集合S及预期簇数k;

■最初阶段，每个数据点为1簇;

■计算各点的链接数;

■为每个簇i，建立1个区域堆q［i］，包含每个与簇i的链接数不为0的簇j;

■q［i］中的各簇 j依 g(i，j)值由大至小排序;

■建立全局堆(global heap)Q，包含每个q［i］的优化函数最大值的簇j;

■每一回合，合并Q中最佳簇j与q［j］中的最佳簇;

■合并的同时重新运算各区域堆及全域堆，包括新形成的簇;

■当簇数不小于k时，持续合并，此外当所有q［i］=0时停止合并。

1.2 MapReduce编程模型

MapReduce是由Google提出的一种处理海量数据的并行编程模式［9］，用于大规模数据集的并行计算，由Map(映射)操作和Reduce(化简)操作2个阶段组成，Map操作把任务分解成为多个任务，Reduce操作把分解后任务处理的结果汇总起来，得到最终结果。

(1)MapReduce编程思想

以Hadoop为平台的大数据处理模式，通过HDFS系统去进行信息存储、分享，使用MapReduce技术去进行分析和挖掘，可以便宜、有效地将这些大量、高速、多变化的终端数据存储下来，并能快速得到所需的结果。改进后的ROCK算法命名为HD-ROCK算法。

HD-ROCK算法是在ROCK算法的基础上进行改进的，它继承了ROCK算法针对类别属性进行聚类的思想，同时将原算法中对数据进行处理的部分进行了分割、再整合的处理，在没有改变原算法执行顺序的同时，提高了每一部分运行的速度，使新算法的整体速度得到了提升。

数据去重是新算法的核心目的［10］，就是让原始数据中出现次数超过1次的数据在输出文件中只出现1次。

Map处理的是一个纯文本文件，文件中存放的数据是每行表示1个用户的姓名及其所购买的项目类别。Mapper处理的数据是由InputFormat分解过的数据集，其中InputFormat的作用是将数据集切割成小数据集InputSplit，每个InputSplit将由1个Mapper负责处理。此外，InputFormat中还提供了1个RecordReader的实现，并将1个InputSplit解析成＜key，value＞对提供给map函数。InputFormat的默认值是TextInputFormat，它针对文本文件，按行将文本切割成 InputSplit，并用 LineRecordReader将 InputSplit解析成＜key，value＞对，key是行在文本中的位置，value是文件中的一行。Map的结果会通过partion分发到Reducer，Reducer做完Reduce操作后，将通过以格式OutputFormat输出。Mapper最终处理的结果对＜key，value＞，会送到Reducer中进行合并，合并时有相同key的键/值对则送到同一个Reducer上。Reducer是所有用户定制Reducer类的基础，它的输入是key和这个key对应的所有value的一个迭代器，同时还有Reducer的上下文。Reduce的结果由 Reducer.Context的 write方法输出到文件中。这就是一个mapreduce的循环。

新算法对原算法的改变主要体现在2个方面:一是对用户之间相似度的计算和共同邻居数的计算上;二是在分别建立堆q(i)以及相近堆的合并上。

因为ROCK算法中需要计算任意2个用户之间的相似度，并根据相似度判断邻居数，而且数据集中任意一个数据对象之间是完全独立、没有关联的，所以可以利用Hadoop思想对其进行分布式处理，用十多台甚至上百台设备去处理原来1台设备所处理的问题将大大提升处理速度，而且不会遇到同步和异步问题。

在建立堆q(i)和Q时需要消耗大量的内存，而当进行堆与堆之间的合并时，同一时间内对所有堆的大小进行比较，这对于1台设备而言是无法承受的，所以运用分布式进行处理，让不同的设备建立代号不同的堆，需要合并时会按照键值对的值进行处理，这将大大地缩减建立堆和处理堆的时间。

HD-ROCK算法的流程如下(图1):

●设定数据集S包含n个数据点，预期簇数为k;

●将每个数据点设定为1个簇;

●将数据集S分为m组，在每份中，分别计算分组中每个点与整个数据集S中的每个点之间的相似度，得到数据集S的邻居矩阵(是邻居的为1，不是邻居的为0)，其中D是S数据集中的数据，n是S集中数据的个数;

●计算分组中每个数据点与整个数据集S中每个数据点之间的共同邻居数，得到键值对L＜(Pi，Pj)，link(Pi，Pj)＞，其中Pi和Pj为数据集S中的任意点，并得到邻居数矩阵;

●为各组中每个数据点建立堆q(i)＜Pi，link(Pi，Pj)＞;

●建立全局簇Q，降序存放所有堆q(i);

●在Q中找到最大元素的编号u;

●在u中找到最大元素的编号v;

●用优化函数进行合并，去除合并前的簇;

●更新Q;

●直到簇数小于k时结束;

(2)MapReduce函数的设计

Map1函数，是Map函数的主要构成之一，它的作用主要在于对数据集进行分块处理，是分布式处理的开端，而本函数的任务则是对数据集进行并行化处理，计算数据集S中各个数据点之间的相似性，并形成中间键值对＜key，value＞，即＜Pj，邻居矩阵Nj＞。其伪码描述如下:

Combine2的任务是合并Q中最相似簇并判断Q中簇的个数，如果大于k，则返回map3继续执行。

1.3 时间复杂度和空间复杂度分析

假设数据集中样本点的总数为n，设备数目为m，其中Mm和Ma分别为1个点的平均近邻数和最大近邻数。

(1)原算法首先计算各个数据点之间的相似度，这一阶段的时间复杂度为O(n);而新算法也同样需要计算各个数据点之间的相似度，但是由于新算法采用了分布式处理，所以其时间复杂度为O(n/m);

(2)在计算完数据点之间的相似度后需要计算邻接矩阵，原算法在这一阶段的时间复杂度为O(n*Mm*Ma);而新算法在此阶段的时间复杂度同样为O(n*Mm*Ma/m);

(3)计算共同邻居数，原算法在这一阶段的时间复杂度为O(n2);而新算法在此阶段的时间复杂度同样为O(n2/m);

(4)建立堆的时间。原算法中，总的建堆时间为O(n2)，执行循环的次数为O(n2*lgn);而新算法在此阶段的建堆时间为O(n2/m)，执行循环的次数也是O(n2*lgn);

所以ROCK算法时间复杂度为O(n+2n2+n*Mm*Ma+n2*lgn);而新算法的时间复杂度为O((2n2+n*Mm*Ma+n*m)/m+n2*lgn)。

由此可知，其中m的数量决定新算法的效率。由于新算法只是对原算法中的可分离的独立数据进行处理，不涉及数据类型的改变，所以两者的空间复杂度都为O(min{n2，n*Mm*Ma})。

2 实验与结果分析

实验的目的在于验证基于MapReduce的ROCK聚类算法(HD-ROCK)在处理数据尤其是高维数据上的执行速度和正确率。为了让实验更加鲜明，将通过2组测试数据来验证新算法的正确性和时效性。

2.1 实验环境

采用Eclipse+Hadoop的结合去验证新算法的可行性。

2.1.1 Hadoop的配置 Hadoop有3种运行方式:单机模式、伪分布式模式和完全分布式模式。单机模式中，默认情况下，Hadoop被配置成一个以非分布式模式运行的独立java进程。伪分布式模式Hadoop可以在单节点上运行，用不同的java进程模拟分布式运行中的各类节点，如NameNode，DataNode，master，slave和taskTracker。在实际使用中，使用3台机器来搭建集群，3台机器均使用centOS6.3操作系统(linux操作系统之一)，第1台用于做NameNode，master和 jobTracker。另外 2 台用于做 DataNode，slave和 taskTracker。3台机器如表1所示。

图1 HD-ROCK算法流程

表1 Hadoop集群信息

2.1.2 eclipse在 Hadoop 中的配置

(1)安装MapReduce插件(Hadoop自带)。将 hadoop-0.20.2-eclipse-plugin.jar copy 至 eclipse/plugin 目录下即可。

(2)打开eclipse，创建MapReduce项目File＞New＞Project。在弹出的对话框中选择 MapReduce Project，输入 project name，如 HD-ROCK。

(3)建立 DFS Locations。Window-＞Show View-＞Other-＞MapReduce Tools-＞MapReduce Location。MapReduce Location配置如图2所示。

最后配置eclipse中的jdk，并将本地的 text文件导入到其中。

2.2 实验结果分析

为了验证基于Hadoop平台的HD-ROCK算法在处理大数据对象的正确性和时效性，采用2组测试数据进行验证。数据集DataSet1采用KDD Cup’99提供的经典数据集，用于测试基于Hadoop的HDROCK聚类结果的正确性。DataSet2采用加利福尼亚大学的机器学习数据集，其中包含许多随机的离群点分布在整个数据空间中，主要用于测试基于Hadoop平台聚类算法的时效性，即能不能做到处理速度的大幅提升。