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

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

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

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

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

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

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

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

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

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

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