GNSS數據的智能聚類學習算法研究

周相兵

1.中國科學院水利部成都山地災害與環境研究所數字山地與遙感應用研究中心，四川 成都 610041；2.四川旅游學院信息與工程學院，四川 成都 610059

隨著GNSS終端設備的普及與廣泛應用，海量的、帶豐富位置信息的數據所隱藏的地質與空間變遷信息正在支撐智慧城市的發展。論文以10組不同城市出租車GPS數據為研究對象，以遺傳算法、粒子群算法和蟻群算法3種智能算法為研究基礎，以聚焦劃分聚類算法為自動聚類的基本算法；提出了基于智能優化的GPS數據自動聚類學習算法，這些算法通過所構建的模糊系統和初始化種群技術，有效地克服了基于劃分聚類算法的聚類數目不易確定、預設參數過多、敏感于初始種子點、難以將上一代優秀聚類結果保存到下一代、易陷入局部最優等長期以來存在的缺陷。試驗驗證表明，本文所提出的算法效率能提升6%及以上，最高可達20%，而且算法計算復雜度能控制在O(n)左右(n是GPS數據點的數目)；能更好地發掘城市熱點、人群聚集區、城市運行狀態等有價值信息。因此，本文主要內容包括：

(1)結合噪音、改進Canopy、密度估計與k-means++分別提出了3種遺傳算法的初始化種群技術；提出了一種基于密度估計的共享小生境技術和改進型基因重排技術，用于避免遺傳算法早熟現象且處理不等長的染色體；并結合自適應交叉、變異、精英操作實現遺傳優化，找到最優染色體(個體)實現城市出租車GPS數據的k-means自動聚類。整個算法有效確保種群的多樣性，達到全局優化。

(2)將基于噪音的初始化種群方法、遺傳算法與自適應模糊的粒子群算法進行融合，提出了一種新的模糊粒子群算法與遺傳算法融合的自動劃分聚類算法。一方面捕獲到最優染色體實現k-means自動聚類；另一方面自動生成噪音半徑和增加了模糊系統輸出量，并將k-means融合到粒子群與遺傳算法混合中實現GPS數據自動聚類。

(3)將基于噪音的初始化種群方法、遺傳算法與提出的自適應模糊蟻群系統進行全面混合，研究了一種遺傳算法與蟻群系統相結合的自適應模糊蟻群k-means自動聚類算法。先用遺傳操作獲得最優染色體，后再進入蟻群系統算法中實現蟻群k-means自適應聚類，有效解決了k-means聚類敏感于初始化聚類中心和聚類陷入局部最優化缺陷。

(4)在云計算環境下，提出了一種基于MapReduce的遺傳k-means聚類算法，用于處理大體量GPS數據。算法以Mahout中的Canopy、k-means為基礎，用采樣頻率改進Canopy和k-means++(是基于MapReduce的)并使其產生適當聚類數目，生成遺傳操作的初始化種群，實現大體量GPS數據自適應遺傳自動聚類。

(5)以出租車GPS數據特征為基礎，提出了一種基于軌跡角度劃分和余弦約束的GPS軌跡片段生成方法(含有3個GPS點的軌跡片段)，再結合基于拉格朗日定理改進了Fuzzy c-means聚類算法，并對所生成的軌跡片段進行模糊聚類。同時，結合基于噪音的初始化種群方法和模糊系統，提出了模糊自適應遺傳算法，并用于實現改進型Fuzzy c-means軌跡片段的自動聚類，最后采用最小二乘算法回歸生成GPS平滑軌跡，為城市道路規劃及路網更新提供了新方法。