基于MapReduce的聚类算法相似性度量分析研究

摘 要：相似性度量在聚类算法设计中起关键作用，使用合适的距离度量函数能够反映数据对象间的相似性。本文对聚类算法中数据对象间相似性度量的特征进行了系统性归纳总结，通过MapReduce编程模型实现对各种相似性度量聚类算法的实验比较分析，将为聚类分析研究者提供参考。

关键词：聚类；相似性度量；MapReduce

中图分类号：TP311.13；TP391.1 文献标识码：A 文章编号：2096-4706（2018）11-0010-03

Research on Similarity Measurement Analysis of

Clustering Algorithm Based on MapReduce

PENG Tianhao，PAN Youshun，YANG Shenglin

（Moutai Institute，Department of Brewing Engineering Automation，Renhuai 564507，China）

Abstract：The similarity measure plays a key role in clustering algorithms. Using appropriate distance measure function can reflect the similarity between data objects. This paper aims to conduct a systematic summary on data objects similarity measure in clustering algorithms. The paper will also implement comparative analysis on various similarity measure clustering algorithms by MapReduce programming model，which can provide references to researchers on clustering algorithms.

Keywords：clustering；similarity measure；MapReduce

0 引 言

聚类分析的研究已有很长历史，是数据挖掘、模式识别等方面的重要研究内容之一，已经广泛应用于电子商务、图像识别、文本分类、Web搜索及生物信息等领域。聚类是一个把数据对象划分成子集的过程[1]，是一个无监督的分类[2]，在数据对象分类分组中发挥着重要作用，分类后同一个类中的数据对象尽可能相似，不同类中数据对象尽可能相异。典型的聚类分析过程包括如下三个步骤。

第一，特征选择和特征提取。特征选择是指从原始数据集中，选择质量好最有效的特征，以此作为进一步分析的数据对象。特征提取是指在特征选择基础上，通过对已经选择好的特征进行某种转换后产生的突出特征。该步骤非常重要，能够提升聚类算法的执行效率，特别是在对复杂数据和高维数据进行聚类时更能突显其重要性。

第二，聚类算法设计。选择合适的聚类算法进行聚类，聚类算法要给出具体的数据对象间距离度量函数及构建相应的目标函数，根据实际应用来选择确定距离度量函数，这 将直接影响聚类效果。

第三，聚类结果评估。因为不同的聚类算法将产生不同的聚类结果，即使是同一聚类算法，参数设置不同也会产生不同的聚类结果，因此如果要评估聚类结果，则主要通过三种方法：外部指标评估、内部指标评估、相关性指标评估。

聚类算法设计是聚类分析过程的核心步骤，使用合适的距离度量函数将反应数据对象间的相似性，相似性度量问题在聚类算法设计中起关键作用。本文将介绍一些常用的相似性度量方法，并从距离和相似系数两方面对其进行论述，其中距离用来度量样本之间的相似性，而相似系数用来度量变量之间的相似性，并通过数据测试进行对比，从而得出相关结论。

1 聚类算法中的相似性度量分析

1.1 明考斯基距离

设论域X={x1，x2，…，xn}为被分类的n个数据对象，每个数据对象又由p个指标组成，其中第i个数据对象表示为如下形式：

xi={xi1，xi2，…，xip} （i=1，2，…，n）

用d（xi，xj）来表示第i个数据对象xi与第j个数据对象xj之间的距离。明考斯基（Minkowski）距离表示如下：

1.1.1 欧氏距离

以上公式（1）中，当q=2时为欧氏距离，即：

欧式距离是一种几何距离，反应数据对象在空间的绝对距离，可用于检测特征空间中球形超球体结构数据对象的相似性度量分析。

1.1.2 曼哈顿距离

以上公式（1）中，当q=1时为曼哈顿距离，即：

用于检测特征空间中菱形超立方体结构数据对象的相似性度量分析。

1.1.3 切比雪夫距离

以上公式（1）中，当q=∞为切比雪夫距离，即：

可用于检测特征空间中矩形超立方体结构，主要表现为在多维空间中，数据对象从一个位置移动到另一个数据对象所要行走的最短距离。

从以上几个比较典型的距离公式可知，明考斯基距离的基本思想就是利用数据对对象各个指标值之间的绝对差异进行分类，操作简单明了，可以证明满足距离的4条基本公理，具体如下：

（1）非负性：d（xi，xj）≥0；

（2）d（xi，xj）=0，当且仅当xi=xj；

（3）对称性：d（xi，xj）=d（xj，xi）；

（4）三角不等式：d（xi，xj）≤d（xi，xk）+d（xk，xj）。

但是在明考斯基距离计算的过程中，将数据对象各分量的“单位”同等对待，没有区分处理，没有考虑各分量分布的差异性等。加权的明考斯基距离是根据每一个分量的重要性赋予一个权重，使聚类效果更好，但其没有体现分量间的相关性。

1.2 马氏距离

在样本集中，样本xi和样本xj之间的马氏距离定义为：

其中Σ为样本对应的协方差矩阵，计算过程相对比较复杂：

其中：。

马氏距离是一种有效地计算两个位置样本集的相似度方法，表示数据的协方差距离[3]，消除了量纲不同对对象聚类分析的影响，排除了变量之间的相关性的干扰，较好地避免发生一致性聚类问题，但是马氏距离最大的问题就是Σ不易确定，容易导致马氏距离效果不理想。

1.3 兰氏距离

如果样本数据的各指标取值均大于零，即xik≥0时，可以定义样本xi和样本xj之间的兰氏距离为：

