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

郭佳祺

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

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

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

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

1 Hadoop簡(jiǎn)介

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

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

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

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

3 半正矢公式計(jì)算球面距離

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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

參考文獻(xiàn)

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

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

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

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

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

作者單位

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