基于Wi-Fi時空數(shù)據(jù)的位置預測

張書欽 王金洋 白光耀 張敏智

摘? 要：在位置預測研究中，歷史軌跡通常呈現(xiàn)分布稀疏和結構單一的特點，導致預測模型準確率下降。針對此問題，利用用戶屬性特征和歷史軌跡特征度量用戶相似性，對相似用戶進行分簇;并提出基于相似用戶簇的LSTM神經(jīng)網(wǎng)絡預測模型SG-LSTM（Similar Group based LSTM model），以改善軌跡數(shù)據(jù)的稀疏性問題。實驗表明，模型能夠較好地捕捉用戶的移動規(guī)律，預測準確率超過87.90%，在準確率和時間復雜度方面均優(yōu)于傳統(tǒng)模型。

關鍵詞：稀疏時空數(shù)據(jù);用戶相似性;LSTM;位置預測

中圖分類號：TN92? ? ? ?文獻標識碼：A 文章編號：2096-4706（2020）24-0164-05

Location Prediction Based on Wi-Fi Spatiotemporal Data

ZHANG Shuqin，WANG Jinyang，BAI Guangyao，ZHANG Minzhi

（School of Computer Science，Zhongyuan University of Technology，Zhengzhou? 450007，China）

Abstract：In the research of location prediction，historical trajectories usually show the characteristics of sparse distribution and single structure，which leads to a decline in the accuracy of the prediction model. To solve this problem，the similarity of users is measured by using user attribute characteristics and historical track characteristics，and similar users are clustered;and proposes similar user cluster based LSTM neural network prediction model SG-LSTM（Similar Group based LSTM model）to improve the sparsity of trajectory data. The experimental results show that the model can better capture the users movement rule，and the prediction accuracy is more than 87.90%，which is better than the traditional model in terms of accuracy and time complexity.

Keywords：sparse spatiotemporal data;user similarity;LSTM;location prediction

0? 引? 言

隨著5G通信技術的發(fā)展及智能設備的普及，人們得以獲取大規(guī)模的時空數(shù)據(jù)，基于海量時空數(shù)據(jù)的人類移動性預測受到人們的廣泛關注[1-3]。在公共服務方面，軌跡預測可應用于交通管理[4]、公共安全預警[5]等，以提升公共設施的服務效率;在個人服務方面，也可用于個性化推薦[6]、智能導航等，以提升用戶體驗。隨著此類基于個性化服務的應用激增，從人們的歷史軌跡中挖掘移動模式，并預測未來去向已成為一種迫切的需要。

目前，基于時空數(shù)據(jù)的位置預測研究面臨以下問題：

（1）時空數(shù)據(jù)稀疏性?？色@取的時空數(shù)據(jù)大多是低采樣的，在采集過程中由于數(shù)據(jù)丟失或者用戶拒絕分享位置信息導致采集的用戶歷史軌跡數(shù)據(jù)較為稀疏。

（2）時空數(shù)據(jù)單一性。人類移動具有規(guī)律性，通常每天只訪問固定的幾個位置，因此在低采樣的情況下，用戶的歷史軌跡包含的位置點比較單一。

以上問題導致預測模型在訓練過程中因缺少足夠的上下文信息，不能很好地捕捉用戶的移動偏好特征，降低了預測準確率。

針對以上問題，本文采用劃分相似用戶簇的方法強化用戶的歷史軌跡上下文信息，有效緩解歷史軌跡的稀疏性和單一性;并提出了一種基于相似用戶簇的LSTM神經(jīng)網(wǎng)絡預測模型，以更好地建模軌跡序列數(shù)據(jù)。

1? 相關工作

