基于Hadoop平臺的經(jīng)緯度信息的聚類算法研究與改進

郭佳祺

摘 要：Mahout中的k-means算法在使用距離測度時通常會使用歐氏距離，當(dāng)使用經(jīng)緯度計算地球兩點距離時會與真實情況存在誤差。本文基于Hadoop平臺，利用半正矢公式對Mahout中所集成的距離測度進行改進，實現(xiàn)球面距離的精確計算。研究結(jié)果可用于移動互聯(lián)網(wǎng)環(huán)境下定位信息的聚類分析。

【關(guān)鍵詞】Mahout Hadoop 半正矢公式 移動互聯(lián)網(wǎng)

聚類分析是數(shù)據(jù)挖掘中重要的研究課題之一。所謂聚類，就是將一組數(shù)據(jù)集合劃分成多個簇，每個簇中的元素或?qū)ο笥兄嗨频奶卣鳎嘏c簇之間的元素盡量保證特征差異的存在。而在大數(shù)據(jù)的時代背景下，傳統(tǒng)的聚類分析在性能上遇到瓶頸。為了解決這個問題，國內(nèi)外的專家學(xué)者將聚類分析與Hadoop平臺相結(jié)合，實現(xiàn)了高效的并行聚類算法。聚類算法在分析樣本的相似性中主要使用兩種方法：基于相似系數(shù)和基于距離測度。本文使用距離測度進行相似性劃分，首次引入半正矢公式計算兩點之間的球面距離，以精確的距離判斷聚簇中的相似性。

本文第一節(jié)介紹了Hadoop平臺的基本構(gòu)成，和k-means算法在Mahout中的工作原理；第二節(jié)引入了半正矢公式來計算球面距離，并對公式做了推導(dǎo)分析；第三節(jié)為實驗環(huán)節(jié)，對改進前后的算法進行比較。

1 Hadoop簡介

Hadoop是由Apache基金會所開發(fā)的分布式系統(tǒng)基礎(chǔ)架構(gòu)，是一個提供對大量數(shù)據(jù)進行分布式并行處理的開源平臺，有著高容錯性和高擴展性的優(yōu)勢。Hadoop主要由兩部分組成，分別是分布式文件系統(tǒng)（HDFS）和分布式計算框架（MapReduce）。HDFS采用主從架構(gòu)，是一個具有高度容錯性的分布式文件系統(tǒng)，適合部署在廉價的機器上，同時能夠提高吞吐量的數(shù)據(jù)訪問，非常適合大規(guī)模數(shù)據(jù)集上的應(yīng)用。MapReduce是一個基于集群的高性能并行計算平臺，同時也是一個并行計算與運行軟件框架。為了能夠?qū)adoop平臺運用到數(shù)據(jù)挖掘領(lǐng)域?qū)崿F(xiàn)簡單的聚類分析，Apache基金會為其提供了可并行計算的開源算法庫——Mahout。

2 Mahout中的k-means聚類算法原理介紹

Mahout是Apache基金會的開源項目之一，是一個基于Hadoop云平臺的數(shù)據(jù)挖掘分析的開源系統(tǒng)，項目本身實現(xiàn)了聚類算法。Mahout實現(xiàn)的k-means算法可以劃分為三個階段。第一階段掃描原始數(shù)據(jù)集合中所有的點，并隨機選取K個點作為初始的簇中心。第二階段Map方法讀取存在本地的數(shù)據(jù)集，計算每個對象到中心點的距離，選擇距離每個對象最近的中心點并輸出鍵值對，最后在Reduce階段用若干聚類集合生成新的全局聚類中心，重復(fù)第二階段過程直到滿足結(jié)束條件。第三階段根據(jù)最終生成的簇中心對所有的數(shù)據(jù)元素進行劃分聚類的工作。

Mahout0.9的版本中封裝了大量的距離測度公式，其中就包括了歐氏距離。但是本文中所使用的實驗數(shù)據(jù)由經(jīng)緯度構(gòu)成，考慮到地球球面的特殊性，直接使用歐氏距離計算兩點之間距離所得到的結(jié)果與實際距離相差很大。為了解決這個問題，文章引入了半正矢公式去計算地球表面兩點之間的距離，將該公式作為一個距離測度封裝到Mahout中。

3 半正矢公式計算球面距離

球面距離的實現(xiàn)需要了解球面半正矢公式（Haversine formula）。球面半正矢公式是目前重要的導(dǎo)航方程，主要是通過球面上兩點經(jīng)緯度給出大圓距離。球面半正矢公式采用了正弦公式，即使距離很小也能夠保持可用的有效數(shù)字。半正矢公式為：

