魏軍林 韓楠 喬少杰 甘戈 溫敏

摘要：以Internet應(yīng)用、GIS、靜態(tài)感知基礎(chǔ)設(shè)施、移動(dòng)及可穿戴設(shè)備感知的軌跡大數(shù)據(jù)挖掘問(wèn)題為背景，將移動(dòng)數(shù)據(jù)庫(kù)作為研究對(duì)象，以大數(shù)據(jù)處理、情景感知計(jì)算、軌跡數(shù)據(jù)挖掘?yàn)橹饕芯渴侄危瑥哪Ｐ屯ㄓ眯匀胧郑们榫矮@取技術(shù)提取復(fù)雜時(shí)空交互語(yǔ)義，建立情景表達(dá)和情景與時(shí)空數(shù)據(jù)關(guān)聯(lián)模型，從主客觀角度闡明時(shí)間、用戶和社會(huì)情景因素對(duì)軌跡大數(shù)據(jù)挖掘準(zhǔn)確性的影響，提出融合復(fù)雜情景信息的軌跡大數(shù)據(jù)挖掘新概念、特色理論及模型，為智慧交通、城市計(jì)算、大數(shù)據(jù)分析研究奠定理論基礎(chǔ)。

關(guān)鍵詞：軌跡數(shù)據(jù)庫(kù);時(shí)空計(jì)算;軌跡預(yù)測(cè);GIS;大數(shù)據(jù);情景感知計(jì)算

中圖法分類號(hào)：TP311文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1672-9129（2018）06-0004-03

Techniques of Trajectory Big Data Mining over Context-aware Computing

WEI Jun-Lin¹， HAN Nan²， QIAO Shao-Jie³， GAN Ge⁴， WEN Min¹

（1.Sichuan JKC Geographical Information Technologies Co.， Ltd.， Chengdu， 610043）

（2.School of Cybersecurity， Chengdu University of Information Technology， Chengdu， 610225）

（3.School of Management， Chengdu University of Information Technology， Chengdu， 610103）

（4.Chengdu Municipal Public Security Bureau， Chengdu， 610017）

Abstract：This study focuses on the research of trajectory big data mining， where the data are obtained from the Internet applications， GIS， static sensing infrastructure and mobile and wearable devices. Aiming to analyze the mobile databases， we apply the big data processing， context-aware computing and trajectory data mining techniques. By taking into full consideration the generalization of models， we use the context acquisition approach to retrieve the complex spatio-temporal interaction semantic， create the context expression and context and spatio-temporal association model， clarify the effect of time， individuals and social contexts on the accuracy of trajectory big data mining from the subjective and objective aspect， and propose new concepts， specific theories and models by integrating complex context information to trajectory big data mining in order to set up the methodology on intelligent traffics， urban computing and big data analysis.

Key words：trajectory databases; spatio-temporal computing; trajectory prediction; GIS; big data; context-aware computing

1? 引言

隨著互聯(lián)網(wǎng)、傳感網(wǎng)、物聯(lián)網(wǎng)、云計(jì)算、移動(dòng)計(jì)算技術(shù)的實(shí)現(xiàn)及應(yīng)用，以及智能手機(jī)、車載移動(dòng)終端等移動(dòng)設(shè)備的普及，可以被人們?cè)L問(wèn)和利用的數(shù)據(jù)呈爆炸式增長(zhǎng)，包括：從Internet和Web的網(wǎng)頁(yè)、圖像及多媒體信息，到車聯(lián)網(wǎng)、移動(dòng)社交網(wǎng)絡(luò)、微博等新興互聯(lián)網(wǎng)應(yīng)用數(shù)據(jù);從靜態(tài)感知基礎(chǔ)設(shè)施（如：移動(dòng)網(wǎng)絡(luò)、基站），到移動(dòng)及可穿戴設(shè)備。最重要的是典型應(yīng)用產(chǎn)生的大數(shù)據(jù)具有情景信息與軌跡時(shí)空數(shù)據(jù)契合的特點(diǎn)。情景感知應(yīng)用產(chǎn)生和積累了海量、動(dòng)態(tài)、異構(gòu)、無(wú)規(guī)律、分布在系統(tǒng)各處的情景信息。而軌跡數(shù)據(jù)研究的最終目的是回答：“在何時(shí)（When）、何地（Where）、時(shí)空對(duì)象（Who或What）發(fā)生了什么樣的變化（What）以及如何變化的（How）”，這與情景感知計(jì)算研究中的4W （Who、When、Where和What）非常契合。因此從時(shí)空特性角度，通過(guò)借鑒軌跡數(shù)據(jù)挖掘已有成果，研究情景感知應(yīng)用中的海量數(shù)據(jù)具有重要的科學(xué)意義。

