本節書摘來自華章出版社《移動資料挖掘》一 書中的第2章，第2.2節，作者連德富 張富峥 王英子 袁晶 謝幸，更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視。
前面提到過移動資料有多種類型，可能是人們攜帶智能裝置收集的gps軌迹資料，也可能是利用公交卡乘坐的公共汽車或地鐵的資訊，還可能是人們在移動社交網絡中分享的地點通路資訊，甚至是收集基站通信時留下的日志資訊解析出的位置資料。在這些移動資料中，資料缺失是一種常見的現象。比如，當人們進入高樓大廈時，智能裝置無法很好地與衛星定位系統進行通信，使得gps可能很難對人們進行精确的定位。盡管結合基站定位或wi-fi定位，定位的方法得到了很大的改進，但是問題并沒有得到徹底的解決。因而，人們通過智能裝置擷取的位置資料仍可能是缺失的或不精确的。再比如，人們在用公交卡乘坐公共汽車時，大部分仍然可能是隻在上車的時候刷卡，進而無法獲得人們下車的地點。再比如說，雖然人們願意通過移動社交網絡等分享自己的位置資訊，但是涉及隐私地點、無趣地點的通路時 ，人們可能會故意地隐藏，這也會造成移動資料的缺失。而且現在人們分享位置資訊的形式多種多樣，可能是從資料庫中選擇出來的，也可能是人們自己建立的，但人們在建立的時候并沒有填充相關的語義資訊，這也會造成語義資料的缺失。最後，人們在打電話或發短信時，會通過與基站的通信留下自己的位置，但是人們隻有很少一部分時間是用于打電話或發短信的，因而有大量時間的位置資訊也是缺失的。針對這些缺失的情形，有些是可以通過技術手段解決的，有些卻是無法通過技術手段解決的。在這些可以用技術手段解決的缺失問題中，有些可以通過時間序列中的值缺失解決方法來解決，有些可以通過矩陣填充的方法來解決，還有些可能需要根據實際情況運用資料挖掘的方法進行分析。下面将介紹兩種重要的缺失資料補全解決方案。
智能卡，比如信用卡、校園卡、公共交通卡，包含了豐富的人的行為資訊。特别是記錄了人的移動資訊的智能公交卡，裡面豐富的資料對于很多行業的人來說都是極具吸引力的，比如城市規劃者和提供地點相關服務的從業人員。近些年基于智能公交卡資料的研究有很多，諸如行為模組化和個性化推薦工作。但是由于許多智能系統的搭建都是以盈利為目的的，或者系統記錄資料隻是為了友善管理，記錄的資料往往不夠全面。比如單一票價的公交系統，一般就不會記錄乘客上車和下車的站點，對于這種資料，如果能恢複出乘客完整的出行路線，将非常有利于後續的研究。在公交系統的資料中存在三種平行的資料空間：消費空間、時間空間和地理空間。圖2.5a展示了三種不同的空間之間的對應關系。消費空間包括了卡的餘額、充值金額和一次乘車行為的消費金額，卡的餘額會在充值後上升，在乘車後下降，并且消費和充值行為都對應了時間空間裡的一些點（如圖2.5a所示）。在乘車過程中，乘客的地理移動和時間空間也是互相對應的，圖2.5a中，時間空間中的實線表示乘車行為，虛線表示在這段時間裡面乘客沒有乘車。
除了有乘坐公共汽車的用途以外，很多智能公交卡還可以被用來乘坐計程車甚至去商場消費，使得公交系統記錄的資料在消費空間上常常是不連續的。為了保證消費空間的連續性，需要将個人消費記錄進行分割。
通過這樣的分割算法，一個分割段中的消費記錄就是連續的了。值得強調的是，這裡的每個分割段中都可以包含很多天的資料。在一個分割段中，可以将乘客的行為定義成兩種：行程内轉移和行程外轉移。定義2（行程内轉移和行程外轉移） 給定一個分割段s={l1,l2,…,lm}，其中li是一條從上車地點oi到下車地點di的公交行程，我們稱oi→di是行程内轉移，乘客在這期間的移動完全受公交的限制（順着公交線路延伸），兩個連續的行程之間的行為稱為行程外轉移，比如，di→oi+1。乘客在行程内和行程外的轉移都具有很多種可能性，比如在一次乘車行為中，假設該條公共汽車線路有n個不同的站點，并且乘客的上車站和下車站不同，那麼這次乘車就有n(n-1)種可能的轉移。給行程内和行程外的行為加上在不同空間（消費空間、時間空間、地理空間）的限制，可以大大減小可能的轉移數目。距離限制（對于行程外轉移） 城市裡人們的換乘距離往往是有上限的。如圖2.5b所示，l1和l2是乘客u的兩趟連續的公交行程，如果u隻通過步行來完成l1和l2之間的換乘，那麼可以認為這個距離不會超過某個範圍。假設乘客u從a和b點出發的步行範圍是兩個以距離r為半徑的圓形，分别以a和b點為圓心，那麼通過三角不等式可以得出，a和b點的距離應該小于2r。在一次行程外行為中，滿足距離限制的換乘站可以是0對（乘客可能通過别的交通方式從l1移動到l2，并且距離超過了2r），這種行程外轉移的節點被稱為漂移點，從漂移點将分割段分割成兩個子段，這樣每個分割段不僅在消費空間上是連續的，在地理空間上也是連續的。票價限制（對于行程内轉移） 公交系統中通常有兩種公交線路：階梯票價線路和非階梯票價線路。對于非階梯票價線路，每次行程的票價都是固定的，而對于階梯票價線路，票價則是根據上車和下車站點的距離來決定的，比如北京的階梯票價計算方式為e=a+b·max(boarding-alighting-c,0)，其中e是票價，a、b、c是系統參數，對于不同的公交線路有不同的數值，這個公式說明當行程不大于c千米時，票價是a，否則每多1千米需要多付b元。實驗中計算每次行程的可能票價，并且與乘客的真實消費相比較，可以大大減少可能的行程數目。時間限制（對于行程内和行程外轉移） 如北京的公交系統，非階梯票價線路會記錄乘客的上車時間，階梯票價線路會記錄乘客的下車時間。雖然每段行程隻記錄一次時間，我們仍然可以用時間限制來過濾掉很多不可能的轉移。用t1、t2、t3分别表示三段行程li=(oi，di)（i=1,2,3）的時間戳。如圖2.6a所示，l1和l2是兩條非階梯票價線路，l3是一條階梯票價線路。可以用距離和每段公路的限速來估計oi和di之間的最小時間△ti。那麼圖2.6a中的線路需要滿足以下條件：
有限制的半監督crf模型 條件随機場（crfs）［53］在資料挖掘和機器學習領域中有着廣泛的應用，特别是線性crf模型，定義了由觀察序列到隐藏序列的條件機率，構成了一個無向的圖模型。事實上，給定了一個分割段的候選行程後，恢複資料的問題就轉化成了在序列中對資料進行标記的問題了。具體來說，是先構造一個線性crf模型：給定一個分割段s={l1，l2,…，lm}，用xi=(li，li+1)（對于i=1,2,…，m-1）來表示觀察序列，也就是說，連續兩條線路之間的行程外轉移在crf序列中被包含在一個節點中（如圖2.6b所示，在這裡一個節點表示兩條線路），用yi=(yi1，yi2，y3i)表示一個行程内轉移和緊接着的一個行程外轉移的三元組(oi，di，oi+1)（i=1,2,…,m-1），序列y={y1,y2,…,ym-1}就是隐藏序列（也稱标記序列）。對于标記資料足夠多的crf序列，通常使用em算法或梯度法來訓練對數似然函數
其中是訓練序列，n是長度。對于标記資料不夠多的模型，可以使用有限制的半監督crf模型來解決問題。具體來說，給定一個限制方程g(y,x)和一個未标記的資料集，廣義期望标準可以定義為
其中p(x)是資料集的經驗分布，e［·］表示期望值，s是表示模型期望和目标期望之間的內插補點的得分函數。這個函數可以用梯度法來優化。
根據參考文獻［139］中提供的統計資訊，在移動社交網絡whrrl和foursquare中，大約有30％的地點是缺失語義資訊的。語義資訊對後續的挖掘具有重要的意義，因而，迫切需要對這些語義資訊進行填充。填充的可行性來自于“具有類似語義的地點具有相似的模式”的發現，比如說大家去餐館吃午飯的時間基本上都是中午。為此，葉懋（音譯）等人在參考文獻［139］中将填充問題歸結為一個多标簽分類問題，對每一個地點的每個類别标簽，均采用二分類的算法進行分類。在分類器的特征中，作者提出利用地點的顯性模式和相似地點的隐性相關性。顯性模式是針對來自某個地點的所有通路資料得到的統計資訊，比如通路時間分布、通路次數。由于帶有不同語義标簽的地點可能會有不同類型的時間分布，因而可以利用地點的時間分布來填充語義資訊。舉例來說，圖2.7a和圖2.7b給出了whrrl資料上關于學校類地點和酒吧類地點在一個星期的不同天中的分布，以及餐館和商店在一天的不同小時中的分布。可以看到酒吧類地點的通路時間更多地集中在周末，而學校類的地點則更多地分布在工作日中。同樣，不同地點的通路頻率也有所不同，比如說，對于個人來講，醫院的通路頻率相較于餐館來說要低很多。因而，地點的連續兩次通路的時間間隔也是一個重要的名額。不過由于移動社交網絡資料中的稀疏性，這個統計名額可能會有較大的偏差，甚至對于很多地點無法計算。為此，可以考慮用地點的總通路人數和單個使用者的最大通路次數來進行替代。圖2.7c和圖2.7d給出了具有不同語義資訊的地點的分布差異性。願意和大家分享自己在醫院的人是非常少的，但是願意分享去餐館就餐的使用者卻會很多。同樣，對于常人來說，不可能每天都住在酒店；但是民以食為天，人們經常去餐館便是可能的。
不過這些統計資訊并沒有刻畫地點之間的相關性，使得缺乏足夠通路資訊的地點無法被很好地語義标注。因而，在本章中，作者提出利用相似地點的隐性相關性，将具有足夠多通路曆史地點的語義資訊傳播給缺乏足夠通路資訊的地點。相似地點的隐性相關性是通過地點的相似性網絡來刻畫的，相似性網絡可以通過使用者通路地點的規律性來建構。具體的做法是，它首先将所有使用者的移動資料處理成使用者地點的二部圖，以及通路時間段地點的二部圖。其中使用者地點二部圖中的連邊代表使用者通路過該地點，邊的權重為使用者對該地點的通路次數；而時間段地點二部圖中的連邊表示地點在這個時間段内被通路過，邊的權重為所有使用者在該時間段中通路該地點的總次數。在二部圖中利用帶重新開機動的随機遊走［126］，可以估計從某個地點節點開始遊走到其他地點節點的機率。特别地，從某個地點出發，要麼沿着二部圖中的邊進行随機遊走，或者從該地點節點重新開機動，直到收斂為止。假設對于任意的兩個地點i和j，分别對時間段地點和使用者地點二部圖運用帶重新開機動的随機遊走獲得的地點隐性相關性為rti,j和rui,j。這兩個地點的隐性相關性通過線性權重的方法進行結合，得到地點i和j的最終的隐性相關性rpi,j=ηrui,j+(1-η)rti,j。這裡的η是一個平衡系數。基于地點的隐性相關性，可建構相關地點的有向圖網絡。特别地，為每個地點選取最相似的k個地點，每個地點和k個最近鄰的地點形成相應的連邊，邊權不變。給定這種相關地點的相似性網絡，可以通過類似于半監督學習的方法來進行語義标簽的預測。特别地，某個地點屬于某個語義類别的機率是正比于與它相似地點的對應類别的機率的權重和。假設i表示為地點i的k最近鄰地點，那麼pr(yi=ti)就表示從地點i的k最近鄰地點推測地點i的類别為t的機率。這個機率是通過如下公式進行疊代估計的
即每次地點語義類别估計機率都是在上一次的機率估計基礎上更新的，其中z=∑j∈irpj,i是歸一化項，pr(n)(yi=ti)表示pr(yi=ti)的第n次疊代的估計。β(n+1)t=β(n)tα=β(0)tαn+1是權重系數，其中β(0)t為一個在0和1之間的常量，而α為小于1的非負衰減因子。而且由于不同語義類型的地點受k近鄰的影響也有所不同，是以β(0)t是與類别相關的，使得具有較小β(0)t值的語義類别地點受近鄰的影響較大，而具有較大β(0)t值的語義類别地點也受較不相似的地點的影響顯著。在獲得pr(yi=ti)後，可以通過與統計名額結合的方法來獲得最佳的地點語義資訊補全。