并行计算是指同时使用多种计算资源解决计算问题的过程。其目的是快速解决大型且复杂的计算问题。其首要任务是将一个应用分解成多个子任务，将其分配给不同的处理器，同时各个处理器之间相互协同，并行地执行子任务，最后将所有子任务的结果合并形成整体的计算任务结果，从而达到加速求解的目的。

Hadoop是Apache软件基金会旗下的一个开源分布式计算平台，以Hadoop分布式文件系统(HDFS)和MapReduce(Google MapReduce的开源实现)为核心的Hadoop，为用户提供了系统底层细节透明的分布式基础框架^[10]。MapReduce是一种用于处理海量数据的编程模型，它将并行处理海量数据的过程抽象成为“Map(映射)”和“Reduce(化简)”两个步骤^[11]。Map任务将输入的文件转换成一个key-value对序列，Reduce将Map输出的键值对序列以某种方式进行合并和汇总，同时，Reduce输出的key-value对会按照key位进行排序。MapReduce的处理流程如图 1所示。MapReduce还提供Combine函数，Combine函数在Map结束后于本地进行结果合并，相当于本地的Reduce，可以大大减少网络I/O操作的消耗。通过MapReduce提供的接口，使得开发人员大大减少了并行化开发的工作量，可以高效地利用分布式资源，而不需要分布式计算的开发经验^[12]，实现该框架下的应用程序可以运行在大规模集群，而且集群对应用程序是透明的，具有很好的容错机制，能够可靠地并行处理大规模数据。

图  1  MapReduce处理流程

聚类是数据挖掘中的重要算法之一，它的目的是在无先验知识的条件下，按照数据集中数据本身的特点和差异，把一个数据集分割成若干个不同的类或簇，使得在同一个类中的数据对象的差异性尽可能小，而处于不同类中的数据对象的差异性尽可能的大。即可将聚类定义为：若数据集X中有n个数据点x，其中$X=({{x}_{1}},{{x}_{2}},\cdots ,{{x}_{n}})$，聚类的最终目的就是把数据集X分为k个类C_i，使得$X={{C}_{1}}\bigcup $ ${{C}_{2}}\bigcup \cdots \bigcup {{C}_{k}}\bigcup {{C}_{n}}$(其中，C_n为噪声)且${{C}_{i}}\bigcap {{C}_{j}}=\Phi $ ($i\ne j$)。需要说明的是，在模糊聚类中，每个数据点可能会属于多个类，因此类间可能会存在交集。

K-means算法是聚类算法中使用最为广泛的算法之一，其用到的数学思想简单，但效率高，且在对“圆形-球形”性质集合进行分类时，可以达到良好的聚类结果。传统K-means算法的执行过程如下所述^[13]：

1) 针对数据集$X=({{x}_{1}},{{x}_{2}},\cdots ,{{x}_{n}})$首先通过人工指定数字K作为要聚类的数目，并随机从样本点中选取相应数目的初始聚类中心$\{{{c}_{1}},{{c}_{2}},\cdots ,{{c}_{k}}\}$；

2) 计算各个样本点x_i到这k个聚类中心的距离，并把样本x_i归到与他距离最近的那个聚类中心c_i所在的类中；

3) 根据前一步的结果，计算同一个类中所有样本点的各维平均值，作为新一轮聚类的k个中心；

4) 再重复上述过程继续聚类，直至收敛。

简单地说，K-means聚类的目的，就是使得式(1)最小化：

其中，

K-means算法简单高效，但其缺点也十分明显。首先，聚类的数目依赖于k值设定，而在实际中，k值一般是难以界定的，而k值的指定决定了聚类的结果。其次，初始聚类中心是随机选择的，使得最终的聚类结果依赖于初始中心点的选择，导致结果的不稳定性^[14]。同时，在标准K-means算法中，许多距离计算是冗余的，因此当计算量很大时，算法的时间开销也非常大。

Canopy^[15]算法也是一种聚类方法，主要用于海量高维数据的聚类。Canopy可以粗略地将数据划分成若干个重叠子集，即Canopy(罩盖)。每个子集作为一个类簇，其一般使用一种代价低的相似性度量方法，以加快聚类的速度^[16]。因此，Canopy聚类一般用于其他聚类算法的初始化操作。Canopy算法中，Canopy(罩盖)的形成需要指定两个距离阈值，T₁、T₂(T₁>T₂)。首先，在数据集中选择一个点作为初始中心点加入到Canopy(罩盖)中心列表C中。对数据集中任意一个点x_i(${{x}_{i}}\notin C$)，若x_i与c_j(${{c}_{j}}\in C$)的距离均大于T₁，则将x_i作为一个新的Canopy(罩盖)中心加入到C中；若距离小于T₁，则将x_i加入以c_j为中心的罩盖中；若x_i与c_j的距离小于T₂，将x_i与c_j强关联，x_i不再能作为其他罩盖的中心，因此将其从

