基于百度地圖的改進(jìn)的K—means算法研究

楊婷婷++王雪梅

摘要：聚類分析在科研和商業(yè)應(yīng)用中都有著非常重要的應(yīng)用，K-means算法是聚類方法中常用的一種劃分方法。隨著數(shù)據(jù)量的增加，K-means算法的局限性日益突出。在百度地圖的各種坐標(biāo)體系下，提出一種改進(jìn)的基于網(wǎng)格的K-means算法，用新的方法確定k值以及K個初始質(zhì)心。相對于傳統(tǒng)的K-means算法，該算法在一定程度上減少了因采用誤差平方和準(zhǔn)則函數(shù)而出現(xiàn)較大的聚類簇分割開的情況，仿真實驗結(jié)果表明：改進(jìn)后的K-means算法優(yōu)于原始算法，并且穩(wěn)定性更好。

關(guān)鍵詞：聚類；K-means算法；百度地圖；穩(wěn)定性

中圖分類號：TP3-0

文獻(xiàn)標(biāo)識碼：A

DOI： 10.3969/j.issn.1003-6970.2016.01.018

0 引言

數(shù)據(jù)挖掘即是從大量的、不完全的、有噪音的、模糊的、隨機(jī)的實際應(yīng)用數(shù)據(jù)中，發(fā)現(xiàn)并提取隱含在其中未知的、可信的、有用的模式的過程。目前，數(shù)據(jù)挖掘已廣泛應(yīng)用于大中型企業(yè)、商業(yè)、銀行、保險等領(lǐng)域，成為未來3-5年內(nèi)對工業(yè)有重大影響的關(guān)鍵技術(shù)之一。聚類是數(shù)據(jù)挖掘中的一類重要技術(shù)，是分析數(shù)據(jù)并從中發(fā)現(xiàn)有用信息的一種有效手段。由聚類所生成的簇是一組數(shù)據(jù)對象的集合，這些對象與同一簇中的對象彼此相似，與其他簇的對象相異。聚類算法有劃分聚類算法、層次聚類算法、基于密度的聚類算法、基于網(wǎng)格的聚類算法、模糊聚類算法、子空間聚類算法。其中，K-me ans算法屬于聚類方法中一種基本的劃分方法，傳統(tǒng)的K-means算法是輸入聚類個數(shù)k，以及包含n個數(shù)據(jù)對象的數(shù)據(jù)庫，輸出滿足方差最小標(biāo)準(zhǔn)的k個聚類。

如今，020如火如荼，移動地圖一直被當(dāng)作是020的重要入口之一，移動地圖本身就是最該挖掘的寶藏，在如今的技術(shù)條件下，地圖服務(wù)完全可以擴(kuò)展成索引真實世界的關(guān)鍵按鈕，成為連接所有020服務(wù)的平臺。而地圖中定位和導(dǎo)航的最終目的大多都會指向某種生活服務(wù)，那就是POI，它是“Pointlnterest”的縮寫，每個POI包含名稱、類別、經(jīng)緯度等信息，我們在地圖上看到xx商店、xx飯店的提示，就是POI數(shù)據(jù)。而市場份額占7成的百度，擁有最集中的用戶場景需求，而且百度地圖上的POI數(shù)據(jù)現(xiàn)在已經(jīng)是行業(yè)內(nèi)最多的，高德次之。隨著地圖上POI點數(shù)量的不斷擴(kuò)大，于是，在地圖上展示過多的POI點信息會顯得雜亂無章甚至出現(xiàn)覆蓋現(xiàn)象，使得地圖的可用性下降，不能很好的服務(wù)于群眾。因此，基于百度地圖的POI聚合也有更深遠(yuǎn)的研究意義。

本課題在020的發(fā)展背景下，在之前的各種聚類算法研究基礎(chǔ)上，提出了基于百度地圖的改進(jìn)的K-means算法，利用地圖特有的坐標(biāo)體系，結(jié)合傳統(tǒng)的K-means算法，提出一種改進(jìn)的基于網(wǎng)格的K-means算法。該算法在POI聚合以及其他的聚合應(yīng)用上有深遠(yuǎn)的研究意義。

