位置預(yù)測在定位服務(wù)中的應(yīng)用研究

(重慶郵電大學(xué) 中韓合作GIS研究所， 重慶 400065)



摘 要：定位服務(wù)在現(xiàn)代社會(huì)中扮演著越來越重要的角色，而引入位置預(yù)測在定位服務(wù)可以使得其更能滿足公眾對于定位的需求。但目前在基于數(shù)據(jù)挖掘的位置預(yù)測的研究中，很少有研究關(guān)注空間關(guān)系的模糊性，因此研究了一種基于模糊集理論，利用FMStree結(jié)構(gòu)的FMSmining方法對位置數(shù)據(jù)進(jìn)行挖掘。仿真實(shí)驗(yàn)結(jié)果表明，該方法有效且高效。

 關(guān)鍵詞：定位服務(wù)； 位置預(yù)測； 模糊集； FMSmining

 中圖分類號(hào)：TP39 文獻(xiàn)標(biāo)志碼： A

文章編號(hào)：10013695(2008)12357203



Research of location prediction for locationbased services

GE Junwei， LI Gongwei， DENG Sibing



(SinoKorea Chongqing GIS Research Center， Chongqing University of Posts Telecommunications， Chongqing 400065， China)



Abstract:

Nowadays locationbased services play a very import role in our daily life， and the location prediction technique could make it meets different needs. However， few researches focus on the fuzziness of spatial data in current research for location prediction based on data mining. This paper presented a FMSmining method based on fuzzy set theory，and it could mine location data according to new structure FMStree. Finally， analyzed the effectiveness and efficiency of proposed method and presented experimental evaluation.

 Key words：locationbased services; location prediction; fuzzy set; FMSmining



0 引言

定位服務(wù)在尋人、交通、移動(dòng)電子商務(wù)、緊急救助等方面應(yīng)用得非常廣泛，作為下一個(gè)殺手級(jí)的增值服務(wù)已經(jīng)得到了廣泛的認(rèn)同。特別地，美國的E911已經(jīng)對運(yùn)營商提出了對用戶的緊急呼叫進(jìn)行定位的強(qiáng)制要求，更是預(yù)示著定位服務(wù)將會(huì)進(jìn)入一個(gè)高速發(fā)展期。但是，目前定位服務(wù)在實(shí)際使用中仍然存在很多問題，當(dāng)前主流定位技術(shù)的一些先天缺陷、自然環(huán)境因素、用戶對精度等相關(guān)的要求或是定位資源分配不合理，導(dǎo)致不能滿足用戶的不同需求^[1]。

位置預(yù)測技術(shù)可以作為現(xiàn)有定位服務(wù)中定位技術(shù)的強(qiáng)有力的補(bǔ)充，能提供滿足更多需求的定位服務(wù)，并能改善定位服務(wù)的質(zhì)量。當(dāng)定位過程過分依賴用戶移動(dòng)設(shè)備時(shí)，如當(dāng)設(shè)備電池耗完，或者某些模塊損壞，定位過程無法持續(xù)完成，在這些緊急情況下，合理的位置預(yù)測可以解決這個(gè)問題；另外，若地理環(huán)境變化，現(xiàn)有定位技術(shù)也很難提供穩(wěn)定的定位精度，如GPS在室內(nèi)壞境定位效果急劇惡化時(shí)，一般不能繼續(xù)提供服務(wù)或者精度太差而使用戶不滿意，因此合理適時(shí)的位置預(yù)測能提供給用戶能忍受的精度。位置預(yù)測技術(shù)還可以解決定位服務(wù)中因?yàn)樾枨蟮脑鲩L帶來的相關(guān)問題。例如，很多定位輔助設(shè)備一直保持開啟，但服務(wù)也不是時(shí)時(shí)刻刻需要提供， 合理的預(yù)測可以節(jié)省能源；任何系統(tǒng)容量是有限的，當(dāng)服務(wù)人群過大，LBS服務(wù)將無法滿足每個(gè)用戶，而合理的預(yù)測可以優(yōu)化資源的分配，減小資源搶占的可能性。因此，基于定位服務(wù)研究位置預(yù)測是非常有價(jià)值的。 

1 位置預(yù)測技術(shù)概述

11 位置預(yù)測研究概述