数据集中删去；反复以上过程，直至数据集为空^[17]。Canopy聚类允许有重叠子集，增加了算法的容错性和消除孤立点作用；同时，由于只需在罩盖内进行精确聚类，从而避免了对所有点精确聚类带来的计算量大的问题。

传统的K-means算法由于初始聚类中心选择的随机性，算法结果随着中心点选择的不同而改变，导致结果的不稳定性，可能会造成局部最优值的问题^[18]。针对中心点选择的问题，将Canopy算法作为传统K-means算法的初始化操作，快速地找出相对准确的聚类中心。本文将每一次Canopy形成的重叠子集称为罩盖，而每次K-means聚类形成的不重叠子集称为簇。在Canopy算法初始化过程中生成的重叠罩盖，使得数据集中的每一个点都至少属于一个罩盖中，因此，在进行K-means聚类的过程中，本文算法将不再考虑每个点到所有中心的距离，而只需计算点到其所属罩盖中心的距离，简而言之，K-means算法将在每个罩盖中进行，而随着K-means算法的迭代，每个罩盖中心也将不断变化，直至收敛。具体执行流程如图 2所示。

图  2  改进Canopy-K-means算法执行流程

由图 2可知，改进后的Canopy-K-means算法首先通过Canopy算法形成相互重叠的罩盖，再进行K-means迭代，最后产出聚类结果。具体分为6步：

1) 生成Canopy。即对于数据集$X=({{x}_{1}},{{x}_{2}},\cdots ,{{x}_{n}})$，通过Canopy算法指定的阈值T₁，T₂，迭代地找出初始中心点$\{{{c}_{1}},{{c}_{2}},\cdots ,{{c}_{k}}\}$，从而形成相互重叠的Canopy(罩盖)。

2) 数据点划分。在生成Canopy之后，由于数据集中每个数据点至少属于一个Canopy(罩盖)，而属于不同罩盖的点一定不属于同一个簇。因此，在计算新中心前，每个点已经明确属于某一个或几个罩盖中，从而不需要再计算每个点与每个中心点的距离，而只需计算其和其所属罩盖中心点的距离，并将其归入到其距离最近的罩盖中心点所属的Canopy(罩盖)中，形成相互不重叠的簇，减少了计算量。即对于任意点x_i，假设$C{{n}_{{{x}_{i}}}}=\{{{c}_{1}},{{c}_{2}},\cdots \}$是其所属Canopy中心集合，若x_i与其所属的某一个Canopy的中心点c_j距离最小，则将x_i划到c_j所属的Canopy中，并将其从其他Canopy中删除。

3) 计算K-means中心。利用上一步生成的簇，计算每个簇的新中心点，即求平均的标准K-means算法。

4) 合并K-means中心。由于前期采用了Canopy算法生成初始中心，而初始半径主要靠人工确定，如果初始半径选择过小，可能会出现中心点较多，或是在进行K-means聚类之后，新的中心点比较靠近的情况，因此在新中心点产生之后，对新中心进行检查，将距离较近的中心点进行合并，其对应所处的簇也相应合并，并计算合并后的新中心，从而产生一次迭代的最终K中心点，以避免人工确定半径带来的聚类效果不稳定的问题。

5) 形成新簇，产生新的重叠罩盖，并迭代。计算合并后K中心落在上一步产生的哪些Canopy(罩盖)中，将这些Canopy(罩盖)的中心点替换为新的K中心，形成新的重叠Canopy(罩盖)。该步骤和步骤4)就是合并产生新Canopy的过程。从步骤2)开始，重复以上步骤，直至算法收敛。

6) 形成聚类结果。在迭代结束之后，得到最终的罩盖，由于算法已经收敛，此时，只需将属于多个罩盖中的点归入到其距离最近的中心点所在Canopy(罩盖)中，形成不重叠的最终簇，完成聚类。

由上面的分析可知，本算法主要由3个阶段组成，即Canopy初始化阶段、K-means迭代聚类阶段，以及聚类结果产生阶段。

1) Canopy初始化阶段

在基于MapReduce的并行化算法中，Canopy初始化阶段有分为两个步骤：Canopy中心点的产生和Canopy的形成，分别对应于两个Job，分别为Job1和Job2，两个Job的执行流程及Map和Reduce过程实现如图 3所示。

图  3  Canopy初始化阶段流程

Job1中Map函数产生局部数据集的Canopy中心，Reduce阶段收集局部中心点，并执行与Map阶段同样的操作，合并局部中心点集，最后得到全局中心点集，并以<centorid，中心点各维度值>形式存放在本地，MapReduce过程可表示为：