通過(guò)分析和挖掘情景感知設(shè)備，如：車載GPS、手機(jī)、公共交通卡等多源移動(dòng)終端提供的軌跡行為信息，可以對(duì)個(gè)體行為模式（如：基于位置的服務(wù)、出租車異常軌跡檢測(cè)、個(gè)性化旅游路線推薦）;群體及社會(huì)行為（如：智慧交通，城市計(jì)算）進(jìn)行預(yù)測(cè)和模擬。針對(duì)軌跡大數(shù)據(jù)的管理和挖掘，已經(jīng)成為當(dāng)前學(xué)術(shù)界的一個(gè)研究熱點(diǎn)。

情景感知計(jì)算（context-aware computing）^[1]源于普適計(jì)算，由Schilit提出，“指根據(jù)情景信息自動(dòng)地為用戶提供適合當(dāng)前情景的信息或服務(wù)”，情景感知被認(rèn)為是下一個(gè)智能科技新趨勢(shì) ，可以通過(guò)位置感知設(shè)備獲得關(guān)于用戶所處環(huán)境的信息，結(jié)合當(dāng)時(shí)的時(shí)間、用戶興趣偏好和用戶與系統(tǒng)的交互歷史等信息，了解用戶行為、發(fā)現(xiàn)用戶真實(shí)意圖，進(jìn)而提供智能服務(wù)。情景感知計(jì)算被定義為一種新的計(jì)算形態(tài)，具有適應(yīng)性、反應(yīng)性、響應(yīng)性、就位性、情景敏感性和環(huán)境導(dǎo)向性等特性^[2]，作為Context-Rich Systems中的核心技術(shù)被美國(guó)著名市場(chǎng)研究公司Gartner評(píng)選為2015年最具戰(zhàn)略意義的十大技術(shù)，具有廣闊的應(yīng)用前景。

將情景感知計(jì)算技術(shù)應(yīng)用于挖掘具有時(shí)間和空間特性的軌跡大數(shù)據(jù)是一個(gè)新的研究領(lǐng)域，具有很高的創(chuàng)新意義和研究?jī)r(jià)值，本文前期調(diào)研發(fā)現(xiàn)目前國(guó)內(nèi)外鮮有相關(guān)技術(shù)成果報(bào)道。值得注意的是“2015年國(guó)家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃（973）和重大科學(xué)研究計(jì)劃”將情感的計(jì)算與交互，面向信息空間、物理世界和人類社會(huì)三元空間的協(xié)同感知理論的基礎(chǔ)研究作為重要支持方向。本文研究的關(guān)鍵技術(shù)：結(jié)合軌跡數(shù)據(jù)時(shí)空特性，設(shè)計(jì)融合情景信息的時(shí)空軌跡聚集模式發(fā)現(xiàn)及復(fù)雜環(huán)境下移動(dòng)對(duì)象軌跡預(yù)測(cè)與國(guó)家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃指南中給出的研究?jī)?nèi)容“研究情感的計(jì)算與交互，空間信息數(shù)據(jù)、社會(huì)網(wǎng)絡(luò)數(shù)據(jù)等的協(xié)同挖掘”高度吻合，說(shuō)明本文研究具有重要科學(xué)意義。

2? 相關(guān)工作

近年來(lái)，移動(dòng)數(shù)據(jù)管理和挖掘技術(shù)成為國(guó)內(nèi)外學(xué)術(shù)界與工業(yè)界共同關(guān)注的研究熱點(diǎn)。2014年出版的《移動(dòng)對(duì)象管理：模型、技術(shù)與應(yīng)用》一書綜述了移動(dòng)對(duì)象管理和預(yù)測(cè)的最新研究進(jìn)展，分析了現(xiàn)有軌跡預(yù)測(cè)研究工作仍然偏向預(yù)測(cè)簡(jiǎn)單的運(yùn)動(dòng)模式。由于多模式軌跡預(yù)測(cè)問(wèn)題較復(fù)雜，現(xiàn)有的模型非常少，融合情景信息對(duì)位置精準(zhǔn)預(yù)測(cè)未獲得充分重視。下面分別從情景感知技術(shù)、移動(dòng)行為模式發(fā)現(xiàn)、城市計(jì)算、軌跡數(shù)據(jù)挖掘、軌跡預(yù)測(cè)等方面介紹相關(guān)研究成果。

2.1? 情景感知計(jì)算

