基于軌跡數(shù)據(jù)挖掘的語義化位置感知計(jì)算研究.pdf

1、普適計(jì)算是信息空間與物理空間的融合，在這個(gè)融合的空間中人們可以隨時(shí)隨地和透明地獲得數(shù)字化服務(wù)。普適計(jì)算最大的特點(diǎn)在于具有上下文感知這一基本特性。上下文感知計(jì)算是指信息空間獲得物理空間的上下文信息，從而察覺物理空間中狀態(tài)的改變，然后自動(dòng)觸發(fā)相應(yīng)操作或提供相應(yīng)服務(wù)，從而主動(dòng)適應(yīng)用戶需求的變化。位置感知計(jì)算是上下文感知計(jì)算中最重要的基礎(chǔ)性課題之一，是指系統(tǒng)能夠獲取用戶的位置信息，并根據(jù)環(huán)境中用戶位置和空間關(guān)系的變化，進(jìn)行位置上下文推理和融合，

2、分析用戶上下文歷史和現(xiàn)狀，預(yù)測用戶未來狀態(tài)，從而非侵入式地自動(dòng)調(diào)整自己的狀態(tài)和行為來適應(yīng)系統(tǒng)和用戶的需求。
　　 如何基于位置上下文設(shè)計(jì)智能、自然、高效的位置感知計(jì)算系統(tǒng)是普適計(jì)算領(lǐng)域亟待解決的重要問題。由于用戶的運(yùn)動(dòng)通常具有很強(qiáng)的時(shí)空規(guī)律，分析用戶歷史運(yùn)動(dòng)數(shù)據(jù)（即軌跡數(shù)據(jù)），從中挖掘用戶運(yùn)動(dòng)規(guī)律，并結(jié)合用戶當(dāng)前上下文進(jìn)行信息適應(yīng)被認(rèn)為是提高位置感知系統(tǒng)交互效率和智能化程度的有效手段。然而，軌跡數(shù)據(jù)分析和應(yīng)用的現(xiàn)有工作主要存在兩

3、方面的問題:第一，現(xiàn)有軌跡數(shù)據(jù)挖掘算法主要針對規(guī)律性較強(qiáng)的時(shí)空數(shù)據(jù)，但是在普適計(jì)算環(huán)境下，軌跡數(shù)據(jù)具有異構(gòu)性、不可靠性、不完整性等特點(diǎn)，現(xiàn)有挖掘算法無法適應(yīng)這些特點(diǎn)。第二，現(xiàn)有軌跡數(shù)據(jù)分析主要集中在運(yùn)動(dòng)規(guī)律挖掘的層面上，沒有提取出隱含在軌跡數(shù)據(jù)中用戶相關(guān)的深層次知識(shí)（如目的意圖、生活習(xí)慣、社會(huì)關(guān)系），導(dǎo)致挖掘結(jié)果抽象程度較低、難以表示用戶高級語義。此外，現(xiàn)有工作缺乏針對基于軌跡挖掘的位置感知應(yīng)用的設(shè)計(jì)指導(dǎo)方法。
　　 針對這些問

4、題，本文提出基于軌跡數(shù)據(jù)挖掘的語義化位置感知計(jì)算方法，即在軌跡數(shù)據(jù)挖掘的基礎(chǔ)上，提取用戶的目的意圖、行為規(guī)律和社會(huì)關(guān)系三方面的語義信息，并基于用戶語義提供合理、高效的信息適應(yīng)，從而解決位置感知系統(tǒng)可用性低和交互效率不高的問題。為此，本文著重從訪問地點(diǎn)和運(yùn)動(dòng)模式挖掘，用戶目的意圖、行為規(guī)律和社會(huì)關(guān)系等高級語義的提取以及相應(yīng)的信息適應(yīng)方式等方面展開研究。主要研究內(nèi)容和成果包括以下幾個(gè)方面:
　　 (1)在訪問地點(diǎn)挖掘方面，本文提出了

5、一種從GPS軌跡數(shù)據(jù)中挖掘語義化訪問地點(diǎn)的方法。該方法首先根據(jù)軌跡數(shù)據(jù)的時(shí)序特性，采用一種結(jié)合基于時(shí)間的聚類算法和基于密度的聚類算法的層次化聚類算法從中挖掘出訪問地點(diǎn)，然后結(jié)合機(jī)器學(xué)習(xí)技術(shù)和一個(gè)定制的POI數(shù)據(jù)庫對訪問地點(diǎn)的時(shí)間和空間特征分別進(jìn)行分析，進(jìn)而獲取訪問地點(diǎn)的分類語義。相比于現(xiàn)有的訪問地點(diǎn)挖掘技術(shù)，該方法可獲得語義化程度較高的訪問地點(diǎn)信息。
　　 (2)在運(yùn)動(dòng)模式挖掘方面，本文提出了從兩種不同定位技術(shù)（即GPS定位技術(shù)