目前基于時空數(shù)據(jù)的軌跡預測工作主要分為基于模式的方法和基于模型的方法[7-9]?；谀Ｊ降姆椒ㄊ紫葟拇罅康臍v史軌跡中發(fā)現(xiàn)頻繁軌跡模式，例如順序模式和周期模式等，然后將當前查詢軌跡與頻繁軌跡模式進行匹配，從而達到軌跡預測的目的。Monreale等[10]提出了基于模式的軌跡預測模型WhereNext，該方法從移動對象的歷史軌跡數(shù)據(jù)中挖掘頻繁項集作為移動模式，并用該模式表示用戶頻繁訪問的地點，同時利用T-Pattern Tree查詢發(fā)現(xiàn)最優(yōu)匹配軌跡?；谀Ｊ降姆椒ㄓ捎诿看胃露夹枰匦峦诰蝾l繁項集，此外在面向稀疏或者單一性數(shù)據(jù)時可能存在無法挖掘頻繁模式的情況，導致預測效果不理想。LSTM作為時序數(shù)據(jù)處理的主流工具，在軌跡預測領域應用廣泛。高雅等[11]為了解決馬爾可夫模型在處理長序列數(shù)據(jù)時存在的維度爆炸問題，提出位置分布式表示模型（LDRM），將高維的One-Hot位置表示向量嵌入到低維空間，并與LSTM結合，對移動對象的軌跡做預測研究，提升了預測準確性。

2? 術語定義及問題描述

定義1（興趣點）：興趣點（Point Of Interest，POI）是指給定空間區(qū)域內(nèi)任何可以被抽象為一個位置點的地理實體，用p表示，該區(qū)域中所有POI集合記為S={p1，p2，…，pn}，其中n為興趣點個數(shù)。

定義2（停留點）：給定的時間閾值θt，若用戶u在p的停留時間超過該閾值，則將p定義為該用戶的一個停留點，記為sp。停留點是具有一定時間約束的POI。

定義3（軌跡序列）：軌跡序列由一系列按照時間排序的停留點構成，記為TS={sp1，sp2，…，spn}，spi為第i個停留點，1≤i≤n。

定義4（用戶屬性）：用戶屬性指用戶固有的且在短時間內(nèi)不易發(fā)生變化的標簽，記AT={a1，a2，…，an}，ai為用戶的第i個屬性，1≤i≤n。

用戶屬性即為用戶的標簽，例如，一名學生的用戶屬性包括：學號、性別、年級和專業(yè)等，可記為AT={001，male，freshman，CS}。

問題定義：本文將所研究的軌跡預測問題定義為：對于某一用戶u，給定用戶屬性ATu={a1，a2，…，an}和用戶u在t時刻的軌跡序列TSu={sp1，sp2，…，spn}，預測該用戶t+1時刻最可能訪問的興趣點p。

3? 軌跡預測模型

傳統(tǒng)的LSTM位置預測模型只根據(jù)單個用戶的歷史軌跡進行建模，而忽略了歷史軌跡數(shù)據(jù)的稀疏性和單一性特點，導致預測精度降低。針對此問題，本文對通過對相似用戶進行分簇，實現(xiàn)稀疏歷史信息增強的效果。具體來說，首先，從用戶數(shù)據(jù)集中提取屬性和歷史軌跡數(shù)據(jù)，再分別計算用戶的屬性相似性和移動行為相似性，并對以上兩種相似性得分進行融合，將最終的相似性得分作為劃分用戶簇的依據(jù)，并在此基礎上劃分用戶簇，將一類用戶的歷史軌跡作為訓練數(shù)據(jù)進行軌跡預測模型的訓練，以提高模型性能。本文模型框架如圖1所示。

3.1? 用戶相似性度量

3.1.1? 屬性相似度度量

對任意用戶u和用戶v以及對應的屬性ATu={au1，au2，

…，aun}和ATv={av1，av2，…，avn}，若對應的屬性值相同則取1，否則為0，如式（1）所示：

（1）

考慮到不同的屬性對用戶下一個軌跡點的選擇會產(chǎn)生不同的影響力，為每個屬性分配不同的權重。任意兩個用戶的屬性相似度計算如式（2）所示：

（2）

其中，simAT∈[0，1]，ωm是第m個用戶屬性的權重，且 。

3.1.2? 軌跡相似度度量

