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平滑轨迹，为城市道路规划及路网更新提供了新方法。