楊婷婷++王雪梅

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

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

中圖分類號：TP3-0

文獻標識碼：A

DOI： 10.3969/j.issn.1003-6970.2016.01.018

0 引言

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

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

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

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

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

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

1.1.1 K-means算法工作原理

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

1.1.2 K-means算法具體步驟

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

算法步驟如下：

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

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

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

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

5.重復第4步，直到聚類結果不再變化。

6.將結果輸出。

1.1.3 K-means算法存在的問題

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

1.K值的確定。

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

2.初始質心的選取

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

3.距離的度量

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

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

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

2 改進的K-means算法

2.1 改進算法概述

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

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

2.2 百度地圖API簡介以及坐標體系概述

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

在百度API中，有如下坐標系：

1.經緯度

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

2.平面坐標

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

var projection=new BMap.MercatorProjection（）；

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

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

3.像素坐標

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

像素坐標=|平面坐標x2 zoom-18|

比如經過計算，在第4級天安門位置的像素坐標是：790，294.

4.圖快坐標：

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

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

圖塊坐標=l像素坐標÷2561

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

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

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

6.覆蓋物坐標

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

2.3 基于網格的改進的K-means算法

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

2.3.1 改進的K-means算法思想

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

1.基于網格以及K值的選擇

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

（a）可以依據百度地圖提供的API計算出其平面坐標：

var projection= new BMap.MercatorProjection（）；

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

（b）依據平面坐標可以根據公式計算出其像素坐標：

像素坐標=|平面坐標x2zoom-18|

（c）依據像素坐標，即可得到POI對應的圖塊坐標：

圖塊坐標=|像素坐標÷256|

2.K個初始質心的選擇

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

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

2.3.2 改進的K-means算法描述

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

百度地圖POI聚合中，基于網格的改進的K-means算法描述如下：

輸入：百度地圖上的POI，即n個坐標點。

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

Begin

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

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

Forl=1 to k do

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

//計算出k個聚類的初始質心；

Repeat

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

//minDic初始化為Double.MAX_VALUE，每個POI點像素坐標坐標為（xh，yh），每個質心像素坐標

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

If

dic

minDic=dic

End

End

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

Until設定迭代終止條件mu（如IE-IO），當各個新質心相對于老質心偏移量小于mu時，終止迭代。

End

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

按照本文改進的算法計算出的聚合結果為下表1所示，其中POI點的坐標是百度坐標體系中的像素坐標。

3 結論

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