关键词：
图论
移动对象数据
机器学习
深度学习
图神经网络
摘要：
随着空间和时间数据的爆炸性增长,对海量时空数据的分析要求已远超人类的理解能力,由此凸显出对时空知识挖掘技术的需求。时空数据挖掘旨在从大型移动对象数据库中发现未知但可能有价值的模式,在地球科学、交通运输、气象学等各种领域,其应用前景十分广泛。作为构成时空数据的重要组成部分,移动对象数据及其数据挖掘的相关研究工作成为该领域的重要研究方向。然而,由于移动对象数据内在联系的复杂性,传统数据科学技术提取时空模式的有效性较为有限。例如车辆轨迹数据等典型的移动对象数据集,由于同时具有不同性质、不同程度的时间相关性和空间相关性,对该类数据的分析处理与挖掘工作更加具有挑战性。
自1736年莱昂哈德·欧拉提出七桥问题的研究以来,图论作为组合数学的一个分支,因其在现实问题建模的重要作用而经历飞速发展,逐渐成为目前应用数学研究中最重要的领域之一。近现代的图论研究通过图的形式有效地描述许多现实问题,从社交网络的朋友关系,到地铁线路、互联网的结构等等。通过对图论问题的目标函数进行优化求解,可以有效解决很多一般建模方法难以解决的数学问题。在一些经典的图论应用中,图结构通常是预先提供的,其研究重点是分析图数据以挖掘数据的信息模式。但是,在现实应用的场景中,图数据通常是高维、含噪且未明确定义的。因此在算法设计或数据分析之前,应当首先从数据中学习图的结构。
本文以图论与机器学习的相关理论为主线,从图论算法、机器学习算法和图神经网络算法三个方面,论述了移动对象数据预测与分类的研究体系。主要的研究内容与成果如下:
(1)图论与机器学习理论研究
本文研究了图论的基础理论和相关算法、图论中的重要问题、谱图理论以及基于图优化的机器学习模型,系统的阐述相关数据挖掘与分析方法的基础理论知识。主要从以下几个方面进行论述:(1)介绍了图论的基本概念与定义、图的基础矩阵表示和中心性度量;(2)讨论了图的搜索算法、最短路径问题、网络最大流问题等图论的主要问题及其相关算法;(3)阐明了谱图理论的核心思想,介绍了邻接矩阵、度矩阵和拉普拉斯矩阵等图论的表示形式;(4)从图的优化角度阐述了概率模型和概率图模型等机器学习的基础理论,介绍了两者之间的关联性以及对于深度学习的理论意义。
(2)基于图算法与移动对象数据的传播力分析模型
本文阐述了基于图算法的移动对象数据分析方法,讨论了时空数据分析的图构建方法,总结了图中的不同距离度量,比较分析了有效距离与地理距离的区别,并基于有效距离提出了流行强度的传播力分析模型。主要从以下几个方面进行论述:(1)根据空间关系划分,将图构建方法分为地理划分法、语义构建法和格网分割法三个分类,基于空间划分结构可以构建一个用于表示时空关系的时空图结构;(2)基于图结构在时空数据分析中的特殊性(即非欧几里得性质),将图的距离度量分为局部距离度量和全局距离度量两类。分别讨论了不同的局部度量和全局度量方法,并重点阐述了有效距离这一特殊的局部距离度量模型;(3)提出了移动性网络中的移动性预测模型,并基于有效距离提出了流行强度模型,用于分析移动性网络中基于人类移动性的传播力;(4)基于Open Flights全球航班数据集建立了中国省级移动性网络,实时调整客流模型中的干预参数,模拟不同移动性限制级别下的客流量,并通过该交通网络研究了人类移动性限制策略对流行病传播的影响。
(3)基于深度学习的时空轨迹数据分类
本文深入讨论了深度学习技术在移动对象数据分析领域的主要研究方法,并基于深度学习进行了时空数据分类预测的实验研究。主要从以下几个方面进行论述:(1)讨论了深度学习的理论与方法和不同神经网络在时空数据中的应用,以阐明循环神经网络和卷积神经网络对于挖掘时空数据中的时间相关性和空间相关性的重要作用;(2)设计了时空轨迹分类任务的深度学习架构——Deep STTC,提出了用于提取轨迹运动特征的MFEx层结构,并融合了Conv LSTM、LSTM以及MLP等多种神经网络结构;(3)将Deep STTC模型应用于露天煤矿卡车移动轨迹数据的不同运行状态分类问题。通过与多种已有多元分类研究方法的分类效果进行比较,分析了实验方法的优越性。
(4)基于图神经网络的时空轨迹数据分类
本文阐述了图信号处理、浅嵌入式编码等图表示学习的相关理论与方法,深入讨论了图神经网络方法的不同类型与理论基础,基于格网构图和图神经网络方法设计了时空图数据的深度学习架构,并进行了数据分类实验研究。主要从以下几个方面进行论述:(1)详细论述了数字信号处理到图信号处理的演化,作为基于谱域的图神经网络的理论基础;将图表示学习分为浅嵌入法和图神经网络(即深度学习方法),详细讨论了不同图表示学习方法的特点;(2)提出了一种基于格网构图和Graph SAGE方法的时空轨迹数据分类架构——Grid-GNN,将轨迹
欢迎来到三峡大学图书馆！
