一种逐级合并OD流向时空联合聚类算法

现有OD流向聚类多将O点和D点相分离或者将OD流向看作4维空间的数据点进行聚类处理,忽视了流向长度、方向、时间对流向聚类的影响。本文以流向作为研究对象,提出一种基于流向间相似性度的逐级合并OD流向时空联合聚类算法。首先在充分研究OD流向的空间信息和时间信息的基础上,构建合理的OD流向间时空相似性度量方法,对OD流向间的时空相似性进行量化;然后提出逐级合并OD流向聚类策略,优化类簇合并的顺序,以减少层次聚类的时间开销,实现OD流向的时空联合聚类。以成都市的滴滴出行OD数据和纽约市出租车数据为例对本文方法进行了验证,结果表明：① 本算法聚类获得的流向类簇不仅带有空间特征还具备时间特征;② 在不同参数下本方法可以得到不同时空尺度的聚类结果;③ 与现有较高水平的流向聚类算法相对比,本文方法的聚类效果更好。这体现在流向类簇内部的流向之间有着充分的相似性,以及本文方法不仅可以提取出显著的流向类簇,还可以提取出非热点区域之间的流向类簇。本算法顾及空间因素和时间因素,可以通过调整时空相似性度量方法中的时间参数和空间参数以实现不同时空尺度的流向聚类,这使得从不同时空角度研究城市居民出行模式成为可能。本文提出的OD流向时空联合聚类算法从联合时间信息和空间信息的角度获得对运动数据的新见解,有助于合理全面地研究居民的移动模式、区域之间的空间联系、已知出行结构的确定以及出行目的的探索,是后续一系列分析工作的基础。     

基于多密度聚类算法的路网提取

随着GPS等定位系统的迅速发展,使得路网提取有了新的发展方向,然而目前利用浮动车GPS轨迹数据提取路网的方法层出不穷,但是提取效果却并不能尽如人意。本文将基于网格密度因子的多密度聚类算法引入路网提取,通过该方法对疑似特征点进行聚类来提取道路特征点,来构建道路几何网络,并通过对比分析取得了不错的实验结果。     

地图点要素注记自动配置中聚类分组的蚁群算法应用

大规模点要素注记自动配置问题是地图注记的难点之一,主要受限于时间效率和注记配置质量。针对该问题,本文首先提出一种椭圆形多方位多级注记待选方位配置方案,使其参数化、多元化。其次,结合点要素空间分布特征,提出一种以聚类分组的蚁群算法,并讨论和优化核心参数,实现大规模点要素的注记快速配置。实验表明,该算法计算效率明显提升,算法性能稳定。针对注记密度在5%~30%随机分布点要素的地图,其相比传统蚁群算法算法效率提高73.2%;同时,该算法的注记结果质量比传统蚁群算法注记结果质量好,注记适应度提升8.0%。实验采用抚顺县集体土地所有权界址点数据进行验证,结果表明效率提升86.7%,且注记适应度提升14.6%。本算法适用于点要素规模大、点簇疏密变化差异大的点要素注记自动配置问题的快速求解。     

基于MST聚类的空间数据离群挖掘算法

空间离群是指空间邻域中属性特征值明显不同于其他对象的空间对象,空间数据离群挖掘能为人们提供很多有趣的信息,但空间数据具有复杂的拓扑关系、方位关系和度量关系等空间特征,传统的面向事务型数据库的离群挖掘算法并不适用于空间数据库。本文提出了基于MST(Minimum Spanning Tree,最小生成树)聚类的空间数据离群挖掘算法(SOM);有机结合了最小生成树理论与密度的方法,既体现了空间离群的局部特性,又体现了空间离群的孤立程度。该算法通过MST维护空间数据的基本空间结构特征,通过打断MST中最不一致的边形成MST聚类,不仅具有密度的聚类方法能够聚集非球状簇和分布不均的数据集的特点,而且聚类结果不依赖于用户参数的选择,因此,离群挖掘结果更合理。最后,通过实例数据,验证了该算法的有效性,它适用于大规模空间数据集的离群挖掘。     

基于多尺度时空聚类的共享单车潮汐特征挖掘与需求预测研究

