吳雨佳，尹偉石，孟品超

（長春理工大學 數(shù)學與統(tǒng)計學院，長春 130022）

隨著移動通信技術的發(fā)展和互聯(lián)網(wǎng)的普及，人們對手機的依賴性越來越強，由此產(chǎn)生了大量的手機信令數(shù)據(jù)。手機信令中的用戶位置信息可以為各類服務提供重要支持。在近期流行的新型冠狀病毒的傳染病防控工作中，對傳染源移動軌跡的追溯以及武漢封城后大規(guī)模人員遷徙的統(tǒng)計監(jiān)測都利用了手機信令數(shù)據(jù)中的位置信息。另外在廣告投放、店鋪推薦、交通狀況監(jiān)測、道路流量分析等問題中，手機信令數(shù)據(jù)也發(fā)揮了重要的作用。其中，位置預測是實現(xiàn)上述應用場景問題的關鍵，因此提出有效的位置預測方法具有重要意義。

從數(shù)據(jù)來源上說，位置預測研究大多采用GPS定位數(shù)據(jù)，因為這部分數(shù)據(jù)定位精度較高；而利用通信基站測算的位置數(shù)據(jù)精度相對較低，因此位置預測研究相應較少。從研究方法來說，常用方法有馬爾可夫鏈（MC）模型［1-2］、頻繁模式挖掘［3-5］和深度學習方法等。近年來，深度學習中的循環(huán)神經(jīng)網(wǎng)絡因擅長時序數(shù)據(jù)的預測而在位置預測中逐漸得到應用，在基于GPS定位數(shù)據(jù)的位置預測研究中取得了一定的進展。Liu 等人［6］提出了 ST-RNN（spatial temporal-RNN）算法，用移動對象歷史時空數(shù)據(jù)訓練RNN網(wǎng)絡，預測用戶在某個時刻的位置；許芳芳［7］提出基于時空特性的LSTM模型，在LSTM網(wǎng)絡的基礎上添加處理用戶移動行為時空信息的門，解決了現(xiàn)有研究時空特征關聯(lián)不足的問題；Yao等人［8］結合用戶的時空轉(zhuǎn)移特征以及用戶活動，將GPS軌跡轉(zhuǎn)化為具有語義特征的軌跡，提出了基于語義的循環(huán)模型（SERM，semantics enriched recurrent model），有效地捕獲了基于位置語義的時空移動模式和用戶偏好。相對于GPS定位數(shù)據(jù)，更為豐富的數(shù)據(jù)來自于蜂窩通信系統(tǒng)基站定位的數(shù)據(jù)，由于這部分定位數(shù)據(jù)質(zhì)量相對較差，定位精度受基站所采取的定位技術的影響而水平不一，因此在位置預測上較有難度。錢琨［9］對基于蜂窩信令數(shù)據(jù)的位置預測展開相關研究，其采用TDOA定位技術產(chǎn)生的定位數(shù)據(jù)，該種定位技術相對Cell-ID定位技術誤差更小，但是其精度仍然不如GPS定位技術。在軌跡數(shù)據(jù)預處理上，作者采用聚類算法去除離群點，基于卡爾曼濾波去除噪聲數(shù)據(jù)；在位置預測方法上，采用層次聚類的方式對用戶進行分組，建立一種橫向的預測方法，基于頻繁序列模式挖掘算法挖掘軌跡模式，構建預測樹進行預測。崔家祥［10］利用Cell-ID定位技術獲取的移動通信數(shù)據(jù)為研究對象，將狀態(tài)定義為具有功能屬性的基站的集合，使用一種加權馬爾可夫模型對用戶位置進行預測，綜合考慮距離預測時刻最近的k個狀態(tài)的影響。以上頻繁模式挖掘的算法效率低下，多階馬爾可夫模型使得轉(zhuǎn)移矩陣的規(guī)模膨脹，預測復雜度高。除此之外，上述基于手機信令數(shù)據(jù)的位置預測方法都沒有考慮軌跡序列位置間的上下文關聯(lián)。

為了更好地利用手機信令定位數(shù)據(jù)進行位置預測，本文構建了強化位置間前后關聯(lián)的LSTM預測方法。首先提出一種循環(huán)迭代的數(shù)據(jù)清洗方法，去除冗余定位數(shù)據(jù)的同時完整保留了用戶的有效位置信息；接著采用時間閾值的方法提取停留點，結合背景地理信息得到用戶語義化的軌跡；最后采用降維的方法將稀疏的one-hot位置編碼轉(zhuǎn)化成位置嵌入向量，與LSTM網(wǎng)絡結合成基于LSTM的位置預測模型。該模型在考慮用戶移動行為具有相似性和實效性的基礎上，對歷史位置序列進行降維并將位置間的語義關聯(lián)隱含到位置嵌入向量中，從而達到良好的預測效果。

