位置数据的智能聚类算法研究

作者简介

内容简介

第1章 引言
　　通常，北斗卫星导航系统(beidou navigation satellite system，BDS)、全球定位系统(global position system，GPS)、俄罗斯的格洛纳斯(GLONASS)、欧盟的伽利略(GALILEO)都属于全球导航卫星系统(global navigation satellite system，GNSS)范畴[1]，其中应用最广泛、数据积累最多的是GPS，在智能终端应用最多的也是GPS；但随着BDS的全球覆盖，定位精度越来越高，在不久的将来，BDS也将成为主流智能终端应用的GNSS。本书以城市出租车GNSS(GPS数据)为研究对象，基于智能学习的划分聚类算法挖掘GNSS数据中所隐藏的信息，获得更优秀的聚类中心和轨迹，并用于描述城市空间状态。
　　GNSS终端设备已日益产生了带有位置信息的大体量GNSS数据(称为位置数据，或者位置大数据[2-5])，从GNSS数据中挖掘隐藏的有价值信息[6]，已成为地球探测、空间计算、城市计算和智慧城市的重要组成部分[7-11]，拓宽了地理信息系统(geographic information system，GIS)的应用范围，特别是这些数据中隐藏的城市状态、时空变迁和发展的信息[12]，如城市交通拥挤情况[13-15]、人群迁移分布[14，16，17]、交通出行与服务推荐[18-21]、路网构造[14，22-24]、城市热点可视化与变迁[15，25-27]等，为现代城市管理、城市可持续发展提供了重要参考。怎样从GNSS数据中挖掘出有价值的信息成为近年来研究的热点。其中，常见的研究方法是先从GNSS数据中获取GPS轨迹模式[28-30]，如起点与终点(origins and destinations，OD)[16，31-34]、停止点与移动点(stops and moves，SM)[12，29，35]、移动对象模式(moving object，MO)[36，37]等，然后在这些模式中采用机器学习方法学习满足需求的信息，实现基于位置的推荐[19，38-40]、发现基于位置的兴趣点(point of interest，POI)[41-45]、管理城市交通监控疏导[46-48]、实现位置语义识别[49-51]、抽取城市道路信息[25，52，53]、获取城市运行行为与位置预测[54-56]等。而最常用的应用模式是基于位置提供服务，即以GIS为基础为不同用户提供基于位置的服务(location based services，LBS)[57-60]和智能推送信息，并形成以云计算和大数据为支撑的新型GIS[61]。为了学习基于GNSS的数据信息，常采用非监督学习中的许多聚类学习算法。其中，由于基于划分的聚类方法简单、容易实现、效率高，以及基于密度的方法不受数据形状、形态影响，其已成为位置数据聚类(轨迹聚类)研究和价值信息挖掘的常用方法，在城市发展中得到了广泛应用。本书主要聚焦基于划分的聚类算法，用基于智能学习的划分聚类算法挖掘GNSS数据中有价值的信息。
　　已有的基于划分的聚类方法研究结果表明，在聚类数目有效确定、聚类中心点敏感性处理、全局最优获取以及轨迹片段和子轨迹生成、将上一代优秀的聚类结果保存到下一代、聚类方法方面仍存在问题，且在不同应用领域其聚类效果也有区别。因此，许多研究者将智能学习算法如遗传算法(genetic algorithm，GA)、粒子群优化算法(particle swarm optimization algorithm，PSO)、蚁群优化算法(ant colony optimization algorithm，ACO)等融合到基于划分的聚类算法中，力求改进上述不足，以获得更好的聚类结果。众多研究证明，基于智能学习的聚类算法已取得良好的结果，有效避免了基本聚类算法的不足，也拓展了智能学习研究的深度。但在初始化种群上仍有较高的复杂度(有的甚至高达三次方)，所获取的聚类数目仍有不确定性，算法运行参数仍需要手动设置，全局优化方面仍受到种群多样性和早熟现象的约束。为此，在基于划分的聚类算法中，研究智能学习的初始化种群技术、降低聚类中心的敏感性、自动获取有效的聚类数目、实现全局早收敛、避免局部早熟现象、自动学习有效的聚类结果仍具有重要的研究意义。同时，在聚类结果应用方面，要避免轨迹的局部特征不丢失以及保证聚类过程不受空间特性的影响，关键取决于GNSS数据聚类效果。
　　在基于智能算法的聚类学习算法中，常用且计算效率高的当数K-means[62]及其变种(如G-means、Means shift、Canopy K-means、K-Means++、X-means、K-modes、Bisecting K-means、K-median、Fuzzy K-means等)。具体实现主要有三种模式：①直接将K-means整合到智能学习过程中，当优化结束时，将捕获到的最优个体作为最终的聚类结果，这种模式被命名为“G-K-A-Clustering”；②先通过智能学习获得最优个体，再以最优个体作为K-means聚类的输入量，即最优个体的基因数目就是K-means聚类数目，基因数就是K-means的初始化种子点(初始化聚类中心)，这样既捕获到了聚类数目，又有效避免了种子点随机选择，降低了聚类过程中初始化种子的随机敏感性，这种模式被命名为“G-A-K-Clustering”；③将K-means整合到混合智能学习算法中实现聚类，如基于遗传粒子群的聚类算法、基于遗传蚁群的聚类算法等，这种模式被命名为“Hybird-Clusting”。另外，在基于智能学习的划分聚类实现过程中，可以引入不同的操作模式增强全局学习能力，也可以将局部最优个体传递到下一代繁衍中，保存最优个体继续学习，如引入精英策略保存局部最优个体和融入小生境策略增强全局学习能力等。然而，对于不同的智能学习方法，选择不同的学习过程和聚类模式所产生的聚类效果是不一样的，如当ACO被用于智能学习K-means聚类时，就不使用第二种聚类模式，而是直接应用ACO优化捕获到优秀的聚类中心。
　　通过研究基于智能学习的划分聚类算法(如K-means等)，实现城市GNSS数据(轨迹)聚类，能进一步提高城市状态挖掘能力，获取更好的城市运行和状态趋势信息。为此，以六座城市［北京(Beijing，China)、重庆(Chongqing，China)、美国纽约(New York，USA)、美国旧金山(San Francisco，USA)、意大利罗马(Rome，Italy)、巴西阿拉卡茹(Aracaju，Brazil)[63]］的GNSS数据(出租车GPS数据集)为研究对象(表1-6)，进行实验验证与测试。本书聚焦城市GPS数据(轨迹)聚类及其在城市热点发现中的应用，即主要研究基于智能学习(GA、PSO、ACO)的城市GPS数据(含轨迹聚类)划分聚类算法，具体为：研究三种智能化种群初始化技术，并以真实GNSS数据进行编码；研究GA的局部优化个体保存和全局学习方法，实现遗传自适应方法和遗传模糊系统方法；研究GA与模糊PSO融合方法和GA与模糊ACO融合方法，实现PSO参数和ACO参数模糊化自动获取，避免过多手动设置参数带来的不确定性，提高K-means自动聚类效率。同时，在云计算环境下研究基于MapReduce的自适应遗传K-means自动聚类算法，改进MapReduce的迭代性能，降低或避免MapReduce的迭代运算代价，研究轨迹片段和子轨迹生成方法，避免局部特征信息丢失，实现基于改进型的Fuzzy C-means轨迹片段聚类，减轻GNSS空间特性对聚类结果的影响，最终采用最小二乘方法实现聚类结果回归和标明轨迹片段的聚类中心，从而在回归轨迹沿线发现人口迁移状态、交通运行状态和时空变化情况。
　　本书主要内容凝练如下。
　　(1)提出了基于噪声、密度和K-means++的三种初始化种群技术，用于解决划分聚类的聚类数目难以确定和初始化种子点(聚类中心)难以发现的问题；对基于密度共享小生境的自适应遗传算法进行全局优化，用于解决遗传迭代停滞及早熟现象。
　　(2)利用粒子群与遗传算法优势互补的特点提出了一种模糊粒子群与遗传算法融合的K-means聚类自动学习算法，并依据粒子群与遗传融合特征构建了模糊系统用于融合算法参数自适应生成，提高聚类学习算法对GNSS数据的整体优化能力和收敛效率。
　　(3)结合遗传算法与构建的模糊系统提出了一种新颖的模糊蚁群与遗传融合的划分聚类自动学习算法，实现GNSS数据中的热点发现，解决了初始化种子点敏感和蚁群优化过程中输入参数过多的问题。
　　(4)在云计算环境下，结合改进的Canopy和K-means++提出了基于MapReduce的GNSS数据遗传K-means自动聚类学习算法，有效解决了大体量GNSS数据聚类自主学习问题。
　　(5)提出了一种基于角度划分和角度约束的轨迹片段生成方法，并在此基础上提出一个基于拉格朗日定理的平滑适应度函数，用于确保Fuzzy C-means聚类的稳定性，完成基于最小二乘法的GNSS轨迹生成，实现了一种面向非监督聚类算法的轨迹生成方法。生成的轨迹能用于解释城市人口、车辆移动、交通拥堵以及预测城市运行状态等。
　　1.1 国内外研究进展
　　为了在城市GNSS数据中学习满足需求的隐藏信息，找到适合城市运行的关键信息，从而为城市良好运行、更好地管理城市提供信息参考，许多研究人员展开了广泛的研究，提出了众多基于城市GNSS数据的位置信息模型，用于描述城市状态，解决城市运行过程中遇到的问题[13-27]。文献[13]提出一种基于实时GPS数据的GIS专家系统，通过该系统中道路片段上的车辆速度来监测交通堵塞情况。文献[20]通过出租车GPS数据关键信息提取、地图匹配和最短路径获取等步骤，提出一种基于GPS数据的出租车路径选择行为方法。文献[18]提出一种人们出行需求与交通服务不匹配的可靠分析方法，用于标明城市中出行需求与交通工具严重不匹配的区域。文献[21]以北京市出租车GPS数据为例，提出一种基于GPS轨迹数据的离线挖掘与在线实时监测相结合的异常轨迹监测算法，用于监测出租车运行轨迹。文献[14]根据城市人口增长状态，提出一种城市路网的检测方法，用于发现现有路网尚未覆盖的区域。文献[24]以城市出租车的GPS轨迹数据为基础，提出一种符合“感知—认知—经验”认知规律的时空轨迹融合与路网生成方法。文献[16]以纽约出租车数据为研究对象，根据社会经济活动和人类活动模式(如POI等)提出一种基于大时空城市数据的可视化平台，且允许用户可视化查询出租车路线。文献[27]根据城市路网间的服务功能、相互联系和非欧氏距离事件，以空间核密度估计为基础，提出一种网络空间POI可视化与分析方法。本书主要聚焦基于智能学习的城市GNSS数据划分聚类方法研究，并以应用广泛和有数据量积累的城市出租车GPS数据为例，学习GPS数据中隐藏且有价值的信息，力求有效解决当前智能聚类学习城市GPS数据所面临的挑战，提升和改进聚类效率，并最终将GPS数据研究结果扩展到一种轨迹生成与聚类方法中(第7章)，以更好地发现城市运行动态与趋势。
　　事实上，聚类学习算法是一种重要且有效的非监督机器学习方法，在地球科学[64]、数据挖掘、遥感图像分析处理[65]、模式识别、知识发现、城市社会分析等领域有着广泛的应用。这些非监督聚类算法可以大体分为六类[66-70]。
　　(1)基于划分的聚类算法主要包括典型的K-means、Fuzzy C-means、K- median、K-means++算法。
　　(2)基于密度的聚类算法，一般也包括密度估计算法，如具有噪声的基于密度的聚类方法(density-based spatial clustering of applications with noise，DBSCAN)[71]和对象排序