l 現(xiàn)有K-means算法思想

1.1 K-means算法的基本思想概述

K-means算法是硬聚類算法，是典型的基于原型的目標(biāo)函數(shù)聚類方法的代表，它是數(shù)據(jù)點到原型的某種距離作為優(yōu)化的目標(biāo)函數(shù)，利用函數(shù)求極值得方法得到迭代運算的調(diào)整規(guī)則。K-means算法以歐式距離作為相似度測度，它是求對應(yīng)某一初始聚類中心向量V最優(yōu)分類，使得評價指標(biāo)J最小。算法采用誤差平方和準(zhǔn)則函數(shù)作為聚類準(zhǔn)則函數(shù)。

1.1.1 K-means算法工作原理

K-means算法以K為參數(shù)，把n個對象分為K個簇，以使簇內(nèi)具有較高的相似度，而簇間的相似度較低。首先隨機(jī)選擇K個對象，每個對象初始地代表了一個簇的平均值或中心。對剩余的每個對象根據(jù)其與各個簇中心的距離，將它賦給最近的簇。然后重新計算每個簇的平均值。不斷重復(fù)該過程，直到準(zhǔn)則函數(shù)收斂。

1.1.2 K-means算法具體步驟

問題提出：給定一個元素集合D，其中每個元素具有n個可觀察屬性，將D劃分為k個子集，要求每個子集內(nèi)部的元素之間相異度盡可能低，而不同子集的元素相異度盡可能高。

算法步驟如下：

1.從D中隨機(jī)取k個元素，作為k個簇的各自的中心

2.分別計算剩下的元素到k個簇中心的相異度，將這些元素分別劃歸到相異度最低的簇

3.依據(jù)聚類結(jié)果，重新計算k個簇各自的中心，計算方法是取簇中所有元素各自維度的算數(shù)平均值。

4.將D中全部元素按照新的中心重新聚類。

5.重復(fù)第4步，直到聚類結(jié)果不再變化。

6.將結(jié)果輸出。

1.1.3 K-means算法存在的問題

原始的K-means算法選取K個點作為初始聚類中心，然后進(jìn)行迭代操作，其中存在以下的幾個問題。

1.K值的確定。

K-means算法首先選擇K個初始質(zhì)心，其中K是用戶指定的參數(shù)，即所期望的簇的個數(shù)，這么做的前提是已知數(shù)據(jù)集中包含簇的個數(shù)，但是在很多情況下，我們并不知道數(shù)據(jù)的分布情況，實際上聚類就是我們發(fā)現(xiàn)數(shù)據(jù)分布的一種手段，所以，K值的確定對K-means聚合結(jié)果至關(guān)重要。

2.初始質(zhì)心的選取

選擇適當(dāng)?shù)某跏假|(zhì)心是基本K-means算法的關(guān)鍵。常用的方法是隨機(jī)選取初始質(zhì)心，但是，這樣簇的質(zhì)量常常很差。

3.距離的度量

常用的距離度量方法包括：歐幾里得距離和余弦相似度。兩者都是評定個體間差異的大小的。歐幾里得距離度量會受指標(biāo)不同單位刻度的影響，所以一般需要先進(jìn)性標(biāo)準(zhǔn)化，同時距離越大，個體間差異越大；空間向量余弦夾角的相似度度量不會受指標(biāo)刻度的影響，余弦值落于[-l，1]，值越大，差異越小。

1.1.4 現(xiàn)有的改進(jìn)的K-means算法

針對以上問題，現(xiàn)在有很多改進(jìn)的K-means算法，例如基于聚類數(shù)和初始值的K-means算法改進(jìn)研究，提出了一種基于密度選取初始質(zhì)心和采取遺傳算法優(yōu)化聚類數(shù)k的算法。該算法在一定程度上解決了初始質(zhì)心和聚類數(shù)k對聚類精度和效率的影響，提高了聚類的準(zhǔn)確率。

2 改進(jìn)的K-means算法

2.1 改進(jìn)算法概述