Map：$X,{{T}_{2}}\to ＜''\text{centroid}'',{{c}_{i}}>$

其中，X为原始数据集，T₂为阈值，$''\text{centroid}''$为map的key值，c_i为计算得到的初始中心点值，${{c}_{i}}\in {{C}_{n}}$，Reduce过程与其类似；

Job2在Map阶段，每个Map节点加载Job1产生的全局Canopy中心，遍历子集中的所有数据点，判断其与Canopy中心的距离，将其加入与其距离小于t₁的Canopy，Reduce阶段负责整理各个Map产生的结果，产生Canopy，以<数据ID：数据各维值，所属Canopy列表(Canopy中心各维值)>的key-value对形式存储，MapReduce过程可表示为：

Map：$X,{{T}_{1}},{{C}_{n}}\to ＜i:{{x}_{i}},{{c}_{j}}>$

Reduce：$＜i:{{x}_{i}},{{c}_{j}}＞\to ＜i:{{x}_{i}},\text{List}({{c}_{j}})＞$

其中，c_n为所有Canopy中心的集合，$\text{List}({{c}_{j}})$为相应数据点所属Canopy中心集合，${{c}_{j}}\in {{C}_{n}}$。

2) K-means迭代聚类阶段

在K-means迭代聚类阶段，在MapReduce框架下可以分为两个步骤：第一步是利用Canopy中每个点各维度的值，重新计算每个Canopy中心；第二步合并邻近的新中心，并判断其属于哪个Canopy，将属于该Canopy的点的中心替换成为新的合并后的中心值，形成新的重叠Canopy。因此这一阶段也是通过两个Job完成，分别对应于Job3和Job4，两个Job的执行流程及Map和Reduce过程实现如图 4所示。

图  4  K-means迭代聚类阶段流程

Job3中的Map函数接收Job2产生的<数据ID：数据各维值，所属Canopy列表(Canopy中心各维值)>key-value对，计算与每个点距离最近的Canopy中心，将其加入该Canopy中，形成<簇，数据ID：数据各维值>；Map函数的输出在本地通过Combine函数，实现同一簇数据对象的合并，并统计数据的个数，得到<簇，数据点各维和+数据个数>，由于只能输出key-value对的形式，在实现中，将数据个数作为各维度和的最后一位加入到value中；Reduce函数接收个Combine函数的输出，进行汇总，得到各个簇的所有点各维度之和以及各簇的数据点总数，最终得到每个簇的新中心K，输出<簇，新K中心各维值>；这里Combine函数的设计，有效地完成了局部数据的统计，减少了节点间的通信代价。

Job3的MapReduce过程可表示为：

Map：$＜i:{{x}_{i}},\text{List}({{c}_{j}})>\to ＜{{c}_{j}},i:{{x}_{i}}＞$

Combine：$＜{{c}_{j}},i:{{x}_{i}}>\to ＜{{c}_{j}},\sum{{{x}_{i}}:{{n}_{j}}}＞$

Reduce：$＜{{c}_{j}},\sum{{{x}_{i}}:{{n}_{j}}}＞\to ＜{{c}_{j}},{{{c}´}_{j}}＞$

其中，n_j表示经过将每个数据点归类到其最近Canopy后，属于集合c_nj的数据对象个数，c´_j为K-means计算后得到的新中心的值。

Job4接收Job3的输出，首先在各个Map节点的初始化(Setup)阶段，检查是否有需要合并的K中心，如果有，将其进行合并，合并后产生得到的新中心，判断其属于那些Canopy中，得到合并后的K中心与原初始的Canopy的对应关系，判断其是否收敛。在Map阶段，将所有数据点的所属的Canopy列表中心替换为合并后的新中心，之后Reduce函数进行汇总，最终形成形如<数据ID：数据各维值，所属Canopy列表(合并后的Canopy新中心各维值)>。在Setup时进行的收敛判断中，若收敛，则在Map完成之后直接进入Job5以产生最后结果，若不收敛，则从Job3开始循环直至收敛。

Job4的MapReduce过程可表示为：

Map：

$＜{{c}_{j}},{{{c}´}_{j}}＞,{{T}_{2}},＜i:{{x}_{i}},\text{List}({{c}_{j}})＞\to ＜i:{{x}_{i}},\text{List}({{{c}''}_{j}})＞$

其中，${{{c}''}_{j}}$是合并后新中心的值，Reduce过程类似。

3) 聚类结果产生阶段

聚类结果产生阶段对应于Job5，接收Job4中产生的各个数据点与一个或多个稳定的K中心对应关系，在Map阶段将局部数据点归到与其距离最近的K中心，输出<数据ID：数据各维值，所属簇(最终K中心各维)>，完成聚类，该过程与Job3的map过程类似。