兰氏距离对大的异常值不敏感，特别适合用高度倾斜的数据来评估距离度量，其与明考斯基距离有部分相同的特点，如奇异值影响小、没有考虑变量间相关性等。

1.4 夹角余弦

设两个p维向量样本点xi和xj，xi和xj之间的相似程度可以用夹角余弦来度量，具体如下：

很明显就可以看出夹角余弦的取值范围是[-1，1]，可以用图1比较直观地说明夹角大小与夹角余弦值之间的关系，空间中A点和B点的夹角越小相应的夹角余弦值就越大，反之越小。从图中还可以进一步比较欧氏距离与夹角余弦距离之间的区别，即欧氏距离的值是指A点和B点之间的绝对距离，其值大小与A点和B点所在空间位置坐标直接相关；而余弦距离指的是空间向量的夹角大小，体现在方向的差异上，而不是具体位置。

1.5 杰卡德系数

根据杰卡德（Jaccard）的相似度原理，文本数据对象A和B的Jaccard相似度等于其交集除以其并集，取值范围在[0，1]之间，当数据对象A和B相同时取值为1，数据对象A和B交集为空时取值为0，Jaccard相似度值越大，样本相似度越高，反之亦然。

1.6 相关系数

变量xi和xj的相关系数为：

其取值范围在[-1，1]之间，绝对值越大，说明变量之间的相关度就越好。变量xi和xj的距离通过以上相似系数来定义：

1.7 高斯相似度

样本xi和xj的高斯相似度计算公式如下：

高斯相似函数常用于谱聚类算法中，用来计算空间数据点之间的相似度，其值越小距离越大。

2 MapReduce编程模型

MapReduce是Google公司推出的能够并发处理大规模数据的并行编程模型，在具体编程中无须考虑底层的实现细节，这在一定程度上降低了编程难度，是当前云计算平台使用较多的并行数据处理模型。MapReduce编程模型的基本思想是，将大规模数据集分解成若干个数据块splits，由集群中的相应节点并行执行Map计算任务，得到相应的一系列中间结果（key，value），再将这些中间结果作为Reduce的输入，并行执行Reduce计算任务，形成最终结果，计算过程如图2所示。

3 实验分析

本文通过4台普通计算机搭建的Hadoop集群系统完成实验，其中1台计算机作为NameNode服务节点，另外3台作为DateNode服务节点。实验数据来源于UCI数据集，可以通过官网直接下载。本实验采用UCI数据库中的Wine数据集，其数据维度较高，共由178个样本组成，分为三类，每个样本包含13个特征属性。实验使用k-means算法，距离度量方式分别以欧式距离和马氏距离为代表，用Java编程实现。通过实验，在本算法中Wine数据集采用马氏距离的聚类精度明显优于欧氏距离。具体使用什么距离度量方式需要根据实际应用来确定，如数据集的大小、数据维度的大小、数据类型等，不能简单地定义哪一种度量方式更好。

4 结 论

当前，有关聚类分析的改进算法研究比较多，应用也比较广泛，并取得了较好的效果。本文重点介绍了聚类算法中数据对象间的相似性度量，有距离度量和相似系数度量两种方式，并介绍了一些常用的度量公式，从本身特点和应用等方面对其进行了简单的比较，较全面地分析了其优点、难点及不足等，通过实验介绍了聚类算法相似性度量的MapReduce并行化实现。本文意在为系统学习聚类分析中的相似性度量分析提供较好的参考价值。

参考文献：

[1] JiaWeiHan，MichelineKamber，Jian Pei.范明，孟晓峰，译.数据挖掘概念与技术 [M].北京：机械工业出版社，2012.

[2] 孙吉贵，刘杰，赵连宇.聚类算法研究 [J].软件学报，2008（1）：48-61.

[3] 蔡静颖.模糊聚类算法及应用 [M].北京：冶金工业出版社，2015.

[4] 何晓群.多元统计分析 [M].第4版.北京：中国人民大学出版社，2015.

[5] 邱宜宁.相似性度量对聚类性能的影响 [J].信息与电脑（理论版），2012（12）：116-119.

[6] 白雪.聚类分析中的相似性度量及其应用研究 [D].北京：北京交通大学，2012.

[7] 代明，钟才明，庞永明，等.基于数据集属性相似性的聚类算法推荐 [J].南京大学学报（自然科学），2016，52（5）：908-917.

[8] 李涛，汪光阳.标准相似性度量及其应用 [J].山西师范大学学报（自然科学版），2016，30（4）：29-33.

[9] 蔡静颖，谢福鼎，张永.基于马氏距离特征加权的模糊聚类新算法 [J].计算机工程与应用，2012，48（5）：198-200.

[10] 王丽娟，关守义，王晓龙，等.基于属性权重的Fuzzy CMean算法 [J].计算机学报，2006（10）：1797-1803.

[11] 江小平，李成华，向文，等.k-means聚类算法的Map Reduce并行化实现 [J].华中科技大学学报（自然科学版），2011，39（S1）：120-124.

[12] 覃雄派，王会举，杜小勇，等.大数据分析——RDBMS与MapReduce的竞争与共生 [J].软件学报，2012，23（1）：32-45.

作者简介：彭天昊（1982-），男，汉族，贵州桐梓人，副教授，硕士。主要研究方向：数据与知识工程；潘有顺（1977-），男，汉族，江苏淮安人，高级工程师，硕士。主要研究方向：网络技术、物联网；杨胜林（1985-），男，侗族，贵州石阡人，讲师，硕士。主要研究方向：机械结构设计与CAE。