TKSPC：轨迹数据中带约束的Top-k连续序列模式挖掘

《Neurocomputing》：TKSPC: Constrained top-k contiguous sequential pattern mining in trajectory data

　　摘要序列模式挖掘（SPM）是一种在数据挖掘领域成熟且应用广泛的技术。特别是，轨迹数据的序列模式挖掘因其在移动性分析、城市规划和基于位置的服务中的关键作用而受到越来越多的关注。然而，由于轨迹数据规模庞大且性质复杂，挖掘轨迹数据带来了独特的挑战，需要专门的策略来提取简洁且可解释的模式。尽管现有方法（如闭合和最大序列模式挖掘）旨在减少冗余模式，但它们仍难以应对由轨迹数据固有特征导致的过度冗余问题。此外，在序列模式挖掘算法中调整最小支持度阈值以获取有意义的模式仍是一个非平凡且劳动密集的过程。为应对这些挑战，我们提出了TKSPC（带最小长度约束的Top-连续序列模式挖掘），这是一种高效的方法，通过优化垂直数据库表示并结合邻接可达性来强制模式连续性，从而增强传统序列模式挖掘。大量实验表明，TKSPC在执行时间和内存效率上均优于基线方法。此外，TKSPC生成的模式更紧凑且语义更明确，使其在轨迹数据分析中尤为有效。引言大规模全球定位系统（GPS）的发展产生了海量的空间轨迹数据，这些数据展示了包括个人、车辆和动物在内的各类实体的移动模式。物体的运动可以通过捕获其地理坐标（包括经纬度）以及每个记录位置对应的时间戳来监测。在此背景下，轨迹被定义为按顺序排列的空间坐标集合，每个坐标与其相应的时间标记配对。空间轨迹通常由一系列按时间顺序排列的点表示，例如，其中每个点包含一组地理坐标和一个时间戳，如[45]。轨迹数据挖掘利用这些轨迹中蕴含的宝贵信息，广泛应用于各个领域。例如，移动对象的状态表示[5]、社会关系发现[10]、地点或区域的交通流量表示[26]、区域间相关性发现[15]、社会事件的检测与识别[44]、交通状态估计[34]、交通预测[25]、路段关键性分析[3]等。本研究聚焦于利用序列模式挖掘（SPM）从车辆轨迹中提取知识。序列模式挖掘的概念最初由Agrawal和Srikant[1]提出。序列模式挖掘从序列数据库中提取频繁子序列，其中每个序列由有序元素组成（每个元素包含一个项集）。给定用户指定的最小支持度阈值，序列模式挖掘识别所有出现频率在数据库中达到或超过该阈值的统计显著子序列。轨迹数据的序列模式挖掘已成为一个重要的研究领域，吸引了计算机科学、交通运输、社会学和地理学等不同领域的关注。特别是，从车辆轨迹数据中挖掘序列模式在理解、分析和预测交通状况方面发挥着关键作用。序列模式挖掘要求输入序列由有序的离散元素组成。然而，轨迹通常是连续的，并非固有离散，往往由受到空间噪声和不确定性影响的地理坐标组成[11]。许多研究人员致力于缓解轨迹数据在提取和传输过程中出现的低质量问题。当前方法采用学习技术来提高数据质量，在有效性和效率方面均取得了显著改进[8], [29], [31]。轨迹离散化方法主要有三类：基于密度的方法[9]、基于网格的方法[37]和地图匹配方法[27]。基于密度的方法采用聚类技术将对应同一位置的轨迹点分组为一个簇。因此，原始轨迹数据从点序列转换为簇标识序列。簇的总数以及每个簇内轨迹点的分布并非预先确定，而是取决于轨迹中的点基于其密度如何分组。每个簇代表一个有意义的聚集点。整个研究区域通过聚类方法划分为若干个聚集点，利用基于密度的分割方法可以通过序列模式挖掘发现区域间的移动模式。基于网格的方法是将整个城市或包含所有轨迹数据的任何空间，根据用户定义的单元格大小划分为若干单元格，每个单元格代表一个具有唯一ID的子区域。轨迹被映射到网格图上，因此原始轨迹从点转换为单元格ID[6]。Karsoum等人对两种轨迹分割方法（基于密度和基于网格）在序列模式发现背景下进行了比较分析[24]。对于给定的路网，轨迹点可以使用地图匹配算法映射到路段上。然后，轨迹由一系列路段ID表示[38]。轨迹点被映射到实际路段，这可以更好地反映车辆在交通系统中的运行过程。地图匹配广泛用于交通状态分析与预测、城市规划、路线规划和交通管理。地图匹配长期以来一直是交通运输领域的研究热点。近年来，研究人员采用深度学习技术提高匹配性能，取得了令人鼓舞的结果[14], [22], [23]。本研究基于地图匹配后的离散轨迹数据研究轨迹数据的序列模式挖掘。序列模式挖掘是分析轨迹数据和提取有意义模式的广泛使用技术。轨迹数据的庞大规模和复杂性质使其区别于传统的交易数据，需要通过序列模式挖掘使用专门方法来提取清晰简洁的模式。传统序列模式挖掘算法直接应用于车辆轨迹数据时表现出若干局限性。首先，获取有意义模式的最小支持度仍是一个非平凡且劳动密集的过程。最小支持度在序列模式挖掘中呈现关键权衡。当设置过低时，算法计算效率低下并产生大量难以管理的模式；而过高的值可能导致结果不足甚至为空，从而丢失潜在有价值的洞察。其次，轨迹数据表现出区别于传统序列数据的独特特征。具体而言，车辆不能同时出现在多个位置（空间排他性）这一固有物理约束使得传统序列模式挖掘算法存在潜在优化空间，以提高计算效率。第三，使用传统序列模式挖掘方法从轨迹数据中提取的模式往往语义不清晰，缺乏可解释性。这些关键局限性显著阻碍了现有算法在实际智能交通系统中的应用。为应对这些挑战，我们提出了带最小长度约束的Top-连续序列模式挖掘（TKSPC），这是一种高效方法，通过优化垂直数据库表示（基于SPAM [2]）并结合邻接可达性来强制模式连续性，从而增强传统序列模式挖掘。TKSPC能够准确高效地从轨迹数据中发现序列模式，同时考虑路网中的邻接可达性和模式的解释性。本工作的贡献如下：1. 一种针对轨迹数据的新型约束Top-连续序列模式模型。该模型消除了传统序列模式挖掘所需的最小支持度人工调整，抑制了琐碎片段，并从轨迹数据中提取语义上有意义的移动模式。2. 一种为轨迹数据重新设计的内存高效垂直表示。传统垂直表示（例如SPAM或TKS中使用的）假设项集包含多个项，这在应用于每个项集恰好包含一个项的轨迹数据时会导致严重的内存膨胀。为此，我们针对包含个不同路段和条序列的数据库，存储个长度为的位向量，其中每个位指示对应项是否出现在该序列中。3. 基于路网图论导出的邻接可达性图（AMap）。基于路网的有向图模型（第3.1节），我们为每个路段预计算其相邻可达项集合，即可以合法跟随其出现的项。候选生成因此严格限制在这个小集合内，与传统序列模式挖掘中任何频繁项都可能被视为候选相比，大大缩减了搜索空间。4. 在五个真实世界城市数据集上进行全面实验验证。我们将TKSPC从真实轨迹数据中挖掘出的模式可视化在实际路网上，从而为识别关键路段提供基础。此外，我们还将我们的方法（TKSPC）与两种最先进的基线方法（TKS和TSP）在三个关键指标上进行比较：模式质量、执行效率（运行时间）和内存消耗。实验结果显示，在评估的所有方面，TKSPC均持续优于基线方法。本文其余部分结构如下：第2节回顾了轨迹数据序列模式挖掘的相关工作，指出现有方法中的关键空白。第3节正式定义关键概念和问题表述，引入使我们框架区别于传统序列模式挖掘方法的新命题。第4节介绍TKSPC模型、为轨迹数据量身定制的改进垂直表示，以及使用相邻可达项的连续性引导候选生成，并附上支持这些优化策略正确性和效率的关键定理。第5节详细描述所提出的方法。第6节使用真实世界轨迹数据集进行全面实验评估，并与多种性能指标下的最先进方法进行基准比较。最后，第7节总结重要贡献，并概述轨迹模式挖掘未来研究的有前景方向。章节片段相关工作本节系统回顾了轨迹数据分析中序列模式挖掘的最新进展，重点关注三个关键领域：（1）轨迹数据上的序列模式挖掘，（2）Top-序列模式挖掘，以及（3）带约束的序列模式挖掘。预备知识与问题定义在本节中，我们首先引入路网的图论建模，作为定义项可达性和连续移动的基础。然后我们给出必要的定义并表述挖掘任务。TKSPC算法本文提出了一种名为TKSPC的轨迹序列模式挖掘新模型。TKSPC重新设计了轨迹数据的垂直数据库表示，用于存储、挖掘和模式扩展，并利用邻接可达性来强制连续性约束。此外，基于所提出的优化策略，我们推导出一组定理，保证剪枝和候选生成的正确性，从而在保持模式质量的同时加速挖掘过程。TKSPC的实现该算法接收序列数据库（SDB）以及参数和作为输入。它从SDB中生成满足约束的Top-连续序列模式集合。在TKSPC算法中，模式挖掘过程通过使用多种策略进行优化，这些策略有助于提高效率并确保只考虑最有希望的模式。一些策略借鉴自TKS（Top-序列模式）算法[16]。额外的优化已在实验部分进行验证。实验为了验证TKSPC的性能，我们在配备Intel(R) Core(TM) i9-10885 H CPU @ 2.40 GHz、运行Windows 10、32 GB RAM的计算机上进行了一系列实验。实验目的是评估TKSPC的有效性，并将其与两种基准算法进行比较：TKS（Top-序列模式）[16]和TSP（带剪枝的Top-序列模式）[35]，两者都是Top-序列模式挖掘的最先进算法。三种算法均...结论在这项工作中，我们提出了TKSPC，一种从轨迹数据中挖掘有意义序列模式的高效算法。通过引入数据表示、候选生成和支持度计算方面的优化，TKSPC相较于传统Top-序列模式挖掘方法在执行时间和内存效率上取得了显著改进。连续约束和要求的结合确保了发现的模式不仅频繁，而且...CRediT作者贡献声明Jianfeng Hou：写作 – 审阅与编辑，写作 – 原稿，可视化，验证，监督，软件，资源，项目管理，方法学，调查，资金获取，形式分析，数据管理，概念化。Wei Song：概念化。Yu Zhang：可视化。Shengmou Yang：写作 – 审阅与编辑。利益冲突声明作者声明，他们不存在任何已知的、可能影响本论文报告工作的竞争性经济利益或个人关系。Jianfeng Hou目前在北方工业大学人工智能与计算机科学学院攻读博士学位，中国北京。研究方向包括数据挖掘和知识发现。Jianfeng Hou|Wei Song|Yu Zhang|Shengmou Yang