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

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

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

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

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

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

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

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

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

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

1? 相關(guān)工作

目前基于時空數(shù)據(jù)的軌跡預(yù)測工作主要分為基于模式的方法和基于模型的方法[7-9]。基于模式的方法首先從大量的歷史軌跡中發(fā)現(xiàn)頻繁軌跡模式，例如順序模式和周期模式等，然后將當(dāng)前查詢軌跡與頻繁軌跡模式進行匹配，從而達到軌跡預(yù)測的目的。Monreale等[10]提出了基于模式的軌跡預(yù)測模型WhereNext，該方法從移動對象的歷史軌跡數(shù)據(jù)中挖掘頻繁項集作為移動模式，并用該模式表示用戶頻繁訪問的地點，同時利用T-Pattern Tree查詢發(fā)現(xiàn)最優(yōu)匹配軌跡。基于模式的方法由于每次更新都需要重新挖掘頻繁項集，此外在面向稀疏或者單一性數(shù)據(jù)時可能存在無法挖掘頻繁模式的情況，導(dǎo)致預(yù)測效果不理想。LSTM作為時序數(shù)據(jù)處理的主流工具，在軌跡預(yù)測領(lǐng)域應(yīng)用廣泛。高雅等[11]為了解決馬爾可夫模型在處理長序列數(shù)據(jù)時存在的維度爆炸問題，提出位置分布式表示模型（LDRM），將高維的One-Hot位置表示向量嵌入到低維空間，并與LSTM結(jié)合，對移動對象的軌跡做預(yù)測研究，提升了預(yù)測準確性。

2? 術(shù)語定義及問題描述

定義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（軌跡序列）：軌跡序列由一系列按照時間排序的停留點構(gòu)成，記為TS={sp1，sp2，…，spn}，spi為第i個停留點，1≤i≤n。

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

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

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

3? 軌跡預(yù)測模型

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

3.1? 用戶相似性度量

3.1.1? 屬性相似度度量

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

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

（1）

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

（2）

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

3.1.2? 軌跡相似度度量

本文將軌跡相似度度量轉(zhuǎn)換為序列匹配任務(wù)，即兩條軌跡之間匹配度越高，則相似性越高，采用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]。當(dāng)simTS=0時，表示兩條軌跡完全不相似;當(dāng)simTS=1時，表示兩條軌跡完全重合。

3.1.3? 用戶相似性度量

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

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

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

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

由相似度度量式（4）可以度量任意兩個用戶之間的相似度，據(jù)此可得包含所有用戶的相似度查詢表。設(shè)定相似度閾值βs，依據(jù)查找表為每個用戶劃分相似用戶簇，得到最終的用戶簇集合。該算法優(yōu)點在于緩解了相似用戶分簇的冷啟動問題，當(dāng)出現(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;//設(shè)定用戶索引起始值

5.whilei≤ n-1

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

7.j = i//設(shè)定用戶索引起始值

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，則該算法關(guān)鍵步驟在于計算相似矩陣M，因此算法1時間復(fù)雜度為O，函數(shù)的表達式為（（n+12）·m+ m（m-1））。

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

稀疏軌跡通常呈現(xiàn)出單一性特點，軌跡序列包含POI類別個數(shù)較少，導(dǎo)致用戶歷史軌跡上下文信息大大減少，不能很好地反映用戶的實際移動偏好特征。本文將相似用戶的歷史軌跡集合作為該相似群體的整體歷史軌跡，用以豐富個體用戶地歷史軌跡，緩解個體用戶歷史軌跡上下文不足的問題，并在此基礎(chǔ)上提出基于相似用戶簇的軌跡預(yù)測模型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）; //獲取訓(xùn)練數(shù)據(jù)

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

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

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

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? 實驗及結(jié)果分析

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

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

4.2? 評價指標

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

（5）

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

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

為了找到更優(yōu)的參數(shù)組合，使得模型預(yù)測性能更高，分別設(shè)計了不同的參數(shù)組合進行實驗對比。圖2為每次輸入模型的軌跡點個數(shù)變化對模型預(yù)測準確率的影響，圖例中的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的軌跡預(yù)測模型、基于HMM的軌跡預(yù)測模型、基于SimpleRNN的軌跡預(yù)測模型和基于Single-LSTM的軌跡預(yù)測模型做準確率和預(yù)測效率對比，結(jié)果如圖4和圖5所示。

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

5? 結(jié)? 論

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

參考文獻：

[1] 徐彪，霍歡，陳尚也，等.基于位置服務(wù)的軌跡預(yù)測方法 [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] 孫未未，毛江云.軌跡預(yù)測技術(shù)及其應(yīng)用——從上海外灘踩踏事件說起 [J].科技導(dǎo)報，2016，34（9）：48-54.

[6] 李寒露，解慶，唐伶俐，等.融合時空信息和興趣點重要性的POI推薦算法 [J].計算機應(yīng)用，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的移動對象位置預(yù)測算法 [J].計算機科學(xué)與探索，2019，13（1）：23-34.

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