1 LSTM神經(jīng)網(wǎng)絡

LSTM模型是傳統(tǒng)RNN模型的一個拓展，存在控制存儲狀態(tài)的結構，有著比RNN模型更好的學習長期記憶信息的能力。LSTM網(wǎng)絡主要改進在兩個方面：新的內(nèi)部狀態(tài)和門機制。LSTM網(wǎng)絡引入一個新的內(nèi)部狀態(tài)（internal state）ct專門進行線性的循環(huán)信息傳遞，同時非線性輸出信息給隱藏層的外部狀態(tài)ht。

其中，ft、it和ot分別為遺忘門、輸入門和輸出門，用來控制信息傳遞的路徑；⊙為向量點乘運算；ct-1為上一時刻的記憶單元；是通過非線性函數(shù)得到的候選狀態(tài)。

在每個時刻t，LSTM網(wǎng)絡的內(nèi)部狀態(tài)ct記錄了到當前時刻為止的歷史信息。遺忘門ft控制上一個時刻內(nèi)部狀態(tài)ct-1需要遺忘多少信息，輸入門it控制當前時刻的候選狀態(tài)有多少信息需要保存，輸出門ot控制當前時刻的內(nèi)部狀態(tài)ct有多少信息需要輸出給外部狀態(tài)ht。

三個門的計算方式為：

其中，σ(·)為 logistic 函數(shù)，其輸出區(qū)間為 (0,1)；xt為當前時刻的輸入；ht-1為上一時刻的外部狀態(tài)。公式（3）—（6）中的W*，U*，b*為可學習的網(wǎng)絡參數(shù)，其中*∈{f,i,o,c}。

圖1給出了LSTM網(wǎng)絡的循環(huán)單元結構，其計算過程為：（1）首先利用上一時刻的外部狀態(tài)ht-1和當前時刻的輸入xt，計算出三個門以及候選狀態(tài)t；（2）結合遺忘門ft和輸入門it來更新記憶單元ct；（3）結合輸出門ot，將內(nèi)部狀態(tài)的信息傳遞給外部狀態(tài)ht。

圖1 LSTM神經(jīng)單元結構

2 基于LSTM的位置預測

基于LSTM的位置預測研究主要由四部分組成，即將原始的手機信令數(shù)據(jù)轉(zhuǎn)化為目標形式數(shù)據(jù)的預處理部分，劃分基站小區(qū)范圍并標注功能部分，提取停留點生成軌跡位置序列部分和基于LSTM的根據(jù)歷史位置序列學習運動模式的預測模型部分。

2.1 手機信令數(shù)據(jù)預處理

運營商采集到的手機信令主要字段如表1所示，采集的信令事件包括接打電話、收發(fā)短信、開關機、位置更新、BSC切換和尋呼。

表1 手機信令主要字段

2.1.1 數(shù)據(jù)篩選

原始信令數(shù)據(jù)存在字段缺失、每日數(shù)據(jù)量過少、位置超出研究范圍等問題，為了提高數(shù)據(jù)質(zhì)量，首先對手機信令數(shù)據(jù)進行篩選，方法如下：①刪除存在字段缺失的數(shù)據(jù)；②刪除多余字段，只保留用戶編號、信令發(fā)生時間和基站編號；③篩選出一天大于100條信令的用戶；④用基站編碼將手機信令數(shù)據(jù)表和基站位置數(shù)據(jù)表匹配，篩選出密集城區(qū)的用戶。

2.1.2 數(shù)據(jù)預處理

當蜂窩網(wǎng)絡系統(tǒng)處于非理想信道環(huán)境時，無線信號的傳播受到干擾而產(chǎn)生定位誤差，使得采集到的手機信令數(shù)據(jù)存在大量的噪聲，包括漂移、乒乓切換和靜止冗余定位數(shù)據(jù)，不利于用戶真實軌跡的提取，需要根據(jù)各類噪聲數(shù)據(jù)的特征予以去除。

