基于移動用戶時空軌跡特征的軌跡分類研究

［劉漢艷］

1 引言

隨著移動通信及移動社交工具的快速發(fā)展，運營商獲取了大量移動用戶的時空軌跡數(shù)據(jù)，這些時空軌跡數(shù)據(jù)已經(jīng)在智能交通、用戶出行等方面具有重要的數(shù)據(jù)支撐作用。時空軌跡作為當(dāng)前研究的熱點，不少學(xué)者已經(jīng)把相關(guān)的研究應(yīng)用于移動目標識別、路徑軌跡模式挖掘等領(lǐng)域。Gonzalez 等[1]人利用收集的GPS 數(shù)據(jù)，采用神經(jīng)網(wǎng)絡(luò)分類器自動識別用戶出行的模式；肖艷麗等[2]人通過提取移動用戶軌跡的停留時間、平均速度等特征后，采用神經(jīng)網(wǎng)絡(luò)對移動用戶的出行模式進行識別，取得了更高的準確率；Jahangiri等[3]人使多種分類方法將用戶軌跡劃分為包括走路在內(nèi)的5 種類別；除了上述學(xué)者對軌跡全局進行分類外，不少學(xué)者通過對軌跡使用多階段分類的方法。Zhang[4]將一條用戶軌跡劃分為多種交通模式；朱進[5]等人提出基于層次運動特征的軌跡分類方法，對軌跡的運動特征分為全局特征和局部特征，然后采用分類的方法對用戶的軌跡進行分類。然而，大規(guī)模的軌跡空間分布往往具有非平穩(wěn)性，因此，軌跡數(shù)據(jù)在空間上的變化是不均勻的。除此之外，移動用戶的軌跡數(shù)據(jù)具有自身獨特性的特征：時空軌跡數(shù)據(jù)受到信號的影響而導(dǎo)致軌跡數(shù)據(jù)本身缺失或者是錯誤的問題；時空軌跡的分類準確度會受到時空的影響；同一個位置在不同時間的運動特征的差別很大；單個用戶軌跡的特征的選取問題。本文針對上述問題，首先采用卡爾曼濾波方法對移動用戶的軌跡進行預(yù)處理；然后根據(jù)移動用戶軌跡自身的特點，提取用戶軌跡的運動特征、形狀特征、軌跡位置特征、時間特征等向量，以此反映不同用戶的軌跡特點；最后，采用譜聚類的方法對移動用戶的軌跡特征進行分類，實現(xiàn)移動用戶軌跡的分類。

2 相關(guān)研究

2.1 軌跡的定義

軌跡是用來描述移動對象的運動狀態(tài)，指移動對象隨著時間的變化而產(chǎn)生的空間變化的序列。本文所指的移動用戶的軌跡是指由于移動用戶發(fā)生業(yè)務(wù)或者位置的移動被基站記錄下來的一系列離散的時空坐標，其時空坐標一般指基站的坐標，移動用戶在時刻tn的基站坐標一般標識為（xn，yn，tn）。由上述的定義可知，移動用戶在一段時間內(nèi)的離散空間軌跡traj=（（x1，y1，t1），（x2，y2，t2），…，（xn，yn，tn））。

2.2 軌跡特征

提取軌跡特征的目的在于將有助于軌跡分類的特征提取出來。軌跡特征包括：運動特征、形狀特征、位置特征以及時間特征。

運動特征是指軌跡的速度、加速度、角速度等特征的平均數(shù)、標準差、變異系數(shù)、自相關(guān)系數(shù)、偏度系數(shù)、幅度、頻率等可以反映一個用戶軌跡運動特征的參數(shù)。

軌跡的形狀特征是指軌跡的曲率、方向、轉(zhuǎn)角等特征的平均數(shù)、標準差、變異系數(shù)、自相關(guān)系數(shù)、偏度系數(shù)等可以反映一個用戶軌跡形狀特征的參數(shù)。

軌跡的位置特征是指軌跡的運動路徑長度、回旋半徑等特征的平均數(shù)、標準差、變異系數(shù)、自相關(guān)系數(shù)、偏度系數(shù)等可以反映一個用戶軌跡位置特征的參數(shù)。

軌跡的時間特征是指軌跡的起始時間、到達時間、持續(xù)時間、停留時間、時間間隔等特征的平均數(shù)、標準差、變異系數(shù)、自相關(guān)系數(shù)、偏度系數(shù)等可以反映一個用戶軌跡時間特征的參數(shù)。

2.3 軌跡的相似性度量研究