当前,我国政府和单车企业多以划定电子围栏停车点的方式进行共享单车的规范化管理,由于单个电子围栏内部单车流入流出的随机性和不确定性较大,以单个围栏为单位进行单车管理的工作量大且不具现实意义。因此,有必要对电子围栏停车点进行聚类划分,实行区域化的管理与调度。基于此,本文提出一种基于时空约束的网络图聚类算法,该算法综合考虑空间因素（地理位置、地理环境特征）和时间因素（历史订单）,只需通过距离阈值设定即可实现电子围栏的多尺度聚类划分,实验分别在3000 m和700 m距离阈值条件下对厦门岛和乌石浦地区电子围栏进行聚类,结果显示该算法不仅能够将具有相似时空特征的电子围栏聚到同一社区簇内,而且能够使得单车流动主要集中在划分后的社区内部;随后,在社区划分基础上进行单车潮汐特征挖掘,能够有效识别和定位单车使用的热点地区;最后,利用长短时记忆神经网络（Long-Short Time Memory network, LSTM）进行单车订单需求预测,结果显示有84%以上社区的预测准确率在85%以上,平均预测准确率为91.301%,预测效果较好,可有效满足单车调度需求。本文研究成果可服务于电子围栏停车点规划与共享单车的区域化管理与调度工作。     

多时间尺度密度聚类算法的案事件分析应用

时空聚类是数据挖掘研究的主要内容之一,在环境保护、疾病预防与控制、犯罪预防与打击等领域具有重要的应用价值。已有的时空聚类方法中,时间“距离”都认为是真实的间隔,而对于具有社会属性的案事件而言,其在不同时间尺度下具有明显的周期性特征,忽略这些特征将很难反映出案事件真实的时空规律。本文综合考虑多时间尺度下的时间属性,构建等效时空邻近域,并借鉴经典的密度聚类算法,提出了多时间尺度等效时空邻近域密度聚类算法（MTS-ESTN DBSCAN）。通过对福州市区2013年案事件数据的聚类分析表明,该方法在案事件时空聚类方面具有可行性,对于进一步深入研究城市犯罪地理具有一定的理论意义和实际价值。     

基于密度的轨迹时空聚类分析

通过轨迹聚类分析挖掘物体移动模式的空间分布和时间特征,对于认识运动的形成机制,预测运动的未来发展具有重要的意义。目前,轨迹聚类研究主要关注物体的空间位置变化,时空聚类中时间约束一般只是作为辅助信息,并不真正参与聚类。本文提出基于密度的轨迹时空聚类方法,在聚类过程中同时考虑轨迹包含的时空信息,在空间聚类的基础上提出了轨迹线段时间距离的度量方法和阈值确定原则,对时空邻域密度进行聚类分析,挖掘物体的时空移动模式。实验对南海涡旋轨迹进行时空聚类分析,得到了涡旋典型移动模式的空间分布和时间特征,验证了基于密度的轨迹时空聚类方法的有效性。加入时间约束后,移动通道主要发生缩短、分裂和消失的变化。和空间聚类相比,轨迹时空聚类可有效地划分发生在同一位置不同时间的轨迹,得到的聚类结果更加细化,移动模式更加准确,有利于物体的移动模式做更深入的分析。     

可视化空间聚类挖掘算法及系统实现

空间聚类与传统聚类方法的区别之一在于空间聚类是对空间实体的集群性进行分析,在聚类过程中需考虑模式在空间分布上的一种或几种结构特征,如模式间的远近关系、拓扑关系、方位关系、疏密关系等。然而,传统聚类算法大多忽略空间结构特征对聚类结果的影响。同时,传统数据挖掘过程往往是“黑箱”作业,用户不论感兴趣与否都只能被动地接受挖掘结果,而且结果往往是抽象的、不易理解的。本文对基于MST的可视化空间数据聚类挖掘算法进行了研究,利用Delaunav三角网和MST最小生成树使得地理实体的邻接度与其他属性数据一起参与了空间聚类处理,同时用J2EE技术开发可视化空间聚类挖掘工具,为此类应用系统的建立提供了一种实用的可行方案。     

基于时间序列聚类方法分析北京出租车出行量的时空特征