情景感知是指系統(tǒng)能夠根據(jù)用戶的情景信息，向用戶提供與其任務(wù)相關(guān)的信息和/或服務(wù)，重點(diǎn)是提升用戶體驗(yàn)^[2]。情景感知計(jì)算是情景感知研究的主要工作，與普適計(jì)算、移動(dòng)計(jì)算和智能計(jì)算密切相關(guān)，且這些前沿研究方向都與情景感知計(jì)算交叉，使情景感知計(jì)算具有廣闊的研究前景與應(yīng)用領(lǐng)域。谷歌Project Tango讓移動(dòng)設(shè)備通過(guò)先進(jìn)的感應(yīng)器來(lái)“理解”空間和運(yùn)動(dòng)，從而實(shí)現(xiàn)了3D掃描和室內(nèi)導(dǎo)航等個(gè)性化體驗(yàn)。國(guó)內(nèi)學(xué)者顧君忠最先開(kāi)始“情景感知計(jì)算”的研究，在情景建模方法及情景感知系統(tǒng)框架方面進(jìn)行深入的研究^[3]。近年來(lái)情景感知計(jì)算得到國(guó)內(nèi)外學(xué)者的廣泛關(guān)注。Perera等人^[4]對(duì)2001-2011年間50項(xiàng)代表性情景感知計(jì)算課題進(jìn)行詳細(xì)闡述，系統(tǒng)給出情景感知計(jì)算在物聯(lián)網(wǎng)上應(yīng)用的技術(shù)、方法、模型及系統(tǒng)。Khalid等人^[5]針對(duì)交通，會(huì)場(chǎng)距離，天氣情況等情景因素建模并進(jìn)行情景分析，利用社會(huì)關(guān)系過(guò)濾技術(shù)查找關(guān)鍵和權(quán)威人物。Fraile等人^[6]基于情景獲取技術(shù)設(shè)計(jì)了一種能夠根據(jù)患者生活的真實(shí)環(huán)境規(guī)劃安全運(yùn)動(dòng)路線的多代理系統(tǒng)。國(guó)內(nèi)學(xué)者的代表性工作包括：陳鵬^[7]對(duì)基于情景感知計(jì)算的時(shí)空數(shù)據(jù)管理、查詢、分析算法展開(kāi)深入研究，詳細(xì)闡述情景感知計(jì)算關(guān)鍵技術(shù)。曹懷虎等人^[8]將用戶的位置信息、環(huán)境特征、運(yùn)動(dòng)軌跡等情景引入到聚合算法中，智能地發(fā)現(xiàn)潛在的社交網(wǎng)絡(luò)。近期，林一等人^[9]提出了增強(qiáng)現(xiàn)實(shí)瀏覽器系統(tǒng)中情景感知四層服務(wù)框架，并給出了其在尋路導(dǎo)航系統(tǒng)中的應(yīng)用。

上述工作對(duì)情景感知數(shù)據(jù)建模，識(shí)別個(gè)體所處的真實(shí)環(huán)境信息，進(jìn)而提供最優(yōu)的服務(wù)或者進(jìn)行智能決策，但是大多數(shù)工作主要針對(duì)小規(guī)模數(shù)據(jù)或者開(kāi)發(fā)實(shí)驗(yàn)原型系統(tǒng)，當(dāng)情景信息復(fù)雜、多變、大體量時(shí)，算法的性能無(wú)法得到保障。

2.2? 移動(dòng)行為模式發(fā)現(xiàn)

這一領(lǐng)域研究主要集中于在原始感知數(shù)據(jù)基礎(chǔ)上識(shí)別個(gè)體行為，分析其行為特性和規(guī)律。美國(guó)東北大學(xué)發(fā)表在Nature上的工作^[10]，通過(guò)分析手機(jī)移動(dòng)網(wǎng)絡(luò)數(shù)據(jù)，發(fā)現(xiàn)人的運(yùn)動(dòng)軌跡具有高度的時(shí)空規(guī)律性，從整體上看用戶的位移分布接近于冪律模型。MIT的Reality Mining項(xiàng)目^[11]通過(guò)分析不同國(guó)家、不同地域手機(jī)用戶位置數(shù)據(jù)，理解不同文化背景人群的社會(huì)經(jīng)濟(jì)狀態(tài)、生活節(jié)奏、移動(dòng)性、對(duì)社會(huì)突發(fā)事件的反應(yīng)。Lazer等人^[12]在Science上撰文分析大規(guī)?，F(xiàn)實(shí)生活數(shù)據(jù)理解個(gè)體、組織和社會(huì)。Song等人^[13]在Science上發(fā)表了一篇介紹如何預(yù)測(cè)人類移動(dòng)性的文章，通過(guò)測(cè)量個(gè)體軌跡的信息熵定量地給出了人類動(dòng)態(tài)運(yùn)動(dòng)行為具有93%的可預(yù)測(cè)性。於志文等人^[14]指出：現(xiàn)有研究主要集中于識(shí)別個(gè)體簡(jiǎn)單的活動(dòng)，對(duì)復(fù)雜行為模式的研究不夠。此外，社會(huì)性方面的語(yǔ)義較少，如交互空間語(yǔ)義、細(xì)粒度關(guān)系等，這些因素都可以歸結(jié)為情景感知范疇。此外，在個(gè)體行為識(shí)別上一般是采用有監(jiān)督的學(xué)習(xí)，現(xiàn)有的方法通常需要樣本訓(xùn)練，計(jì)算開(kāi)銷較大，不適合軌跡大數(shù)據(jù)中運(yùn)動(dòng)行為模式發(fā)現(xiàn)。

