GNSS数据的智能聚类学习算法研究

发布时间：2020-06-16 06:01

【摘要】：随着GNSS(Global Navigation Satellite System)终端设备的普及与广泛应用,日益产生了海量的、带丰富位置信息的数据,这些数据正在支撑地球探测技术的发展。然而,GPS(Global Position System)作为GNSS的一种应用最广泛、数据积累最丰富的导航卫星系统,怎样分析、处理且获取到GPS数据中所隐藏的地质与空间变迁信息,并将结果应用到地球探测中拓展GIS(Geographic Information System)应用范围,为智慧城市发展和规划提供更有效的参考和支持,是当前地球探测领域研究的热点。论文以城市出租车GPS数据为研究对象,以遗传算法、粒子群算法和蚁群算法三种智能算法为研究基础,以聚焦划分的聚类算法(K-means/K-means++、Fuzzy C-means、K-median)为自动聚类的基本算法;提出了基于智能优化的GPS数据自动聚类学习算法,这些算法可以不需要用户输入过多参数而实现GPS数据自动聚类,并能获得较好的聚类结果以及更好的发现城市热点、城市运行状态等有价值的信息,从而为地球探测的发展提供有效的技术支撑。在GNSS数据的智能聚类学习算法中,提出了基于噪音和密度的初始化种群技术、构建了基于模糊系统的智能算法参数自动生成技术、提出了基于密度的共享小生境技术及其智能算法混合方法,用于克服了智能学习算法优化停滞难以全局最优化、需要用户定义众多参数、以及算法本身易早熟等现象,确保了智能算法适应了划分聚类的非监督自适应学习;同时,也有效克服了基于划分的聚类算法聚类数目不易确定、对种子点的敏感、易陷入局部最优等长期以来存在的缺陷。因此,创新开展了以下工作。(1)结合噪音、改进Canopy、密度估计与K-means++分别提出了三种遗传算法的初始化种群技术,并将时间复杂度控制在O(n)左右(n是GPS数据点的数目);同时提出了一种基于密度估计的共享小生境技术和改进型基因重排技术,用于避免遗传算法早熟现象且处理不等长的染色体长度。并结合自适应交叉、变异、精英操作实现遗传优化,找到最优个体(染色体)实现城市出租车GPS数据的K-means自动聚类。最终通过实验验证显示,获得了较好的对聚类结果。特别地,在捕获的最优个体中,包括了聚类数目和初始化聚类中心(种子点),也是基于遗传算法的最优解。因此,整个算法有效克服了遗传算法早熟现象,并能有效确保种群的多样性,达到全局优化;同时,不需要事先为K-means聚类输入聚类数目和随机选择种子点,有效提高了K-means聚类的性能。(2)用基于噪音的初始化种群方法、遗传算法与自适应模糊的粒子群算法融合,提出一种新的模糊粒子群算法与遗传算法融合的自动聚类算法。一方面找到最优染色体实现K-means自动聚类;另一方面改进了噪音半径(自动生成噪音半径实现种群初始化)和增加了模糊输出量,并将K-means融合到粒子群与遗传算法混合中实现聚类,即先粒子群操作,再执行遗传操作聚类,后执行K-means操作,最终以最好哪个个体作为最终聚类结果。用多组出租车GPS数据实验评估表明,两种方法都可以获取较好的结果,更容易挖掘到城市热点和人群聚焦点。(3)用基于噪音的初始化种群方法、遗传算法与提出的自适应模糊蚁群系统全面混合,提出一种遗传算法与蚁群系统相结合的自适应模糊蚁群K-means自动聚类算法,即先遗传操作获得最优染色体,后再进入蚁群系统算法中实现蚁群K-means自适应聚类,有效克服了遗传算法、蚁群系统和K-means不足,特别是有效解决了K-means聚类敏感于初始化聚类中心和将上一代最优聚类结果保存到下一代的问题,实现了非监督自动学习完成聚类。最后以几种出租车城市GPS数据为实验数据,从两个角度实验验证评估表明算法具有很好的有效性,并提高聚类性能,有效避免了聚类陷入局部最优化。(4)在云计算环境下,提出了基于MapReduce的遗传K-means聚类算法,用于处理大体量GPS数据。首先以Mahout中的Canopy、K-means为基础,用采样频率改进Canopy和K-means++(是基于MapReduce的)并使其产生适当聚类数目,生成遗传操作的初始化种群;接着进行自适应遗传操作完成聚类优化,然后获取最优染色体实现K-means操作;实验采用一组208M、19M和1.9M的出租车GPS数据与其它算法比较表明,本文提出的算法具有较好的效率,并获取到了优良的聚类结果。(5)以出租车GPS数据特征为基础,提出一种基于角度划分和余弦约束的GPS轨迹片段生成方法(含有3个GPS点的片段),再结合基于拉格朗日定理改进了模糊C-means(Fuzzy C-means)聚类算法,并对所生成的轨迹片段进行聚类。同时,结合基于噪音的初始化种群方法和模糊系统,提出了模糊自适应GA,并用于实现改进型模糊C-means轨迹片段的自动聚类;最后采用最小二乘算法回归生成GPS平滑轨迹,能用于解释轨迹周边的城市热点、人流量和交通状态等。最后以含有71375个北京出租车GPS点的实验验证表明,所提出的两种方法具有很好的性能和效率,并能降低GPS轨迹局部信息丢失和避免聚类陷入局部最优,从而为城市道路规划、城市运行趋势和城市发展提供一定的参考。
【学位授予单位】：成都理工大学
【学位级别】：博士
【学位授予年份】：2018
【分类号】：P228.4

【参考文献】