胡 燕，朱曉瑛，馬 剛

(北京郵電大學 信息網絡中心，北京 100876)

基于K-Means和時間匹配的位置預測模型

胡 燕，朱曉瑛，馬 剛

(北京郵電大學 信息網絡中心，北京 100876)

隨著移動服務的發(fā)展，越來越多的移動端服務基于對象的位置進行推送和推薦，因此位置預測技術顯得越來越重要.由于對象位置信息存在采集不連續(xù)或對象行為不規(guī)律等因素，導致位置預測成為一項非常有挑戰(zhàn)的工作.為了提高位置預測的準確性，提出一種基于K-Means算法和時間匹配的位置預測模型.該模型使用K-Means算法對歷史位置點進行聚類，劃分多個對象運動區(qū)域，針對對象運動區(qū)域進行預測.按照對象的作息時間將一天時間劃分為多個時間段，運用筆者提出的軌跡建模算法和軌跡更新算法形成用戶運動軌跡，形成對象運動軌跡，再使用時間匹配原則進行位置預測.筆者最后利用真實的數(shù)據(jù)實現(xiàn)該模型，實驗證明：未使用該模型的位置預測準確率為39.7%；使用該模型后算法和時間匹配的位置預測模型預測準確率達到60.3%，準確率提高了20%左右.

位置預測；K-Means算法；時間匹配；聚類

0 引言

隨著移動對象空間技術的快速發(fā)展，對象位置信息采集更加便捷，隨之而來的移動位置服務也越來越重要.為了使服務具有前瞻性，不僅要對移動對象的位置進行分析，更要對其位置進行預測[1-2].對象位置信息可以通過多種方式采集，例如GPS、WiFi、AP等，這些位置信息和訪問時間對應就能形成一個對象的軌跡信息.然而，位置預測卻是一項有難度的工作，例如位置信息采集總是不連續(xù)的或者存在盲點，一些重要位置信息無法采集到；已采集的數(shù)據(jù)通常無法直接進行對象位置預測，需要預處理工作；對象的行為存在不規(guī)律和不確定性，很難用一種算法進行預測，要綜合考慮多種因素,以上這些原因導致位置預測比較困難.

位置預測通常有兩種方法，第一種是根據(jù)對象的上一個訪問位置點預測當前位置點，通過計算轉移概率進行預測.文獻[3-5]中的馬爾科夫和隱馬爾科夫算法用于位置預測，同時結合對象社會關系和時間匹配，這種預測方式只與上一個位置到當前位置的轉移概率有關.其中，文獻[3]將貝葉斯網絡用于預測，并且考慮多種因素來提高預測效率，將空間、時間、對象相似性等屬性考慮到預測模型中.文獻[6-8]使用漫步算法和馬爾科夫算法同時進行預測，對象訪問路徑和時間間隔也作為預測的影響因素.第二種方式是收集歷史位置點信息預測當前位置.文獻[1]和文獻[9]對歷史活動位置進行建模，并且將對象的運動趨勢作為位置預測的重要因素.

筆者的位置預測屬于第二種預測方式，即采用基于對象歷史訪問位置信息進行預測.由于預測對象的精確位置較為困難，且移動服務推送總是面向某個區(qū)域的對象提供服務，因此筆者的預測模型也以區(qū)域為基礎.首先對對象的歷史位置點用K-Means算法進行聚類，每一個聚類的結果就是一個對象活動區(qū)域，再基于以上區(qū)域的劃分進行位置預測以提高預測的準確性，并且對對象所在位置區(qū)域的預測對移動服務提供者是有價值的.最后基于時間匹配原則，將對象24 h的時間進行分段，并將每個時間段歷史上出現(xiàn)概率最多的位置區(qū)域作為該時間段的熱點位置.熱點位置與時間點結合就能形成對象一天的運動軌跡，根據(jù)對象運動軌跡中所對應的時間和位置就能進行對象位置預測.

