稀疏度過濾和密度聚類的商圈核心區(qū)域范圍劃分方法

睢文蓉

（美味不用等(上海)信息科技股份有限公司 上海市 201203）

1 概述

隨著交通出行方式多樣化、居民消費水平不斷提高以及旅游業(yè)不斷發(fā)展的影響下，中國城市商圈概念得到快速發(fā)展。在這樣的大背景下，對商圈核心范圍劃定并做空間維度統(tǒng)計分析，可以幫助商業(yè)管理者和業(yè)主們制定經營策略方向和區(qū)域商業(yè)布局，甚至還可以幫助城市做整體區(qū)域規(guī)劃和城市交通規(guī)劃等，在商業(yè)布局及城市規(guī)劃上都具有重要意義。如何對商圈核心范圍進行精準的劃定，本文提出了一種新方法：稀疏度過濾和密度聚類(Sparsity-Filter and Density-Cluster)，簡稱SFDC。此方法通過結合GeoHash 編碼算法和DBSCAN 聚類算法，利用它們的特點來計算經緯度樣本分布稀疏度，實現(xiàn)邊緣樣本過濾和噪點過濾，同時完成高密度核心區(qū)域的劃定。實際數(shù)據(jù)證明，通過SFDC 的方法，可以有效過濾邊緣樣本和噪點，并將邊界誤差控制在±0.076km 范圍內。

2 GeoHash編碼和DBSCAN密度聚類算法

2.1 GeoHash算法

GeoHash 編碼是一種對空間編碼的算法，也就是創(chuàng)建空間索引的算法，以B 樹實現(xiàn)。在墨卡托投影平面上進行劃塊，劃成N 個矩形區(qū)域，每個矩形區(qū)域都被賦予一個字符串編碼，所有落在同一個矩形區(qū)域內的經緯度樣本將被賦予相同的編碼。

對一個經緯度樣本進行GeoHash 編碼的過程就是對經度和緯度進行多次二分法逼近，落在左區(qū)間為0，右區(qū)間為1。然后將獲得的兩個二進制字符串進行合并，偶數(shù)位放經度，奇數(shù)位放緯度。GeoHash 采用base32 編碼方式，即每一個字母或數(shù)字由5bits 組成（2^5=32），通過將經緯度二分法合并獲得的二進制值進行進制轉換和編碼字符對應轉換后形成新的字符串，這個新字符串即GeoHash 編碼。通常使用0-9 和a-z[^ailo]來進行對應。

因為base32 基于5bits，需要經度和緯度進行二分法的次數(shù)之和是5 的倍數(shù)、經度次數(shù)≥緯度次數(shù)且次數(shù)值最相近，以達到劃塊趨近正方形的效果。以編碼位數(shù)為1 位來舉例，需要5 個bits，即00000～11111，可獲得32 種不同的二進制值。對緯度進行2 次二分逼近，經度進行3 次二分逼近，獲得對應二進制字符串。

按照偶數(shù)位經度奇數(shù)位緯度合并后，得到5 位bits 的二進制編碼表，如表1 所示。

最后通過進制轉換成十進制，再根據(jù)編碼字符對應轉換生成最終的編碼。通過上面的過程，就獲得了把整個地圖用1 位GeoHash編碼切分為32 個矩形的效果。這個算法過程其實是遵循Z 階空間填充曲線的算法，是z-orader 的一種應用，在進行最近鄰查詢等場景應用中非常方便。

當編碼長度取1 位時，就相當于把整個地圖切割成32 個矩形區(qū)域，再增加一位就相當于在這32 個矩形區(qū)域各自再次劃分，以此類推，編碼位數(shù)越多，劃塊越多，也就是地理上精度越高。

2.2 DBSCAN算法

DBSCAN 是一種基于密度的聚類算法，有兩個參數(shù)，分別是密度圈半徑(epsilon)和圈內點個數(shù)(minPts)，結合這兩個參數(shù)可以把所有樣本點分為三種，即核心點、邊緣點和離群點。按照以下步驟進行數(shù)據(jù)的處理：

（1）將樣本坐標點(X,Y) 作為樣本數(shù)據(jù)集，給定參數(shù)(epsilon,MinPts)后，將所有樣本坐標點(X,Y)標記為“unvisited”。