去除噪聲數(shù)據(jù)后仍然存在不利于停留點提取的冗余位置信息，本文以基站小區(qū)作為停留點提取的最小單元，目標是對于連續(xù)的相同位置，只保留第一條和最后一條，并刪除未連續(xù)出現(xiàn)的定位點。針對上述任務設計了一種如圖2所示的可以多次循環(huán)迭代的數(shù)據(jù)清洗算法，該算法可以有效減少不利于停留點提取的冗余位置信息，在對每個用戶的數(shù)據(jù)進行瘦身的同時，完整保留了用戶有價值的位置信息。多次循環(huán)迭代清洗算法，能夠得到良好的數(shù)據(jù)沉降效果。

圖2 可迭代的數(shù)據(jù)清洗算法

2.2 區(qū)域功能標注

泰森多邊形又叫Voronoi圖，是根據(jù)平面上分散的點對空間平面進行剖分的方法，其特點是每個多邊形內(nèi)僅包含一個樣點，且多邊形內(nèi)的任何位置到該多邊形的樣點的距離最近，到相鄰多邊形內(nèi)樣點的距離遠。由于用戶通訊時所連接的基站默認是離用戶最近的基站，因此選用泰森多邊形法對基站小區(qū)的覆蓋范圍進行劃分。對于每一個Voronoi區(qū)域，利用高德地圖周邊搜索服務API抓取興趣點信息，統(tǒng)計各類興趣點的數(shù)量，將占比最高的那一類作為該基站小區(qū)的功能標識。

2.3 停留點提取

本文所研究的手機信令定位數(shù)據(jù)采用Cell-ID的定位技術，即以基站的位置粗略表示用戶的位置?？紤]到基站的服務半徑在城市約為幾百米，這個地理空間大小符合用戶停留點的活動范圍，因此本文以基站小區(qū)作為停留點提取的最小單元，以1小時為時間閾值，將在基站小區(qū)內(nèi)停留時間大于1小時的位置點提取出來，并記錄其開始時間和結束時間，得到用戶停留點位置序列。構建移動對象所有n個位置的集合S={L1,L2,…,Ln}，用戶的停留點由位置Li和開始時間ti構成的二元組表示，Ti=＜Li,ti＞。用戶停留點構成的長度為h的歷史位置序列如式（7）所示。

將歷史位置序列匹配上一步中標注的基站小區(qū)功能，可以得到直觀的含有用戶語義信息的位置序列，如式（8）所示。

移動對象的位置預測問題定義為：設h個歷史位置序列構成的歷史軌跡為H={T1,T2,…,Th}，當前軌跡為T′={＜Li,ti＞},0≤i≤t，預測移動對象在t+1時所在的位置Lt+1。

2.4 基于LSTM的位置預測模型

圖3是基于LSTM的位置預測網(wǎng)絡結構。

圖3 基于LSTM的位置預測網(wǎng)絡結構

不同于粒子的無規(guī)則運動，移動對象在每個時刻出現(xiàn)的位置是存在某種關聯(lián)的，即當前時刻的位置與之前時刻的位置是相關的，可以用條件概率表示。設一個長度為N的位置序列出現(xiàn)概率為P(L1,L2,…,LN)，假設在一段位置中，移動對象的位置與前t個位置有關，條件概率如式（9）所示。

構成軌跡序列的各個位置是離散的編碼，比如1表示XX大學，2表示商業(yè)區(qū)，3表示景區(qū)，4表示高鐵站，對于［1，2，3］和［1，2，4］兩種軌跡情況可能蘊含不同的語義信息。向量［1，2，3］和向量［1，2，4］通過歐式距離計算相似度會比較接近，但實際是兩種完全不同的語義軌跡，這種離散的編碼無法直接進行訓練，需要先轉(zhuǎn)換成向量。Embedding是把離散的編碼轉(zhuǎn)化為向量的關鍵路徑。

設移動對象歷史位置序列共有n個位置，將所有位置按出現(xiàn)次數(shù)降序排列并賦予從1到n的編號，再對所有位置進行one-hot編碼。One-hot編碼將n個離散的編號轉(zhuǎn)化為長度為n的向量，在編號對應的位置上賦值為“1”，其余位置賦值為“0”。Embedding層的訓練任務是找到一個矩陣Vn×m，將n維的one-hot位置向量降成m維的位置嵌入向量，并將位置間的語義關聯(lián)隱含到位置嵌入向量中，使得P(Li|Li-t,Li-t+1,…,Li-1)最 大化，如圖4所示。權重矩陣Vn×m由神經(jīng)網(wǎng)絡結構結合下游預測任務隨模型一起訓練，通過反向傳播不斷地調(diào)整網(wǎng)絡參數(shù)，位置嵌入向量實際就是權重矩陣中對應位置上的向量。