1 K-Means算法及相關定義

1.1 K-Means算法

K-Means算法是用于解決聚類問題的經典算法，是在給定樣本點集合和k值的前提下進行聚類的簡單算法.假設X=(x1,x2,…,xn)是要進行聚類的樣本點，xi是其中任意一個樣本.K-Means算法將樣本點劃分為k個聚類，定義為C=(c1,c2,…,ck)，其主要思路是為每個聚類定義ci個質心點.首先，在樣本點中隨機選取k個質心點,然后計算樣本點到該質心點的距離.質心點到樣本點的距離可以定義為：‖xi-cj‖2(i∈n,j∈k) .計算每個樣本點到質心點的距離，將該樣本點歸到距離最近的質心點類里，重復直到所有樣本點都被歸類.

1.2 相關定義

基于K-Means和時間匹配的位置預測模型與對象的歷史位置信息、時間段、對象位置軌跡、預測準確率等概念相關，因此對以上概念做如下定義.

定義1 位置點.假設L=(L1,L2,…,Ln)是所有對象的歷史位置點集合， 對于任意的Li，其經緯度的位置信息可以記錄為Li=(xi,yi) .

定義2 對象活動區(qū)域.聚類的結果記為Cluster=(c1,c2,…，ck)，其中k是給定的輸入值.聚類中每個位置點的最小和最大經度緯度形成運動區(qū)域，記錄為：

O=(Xmin,Ymin,Xmax,Ymax).

