基于多维度数据建模及空间相似性分析研究

吴斌 张守震

摘 要：高维空间中，数据投影算法难以从高维空间获取信息并将其关联到形象直观的低维空间。面对具有复杂性和动态性特征的高维空间数据挖掘和可视化建模时，理论依据和高效算法有待于更加深入广泛地研究。本文分析研究了低维轨迹数据的可视化理论和方法，实现了轨迹相关的高维轨迹数据的信息挖掘算法和可视化模型。改进基于编辑距离和层次聚类的异常轨迹检测方法，以相似性度量和历史标记数据对轨迹进行段分割，将基于点堆叠的停留点位置和数量的计算方法进行重设计。以此为基础，检测了相似性轨迹的特性，评估了异常轨迹的行为模式，绘制了停留点的地理点图，定义了语义轨迹的挖掘模型;以堆叠轨迹为基础，建立了基于移动对象轨迹的回归高程模型，实现了基于静态可视化和动态可视化的多属性关联分析。

关键词：多维度;数据建模;轨迹挖掘

一、深层语义轨迹数据模型

移动数据的时空和属性聚集方法可以只作用于单个维度，如空间聚集（S）、时间聚集（T）、属性聚集（A），也可作用于多个维度，如时空聚集（SxT）、时间属性聚集（TxA）、空间数据聚集（SxA）和时空厲性聚集（SxTxA），将客种M性定义为“A+”。移动对象轨迹中S、T和A+成分之间的相互关系，即相对于空间和时间的多属性行为。这些行为共同依赖于给定轨迹的特征，并表现出多种相关性：

1）行为搜索。观察A+的异常值，检测分析人员感兴趣的特定行为发生时间或位置，并将它们在S和T中定位。例如某区域在某个时间段出现多个属性值（方向、速度、加速度等）同时异常的情况，则对应区域可能发生了交通事故。㏂

2）行为比较。比较S内不同区域或T内不同间隔或轨迹集T的不同子集的A+的行为。例如，比较春季航线与冬季航线航船的航速行为、载重行为等。㏂

3）行为组合。观察轨迹集的不同子集在S内的相同区域或T内相同间隔同时发生不A+的行为。

二、多目标动态标准规划位置匹配算法

为了匹配大规模的浮动车轨迹数据，本文提出的多标准动态规划地图匹配算法的处理框架如图所示，主要分为5个步骤，分别为路网初始化、车辆轨迹跟踪、备选匹配点生成、备选路径生成以及最优匹配路径选取。为了提高地图匹配过程中最短路径分析算法的计算效率，本文从2个方面改进了传统的最短路径分析算法。首先，利用一个全局路径分析标识避免了标记初始化步骤;另外，使用多起点到一个终点的路径分析过程计算备选匹配路径，避免了重复调用传统的路径分析算法。

（一）单维度点图算法的改进

原始的单维度点图算法有三个限制：（1）该算法通过从最小观测值;移动到最大观测值;（从左到右）生成点图。以类似的方式，也可以通过相反顺序（从右到左）生成点图。这些不同的移动方向在同一批数据上可能产生不同的点图;（2）对称分布的数据可能会导致不对称的点图;（3）由于该算法在单一数值轴上本质上是一维的，因此难以扩展到多维数据。但是，通过一种无向算法可以克服原始点图算法的缺点：避免从最小的观测值（从左到右）或从最大的观测值（从右到左）开始，而是从一个点半径邻域中具有最大领域的数据点开始。以下是该算法的伪代码，可以有效降低点的位置偏差，并将点图扩展到更高维度。㏂

（二）空间扩展的高程模型建立

过去的堆叠可视化模型将一幅2D地图放置在一个虚拟的3D空间，忽略了高程维对轨迹数据带来的影响。然而，在实际用例中，表示三维时空域中的移动对象形成的路径为时空路径，时空路径的空间位置由地面位置和高程共同界定。因此，对轨迹空间的需求分析应在传达时间信息的前提下保持三维地理空间位置的可视化，这对处理三维轨迹集数据的时空可视化技术提出了更高的要求。此外，如果考虑在堆叠轨迹条带的上方体现高程信息，会出现轨迹条带在Z轴上的波动幅度变大，从而导致直观性变差，无法实现轨迹堆叠。

在生成轨迹的高程视图中，由于使用3D场景的透视投影和立体渲染，轨迹点的高度信息很难感知，尤其是用户在观察可视化视图时使用了非立体显示工具。考虑这个因素，在渲染轨迹高程带时基于高程的分带设色，以渐变过渡保证地势起伏的连续性，可以展示出良好的三维可视化效果。㏂

三、最短路径分析优化过程

MDP-MM算法中，调用了FCOSP算法来计算从上一个GPS的备选路径集合及W到当前备选匹配点的备选路径其中具有最优路径评价指标值。在本文中，假设浮动车在连续的两个GPS之间行驶的是具有最短距离的路径，这种假设是合理的，因为连续2个GPS点间的时间间隔是相对较短的，二者之间的距离不会过远，可选路径相对较少，因此选择最短路径的可能性最高。基于这种假设，利用考虑了路网转向限制条件的基于边的Dijkstra算法来计算两个备选匹配点之间的最短路径。

FCGSP过程中路径分析的起点和终点不仅可以是路网节点，也可以在路网边上。在传统Dijkstra算法中，起点和終点只能位于节点上，然而GPS点的备选匹配点可能位于路网边的任意位置。FCGSP过程通过添加虚拟的节点和边到路网中来解决该问题，MDP-MM算法的计算性能如表1所示，在不考虑数据的读写时间时，MDP-MM算法的运行时间为30.7秒，处理速度达5590点/秒，具有很高的计算性能。即使考虑轨迹数据的读写时间，MDP-MM算法在仅使用单CPU的情况下可以在12.6分钟内处理完15分钟的浮动车轨迹数据，表明MDP-MM算法可以实时匹配大规模的浮动车轨迹数据。㏂

四、总结

围绕低维数据在地理空间中构建的轨迹数据模型展开讨论，研究内容主要是：改进了轨迹聚类和异常检测算法并实现了轨迹段的有效检测和行为模式推理、基于MADS的时空数据建模实现了语义轨迹的时空和属性对象丰富、建立了停留点的点堆栈模型以绘制停留点的地理点图、建立了回归高程模型以实现堆叠轨迹的三维特性、设计了属性的动态提取方式，以多个视角挖掘了轨迹数据的行为知识和运动模式等。㏂

参考文献：

[1] 齐佳倩. 基于视频监控数据的人群行为分析和异常轨迹检测[D].北京交通大学，2018.

[2] 吴星. 运动轨迹时空模式挖掘与可视化[D].东华理工大学，2018.

[3] 赵如意. 面向GIS的多维时空可视化Web组件库的开发与应用[D].华东师范大学，2018.

[4] 宋英华. 基于图像处理与遗传算法的视频内容3D可视化浏览系统[D].天津大学，2018.