早期預(yù)測技術(shù)的研究大多集中在利用一些簡單的數(shù)學(xué)物理模型進(jìn)行預(yù)測，這類研究不是通過尋找用戶移動(dòng)的規(guī)律來進(jìn)行預(yù)測，而是首先假設(shè)已經(jīng)存在相應(yīng)的用戶移動(dòng)的規(guī)律；也沒有充分考慮到用戶移動(dòng)的隨機(jī)性，更沒有考慮用戶所處環(huán)境的特性，因而預(yù)測的準(zhǔn)確低度，將其用于現(xiàn)在的位置沒有多大的實(shí)用價(jià)值?，F(xiàn)在仍然有少量這種基礎(chǔ)而改進(jìn)的研究，大多都是通過將已知的模型優(yōu)化^[2]，考慮增加一些空間屬性等。隨著研究的不斷深入，概率學(xué)的引入使得預(yù)測模型^[3]的效果得到了更大的提高，利用用戶下一步移動(dòng)的方向和速度大小的概率來計(jì)算得到用戶下一步的位置。

目前，位置預(yù)測的研究大多數(shù)學(xué)者都傾向于采用數(shù)據(jù)挖掘的方法來實(shí)現(xiàn)位置預(yù)測，且大多采用基于經(jīng)典的Apriori算法^[4，5]變化而來。文獻(xiàn)[6]中就直接將Apriori引入用于移動(dòng)模式的挖掘，現(xiàn)有的很多研究都是針對定位服務(wù)的特點(diǎn)進(jìn)行改進(jìn)；文獻(xiàn)[7]中考慮了移動(dòng)過程中一些隨機(jī)運(yùn)動(dòng)，被傳統(tǒng)的算法挖掘出來，利用動(dòng)態(tài)的支持度計(jì)數(shù)解決了這個(gè)問題；文獻(xiàn)[8]考慮的是由于記錄不斷增長而產(chǎn)生的增量挖掘的問題；文獻(xiàn)[9]考慮時(shí)空的多維挖掘；文獻(xiàn)[10，11]充分考慮了數(shù)據(jù)的空間屬性。 但是這些研究在對原始的位置數(shù)據(jù)進(jìn)行變換為適合挖掘的序列時(shí)，直接判斷每個(gè)坐標(biāo)數(shù)據(jù)在哪個(gè)網(wǎng)格直接用當(dāng)前網(wǎng)格表示代替，這對空間的劃分提出了很高的要求，挖掘的效果很依賴于劃分的方式。因此，需要考慮空間數(shù)據(jù)的模糊性進(jìn)行挖掘，減小網(wǎng)格劃分對挖掘的影響。

12 基于模糊移動(dòng)序列挖掘的位置預(yù)測及相關(guān)概念

引入模糊集能更豐富地表達(dá)出原始空間數(shù)據(jù)包含的信息，從而使挖掘出來的模式具有更好的語義表達(dá)功能和更好的預(yù)測效果。為了方便說明，定義相關(guān)概念如下。

ε是用戶定義的支持度閾值，則稱這條序列為有效頻繁序列。

進(jìn)行位置預(yù)測的任務(wù)，即在給定移動(dòng)數(shù)據(jù)庫D，用戶定義支持度閾值后進(jìn)行挖掘，得到所有的有效頻繁序列。

2 基于FMSmining的預(yù)測方法

21 算法描述

211 數(shù)據(jù)預(yù)處理

數(shù)據(jù)預(yù)處理就是將移動(dòng)數(shù)據(jù)庫D中的位置信息轉(zhuǎn)換為移動(dòng)序列，并構(gòu)建移動(dòng)序列數(shù)據(jù)庫(moving sequence database，MSD)。表1為一個(gè)移動(dòng)數(shù)據(jù)的原始記錄。

表1空間已經(jīng)劃分為若干網(wǎng)格，并編號(hào)可以通過相關(guān)模型求得每個(gè)坐標(biāo)對應(yīng)的ai以及θ(ai)，即得到移動(dòng)序列數(shù)據(jù)庫MSD={S1，S2，…，SN}以供挖掘。從表1很容易看出，每個(gè)坐標(biāo)可能對應(yīng)多個(gè)模糊集，最終的生成序列可能比一般方法多一些數(shù)據(jù)。

本文以文獻(xiàn)[13]的WAPtree算法為基礎(chǔ)。本算法的優(yōu) 點(diǎn)在于只需要掃描數(shù)據(jù)庫兩次，比傳統(tǒng)的Apriori更加適合海量的數(shù)據(jù)。

