基于過程發現和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.

【通聯編輯：王力】