圖4 Embedding層任務示意圖

經(jīng)過embedding層對稀疏的one-hot向量降維后，離散的位置編碼被轉(zhuǎn)化為低維度的含有上下文信息的位置嵌入向量，從而使得基于LSTM的位置預測算法可以更好地處理位置預測問題。

根據(jù)上文對位置預測問題的定義，采用滑動窗口的方法構建訓練數(shù)據(jù)，將所有的移動對象的軌跡序列分割并轉(zhuǎn)化為可訓練的固定長度的輸入和輸出樣本集，如圖5所示。

圖5 滑動窗口法生成樣本集

構建好訓練數(shù)據(jù)后就有了理想狀態(tài)下的輸出向量。用softmax激活函數(shù)對全連接層輸出的logits向量進行歸一化處理得到一個n維的概率分布，代表在各個位置上取值的概率，如式（10）所示。

將目標位置以one-hot向量表示，記為oi，于是損失函數(shù)為：

使用梯度下降的方法反向傳播更新網(wǎng)絡的參數(shù)。經(jīng)過LSTM根據(jù)訓練數(shù)據(jù)調(diào)整神經(jīng)元之間權重的學習過程，得到一個全局的位置預測模型。該模型利用語言模型中學習詞嵌入的思想構建Embedding層，將位置間的語義關聯(lián)隱含到位置嵌入向量中，同時降低輸入LSTM網(wǎng)絡結構的訓練向量的維度，降低了模型訓練的復雜度。通過LSTM網(wǎng)絡的門控機制，解決了處理長序列時容易產(chǎn)生的歷史信息損失、梯度消失和梯度爆炸等問題，能夠較好地應用于移動對象的位置預測。

3 實驗與分析

3.1 實驗數(shù)據(jù)

本文以長春市聯(lián)通用戶2019年8月份的手機信令數(shù)據(jù)作為實驗數(shù)據(jù)，該數(shù)據(jù)集共有約524.56萬個用戶，考慮到每天產(chǎn)生信令數(shù)小于100條不足以準確反應用戶的移動軌跡，過濾掉這部分用戶后剩余共15 231人的13 281.90萬條數(shù)據(jù)。將用戶的手機信令數(shù)據(jù)與基站經(jīng)緯度進行匹配，結果顯示有14 198人在這1個月期間有長春市市區(qū)以外的活動軌跡，本實驗以長春市區(qū)作為研究范圍，最終符合條件的有1 033個用戶的共708.15萬條數(shù)據(jù)，從中隨機選擇180個用戶的手機信令數(shù)據(jù)作為本次實驗的最終數(shù)據(jù)。

3.2 預測評價標準

本文的預測目標是用戶下一個可能去的位置，但是為了體現(xiàn)LSTM模型在預測長序列方面的能力以及以往在文本生成中的良好表現(xiàn)，除了下一步位置的預測精度，嘗試展示以下連續(xù)多步位置的預測精度。為此定義一個n單位步長精確度（n-gram precision），設n為當前位置后面想要預測的長度為n的位置序列，pli為第i個位置的預測結果，tli為第i個位置的真實結果，若當i≤k，(1≤k≤n)時，對于任意的i滿足pli=tli，則預測步長記為k-gram。設共有K個測試樣本，用 num()計數(shù)，num（k-gram）表示預測步長為k-gram的樣本數(shù)，則k(k≤n)單位步長精確度k-gram precision計算方式如式（12）所示。

3.3 預處理數(shù)據(jù)沉降效果

數(shù)據(jù)預處理各階段的效果可以用數(shù)據(jù)經(jīng)過每一步處理后的數(shù)據(jù)減少率來描述。統(tǒng)計每個用戶信令數(shù)據(jù)在依次經(jīng)過去漂移、去冗余、去乒乓切換和再次去冗余后剩余的信令條數(shù)，用絕對數(shù)據(jù)沉降率Ai來表示各階段處理后信令數(shù)據(jù)累計減少的程度，用相對數(shù)據(jù)沉降率Ri來表示各階段本身對數(shù)據(jù)的沉降能力，計算公式如下：

其中，D*為用戶數(shù)據(jù)在預處理各階段后信令減少的數(shù)目；Ntotal為原始信令條數(shù)；i取 1，2，3分別表示去漂移、去冗余、去乒乓切換，i＞3時每增加1表示迭代一次數(shù)據(jù)清洗算法。