（2）隨機選擇一個樣本坐標點作為起始點，將它標記為“visited”，以它為圓心畫個圈，如果這個圈覆蓋到其它樣本坐標點的數(shù)量n MinPts，則把此樣本點記為核心點，而被圈中的n 個樣本坐標點與合并歸入為一個類，同時把其中標記是“unvisited”的點改為“visited”。之后對這n 個樣本坐標點做與相同的操作：畫圈、覆蓋其它點、歸入類，如此循環(huán)。如果循環(huán)中某個樣本坐標點的圈內樣本數(shù)量n MinPts，則將此樣本坐標點記為邊緣點，并且它圈內的點不再參與循環(huán)。當類沒有新的點可以參與循環(huán)后，則循環(huán)結束， 聚類完成。

（3）然后從其它標記仍然是“unvisited”樣本坐標點中隨機選擇一個點作為下一個起始點，開始和上面相同的操作直至第二個類聚類完成。如此往復直至所有樣本坐標點都被訪問過為止。如果某個起始點的圈內樣本數(shù)量n MinPts，則此起始點記為離散點，不做其它操作，直接開始隨機選擇下一個起始點。

按照上述算法步驟，當樣本數(shù)據(jù)集中所有“unvisited”的樣本遍歷完成后，所有樣本被聚類到一個或幾個類(Ln)中，同時依照設置的參數(shù)，把一些離散的噪點檢測出來并過濾掉。

3 商圈核心區(qū)域劃定方法——稀疏度過濾和密度聚類(SFDC)

3.1 商圈店鋪分布特點

商圈內店鋪的密度分布，一般有幾個特點：

（1）商圈與商圈之間店鋪分布有稀疏緊密之分，但一個商圈內店鋪是比較集中的。

（2）商圈內店鋪分布一般是核心密集邊緣稀疏。

表2：GeoHash 經度對照表

圖1

3.2 SFDC劃定商圈核心區(qū)域過程模塊

用稀疏度過濾和密度聚類(SFDC)劃分商圈核心區(qū)域的過程分幾個模塊：

（1）樣本準備：需要采集商圈店鋪地理位置信息，并將商圈店鋪地理位置樣本轉換成經緯度，將此數(shù)據(jù)作為初始數(shù)據(jù)樣本。我們利用地圖開放平臺和本地生活平臺的開放API 來獲取數(shù)據(jù)，并規(guī)整為我們需要的經緯度樣本數(shù)據(jù)。

（2）GeoHash 編碼：對經緯度樣本進行GeoHash 編碼，將POI 經緯度轉換為編碼樣本。

（3）稀疏度過濾：對編碼樣本計算稀疏度，做大范圍邊緣樣本過濾，剔除那些離商圈核心過于遙遠的樣本。

（4）DBSCAN 聚類：對編碼樣本坐標點做聚類，過濾離散樣本即噪點，標記核心點和邊緣點，形成可信的樣本聚類作為商圈范圍度量。

（5）可視化：對邊緣點的凸點繞數(shù)實現(xiàn)可視化展示。

3.3 GeoHash編碼和稀疏度過濾

假定商圈A 獲得了大量的店鋪經緯度樣本后，下一步要獲取商圈稀疏度指標用以過濾非常邊緣的樣本，也即是計算商圈的稀疏度。經緯度樣本落在地圖上，有疏有密，一般都遵循核心密集邊緣稀疏的規(guī)律，利用單位面積內的經緯度樣本數(shù)量來確定稀疏度。

把地球展開成一個二維坐標平面，即墨卡托投影，那么經線為范圍為[-180,180]區(qū)間的x 軸，緯線為范圍為[-90,90]的y 軸。

商圈A 的店鋪經緯度樣本將在墨卡托投影上進行GeoHash 編碼。

根據(jù)經驗和計算，GeoHash 編碼位數(shù)對應的精度如表2 所示。

零售店鋪面積大小在邊長為0.076km 區(qū)域范圍內是比較合理的，因此我們把先前獲取的商圈A 的店鋪經緯度樣本進行7 位長度的GeoHash 編碼 (Geo7)。

3.4 計算稀疏度過濾邊緣樣本

將商圈A 的店鋪經緯度樣本進行7 位GeoHash 編碼后，我們按編碼分組計算每個編碼樣本的經緯度樣本數(shù)(N)，N=0 排除，獲得商圈A 的一組編碼樣本(Geo7,N)，樣本個數(shù)為C。設定閥值為n，我們將商圈A 的編碼樣本(Geo7,N)中N ≥n 的樣本計數(shù)(CN≥n)，然后將其占所有樣本數(shù)的比值作為稀疏度(S)。

將(Geo7,N)的矩形區(qū)域中心坐標經緯度作為該編碼樣本的坐標點(Lati, Lngi)，通過對商圈A 所有(Lati, Lngi)做平均經緯度計算得到編碼樣本的中心點(Latc, Lngc)。

