[發明專利]一種基于K-means算法的地圖聚合方法

有效

• 申請號: 201510697813.5
• 申請日: 2015-10-23
• 公開（公告）號: CN105426387B
• 公開（公告）日: 2020-02-07
• 發明（設計）人: 楊田鎂
• 申請（專利權）人: 北京銳安科技有限公司
• 主分類號: G06F16/29
• 分類號: G06F16/29;G09B29/10
• 代理公司: 11332 北京品源專利代理有限公司
• 代理人: 胡彬;孟金喆

本發明公開了一種基于K?means算法的地圖聚合方法，通過對視野范圍內的標志物列表先進行聚合分類，使每一個標志物都找到自己的目標聚簇，形成最終的聚簇列表，再對聚簇列表中的每一個聚簇應用K?means算法計算每一個聚簇的中心點，最后將所述中心點顯示在地圖上，實現了用少量的點來表示地圖中的所有點，使地圖顯示的更清晰、明朗。

技術領域

本發明實施例涉及地圖數據處理技術領域，尤其涉及一種基于K-means算法的地圖聚合方法。

背景技術

隨著互聯網地高速發展，數據已經滲透到每行每業中，逐漸成為重要的生產因素，伴隨而來的是人類可以進行分析和處理的海量數據，稱之為大數據。如今在中型以上的城市如北京、上海等，每天在網絡行為中產生的各類數據已經非常龐大。

在地理信息系統(Geographic Information System，GIS)中，一個興趣點(Pointof Interest，POI)可以是一棟房子、一個商鋪、一個郵筒以及一個公交站等。傳統的地理信息采集方法需要地圖測繪專業人員采用精密的測繪儀器去獲取一個興趣點的經緯度，然后再標記下來。采集每一個POI是一個非常耗時耗力的工作，同時，POI的數量在一定程度上又代表著整個GIS的價值。每個POI包含四方面信息：名稱、類別、經度和緯度，完整的POI信息是豐富導航地圖的必備資訊，而及時的POI能提醒用戶路況的分支及周邊建筑的詳細信息，也能方便導航查到用戶所需要的各個地方，選擇最為便捷和通暢的道路來進行路徑規劃，因此，導航地圖中的POI數量直接影響了導航的質量和效率。

正是因為在電子地圖中有著大量的POI，在使用電子地圖時，通常會遇到在某個地區包含成千上萬個POI的情況，若同時加載顯示在電子地圖中，會顯得很亂，甚至覆蓋地圖底圖，也會占用大量系統資源，甚至引發瀏覽器的崩潰或者卡頓，極大地影響用戶體驗。因此當數據量過大時，通過一種方法對數據進行處理顯得非常有必要。

發明內容

本發明提供一種基于K-means算法的地圖聚合方法，以實現標志物在地圖上顯示的更清晰明朗。

第一方面，本發明實施例提供了一種基于K-means算法的地圖聚合方法。該方法包括：

S1、查詢地圖上視野范圍內的標志物列表；

S2、根據所述標志物列表創建聚簇列表，提取所述標志物列表中的一個標志物作為當前標志物；

S3、判斷所述當前標志物與所述聚簇列表中的每一個聚簇之間的距離，是否小于預設距離，若是，則將對應的聚簇作為所述當前標志物的目標聚簇，繼續執行步驟S4，否則，執行步驟S6；

S4、判斷所述當前標志物是否在目標聚簇的網格范圍內，如果在，則將所述當前標志物加入到所述目標聚簇的標志物列表中，否則，執行步驟S6；

S5、判斷所述標志物列表中是否存在下一個未確定目標聚簇的標志物，若是，則作為當前標志物，并返回執行步驟S3，若否，則執行步驟S7；

S6、以所述當前標志物為聚簇中心，建立新的聚簇，并將該聚簇加入到步驟S2中的聚簇列表中，返回步驟S5；

S7、對聚簇列表中的每一個聚簇應用K-means算法得到每個聚簇的中心點；

S8、將所述中心點在地圖上進行顯示。

進一步地，所述標志物列表中的每一個標志物包括：名稱、類別、經度以及緯度信息。

優選的，根據所述標志物列表創建聚簇列表，包括：從所述標志物列表中選取設定數量的標志物，添加至聚簇列表中。

示例性地，判斷所述當前標志物是否在目標聚簇的網格范圍內之前，還包括：根據地圖的縮放級別確定所述目標聚簇的網格范圍。

優選的，所述K-means算法中的k設置為1。