地圖定位或?qū)Ш蕉紩赶蚰撤N生活服務(wù)，這些服務(wù)通過POI數(shù)據(jù)來展現(xiàn)。POI包含名稱、類別、經(jīng)緯度等信息。例如，現(xiàn)在百度上能夠找到3800萬個POI數(shù)據(jù)，這些數(shù)據(jù)中，有2000萬個與生活服務(wù)深度關(guān)聯(lián)，當(dāng)然，不止百度，高德等都從未停止對POI的采集與應(yīng)用。百度地圖上的POI數(shù)據(jù)越來越多，如果直接全部展示到地圖上，便會出現(xiàn)POI點圖標(biāo)過密，尤其當(dāng)?shù)貓D縮放到一定級別時，甚至出現(xiàn)信息覆蓋等現(xiàn)象，如下圖2所示，這樣使得地圖可用性大大降低，為更友好地展示POI信息點，需要對這些POI進(jìn)行聚合。

本文在百度地圖的基礎(chǔ)上對k-means算法進(jìn)行改進(jìn)，利用現(xiàn)有的百度地圖的坐標(biāo)體系，可以實現(xiàn)確定k的初始值和k個初始簇質(zhì)心的計算。

2.2 百度地圖API簡介以及坐標(biāo)體系概述

百度地圖API是一套有Javascript編寫的將百度地圖嵌入到網(wǎng)頁應(yīng)用程序接口，它能夠幫助您在網(wǎng)站中構(gòu)建功能豐富、交互性強的地圖應(yīng)用程序。百度地圖API為開發(fā)者提供豐富的函數(shù)、空間、事件和封裝的類，提供很多的專題服務(wù)，如本地搜索、路線規(guī)劃、地址解析等接口工用戶使用。開發(fā)者只需要按照百度的要求進(jìn)行注冊使用，通過API，利用Javascript腳本語言就可以將百度地圖服務(wù)連接到自己的網(wǎng)頁中陸1。

在百度API中，有如下坐標(biāo)系：

1.經(jīng)緯度

通過經(jīng)度（longitude）和緯度（latitude）描述地球上的某一個位置

2.平面坐標(biāo)

投影之后的坐標(biāo)（用x和y描述），用于在平面上標(biāo)識某個位置，百度地圖API默認(rèn)使用墨卡托投影（Mercator Projection），平面坐標(biāo)是以最大級別18級為基準(zhǔn)的。即在18級下，平面坐標(biāo)的一個單位就代表了屏幕上的一個像素。平面坐標(biāo)與地圖所展示的級別沒有關(guān)系，也就是說在1級和18級下，天安門位置的平面坐標(biāo)都是一致的。某個位置的平面坐標(biāo)可以通過BMap.MercatorProj ection類來完成，該類提供經(jīng)緯度與平面坐標(biāo)互相轉(zhuǎn)換的方法。例如天安門的經(jīng)緯度大約是116.404，39.915，經(jīng)過轉(zhuǎn)換即可得到平面坐標(biāo)：

var projection=new BMap.MercatorProjection（）；

var point=projection.lngLatToPoint （newBMap.Point （116.404， 39.915》；

得到結(jié)果就是12958175，4825923.77就是平面坐標(biāo)?？梢岳斫鉃?8級下，天安門距離坐標(biāo)原點的位置差為12958175，4825923.77，單位為像素。

3.像素坐標(biāo)

描述不同級別下地圖上某點的位置，在第18級別下，我們直接將平面坐標(biāo)向下取整就得到了像素坐標(biāo)，而在其他級別下可以通過如下公式進(jìn)行換算：

像素坐標(biāo)=|平面坐標(biāo)x2 zoom-18|

比如經(jīng)過計算，在第4級天安門位置的像素坐標(biāo)是：790，294.

4.圖快坐標(biāo)：

地圖圖塊編號，百度地圖API在展示地圖時是將征地地圖切割成若干圖塊顯示的，當(dāng)?shù)貓D初始化或是地圖級別、中心點位置發(fā)生變化時，地圖API會根據(jù)當(dāng)前像素坐標(biāo)計算出視野內(nèi)需要的圖塊坐標(biāo)（也叫圖塊編號），從而加載對應(yīng)的圖塊用以顯示地圖。百度地圖的圖塊坐標(biāo)原點與平面坐標(biāo)一致，從原點向右上方開始編號為0，0。

