基于RFID的電動車運行軌跡頻繁模式挖掘算法研究

鄢團軍，呂 軍，齊國強

（浙江?？悼萍加邢薰荆憬?杭州 310012）

0 引言

射頻識別即RFID（Radio Frequency Identification）技術，是自動識別技術在無線電技術方面的具體應用與發展，其利用射頻信號通過空間耦合實現無接觸信息傳遞，并通過所傳遞的信息識別目標[1]，無需識別系統與特定目標之間建立機械或光學接觸。該技術已被廣泛應用于安防、倉儲、物流、追溯、防偽、旅游、醫療、教育等不同領域。

運用有源RFID技術，構建射頻網，管控網內所有的電動自行車，可以實現車輛被盜能及時發現，及時尋回。電動車防盜系統也可以對車主在通勤中的違章情況進行善意提示，逐步提高車主交通安全意識。該系統對于建設智慧城市、提升城市公共服務質量具有較為深遠的意義。

在系統運行過程中，會累積海量的過車數據，將過車數據按時間和空間維度表示，可以形成車輛的運行軌跡。在大量的車輛位置和運行軌跡數據背后，隱含了豐富的空間結構信息和用戶行為規律。對這些信息進行深入的挖掘，不僅可以發現個體用戶的日常行為規律和群體用戶的共性行為特征，甚至還有可能掌握他們的社交關系信息，這對城市規劃、智能交通甚至廣告推薦等應用都具有非常重要的意義。

本文首先描述有關軌跡數據的來源及結構，然后給出頻繁軌跡相關定義，最后提出基于帶權無環圖計算頻繁軌跡的方法并驗證可行性。

1 相關研究綜述

軌跡數據挖掘是從大量的軌跡數據集里發現隱藏在數據背后、用戶感興趣且未知的信息。軌跡數據通常包含空間信息和時間信息，在進行軌跡數據挖掘時，通過對序列模式或位置序列增加時間維度的方法，將序列模式擴展成軌跡模式。

Agrawal[2]等首先介紹了序列模式挖掘問題，序列模式挖掘是找出所有的頻繁子序列。Giannotti[3]給出了時間約束、滑動時間窗口、用戶分類與序列模式挖掘相關的定義，并提出了一種基于先驗的改進 算 法 GSP （Generalized Sequential Patterns）。Mannila[4]等提出了一個事件序列中頻繁片斷的挖掘問題，認為片斷實質上是由一組事件組成的無環圖，無環圖的邊表示事件發生的先后關系，該文沒有考慮時間間隔的限制。Lu[5]等認為事物間的關聯規則是一種隱含規則，其是完全受時間間隔限制的有序事件片斷。Han[6]等開發了一種針對周期模式的頻繁模式挖掘方法用于挖掘頻繁最大模式，頻繁最大模式中的每種模式滿足固定的周期和固定的序列集及支持度。以上所有方法在挖掘序列模式和時間相關的頻繁序列模式時均是類APRIORI[7]算法，如先驗原理認為在關聯挖掘中，候選集和測試范例生成時，任何非頻繁模式的超模式都不可能是頻繁的[8]。典型的APRIORI序列模式挖掘方法，如軌跡模式挖掘[3]，采用了多遍、候選生成和測試的方法。

軌跡的頻繁模式挖掘可以形式化為頻繁序列挖掘[9]，而軌跡數據頻繁模式相比頻繁序列，增加了空間維度、時間維度和語義維度[10]，所以簡單地采用傳統序列挖掘方法無法有效解決軌跡頻繁模式挖掘問題。

Lu[5]等提出了用時空模式表示總體移動行為，稱為軌跡模式，以描述個體的移動軌跡，這些軌跡具有相似移動時間和相同位置序列的屬性。因此，有2個核心概念：第一，給定空間中的感興趣區域；第二，移動對象從區域到區域的移動時間。在該方法中，軌跡模式是一系列空間區域的集合，這些空間區域是移動對象頻繁地按特定順序經過位置的集合。

Luo[11]等研究了一種基于時間周期的最頻繁路徑查詢問題，主要目標是分析和研究大多數行人最頻繁的道路選擇情況，為了避免路徑邊數和非頻繁路徑對挖掘結果的影響，采用序列形式描述路徑頻數。Zhang[10]提出時空軌跡的細粒度序列模式挖掘問題，認為在連續空間中的位置點不適合進行序列模式挖掘，而由相同語義的位置點構成的區域更合適，故將位置的語義維度連同空間和時間維度一同加入到細粒度序列模式挖掘中。