。公式的推導(dǎo)過程如圖1。

如圖1所示地球球面，假設(shè)半徑R為1，O是地球球心，在地球球面上選取A、B兩點，兩點的經(jīng)緯度分別設(shè)為（a1， a2）和（b1， b2），AB兩點的經(jīng)度線相交北極點N，同時在這兩條經(jīng)度線上選取C、D兩點，經(jīng)緯度分別是（b1， a2）和（a1， b2）。圖中赤道上兩點E和F緯度為0，AD和BC分別是兩點之間的直線。點A與點C的緯度差∠AOC和點B與點D的緯度差都是dlat?！螮OF是點E與點F的經(jīng)度差dlon。將ABCD四點投射在二維平面上形成一個等腰梯形，如圖2所示。

AC和BD可看作圓內(nèi)的兩條弦，則

求角度∠AOB，假設(shè)AC=，得到：OC；假設(shè)c是∠AOB的度數(shù)，sin∠AOC=，則：c=2*。

最后一步求得AB的球面距離，設(shè)地球半徑為R，將上述公式帶入得到AB的真實距離：d = 2 * R * c。

半正矢公式可以將抽象的經(jīng)緯度坐標(biāo)點轉(zhuǎn)換成實際距離，為了比較直接使用歐氏距離，將兩者分別在單機的eclipse中執(zhí)行，所用到的測試數(shù)據(jù)為（39.946071， 116.327932）和（31.240634， 121.425752）兩點。在兩種計算公式中結(jié)果分別是：半正矢公式的4169.4474和歐氏距離的10.0882?？芍捎冒胝腹娇梢缘玫絻牲c的真實距離，而歐氏距離所得到的結(jié)果僅僅是兩個點在坐標(biāo)系上的距離。

4 實驗環(huán)境與結(jié)果分析

本文實驗均是運行在Hadoop集群中。系統(tǒng)使用centos 6.5，java版本是1.7，Hadoop版本是2.5.2，Mahout版本是0.9，各節(jié)點之間通過交換機相互連接，保證數(shù)據(jù)網(wǎng)絡(luò)通暢。所使用的數(shù)據(jù)集主要包括經(jīng)緯度信息，為了檢測性能上的區(qū)別分別使用了3萬和300萬條數(shù)據(jù)。

實驗的第一階段，對Mahout中本身k-means算法不做改進進行實驗，其中Datanode節(jié)點信息如圖3所示，以前兩個從節(jié)點為例，所使用block分別是26和7。

實驗的第二階段，對k-means算法進行重寫并編譯，加入半正矢公式作為距離計算的公式，設(shè)置k值為3。該階段從節(jié)點屬性信息如圖4所示，從圖中可知，從節(jié)點中使用的block數(shù)有小幅的下降，下降的主要原因在于k值的設(shè)置上。

實驗結(jié)果雖然沒能明顯降低空間復(fù)雜度，但是證明了對算法研究和改進的可行性，而且在時間復(fù)雜度上，半正矢公式與歐氏距離在數(shù)據(jù)計算的過程中基本相同。

5 結(jié)束語

本文提出在聚類分析中引入球面距離的思想實現(xiàn)兩點間的距離計算，并以此對Mahout中k-means算法的距離測度進行擴展優(yōu)化。同時，最大程度的利用Mahout開源特性，對其中源碼進行重寫和編譯。最后通過實驗表明，改進后的算法能夠在Hadoop平臺上運行，可以有效應(yīng)對經(jīng)緯度數(shù)據(jù)的分析和挖掘，而且實驗過程中所占用的空間資源得到了明顯的改善。文章將半正矢公式引入到聚類算法中，找到了一種解決聚類球面數(shù)據(jù)的新方法，為實現(xiàn)移動終端的推薦服務(wù)打下堅實基礎(chǔ)。

參考文獻

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

[2]趙衛(wèi)中，馬惠芳等.基于云計算平臺Hadoop的并行k-means聚類算法設(shè)計研究[J].計算機科學(xué)，2011.

[3]李建江，崔健，王聃，嚴(yán)林，黃義雙. MapReduce并行編程模型研究綜述[J].電子學(xué)報，2011，11：2635-2642.

[4]牛怡涵，海沫.Hadoop平臺下Mahout聚類算法的比較研究[J].計算機科學(xué)，2015.

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

作者單位

中國海洋大學(xué)信息科學(xué)與工程學(xué)院 山東省青島市 266100