基于过程发现和LDA的RFID轨迹数据挖掘方法

冯健文

摘要：射频识别（RFID）技术应用广泛，但移动对象RFID轨迹（RFID-STR）数据挖掘研究较少，不能体现数据的社会和应用价值。针对数据预处理难度大、缺乏有效语义轨迹挖掘方法、知识可视化技术少等问题，结合过程发现、LDA模型、聚类算法、轨迹数据可视化等技术，把RFID-STR数据映射到业务过程模型，提出基于LDA的RFID-STR数据特征知识提取方法，重点阐述RFID-STR数据挖掘方法的轨迹数据预处理、轨迹知识提取和知识可视化阶段。为解决RFID数据的轨迹搜索与分析技术提供新的技术途径。

關键词：RFID;LDA;轨迹挖掘

中图分类号：TP311        文献标识码：A

文章编号：1009-3044（2022）09-0008-03

开放科学（资源服务）标识码（OSID）：<E：＼2022知网文件＼8-9＼9＼1xs202109＼Image＼image1_1.png>

1 引言

物联网、移动互联网技术的飞速发展催生了大量的移动对象时空轨迹（spatio-temporal trajectories，STR）数据，这些数据蕴含了群体对象的泛在移动模式与规律，还揭示了社会演化的内在机理，有重要的社会和应用价值[8]。轨迹数据挖掘已成为数据挖掘领域的一个重要新兴分支，是当前的研究热点[1]。

射频识别（RFID）技术是标识移动对象的主流方式，在金融、物流、地铁、旅游、超市、校园卡、企业卡、运动等领域广泛应用。但相比安装GPS设备的出租车、公交车等轨迹数据研究[2-4]，移动对象RFID轨迹（RFID-STR）数据挖掘的研究相对滞后。一方面，RFID轨迹数据虽有时空序列性，但没有明显的业务流程开始和结束标记，RFID应用业务点间多数没有关联和约束，不同业务点可能存在数据和语义异构，加大了数据预处理的难度;另一方面，特定领域内的移动对象有不同的角色定义、活动环境和语义，现有研究多侧重轨迹挖掘结果，而忽视特定领域的轨迹语义归纳和可视化研究，不能直接应用于RFID-STR数据挖掘，较难从挖掘结果解释用户的行为，影响了分析和应用效果。

近几年，起源于文本处理的狄利克雷分布模型（LDA，latent Dirichlet allocation）凭借提取兴趣主题的多样性和简单性、数据降维、异构数据建模、语义归纳等优点[9]，在手机数据特征提取[5]、出租车轨迹模式[2]、社交数据特征分析[6]、城市功能区分析[7]等语义轨迹挖掘应用取得了较好效果。而过程发现（process discovery）技术已在社会关系挖掘[10]、面向电子邮件的组织结构挖掘[11]和一卡通过程挖掘等非业务流程特征日志数据应用成功使用。把过程发现技术引入RFID-STR数据预处理中，可建立基于时间阀值的数据轨迹分段方法，便于进行业务点的关联分析和用户特征模式挖掘。

因此，本文结合过程发现技术和LDA主题模型理论，提出一种RFID-STR数据挖掘方法，为解决RFID数据的轨迹搜索与分析技术提供新的技术途径。

2 国内外研究现状分析

轨迹挖掘（Trajectory Mining）一直是科学研究热点。高强[12]和许佳捷[1]对轨迹大数据处理关键技术和应用进行综述，表示轨迹数据价值巨大，但研究成果应用还面临挑战，研究工作侧重轨迹数据预处理、轨迹数据挖掘、数据可视化和隐私信息保护。

在数据预处理方面，主要研究数据清洗、轨迹压缩、轨迹分段、路网匹配、轨迹数据模型和语义轨迹等。轨迹分段是对长时段轨迹的切分与标注，可降低计算复杂度，提供丰富的语义，是预处理的重点研究问题。主流方法有基于时间阀值、几何拓扑和轨迹语义策略。Zheng利用轨迹数据学习获得停留点对轨迹分段，从而获得热门旅游景点区域[13]。曹卫权提出了一种基于“极大稳定分段阈值”的时空模式挖掘方法解决单一、固定的分段粒度问题[14]。孙艳在RFID物流跟踪系统中，采用基于最小描述长度（MDL）的方法把轨迹划分成若干coarse分段，然后按照划分的基本单位将分段进一步划分为fine分段 [17]。对于时间阀值的使用多根据业务场景主观确定，这种方法对于有明显开始结束节点的轨迹数据适用，但对于RFID中非业务过程特征的数据较难使用，目前研究较少。