將(Lati, Lngi)與中心點(Latc, Lngc)做距離計算獲得每個編碼樣本坐標點之間的距離(Ri)。

將所有編碼樣本距離(Ri)中的最遠距離記為R，R 與稀疏度S的乘積作為過濾編碼樣本的依據(jù)，也就是說每個編碼樣本的坐標點(Lati, Lngi)與中心坐標點(Latc, Lngc)之間的距離超過R×S，則將之過濾，留下的編碼樣本即為商圈A 的核心區(qū)域。

這個過程中，設定一個合適的n 值是最為關鍵的，它跟每個商圈的樣本的數(shù)據(jù)量、數(shù)據(jù)質量都有很大關系，需要進行大量的實驗調整才能達到預期。本文統(tǒng)一使用了n=20。當然，根據(jù)不同的商圈，n 可以適當調整為差異化的值。

經過以上步驟，商圈的大致范圍以及需要精細過濾和邊界查找的編碼樣本就得到了。

3.5 DBSCAN精細過濾噪點，查找邊界

在上一步過程后，商圈的大致范圍已經勾勒出來，下一步我們通過DBSCAN 算法對編碼樣本坐標點進行處理，精細過濾噪點，以及進行邊界查找。

本文選擇過濾后的GeoHash 編碼樣本坐標點作為DBSCAN 算法樣本，而不選擇過濾后的經緯度樣本，有兩個原因：

（1）在地理位置范圍上，現(xiàn)實中劃分商圈核心區(qū)域邊界誤差在±0.07 內是完全可以接受的。

（2）經緯度樣本的密度分布不均勻，這對于使用給定值參數(shù)(epsilon, MinPts)的DBSCAN 算法來說，處理多密度的效果和效率不理想。而編碼樣本坐標點是密度均勻的， DBSCAN 效率會非常高且效果好，這易于我們實驗和調整參數(shù)。

我們將商圈A 所有編碼樣本坐標點(Lati, Lngi)進行DBSCAN算法處理，一些離散異常樣本可以被找到并被過濾掉，同時聚類獲得的核心點和邊緣點也基本可以把商圈A 的邊界查找出來。而要想獲得較為符合常識和預期的商圈邊界結果，算法的參數(shù)(epsilon, MinPts)值的選擇就非常關鍵，這需要進行大量的聯(lián)合調參工作，經過多次迭代計算對比，選擇最合適的參數(shù)值。

3.6 基于繞數(shù)的方法描邊圖形展示

我們對經過過濾的編碼樣本坐標點邊緣點進行繞數(shù)的方法來進行圖形描邊。原理是：

（1）每個邊緣點作為凸點樣本，找到Y 最大的樣本中X 最小的那個點作為起始點，記做點A，將此點作為原點做水平切線，順時針旋轉，當線碰到的第一個點記做點B，聯(lián)線AB。

（2）以點B 為原點做切線，切線方向為C，同樣做順時針旋轉，當線碰到的第一個點記為點C，聯(lián)線BC。

（3）C 與B 做相同操作，以B 為切線方向，以此類推，直到找到起始點A。

把商圈編碼樣本進行上述操作后，就可以獲得直觀的商圈范圍劃定。

4 結論

本文通過結合GeoHash 編碼算法和DBSCAN 聚類算法，提出一種新的方法：稀疏度過濾和密度聚類(SFDC)，在劃分商圈核心區(qū)域范圍中得到應用。利用商圈內店鋪經緯度樣本，通過GeoHash編碼將經緯度樣本轉變?yōu)橐环N密度劃塊的形式，從而計算出商圈的稀疏度，通過稀疏度進行大范圍的邊緣數(shù)據(jù)過濾。然后對編碼樣本坐標點通過DBSCAN 算法處理，精細過濾離散點數(shù)據(jù)，獲得核心點和邊緣點，實現(xiàn)邊界查找。通過這種方法，我們可以有效劃分出商圈核心區(qū)域的范圍，且邊界誤差保持在±0.076km 范圍內。整個過程中，稀疏度的樣本數(shù)閥值n 和DBSCAN 的(epsilon,MinPts)參數(shù)的選擇對結果的準確性影響非常大，需要對數(shù)據(jù)進行大量實驗不斷的調整后才能得到較為理想的參數(shù)值，同時整個計算過程也較為依賴樣本數(shù)據(jù)的量和數(shù)據(jù)質量的情況。