2.3? 軌跡預(yù)測(cè)

軌跡預(yù)測(cè)作為移動(dòng)數(shù)據(jù)管理中的關(guān)鍵問(wèn)題一直得到國(guó)內(nèi)外學(xué)者的廣泛關(guān)注^[15]。Meng等人^[16]在《移動(dòng)數(shù)據(jù)管理—建模，技術(shù)及應(yīng)用》對(duì)移動(dòng)對(duì)象建模、位置預(yù)測(cè)、索引查詢、聚類和隱私保護(hù)等問(wèn)題進(jìn)行了詳實(shí)的介紹。Ding等人^[17]提出了一種路網(wǎng)匹配的基于軌跡數(shù)據(jù)庫(kù)的交通流分析方法，用于預(yù)測(cè)移動(dòng)對(duì)象位置信息。

Qiao等人^[18]對(duì)移動(dòng)對(duì)象軌跡數(shù)據(jù)進(jìn)行分段處理，提出基于隱馬爾科夫模型的軌跡預(yù)測(cè)算法及參數(shù)自適應(yīng)調(diào)整策略。Qiao等人^[19]提出了一種基于頻繁軌跡模式的軌跡預(yù)測(cè)算法，構(gòu)建軌跡頻繁模式樹(shù)挖掘頻繁軌跡模式。為了解決大規(guī)模軌跡數(shù)據(jù)處理和預(yù)測(cè)時(shí)間效率低下的問(wèn)題，在文獻(xiàn)[18]工作基礎(chǔ)上對(duì)海量軌跡利用基于密度的聚類方法進(jìn)行位置密度分區(qū)和高效分段處理，減少HMM的狀態(tài)數(shù)量^[20]。為了解決分布式傳感器網(wǎng)絡(luò)中異構(gòu)軌跡數(shù)據(jù)挖掘問(wèn)題，Qiao等人^[21]組織一期SCI?？榻B了當(dāng)前分布式傳感器網(wǎng)絡(luò)數(shù)據(jù)中軌跡數(shù)據(jù)挖掘熱點(diǎn)問(wèn)題。近期，文獻(xiàn)[22， 23]針對(duì)移動(dòng)對(duì)象復(fù)雜多模式運(yùn)動(dòng)行為，利用高斯混合回歸方法建模，計(jì)算不同運(yùn)動(dòng)模式的概率分布，利用高斯過(guò)程回歸預(yù)測(cè)運(yùn)動(dòng)軌跡。

通過(guò)上述工作分析可知，現(xiàn)有研究工作中存在的突出問(wèn)題是：并未深入考慮復(fù)雜情景下多模式軌跡預(yù)測(cè)所衍生的深刻挑戰(zhàn)，而是分別針對(duì)簡(jiǎn)單模式開(kāi)展研究工作，無(wú)法有效應(yīng)對(duì)諸如軌跡預(yù)測(cè)算法的實(shí)時(shí)性、準(zhǔn)確性、穩(wěn)定性和可伸縮性的要求。而這些技術(shù)指標(biāo)正是研究中所要考慮的核心問(wèn)題。

3? 軌跡大數(shù)據(jù)挖掘體系架構(gòu)

軌跡數(shù)據(jù)挖掘是數(shù)據(jù)挖掘的一個(gè)新興分支，近年來(lái)得到大型科研機(jī)構(gòu)的廣泛關(guān)注。2014年大數(shù)據(jù)應(yīng)用案例TOP 100中浪潮幫助濟(jì)南公安局搭建大數(shù)據(jù)平臺(tái)，開(kāi)展軌跡行為分析等多種大數(shù)據(jù)研判手段研究。微軟亞洲研究院以鄭宇為代表的課題組分析大規(guī)模車流軌跡數(shù)據(jù)在不同區(qū)域之間行駛特征，發(fā)掘現(xiàn)有城市道路網(wǎng)的不足;利用裝有GPS 傳感器的出租車感知交通流量，為普通用戶設(shè)計(jì)最快駕車線路。上述案例進(jìn)一步證明軌跡大數(shù)據(jù)挖掘的研究成果可以一方面解決具有挑戰(zhàn)性的科學(xué)問(wèn)題，另一方面可應(yīng)用于真實(shí)移動(dòng)行為分析案例中。本文立足于大數(shù)據(jù)處理層和數(shù)據(jù)挖掘?qū)?，通過(guò)抽取邏輯規(guī)則對(duì)不同的特征或情境信息進(jìn)行集成，設(shè)計(jì)新型軌跡數(shù)據(jù)挖掘方法，獲得智能決策信息，服務(wù)于應(yīng)用層。

