地圖興趣點聚合演算法的探索與實踐

  • 2020 年 12 月 18 日
  • AI

​一、導讀

在實現基於地圖的業務時,當地圖上需要展示的興趣點(POI)過多時,一般會基於圖面效果和渲染性能的考慮,在大比例尺展示完整的業務數據,而在小比例尺展示聚合態數據。在處理不同數量級、不同分布形態的POI時,如何通過演算法取得更加合理的聚合效果,同時既能支援離線的預處理聚合,也能較好的滿足實時聚合的性能要求是本文主要討論的內容。

註:興趣點(Point of Interest,通常縮寫成POI)是指電子地圖上的某個地標、景點,用以標示出該地所代表的政府機關、商業機構(加油站、超市、餐廳、酒店等)、風景名勝、公共廁所、交通設施等處所。

本文通過對現有聚合演算法進行預研,並結合實際業務對其進行改進,構建了一套能夠滿足多種業務需求的數據聚合方案。其中包含多種針對不同業務場景、不同數量級的POI聚合演算法,並將聚合演算法的配置進行了抽象,實現了聚合效果好,性能高且使用方便的聚合演算法庫,目前已應用到離線聚合和線上實時聚合的各個業務場景中。

二、點聚合演算法比較

本節介紹目前使用較多的點聚合演算法,並對不同點聚合演算法的性能和聚合效果進行橫向對比。針對不同的場景給出了參考使用的點聚合演算法。在此基礎上構建了一套相對通用的點聚合演算法工具,使用者可以根據自身業務的特點,通過一定的配置來自定義具體使用的演算法、策略和參數等等。

2.1 點聚合演算法:

這裡對使用較多的點聚合方案做簡單介紹。

2.1.1 kmeans演算法

kmeans演算法主要通過初始指定k個聚類質心,而後按照「距離」來聚攏「相近」的數據點,而後重新計算新的質心,以此往複。不斷迭代計算k個聚類點的質心,最終回歸到k個聚類結果中,主要有以下兩個缺點:

  • 性能, kmeans是計算密集型演算法,模型需要迭代很多次才能夠完善,且大量的距離計算比較消耗cpu。
  • 效果,kmeans不能解決重疊覆蓋問題(演算法設計指標裡邊沒有對覆蓋問題的評估指標)。

2.1.2 直接網格演算法(Grid-based Clustering)

將地圖劃分為若干個網格,將落在對應網格中的點聚合在小網格的中心點。每個小網格只顯示一個中心點,值為網格內的點數量。具體計算公式如下:

  • 優點,運算速度快,不涉及兩個點之間的距離計算,只有點是否處在網格內的一次性計算就能拿到結果。
  • 缺點,如下圖示,明明相近的兩個點,因為劃分在了不同的網格,而被迫分開計算在不同的網格中心。同時網格的中心,不一定就是網格內點的聚類中心,不能真實地反映聚類的中心點。

2.1.3 網格質心合併演算法

與2.1.2方法基本一致,不同點在於,演算法在將點劃分到不同的網格中以後,會對每個網格的質心重新計算,得到更精確的聚類中心點。此外,還對經過質心計算的網格聚類中心點,進行了合併。(如果不進行合併,可能導致不同網格質心相近,造成覆蓋)。網格質心的合併演算法以一個網格質心為中心,畫一個圓圈(或方格),將在這個範圍內的網格質心都進行合併。圓圈或者方格的覆蓋範圍,可以作為配置來調整。

  • 優點,運算速度較快(計算質心和合併質心不會帶來特別大的計算量)
  • 缺點,增加了計算量,同時也存在一定的誤差,網格的劃分,依舊可能會將原本聚集的點,強制分離開。

2.1.4 網格距離演算法(Grid-Distance-based Clustering)

初始時沒有任何已知聚合點,然後對每個點進行迭代,計算一個點的外包正方形,若此點的外包正方形與現有的聚合點的外包正方形不相交,則新建聚合點(這裡不是計算點與點間的距離,而是計算一個點的外包正方形,正方形的邊長由用戶指定或程式設置一個默認值),若相交,則把該點聚合到該聚合點中,若點與多個已知的聚合點的外包正方形相交,則計算該點到到聚合點的距離,聚合到距離最近的聚合點中,如此循環,直到所有點都遍歷完畢。

  • 優點,運算速度相對較快,每個原始點只需計算一次,可能會有點與點距離計算,聚合點較精確的反映了所包含的原始點要素的位置資訊。
  • 缺點,速度不如完全基於網格的速度快等,同時各個點迭代順序不同導致最終結果不同。因此涉及到制定迭代順序的問題。同時聚類的中心點,是第一個加入該類的點的位置,並不能夠代表整個聚類的中心位置,存在一定的不準確性。

