鄢團(tuán)軍，呂 軍，齊國強(qiáng)

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

0 引言

射頻識(shí)別即RFID（Radio Frequency Identification）技術(shù)，是自動(dòng)識(shí)別技術(shù)在無線電技術(shù)方面的具體應(yīng)用與發(fā)展，其利用射頻信號(hào)通過空間耦合實(shí)現(xiàn)無接觸信息傳遞，并通過所傳遞的信息識(shí)別目標(biāo)[1]，無需識(shí)別系統(tǒng)與特定目標(biāo)之間建立機(jī)械或光學(xué)接觸。該技術(shù)已被廣泛應(yīng)用于安防、倉儲(chǔ)、物流、追溯、防偽、旅游、醫(yī)療、教育等不同領(lǐng)域。

運(yùn)用有源RFID技術(shù)，構(gòu)建射頻網(wǎng)，管控網(wǎng)內(nèi)所有的電動(dòng)自行車，可以實(shí)現(xiàn)車輛被盜能及時(shí)發(fā)現(xiàn)，及時(shí)尋回。電動(dòng)車防盜系統(tǒng)也可以對(duì)車主在通勤中的違章情況進(jìn)行善意提示，逐步提高車主交通安全意識(shí)。該系統(tǒng)對(duì)于建設(shè)智慧城市、提升城市公共服務(wù)質(zhì)量具有較為深遠(yuǎn)的意義。

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

本文首先描述有關(guān)軌跡數(shù)據(jù)的來源及結(jié)構(gòu)，然后給出頻繁軌跡相關(guān)定義，最后提出基于帶權(quán)無環(huán)圖計(jì)算頻繁軌跡的方法并驗(yàn)證可行性。

1 相關(guān)研究綜述

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

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

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

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

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

2 軌跡數(shù)據(jù)的形式

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

本文以有源RFID防盜系統(tǒng)記錄移動(dòng)對(duì)象通過基站的序列來表示軌跡。對(duì)路網(wǎng)環(huán)境下的車輛運(yùn)行軌跡而言，路口被當(dāng)作是軌跡分段的劃分點(diǎn)[14]，一段沒有分岔的道路是一個(gè)軌跡分段的最小單位。本系統(tǒng)采用基于路網(wǎng)的關(guān)鍵點(diǎn)采樣，通過控制有源RFID讀寫器（后文稱基站）的采集范圍來實(shí)現(xiàn)基站與基站間采集范圍不重疊的同時(shí)，道路路口不留信號(hào)死角。如圖1所示，若目標(biāo)O經(jīng)過路口A，被基站d1采集，系統(tǒng)認(rèn)為O的位置在A附近，然后，若目標(biāo)O被基站d3采集到，則可認(rèn)為O的行動(dòng)軌跡為從A到C。

圖1 基站信號(hào)范圍及部署節(jié)點(diǎn)示意圖

電動(dòng)自行車（后文稱車輛）附著有射頻標(biāo)簽，該射頻標(biāo)簽的編號(hào)視為該車輛身份唯一標(biāo)識(shí)，車輛進(jìn)入射頻網(wǎng)后，系統(tǒng)可以對(duì)車輛進(jìn)行定位并記錄車輛移動(dòng)軌跡，如圖2所示。

3 基于帶權(quán)無環(huán)圖的頻繁軌跡挖掘算法

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

3.1 軌跡定義

定義1：軌跡點(diǎn)

車輛運(yùn)動(dòng)過程中在時(shí)間空間域中的坐標(biāo)d=（x，y，t），其中（x，y）為空間坐標(biāo)。 本文以有源 RFID防盜系統(tǒng)記錄移動(dòng)對(duì)象通過基站的序列來表示軌跡，所以軌跡點(diǎn)與RFID基站位置信息等價(jià)，t為車輛經(jīng)過空間點(diǎn)（x，y）的時(shí)刻。

定義2：軌跡

車輛 Oi在時(shí)間區(qū)間Δt內(nèi)，經(jīng)過的軌跡點(diǎn)序列集合，表示為 D（Oi，Δt）=｛d0，d1，d2，…，dn｝，其中 di表示軌跡點(diǎn)，即 di=（xi，yi，ti）。

定義3：軌跡邊序列

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

定義4：子軌跡

給定Oi某一時(shí)間區(qū)間Δt內(nèi)的運(yùn)行軌跡D（Oi，Δt）=｛d0，d1，d2，…，dn｝，按時(shí)間先后順序取其中一部分連續(xù)基站組成的有序集合 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′）經(jīng)過的時(shí)間區(qū)間 Δt′是 Δt的子區(qū)間。

定義5：軌跡長度

軌跡包中軌跡點(diǎn)的個(gè)數(shù)。 如 D（Oi，Δt）=｛d0，d1，d2，…，dn｝的軌跡長度 l=n。

定義6：軌跡頻次

圖2 電動(dòng)自行車運(yùn)行軌跡

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

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

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

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

3.2 頻繁模式挖掘算法

（1）生成圖

給定標(biāo)簽 Oi的軌跡集合 S=｛D1，D2，…，Dn｝，遍歷軌跡集合，按照軌跡邊構(gòu)建帶權(quán)圖，權(quán)重為經(jīng)過該軌跡邊的軌跡數(shù)。

①從集合S中取中第一條軌跡，初始化圖F，對(duì)兩點(diǎn)的連接邊記權(quán)值為1，增加虛擬節(jié)點(diǎn)起點(diǎn)和終點(diǎn)的權(quán)值為1，起點(diǎn)指向第一個(gè)點(diǎn)，終點(diǎn)指向最后一個(gè)點(diǎn)。

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

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

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

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

End for

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

End for

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

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

②如果W≤h，將該權(quán)值更新為0。

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

4 算法驗(yàn)證

從電動(dòng)車防盜系統(tǒng)中，抽取出某車主近30天52條運(yùn)行軌跡數(shù)據(jù)對(duì)算法可行性進(jìn)行驗(yàn)證。每條軌跡數(shù)據(jù)包括多個(gè)通過基站的信息，包含基站ID、進(jìn)入時(shí)間、停留時(shí)間。首先對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，將停留時(shí)間為1s的數(shù)據(jù)清理掉。生成的帶權(quán)無環(huán)圖如圖3所示，其中數(shù)字編號(hào)為軌跡序列中的位置點(diǎn)，A、B、C表示起點(diǎn)或者終點(diǎn)（僅標(biāo)識(shí)起點(diǎn)和終點(diǎn)，不作為軌跡的一部分）。通過計(jì)算后結(jié)果如表1所示。

圖3 帶權(quán)無環(huán)圖

表1 挖掘結(jié)果

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

5 結(jié)語

實(shí)際應(yīng)用中有很多領(lǐng)域可運(yùn)用軌跡數(shù)據(jù)挖掘，通過分析歷史軌跡，可以更好地理解活動(dòng)對(duì)象行為。同時(shí)，軌跡數(shù)據(jù)挖掘?yàn)楣娞峁┝撕芏啾憷缏肪€推薦、實(shí)時(shí)交通信息發(fā)布。對(duì)政府組織而言，軌跡數(shù)據(jù)挖掘有助于降低監(jiān)督和管理成本。在城市區(qū)域，車輛軌跡數(shù)據(jù)挖掘?yàn)楸O(jiān)測(cè)城市的交通狀態(tài)提供了一種高效可擴(kuò)展的方法。

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