2 軌跡數據的形式

根據采集移動對象移動數據不同的技術方法，軌跡數據有不同的形式。Spinsanti[12]等將軌跡數據分成基于差分GPS（全球定位系統）、GSM（全球移動通信系統）以及基于地理社交網絡的軌跡數據。Pelekisan[13]等增加了另外2種形式：基于RFID和基于Wi-Fi的數據?；贕PS的數據由被采集對象攜帶的具有GPS功能的設備記錄時間有序的地理坐標序列組成；基于GSM的軌跡數據，由按時間順序通過GSM基站單元的標識符組成；基于地理社交網絡的軌跡數據，是通過互聯網上的內容媒體和地理坐標附加而成；基于RFID的數據由一系列移動對象通過的RFID閱讀器的標識符組成；基于Wi-Fi的數據是一系列與之通信的接入點標識符。

本文以有源RFID防盜系統記錄移動對象通過基站的序列來表示軌跡。對路網環境下的車輛運行軌跡而言，路口被當作是軌跡分段的劃分點[14]，一段沒有分岔的道路是一個軌跡分段的最小單位。本系統采用基于路網的關鍵點采樣，通過控制有源RFID讀寫器（后文稱基站）的采集范圍來實現基站與基站間采集范圍不重疊的同時，道路路口不留信號死角。如圖1所示，若目標O經過路口A，被基站d1采集，系統認為O的位置在A附近，然后，若目標O被基站d3采集到，則可認為O的行動軌跡為從A到C。

圖1 基站信號范圍及部署節點示意圖

電動自行車（后文稱車輛）附著有射頻標簽，該射頻標簽的編號視為該車輛身份唯一標識，車輛進入射頻網后，系統可以對車輛進行定位并記錄車輛移動軌跡，如圖2所示。

3 基于帶權無環圖的頻繁軌跡挖掘算法

在城市道路環境下，軌跡數據無法離開道路，故兩者必然匹配。理論上，車輛移動產生的軌跡數據根據采集頻率，會產生大量的位置點數據。由于相鄰的位置點冗余度較大，需要對原始的軌跡進行近似化表示[15]，一方面對挖掘效果無影響，另一方面提升計算的執行效率。本系統將軌跡點序列根據道路實際情況，近似地用線段序列來表示。

3.1 軌跡定義

定義1：軌跡點

車輛運動過程中在時間空間域中的坐標d=（x，y，t），其中（x，y）為空間坐標。 本文以有源 RFID防盜系統記錄移動對象通過基站的序列來表示軌跡，所以軌跡點與RFID基站位置信息等價，t為車輛經過空間點（x，y）的時刻。

定義2：軌跡

車輛 Oi在時間區間Δt內，經過的軌跡點序列集合，表示為 D（Oi，Δt）=｛d0，d1，d2，…，dn｝，其中 di表示軌跡點，即 di=（xi，yi，ti）。

定義3：軌跡邊序列

軌跡邊是通過對軌跡點變換得來，表示車輛所經過的路徑 E（Oi，Δt）=｛e0，e1，e2，…，en｝，其中 ei表示為[（xi-1，yi-1，ti-1），（xi，yi，ti）]，是從軌跡點 di-1到軌跡點di的路徑。本文不考慮從di-1到di的軌跡邊與從di到di-1的軌跡邊的差異，認為兩者的意義相同。

定義4：子軌跡

給定Oi某一時間區間Δt內的運行軌跡D（Oi，Δt）=｛d0，d1，d2，…，dn｝，按時間先后順序取其中一部分連續基站組成的有序集合 D（Oi，Δt′）=｛dk，dk+1，…，dk+m｝，其中 k＞0，k+m≤n，則 D（Oi，Δt′）是軌跡 D（Oi，Δt）的子軌跡，記作 D（Oi，Δt′）?D（Oi，Δt），顯然子軌跡 D（Oi，Δt′）經過的時間區間 Δt′是 Δt的子區間。

定義5：軌跡長度

軌跡包中軌跡點的個數。 如 D（Oi，Δt）=｛d0，d1，d2，…，dn｝的軌跡長度 l=n。

定義6：軌跡頻次

圖2 電動自行車運行軌跡

在給定的軌跡集合 S=｛D1，D2，…，Dn｝中，含有子軌跡 Dsub的軌跡的個數，記作 ｜｛D ｜Dsub?D，D?S｝ ｜。

定義7：軌跡頻繁模式挖掘