6、和蜂窩基站定位技術(shù)）獲得的軌跡數(shù)據(jù)中分別挖掘運(yùn)動(dòng)模式的算法。在GPS軌跡數(shù)據(jù)運(yùn)動(dòng)模式挖掘方面，算法對原始GPS軌跡數(shù)據(jù)進(jìn)行路徑分割、候選起點(diǎn)/終點(diǎn)提取、基于空間劃分的抽象化等預(yù)處理，然后采用一種改進(jìn)的PrefixSpan算法從抽象結(jié)果中挖掘出運(yùn)動(dòng)模式。該算法可在保持運(yùn)動(dòng)模式連續(xù)性的基礎(chǔ)上極大程度地容忍軌跡數(shù)據(jù)的不確定性，從而獲得更長、更完整的模式。在蜂窩基站軌跡數(shù)據(jù)運(yùn)動(dòng)模式挖掘方面，算法對原始GSM基站軌跡數(shù)據(jù)進(jìn)行分割、窗口化、分組、聚

7、類等預(yù)處理，然后采用關(guān)聯(lián)規(guī)則挖掘算法從處理結(jié)果中挖掘出運(yùn)動(dòng)模式。該算法可克服蜂窩基站軌跡數(shù)據(jù)的不精確、振蕩、交疊等一系列問題，從而有效地挖掘出運(yùn)動(dòng)模式。
　　 (3)在用戶目的語義提取方面，本文提出了預(yù)測用戶未來運(yùn)動(dòng)行為的方法，包括一種用于改進(jìn)位置預(yù)測性能的自適應(yīng)多階Markov模型，以及一種基于運(yùn)動(dòng)模式挖掘的目的地和未來路徑聯(lián)合預(yù)測方法。自適應(yīng)多階Markov模型可根據(jù)訓(xùn)練數(shù)據(jù)與輸入數(shù)據(jù)的相關(guān)度，自動(dòng)適配合適階數(shù)的Markov

8、模型進(jìn)行預(yù)測，從而在提高預(yù)測性能的同時(shí)降低訓(xùn)練數(shù)據(jù)質(zhì)量對預(yù)測結(jié)果的影響。聯(lián)合預(yù)測方法基于前綴樹數(shù)據(jù)結(jié)構(gòu)對運(yùn)動(dòng)模式建立索引，然后通過模式匹配尋找候選運(yùn)動(dòng)模式，最后根據(jù)概率模型聯(lián)合預(yù)測目的地和未來路徑。該方法在預(yù)測更長的未來路徑方面具有較強(qiáng)的優(yōu)勢。
　　 (4)在用戶行為語義提取方面，本文提出了一種基于訪問地點(diǎn)挖掘的日程行為規(guī)律建模及挖掘方法。該方法采用地點(diǎn)偏好矩陣對用戶日程行為進(jìn)行建模，并對偏好矩陣進(jìn)行聚類以獲得其日程行為模式。在

9、此基礎(chǔ)之上，我們提出了一種基于日程行為模式的用戶相似度計(jì)算方法，對用戶間長期生活習(xí)慣的相似度進(jìn)行度量。實(shí)驗(yàn)結(jié)果表明基于提出的相似度度量方法可有效地區(qū)分用戶職業(yè)背景，從而證明了日程行為模式表示用戶長期生活規(guī)律的有效性。
　　 (5)在用戶關(guān)系語義提取方面，本文提出了一種針對移動(dòng)社會(huì)網(wǎng)絡(luò)的用戶社會(huì)關(guān)系推理方法和一種針對基于位置社會(huì)網(wǎng)絡(luò)的興趣地點(diǎn)個(gè)性化推薦方法。在社會(huì)關(guān)系推理方面，基于語義化訪問地點(diǎn)挖掘和接近數(shù)據(jù)對用戶間的相遇模式進(jìn)行

10、分析，進(jìn)而估計(jì)其可能的真實(shí)社會(huì)關(guān)系類型。在興趣地點(diǎn)個(gè)性化推薦方面，基于多用戶軌跡數(shù)據(jù)協(xié)同挖掘獲得興趣地點(diǎn)、用戶間社會(huì)關(guān)系強(qiáng)度及用戶間興趣相似度等信息，并同時(shí)考慮用戶社會(huì)關(guān)系和興趣偏好對真實(shí)世界中的興趣地點(diǎn)進(jìn)行個(gè)性化推薦，從而提高推薦的可接受程度。
　　 (6)基于提出的軌跡數(shù)據(jù)挖掘和用戶語義提取方法，實(shí)現(xiàn)了一個(gè)語義化位置感知計(jì)算平臺(tái)原型系統(tǒng)。在此基礎(chǔ)之上，設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)基于用戶目的語義的智能化任務(wù)提醒系統(tǒng)iReminder作為