數(shù)據(jù)預處理各階段后，數(shù)據(jù)量的變化情況如圖6所示。從圖中可以看出，在去乒乓步驟后，數(shù)據(jù)沉降率在30%～60%的人占比最大，經(jīng)過一次迭代清洗冗余數(shù)據(jù)的算法后，幾乎所有人的數(shù)據(jù)沉降率都達到了50%～100%之間，經(jīng)過兩次迭代后，此時相對第一次清洗后的數(shù)據(jù)量減少量大部分在0%～30%之間，說明再次清洗仍然可以去除冗余數(shù)據(jù)，經(jīng)過二次迭代后，絕對數(shù)據(jù)沉降率整體相對第一次有了提升，說明數(shù)據(jù)清洗算法具有良好的效果。

圖6 數(shù)據(jù)預處理各階段數(shù)據(jù)量變化分布圖

3.4 實驗設置

隨機抽取180個用戶的原始信令數(shù)據(jù)共有132.89萬條，位置集合S共3 296個位置。在對實驗數(shù)據(jù)進行預處理后，將180個用戶的前27天的手機信令數(shù)據(jù)作為訓練集，后3天數(shù)據(jù)作為測試集，對用戶軌跡數(shù)據(jù)提取停留點，轉(zhuǎn)化為停留點位置序列。對訓練集和測試集中提取出的停留點位置序列，使用滑動窗口的方式劃分輸入和標簽，設滑動窗口長度len=5，滑動步長step=1。輸入一段待預測位置序列，模型輸出一個預測結果的概率分布，采用隨機采樣策略生成一個位置；把這個位置加入到輸入位置序列并將滑動窗口前移，生成新的輸入再預測下一個位置，依次類推，生成一個長度為5的預測結果序列。通過多次實驗調(diào)整模型參數(shù)，最終確定LSTM位置預測模型中部分參數(shù)的最優(yōu)值如表2所示。

表2 LSTM模型參數(shù)

3.5 模型評價

加載上一小節(jié)中用最優(yōu)參數(shù)進行訓練時保存的模型，對測試集中的待預測位置序列進行預測。遍歷測試集所有樣本，對每個待預測位置序列預測下5個單位步長的位置，保留每次的預測結果，計算n-gram precision（此時n取5）。為了驗證基于LSTM的位置預測模型具有更好的預測效果，本文將基于LSTM模型的預測結果與文獻9中橫向的頻繁序列模式挖掘算法、文獻10中加權馬爾可夫模型當階數(shù)為5時（階數(shù)為5時模型達到最高準確率）的預測結果進行對比分析。為了統(tǒng)一評價標準，將加權馬爾可夫模型在不同時段的預測準確率的均值作為該模型準確率，結果如圖7所示。

圖7 位置預測模型的n步預測精度

由圖7可知，本文的LSTM位置預測模型對下一個位置（1-gram）的預測精度高達79%，明顯高于加權馬爾可夫模型（weighted-MM）的70.1%和頻繁序列模式挖掘（FSPM）模型的61%，說明本文的LSTM位置預測模型在位置嵌入向量的加持下，能夠較好地表達位置間的上下文關聯(lián)，得到更加準確的預測結果。隨著預測步長的增加，加權馬爾可夫模型預測準確率迅速下降，而LSTM模型和FSPM的準確率下降相對緩慢。這是由于FSPM模型利用分組的方法對用戶聚類，使得可預測距離有了一定改善；LSTM模型得益于門控機制對歷史信息的記憶，對較長的可預測序列也具有一定潛力?？傮w來說，本文基于LSTM的位置預測模型具有較高的預測精確度。

4 結論

本文提出一種基于手機信令數(shù)據(jù)的LSTM位置預測方法。使用運營商提供的真實的用戶手機信令數(shù)據(jù)進行實驗。針對手機信令數(shù)據(jù)的特點，提出一種循環(huán)迭代的數(shù)據(jù)清洗方法，經(jīng)實驗數(shù)據(jù)驗證，在預處理后期多次迭代該算法能夠達到良好的數(shù)據(jù)沉降效果，有利于停留點提取。本文建立一個強化位置間語義關聯(lián)的LSTM位置預測模型，采用矩陣降維的方法構建embedding層，將稀疏的one-hot位置編碼轉(zhuǎn)化成位置嵌入向量，強化位置間的語義關聯(lián)，并降低輸入LSTM網(wǎng)絡的數(shù)據(jù)維度。實驗證明本文的基于手機信令數(shù)據(jù)結合LSTM的位置預測算法具有良好的預測效果。在今后的工作中希望可以將降維程度與預測精度的關系進行量化，進一步優(yōu)化模型。