給定 Oi的軌跡集合 S=｛D1，D2，…，Dn｝和最小支持度 Supportmin，Supportmin?[0，1]，找出所有軌跡Dsub，滿足條件 Support（Dsub）≥Supportmin其中

顯然，頻繁軌跡的子軌跡也是頻繁軌跡，所以只需找出每類軌跡長度最長的子軌跡即可。

3.2 頻繁模式挖掘算法

（1）生成圖

給定標簽 Oi的軌跡集合 S=｛D1，D2，…，Dn｝，遍歷軌跡集合，按照軌跡邊構建帶權圖，權重為經過該軌跡邊的軌跡數。

①從集合S中取中第一條軌跡，初始化圖F，對兩點的連接邊記權值為1，增加虛擬節點起點和終點的權值為1，起點指向第一個點，終點指向最后一個點。

②For D1in S，其中 1＜i＜n，D1=｛di0，di1，…，dik｝

在Di中取出di0，在F中查找該di。如果找到，則在虛擬起點與該點間的邊權值增加1；如果找不到，將di0加入圖F，給di0增加虛擬起點，兩點連接的邊權值為1。

For di1IN ｛di1，di2，di3，…，dik-1｝

在 F中查找dij，如果已有點 dij，且與 dij-1有連接邊，則給邊的權值加1；如果沒有連接邊，則增加連接邊給定權值為1。如果沒有點dij，則將dij加入到圖F，增加與dij-1連接邊，給邊的權值為1。

End for

在Di中取出dik，在F中查找dik，如果找到，且與dik-1有連接邊，則給邊的權值加1；如果沒有連接邊，則增加連接邊，給定權值為1，將dik與虛擬終止點間的邊加1。如果找不到，將dik加入到F，增加與dik-1連接邊且設置權值為1，增加虛擬終點及其與dik的連接邊設置權值為1。

End for

（2）給定最小支持度 Smin，根據軌跡總數 n，可算出頻繁軌跡滿足至少要有h條軌跡經過該軌跡段。按h進行減權后得到圖F′。

①圖F′中的邊的權值W減去h，如果W＞h，則權值更新為W減去h。

②如果W≤h，將該權值更新為0。

（3）對圖以虛擬起點為根進行深度遍歷，將遍歷過程中經過的點：如果權值大于0，將點加入到頻繁軌跡候選表里，直到到達虛擬終點為止，記錄整條鏈路上的最小權值Wmin，此候選軌跡的支持度為（Wmin+h）/n。由于有的點既是起始點又是終止點，那么可能存在兩條軌跡序列點相同，只是序列點相互倒序，所以最后再對候選軌跡進行去重。

4 算法驗證

從電動車防盜系統中，抽取出某車主近30天52條運行軌跡數據對算法可行性進行驗證。每條軌跡數據包括多個通過基站的信息，包含基站ID、進入時間、停留時間。首先對數據進行預處理，將停留時間為1s的數據清理掉。生成的帶權無環圖如圖3所示，其中數字編號為軌跡序列中的位置點，A、B、C表示起點或者終點（僅標識起點和終點，不作為軌跡的一部分）。通過計算后結果如表1所示。

圖3 帶權無環圖

表1 挖掘結果

通過在地圖上查看各位置點的坐標，可知：位置1，是某小區門前路口位置，而位置19是某寫字樓附近路口，位置22是某綜合體購物中心。結合圖3與軌跡的起終點時間可知，該車主住在位置1，在位置19處上班，偶爾去綜合體消費，表1的挖掘結果符合常理。

5 結語

實際應用中有很多領域可運用軌跡數據挖掘，通過分析歷史軌跡，可以更好地理解活動對象行為。同時，軌跡數據挖掘為公眾提供了很多便利，例如路線推薦、實時交通信息發布。對政府組織而言，軌跡數據挖掘有助于降低監督和管理成本。在城市區域，車輛軌跡數據挖掘為監測城市的交通狀態提供了一種高效可擴展的方法。

本文論述了頻繁軌跡的分析算法，以電動自行車防盜系統為例，從軌跡數據庫中取出軌跡數據，結合車主的實際情況，驗證了算法的有效性。本文只是對軌跡數據從頻繁這一角度進行了分析，針對車主軌跡數據還有伴隨車輛、熱點路徑等其它方面的分析角度，這將是后期研究的重點。另外如何利用挖掘出的信息，分析車主內在需求、發掘商業機會、改善城市公共服務質量、提升服務準確性和建設智慧城市也將是需要深入思考的問題。