大部分軌跡相似性研究側(cè)重于移動對象在自由空間的相似性，還有一部分研究是關(guān)注移動對象在受限空間的相似性，特別是在道路或者軌道網(wǎng)絡(luò)上的相似性。當(dāng)前的軌跡相似性一般都是擴展軌跡時間序列的時空相似性獲得的。如Sinha 等人采用間隔時間作為軌跡時間特征，采用加權(quán)平均的歐式距離衡量個體間的時空相似性[6]；Kreveld 等[7]人以軌跡起始時間和持續(xù)時間為軌跡的時間特征，引入軌跡時空相似性來查找相同的子軌跡；Abraham 等[8]人考慮了軌跡的興趣點和興趣時間，然后采用類似編輯聚類的方法進行相似性研究。研究發(fā)現(xiàn)，軌跡的相似性度量主要依賴于軌跡間距離的定義，該“距離”主要指采用哪一種軌跡特征可以有效的衡量不同軌跡間的差別。比如：同一段道路的軌跡不應(yīng)該由于時間的不同而具有時空相似性；同理，相同時間的不同道路上的軌跡不應(yīng)該具有時空相似性。因此，在衡量移動用戶時間軌跡的相似性時，必須考慮移動用戶之間軌跡的時間、空間、運動、形狀等多種特征，才能有效的衡量移動用戶之間軌跡的相似性。

2.4 軌跡分類算法

在介紹軌跡分類前，先來介紹一下基于分類規(guī)則的時空軌跡預(yù)處理算法。分類規(guī)則算法的基本原理是：通過對訓(xùn)練數(shù)據(jù)進行分析，挖掘出某一個區(qū)域內(nèi)軌跡支持度和置信度的閾值，然后對每一條軌跡進行遍歷，如果該軌跡滿足規(guī)定的條件，那么對軌跡進行特征提取，否則，該軌跡的特征為0。上述的軌跡預(yù)處理的優(yōu)點在于能夠剔除一部分隨機的軌跡，大大減少了計算的復(fù)雜度。

在軌跡預(yù)處理之后，一般對軌跡的特征向量進行訓(xùn)練，建立分類器，然后再把實時的軌跡放進分類器中，實現(xiàn)軌跡模式的預(yù)測。分類方法有以下幾種：神經(jīng)網(wǎng)絡(luò)[9,10]、支持向量機[11～13]、決策樹[14～16]、譜聚類[17～19]、k-近鄰[20,21]等。由于文章篇幅的限制，本文簡單介紹支持向量機、決策樹以及譜聚類算法實現(xiàn)的思路。

支持向量機在解決小樣本、非線性及高維模式識別中具有很多優(yōu)勢，其處理數(shù)據(jù)思路：建立一個最優(yōu)決策的超平面，使得平面兩側(cè)距離該平面最近的兩類樣本距離最大化。簡而言之，就是找到一個超平面，使得不同類別樣本之間的距離最大化。

決策樹作為一種高效、可讀性好的分類器，受到眾多學(xué)者的追捧，其處理數(shù)據(jù)的思路：通過計算信息增益大小來判斷當(dāng)前的節(jié)點應(yīng)該用什么特征來構(gòu)建樹，也就是說用計算出來的信息增益最大特征來構(gòu)建決策樹當(dāng)前的節(jié)點。但是決策樹存在特征選取困難和過擬合的問題是它計算精度的軟肋。為了應(yīng)對軌跡空間分布非平穩(wěn)性、時空軌跡分類準確度受到時空影響以及特征數(shù)量的問題，本文采用譜聚類方法來實現(xiàn)用戶軌跡分類，譜聚類算法無需事前確定特征向量的數(shù)量，還可對分布不均勻、任意形狀的樣本空間進行聚類分析，且聚類結(jié)果能收斂于全局最優(yōu)。

譜聚類作為從圖論演化出來的算法，在聚類中得到廣泛應(yīng)用。其主要思路為：所有的數(shù)據(jù)都視為空間的點，點之間可以用一條邊連起來。“距離”較遠的點的邊權(quán)值較低，反之亦然，通過對所有數(shù)據(jù)點形成的圖進行切圖，讓子圖內(nèi)部的邊權(quán)值之和盡量高，子圖之間的邊權(quán)值之和盡量低，從而達到聚類的目的。譜聚類具有無監(jiān)督、高效的特點，但是兩點的“距離”的定義是復(fù)雜的，其需要根據(jù)不同的目標去選取每一個點的特征。有些“距離”可用兩點之間的真實距離的倒數(shù)來衡量；但有些“距離”則需要用每一個點的特征向量來衡量，具體需要根據(jù)研究者的目的選取。

3 基于移動用戶時空軌跡特征的軌跡分類

3.1 移動用戶軌跡預(yù)處理

本文記錄移動用戶的軌跡是通過基站的位置來體現(xiàn)的，考慮到基站信號的不穩(wěn)定、網(wǎng)絡(luò)延遲等問題，因此本文采用動態(tài)卡爾曼濾波器[22]對用戶軌跡進行過濾，以提高用戶軌跡的準確性。如表1 是移動用戶軌跡數(shù)據(jù)，通過對用戶切換時間來計算移動用戶當(dāng)前的運動速度?；谝苿佑脩粑恢煤鸵苿铀俣鹊膭討B(tài)卡爾曼濾波，能夠?qū)崿F(xiàn)用戶軌跡信息的平滑。

