科创中国
一种轨迹数据中的频繁子轨迹查找方法及装置
成果类型：: 发明专利
发布时间: 2022-10-27 09:48:36
科技成果产业化落地方案
方案提交机构：天津市滨海新区| 门松 | 2022-10-27 13:43:06
本发明适用于数据处理技术领域，提供了一种轨迹数据中的频繁子轨迹查找方法及装置，包括：分离轨迹数据中的空间信息和时间信息；将所述空间信息编码成第一类字符，每个所述第一类字符用于表示一个地理位置；将所述时间信息编码成第二类字符，每个所述第二类字符用于表示一段间隔时间；根据编码成所述第一类字符的所述空间信息和编码成所述第二类字符的所述时间信息，建立广义后缀树；查找所述广义后缀树中的频繁子字符串；将查找出的所述频繁子字符串转换成频繁子轨迹。本发明通过使用较为高效的字符串算法来处理较为复杂的多维数值数据，使得整个频繁子轨迹查找过程的计算复杂度大大降低。
一种轨迹数据中的频繁子轨迹查找方法，其特征在于，包括：分离轨迹数据中的空间信息和时间信息；将所述空间信息编码成第一类字符，每个所述第一类字符用于表示一个地理位置；将所述时间信息编码成第二类字符，每个所述第二类字符用于表示一段间隔时间；根据编码成所述第一类字符的所述空间信息和编码成所述第二类字符的所述时间信息，建立广义后缀树；查找所述广义后缀树中的频繁子字符串；将查找出的所述频繁子字符串转换成频繁子轨迹。
轨迹数据就是时空环境下，通过对一个或者多个移动对象运动过程的采样所获得 的数据信息，包括采样点位置、采样时间、速度等，这些采样点数据信息根据采样先后顺序 构成了轨迹数据。常见的轨迹数据包括车辆行驶轨迹、移动互联网用户的旅行轨迹、移动互 联网用户的签到轨迹，等等，海量的轨迹数据里蕴含着丰富的信息，其频繁子轨迹可以表现 大多数人的行为模式及习惯，或者表现气候的变化规律等。
由于轨迹数据是数值数据，不能直接套用目前已相当成熟的字符串频繁子串的查 找算法来查找轨迹数据中的频繁子轨迹，因此，现有技术中大多直接对轨迹数据进行划分 并聚类，将长度为〇 (η)的轨迹划分为0 (η2)个子轨迹，再对这些子轨迹进行聚类分析来发现 频繁子轨迹，整个过程计算复杂度高，运算时间长。
中国科学院深圳先进技术研究院提升了粤港地区及我国先进制造业和现代服务业的自主创新能力，推动我国自主知识产权新工业的建立，成为国际一流的工业研究院。 深圳先进院目前已初步构建了以科研为主的集科研、教育、产业、资本为一体的微型协同创新生态系统，由九个研究平台，国科大深圳先进技术学院，多个特色产业育成基地、多支产业发展基金、多个具有独立法人资质的新型专业科研机构等组成。开展先进技术研究，促进科技发展。信息、电子、通讯技术研究新材料、新能源技术研究高性能计算、自动化、精密机械研究生物医学与医疗仪器研究相关学历教育、博士后培养与学术交流。
本发明实施例结合了数据挖掘技术、后缀树算法以及非精确匹配，从而实现了较 优的轨迹数据中的频繁子轨迹的查找，通过使用较为高效的字符串算法来处理较为复杂的 多维数值数据，使得整个频繁子轨迹查找过程的计算复杂度大大降低，且合理的聚类方法 也使得本发明实施例对轨迹数据空间信息的聚类划分更加准确。 增加单元，为所述广义后缀树中的每个节点增加一个计数属性，所述计数属性用 于对该节点对应的字符串在所述广义后缀树中出现的次数进行计数.
技术合作
示出了本发明实施例提供的轨迹数据中的频繁子轨迹查找装置的结构框图， 该装置可以用于运行本发明图1至图5实施例所述的轨迹数据中的频繁子轨迹查找方法。为 了便于说明，仅示出了与本实施例相关的部分。以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精 神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。
下载app