GNSS數(shù)據(jù)的智能聚類學(xué)習(xí)算法研究

周相兵

1.中國科學(xué)院水利部成都山地災(zāi)害與環(huán)境研究所數(shù)字山地與遙感應(yīng)用研究中心，四川 成都 610041；2.四川旅游學(xué)院信息與工程學(xué)院，四川 成都 610059

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

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

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

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

(4)在云計(jì)算環(huán)境下，提出了一種基于MapReduce的遺傳k-means聚類算法，用于處理大體量GPS數(shù)據(jù)。算法以Mahout中的Canopy、k-means為基礎(chǔ)，用采樣頻率改進(jìn)Canopy和k-means++(是基于MapReduce的)并使其產(chǎn)生適當(dāng)聚類數(shù)目，生成遺傳操作的初始化種群，實(shí)現(xiàn)大體量GPS數(shù)據(jù)自適應(yīng)遺傳自動(dòng)聚類。

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