本文旨在從時(shí)空特性角度研究情景感知應(yīng)用中的海量軌跡數(shù)據(jù)，利用軌跡大數(shù)據(jù)預(yù)處理技術(shù)提取情景感知數(shù)據(jù)特征并對(duì)軌跡大數(shù)據(jù)進(jìn)行降維分析;利用情景感知計(jì)算技術(shù)獲取復(fù)雜情景信息并構(gòu)建語(yǔ)義網(wǎng)絡(luò)，設(shè)計(jì)新型時(shí)空索引結(jié)構(gòu)，提升軌跡大數(shù)據(jù)管理性能;設(shè)計(jì)基于相似性的層級(jí)聚類算法發(fā)現(xiàn)時(shí)空軌跡聚集模式，進(jìn)而挖掘軌跡時(shí)空交互規(guī)律;結(jié)合情景信息與時(shí)空數(shù)據(jù)的關(guān)聯(lián)，利用高斯混合模型、卡爾曼濾波等機(jī)器學(xué)習(xí)方法預(yù)測(cè)最可能運(yùn)動(dòng)行為。提出新的有特色的軌跡大數(shù)據(jù)挖掘方法。本文將面向情景感知計(jì)算的軌跡大數(shù)據(jù)挖掘體系定義為四個(gè)層次，如圖1所示。

4? 軌跡大數(shù)據(jù)的處理方法

軌跡大數(shù)據(jù)預(yù)處理主要包括三個(gè)關(guān)鍵步驟：

（1）情景感知數(shù)據(jù)特征提取。標(biāo)準(zhǔn)GPS數(shù)據(jù)包含時(shí)間、位置、狀態(tài)和信號(hào)質(zhì)量四類數(shù)據(jù)，可以從中獲得包括用戶情景和時(shí)間情景在內(nèi)的初級(jí)情景信息，對(duì)于位置點(diǎn)之間的關(guān)系、用戶當(dāng)前活動(dòng)、交通擁擠情況等高級(jí)社會(huì)情景，本文采用SVM和關(guān)聯(lián)規(guī)則分析等技術(shù)進(jìn)行深層次抽取，構(gòu)建軌跡時(shí)空語(yǔ)義交互網(wǎng)絡(luò)。

（2）軌跡大數(shù)據(jù)降維分析。對(duì)軌跡數(shù)據(jù)實(shí)現(xiàn)空間維度和時(shí)間維度的降維分析，空間維度通過(guò)分析路網(wǎng)中節(jié)點(diǎn)的介數(shù)（betweenness），減少路網(wǎng)中的區(qū)域或減少邊，抽取關(guān)鍵節(jié)點(diǎn)和路徑。此外，采用主成分分析技術(shù)將關(guān)鍵分量的分析獲得全局特征，實(shí)現(xiàn)進(jìn)一步空間降維。對(duì)于時(shí)間尺度的降維分析，設(shè)計(jì)找尋和量化移動(dòng)對(duì)象的整體移動(dòng)模式在各自時(shí)間片下顯著差異的算法，進(jìn)而實(shí)現(xiàn)精確的時(shí)間片劃分，降低各時(shí)間段間的相似性。

（3）混合時(shí)空索引結(jié)構(gòu)。本文采用如圖2所示的混合索引結(jié)構(gòu)，索引移動(dòng)對(duì)象歷史、當(dāng)前和未來(lái)軌跡信息，實(shí)現(xiàn)軌跡及位置點(diǎn)的高效查詢。圖1所示的索引結(jié)構(gòu)是一種基于歷史樹(shù)和基于雙層索引結(jié)構(gòu)的DISC-tree，歷史樹(shù)采用四叉樹(shù)索引移動(dòng)對(duì)象歷史軌跡點(diǎn)，DISC-tree^[24]索引移動(dòng)對(duì)象現(xiàn)在和最近將來(lái)的位置信息。同時(shí)，隨著時(shí)間的推移，將DISC-tree的內(nèi)容過(guò)渡到歷史樹(shù)中。此外，為移動(dòng)對(duì)象的各段軌跡建立雙向鏈表，當(dāng)要查找某一移動(dòng)對(duì)象的完整或者部分軌跡時(shí)，只要找到一段，就可以依據(jù)前向后向指針找到軌跡所有各段。這樣既保證了歷史軌跡的空間性，又實(shí)現(xiàn)了軌跡的連續(xù)性。

