[發明專利]一種動態地理網格聚類算法

在審

• 申請號: 201410199387.8
• 申請日: 2014-05-08
• 公開（公告）號: CN104021274A
• 公開（公告）日: 2014-09-03
• 發明（設計）人: 凌晨;胡亮;邢長勝;何宇
• 申請（專利權）人: 烽火通信科技股份有限公司
• 主分類號: G06F19/00
• 分類號: G06F19/00
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本申請屬于數據挖掘技術領域，涉及聚類分析，尤其涉及一種動態地理網格的聚類分析算法。

背景技術

聚類分析是數據挖掘中廣為研究的課題之一，是從數據中尋找數據間的相似性，并依此對數據進行分類，從而發現數據中隱含的有用信息或知識。網格方法是空間數據處理中常用的將空間數據離散化的方法，基于網格的聚類算法由于易于增量實現和進行高維數據處理而被廣泛應用于聚類算法中。

傳統的地理網格地圖是一種比較簡單的地圖類型。將地圖區域按照平面坐標或者按照經緯度劃分網格，以網格為單元描述地理位置信息。把這種特定的劃分方式延伸到與數據融合中來，可以用在區域綜合分析，統計空間制圖，以及數據挖掘等方面。

目前，研究人員已經提出了很多基于網格的聚類算法，其中STING、WaveCluster和CLIQUE是具有代表性的基于網格的聚類算法，或者說是比較傳統的基于網格的聚類算法。此外聚類算法還有蟻群聚類算法等傳統的網格聚類算法，如STING，它的網格結構的最低層的劃分粒度決定了自身算法聚類的質量。如果網格結構的最低層的劃分粒度比較粗，網格單元的數量相對較少，則會減少聚類時間，聚類速度快，但是粗粒度會降低聚類精度；反之，如果網格結構的最低層的劃分粒度比較細，就會得到較高的聚類精度，但同時處理開銷會增加，從而導致聚類時間會較長。另一方面，如果網格結構的最低層的劃分粒度過小，就會增加網格單元的數量，可能會導致落入網格單元中的數據點數目過少，從而不滿足稠密度閾值要求而被忽略。蟻群聚類算法是聚類分析常用的算法，基于蟻群算法的聚類分析方法在聚類分析過程中，運行時間可能較長，對于要求實時性的系統性能不能達到要求。

發明內容

本專利申請要解決的技術問題是：針對傳統的基于網格的聚類算法的不足，提供一種新的地理網格聚類算法，提高聚類的精度和實時性。

為了解決上述技術問題，本專利申請提供了一種動態地理網格聚類算法。具體步驟包括：

1)找出區域中的最大、最小經緯度，再根據步進長度step對最大、最小經緯度之間的區域劃分網格，其中，步進長度可在聚合數據分析中根據實際情況自行調整；

2)計算出每個點所在的網格的編號，點Pn(Xn，Yn)網格編號的方法如下：

(1)計算點Pn所在的列數C(Pn)＝(Xn-Xmin)/step；

(2)計算點Pn所在的行數R(Pn)＝(Yn-Ymin)/step；

(3)計算點Pn所在的網格編號G(Pn)＝1+R(Pn)*(Xmax-Xmin)/step+C(Pn)

同一網格中的數據我們認為它們具有共同的聚類屬性，對同一個網格內的點進行聚類，計算出聚合重心點；聚合重心點的計算方法可采用常規的重心點計算方法；

3)以第一次劃分的網格為基礎分別向上、下、左、右方向移動，移動方向的順序不限，移動長度根據區域范圍大小、點分布的密集程度以及聚類精度要求自行調整(一般小于步進長度)，互為對稱方向的移動次數保持一致，每次移動后都重復步驟1)進行聚類。

較佳的，根據區域范圍大小、點分布的密集程度以及聚類精度要求選取合適的移動長度，將網格向上、下、左、右方向各移動一次，移動方向順序不限，每次移動后重復步驟1)進行聚類，所有的聚類點構成最終的聚類結果。

本申請的有益后果是：

1.傳統的網格劃分方法需要將整張地圖進行劃分然后對每個格子進行編號，本專利所述方法無需考慮地圖邊界，只取決于欲分析的數據的邊界值；

2.動態平移網格時，粗細粒度自由控制，靈活性高，且速度高效。

附圖說明

附圖1為實施例中第一次劃分的網格圖；

附圖2為網格右移示意圖。

具體實施方式

本專利申請所述的一種動態地理網格聚類算法，在實現本方法時，在出現經緯度點的一塊區域中找出最大、最小經緯度，例如，現有Pl-Pn個點P1(x1，y1)，P2(x2，y2)，…Pn(xn，yn)，首先取出P1-Pn個點中的最大、最小經緯度(Xmax，Xmin，Ymax，Ymin)；再根據步進長度step對最大、最小經緯度之間的區域劃分網格，并且計算出每個點所在的網格的編號。在聚合數據分析中結合區域大小、點的分布情況以及聚類精度等自行調整步進長度的大小，例如區域范圍較大，且點的分布較稀疏時，步進長度應稍大，反之，區域范圍較小，且點的分布較密集，對聚類精度要求較高時，步進長度應稍小。