基于手機信令數據的用戶位置預測方法研究

吳雨佳，尹偉石，孟品超

（長春理工大學 數學與統計學院，長春 130022）

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

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

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

1 LSTM神經網絡

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

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

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

三個門的計算方式為：

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

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

圖1 LSTM神經單元結構

2 基于LSTM的位置預測

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

2.1 手機信令數據預處理

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

表1 手機信令主要字段

2.1.1 數據篩選

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

2.1.2 數據預處理

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

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

圖2 可迭代的數據清洗算法

2.2 區域功能標注

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

2.3 停留點提取

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

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

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

2.4 基于LSTM的位置預測模型

圖3是基于LSTM的位置預測網絡結構。

圖3 基于LSTM的位置預測網絡結構

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

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

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

圖4 Embedding層任務示意圖

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

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

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

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

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

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

3 實驗與分析

3.1 實驗數據

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

3.2 預測評價標準

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

3.3 預處理數據沉降效果

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

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

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

圖6 數據預處理各階段數據量變化分布圖

3.4 實驗設置

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

表2 LSTM模型參數

3.5 模型評價

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

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

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

4 結論

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