过程发现是业务流程管理（BPM）领域挖掘的重要方法，目标是从事件记录中提取反映业务流程特征和知识。随着研究工作的深入，IEEE成立了过程挖掘工作组（ITFPM，http：//www.win.tue.nl/ieeetfpm）。目前，过程发现技术已进入云服务挖掘、业务流程大数据挖掘、用户网络行为轨迹挖掘等领域。

轨迹数据挖掘即知识提取，主要包括模式挖掘和语义分类两种。模式挖掘侧重轨迹路径，研究成果较多，但不易解释用户行为。语义分类则同时关注路径和语义，是新兴研究分支，受到广泛关注。主要方法有动态贝叶斯网络、隐马儿可夫模型、条件随机场、高斯混合模型、主题模型、聚类等。Nascimento和Sun提出了改进的隐马儿可夫模型，处理人类活动认知[16，17]。Santos提出使用动态贝叶斯网络作为分类器推理[18]。LDA主题模型是文档分析重要的模型，本质上是一种贝叶斯网络，近年开始应用与用户特征提取和语义轨迹分类。Ferrari应用LDA模型从社交位置数据提取城市日常活动模式[6]。Chu采用一种基于LDA主题模型的语义转换方法，出租车行驶轨迹作为文档，经过的街道名字作为单词，映射GPS坐标为轨迹数据，提取出租车行驶轨迹特征[2]。蔡文学通过LDA模型分析出租车轨迹得到热门城市区域，有效解释用户行为[19]。虽然现有的LDA模型轨迹分类应用取得了较好效果，但是很少面向RFID轨迹数据，非业务特征轨迹数据分析鲜见，因此相关研究需要更多探索。

轨迹可视化技术可帮助用户理解挖掘结果，受到研究者和应用市场的关注。Wang介绍了直接可视化、抽象可视化和特征提取可视化三种可视化方法[20]。直接可视化适用于固定数据格式且数据量不大。Bakshev介绍一种三维语义框架，实现轨迹数据展示和语义注释[21]。抽象可视化可展示时空属性和移动对象属性特征。Li基于时间维度对历史气候变化数据可视化[22]。特征可视化需要研究人员预先提取特定轨迹数据集。Lu预先将出租车数据匹配路网，分析热门路径集合，可视化显示最优路径[23]。虽然目前研究很多，但轨迹数据種类众多，应用环境不同造成处理方法不一样，面向RFID轨迹数据的可视化研究还不多。

根据上述分析，目前面向RFID领域的轨迹挖掘研究不多，现有的算法和技术需更多的改进。

3 RFID-STR数据定义

RFID-STR数据定义为T={p|i=1…N}，其中轨迹点p=（R，B，X，t）为四元组，包括RFID标签R、业务点B、属性信息X、时间戳t。业务点包含业务点的地理空间信息、业务类型等。属性信息包含交易金额、经手人、交易内容等。

RFID-STR数据分段目标是得到在一个时间区间的轨迹点集合。因此寻找分段点就是通过时间阀值参数来划分轨迹点集合。下面把RFID-STR数据映射到业务过程模型中，业务活动是RFID业务点，活动的执行事件是RFID标签在业务点的一次操作行为，即轨迹点P。同个RFID标签在时间区间的轨迹点形成了一个业务过程，即轨迹点序列P…P。基于过程发现的轨迹分段方法是从轨迹数据中寻找同个RFID标签的轨迹点序列集合，集合中任意两个轨迹点的时间戳距离满足时间阀值的要求。

4 基于LDA主题模型的RFID-STR数据特征知识提取方法

建立语义轨迹与文本描述之间的映射关系，通过RFID应用领域“语义轨迹-主题-应用标签”到LDA“用户-主题-单词”三层贝叶斯模型的语义转换，最后通过模型的生成实现轨迹特征知识的提取，主要分为三个步骤：

（1）建立应用标签的词袋模型

RFID应用标签对应单词，是从RFID应用业务名称文本集合中提取出词频大于某个阀值的业务名称集合;主题采用主题重要度确定，即轨迹出现次数;将语义轨迹看作为文档，轨迹中涉及多个RFID应用主题区域，好比文档包含多个主题，这样轨迹集合类比文档集合，对轨迹集合进行主题推断，就可以得到多个主题区域，而这些主题区域通过应用标签来表示，所以反映了语义轨迹的特征知识。