利用本文提出的改进Canopy-K-means算法进行文本聚类，采用文本向量空间模型VSM对文本进行预处理。即给定文本集$D=\{{{d}_{1}},{{d}_{2}},\cdots ,{{d}_{n}}\}$，d_i表示每个文本向量，且${{d}_{i}}=(＜{{t}_{1}},{{w}_{i1}}＞,＜{{t}_{2}},{{w}_{i2}}＞,\cdots ,$ $＜{{t}_{j}},{{w}_{ij}}＞)$。其中$T=\{{{t}_{1}},{{t}_{2}},\cdots ,{{t}_{j}}\}$表示从所有文本中提取的特征词集合，${{W}_{i}}=\{{{w}_{i1}},{{w}_{i2}},\cdots ,{{w}_{ij}}\}$表示文本d_i中包含各个特征词所对应的权重。向量权重的计算采用统计方法TF-IDF(term frequency-inverse document frequency)^[3]来计算：

式中，w_ij表示词语i在文档j中的权重值；f_ij为词语i在文档j中的出现次数；n_i表示整个文本集中出现过词语i的文本数；N为文档总数。由式(3)可以看出，词语i在该文本中出现的次数越多，其权值越大；而整个文本集中出现过词语i的文本越多，其权值则会相应减少，也就是说，字词的权重与它在文件中出现的次数成正比，与它在资料库中出现的频率成反比^[10]。具体实现中，在构建向量空间模型之前，采用中科院计算机研究所研制的汉语词法分析系统NLPIR^[19]，同时，利用哈工大中文停词表去除广泛使用词语和实际意义很小的词语，最后选择特征较大的词语形成VSM中的维度。

本文算法使用两个点之间的距离作为衡量两个点是否相似的标准。而在文本聚类中通常是使用两个文本向量间夹角的余弦值，即余弦相似度，来衡量两个文档的相似程度。而由于两个文本之间，向量夹角余弦值越大，相似度越大，说明其距离越小，也就是相似度和距离成反比，因此构造式(4)来定义两个文本d_i、d_j之间的距离。

式中，

式中，$\text{dist}({{d}_{i}},{{d}_{j}})$为两个文本的距离；$\text{sim}({{d}_{i}},{{d}_{j}})$为两个文本的余弦相似度。

实验采用UCI Machine Learning Repository^[20]机器学习数据集中的Iris和Wine数据集，其中，Iris数据集共有150个样本，每个样本4个属性，共分为3类；Wine数据集共178个样本，每个样本13个属性，分为3类。文本聚类方面，选用搜狗实验室文本分类语料库^[21]中选取财经、体育、旅游、教育4个类别的中文新闻文档各1 000篇。另外，为了对算法的扩展性进行验证，将Iris数据集构造成维度60维，行数为100万行(0.25 G)、300万行(0.6G)、500万行(1.1G)、900万行(2G)的更大规模数据集。

实验在由4台Ubuntu14.04平台下搭建的Hadoop集群下完成，由1台作为namenode，3台作为datanode，其配置均为2 GB内存，80G硬盘，Hadoop版本为1.2.1。

1) 算法准确度

利用Iris数据集、wine数据集对算法聚类准确性进行检验，实验一共进行20次，结果为这20次的平均值。在传统K-means过程中，由于每次选择的初始中心不同，聚类效果不稳定，迭代次数较多，而本文算法由于优化了中心的选择，因此结果十分稳定。由表 1可知，本文算法的正确率高于传统K-means算法，而误差平方和以及迭代次数比K-means算法更低，说明本文算法聚类结果的类内相似度更高且收敛速度更快。

在利用本文算法进行文本聚类时，采用前文中提到的通过文本间余弦相似度来计算距离的方法来衡量文本间的距离，在不同的单词提取率下比较本文算法与传统K-means算法在文本聚类上的准确率(precision)、召回率(recall)和F度量值^[22]，如表 2所示。

可以看到，本文算法可以很好地应用到文本聚类中。

2) 算法扩展性

为了分析算法在Hadoop框架下并行执行的性能，需要计算算法执行的加速比。对同一个计算任务，并行算法的加速比等于单机执行时间除以并行执行时间的值。加速比是用来衡量程序执行并行化的重要指标^{[13, 15]}。算法加速比曲线如图 4所示，由图 4可知，本文算法在并行化后有良好的加速比，并随着数据集的增大效果更佳明显。

图  4  Hadoop下并行加速比

本文以海量数据聚类为背景，改进了原有传统K-means算法，克服了其随机选择中心点带来的结果不稳定问题，提高了聚类结果的准确性和稳定性，减少了聚类次数；并利用MapReduce框架给出了算法的并行化设计。同时结合实际文本聚类应用场景，给出了本算法在文本聚类方面的应用。实验验证了本文算法具有良好的有效性和扩展性。