FMStree的定義如下：由一個(gè)根節(jié)點(diǎn)root，一組項(xiàng)目節(jié)點(diǎn)的子樹，一組項(xiàng)目隸屬度節(jié)點(diǎn)的模糊子樹和一個(gè)項(xiàng)頭表組成；節(jié)點(diǎn)子樹的每個(gè)節(jié)點(diǎn)由項(xiàng)目名和節(jié)點(diǎn)鏈兩個(gè)部分組成，節(jié)點(diǎn)鏈由項(xiàng)頭表開始，指向FMStree中下一個(gè)擁有相同項(xiàng)目名的節(jié)點(diǎn)(若沒有時(shí)，為空)；項(xiàng)目隸屬度節(jié)點(diǎn)由項(xiàng)目名、對應(yīng)隸屬度之和及一個(gè)指針構(gòu)成；項(xiàng)頭表的每個(gè)表目由項(xiàng)名、節(jié)點(diǎn)計(jì)數(shù)和節(jié)點(diǎn)鏈頭三個(gè)字段組成，其中節(jié)點(diǎn)鏈頭指向FMStree中的第一個(gè)該項(xiàng)目的節(jié)點(diǎn)。

輸入：移動(dòng)序列數(shù)據(jù)庫MSD和支持度閾值ε

輸出：FMStree

a)掃描MSD一次，找到有效頻繁項(xiàng)目的集合，去除每個(gè)序列中非頻繁的項(xiàng)目，得到一系列有效頻繁子序列。

b)創(chuàng)建根節(jié)點(diǎn)root，指針current_node指向root；創(chuàng)建模糊子樹根節(jié)點(diǎn)froot，指針fcurrent_root指向froot。

如果current_node存在一個(gè)標(biāo)志為ai的子節(jié)點(diǎn)，將當(dāng)前ai對應(yīng)的有效支持度值加θ(ai)，同時(shí)將current_node指向ai；否則，創(chuàng)建新的節(jié)點(diǎn)aj，將θ(ai)賦值給aj對應(yīng)的隸屬度之和，同時(shí)使current_node指向aj，將aj加入到節(jié)點(diǎn)鏈

如果an指向NULL，則an指向froot，且依次創(chuàng)建新的節(jié)點(diǎn)Ai=(a(d，02)，(f，02)；第二次掃描，對于第一個(gè)序列，創(chuàng)建新的節(jié)點(diǎn)子樹和新的模糊子樹，第二次因?yàn)榇嬖谙嗤瑯?biāo)志的節(jié)點(diǎn)，隸屬度計(jì)數(shù)直接累加，根據(jù)定義1得知是相似序列，模糊子樹的隸屬度計(jì)數(shù)直接累加。類似地，可以得到如圖1所示的結(jié)果。

首先，對每個(gè)FMStree的有效頻繁節(jié)點(diǎn)ai構(gòu)造條件移動(dòng)模式數(shù)據(jù)庫P|ai。P|ai中包含ai的所有前綴序列及對應(yīng)前綴序列的隸屬度之和。當(dāng)把a(bǔ)i的一個(gè)隸屬度之和為c的前綴序列插入到P|ai中時(shí)，所有該序列中的ai前綴子序列也被插入到P|ai中，且隸屬度之和為c；然后在P|ai中尋找有效頻繁節(jié)點(diǎn)，用算法1遞歸地構(gòu)造節(jié)點(diǎn)ai的FMStree并進(jìn)行挖掘，直到FMStree只有一個(gè)分支或不存在FMStree為止。P|ai的構(gòu)造可以通過查詢項(xiàng)目頭表生成。首先通過項(xiàng)目頭表依次找到ai，在節(jié)點(diǎn)子樹中查詢它們對應(yīng)的前綴序列和在模糊子樹中查詢前綴序列對應(yīng)的隸屬度之和，分別插入P|ai，直到遍歷完所有的節(jié)點(diǎn)。如圖1的例子，按照順序分別在P|c數(shù)據(jù)庫中插入S′ 1=(b，19)(a，19)(b，19)，S′ 2=(b，09)，S′ 3=(a，09)(b，05)三條序列。 

算法2FMSmining算法

輸入：FMStree和有效支持度閾值ε

輸出：全部的有效移動(dòng)模式MP

a)如果FMStree只有一個(gè)分支或者不能構(gòu)成FMStree，則返回該分支的全部節(jié)點(diǎn)的有序組合；

b)初始化訪問序列模式集MP=NULL，F(xiàn)MStree中的每個(gè)節(jié)點(diǎn)本身就是序列模式，將它們輸入到MP中；

c)對FMStree中的每個(gè)節(jié)點(diǎn)ai，

(a)利用項(xiàng)目頭表，通過ai的節(jié)點(diǎn)鏈構(gòu)造P|ai；

(b)如果P|ai非空，則用算法1構(gòu)造P|ai的FMStree，并用算法2遞歸挖掘FMStree；