定義3 時間段. 將一天24小時劃分為多個不同的時間段，描述為：T=([ti,tj],[tj,tk],…,[tn,ti])(0≤ti

定義4 熱點位置.對象出現(xiàn)在某個歷史位點的概率可以描述為：

在Tij=[ti,tj]時間段內，對象出現(xiàn)概率最大的位置點為熱點位置，記為Mp，

定義5 對象運動軌跡.對象在一天的不同時間段內對應的位置序列稱為對象位置軌跡，其中某天的運動軌跡為：

S=([T1,L1],[T2,L2],…,[Tn,Ln]).

定義6 位置預測準確率.以天為單位對對象位置進行預測，對象在每天的每個時間段,熱點位置實際發(fā)生的位置與運動軌跡中預測的運動區(qū)域相同則認為預測準確.根據(jù)定義5，將一天時間劃分為n個時間段，其中有m個時間段的熱點位置預測準確，位置預測準確率記為：

2 基于K-Means和時間匹配的位置預測模型

筆者提出一種基于K-Means和時間匹配的位置預測模型，預測過程主要分兩個階段.第一階段為軌跡建模階段，使用K-Means算法對歷史訪問位置點按照不同時間段進行聚類形式軌跡簇，計算出每個時間段出現(xiàn)最頻繁的位置點作為該時間段的熱點位置，形成對象每天的運動軌跡.第一階段中用K-Means對歷史位置點進行聚類，形成對象運動區(qū)域，目的是提高預測的準確性，同時對運動區(qū)域的預測不影響移動服務的推送和推薦.第二階段根據(jù)時間匹配原則對位置進行預測.

2.1 軌跡建模

軌跡建模階段是對歷史位置點進行聚類，形成對象運動區(qū)域.使用任意兩個歷史位置點之間的距離用K-Means算法進行聚類，其距離表示為Dij=‖xi-yi‖2，聚類過程如下：

輸入:所有歷史位置點Li=(xi,yi)和k值.

輸出:聚類結果.

①在歷史位置點中隨機選擇k個樣本點為初始質心.

②計算某個歷史位置點到每個質心點的距離，將該歷史位置點歸入距離最近的那個質心點.歷史位置點到所有質心點的最小距離可以表示為：

③當所有的歷史位置點被分配以后，重新計算質心的位置.

④重復②和③直到質心點沒有變化，按照計算最短距離的方式將所有的歷史位置點進行聚類.

聚類的結果記為Cluster=(c1,c2,…,ck)，其中k是給定的輸入值.聚類完成后計算對象活動區(qū)域，任意一個ci的對象位置區(qū)域為:

O=(Ximin,Yimin,Ximax,Yimax).

由于每個對象出現(xiàn)的歷史位置點都有對應的時間，因此對象出現(xiàn)時間與對象位置預測是有緊密聯(lián)系的.假設Oi=(Oa,Ob,…,Ok)為對象在時間段Ti=[Tij,Tjk,…,Tni]的熱點位置，按照時間序列可以形成對象一天的歷史軌跡，即

S={〈Tij,Oa〉,〈Tjk,Ob〉,…,〈Tni,Ok〉}，

(0≤ti

2.2 軌跡預測

通過軌跡建模階段對對象位置數(shù)據(jù)進行處理，使用軌跡建模算法得到的對象運動軌跡，該模型由不同時間序列組成，每個時間段的熱點位置用概率估算的方法對對象未來的運動軌跡進行預測.

S′={〈Tij,Oa〉,〈Tjk,Ob〉，…，〈Tni,Ok〉}，

(0≤ti

3 實驗和結果

實驗使用加利佛尼亞大學發(fā)布的真實數(shù)據(jù)，這些數(shù)據(jù)是從校園AP獲取的對象位置信息.數(shù)據(jù)包含AP信息和對象訪問信息.AP信息包含AP的經緯度、高度等信息.對象訪問信息是通過對象的終設備軟件采集，當對象打開該軟件時軟件將會記錄訪問AP的信息，包括AP編號、訪問時間、信號強度等信息.筆者從發(fā)布的數(shù)據(jù)中選取50個對象兩個星期的訪問信息作為歷史位置信息，其中前一個星期數(shù)據(jù)用于軌跡建模，后一個星期的訪問信息用于軌跡更新.

首先將所有歷史記錄中出現(xiàn)的AP使用K-Means聚類，假設k=8，所有的AP按照位置聚類為8個類，圖1為聚類結果.

根據(jù)作息規(guī)律將一天24小時劃分為6個時間段，分別是t1=[0am,6am]、t2=[6am,9am]、t3=[9am,12am]、t4=[12am,14pm]、t5=[14pm,18pm]、t6=[18pm,24pm].然后計算每個時間段訪問次數(shù)最多的位置作為該時間段的代表位置.這樣就能按照時間段形成對象的位置軌跡，并利用該對象一天的運動軌跡對對象位置進行預測.

實驗選取50個采集信息較多的對象位置進行實驗，圖2為不同時間段預測準確率的對比結果.在t1時間段，兩種方式的預測準確率相同，因為該時間段([0am, 6am])是對象睡覺時間，因此聚類前后準確率無變化.t2([6am, 9am])時間段是早晨活動時間，該時間對象的活動范圍不太固定，聚類后的預測準確率低于聚類前.t3～t6時間為學習和晚間活動時間，該時間段對象活動范圍相對固定，因此聚類后預測準確率高于聚類前.實驗結果證明校園對象在一定時間段內在固定區(qū)域內活動較多，筆者提出的基于K-Means和時間匹配的位置預測模型適合針對校園對象進行位置預測.使用模型前按照時間段對位置點預測，不針對運動區(qū)域進行預測，圖3顯示使用預測模型前的預測準確率為39.7%，使用預測模型后的預測準確率為60.3%.

圖1 K-Means 算法聚類結果

圖2 不同時間段預測準確率對比結果

圖3 使用預測模型前和使用預測模型后預測準確率對比結果

4 結論

提出一種基于K-Means和時間匹配的位置預測模型，該模型使用K-Means算法對歷史位置點信息聚類，形成對象運動區(qū)域.在此基礎上筆者又提出軌跡建模算法用于確定對象歷史運動軌跡，并根據(jù)時間匹配原則按天對對象軌跡進行預測.為了實現(xiàn)該模型，使用加利佛利亞大學的真實數(shù)據(jù)進行試驗.試驗證明，該模型提高了位置預測的準確性.因此，基于K-Means和時間匹配的位置預測模型是較為準確、高效的.

[1] 李雯,夏士雄,劉峰,等. 基于運動趨勢的移動對象位置預測[J].通信學報, 2014, 35(2): 46-53.

[2] 于瑞云,夏興有,李婕,等. 參與式感知系統(tǒng)中基于社會關系的移動對象位置預測算法[J].計算機學報, 2015, 38(2): 374-385.

[3] ROBARDS W M, SUNEHAG P. Semi-markov K-Means clustering and activity recognition from body-worn sensors[C].2009 Ninth IEEE International Conference on Data Mining.2009.

[4] YANG Y, WANG Z L, ZHANG Q, et al. A time based markov model for automatic position-dependent services in smart Home[C].2010 Chinese Control and Decision Conference.Beijing, 2010.

[5] 趙楊,田國會,尹建芹,等. 家庭智能空間下基于HMM的人軌跡分析方法[J].模式識別與人工智能,2015,28(6): 542-549.

[6] 彭曲,丁治明,郭黎敏. 基于馬爾可夫鏈的軌跡預測[J].計算機科學，2010,37(8):189-192.

[7] 李婕,夏興有,王興偉,等. 機會認知網絡中基于社會關系的節(jié)點位置預測算法[J].東北大學學報(自然科學版)，2014, 35(12):1701-1705.

[8] LI W, XIA S X, LIU F, et al. Markov location prediction algorithm based on dynamic social ties[C]. IEICE TRANS. INF.& SYST,2015.

[9] 趙雪涵. 基于密度聚類的用戶軌跡預測算法研究[D].西安：西安理工大學計算機等院.2014.

[10]FULOP P, SZABO S, SZALKA T. Accuracy of random walk and markovian mobility models in location prediction methods[C].15th International Conference on Software, Telecommunications and Computer Networks. 2007.

[11]RACHURI K, MURTHY R C. Level biased random walk for information discovery in wireless sensor networks[C].IEEE International Conference on Communications. 2009.

[12]XU J H, LIU H. Web user clustering analysis based on K-Means algorithm[C].International Conference on Information Networking and Automation (ICINA). 2010.

Location Prediction Model Based on K-Means Algorithm and Time Matching

HU Yan, ZHU Xiaoying, MA Gang

(Network and Information Center, Beijing University of Posts and Communications, Beijing 100786, China)

Location prediction was critical to mobile service because various kinds of applications were tightly combined with user’s location. However, location prediction was a challenging work because location capturing was always not continuous and user’s behavior were uncertain and irregular. To improve the location prediction accuracy rate, this paper proposed a location prediction model based on K-Means algorithm and time matching. For the mobile service always region oriented, we first clusted history location using K-Means algorithm to define several regions. Then we divided every day time into several segments and calculated the maximum probability location in every time segment. A trajectory of a user in one day was formed with trajectory model and trajectory updating model which proposed in this paper. We could predict user’ location with time matching method. At last, we did experiments with real location data in campus which captured by APs. The prediction out come with K-Means was compared to the outcome without model based on K-Means algorithm. The experiment result shows that accuracy rate of our model was higher than the prediction without new model. So, more location services could be provided to users with this new model.

location prediction; K-Means algorithm; time matching; cluster

2016-10-27；

2017-01-10

國家高技術研究發(fā)展計劃(863計劃)資助項目(2013AA014702)

胡燕(1982— ),女,湖北武漢人,北京郵電大學工程師，主要研究方向為信息處理、大數(shù)據(jù).

1671-6833(2017)02-0017-04

TP311

A

10.13705/j.issn.1671-6833.2017.02.005