基于Hadoop平台的经纬度信息的聚类算法研究与改进

郭佳祺

摘 要：Mahout中的k-means算法在使用距离测度时通常会使用欧氏距离，当使用经纬度计算地球两点距离时会与真实情况存在误差。本文基于Hadoop平台，利用半正矢公式对Mahout中所集成的距离测度进行改进，实现球面距离的精确计算。研究结果可用于移动互联网环境下定位信息的聚类分析。

【关键词】Mahout Hadoop 半正矢公式 移动互联网

聚类分析是数据挖掘中重要的研究课题之一。所谓聚类，就是将一组数据集合划分成多个簇，每个簇中的元素或对象有着相似的特征，簇与簇之间的元素尽量保证特征差异的存在。而在大数据的时代背景下，传统的聚类分析在性能上遇到瓶颈。为了解决这个问题，国内外的专家学者将聚类分析与Hadoop平台相结合，实现了高效的并行聚类算法。聚类算法在分析样本的相似性中主要使用两种方法：基于相似系数和基于距离测度。本文使用距离测度进行相似性划分，首次引入半正矢公式计算两点之间的球面距离，以精确的距离判断聚簇中的相似性。

本文第一节介绍了Hadoop平台的基本构成，和k-means算法在Mahout中的工作原理；第二节引入了半正矢公式来计算球面距离，并对公式做了推导分析；第三节为实验环节，对改进前后的算法进行比较。

1 Hadoop简介

Hadoop是由Apache基金会所开发的分布式系统基础架构，是一个提供对大量数据进行分布式并行处理的开源平台，有着高容错性和高扩展性的优势。Hadoop主要由两部分组成，分别是分布式文件系统（HDFS）和分布式计算框架（MapReduce）。HDFS采用主从架构，是一个具有高度容错性的分布式文件系统，适合部署在廉价的机器上，同时能够提高吞吐量的数据访问，非常适合大规模数据集上的应用。MapReduce是一个基于集群的高性能并行计算平台，同时也是一个并行计算与运行软件框架。为了能够将Hadoop平台运用到数据挖掘领域实现简单的聚类分析，Apache基金会为其提供了可并行计算的开源算法库——Mahout。

2 Mahout中的k-means聚类算法原理介绍

Mahout是Apache基金会的开源项目之一，是一个基于Hadoop云平台的数据挖掘分析的开源系统，项目本身实现了聚类算法。Mahout实现的k-means算法可以划分为三个阶段。第一阶段扫描原始数据集合中所有的点，并随机选取K个点作为初始的簇中心。第二阶段Map方法读取存在本地的数据集，计算每个对象到中心点的距离，选择距离每个对象最近的中心点并输出键值对，最后在Reduce阶段用若干聚类集合生成新的全局聚类中心，重复第二阶段过程直到满足结束条件。第三阶段根据最终生成的簇中心对所有的数据元素进行划分聚类的工作。

Mahout0.9的版本中封装了大量的距离测度公式，其中就包括了欧氏距离。但是本文中所使用的实验数据由经纬度构成，考虑到地球球面的特殊性，直接使用欧氏距离计算两点之间距离所得到的结果与实际距离相差很大。为了解决这个问题，文章引入了半正矢公式去计算地球表面两点之间的距离，将该公式作为一个距离测度封装到Mahout中。

3 半正矢公式计算球面距离

球面距离的实现需要了解球面半正矢公式（Haversine formula）。球面半正矢公式是目前重要的导航方程，主要是通过球面上两点经纬度给出大圆距离。球面半正矢公式采用了正弦公式，即使距离很小也能够保持可用的有效数字。半正矢公式为：

。公式的推导过程如图1。

如图1所示地球球面，假设半径R为1，O是地球球心，在地球球面上选取A、B两点，两点的经纬度分别设为（a1， a2）和（b1， b2），AB两点的经度线相交北极点N，同时在这两条经度线上选取C、D两点，经纬度分别是（b1， a2）和（a1， b2）。图中赤道上两点E和F纬度为0，AD和BC分别是两点之间的直线。点A与点C的纬度差∠AOC和点B与点D的纬度差都是dlat。∠EOF是点E与点F的经度差dlon。将ABCD四点投射在二维平面上形成一个等腰梯形，如图2所示。

AC和BD可看作圆内的两条弦，则

求角度∠AOB，假设AC=，得到：OC；假设c是∠AOB的度数，sin∠AOC=，则：c=2*。

最后一步求得AB的球面距离，设地球半径为R，将上述公式带入得到AB的真实距离：d = 2 * R * c。

半正矢公式可以将抽象的经纬度坐标点转换成实际距离，为了比较直接使用欧氏距离，将两者分别在单机的eclipse中执行，所用到的测试数据为（39.946071， 116.327932）和（31.240634， 121.425752）两点。在两种计算公式中结果分别是：半正矢公式的4169.4474和欧氏距离的10.0882。可知采用半正矢公式可以得到两点的真实距离，而欧氏距离所得到的结果仅仅是两个点在坐标系上的距离。

4 实验环境与结果分析

本文实验均是运行在Hadoop集群中。系统使用centos 6.5，java版本是1.7，Hadoop版本是2.5.2，Mahout版本是0.9，各节点之间通过交换机相互连接，保证数据网络通畅。所使用的数据集主要包括经纬度信息，为了检测性能上的区别分别使用了3万和300万条数据。

实验的第一阶段，对Mahout中本身k-means算法不做改进进行实验，其中Datanode节点信息如图3所示，以前两个从节点为例，所使用block分别是26和7。

实验的第二阶段，对k-means算法进行重写并编译，加入半正矢公式作为距离计算的公式，设置k值为3。该阶段从节点属性信息如图4所示，从图中可知，从节点中使用的block数有小幅的下降，下降的主要原因在于k值的设置上。

实验结果虽然没能明显降低空间复杂度，但是证明了对算法研究和改进的可行性，而且在时间复杂度上，半正矢公式与欧氏距离在数据计算的过程中基本相同。

5 结束语

本文提出在聚类分析中引入球面距离的思想实现两点间的距离计算，并以此对Mahout中k-means算法的距离测度进行扩展优化。同时，最大程度的利用Mahout开源特性，对其中源码进行重写和编译。最后通过实验表明，改进后的算法能够在Hadoop平台上运行，可以有效应对经纬度数据的分析和挖掘，而且实验过程中所占用的空间资源得到了明显的改善。文章将半正矢公式引入到聚类算法中，找到了一种解决聚类球面数据的新方法，为实现移动终端的推荐服务打下坚实基础。

参考文献

[1]Han J W，Kamber M.Data mining：concepts and techniques[M].San Francisco，US：Morgan Kaufmann，2001.

[2]赵卫中，马惠芳等.基于云计算平台Hadoop的并行k-means聚类算法设计研究[J].计算机科学，2011.

[3]李建江，崔健，王聃，严林，黄义双. MapReduce并行编程模型研究综述[J].电子学报，2011，11：2635-2642.

[4]牛怡涵，海沫.Hadoop平台下Mahout聚类算法的比较研究[J].计算机科学，2015.

[5]R.W.Sinnott.Virtues of the Haversine.Sky and Telescope 68（2），1984.

作者单位

中国海洋大学信息科学与工程学院 山东省青岛市 266100