2.1.5 四叉樹演算法(提供快速查找POI點的能力)+網格聚合演算法(提供聚合POI點的具體策略)

首先明確,四叉樹演算法本身不提供數據聚合的能力,它的存在是為了配合之前的網格點聚合演算法,提供快速查找到某一個網格下的所有POI數據的能力。

對應於二叉樹,二叉查找樹適合用來存儲和查找一維數據,可以達到O(logn)的效率。在用二叉查找樹進行插入數據時,查找一個數據只需要和樹結點值的對比,選擇二叉樹的兩個叉之一向下,直到葉子結點,查找時使用二分法也可以迅速找到需要的數據。對應於地圖數據的二維坐標來說,四叉樹可以很好地對二維數據進行存儲和查找。它能夠將數據分成四個象限,在查找數據時,通過對二維屬性(一般是x, y)進行判斷,選擇四個分叉(象限)之一向下查找,直至葉子節點。(同樣的對於三維數據來說,使用八叉樹來進行存儲和查詢)。

2.2.5.1 四叉樹的操作

1.節點分裂:

    • 當滿足特定條件時,為了獲得更好的檢索效率,四叉樹的節點會發生分裂,分裂的做法是:以當前節點的矩形為中心,劃分出四個等大的矩形,作為四個子節點,每個節點深度=當前節點深度+1,根節點深度為0;並且將當前節點的元素重新插入到對應的子節點。

2.插入元素:

    • 從根節點開始,如果當前節點無子節點,將元素插入到當前節點。如果存在子節點(定義為K),並且元素能夠完全被子節K點所「包圍」,就將元素插入到子節點K,對於子節點K進行上述遞歸操作(即查看K節點是否有子節點,如沒有子節點,則將數據存儲在K節點上,如果有子節點,則下沉繼續查找匹配);如果元素跨越了多個子節點,那就將元素存儲在當前節點(即可以將跨越多個節點的數據存儲在多個節點上)。
    • 如果某一節點元素超過特定值,並且深度小於四叉樹允許的最大深度,分裂當前節點。

3.查找元素:

    • 對於給定檢索區域,從根節點起,如果檢索區域與當前節點有交集,且當前節點沒有子節點,則返回當前節點的所有元素。
    • 如果當前節點還有子節點,遞歸檢索與檢索區域有交集的子節點。

2.1.5.2 基於四叉樹的點聚合方案具體實現:

採用網格質心演算法來進行點的聚合,四叉樹提供數據查詢的能力。簡單來說就是把螢幕分割成若干個區域,每個區域最多顯示一個標註,每個區域的數據內容由四叉樹來進行查詢和提供。然後根據地圖縮放比例去設置每個網格區域的大小以達到較好的展示效果。

1.使用基於四叉樹的點聚合的方案首先需要建立四叉樹,具體實現原理如下:

a. 首先對POI數據建立四叉樹索引,四叉樹的結構可以用如下程式碼表示。(創建四叉樹的代價比較大

typedef struct TBQuadTreeNodeData { //四叉樹中存儲的數據點(即poi資訊)(一個四叉樹節點可能包含多個數據點)
   double x; //經緯度坐標
   double y;
   void* data; //額外的補充資訊
} TBQuadTreeNodeData;
TBQuadTreeNodeData TBQuadTreeNodeDataMake(double x, double y, void* data);
​
typedef struct TBBoundingBox { //每個四叉樹節點所表示的區間範圍
   double x0; double y0; //橫縱坐標的最小值
   double xf; double yf; //橫縱坐標的最大值
} TBBoundingBox;
TBBoundingBox TBBoundingBoxMake(double x0, double y0, double xf, double yf);
​
typedef struct quadTreeNode { //四叉樹節點
   struct quadTreeNode* northWest; //西北象限(子節點)
   struct quadTreeNode* northEast; //東北象限(子節點)
   struct quadTreeNode* southWest; //
   struct quadTreeNode* southEast; //
   TBBoundingBox boundingBox; //本節點所表示的數據範圍
   int bucketCapacity;  //本節點的數據容納量(上限)
   TBQuadTreeNodeData *points; //本節點存儲的數據點資訊(poi資訊)
   int count; //目前已經存儲的數據點(poi點)個數
} TBQuadTreeNode;
TBQuadTreeNode* TBQuadTreeNodeMake(TBBoundingBox boundary, int bucketCapacity);

b. 建立四叉樹的過程如下圖所示,在到達節點的容量上限之後節點就會將其表達的數據範圍從中心點開始劃分為四個象限,構成它的四個子節點,子節點如果達到容量上限,同樣重複這一過程。

c. 查找一定範圍內的POI數據的過程如下圖所示(如下圖中查找紅色邊框圈出來的範圍)。比較紅色區域是否和四叉樹元素的根節點有交集,無交集則捨棄,有交集繼續向四叉樹的分支中進行查找。

2.四叉樹建好並且能夠進行區域查詢。接下來點聚合演算法就可以開始執行了,點聚合演算法首先會先將當前螢幕劃分為若干個網格(grid),然後對每一個網格通過四叉樹來查找該網格內的POI,等找到同一個網格中的所有POI數據之後,計算其平均質心,並統計該網格中一共存在多少數據,即可完成聚合。

2.1.6 K-D樹演算法(同四叉樹演算法,提供快速查找的能力)

K-D樹(k-dimensional樹的簡稱)是一種分割k維數據空間的數據結構,主要應用於多維空間數據的搜索(如:範圍搜索和最近鄰搜索)。了解K-D樹可以從理解線段樹開始。

2.1.6.1 線段樹的實現

1.線段樹的本質是一棵維護一段區間的平衡二叉樹。線段樹維護的是一個區間內的最大值。比如樹根是8,維護的是整個區間的最大值,每一個中間節點的值都是以它為樹根的子樹中所有元素的最大值。其構建過程可以使用如下偽程式碼表示:

class Node:
   def __init__(self, value, lchild, rchild):
      self.value = value        
      self.lchild = lchild        
      self.rchild = rchild     
​
def build(arr): 
   n = len(arr): 
   left, right = arr[: n//2], arr[n//2:]    
   lchild, rchild = self.build(left), self.build(right)    
   return Node(max(lchild.value, rchild.value), lchild, rchild)

2.通過線段樹,可以在 O(logN) 的時間內計算出某一個連續區間的最大值。如下圖所示:

3.當需要查找樹底層被方框圈起來的區間中的最大值時,我們只需要找到能夠覆蓋這個區間的中間節點就行。可以發現被紅框框起來的兩個節點的子樹剛好覆蓋這個區間,於是整個區間的最大值,就是這兩個元素的最大值。這樣,我們就把一個需要O(N)查找的問題降低成了O(logN),不但如此,也還可以做到O(logN)時間複雜度內的更新,也就是說不僅可以快速查詢,還可以快速更新線段當中的元素。

2.1.6.2 K-D樹的實現

線段樹維護的是一個區間內的元素,是一個一維的序列。如果我們將數據的維度擴充一下,擴充到多維呢?KD-Tree就可以理解成是線段樹拓展到多維空間當中的情況。以二維空間數據來說明K-D樹如何建立。

1.K-D樹建立過程

a. 一個二維的平面中分布著若干個點坐標。

b. 選擇一個維度(比如選擇X軸),將數據一分為二。

c. 經過切分之後,左右兩側的點被分成了兩棵子樹,對於這兩個部分的數據來說我們更換一個維度在進行二分,(其實可以選擇方差最大的維度進行劃分,以此來保證更平均的分配,和更好的區分度)。此處我們選擇y軸進行劃分,就可以得到:

d. 重複上述過程,一直到點不能進行分割為止。即可得到一顆KD樹。因為每次劃分都是選擇中位數來進行劃分,所以可以保證根節點到葉子節點的深度不會超過log(N)。

最終建立的K-D樹存儲上的形式如下圖所示:

2.K-D樹查詢過程
K-D樹的一個最大的優點在於,能夠快速的進行批量查詢,如查詢K個距離最近的數據有哪些、查詢距離滿足一定閾值的數據有哪些等。

a. 假設我們要查找距離給定目標點最近的3個點。首先會創建一個候選集來存儲答案。當找到葉子節點(葉子節點代表一塊兒小區域)之後,這個區域當中只有一個點,把它加入候選集。如下圖所示,「綠色✔️ 」表示樣本被放入了候選集當中,「黃色✔️ 」表示已經訪問過。

b. 通過判斷樣本和當前分割軸的距離,來確定分割軸的另一側有沒有更臨近的數據點。

    • 如果是葉子節點,沒有軸的另一側,則向上從父節點開始查找。
    • 如果是非葉子節點,且當前候選集中已經存在K個最小值,則計算候選集中與目標點距離最遠的距離(d2),與目標點到分割軸的距離(d1)誰更大:
      • 如果目標點到分割軸的距離(d1)更大,即d1 > d2,則另一側沒有比候選集中距離(目標點)更小的點。不需要遍歷另一側的數據點。(因為另一側距離目標點最近的距離,至少是目標點到分界軸的距離d1,還得加上另一側到分界軸的距離x,即 d1+x > d2)。
      • 如果目標點到分割周的距離(d1)更小,即d1 < d2,則分割軸的另一側可能存在距離目標點更小的點,需要進行遍歷。

(a步驟中的節點為葉子節點,本輪向上查找父節點,同時候選集中不滿3個,父節點加入候選集)

c. 分析b步驟中的節點,雖然是父節點,但是另一側沒有數據,所以也向上查找他的父節點,同時目前候選集不滿3個,也加入候選集。

d. 當前節點作為父節點,且右子節點不為空,所以需要判斷目標點到分界線的距離,目標點到分界線的距離d1小於目標點到最遠候選集中點的距離d2,所以分界線另一側有可能有更小的值,需要遍歷。

e. 找到邊界另一側的葉子節點,發現他到目標點距離,大於候選集到目標點的距離,同時候選集已經有了K個值,所以不能構成新的答案。需要繼續向上查找他的父節點。

f. 發現其父節點到目標點的距離,比已有的候選集中的點更小,更新候選集。

2.2 點聚合實現方案:

依託於之前進行的調研,開始對點聚合方案進行實現。本文嘗試了多種演算法的實現,並就其性能和效果進行了對比。其中包含:

  • 直接歐式距離演算法
  1. 計算每個點,與周圍點的距離是否在指定閾值之內,如果滿足則共同構建聚合點,聚合點的坐標取平均值。
  2. 將步驟a中的聚合點,從原有數據集中剔除。重新從原始POI點中選擇一個點,再次進行步驟a構建新的聚合點。
  3. 重複a,b兩個過程,直至所有POI點都完成了聚合。
  • 基於四叉樹的直接歐式距離演算法
    1. 與直接歐式距離演算法基本一致,不同點在於,計算與周圍點的距離是否在指定閾值之內時,是通過四叉樹的查詢來完成的。
  • 網格質心演算法
    1. 與3.1.2中演算法基本一致,不同點在於,本演算法計算了每個網格中數據點的平均質心作為聚合點的位置坐標。
  • 網格質心合併聚合演算法
    1. 在網格質心演算法的基礎上,新增了聚合點的合併邏輯,通過指定閾值來完成聚合點的合併。
  • 基於四叉樹的網格質心演算法
    1. 與網格質心演算法基本一致,不同點在於,查詢一個網格內對應的數據時,使用的是四叉樹來進行查詢。
  • 網格距離演算法
    1. 與3.1.4中演算法一致。
  • 基於四叉樹的網格距離演算法
    1. 與3.1.4中演算法基本一致,只是使用了聚合點來構建了四叉樹,來加快遍歷查詢的速度。
  • 基於KD樹的網格距離演算法
    1. 與3.1.4中演算法基本一致,只是使用了聚合點來構建了KD樹,來加快遍歷查詢的速度。

    2.3 聚合演算法流程:

    1.演算法的輸入:

      • 請求參數中需要包含data和config
        • data指的是需要聚合的poi數據,POI數據需要包含位置資訊。
        • config指的是聚合演算法的配置,如包含多少層級,每個層級聚合演算法的相關參數等等。

    2.演算法的輸出:

      • 點聚合的結果數據中,包含了不同層級的點聚合結果,以Map < String, List < AggregationDTO > > 的形式下發,String代表不同聚合層級的唯一標識,List < AggregationDTO > > 代表著該層多個聚合點的數據。
      • 每一層的聚合結果由多個聚合點來組成,其中每一個聚合點(AggregationDTO)需要包含如下資訊:
        • 聚合點的位置(經緯度或坐標)
        • 聚合點包含的原始POI個數
        • 其他資訊(目前填充的是該聚合點聚合了哪些原始的poi數據資訊)

    3.整個演算法的流程如下:

    三、結果&效果

    1.效果測試數據集
    如下圖所示,目前效果測試使用的數據集為GPS點坐標資訊,下圖中每個黑色的圓點代表一個坐標數據,共175個。

    GPS點分布圖

    同上圖,無地圖資訊

    2.評價指標

      • 對於聚類結果的評價指標,核心的思想分為兩部分:
        • 一是緊湊度,即簇內樣本距離盡量的近;
        • 二是分離度,即簇與簇之間的樣本盡量的遠。
      • 一篇Google學術引用量600+的論文做了解析,Liu Y, Li Z, Xiong H, et al. Understanding of internal clustering validation measures[C]//2010 IEEE International Conference on Data Mining. IEEE, 2010: 911-916. 結論是:一種「S_Dbw」聚類評價指標對於各種雜訊,不同密度的數據集等等干擾項的評價結果魯棒性最強,對比其他評價指標有顯著優勢。
      • 「S_Dbw」公式分為兩部分,Dens_bw(c)用來衡量各個類的平均密度關係,該值較小表明,聚類簇集的類間區分度較好。Scat(c)用來計算類內距離 ,距離越小同一類中數據對象間的相似性越高。具體公式中每個部分的解釋可參考論文,此處不再贅述。

    3.演算法效果(部分演算法直觀演示)
    a. 網格質心演算法(劃分網格,然後計算每個網格的質心作為聚類中心)由於網格是固定的,出現了「聚集點被網格割裂」的情況。

    b. 網格質心合併演算法(在網格質心演算法的基礎上,對兩個距離較近的聚合點,進行合併)
    將點聚合的結果,再進行一次聚合,以期望被網格割裂開來的聚集點數據,能夠重新聚合在一起。

    c. 網格距離演算法(即2.2.4中的演算法)

    以原始數據點自身為中心,按照一定的距離範圍,去聚合周圍距離最近的聚合點。與其他演算法不同,網格距離演算法的設計思想是原始數據點和聚合點的合併,而不是原始數據點之間的相互合併。如果沒有在聚合範圍內找到聚合點,就以自身位置新建一個聚合點。

    參數:0.04

    參數:0.03

    d. 效果對比:

      • 在使用直接距離聚合演算法和網格質心演算法中,有些場景下會將距離較遠的兩個點聚合在一起,網格距離演算法能夠有效改善這種情況。原因有兩個:
    1. 因為網格距離演算法是將原始數據點聚合到「距離最近的」聚合點中,能夠在一定程度上避免原始數據點聚合到「距離更遠」的聚合點。
    2. 網格距離演算法中,對於每一個原始數據點的遍歷中,它能夠影響的只有自己這一個原始數據點。而直接距離演算法中每一個原始數據點的遍歷,可能會影響到多個原始數據點。雖然兩種演算法都會受到原始數據點的遍歷順序影響,但影響的程度相差很大。總體來說,網格距離演算法表現更好。
  • 網格距離演算法能夠在一定程度上避免「網格將原本聚集的數據點割裂」開的這種情況。
  • 如網格距離演算法中所展示的兩張圖,聚合點的分布並沒有被網格所局限。而對比網格質心演算法所展示的效果圖,其每個網格只能出現了一個聚合點。

    不同演算法使用建議:

    其中,原始POI數據量的大小分界線,以10K為分界線,超過10K可以認為數據量較大,演算法之間的性能會有差別。聚合點數量的多少,以1K為邊界,超過1K個聚合點可以認為聚合點數量較大。準確率和效率的要求,需要使用者根據業務的具體要求來做判斷。

    招聘

    阿里巴巴高德地圖在線引擎和安全運維中心團隊長期招聘機器學習演算法、C++Java 資深工程師/技術專家/高級專家,職位地點:北京。歡迎投遞簡歷到 [email protected],郵件主題為:姓名-應聘團隊-應聘方向。