词袋模型采用了业务点重要度衡量，业务点重要度指应用标签单词在某个语义轨迹中出现的次数，次数越高说明该单词越能代表该语义轨迹特征。在校园卡RFID应用中，考虑业务点太多，采用业务点类型与校区结合的方式定义应用标签类。采用单个业务点刷卡次数与LDA模型的词频对应，通过打分机制提高单词的文档代表性。一个业务点在所有主题中出现概率为1。设置一个阀值筛选主题中的业务点。

（2）建立主题特征模型

在RFID应用领域，根据LDA主题模型，得到公式（1）：

P（标签|轨迹）=P（标签|主题）×P（主题|轨迹）     （1）

每个轨迹与N个主题的一个多项分布θ对应，每个主题又与M个标签的一个多项分布[ϑ]对应，因此LDA模型求解如图1所示，首先要求解与θ和ϑ参数相关的狄利克雷先验分布参数α和β，然后推理出θ和ϑ参数，最后使用Gibbs抽样法求出轨迹在主题上的分布和主题在标签上的分布，就能得到轨迹与标签的分布。

（3）轨迹特征聚类

在得到轨迹与主题的相关度后，采用主流的K-means等聚类算法将具有相近主题特征的轨迹聚集，形成代表性轨迹。

5 RFID-STR数据挖掘方法

该方法分为数据预处理、轨迹知识提取、知识可视化三大阶段：

（1）数据预处理阶段：生成校准轨迹、数据库轨迹和语义轨迹

首先从分布式环境中抽取RFID移动对象原始轨迹数据，原始数据主要包含标签和业务点的特征数据、交易数据和属性数据;然后经过数据清洗后，采用基于时间阀值的过程发现技术进行轨迹分段，并通过路网匹配方法关联轨迹与业务点地理位置信息，从而得到校准轨迹;接着采用Petri-net建立轨迹数据模型，利用Petri-net理论的特性对轨迹进行形式化验证，根据业务点类型进行轨迹压缩得到数据库轨迹，提高数据价值密度和存取效率;最后根据移动性和行为理解方法建立不同主题的轨迹数据仓库和集市，得到的语义轨迹作为知识提取阶段的输入。

（2）轨迹知识提取阶段：基于LDA主题模型提取特征知识

首先通过分析RFID业务点特征来定义应用类型标签，标签作为单词集;接着基于使用次数或交易金额等语义打分机制建立词袋模型，语义轨迹作为文档;然后利用LDA主题模型的文本相似度分析方法和聚类算法，得到语义轨迹与主题、主题与应用类型标签的特征知识。

（3）知识可视化阶段：建立交互式和抽象式的知识可视化展示

首先建立交互参数与轨迹特征知识的关联模型，然后根据时空和其他属性语义进行抽象化表示与处理，最终通过交互式的主题地图、业务云图、层次气泡图、泰森多边形树图等可视化技术展示，并结合领域知识进行分析总结。

① 主题地图：时空维度结合属性特征，在地形图上显示主题和轨迹的分布情况，通过颜色和透明度显示不同主题，度量指标包括业务点重要度和熵信息。

② 业务云图：展示业务点间的关系。基于业务点重要度。采用折线表示业务点在不同主题上的概率分布。不同业务点根据余弦相似度决定是否聚集显示。

③ 主题变化图：支持交互式可视化，在不同时间窗口度量下，轨迹主题的变化采用相似度衡量。相似度基于每个主题中高于阀值的业务点集合。可观察到主题的出现和消失情况。

④ 层次气泡图：以分层嵌套气泡方式展示轨迹、主题和应用标签，以及移动对象属性特征的关联;

⑤ 泰森多边形树图：采用任意形状的多边形代表不同的轨迹聚类结果，适合移动设备。

6 结束语

在移动互联网、LBS技术、物联网技术高速发展的背景下，社会对轨迹数据挖掘的需求逐渐增多，目前GPS数据轨迹挖掘研究较多，RFID轨迹挖掘研究较少，本文针对RFID应用领域业务需求和轨迹数据特征，提出了采用过程发现技术进行非业务过程特征数据轨迹分段的新方法，实现移动对象轨迹与业务过程模型的映射转换，为轨迹数据预处理提供了新技术，并提出了基于语义的RFID-STR数据挖掘方法，注重业务需求和语义归纳，涵盖了数据预处理、知识提取、知识可视化完整的生命周期。下一步将选取公开测试数据集（签到数据）和真实测试数据集（校园卡）进行方法应用。