(c)將挖掘FMStree得到的每個(gè)模式與ai組合，并將結(jié)果插入到MP中。

22 仿真結(jié)果與分析

實(shí)驗(yàn)采用Stanford大學(xué)無線網(wǎng)絡(luò)小組開發(fā)的仿真程序產(chǎn)生的測試數(shù)據(jù)集SUMATRA(Stanford University mobile activity TRAces)。它包含美國舊金山地區(qū)90個(gè)區(qū)域的位置信息，記錄了移動(dòng)用戶約40 000條移動(dòng)序列，序列的平均長度為116。實(shí)驗(yàn)的硬件環(huán)境是兼容機(jī)30 GHz CPU、512 MB內(nèi)存、80 GB硬盤；操作系統(tǒng)為Windows XP Professional。

圖2是移動(dòng)序列數(shù)量變化時(shí)所需運(yùn)行時(shí)間的實(shí)驗(yàn)結(jié)果。從圖中可以看出，與經(jīng)典的WAPtree算法運(yùn)行結(jié)果相比較，兩種算法都隨著序列長度的增加而運(yùn)行時(shí)間線性增長，但本文算法增長更快一些，是大約一倍的空間復(fù)雜度決定的。

圖3描述的是有效支持度閾值變化時(shí)運(yùn)行時(shí)間的變化。顯然，算法運(yùn)行的時(shí)間對支持閾值不敏感。

3 結(jié)束語

本文提出了FMSmining方法，其優(yōu)點(diǎn)是速度快、效率高，引入模糊理論，能挖掘出更多隱藏有效頻繁序列，預(yù)測效果更 好，也可以應(yīng)用到其他有模糊性的系統(tǒng)中；缺點(diǎn)是空間復(fù)雜度很高，當(dāng)數(shù)據(jù)量過大時(shí)，可能使算法性能降低。另外，為了更好地服務(wù)于定位服務(wù)，將來算法可以考慮流數(shù)據(jù)、增量挖掘等因素。

參考文獻(xiàn)：

[1]葛君偉，李恭偉，袁正午.基于TDSCDMA的無縫定位服務(wù)[J].計(jì)算機(jī)應(yīng)用研究，2007， 24 (9):205207.

[2] CHEN Jidong， MENG Xiaofeng， GUO Yanyan，et al. Modeling and predicting future trajectories of moving objects in a constrained network[C]//Proc of the 7th International Conference on Mobile Data Management. 2006:156157.

[3] NECHYBA M C， MEMBER S， XU Yangsheng， et al. Stochastic similarity for validating human control strategy models[J].IEEE Trans on Robotics and Automation，1998， 14 (3):437451.

[4] AGRAWAL R， SRIKANT R. Fast algorithms for mining association rules[C]//Proc of Very Large Data Bases Conference. Chile:[s.n.]， 1994:487499.

[5] AGRAWAL R， SRIKANT R. Mining sequential patterns[C]//Proc of IEEE Conference on Data Engineering. Taiwan:[s. n.]， 1995:314.

[6] CHUNG J D， PAEK O H， LEE J W， et al. Temporal patterns mining of moving objects for locationbased service[C]//Proc of DEXA. 2002:331340.

[7]YAVA G. Using a data mining approach for the prediction of user movements in mobile environments[EB/OL].（2003）[20071025].http://www.cs.bilkent.edu.tr/techreports/2003/BU_CE0311/pdf. 

[8] MA Shuai， TANG Shiwei， YANG Dongqing， et al. Incremental maintenance of discovered mobile user maximal moving sequential patterns[C]//Proc of DASFAA. Korean:[s.n.]， 2004:824830.

[9] TSENG S M， TSUI C F. Mining multilevel and locationaware service patterns in mobile Web environments[J].IEEE Trans on System， Man and Cybernetics，2004， 34 (6):24802485.

[10] PENG W C， KO Y Z. On mining moving patterns for object tracking sensor networks[C]//Proc of IEEE MDM. 2006:4142.

[11] KIM D O， KANG H K， HONG D S， et al. STMPE: an efficient movement pattern extraction algorithm for spatiotemporal data mining[C]//Proc of ICCSA. 2006:259269.

[12]楊朝暉，李德毅.二維云模型及其在預(yù)測中的應(yīng)用[J].計(jì)算機(jī)學(xué)報(bào)，1998， 21 (11):961969.

[13]PEI Jian， HAN Jiawei， MORTAZAVIASL B， et al. Mining access patterns efficiently from Web logs[C]//Proc of PAKDD. 2000:396407.