基于上下文的位置預測研究
2008-12-31 00:00:00李彩霞周集良曹奇英顧愛萍劉琳瑯
計算機應用研究 2008年11期
（東華大學 a.信息科學與技術學院; b.信息化辦公室， 上海 201620）
摘要：分析了現有的三種預測用戶下一時刻位置的方法，即概率模型、Markov模型、狀態模型。在此基礎上提出了一種基于普適計算上下文信息的學習模型，用logistic回歸解決分類問題。該模型可以很好很靈活地預測用戶的下一位置。
關鍵詞：普適計算; 上下文感知; 位置感知; 概率矩陣; 邏輯回歸
中圖分類號：TP391文獻標志碼：A
文章編號：1001-3695(2008)11-3325-03
Research on location prediction based on context
LI Cai-xiaa，b， ZHOU Ji-lianga， CAO Qi-yingb， GU Ai-pinga，b， LIU Lin-langa，b
(a.College of Information Science Technology， b.Informatization Office， Donghua University， Shanghai 201620， China)
Abstract:This paper analyzed three methods for predicting next location: probability model、Markov model and state model. Proposed a learning-based model based on context of ubiquitous computing environment well. Logistic regression was using to predict labels. The learning-based model could predict next location well and freely.
Key words：ubiquitous computing; context-aware computing; location-aware computing; probability matrix; logistic regression
普適計算環境通過感知設備感知人們的上下文信息，并進行上下文融合，推導出人們的服務需求，主動或被動地為人們提供服務。位置服務是上下文感知中研究最多的問題之一。移動設備大量涌現、低成本位置感知技術的出現、無線覆蓋范圍的不斷擴大、無線連接越來越可靠，這些更為普適計算在位置服務方面的研究拓寬了道路。當今，用戶攜帶無線移動設備，在旅途中請求獲得位置服務的應用已經很常見了，位置感知服務（LASs）已成為人們日常生活的一部分。位置感知服務架構建立在上下文感知設備基礎之上，需配套有地理信息系統、互聯網及無線網絡等技術的支持。例如最近停車位[1]、上下文感知導游系統[2]等。獲得移動設備的位置信息是位置感知服務的基本要求。獲得的方法各不相同，得到的位置的精確度也各不相同，常用方法有TDOA[3]、AOA[4]、GPS等。其中GPS只用于戶外，而TDOA和AOA可用于室內位置感知服務。
目前位置感知服務的研究主要是基于當前位置的服務，專門針對將來信息的位置服務比較少，而提前的位置服務恰恰對用戶來說非常有用。例如，用戶正在A地點，而系統通過上述的獲得位置方法，獲取到用戶位置后提供了A地點的服務，但是A地點的服務不是用戶希望的服務，用戶只能繼續尋找，當用戶前往尋找時，用戶并不知道往哪里走會有自己希望的服務，可能到了B地點后，才得知B地點沒有他想要的服務。為了避免給用戶帶來類似這樣的不必要的麻煩，提前提供服務是非常必要的。
本文提出了一種提前預測用戶行蹤的方法，通過提前預測用戶的行蹤，提前提供服務信息給用戶，如果用戶發現他要去的B地點沒有他要的服務，那么他可以盡早改變行車路線，而避免到了B地點再返回的麻煩。
1相關研究
在普適計算移動環境中，用戶的位置信息一般包括兩部分內容，即位置和時間，也就是說如果要描述用戶的位置，要用〈L， t〉來表示，即在t時刻用戶處在L位置。要估計用戶將來的位置，必須知道用戶當前的位置、時間以及相關的歷史數據。對位置移動的描述主要有單元描述法和地圖匹配法。
在單元描述法中，地理區域被分成形狀規則的單元，這些單元的判定通常是借助蜂窩網來實現的，將一個蜂窩看做一個單元。當確定用戶位置時，通過廣播信息確定用戶處于哪個蜂窩的覆蓋范圍，就用〈c， t〉來表示在t時刻用戶處于c蜂窩中。若用戶從地點A到地點B經歷了c1、c3、c6蜂窩，那么可以用蜂窩號的序列來表示用戶的移動路徑{c1c3c6}。但是這種用單元格序列來表示用戶的位置軌跡信息的方法有兩個缺陷：a）它不能精確確定用戶的位置，誤差最大可能達到單元的直徑那么大；b）它不能精確確定用戶的軌跡，因為一個單元可能覆蓋了好幾條路，而單元描述法只能知道在什么單元，而不知道用戶是經過了其中的哪幾條路。
地圖匹配法的精確度要比單元描述法高得多，該方法借助GPS的定位功能，將定位出來的用戶行駛路線和標準電子地圖進行匹配，找到最相似的路線作為用戶的行駛路線。這種方法可以較精確地描述出用戶的行駛路線，可以用用戶所經過的路口序列或者路名序列來描述。在基于地圖匹配的方法中，當用戶知道自己的目的地時非常容易，只要輸入用戶的目的地，根據電子地圖及GPS導航，可以很容易得到想要的服務。而很多時候用戶不知道自己要去哪里才能得到自己想要的服務，這就使得筆者要解決預測用戶將來位置的問題。目前在這方面的研究還很少，筆者提出一個可以判斷用戶將來走哪條路的方法，便于提前提供服務給用戶。本文將詳細討論地圖匹配法中的路徑預測方法。
2路徑預測模型
21環境介紹
本文的位置感知服務架構假設是在移動環境中，有服務基站，用戶帶有客戶端，他們之間通過無線網絡進行通信。假設無線網絡信號覆蓋所有用戶經過的地方，而且通信質量良好，每個客戶端有GPS定位功能。服務基站有數據庫存儲用戶的歷史數據，包括用戶的上下文歷史信息，尤其是歷史軌跡信息。
在定義此模型之前需先定義一些變量：Lk——用戶當前位置，即在tk時刻的位置，按照GPS定義的位置表示法表示；T——判斷周期，即tk+1-tk；G=〈V， E〉——表示道路圖，V為道路交叉點，E為道路。為了計算方便，將實際地圖規范化，如圖1所示。
22概率模型
該模型是用來預測tk+1時刻用戶的位置Lk+1，然后根據用戶將要去的位置Lk+1提醒相應的服務。用戶從一個地點到另一個地點一次，就產生一個軌跡，作為用戶的歷史數據存在服務器端的數據庫中。慢慢的數據庫中的數據越來越豐富，用戶的行蹤也越來越更可推測化。假設每條道路都是雙向的，因此道路圖可以看做是一個無向圖。對應的鄰接矩陣就可以構造出來。相應地，根據歷史行駛路徑，每個路口vi的概率矩陣就可以構造出來，在以用戶當前位置為根的樹中，用深度優先遍歷算法可以遍歷出將要到達的vi處的可選路徑，根據概率矩陣，選擇概率最大的作為預測路徑[5]。
概率模型雖然簡單，易計算，在歷史信息豐富的情況下準確率較高；但是在陌生環境或概率相同時，預測準確性較低。
23Markov模型
利用一個k步Markov預測器的核心任務是建立一個與一階Markov預測器的轉移概率矩陣同規模的轉移概率矩陣。矩陣的行元素代表移動用戶k步以前的vi位置，矩陣的列元素代表移動用戶下一步即將到達的vi+1位置。通過這個矩陣，就可以根據移動用戶k步以前的vi位置來預測其下一步即將到達的位置。
不同步數的Markov預測器的預測精度取決于具體應用環境對應的隨機過程中不同間隔的隨機變量之間的相關程度。如果Markov預測器選擇的步數等于相關程度最大的隨機變量的間隔數，則此步數Markov預測器將達到最佳效果。關于Markov模型的詳細步驟參見文獻[6]。
Markov模型由于頻率計數器而導致再學習能力下降，而且k階預測器應用在實時在線方面性能不是很好。
24狀態模型
狀態預測器[7]避免了Markov模型的上述缺點。當一個習慣改變后，新的習慣必須在作出預測之前馬上跟上之前的習慣。狀態預測器用有限狀態機（文中也稱為兩狀態預測器）的每個模式去代替Markov預測器中的頻率計數器。由模式的選擇和狀態機的使用構成的預測器，稱做兩級兩狀態預測器。此外還有自身兩級預測器、全局兩級預測器[8]等。
狀態預測器有個缺點就是容易在兩個弱狀態之間振蕩，導致此時的預測隨機性。
25學習模型
在上述的預測模型中，均沒有結合上下文的具體情況進行計算，而在普適計算環境中，主要研究的性質就是對象的上下文特征。在上下文信息很豐富的普適計算環境中，充分利用現有的上下文資源將勢在必行。利用學習模型，可以很靈活地將上下文信息和位置預測緊密結合起來。
在圖1中，用戶的當前位置見圖中圓點所示，用戶即將到達V2路口，此時存在的預測問題就是，當用戶到達V2路口后，用戶會選擇e5、e6、e12中的哪條路。可以將問題看成是一個多分類的情況。為了簡化問題，將多分類的問題轉換為多個兩分類的問題，并將e5、e6、e12看成是0、1、2三個類標的選擇。解決這種二分類問題，logistic回歸模型是有效的方法之一，該方法也是在一定的概率模型假定下推出的。假定y 的取值為0或1。
道路選擇的判別函數如下：
g1(x)=g(wTx)g0(x)=1-g(wTx)（1）
其中：x是一個d維特征向量，可以是任何普適計算的上下文信息[9]，w是d維特征對應的權向量數組。
首先考察函數：
hw(x)=g(wTx)=1/1+e-wTx（2）
其中：g(z)=1/1+e-z稱為logistic函數或sigmoid函數。
假定在給定x、w的條件下，y=1出現的概率服從伯努利分布，并可表示為
p(y-1｜x，w)=hw(x)p(y=0｜x，w)=1-hw(x)（3）
如上兩式可合并為緊湊形式：
p(y｜x，w)=hw(x)y(1-hw(x))1-y(4)
其中:y∈{0，1}。在n個獨立樣本數對情況下，樣本數據的似然函數為
L(w)=p(Y｜X，w)=∏ni=1p(y=yi｜xi，w)=
∏ni-1(hw(xi))yi(1-hw(xi))1-yi(5)
同樣，為計算方便，取對數似然：
l(w)=log L(w)=∑ni=1yilog hw(xi)+(1-yi)log (1-hw(xi))(6)
合理回歸就是恰當選擇w使得l(w)達到最大，即式（2）可以作為回歸的指標函數。對于式（2）的似然函數l(w)，回歸時應使之最大化。
下面推導式（2）的似然函數l(w)的梯度。為了運算方便，首先考慮一個數對{x=xi，y=yi}的情況，對式（2）求wj∈w的偏導：
l(w)/wj=(y/g(wTx)-(1-g(wTx)))g(wTx)/wj (7)由sigmoid函數的導數公式：
g′(z)=e-z/(1+e-z)2=(1/(1+e-z))(1-1/(1+e-z))=
g(z)(1-g(z))(8)
式（3）可變為
l(w)/wj=(y/g(wTx)-((1-y)/(1-g(wTx)))g(wTx)(1-g(wTx))wTx/wj=(y(1-g(wTx)-(1-y)g(wTx)))xj=(y-hw(x))xj(9)
考慮到微分算子的線性性質，得出對數似然函數的梯度：
l(w)=∑ni=1[yi-hw(xi)]xi (10）
可得w的梯度解的迭代公式為
w(k+1)=w(k)+ρk∑ni=1[yi-f(w(k)，xi)]xi(11）
預測類別y＾的決策函數如下：
y＾=1，g1(x)≥g0(x)0，g1(x)＜g0(x)
（12）
根據用戶的上下文信息，可以得知用戶一個基本情況。例如，用戶的喜好、用戶身處的地點是旅游景區還是工業開發區，是白天還是晚上，是開車還是徒步等。這些均可以作為x的某個特征輸入模型。
假設用戶的x特征是一個四維向量，x={f，l，t，v}，f：fonder表示用戶的喜好；l：location表示當前位置；t：time表示當時的時間；v：vehicle交通工具。
將這些上下文信息作為輸入，利用歷史數據，通過學習模型的參數修正過程，可以求出相對最合適的權向量w，然后將當時獲取的上下x={f，l，t，v}的值代入模型，得出用戶最有可能選擇的路徑，并將相應服務提供給用戶。假如當時的一個上下文情況是：f——用戶喜歡釣魚，l——用戶處在一個垂釣區附近500米路口，t——上午十點鐘，v——開車，那么系統經過這一系列的上下文信息融合，就可以推斷出用戶是來釣魚的，那么根據已有的GIS和GPS功能，將去最近釣魚區域的最佳路徑計算出來，反饋給用戶。如果用戶不認同，那么系統依次推出方案二、方案三等。模型會根據系統的能力和用戶的喜好來設定一個友好的、個人可定制的服務方式。
對于模型中x向量的各個維是可以靈活變化的，可以根據應用的環境不同而改變某個維或者全部維。例如將該路徑預測模型應用在博物館的話，就可以將x向量的各個維設置為x={i，tr，l，t}，i:illness，包含用戶所得疾病的名稱；tr:病的治療情況；l:location，用戶當前的位置；t:時間。可以作為一個簡單的導醫模型，若患者是胳膊外傷住院治療的，那么可以根據t及tr，推導出患者是該換藥的時候了，那么提示患者從哪里走可以去醫護室清洗、換藥，治療到一定階段后根據tr可以提示用戶去拍X片復查的路線等。在大型醫院樓層、科室分布相對廣泛的情況下，這種模型及產品的研制是非常有必要。
3結束語
在本文提到的三類位置預測模型中，概率模型和Markov模型主要是通過用戶的歷史數據，推斷用戶的將來位置情況。但在歷史路徑數據不豐富的情況下，準確率不高。在機器學習模型中，根據用戶的上下文信息，可以得知用戶一個基本情況，從而很大程度上提高了預測的準確性。而且x的取值可以根據長期使用的經驗，不斷進行參數的修正，逐漸提高模型的預測準確率，在上下文信息選取上，有極大的靈活性。顯然機器模型優于前面的模型。由于篇幅所限，上下文信息的權向量優化問題將在以后的文章中詳細討論。另外，上下文信息的融合方法也將是今后工作的重點。
參考文獻：
［1］CHON H D， AGRAWAL D， ABBADI A E. NAPA:nearest available parking lot application[C]//Proc of the 18th International Conference on Data Engineering. 2002.
[2]CHEVERST K， DAVIESN， MITECHELL K，et al. Experiences of developing and deploying a context-aware tourist guide[C]//Proc of the 6th Annual International Conference on Mobile Computing and Networking. 2000.
[3]李彩霞，曹奇英，蒲芳.普適計算中的室內位置感知[J].計算機工程，2005，31(2l):153-155.
[4]李彩霞，曹奇英.普適計算中的上下文感知及純方位定位模型[J].計算機工程與設計， 2005，26(1):50-52.
[5]KARIMI H A， LIU Xiong. A predictive location model for location-based services[C]//Proc of the 11th ACM International Symposium on Advances in Geographic Information Systems. New Orleans，LA:[s.n.]， 2003:126-133.
[6]BEHRENDS E. Introduction to Marcov chains[M]. Vieweg:[s.n.]， 1999.
[7]PETZOLD J， BAGCI F， TRUMLER W， et al. Global state context prediction techniques applied to a smart office building[C]//Proc ofCommunication Networks and Distributed Systems Modeling and Simulation Conference. San Diego，CA:[s.n.]， 2004.
[8]PETZOLD J， BAGCI F， TRUMLER W，et al. Global and local context prediction[C]//Proc ofArtificial Intelligence in Mobile Systems. Seattle，WA:[s.n.] ，2003.
[9]ABOWD G D， MYNATT E D. Charting past， present， and future research in ubiquitous computing[J].ACM Trans on Computer-Human Interaction， 2000，7(1):8-10.