参考文献：

[1] 许佳捷，郑凯，池明旻，等.轨迹大数据：数据、应用与技术现状[J].通信学报，2015，36（12）：97-105.

[2] Chu D， Sheets D A， Zhao Y， et al. Visualizing Hidden Themes of Taxi Movement with Semantic Transformation[C]. Visualization Symposium. IEEE， 2014：137-144.

[3] 齐观德， 潘遥， 李石坚，等. 基于出租车轨迹数据挖掘的乘客候车时间预测[J]. 软件学报，2013，24（2）：14-23.

[4] 马连韬，王亚沙，彭广举，等.基于公交车轨迹数据的道路GPS环境友好性评估[J].计算机研究与发展，2016，53（12）：2694-2707.

[5] 张宏鑫， 盛风帆， 徐沛原，等. 基于移动终端日志数据的人群特征可视化[J]. 软件学报， 2016（5）：1174-1187.

[6] Ferrari L， Rosi A， Mamei M， et al. Extracting urban patterns from location-based social networks[C]// ACM Sigspatial International Workshop on Location-Based Social Networks. ACM， 2011：9-16.

[7] Yuan J， Zheng Y， Xie X. Discovering regions of different functions in a city using human mobility and POIs[C]// ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM， 2012：186-194.

[8] 袁冠. 移動对象轨迹数据挖掘方法研究[D]. 中国矿业大学， 2012.

[9] 王丹. 基于主题模型的用户画像提取算法研究[D]. 北京工业大学， 2016.

[10] Sahlabadi， M.， Muniyandi， R. C.， & Shukur， Z.  Detecting abnormal behavior in social network websites by using a process mining technique[J]. Journal of Computer Science， 2014： 393-402.

[11] Soares D C， Santoro F M， Baião F A. eMail Mining： Knowledge intensive process discovery through e-mails[C]// IEEE， International Conference on Computer Supported Cooperative Work in Design. IEEE， 2012：228-235.

[12] 高强， 张凤荔， 王瑞锦，等. 轨迹大数据：数据处理关键技术研究综述[J]. 软件学报， 2017， 28（4）：34.

[13] Zheng Y， Xie X. Learning travel recommendations from user-generated GPS traces[J]. ACM Trans. On Intelligent System & Technology， 2011，2（1）：389-396.

[14] 曹卫权，  褚衍杰，  贺亮.  基于自适应分段粒度的时空模式挖掘方法.计算机应用研究[J]， 2018， 35（3）：5.

[15] 孙艳. 面向RFID海量数据的图挖掘技术研究[D]. 扬州大学， 2011.

[16] Nascimento J C， Figueiredo M， Marques J S. Trajectory classification using switched dynamical hidden Markov models[J]. IEEE Transactions on Image Processing A Publication of the IEEE Signal Processing Society， 2010， 19（5）：1338-48.

[17] Sun S， Zhao J， Gao Q. Modeling and recognizing human trajectories with beta process hidden Markov models[J]. Pattern Recognition， 2015， 48（8）：2407-2417.

[18] Santos L， Khoshhal K， Dias J. Trajectory-based human action segmentation[J]. Pattern Recognition， 2015， 48（2）：568-579.

[19] 蔡文学， 萧超武， 黄晓宇. 基于LDA的用户轨迹分析[J]. 计算机应用与软件， 2015， 32（5）：307-309.

[20] Wang Z， Yuan X， University P. Visual Analysis of Trajectory Data[J]. Journal of Computer-Aided Design & Computer Graphics， 2015， 27（1）：9-25.

[21] Bakshev S， Spinsanti L， Vidal C， et al. Trajectory Semantic Visualization[C]// Iceis 2011 - Proceedings of the， International Conference on Enterprise Information Systems， Volume 1， Beijing， China， 8-11 June. DBLP， 2011：326-332.

[22] Li J， Zhang K， Meng Z P. Vismate： Interactive visual analysis of station-based observation data on climate changes[C]// Visual Analytics Science and Technology. IEEE， 2014：133-142.

[23] Lu M， Lai C， Ye T， et al. Visual analysis of route choice behaviour based on GPS trajectories[C]// Visual Analytics Science and Technology. IEEE， 2015：203-204.

【通聯编辑：王力】