5? 融合情景信息的軌跡聚集模式發(fā)現(xiàn)方法

將軌跡大數(shù)據(jù)處理后抽取的初級(jí)和高級(jí)情景感知數(shù)據(jù)作恰當(dāng)?shù)霓D(zhuǎn)換，轉(zhuǎn)換成與模型相符的形態(tài)，通過(guò)情景過(guò)濾技術(shù)把影響應(yīng)用的情景信息篩選出來(lái)，構(gòu)建數(shù)學(xué)模型對(duì)不同情境特征融合，量化表達(dá)它們間的關(guān)聯(lián)。利用興趣點(diǎn)識(shí)別技術(shù)挖掘軌跡時(shí)空交互行為模式，構(gòu)建用戶&位置關(guān)聯(lián)矩陣。

設(shè)計(jì)一種基于個(gè)體時(shí)空相似性度量方法對(duì)具有相似行為特征的軌跡聚類識(shí)別。算法利用用戶&位置關(guān)聯(lián)矩陣，基于個(gè)體位置、時(shí)間、環(huán)境特征、移動(dòng)軌跡相似性的層次型聚類算法自下而上地把較小的cluster合并聚集。聚類過(guò)程分為兩個(gè)階段，1） 局部匹配，將軌跡劃分成不同基本單元，給定一個(gè)距離閾值θ，如果兩個(gè)基本單元之間的距離小于θ，則認(rèn)為基本單元匹配;2） 全局匹配，計(jì)算任意兩條軌跡的基本單元集合中局部匹配軌跡點(diǎn)的數(shù)量，如果大于給定的數(shù)量閾值ξ，則認(rèn)為兩條軌跡全局匹配。基于平移的最小Hausdorff距離的思想，不僅比較兩個(gè)基本單元的形狀及其蘊(yùn)含的運(yùn)動(dòng)規(guī)律，而且能夠消除一定范圍內(nèi)基本比較單元的公共偏差，提高聚類準(zhǔn)確性。

6? 復(fù)雜情景下時(shí)空軌跡預(yù)測(cè)模型

復(fù)雜情景下時(shí)空軌跡預(yù)測(cè)模型主要包括情景感知信息建模、軌跡熱點(diǎn)區(qū)域挖掘和模型訓(xùn)練和學(xué)習(xí)預(yù)測(cè)過(guò)程，其技術(shù)路線如圖3所示^[22]。下面將對(duì)軌跡預(yù)測(cè)的關(guān)鍵步驟給出詳細(xì)的說(shuō)明。

1）情景感知信息建模。利用關(guān)鍵值偶模型（key&value pair models）對(duì)時(shí)間和位置情景等簡(jiǎn)單情景信息建模;利用面向?qū)ο竽Ｐ停╫bject oriented models）對(duì)用戶情景和社會(huì)情景等復(fù)雜情景信息建模，模型將每一種可能出現(xiàn)的情景因素組合映射為一種關(guān)于移動(dòng)對(duì)象行為模式的狀態(tài)，每一種狀態(tài)信息能夠充分反映動(dòng)態(tài)情景的變化，與軌跡上不同位置點(diǎn)相對(duì)應(yīng)，將移動(dòng)對(duì)象的一條完整軌跡表示為一條包含復(fù)雜情景信息的狀態(tài)鏈^[25]。

2）軌跡熱點(diǎn)區(qū)域挖掘。提出基于頻繁軌跡模式的熱點(diǎn)區(qū)域挖掘算法，算法的主要步驟包括：a） 通過(guò)挖掘軌跡數(shù)據(jù)計(jì)算各軌跡片段的訪問(wèn)頻率，獲取頻繁軌跡模式進(jìn)而構(gòu)建軌跡熱點(diǎn)區(qū)域;b） 對(duì)軌跡進(jìn)行劃分，計(jì)算落在熱點(diǎn)區(qū)域內(nèi)的片段構(gòu)造的完整軌跡。通過(guò)軌跡熱點(diǎn)區(qū)域挖掘出包含單一和多種運(yùn)動(dòng)特征的軌跡模式。