本文將軌跡相似度度量轉換為序列匹配任務，即兩條軌跡之間匹配度越高，則相似性越高，采用LCSS算法（Longest Common Subsequence，LCSS）估計用戶之間的歷史軌跡相似度。對任意的用戶u和用戶v，軌跡序列分別為TSu={sp1，sp2，…，spm}和TSv={sp1，sp2，…，spn}，m，n分別為用戶u，v的軌跡序列長度，用戶u和用戶v的軌跡最長公共子序列LCSS（u，v）={spk1，spk2，…，spkz}，spki∈TSu∪TSv，1≤i≤z，z為用戶u和用戶v的軌跡序列包含的最長公共子序列長度。任意兩個用戶的歷史軌跡相似度計算如式（3）所示：

（3）

len（TS）表示軌跡序列的長度，simTS∈[0，1]。當simTS=0時，表示兩條軌跡完全不相似;當simTS=1時，表示兩條軌跡完全重合。

3.1.3? 用戶相似性度量

將用戶的屬性相似度與軌跡相似度進行加權融合，得到任意兩個用戶相似度，計算公式如式（4）所示：

sim（u，v）=α·simAT（u，v）+（1-α）·simTS（u，v） （4）

其中α為用戶屬性對用戶相似度的影響因子。

3.2? 基于用戶相似度的用戶簇劃分

由相似度度量式（4）可以度量任意兩個用戶之間的相似度，據(jù)此可得包含所有用戶的相似度查詢表。設定相似度閾值βs，依據(jù)查找表為每個用戶劃分相似用戶簇，得到最終的用戶簇集合。該算法優(yōu)點在于緩解了相似用戶分簇的冷啟動問題，當出現(xiàn)新用戶時，只需在相似度查詢表中更新該用戶與已有用戶的相似度即可完成用戶簇劃分，具體如算法1所示。

算法1：用戶簇劃分算法

Input： U， AT， TS，βs.//輸入用戶集合，及各用戶的屬性信息、軌跡記錄。

Output： 用戶相似矩陣M，相似簇Dict = {ui ： list（uj）}.

1.n = lenth（U）; //用戶個數(shù)

2.create similar matrix Mn×n//記錄用戶間相似度

3.create empty dictDict;//記錄相似用戶簇

4.i = 0;//設定用戶索引起始值

5.whilei≤ n-1

6.create empty list L; //創(chuàng)建空列表

7.j = i//設定用戶索引起始值

8.while j≤n-1：

9.sim（ui， uj）;//計算相似度

10.mij = mji = sim（ui， uj）;//mij是M的元素

11.? ? if sim（ui， uj） ≥ βs：//滿足相似閾值

12.add uj to L; //添加到相似用戶

13.j = j + 1;

14.add to Dict;//保存相似用戶簇

15.i = i + 1;

16.return M， Dict. //返回相似度矩陣和相似簇字典

若用戶簇中用戶個數(shù)為m，每個用戶包含n個屬性，且平均軌跡長度為l，則該算法關鍵步驟在于計算相似矩陣M，因此算法1時間復雜度為O，函數(shù)的表達式為（（n+12）·m+ m（m-1））。

3.3? 基于相似用戶簇的SG-LSTM模型

稀疏軌跡通常呈現(xiàn)出單一性特點，軌跡序列包含POI類別個數(shù)較少，導致用戶歷史軌跡上下文信息大大減少，不能很好地反映用戶的實際移動偏好特征。本文將相似用戶的歷史軌跡集合作為該相似群體的整體歷史軌跡，用以豐富個體用戶地歷史軌跡，緩解個體用戶歷史軌跡上下文不足的問題，并在此基礎上提出基于相似用戶簇的軌跡預測模型SG-LSTM，模型基于相似用戶群體軌跡建模，其中考慮了用戶的屬性信息，在一定程度上緩解了用戶軌跡數(shù)據(jù)的稀疏性問題。SG-LSTM模型實現(xiàn)如算法2所示。

算法2：SG-LSTM模型算法實現(xiàn)

Input：Dict={ui ： list（uj）}， AT， TS，ε.//輸入相似簇字典、用戶屬性、軌跡記錄及損失閾值