某個位置的圖塊坐標(biāo)可以通過如下公式計算：

圖塊坐標(biāo)=l像素坐標(biāo)÷2561

256實際上是每個圖塊的寬度和高度，我們用像素坐標(biāo)除以這個數(shù)就知道圖塊坐標(biāo)了。還以天安門為例，在第4級下天安門所在的圖塊編號為：3，1，而在第18級下，圖塊編號為：50617，18851

5.可視區(qū)域坐標(biāo)

地圖可視區(qū)域的坐標(biāo)系（用x和y描述），地圖都是顯示在確定大小的矩形框中的，這個矩形框通常是開發(fā)者在初始化地圖傳入的某個容器元素。這個矩形框也有自己的坐標(biāo)系，在百度地圖API中稱之為可視區(qū)域坐標(biāo)系，它的原點位于矩形的左上角。通過Map類的pointToPixel和pixeIToPoint方法可以相互轉(zhuǎn)換經(jīng)緯度坐標(biāo)與可視區(qū)域坐標(biāo)。

6.覆蓋物坐標(biāo)

覆蓋物相對于容器的坐標(biāo)（用x和y描述），覆蓋物在實現(xiàn)上就是若干DOM元素，這些元素會被放在若干覆蓋物容器內(nèi)（具體請參考地圖API開發(fā)指南），那么覆蓋物的坐標(biāo)實際上就是相對于這些覆蓋物容器的坐標(biāo)。

2.3 基于網(wǎng)格的改進(jìn)的K-means算法

原始的K-means算法選取K個點作為初始聚類中心點，然后進(jìn)行迭代操作，初始點選取不同可能獲得不同的聚類結(jié)果。本文主要提出用改進(jìn)的Kmeans算法來解決百度地圖上POI聚合的問題。改進(jìn)主要是利用百度地圖的坐標(biāo)體系，以及針對傳統(tǒng)的K-means算法中存在的問題，提出初始K值的選擇以及K個初始質(zhì)心的選擇方法。

2.3.1 改進(jìn)的K-means算法思想

針對上文提到的傳統(tǒng)K-means算法存在的問題，K-means的初始K值的確定以及K個初始質(zhì)心的選擇會明顯的影響聚合結(jié)果。本文提出一種新的基于網(wǎng)格的K-means算法，其創(chuàng)新之處在于網(wǎng)格的確定、k值的選擇、k個初始質(zhì)心的選擇。

1.基于網(wǎng)格以及K值的選擇

百度地圖可以看作是將整個地圖圖片切割成若干個圖塊顯示的，每一個圖塊就可以看作一個網(wǎng)格。在百度地圖每個縮放級別下，每個POI都有其唯一對應(yīng)的圖塊坐標(biāo)?；诰W(wǎng)格的思想是指每個POI有對應(yīng)的網(wǎng)格，網(wǎng)格的個數(shù)就是K值。在此，每個POI的圖塊坐標(biāo)計算過程如下：

（a）可以依據(jù)百度地圖提供的API計算出其平面坐標(biāo)：

var projection= new BMap.MercatorProjection（）；

var point = projection.lngLatToPoint （newBMap.Point （116.404. 39.915》；

（b）依據(jù)平面坐標(biāo)可以根據(jù)公式計算出其像素坐標(biāo)：

像素坐標(biāo)=|平面坐標(biāo)x2zoom-18|

（c）依據(jù)像素坐標(biāo)，即可得到POI對應(yīng)的圖塊坐標(biāo)：

圖塊坐標(biāo)=|像素坐標(biāo)÷256|

2.K個初始質(zhì)心的選擇

在百度地圖某個縮放級別下，所有POI的個數(shù)是n，即原始數(shù)據(jù)集合（xl，x2，…，xn），此處的每個XI為二維向量，所有POI所在的圖塊為k個，即將原始數(shù)據(jù)分成k類S={S1，S2，…，Sk}。在此，每個初始質(zhì)心指對應(yīng)圖塊中所有的POI點的各維度的算數(shù)平均數(shù)，則初始質(zhì)心坐標(biāo)為：