表1 移動用戶的軌跡示意圖

當(dāng)移動用戶在移動過程中遇到基站信號不穩(wěn)定發(fā)生來回切換的問題，結(jié)合速度和位置的動態(tài)卡爾曼濾波得到的效果如圖1 所示。

圖1 移動用戶軌跡信息平滑前后的效果圖

從圖1 可以看出，經(jīng)過動態(tài)卡爾曼濾波處理的移動用戶軌跡對軌跡有典型的平滑作用，在城市密集區(qū)域，由于基站信號發(fā)生來回切換，使得移動用戶軌跡信息不能真實的反映用戶移動的真正狀態(tài)，因此，使用動態(tài)卡爾曼濾波生成的軌跡能夠在很大程度上平滑用戶軌跡信息。

3.2 提取移動用戶時空軌跡的特征

經(jīng)過動態(tài)卡爾曼濾波器平滑用戶軌跡后，不僅需要考慮軌跡的時間特征，還要考慮軌跡的位置特征。也就是在選定的時間段和某個區(qū)域范圍內(nèi)，通過關(guān)聯(lián)規(guī)則FPGrowth 方法[23]挖掘移動用戶的軌跡分類規(guī)則，如果某條軌跡滿足支持度和置信度閾值，則提取該移動用戶某段軌跡的特征；否則，把該移動用戶的某段軌跡特征設(shè)為0，作為異常軌跡分開處理。通過訓(xùn)練某個區(qū)域某個時間段的所有都移動用戶軌跡，找到了基于該區(qū)域的分類軌跡以及軌跡運行模式的分類規(guī)則，得到的某個區(qū)域移動用戶分類規(guī)則示意圖，如圖2 所示。

圖2 某個區(qū)域的移動用戶軌跡分類規(guī)則

圖2 展現(xiàn)的是基于FP 樹算法找到的滿足區(qū)域分類規(guī)則的軌跡段，由于速度和發(fā)生業(yè)務(wù)的時間間隔的差異性，在某一個區(qū)域的軌跡也有不定的差異。經(jīng)過關(guān)聯(lián)規(guī)則處理后，下一步就是要提取軌跡段的特征向量。本文提取的軌跡特征包括：運動特征、形狀特征、位置特征以及時間特征。其中運動特征的參數(shù)有加速度、速度；形狀特征參數(shù)有曲率和轉(zhuǎn)角；位置特征參數(shù)包括運動路徑長度；時間特征參數(shù)包括：起始時間、到達時間、停留時間。通過計算上述參數(shù)的標準差、變異系數(shù)、偏度系數(shù)，形成24個軌跡特征向量。

3.3 采用譜聚類的算法對移動用戶的軌跡進行分類

把每一個用戶視為圖論的一個點，這些點用邊連接起來。距離較遠兩個點的邊權(quán)重值較低；距離較近兩個點的邊權(quán)重較高。本文的邊權(quán)重計算方法是計算點與點之間的特征向量的空間距離，如果兩點之間的距離較小，則說明兩個軌跡段的特征比較相似，反之亦然；對每個點的距離標準化處理后，采用譜聚類的算法對上述的軌跡段進行聚類，聚類的結(jié)果如圖3 所示。

圖3 譜聚類的用戶軌跡分類結(jié)果

3.4 實驗結(jié)果

本實驗選取某條道路中不同時間段的用戶移動軌跡進行試驗，實驗隨機選取10 天固定的5 個時間段進行實驗，實驗的準確率如表2 所示。

表2 實驗準確率

表2給出了不同時間段的軌跡數(shù)據(jù)在本實驗的聚類準確率分析結(jié)果。從表2可以看出，在相同路段的軌跡數(shù)據(jù)量下，基于軌跡多特征的不同時間段產(chǎn)生的聚類結(jié)果準確率存在一定的差異性。閑時準確率比忙時準確率要高一些，這是因為閑時用戶軌跡的時間、空間、運動、形狀等多種特征更具有平穩(wěn)性。由此可知，本文的算法能夠較好地對移動用戶的時空軌跡進行分類。

4 結(jié)束語

本文基于移動用戶軌跡提出了移動用戶時空軌跡的分類算法，首先是采用動態(tài)卡爾曼濾波對移動用戶的軌跡進行平滑處理；接著，利用FP 樹挖掘移動用戶的軌跡分類規(guī)則，剔除噪音軌跡后再對滿足條件的軌跡進行特征提?。蛔詈蟛捎米V聚類的方法對移動用戶的軌跡進行分類。實驗證明，利用該方法能夠在一定程度上提升移動用戶軌跡分類的準確率。