Output： Trained SG-LSTM model.

1.select ui from Dict.keys; //選擇相似用戶簇

2.add ui to list（uj）;

3.train user set S = list（uj）; //獲取訓練數(shù)據(jù)

4.m = lenth（list（uj））;//相似簇中用戶個數(shù)

5.set bitchsize = m; timestep = n; //設置模型參數(shù)

6.construct trainset X = {TS}m×n ; //構造神經(jīng)網(wǎng)絡輸入

7.initialize δ={ωf，ωu，ωo，ωc，bf，bu，bo，bc};//初始化

8.loss = J（X， δ）; //計算損失函數(shù)

9.whileloss ≥ ε：

10.? adjust δ; //調(diào)整參數(shù)

11.loss = J（X， δ）;

12.return δ.

4? 實驗及結果分析

4.1? 數(shù)據(jù)集

本文采用某高校包含學生屬性信息的Wi-Fi簽到日志數(shù)據(jù)集。該數(shù)據(jù)集為11 524名在校學生在2019年10月1日—2019年10月19日期間的3 646 592條簽到日志記錄，其中包括：學生編號、設備MAC地址、經(jīng)度和緯度、連接時間等，用戶屬性信息數(shù)據(jù)包括：學生編號、性別、年級和專業(yè)班級，數(shù)據(jù)樣例如表1所示。

4.2? 評價指標

本文采用準確率作為模型性能評價指標，記為Acc，計算公式為：

（5）

其中，PTrue表示模型在測試集上預測正確的樣本個數(shù)，NAll表示測試集的樣本總個數(shù)。

4.3? 實驗參數(shù)影響

為了找到更優(yōu)的參數(shù)組合，使得模型預測性能更高，分別設計了不同的參數(shù)組合進行實驗對比。圖2為每次輸入模型的軌跡點個數(shù)變化對模型預測準確率的影響，圖例中的N_step即timestep表示每次輸入模型中的軌跡長度，即軌跡點個數(shù)。由圖2可以看出，N_step=5時模型的性能最好，表明剛訪問的5個POI對用戶下一個軌跡點的選擇有較強影響力;圖3展示模型隱藏層神經(jīng)元個數(shù)對模型準確率的影響，N_hidden表示每層LSTM的神經(jīng)元個數(shù)。經(jīng)過不斷調(diào)整優(yōu)化，最終選取模型參數(shù)：N_step=5，N_hidden=12。

4.4? 實驗對比

為了驗證本文所提出的SG-LSTM模型的有效性，將本文模型與基于MF的軌跡預測模型、基于HMM的軌跡預測模型、基于SimpleRNN的軌跡預測模型和基于Single-LSTM的軌跡預測模型做準確率和預測效率對比，結果如圖4和圖5所示。

結合圖4預測準確率和圖5訓練時間對比結果，基于MF的興趣點預測模型訓練耗時最短，但是準確率最低，這是因為MF模型并未考慮用戶屬性特征和歷史軌跡信息對下一個位置選擇的影響，只是對User-POI矩陣進行簡單分解，導致準確率較低;基于HMM的預測模型準確率略低于基于SimpleRNN，不過訓練耗費的時間卻遠遠高于后者，因為HMM在計算狀態(tài)轉移矩陣時，受隱狀態(tài)以及階數(shù)影響很大，當數(shù)據(jù)量較大時，耗時較長，本文將HMM模型的階數(shù)設置為1，即考慮前一個軌跡信息對下個位置的影響，增加了歷史信息影響，因此準確率與SimpleRNN相差較小;本文提出的SG-LSTM模型相較于Single-LSTM準確率提升超過1%，而且訓練時間也明顯降低，是由于相似用戶簇對用戶的歷史信息進行了增強，使得模型學習到更加豐富的特征，因此準確率比Single-LSTM高。總的來說，基于RNN的模型預測性能優(yōu)于HMM和MF，而且SG-LSTM無論準確率還是訓練時間都優(yōu)于其他模型，也證明了本文模型的有效性。

5? 結? 論

