大規(guī)模軌跡數(shù)據(jù)的檢索、挖掘及應(yīng)用.pdf

1、軌跡可以看作是移動(dòng)對象隨著時(shí)間的變化在空間中留下的印跡。近年來，隨著民用GPS(全球定位系統(tǒng)，Global Positioning System)等定位設(shè)備在移動(dòng)終端上的廣泛使用以及基于位置服務(wù)(Location-Based Service)和移動(dòng)社交網(wǎng)絡(luò)(Mobile Social Network)的發(fā)展和普及，大量的軌跡數(shù)據(jù)在日常生活中正在日益積累并為不同類型的應(yīng)用所服務(wù)。
　　 這些與軌跡相關(guān)的新興技術(shù)和服務(wù)為人們的生活帶

2、來方便的同時(shí)，也對海量軌跡數(shù)據(jù)的管理和利用提出了極大的挑戰(zhàn)。如何高效的檢索軌跡數(shù)據(jù)，如何從軌跡數(shù)據(jù)中挖掘出對不同的應(yīng)用有價(jià)值的潛在信息，已經(jīng)成為時(shí)空數(shù)據(jù)管理和挖掘領(lǐng)域的一個(gè)重要研究課題。本文圍繞軌跡數(shù)據(jù)的檢索和挖掘，針對移動(dòng)對象和軌跡的κ近鄰檢索、軌跡數(shù)據(jù)的映射和地圖匹配、軌跡數(shù)據(jù)挖掘及其在智能交通中的應(yīng)用等若干重要問題展開研究，并結(jié)合實(shí)際應(yīng)用，給出了具體的解決方案和實(shí)際系統(tǒng)，這些研究成果具有重要的學(xué)術(shù)價(jià)值和廣泛的應(yīng)用前景。具體而言，本

3、文的主要研究成果、貢獻(xiàn)和創(chuàng)新點(diǎn)可概括為以下幾點(diǎn)：
　　 1)提出了一種路網(wǎng)中移動(dòng)對象連續(xù)κ近鄰檢索的高效近似算法。傳統(tǒng)的基于歐氏距離的κ近鄰算法不能適用于基于路網(wǎng)距離的移動(dòng)對象的κ近鄰檢索，現(xiàn)有的路網(wǎng)中移動(dòng)對象的κ近鄰檢索由于其計(jì)算代價(jià)巨大，很難適用于在線連續(xù)檢索。本文提出的方法通過從路網(wǎng)中提取特征集，利用離線計(jì)算與在線計(jì)算相結(jié)合的方式，實(shí)現(xiàn)了高效的連續(xù)κ近鄰的實(shí)時(shí)檢索。此外，本文針對算法復(fù)雜度和近似精度給出了理論分析和證明。<

4、br>　　 2)提出了κ近鄰軌跡檢索的概念，并將κ近鄰軌跡檢索問題轉(zhuǎn)化為聚合top-κ查詢問題。本文提出了在無隨機(jī)訪問情形下，top-κ聚合查詢的高效算法，本文針對實(shí)例最優(yōu)性和訪問時(shí)間進(jìn)行了理論分析和優(yōu)化，并在生成數(shù)據(jù)集和大量真實(shí)數(shù)據(jù)集上驗(yàn)證了該算法的高效性和有效性。
　　 3)提出了針對軌跡數(shù)據(jù)挖掘預(yù)處理的若干算法。針對軌跡數(shù)據(jù)在路網(wǎng)中的映射，本文提出了一個(gè)基于圖像處理中形態(tài)學(xué)方法的地圖分割算法，巧妙的解決了基于柵格的路網(wǎng)分

5、割問題；針對路網(wǎng)中的低采樣率軌跡，本文提出了一種基于相互投票的地圖匹配算法，該算法比現(xiàn)有最好的低采樣率軌跡算法提高了10％的匹配準(zhǔn)確率；針對地圖匹配中的錯(cuò)誤匹配結(jié)果，本文提出了一種多項(xiàng)式時(shí)間的平滑算法，解決了因錯(cuò)誤匹配導(dǎo)致的路徑迂回問題。
　　 4)提出并實(shí)現(xiàn)了一個(gè)基于出租車軌跡的智能行車路線規(guī)劃系統(tǒng)(T-Drive系統(tǒng))。該系統(tǒng)從大量的出租車GPS軌跡中挖掘有經(jīng)驗(yàn)的司機(jī)在路線規(guī)劃中的智能，同時(shí)結(jié)合實(shí)時(shí)交通狀況數(shù)據(jù)進(jìn)行分析和預(yù)測

6、，從而為普通的駕車用戶提供個(gè)性化的實(shí)際通行中的最快路線。本文在該系統(tǒng)中提出了一系列軌跡數(shù)據(jù)挖掘的模型和方法（如地標(biāo)圖模型、方差一熵聚類算法、基于高階馬爾科夫的交通預(yù)測模型），并以大量的實(shí)驗(yàn)比較了該系統(tǒng)和現(xiàn)有的路線規(guī)劃系統(tǒng)及算法，實(shí)驗(yàn)結(jié)果充分驗(yàn)證了該系統(tǒng)的有效性以及相對其他方法的優(yōu)越性。
　　 5)提出并實(shí)現(xiàn)了一個(gè)基于出租車軌跡的推薦系統(tǒng)(T-Finder系統(tǒng))。該系統(tǒng)給出租車司機(jī)推薦最易等到乘客的地點(diǎn)以及去往這些地點(diǎn)的路徑，并同