3）模型訓(xùn)練和學(xué)習(xí)預(yù)測(cè)^[22]。結(jié)合情景感知信息，將單一運(yùn)動(dòng)模式利用高斯過(guò)程GP表示，而復(fù)雜場(chǎng)景中多種運(yùn)動(dòng)模式利用高斯混合模型GMM建模。a） 針對(duì)稀疏離散的軌跡大數(shù)據(jù)，利用高斯混合模型對(duì)軌跡數(shù)據(jù)利用概率密度函數(shù)建模，通過(guò)GMM對(duì)訓(xùn)練軌跡數(shù)據(jù)進(jìn)行聚類分析;然后，利用EM算法估計(jì)相應(yīng)參數(shù)，依據(jù)符合正態(tài)分布數(shù)據(jù)的條件分布得到多個(gè)高斯分量的回歸函數(shù);最后，將回歸函數(shù)加權(quán)混合完成軌跡回歸預(yù)測(cè)。b） 對(duì)于密集復(fù)雜的軌跡大數(shù)據(jù)，利用卡爾曼濾波算法計(jì)算的高效性，通過(guò)系統(tǒng)的狀態(tài)空間模型以及觀測(cè)模型，同時(shí)以最小均方差為準(zhǔn)則，利用前一時(shí)刻的估計(jì)值和現(xiàn)時(shí)刻的觀測(cè)值來(lái)更新對(duì)狀態(tài)變量的估計(jì)，進(jìn)而對(duì)下一時(shí)刻的軌跡預(yù)測(cè)^[26]。在卡爾曼濾波周期過(guò)程中存在兩個(gè)不同更新過(guò)程，分別是時(shí)間更新和觀測(cè)更新過(guò)程，時(shí)間更新過(guò)程根據(jù)前一時(shí)刻的最優(yōu)狀態(tài)估計(jì)預(yù)測(cè)出當(dāng)前時(shí)刻下的狀態(tài)，同時(shí)更新當(dāng)前預(yù)測(cè)狀態(tài)的協(xié)方差。預(yù)測(cè)出軌跡點(diǎn)之后，需要用觀測(cè)值來(lái)進(jìn)行線性擬合出最優(yōu)估計(jì)軌跡點(diǎn)信息。

7? 結(jié)論

本文針對(duì)軌跡大數(shù)據(jù)挖掘提出新的研究問(wèn)題：1） 結(jié)合情景信息（時(shí)間情景、物理情景、用戶情景、社會(huì)情景）挖掘軌跡數(shù)據(jù)中人類活動(dòng)模式和預(yù)測(cè)空間移動(dòng)行為;2） 基于個(gè)體行為相似性的軌跡時(shí)空聚集模式發(fā)現(xiàn)算法。利用情景感知計(jì)算技術(shù)結(jié)合軌跡大數(shù)據(jù)的時(shí)空特性、用戶興趣偏好、用戶與系統(tǒng)的交互歷史信息，來(lái)了解用戶行為、發(fā)現(xiàn)用戶真實(shí)意圖、挖掘用戶行為模式可以推動(dòng)數(shù)據(jù)庫(kù)及相關(guān)領(lǐng)域，如大數(shù)據(jù)管理、數(shù)據(jù)挖掘、GIS等多學(xué)科多領(lǐng)域交叉研究的發(fā)展。本文提出的方法在適當(dāng)變通后，可應(yīng)用于廣泛的領(lǐng)域，如：環(huán)境監(jiān)控，公共安全等民生應(yīng)用。此外，可以將其擴(kuò)展到現(xiàn)實(shí)世界挖掘、城市計(jì)算等實(shí)際若干類似的研究領(lǐng)域。

參考文獻(xiàn)

[1]????? Schilit B， Adams N， Want R. Context-aware Computing Applications. In： Proceedings of WMCSA94， Santa Cruz， CA， USA， 1994： 89-101.

[2]????? Dey A K. Providing Architectural Support for Building Context-aware Applications[Ph.D. Thesis]. Atlanta： Georgia Institute of Technology， 2000.

[3]????? 顧君忠. 情景感知計(jì)算. 華東師范大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2009， （5）： 1-20.

[4]????? Perera C， Zaslavsky A， Christen P， Georgakopoulos D. Context Aware Computing for the Internet of Things： A Survey. IEEE Communications Surveys & Tutorials， 2014， 16（1）： 414-454.

[5]????? Khalid O， Khan M U S， Khan S U， et al. OmniSuggest： A Ubiquitous Cloud-Based Context-Aware Recommendation System for Mobile Social Networks. IEEE Transactions on Services Computing， 2014， 7（3）： 401-414.

[6]????? Fraile J A， Paz Y D， Bajo J， et al. Context-aware Multiagent System： Planning Home Care Tasks. Knowledge and Information Systems， 2014， 40（1）： 171-203.

[7]????? 陳鵬. 面向情景感知計(jì)算的時(shí)空數(shù)據(jù)管理、查詢、分析與相關(guān)算法研究[博士學(xué)位論文]. 上海： 華東師范大學(xué)， 2013.