本文研究了稀疏時空數(shù)據(jù)場景下用戶的軌跡預測問題，提出融合用戶屬性和歷史軌跡的用戶相似性度量框架，并在此基礎上提出基于相似用戶簇的軌跡預測模型SG-LSTM，緩解了軌跡預測模型的用戶歷史數(shù)據(jù)稀疏性和單一性問題，并且通過將軌跡語義化，使得預測結果更具有物理意義和實用價值;在真實的數(shù)據(jù)集上對模型性能進行實驗評估，結果表明，在具有稀疏性和單一性的時空數(shù)據(jù)中，SG-LSTM模型能夠較好地捕獲用戶的移動規(guī)律，有效緩解稀疏軌跡導致的上下文信息缺乏問題，軌跡預測的準確率達到87.90%，優(yōu)于傳統(tǒng)軌跡預測模型。SG-LSTM模型具有廣泛的應用前景，例如可用于城市區(qū)域規(guī)劃、智能交通疏導和基于位置的個性化服務，在實際應用中具有較高的價值。

參考文獻：

[1] 徐彪，霍歡，陳尚也，等.基于位置服務的軌跡預測方法 [J].小型微型計算機系統(tǒng)，2016，37（6）：1191-1196.

[2] ALAHI A，GOEL K，RAMANATHAN V，et al. Social LSTM：Human Trajectory Prediction in Crowded Spaces [C]//2016 IEEE Conference on Computer Vision and Pattern Recognition （CVPR）.Las Vegas：IEEE，2016：961-971.

[3] LEE N H，CHOI W，VERNAZA P，et al. DESIRE：Distant Future Prediction in Dynamic Scenes with Interacting Agents [C]//2017 IEEE Conference on Computer Vision and Pattern Recognition （CVPR）.Honolulu：IEEE，2017：2165-2174.

[4] ZHENG Y，LIU Y C，YUAN J，et al. Urban Computing with Taxicabs [C]//Proceedings of the 13th ACM International Conference on Ubiquitous Computing.Beijing：Ubicomp，2011：98-98.

[5] 孫未未，毛江云.軌跡預測技術及其應用——從上海外灘踩踏事件說起 [J].科技導報，2016，34（9）：48-54.

[6] 李寒露，解慶，唐伶俐，等.融合時空信息和興趣點重要性的POI推薦算法 [J].計算機應用，2020，40（9）：2600-2605.

[7] GIANNOTTI F，NANNI M，PINELLI F，et al. Trajectory pattern mining [C]//Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining.New York：Association for Computing Machinery，2007：330-339.

[8] GAMBS S，KILLIJIAN M，NUNEZ M. Next place prediction using mobility Markov chains [C]//EuroSys 2012 Workshop on Measurement，Privacy，and Mobility.New York：Association for Computing Machinery，2012：1-6.

[9] CHEN M，LIU Y，YU X. NLPMM：A Next Location Predictor with Markov Modeling [C]//Pacific-Asia Conference on Knowledge Discovery and Data Mining.Cham：Springer，2014.

[10] MONREALE A，PINELLI F，TRASARTI R，et al. WhereNext：a location predictor on trajectory pattern mining [C]//The 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York：Association for Computing Machinery，2009：637-646.

[11] 高雅，江國華，秦小麟，等.基于LSTM的移動對象位置預測算法 [J].計算機科學與探索，2019，13（1）：23-34.

作者簡介：張書欽（1978—），男，漢族，河南禹州人，副教授，博士后，主要研究方向：物聯(lián)網(wǎng)、數(shù)據(jù)挖掘、網(wǎng)絡攻防、無線網(wǎng)絡;王金洋（1995—），男，漢族，河南周口人，碩士研究生在讀，主要研究方向：大數(shù)據(jù)挖掘、自然語言處理;白光耀（1996—），男，回族，河南鄭州人，碩士研究生在讀，主要研究方向：物聯(lián)網(wǎng)大數(shù)據(jù);張敏智（1998—），女，漢族，河南鄭州人，碩士研究生在讀，主要研究方向：物聯(lián)網(wǎng)大數(shù)據(jù)。