其中m為每個質(zhì)心的POI個數(shù)。

2.3.2 改進(jìn)的K-means算法描述

百度地圖為用戶提供地圖位置搜索、展示、POI檢索等多種服務(wù)，而上文提到的豐富的坐標(biāo)體系是這些服務(wù)的基礎(chǔ)。在本文中，把百度地圖豐富的坐標(biāo)體系元素融入到現(xiàn)有的基于網(wǎng)格的K-means算法中。充分利用百度地圖的圖塊坐標(biāo)和像素坐標(biāo)等，巧妙地實現(xiàn)網(wǎng)格的劃分，以及K-means中k值的選擇與質(zhì)心的確定。這樣，即使POI點的數(shù)量增加，也不會出現(xiàn)覆蓋現(xiàn)象。

百度地圖POI聚合中，基于網(wǎng)格的改進(jìn)的K-means算法描述如下：

輸入：百度地圖上的POI，即n個坐標(biāo)點。

輸出：在百度地圖的不同縮放級別下，實現(xiàn)n個POI點的聚合為k個聚類中心。

Begin

取樣，獲取n個坐標(biāo)點（即POI點的坐標(biāo)），在百度地圖的某一個縮放級別下，計算出n個坐標(biāo)點的圖塊坐標(biāo)，分別為（X1，Yl）、（X2，Y2）….（Xn，Yn），得到k個不同的圖塊坐標(biāo)即分為k個聚類{SI，S2，…，Sk}；

計算出每個簇中POI點的個數(shù)為m；設(shè)k個質(zhì)心的像素坐標(biāo)為（XI，Y1）、（X2，Y2）…（Xk，Yk）

Forl=1 to k do

為每個聚類中的POI點的個數(shù)

//計算出k個聚類的初始質(zhì)心；

Repeat

分別計算剩下的元素到k個簇中心的相異度，將這些元素分別劃歸到相異度最低的簇。在此處是利用像素坐標(biāo)間的距離計算出各個POI點的坐標(biāo)到k個質(zhì)心間的距離，將POI點歸到距離它最近的那個質(zhì)心。即：

//minDic初始化為Double.MAX_VALUE，每個POI點像素坐標(biāo)坐標(biāo)為（xh，yh），每個質(zhì)心像素坐標(biāo)

//計算每個POI點到質(zhì)心的距離找到離得最近的質(zhì)心點

If

dic

minDic=dic

End

End

根據(jù)聚類結(jié)果，重新計算k個簇各自的中心，計算方法是取簇中所有元素各自維度的算術(shù)平均數(shù)。

Until設(shè)定迭代終止條件mu（如IE-IO），當(dāng)各個新質(zhì)心相對于老質(zhì)心偏移量小于mu時，終止迭代。

End

如下圖3中，百度地圖有POI若干，在地圖縮放級別為15時，它們的像素坐標(biāo)如表一中第三列所示，按照文本提出的算法進(jìn)行聚合，首先這寫POI點分屬于四個圖快坐標(biāo)，分別為（6325.0，2359.0）、（6325.0， 2360.0）、（6326.0， 2361.0）和（6331.0，2363.0），所以k值初始化為4，即將這些POI點聚合于四簇，利用算法進(jìn)行聚合之后的四個簇的中心點，如表1所示。

按照本文改進(jìn)的算法計算出的聚合結(jié)果為下表1所示，其中POI點的坐標(biāo)是百度坐標(biāo)體系中的像素坐標(biāo)。

3 結(jié)論

本文給出了基于網(wǎng)格的改進(jìn)的K-means算法。該算法提出背景在于提出適用于應(yīng)用在地圖上的聚合算法。利用百度地圖的坐標(biāo)體系，實現(xiàn)不同縮放級別下POI的聚合，是本文的直接目標(biāo)。改進(jìn)的算法吸取了傳統(tǒng)Kmeans算法的優(yōu)點，充分利用并結(jié)合地圖的特點，巧妙地實現(xiàn)了地圖上的POI的聚合。