受城市资源配置、区域功能分化的影响,城市中居民的出行往往呈现出特定的模式和规律,而这种出行模式的背后反映出城市的功能结构。城市车辆GPS导航的广泛使用,以及车辆轨迹数据的大量获取,为分析城市居民出行模式及理解城市功能结构提供了数据支撑。本文以道路分割城市得到的地块为研究单元,利用北京市一个月的出租车轨迹数据,对北京居民的出行模式及城市功能格局进行分析。在轨迹数据分析中,本文从轨迹数据中提取每个地块的出行量时间序列信息,然后采用结合时间序列距离度量和时间序列自身相关性的聚类方法,对出行量时间序列数据进行聚类分析,从而研究乘客出行的时空分布特征,最后结合北京市POI数据,探讨了不同区域乘客出行规律和区域功能类型的相互关系。结果表明,出租车出行量时间序列模式在工作日和周末间存在明显差异。此外,工作日的2个出行高峰与通常的通勤早晚高峰不同。由出行量所得的区域聚类结构,除具有重要交通枢纽功能的地块外,总体上以市中心为圆心大致呈同心圆分布,且距离市中心越远出行量越小。研究结果对于分析北京市居民出行行为、辅助城市交通规划具有一定的意义。     

基于MapReduce的网格化优化CURE算法的实现

针对CURE算法处理大量数据时聚类速度较慢的问题,一方面采用网格聚类方法对初始聚类对象进行网格预聚类处理,缩短初始化族聚类时间;另一方面采用MapReduce框架对算法进行并行性扩展,使其能够充分利用集群的计算和存储能力,从而加速海量数据的处理。以联合程序开发网站的数据集和MATLAB人工数据集作为测试数据集,对改进算法Grid-CURE进行实验分析。实验结果表明:方法可有效提升处理大数据的效率以及提升其抗噪声能力。     

栅格成本距离计算的改进蚁群算法

栅格数据模型是地理信息科学领域的主要数据模型,成本距离分析是其重要的应用方向之一。但当栅格数据量较大时,传统的Dijkstra求解效率较低,因此本文提出了一种用改进蚁群算法来求解栅格成本距离的方法。首先,构建了适合人工智能算法的栅格数据模型及编码方法;然后,在此基础上初始化蚁群,采用状态概率选择机制计算相邻栅格单元之间距离成本,以及距离成本路径方向选择,同时利用改进的信息素更新机制加强蚁群之间信息交流,加快算法收敛速度;最后,引入了遗传算法的选择、交叉和变异等算子优化生产的成本距离的解,增加解的全局性。本文以北极地区的海冰密集度栅格数据为基础,求解北极地区适合航行路线的成本距离。实验表明,结合了蚁群算法和遗传算法优势的改进蚁群算法,能够快速有效地求解出基于栅格数据的成本距离。     

耦合蚁群算法和SCS-CN水文模型的城市不透水面空间格局优化

近年来,中国城市暴雨内涝频繁发生,已经发展成为一类严重的“城市病”。城市不透水面密度及其空间格局是形成暴雨内涝的一个重要影响因素。本文提出一种耦合蚁群算法和SCS-CN水文模型优化不透水面空间格局的方法,从而实现通过增加地面雨水渗透量达到减缓城市内涝发生的目的。首先应用Williams公式计算基于坡度修正的CN值,在此基础上计算地表径流量;然后设定径流系数最小化目标,耦合水文模型和蚁群算法对径流小区尺度的不透水面空间格局进行优化配置;最后应用景观格局指数对不透水面空间格局进行分析。研究结果表明：面对1年、5年、10年、20年、50年以及100年一遇重现期的1 h持续降雨事件,研究区优化后的不透水面空间格局可以分别减少径流系数21.19%、19.58%、19.38%、18.93%、18.41%和17.25%,在一定程度上缓解城市暴雨内涝的发生。在此基础上,提出面向暴雨内涝防治的城市更新优化措施建议：① 通过增加草地、花园、树木等植被绿化减少高不透水面类型的面积,并划分成更多中高不透水面类型的斑块;② 集聚低、中低等不透水面类型,从而加大连通性,形成更多的中高不透水面类型;③ 增加每个径流小区内斑块数量,增大斑块密度,减少其蔓延度和聚集度。     

一种基于改进蚁群算法与GIS的多约束配送中心选址方法

针对单一指派约束和容量约束的设施选址问题（Single Source Capacitated Facility Location Problem, SSCFLP）,建立了一种基于改进蚁群算法与GIS的配送中心选址方法。构建了以总成本费用最小为目标的配送中心选址模型;提出了适合求解SSCFLP问题的改进双层蚁群算法,将求解过程划分为彼此关联的设施选择层和需求指派层2层蚁群,采用改进的全局信息素更新策略加强双层蚁群交流,并对迭代最优解的指派关系进行局部优化;将方法应用于汽车配送中心的选址,利用GIS工具构建选址空间。实验结果表明,该选址方法能找到质量较好的选址及指派结果,对于求解同类问题具有较强的借鉴意义。