睢文蓉

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

1 概述

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

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

2.1 GeoHash算法

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

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

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

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

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

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

2.2 DBSCAN算法

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

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

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

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

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

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

3.1 商圈店鋪分布特點(diǎn)

商圈內(nèi)店鋪的密度分布，一般有幾個(gè)特點(diǎn)：

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

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

表2：GeoHash 經(jīng)度對照表

圖1

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

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

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

（2）GeoHash 編碼：對經(jīng)緯度樣本進(jìn)行GeoHash 編碼，將POI 經(jīng)緯度轉(zhuǎn)換為編碼樣本。

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

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

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

3.3 GeoHash編碼和稀疏度過濾

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

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

商圈A 的店鋪經(jīng)緯度樣本將在墨卡托投影上進(jìn)行GeoHash 編碼。

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

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

3.4 計(jì)算稀疏度過濾邊緣樣本

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

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

將(Lati, Lngi)與中心點(diǎn)(Latc, Lngc)做距離計(jì)算獲得每個(gè)編碼樣本坐標(biāo)點(diǎn)之間的距離(Ri)。

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

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

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

3.5 DBSCAN精細(xì)過濾噪點(diǎn)，查找邊界

在上一步過程后，商圈的大致范圍已經(jīng)勾勒出來，下一步我們通過DBSCAN 算法對編碼樣本坐標(biāo)點(diǎn)進(jìn)行處理，精細(xì)過濾噪點(diǎn)，以及進(jìn)行邊界查找。

本文選擇過濾后的GeoHash 編碼樣本坐標(biāo)點(diǎn)作為DBSCAN 算法樣本，而不選擇過濾后的經(jīng)緯度樣本，有兩個(gè)原因：

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

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

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

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

我們對經(jīng)過過濾的編碼樣本坐標(biāo)點(diǎn)邊緣點(diǎn)進(jìn)行繞數(shù)的方法來進(jìn)行圖形描邊。原理是：

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

（2）以點(diǎn)B 為原點(diǎn)做切線，切線方向?yàn)镃，同樣做順時(shí)針旋轉(zhuǎn)，當(dāng)線碰到的第一個(gè)點(diǎn)記為點(diǎn)C，聯(lián)線BC。

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

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

4 結(jié)論

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