[8]????? 曹懷虎， 朱建明， 潘耘， 李海峰. 情景感知的P2P移動(dòng)社交網(wǎng)絡(luò)構(gòu)造及發(fā)現(xiàn)算法. 計(jì)算機(jī)學(xué)報(bào)， 2012， 35（6）： 1223-1234.

[9]????? 林一， 劉越， 王涌天， 賀長(zhǎng)宇. 一種增強(qiáng)現(xiàn)實(shí)分場(chǎng)景推送情景感知服務(wù)的方法. 軟件學(xué)報(bào)， 2016， 27（8）： 2115-2134.

[10]??? González M， Hidalgo C， Barabási A -L.Understanding Individual Human Mobility Patterns. Nature， 2008， 453（5）： 779-782.

[11]??? Pentland A. Societys Nervous System： Building Effective Government， Energy， and Public Health Systems. IEEE Computer， 2012， 45（1）： 31-38.

[12]??? Lazer D， Pentland A， et al. Life in the Network： the Coming Age of Computational Social Science. Science， 2009， 323（5915）： 721-723.

[13]??? Song C， Qu Z， Blumm N， Barabási A -L. Limits of Predictability in Human Mobility. Science， 2010， 327（5968）： 1018-1021.

[14]??? 於志文， 於志勇， 周興社. 社會(huì)感知計(jì)算：概念、問(wèn)題及其研究進(jìn)展. 計(jì)算機(jī)學(xué)報(bào)， 2012， 35（1）： 16-26.

[15]??? Shaojie Qiao， Nan Han， Junfeng Wang， Rong-Hua Li， Louis Alberto Gutierrez， Xindong Wu. Predicting Long-term Trajectories of Connected Vehicles via Prefix-Projection Technique. IEEE Transactions on Intelligent Transportation Systems， 2017， 19（7）： 2305-2315.

[16]??? Meng X， Ding， Z， Xu J. Moving Objects Management： Models， Techniques and Applications. Springer Press， 2014.

[17]??? Ding Z， Yang B， Guting R H， et al. Network-Matched Trajectory-Based Moving-Object Database： Models and Applications. IEEE Transactions on Intelligent Transportation Systems， 2015， 16（4）： 1-11.

[18]??? Qiao S， Shen D， Wang X， Han N， Zhu W. A Self-Adaptive Parameter Selection Trajectory Prediction Approach via Hidden Markov Models. IEEE Transactions on Intelligent Transportation Systems， 2015， 16（1）： 284-296.

[19]??? Qiao S， Han N， Zhu W， Gutierrez L. TraPlan： An Effective Three-in-One Trajectory-Prediction Model in Transportation Networks. IEEE Transactions on Intelligent Transportation Systems， 2015， 16（3）： 1188-1198.

[20]??? 喬少杰， 李天瑞， 韓楠， 高云君， 元昌安， 王曉騰， 唐常杰. 大數(shù)據(jù)環(huán)境下移動(dòng)對(duì)象自適應(yīng)軌跡預(yù)測(cè)模型. 軟件學(xué)報(bào)， 2015， 26（11）： 2869-2883.

[21]??? Qiao S， Jin H， Gao Y， Xing H. Trajectory Data Mining in Distributed Sensor Networks. International Journal of Distributed Sensor Networks， 2015（3， article 1）： 1-3.

[22]??? 喬少杰， 金琨， 韓楠， 唐常杰， 格桑多吉， Gutierrez Louis Alberto. 一種基于高斯混合模型的軌跡預(yù)測(cè)算法， 軟件學(xué)報(bào)， 2015， 26（5）： 1048-106.

[23]??? 喬少杰， 韓楠， 丁治明， 金澈清， 孫未未， 舒紅平. 多模式移動(dòng)對(duì)象不確定性軌跡預(yù)測(cè)模型. 自動(dòng)化學(xué)報(bào)， 2018， 44（4）： 608-618.

[24]??? 喬少杰， 韓楠， 王超， 祝峰， 唐常杰. 基于路網(wǎng)的移動(dòng)對(duì)象動(dòng)態(tài)雙層索引結(jié)構(gòu). 計(jì)算機(jī)學(xué)報(bào)， 2014， 37（9）： 1947-1958.

[25]??? 喬少杰， 韓楠， 李天瑞， 熊熙， 元昌安， 黃江濤， 王曉騰. 一種基于空間編碼技術(shù)的軌跡特征提取方法. 中國(guó)科學(xué)： 信息科學(xué)， 2017， 47（11）： 1523-1537

[26]??? 喬少杰， 韓楠， 朱新文， 舒紅平， 鄭皎凌， 元昌安. 基于卡爾曼濾波的動(dòng)態(tài)軌跡預(yù)測(cè)算法. 電子學(xué)報(bào)， 2018， 46（2）： 418-423.