基于軌跡相似度的軌跡推薦算法

1、蘇州大學(xué)本科生畢業(yè)設(shè)計(jì)（論文）學(xué)院(部)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院題 目基于軌跡相似度的軌跡推薦算法目 錄摘 要1前 言3第一章 緒 論41.1 研究背景及意義41.2 本文的主要工作和創(chuàng)新點(diǎn)51.3本文的組織結(jié)構(gòu)6第二章 軌跡數(shù)據(jù)壓縮算法72.1 降采樣方法72.2 Douglas-Peucker算法82.3 離散傅里葉變換算法102.4 分段聚合近似算法112.5 基于速度和方向的軌跡壓縮算法122.6 基于GeoHash的數(shù)據(jù)點(diǎn)壓縮算法13第三章 軌跡相似度度量標(biāo)準(zhǔn)163.1 距離度量函數(shù)163.2 歐幾里得距離163.3 Dynamic Time Wraping173.4 Longest C

2、ommon Subsequences183.5 Edit Distance on Real Sequence19第四章 軌跡數(shù)據(jù)的存儲(chǔ)方法204.1 對(duì)空間點(diǎn)的存儲(chǔ)方法204.1.1 R樹(shù)系列204.1.2 KD樹(shù)系列214.2 對(duì)時(shí)間序列的存儲(chǔ)方法224.2.1 對(duì)點(diǎn)的倒排索引224.2.2 對(duì)特征維度的索引22第五章 基于軌跡相似度的軌跡推薦方法235.1 相似度模型235.2 索引策略245.3 算法流程255.4 實(shí)驗(yàn)和分析27第六章 總結(jié)與展望306.1 總結(jié)306.2 展望30參考文獻(xiàn)32致 謝3433摘 要本文以軌跡推薦問(wèn)題為突破口，研究并分析了軌跡的壓縮方法、軌跡相似度度量標(biāo)準(zhǔn)

3、、軌跡特征提取算法以及軌跡索引查詢(xún)方法等，并且綜合了已有方法的優(yōu)勢(shì)，針對(duì)已有方法的不足，設(shè)計(jì)了一套基于軌跡相似度的軌跡推薦算法，保證了高效而準(zhǔn)確的相似軌跡的推薦。具體的說(shuō)，本文開(kāi)展了以下研究：1. 一種軌跡數(shù)據(jù)的特征提取算法?，F(xiàn)有的對(duì)于軌跡數(shù)據(jù)的特征提取算法大多沒(méi)有考慮的軌跡數(shù)據(jù)的存儲(chǔ)和索引。這些提取出來(lái)的特征雖然能夠從一定程度上對(duì)軌跡數(shù)據(jù)進(jìn)行了降維，但是這樣的特征提取也只能算是一種數(shù)據(jù)壓縮，我們不能在保證沒(méi)有漏檢的情況下使用這些特征。而本文提出的方法則既能保證數(shù)據(jù)的壓縮效果，也能保證沒(méi)有漏檢情況的發(fā)生。2. 基于軌跡相似度的軌跡數(shù)據(jù)的推薦方法現(xiàn)有的軌跡推薦算法大都是基于機(jī)器學(xué)習(xí)算法，對(duì)軌跡數(shù)

4、據(jù)進(jìn)行聚類(lèi)，或者建立用戶(hù)畫(huà)像，在擁有相同用戶(hù)畫(huà)像的相似用戶(hù)之間互相推薦軌跡。本文在上面的軌跡數(shù)據(jù)的特征提取算法的基礎(chǔ)上，設(shè)計(jì)了一套基于軌跡相似度的軌跡推薦算法，單純的從軌跡相似的角度為用戶(hù)推薦軌跡數(shù)據(jù)。關(guān)鍵詞：軌跡相似度；文件索引；特征提?。卉壽E壓縮；相似度查詢(xún)AbstractThis paper studies and analyzes the trajectory compression method, the trajectory similarity metric, the trajectory feature extraction algorithm, and the traject

5、ory index query method, and integrates the advantages of the existing methods. A trajectory recommendation algorithm based on trajectory similarity is designed to ensure the efficient and accurate similar trajectory recommendation. Specifically, this article has carried out the following research:1.

6、 A feature extraction algorithm for trajectory data.Most existing feature extraction algorithms for trajectory data do not take the storage and indexing of trajectory data into account. Although these extracted features can reduce the dimension of the trajectory data to some extent, such feature ext

7、raction can only be regarded as a kind of data compression. We cannot use these features which may cause false dismissal. The method proposed in this paper not only guarantees the compression effect of data, but also ensures that no false dismissal occurs.2. Recommended method for trajectory data ba

8、sed on trajectory similarityMost of the existing trajectory recommendation algorithms are based on machine learning algorithms, clustering trajectory data, or creating user portraits, and recommending trajectories between similar users having the same user portrait. In this paper, a trajectory recom

9、mendation algorithm based on trajectory similarity is designed, which simply recommends the trajectory data for users from the perspective of trajectory similarity.Keywords: Trajectory Similarity; File Index; Feature Extraction; Trajectory Compression; Similarity Query前 言近年來(lái)，隨著無(wú)線(xiàn)定位設(shè)備的廣泛使用，我們能夠越來(lái)越方便的

10、獲得由這些定位設(shè)備發(fā)送的定位數(shù)據(jù)。這些數(shù)據(jù)通常由經(jīng)度、緯度、高度和其他輔助信息組成。這些數(shù)據(jù)給我們帶來(lái)了大量的研究?jī)r(jià)值，但是同時(shí)也給我們的計(jì)算和挖掘能力帶來(lái)了巨大的挑戰(zhàn)。龐大的數(shù)據(jù)量要求更好的數(shù)據(jù)存儲(chǔ)能力、更快的數(shù)據(jù)計(jì)算能力和更高的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)能力。同時(shí)，如何對(duì)這些數(shù)據(jù)進(jìn)行高效地應(yīng)用也是一個(gè)復(fù)雜的問(wèn)題。當(dāng)前，學(xué)術(shù)界對(duì)軌跡數(shù)據(jù)挖掘的研究正得到越來(lái)越多的重視。對(duì)于軌跡數(shù)據(jù)相似性問(wèn)題的研究可以追溯到度時(shí)間序列相似性問(wèn)題的研究。時(shí)間序列相似性問(wèn)題的最早研究論文由 Agrawal 等人在1993 年發(fā)表。起初加入研究行列的有 IBM 公司的 Agrawal 和 UC Irvine 的一些研究小組，在最近

11、一段時(shí)間內(nèi)則 UC Riverside 的 Eamonn Keogh 和 Carnegie Mellon 大學(xué)的 Christos Faloutsos 領(lǐng)導(dǎo)的研究小組則更加活躍。除此之外，UC Santa Barbara 大學(xué)、 Maryland 大學(xué)、New York 大學(xué)、Simon Fraser大學(xué)等都有對(duì)相應(yīng)進(jìn)行研究的研究小組。國(guó)內(nèi)的相關(guān)研究近年來(lái)勢(shì)頭強(qiáng)勁，其中有清華大學(xué)、復(fù)旦大學(xué)、浙江大學(xué)、中國(guó)科技大學(xué)、 西安交通大學(xué)、香港大學(xué)、香港城市大學(xué)等。而且不僅在學(xué)術(shù)界，在工業(yè)界也逐漸展開(kāi)了對(duì)軌跡序列的相似性問(wèn)題的研究。知名的研究機(jī)構(gòu)包括 Yahoo、IBM、Google 以及美國(guó)國(guó)家航空航

12、天局 NASA 等。這些公司都有很多專(zhuān)職人員參與本問(wèn)題的研究。一些資深的數(shù)據(jù)挖掘領(lǐng)域人士甚至認(rèn)為，對(duì)軌跡數(shù)據(jù)的挖掘已經(jīng)成為目前數(shù)據(jù)挖掘中最具挑戰(zhàn)性的問(wèn)題之一。以經(jīng)典的軌跡數(shù)據(jù)相似性查詢(xún)問(wèn)題為例，如何既保證查詢(xún)的效率，又能保證查詢(xún)的準(zhǔn)確性一直是一個(gè)值得權(quán)衡的問(wèn)題。在很多情景下，我們?yōu)榱吮ＷC查詢(xún)的準(zhǔn)確性，我們需要犧牲查詢(xún)的效率，采用全表查找等形式；在有的情形下我們可能不太關(guān)注查詢(xún)的精確度，這樣我們就可以通過(guò)粗略查找或者近似查找的方法，降低算法復(fù)雜度提高查詢(xún)的效率。為了同時(shí)提高算法的準(zhǔn)確率和執(zhí)行效率，本文對(duì)軌跡數(shù)據(jù)的壓縮、存儲(chǔ)和軌跡數(shù)據(jù)相似度度量標(biāo)準(zhǔn)進(jìn)行研究，以設(shè)計(jì)一個(gè)高效的基于軌跡相似度的軌跡推薦

13、算法為主要研究課題。第一章 緒 論本章首先介紹了軌跡存儲(chǔ)與推薦算法的研究背景和意義，其次概括了本文做的主要工作和貢獻(xiàn)，以及主要的創(chuàng)新點(diǎn)。最后介紹了本篇論文的組織結(jié)構(gòu)。1.1 研究背景及意義時(shí)間序列挖掘研究自從上世紀(jì) 90 年代提出以來(lái)，得到了國(guó)內(nèi)外的廣泛關(guān)注，成為研究的熱點(diǎn)領(lǐng)域之一。它包括時(shí)間序列的相似性搜索、聚類(lèi)、分類(lèi)、模式匹配、規(guī)則發(fā)現(xiàn)、異常檢測(cè)等各個(gè)方面。軌跡數(shù)據(jù)是時(shí)間序列的一種特殊形式，通常由經(jīng)度、緯度、高度和其他輔助信息組成，已經(jīng)成為諸如經(jīng)濟(jì)、管理、計(jì)算機(jī)、數(shù)學(xué)、電子等諸多學(xué)科的交叉研究范疇。軌跡數(shù)據(jù)相似性問(wèn)題也是時(shí)間序列挖掘中的一個(gè)基礎(chǔ)問(wèn)題，它的主要研究?jī)?nèi)容是判別軌跡數(shù)據(jù)是否相似、

14、如何衡量相似程度、如何比較軌跡的相似等，它的外在表現(xiàn)是軌跡數(shù)據(jù)的相似性搜索。隨著各種無(wú)線(xiàn)通信和定位技術(shù)的高速發(fā)展，人們可以非常方便地收集到大量軌跡數(shù)據(jù)。軌跡數(shù)據(jù)具有很高的應(yīng)用價(jià)值，人們可以進(jìn)行通過(guò)運(yùn)用這些數(shù)據(jù)進(jìn)行相應(yīng)的數(shù)據(jù)分析來(lái)實(shí)現(xiàn)很多重要的功能。如根據(jù)日常活動(dòng)軌跡，我們可以向人們推薦潛在的朋友；根據(jù)動(dòng)作的軌跡，我們可以進(jìn)行人們動(dòng)作目的的識(shí)別；根據(jù)已有的車(chē)輛軌跡，我們可以向駕駛員推薦最為流行的行車(chē)路線(xiàn)等。相似軌跡查找是對(duì)軌跡數(shù)據(jù)進(jìn)行充分運(yùn)用的基礎(chǔ)功能之一，即要求對(duì)于給定的某個(gè)時(shí)間序列，從大型數(shù)據(jù)集合中找出與之相似的時(shí)間序列1，主要包括軌跡相似度度量、軌跡數(shù)據(jù)壓縮、軌跡數(shù)據(jù)存儲(chǔ)、軌跡推薦等。但是

15、，由于軌跡數(shù)據(jù)獲取的方便性，軌跡數(shù)據(jù)的規(guī)模也在呈幾何數(shù)量地增加。因此如何更快、更好、更高效地進(jìn)行軌跡查找就成了現(xiàn)階段的一個(gè)巨大的挑戰(zhàn)。更快，就是要求能夠盡可能減少單次查詢(xún)的時(shí)間消耗；更好，就是要求查詢(xún)的結(jié)果更加符合給定的要求；更高效，就是指將空間和性能運(yùn)用在更有價(jià)值的地方。近幾年，相似軌跡的查詢(xún)研究有了很大的進(jìn)步，提出了很多有效的算法。在軌跡壓縮方面，提出了通過(guò)減少軌跡點(diǎn)的冗余度來(lái)加速軌跡查詢(xún)的各種軌跡壓縮算法，代表性的有Douglas-Peucker算法2、離散傅里葉變換方法、奇異值分解方法3、滑動(dòng)窗口法4等。在軌跡相似度度量方面，提出了通過(guò)設(shè)計(jì)更優(yōu)化的相似度度量標(biāo)準(zhǔn)來(lái)節(jié)約時(shí)間的各種下限算法

16、，常用的算法有LB_Kim5、LB_Yi6、LB_Keogh7、LB_PAA8等。在軌跡存儲(chǔ)方面，提出了通過(guò)設(shè)計(jì)更加優(yōu)秀的索引結(jié)構(gòu)和搜索樹(shù)來(lái)加快查找的過(guò)程。上述的各種方法各有優(yōu)缺點(diǎn)，我們將在第二章到第五章中進(jìn)行詳細(xì)地分析說(shuō)明。1.2 本文的主要工作和創(chuàng)新點(diǎn)本文總結(jié)并分析了目前較為流行的軌跡數(shù)據(jù)加工處理的方法，詳細(xì)研究了各種軌跡壓縮技術(shù)、軌跡相似度度量標(biāo)準(zhǔn)、軌跡特征提取算法以及軌跡索引查詢(xún)方法等，分析了各自的應(yīng)用場(chǎng)景和優(yōu)缺點(diǎn)。并提出了一套高效的對(duì)相似軌跡進(jìn)行查詢(xún)的方法。和原有算法相比，該算法具有如下創(chuàng)新：（1）基于文件索引。不需要同時(shí)將所有數(shù)據(jù)讀入內(nèi)存，適合對(duì)大量數(shù)據(jù)進(jìn)行查找。并且利用索引文件，

17、不需要進(jìn)行全表查找，可以更高效地進(jìn)行查找，有效提高了查詢(xún)效率，減少了查詢(xún)時(shí)間。（2）支持增量添加數(shù)據(jù)。在數(shù)據(jù)集擴(kuò)大時(shí)不需要重新構(gòu)建索引，只需要按照規(guī)則將新添加的數(shù)據(jù)加入數(shù)據(jù)集即可，具有較強(qiáng)的擴(kuò)展性。（3）不會(huì)出現(xiàn)漏檢（False Dismissal，F(xiàn)D）的情況。為了提高數(shù)據(jù)的查詢(xún)效率，當(dāng)前很多查詢(xún)方案都將類(lèi)似KNN（k Nearest Neighbor）的問(wèn)題描述為ANN（Approximate Nearest Neighbor）問(wèn)題。由于不需要保證結(jié)果的絕對(duì)準(zhǔn)確性，所以ANN問(wèn)題的解決速度比KNN問(wèn)題快得多，但是代價(jià)就是要犧牲準(zhǔn)確率，他無(wú)法保證檢索出最合適的結(jié)果，而是一個(gè)較為合適的結(jié)果。本

18、文提出的方案既可以保證高效率，也可以杜絕漏檢情況的發(fā)生。（4）支持不等長(zhǎng)軌跡數(shù)據(jù)的比較。即使是軌跡數(shù)據(jù)長(zhǎng)度不同，該算法也可以高效的進(jìn)行比較以及索引。本文利用的MSRA（Microsoft Research Asia）提供的GeoLife數(shù)據(jù)集9-11對(duì)本文提出的方法進(jìn)行了仿真實(shí)驗(yàn)，并與當(dāng)前已有的方法進(jìn)行了對(duì)比分析，驗(yàn)證了本文提出的方法的正確性和高效性。1.3 本文的組織結(jié)構(gòu)本文共分為六章，各章節(jié)的安排如下：第一章為緒論。本章首先簡(jiǎn)要介紹了本文所涉及的研究課題的背景、意義、實(shí)際應(yīng)用等。然后概括了本文的主要工作和創(chuàng)新點(diǎn)，最后闡述了本文的組織結(jié)構(gòu)。第二章：軌跡數(shù)據(jù)壓縮算法。本章主要介紹了當(dāng)前主流的軌

19、跡數(shù)據(jù)壓縮算法，并且分析了各個(gè)算法的優(yōu)劣和應(yīng)用場(chǎng)景。第三章：軌跡相似度度量標(biāo)準(zhǔn)。本章主要介紹了收到學(xué)術(shù)界廣泛認(rèn)可的相似度度量標(biāo)準(zhǔn)以及這些度量標(biāo)準(zhǔn)的優(yōu)化版本、下界版本。第四章：軌跡數(shù)據(jù)的存儲(chǔ)方法。本章主要介紹了用于存儲(chǔ)軌跡數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)以及常用的查找方法。第五章：基于軌跡相似度的軌跡推薦方法。本章主要介紹了本文提出的基于軌跡相似度的推薦算法，同時(shí)通過(guò)實(shí)驗(yàn)加以對(duì)比分析。第六章：總結(jié)與展望。總結(jié)全文，提出未來(lái)工作的設(shè)想與展望。第二章 軌跡數(shù)據(jù)壓縮算法通常而言，大多數(shù)的軌跡數(shù)據(jù)都是通過(guò)傳感器定時(shí)采集物體的運(yùn)動(dòng)狀態(tài)，并將數(shù)據(jù)進(jìn)行存儲(chǔ)。由于傳感器的采樣率不同，數(shù)據(jù)獲取的密度也有所差異。大多情況下，對(duì)于車(chē)輛

20、軌跡的采樣間隔是秒級(jí)的，而對(duì)行人軌跡采樣的間隔大約是分鐘級(jí)的。在這種采集頻率下，每一輛車(chē)一天就大約可以采集到4GB左右的數(shù)據(jù)，而每一個(gè)行人每一天就大約可以采集到160GB的軌跡數(shù)據(jù)。這導(dǎo)致了采集得到的軌跡數(shù)據(jù)的規(guī)模非常大，其中很多軌跡點(diǎn)包含了很多的冗余信息，有效信息較少，沒(méi)有存儲(chǔ)的必要性。為了能夠減少存儲(chǔ)時(shí)的總數(shù)據(jù)量，并提高存儲(chǔ)的每一個(gè)點(diǎn)的有效性，現(xiàn)階段提出了很多軌跡數(shù)據(jù)壓縮方法。本文詳細(xì)闡述了目前廣泛使用的一些軌跡數(shù)據(jù)壓縮算法，并對(duì)它們進(jìn)行了對(duì)比分析，分別闡述了它們的優(yōu)勢(shì)和缺點(diǎn)，以及在實(shí)際生活中適用的場(chǎng)景。12.1 降采樣方法減少一條軌跡中軌跡點(diǎn)的個(gè)數(shù)最簡(jiǎn)單而直觀(guān)的方法就是降低采樣率。比如對(duì)

21、于一個(gè)可控的采樣設(shè)備，原本是每隔五秒鐘獲取一個(gè)坐標(biāo)數(shù)據(jù)，使用降采樣方法，可以修改為每隔一分鐘獲取一個(gè)坐標(biāo)數(shù)據(jù)，這樣數(shù)據(jù)量就減少為了原先的十二分之一。通過(guò)講采樣時(shí)間間隔改為更大的樹(shù)枝，可以達(dá)到獲取較少的軌跡數(shù)據(jù)的目的。對(duì)于采樣率固定的設(shè)備，無(wú)法更改采樣時(shí)間，可以通過(guò)一些數(shù)據(jù)過(guò)濾算法對(duì)數(shù)據(jù)點(diǎn)進(jìn)行過(guò)濾。通常來(lái)說(shuō)，數(shù)據(jù)過(guò)濾方法可以分為兩種：（1）在線(xiàn)過(guò)濾。這類(lèi)方法主要適用于一些不停獲得的流式數(shù)據(jù)。這些數(shù)據(jù)的重要級(jí)別通常比較低，因此可以設(shè)置一個(gè)較低的采樣率，讓存儲(chǔ)設(shè)備每隔N個(gè)數(shù)據(jù)存儲(chǔ)一次，這樣數(shù)據(jù)量就可以縮減到原來(lái)的1/N。有時(shí)候?yàn)榱藴p少舍棄的軌跡點(diǎn)造成的影響，可以設(shè)置一個(gè)緩存窗口，每當(dāng)獲得一個(gè)軌跡點(diǎn)，

22、就將這個(gè)軌跡點(diǎn)添加進(jìn)緩存窗口。當(dāng)窗口滿(mǎn)了的時(shí)候，計(jì)算窗口里所有軌跡點(diǎn)的平均值，得到相應(yīng)的平均點(diǎn)，將這個(gè)平均點(diǎn)加入最終的軌跡序列，并且將緩存窗口清空。（2）離線(xiàn)過(guò)濾。這類(lèi)方法主要適用于數(shù)據(jù)已經(jīng)完全獲取的情況。該類(lèi)算法通過(guò)對(duì)存儲(chǔ)的軌跡點(diǎn)進(jìn)行隨機(jī)采樣，或按照固定間隔進(jìn)行刪減，達(dá)到壓縮存儲(chǔ)的軌跡點(diǎn)個(gè)數(shù)的目的。降采樣方法非常的簡(jiǎn)單、易用、可靠。在大多數(shù)場(chǎng)景下都能使用，而且可以精準(zhǔn)的控制壓縮后軌跡點(diǎn)的個(gè)數(shù)，非常便捷。但是該類(lèi)算法常常受到個(gè)采樣率的選擇的影響。在不同場(chǎng)景或是相同場(chǎng)景的不同階段，采樣率的最佳選擇都會(huì)有所差異。如果將采樣率設(shè)置得太低，那么將會(huì)有大量的軌跡點(diǎn)丟失，和原始軌跡出入較大；如果將采樣率設(shè)

23、置得太高，那么仍然保留了很多冗余的數(shù)據(jù)，壓縮不完全。而且由于刪減軌跡點(diǎn)方法常常帶有隨機(jī)性，很容易將一些重要的軌跡點(diǎn)刪除，導(dǎo)致壓縮后的軌跡失去了某些重要的特征。總而言之，由于降采樣的方法簡(jiǎn)單，高效，適合快速地將一些稠密的軌跡點(diǎn)變得稀疏，所以比較適合用于對(duì)軌跡做初步的壓縮。2.2 Douglas-Peucker算法Douglas-Peucker算法12是一個(gè)經(jīng)典的軌跡數(shù)據(jù)壓縮算法，彌補(bǔ)了樸素降采樣方法容易使軌跡失去關(guān)鍵特征的不足。該算法的原理是只刪除對(duì)軌跡特征影響比較小的點(diǎn)，從而保證能夠保留軌跡的絕大部分特征。Douglas-Peucker算法的具體步驟如下：Douglas-Peucker算法輸入

24、：T一條軌跡輸入：i軌跡起點(diǎn)的序號(hào)輸入：j軌跡終點(diǎn)的序號(hào)輸入：預(yù)設(shè)的誤差閾值輸出：壓縮之后的軌跡1. function DOUGLASPEUCKER(T,i,j,)2. 找出pi+1:pj1中距離線(xiàn)段pipj最遠(yuǎn)的點(diǎn)pf，并設(shè)這個(gè)距離為dist3. if dist4. DOUGLASPEUCKER(T,i,f,)5. DOUGLASPEUCKER(T,f,j,)6. else7. 輸出pipj以pipj作為近似軌跡通過(guò)一個(gè)例子對(duì)Douglas-Peucker算法進(jìn)行簡(jiǎn)單的說(shuō)明。給定一個(gè)軌跡序列T=，首先連接p0和p16 ，分別計(jì)算剩余點(diǎn)到這條線(xiàn)段的垂直距離，如圖2.1(a)所示。從圖2.1(a

25、)中可以看出，p9離這條線(xiàn)段的距離最大，那么就選擇該點(diǎn)作為下一個(gè)分段點(diǎn)，將這個(gè)軌跡分割為p0p9,p9p16兩部分，如圖2.2(b)所示，(a) 步驟一(b) 步驟二(c) 步驟三圖2.1 Douglas-Peucker算法步驟然后對(duì)這兩個(gè)部分遞歸這個(gè)過(guò)程，于是又將該軌跡分成了四段，如圖2.3(c)所示。假設(shè)到此為止，所有的點(diǎn)到他所屬的連線(xiàn)的距離均小于閾值，那么這個(gè)時(shí)候，就可以用p0p3p9p16表示整個(gè)軌跡。從圖2.1中可以看出，雖然軌跡點(diǎn)的數(shù)量大大減少了，但是壓縮后得到的軌跡點(diǎn)仍然能夠較好地保持了原先軌跡的特征。Douglas-Peucker算法通過(guò)計(jì)算，在軌跡壓縮的同時(shí)，也有選擇地保留維

26、護(hù)軌跡最大特征的軌跡點(diǎn)，很大程度的消除了冗余的軌跡點(diǎn)。同時(shí)這個(gè)算法的壓縮程度也是可控的，壓縮率也可以與軌跡的還原率成正比。但是該算法的時(shí)間復(fù)雜度為O(n2)，相較于其他軌跡壓縮算法，運(yùn)行速率較慢。雖然也有一些相關(guān)的加速算法13，能夠?qū)⒃擃?lèi)算法的復(fù)雜度優(yōu)化到O(nlog2n)，但是優(yōu)化后的算法的靈活性就下降了很多。同時(shí)，如果閾值設(shè)置對(duì)Douglas-Peucker算法也有很大的影響。2.3 離散傅里葉變換算法離散傅里葉變換算法14也經(jīng)常用來(lái)對(duì)時(shí)序數(shù)據(jù)進(jìn)行將降維。離散傅里葉變換本質(zhì)上是一種譜分解算法，理論上可以用多個(gè)正弦波去擬合任何一個(gè)函數(shù)。因此對(duì)于一個(gè)長(zhǎng)度為n的時(shí)間序列，可以通過(guò)n個(gè)正弦波來(lái)組合

27、還原。由于這n個(gè)正弦波所占的比重不同，可以去掉這當(dāng)中對(duì)軌跡貢獻(xiàn)較小的那些正弦波，用留下來(lái)的波來(lái)表示整個(gè)序列。離散傅里葉變換算法特征分解如圖2.2所示。圖2.2 離散傅里葉變換的特征分解圖從圖2.2可知，對(duì)于給定一維序列X，我們可以通過(guò)將四條正弦波按不同權(quán)重進(jìn)行加權(quán)得到X，并用X作為X的近似序列。在數(shù)據(jù)壓縮的同時(shí)，也很好地保留了X的重要基本特征。但是，由于軌跡數(shù)據(jù)并不是單純的一維時(shí)間序列，而是二維時(shí)間序列，因此需要分別對(duì)時(shí)間序列的兩個(gè)維度都進(jìn)行離散傅里葉變換。原始離散傅里葉變換算法的復(fù)雜度是O(N2)，快速傅里葉變換可以將算法復(fù)雜度優(yōu)化到O(NlogN)。離散傅里葉變換比較適合擬合運(yùn)動(dòng)變化較為頻

28、繁的軌跡，對(duì)于行人或者車(chē)輛這種方向變化不大的軌跡壓縮的效果并不是特別好。所以在實(shí)際運(yùn)用中，離散傅里葉變換通常被用于一維的時(shí)間序列的壓縮而很少被用來(lái)做軌跡數(shù)據(jù)的壓縮。2.4 分段聚合近似算法分段聚合近似（Piecewise Aggregate Approximation，PAA）是一個(gè)非常經(jīng)典的對(duì)軌跡數(shù)據(jù)進(jìn)行壓縮近似的算法。該算法的目的是對(duì)于一條給定的長(zhǎng)度為n的軌跡T=x1,y1,x2,y2,(xn,yn)，將它壓縮為一個(gè)長(zhǎng)度為n的軌跡T，其中nn。那么分段聚合近似算法即首先對(duì)軌跡段進(jìn)行平均分段，然后對(duì)每一個(gè)分段求一個(gè)平均值作為最終結(jié)果的一部分。具體的計(jì)算方法如下：xi=nNj=N/n(i1)+

29、1N/nixj (2.1)yi=nNj=N/n(i1)+1N/niyj (2.2)可以通過(guò)控制n的值來(lái)控制壓縮的比例以及還原度的比例。當(dāng)n越大時(shí)，還原度越高，壓縮率越低；當(dāng)n越小時(shí)，還原度越低，壓縮率越高，當(dāng)n縮小到1的時(shí)候，軌跡就退化成了一個(gè)軌跡點(diǎn)。對(duì)圖2.3中的軌跡X，我們采用分段聚合近似來(lái)將其分割成八段，最終組合成近似軌跡X，如圖2.3所示。可以看出，分段聚合近似組成的軌跡還是能夠從整體上保證軌跡的特征不會(huì)丟失，而且計(jì)算的復(fù)雜度比較低，相比之前算法動(dòng)輒O(N2)的復(fù)雜度，他只需要O(N)即可完成壓縮。不過(guò)在每個(gè)分段求平均值這個(gè)做法很有可能會(huì)帶來(lái)“平均值陷阱”，使得該分段內(nèi)的極大和極小的特

30、征被平均化了，從一定程度上會(huì)導(dǎo)致特征的丟失。圖2.3 分段聚合近似特征分解圖2.5 基于速度和方向的軌跡壓縮算法基于速度和方向的軌跡壓縮算法是專(zhuān)門(mén)用于車(chē)輛軌跡這種帶有明顯的方向和速度特性的軌跡的壓縮。原始的軌跡壓縮算法僅僅考慮軌跡的幾何特征，而沒(méi)有考慮軌跡本身的含義。對(duì)于車(chē)輛軌跡而言，駕駛員關(guān)注的不是自己的歷史軌跡，而是自身的方向和速度，因此可以根據(jù)這個(gè)特性，使用基于速度和方向的軌跡壓縮算法對(duì)軌跡進(jìn)行壓縮15。軌跡壓縮算法需要事先設(shè)定速度閾值和方向容忍度閾值。根據(jù)這兩個(gè)閾值可以從前一個(gè)軌跡點(diǎn)預(yù)測(cè)出下一個(gè)軌跡點(diǎn)應(yīng)當(dāng)出現(xiàn)范圍。如果新的軌跡點(diǎn)落在這個(gè)范圍內(nèi)，則將這個(gè)新的軌跡點(diǎn)舍棄，否則就將新的軌跡點(diǎn)

31、加入最終的近似軌跡中，如圖2.4所示圖2.4 基于速度和方向的軌跡壓縮算法示意圖首先設(shè)定一個(gè)速度的范圍，比如設(shè)置速度區(qū)間為a,b，然后設(shè)定一個(gè)角度的旋轉(zhuǎn)區(qū)間。對(duì)于上圖中的這條軌跡T=，首先將p0p1加入壓縮后的軌跡集，然后延長(zhǎng)p0p1，通過(guò)之前設(shè)定的速度區(qū)間和角度旋轉(zhuǎn)區(qū)間，以及p1到p2的采樣時(shí)間隔的時(shí)間，可以預(yù)測(cè)出p2點(diǎn)允許出現(xiàn)的扇形區(qū)域。如果p2確實(shí)落在這個(gè)扇形區(qū)間，就說(shuō)明p2這個(gè)點(diǎn)具有的信息量有限，沒(méi)有存儲(chǔ)的必要，則舍棄該軌跡點(diǎn)，從而達(dá)到軌跡壓縮的目的。在圖2.4中，軌跡點(diǎn)p2,p5,p6,p8,p11,p12,p13,p14,p15都可以根據(jù)如上原則被刪除，從而得到壓縮后的軌跡。基于速

32、度和方向的軌跡壓縮算法相較于之前的軌跡壓縮方法，可能會(huì)保留更多的軌跡點(diǎn)，但是這種算法壓縮后的軌跡不僅保留了原軌跡的形狀信息，而且保留了原軌跡的方向和速度信息。同時(shí)該算法的復(fù)雜度只有O(N)。2.6 基于GeoHash的數(shù)據(jù)點(diǎn)壓縮算法軌跡數(shù)據(jù)是時(shí)間序列數(shù)據(jù)的一種，但是與時(shí)間序列數(shù)據(jù)有所差異，即時(shí)間序列數(shù)據(jù)除了時(shí)間維度之外可以看成是一維的，而軌跡序列中承載的數(shù)據(jù)卻是一個(gè)二維（經(jīng)度、維度），甚至是三維（高度）的。因此為了方便后期的比較，可以先將一個(gè)二位數(shù)據(jù)點(diǎn)壓縮成一個(gè)一維的數(shù)據(jù)。將二維數(shù)據(jù)轉(zhuǎn)化為一維數(shù)據(jù)最經(jīng)典的模型就是皮亞諾曲線(xiàn)。皮亞諾曲線(xiàn)是一個(gè)曲線(xiàn)序列的極限，一個(gè)能填滿(mǎn)一個(gè)封閉圖形的不可導(dǎo)的曲線(xiàn)。

33、與皮亞諾曲線(xiàn)有異曲同工之妙的就是GeoHash算法。GeoHash算法首先將地球作為一個(gè)大的區(qū)域，然后這個(gè)區(qū)域沿著東西、南北方向分別進(jìn)行二分，對(duì)每一個(gè)子區(qū)域進(jìn)行編碼；然后再對(duì)每一個(gè)子區(qū)域進(jìn)行二分，再編碼重復(fù)這個(gè)操作，直至精度滿(mǎn)足給定的要求。這樣每一個(gè)坐標(biāo)點(diǎn)（其實(shí)是一個(gè)近似于點(diǎn)的區(qū)域）就對(duì)應(yīng)于一個(gè)數(shù)值，可以用這個(gè)一維的值來(lái)代替二維的坐標(biāo)點(diǎn)。以經(jīng)緯度值（116.389550, 39.928167）為例。首先對(duì)緯度39.928167進(jìn)行逼近編碼。具體如圖2.5所示。圖2.5 GeoHash算法編碼示意圖根據(jù)圖2.5可以看出，在精度等級(jí)為15時(shí)，緯度部分的GeoHash編碼值是“11010010110

34、0010”，同理，經(jīng)度部分的編碼值就是“101110001100011”。然后將經(jīng)度和維度的編碼值交叉組合，經(jīng)度的編碼放在偶數(shù)位，維度的編碼放在奇數(shù)位，并且將得到的01串轉(zhuǎn)化為十進(jìn)制數(shù)字，再轉(zhuǎn)化為base32編碼，即可得到這個(gè)坐標(biāo)點(diǎn)對(duì)應(yīng)的GeoHash編碼“wx4g0e”。將這些編碼值從大到小進(jìn)行連線(xiàn)，可以發(fā)現(xiàn)這其實(shí)就是填充了整個(gè)平面的Z階曲線(xiàn)，如圖2.6所示。圖2.6 GeoHash算法的Z階曲線(xiàn)GeoHash能夠在精度允許的范圍內(nèi)將二位數(shù)據(jù)有效壓縮為一維數(shù)據(jù)，但是美中不足的是GeoHash編碼無(wú)法保證二維坐標(biāo)相鄰的點(diǎn)的編碼值也相鄰，因此并不方便做索引。從圖2.6中，我們可以看出相鄰的點(diǎn)基本

35、保持相鄰關(guān)系，但是仍然存在一些“突變”的位置。如果在軌跡查詢(xún)的時(shí)候查詢(xún)到了這些軌跡點(diǎn)，那么就很容易出現(xiàn)漏檢的情況。由于GeoHash簡(jiǎn)單、快捷、節(jié)約存儲(chǔ)的特點(diǎn)，在對(duì)查詢(xún)精度要求不高的情況下，GeoHash的用處非常多。但是如果場(chǎng)景對(duì)查詢(xún)精度有要求，那么GeoHash可能表現(xiàn)效果不佳。第三章 軌跡相似度度量標(biāo)準(zhǔn)如何衡量?jī)蓷l軌跡之間的相似性是相似軌跡進(jìn)行查詢(xún)時(shí)的核心問(wèn)題之一。由于在不同場(chǎng)景下軌跡查詢(xún)的側(cè)重點(diǎn)不同，因此相似度度量標(biāo)準(zhǔn)也不同。在本章，我們對(duì)一些常用的相似軌跡度量標(biāo)準(zhǔn)進(jìn)行分析說(shuō)明。23.1 距離度量函數(shù)首先給出關(guān)于軌跡的距離度量函數(shù)的定義：對(duì)于給定的一個(gè)定義在軌跡數(shù)據(jù)上的空間T，以及任意

36、兩條T中的軌跡x與yT上的距離度量函數(shù)d定義為：d:TTR (3.1)其中R是實(shí)數(shù)空間，且d具有如下性質(zhì)：(1) dx,y0（非負(fù)性）(2) dx,y=0x=y（自反性）(3) dx,y=d(y,x)（對(duì)稱(chēng)性）(4) （可選）dx,ydx,z+dz,y，x,y,zT（三角不等式）前三條性質(zhì)是距離函數(shù)的必備條件，且比較容易滿(mǎn)足。最后一個(gè)三角形不等式性質(zhì)很多距離度量函數(shù)較難滿(mǎn)足。在大多數(shù)情況下，三角形不等式的性質(zhì)不是距離函數(shù)的必備條件。但是嚴(yán)格來(lái)說(shuō)，如果一個(gè)距離度量函數(shù)不滿(mǎn)足三角形不等式，那么它的價(jià)值相對(duì)較低，因?yàn)椴粷M(mǎn)足三角形不等式的距離函數(shù)無(wú)法滿(mǎn)足通常所理解的“兩點(diǎn)之間直線(xiàn)最短”的概念，這也意味

37、著它不存在極限唯一性，所以不能用來(lái)做索引比較。因此，如果說(shuō)一個(gè)函數(shù)能夠滿(mǎn)足上述的定義，那么就認(rèn)為它是一個(gè)合格的距離度量函數(shù)。3.2 歐幾里得距離歐幾里得距離是一個(gè)非常經(jīng)典的距離度量單位，也被一直用來(lái)進(jìn)行軌跡之間的距離度量。歐幾里得距離的定義如下：給定兩條長(zhǎng)為n的時(shí)間序列A與B，它們之間的 歐幾里得距離定義為：eud(A,B)=i=1naibi2 (3.2)其中ai和bi分別是時(shí)間序列A與B的第i個(gè)元素。顯然，軌跡間的歐幾里得距離其實(shí)就是計(jì)算兩個(gè)長(zhǎng)度相同的軌跡中對(duì)應(yīng)點(diǎn)的距離，并求和歸一化。歐幾里得距離是 lpnorm的一個(gè)特例。lpnorm定義為：lpnorm (A,B)= pi=1naibip

38、 (3.3)當(dāng)p=2的時(shí)候，就是歐幾里得距離。類(lèi)似的，當(dāng)p=1時(shí)，l1norm是曼哈頓距離，當(dāng)p=的時(shí)候，lnorm就變成了：lnorm=nmax i=1aibi (3.4)歐距離以及l(fā)pnorm已經(jīng)被廣泛的作為相似軌跡的度量標(biāo)準(zhǔn)，這種方法計(jì)算簡(jiǎn)單，物理含義直觀(guān)，而且復(fù)雜度較低。不過(guò)它們只能夠用來(lái)比較兩條軌跡長(zhǎng)度相同的軌跡，對(duì)于軌跡長(zhǎng)度不同的兩條軌跡，便無(wú)法使用了。3.3 Dynamic Time WrapingDTW（Dynamic Time Wraping）最先被用于語(yǔ)音識(shí)別，能夠比較好地處理局部時(shí)間偏移，計(jì)算兩條不等長(zhǎng)的序列之間的距離。DTW距離定義如下：DTWA,B=, if m=0

39、or n=0dista1,b1+minDTWRestA,RestBDTW(RestA,B)DTW(A,RestB), else (3.5)其中m和n分別時(shí)間序列A與B的長(zhǎng)度，Rest(A)表示出去除去第一個(gè)點(diǎn)后的序列A，Rest(B)表示除去第一個(gè)點(diǎn)后的序列B，dist(a1,b1)表示這兩個(gè)點(diǎn)之間的距離，通常是歐氏距離。如圖3.1所示，DTW能通過(guò)對(duì)某些點(diǎn)進(jìn)行復(fù)制，從而計(jì)算出不等長(zhǎng)時(shí)間序列之間的距離，從而反應(yīng)出兩個(gè)序列之間的相似程度。但是由于DTW距離的時(shí)間復(fù)雜度為O(mn)，當(dāng)序列長(zhǎng)度變長(zhǎng)時(shí)，計(jì)算的性能會(huì)很差。針對(duì)DTW較高的時(shí)間復(fù)雜度的問(wèn)題，國(guó)內(nèi)外的研究人員也提出了很多優(yōu)化算法，比如LB

40、_Keogh16, LB_Improved17。這些優(yōu)化算法基本是通過(guò)限制兩個(gè)匹配點(diǎn)之間的范圍差來(lái)計(jì)算一個(gè)標(biāo)準(zhǔn)DTW的下限，但是這些算減小時(shí)間復(fù)雜度的同時(shí)，也犧牲了精度。DTW算法能夠非常方便的比較兩個(gè)不等長(zhǎng)軌跡的“距離”，因此在實(shí)際使用中應(yīng)用非常廣泛。但是它有一個(gè)致命的缺陷，就是DTW距離并不滿(mǎn)足三角形不等式，因此從嚴(yán)格意義上講，并不是一個(gè)好的距離度量單位。圖3.1 DTW算法軌跡點(diǎn)匹配示意圖3.4 Longest Common SubsequencesLCSS（Longest Common Subsequences）算法通常被用于帶有噪聲序列的降噪處理18。該算法通過(guò)比較給定的兩條序列之間

41、的對(duì)應(yīng)點(diǎn)來(lái)完成降噪處理，它的具體定義如下：LCSSA,B=0, if m=0 or n=0LCSSRestA,RestB+1,if dista1,b1maxLCSSRestA,B,LCSSA,RestB,else (3.6)LCSS算法常被描述為相似度度量標(biāo)準(zhǔn)，而不是距離度量標(biāo)準(zhǔn)，所以為了將相似度度量標(biāo)準(zhǔn)轉(zhuǎn)換成距離度量標(biāo)準(zhǔn)，需要做如下處理：LCSSdistA,B=1LCSS(A,B)min(A,|B|) (3.7)LCSS算法需要一個(gè)閾值來(lái)判斷兩個(gè)點(diǎn)是否在誤差允許的范圍內(nèi)。從公式(3.7)中我們可以看出，LCSSdis0,1，而且數(shù)值越大，說(shuō)明這兩個(gè)軌跡越相似。LCSS算法有一個(gè)極佳的特性就是

42、它能夠消除異常值帶來(lái)的影響。DTW算法和歐氏距離中計(jì)算過(guò)程中每一個(gè)點(diǎn)都會(huì)對(duì)影響最終的計(jì)算結(jié)果，而LCSS算法會(huì)有選擇的放棄一些誤差較大的點(diǎn)，減小部分點(diǎn)對(duì)最終結(jié)果的影響。不過(guò)LCSS算法執(zhí)行的復(fù)雜度是O(A|B|)，時(shí)間運(yùn)行效率比較低，而且LCSS也不支持三角形不等式，無(wú)法方便地進(jìn)行索引比較。3.5 Edit Distance on Real SequenceLCSS算法能夠有效地降低異常值帶來(lái)的影響，但是卻不能區(qū)分具有相同子序列但是大小不同的軌跡。因此Lei Chen等人19提出了EDR（Edit Distance on Real Sequence）函數(shù)作為新的距離度量標(biāo)準(zhǔn)。EDR距離定義如下

43、：EDRA,B=n, if m=0m,if n=0minEDRRestA,RestB+0,if distHeadA,HeadB1,elseEDRA,RestB+1EDRRestA,B+1(3.8)EDR也需要一個(gè)最小距離閾值來(lái)判斷兩個(gè)點(diǎn)是否是同一個(gè)點(diǎn)。由于EDR能夠匹配間隔不相同的兩個(gè)軌跡，因此比LCSS更加準(zhǔn)確，也更加具有代表性，不過(guò)相較于其它算法，EDR的時(shí)間復(fù)雜度并沒(méi)有什么優(yōu)勢(shì)。第四章 軌跡數(shù)據(jù)的存儲(chǔ)方法為了能夠更高效的對(duì)軌跡數(shù)據(jù)進(jìn)行查找，需要對(duì)軌跡數(shù)據(jù)進(jìn)行存儲(chǔ)和檢索。從本質(zhì)上講，軌跡數(shù)據(jù)其實(shí)可以看成是時(shí)間序列和空間點(diǎn)的結(jié)合，而無(wú)論從時(shí)間序列，還是空間點(diǎn)的角度上講，我們都需要一個(gè)能夠索引

44、多維數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。本章將會(huì)對(duì)一下目前常用的對(duì)多維數(shù)據(jù)進(jìn)行存儲(chǔ)的方法進(jìn)行分析。34.1 對(duì)空間點(diǎn)的存儲(chǔ)方法對(duì)空間點(diǎn)進(jìn)行存儲(chǔ)的方法目前在業(yè)界已經(jīng)比較成熟，絕大多數(shù)主流數(shù)據(jù)庫(kù)都支持對(duì)多維數(shù)據(jù)的存儲(chǔ)和索引。而且隨著相關(guān)方面研究的深入，提出了很多優(yōu)化算法。不過(guò)總體來(lái)說(shuō)，存儲(chǔ)和索引方法通?；臼菄@兩個(gè)基本模型進(jìn)行深入優(yōu)化的：一個(gè)是R樹(shù)，另一個(gè)就是KD樹(shù)。1.2.3.4.4.1.4.1.1 R樹(shù)系列R樹(shù)是GUTTMAN于1984年提出的最早支持有序擴(kuò)展的對(duì)象存取方法之一，并且也是目前為止應(yīng)用最為廣泛的一種空間索引結(jié)構(gòu)。許多人們耳熟能詳?shù)目臻g數(shù)據(jù)庫(kù)系統(tǒng)，比如Oracle Spatial，PostgreSQ

45、L和MapInfo SpatialWaro等均提供對(duì)R樹(shù)的支持。同時(shí)，在R樹(shù)的基礎(chǔ)上也提出了很多優(yōu)化算法，最著名的有R+樹(shù)、R*樹(shù)等。R樹(shù)是一個(gè)高度平衡樹(shù)，它可以看成是B樹(shù)在K個(gè)維度上的自然擴(kuò)展。它用空間對(duì)象的MBR(Minimum bounding rectangle)來(lái)近似表達(dá)空間對(duì)象，根據(jù)物體的MBR建立R樹(shù)，我們就可以直接對(duì)在空間中占據(jù)一定范圍的空間對(duì)象進(jìn)行存儲(chǔ)和索引?？臻g對(duì)象的MBR被包含于R樹(shù)的葉結(jié)點(diǎn)中。在R樹(shù)空間索引中，可以設(shè)計(jì)一些虛擬的矩形目標(biāo)，將一些空間位置相近的目標(biāo)，包含在這個(gè)矩形內(nèi)。這些虛擬的矩形作為空間索引，它將含有所包含的空間對(duì)象的指針。虛擬矩形還可以進(jìn)一步細(xì)分，即可

46、以再套虛擬矩形形成多級(jí)空間索引。在R樹(shù)的構(gòu)造中，我們要求虛擬矩形要盡可能少地重疊，并且要求一個(gè)空間對(duì)通常僅被一個(gè)虛擬矩形所包含。但是空間對(duì)象千姿百態(tài)，它們的MBR經(jīng)常重疊。 R+ 樹(shù)改進(jìn)了R樹(shù)的空間索引，為了平衡，它允許虛擬矩形相互重疊，并允許一個(gè)空間目標(biāo)被多個(gè)虛擬矩形所包含。R*樹(shù)都是完全動(dòng)態(tài)的，插入、刪除操作可以與查詢(xún)操作混合進(jìn)行，而且不需要進(jìn)行定期的全局重建。它允許不同子樹(shù)的最小外包矩形發(fā)生重疊，因此這種結(jié)構(gòu)在進(jìn)行精確匹配搜索的時(shí)候會(huì)產(chǎn)生多條搜索路徑。R*樹(shù)的性能都比其他R樹(shù)變種高。對(duì)于點(diǎn)數(shù)據(jù)的訪(fǎng)問(wèn)，它的性能提升更加明顯。R*樹(shù)主要是考慮降低面積、邊長(zhǎng)、路徑矩形的重疊，R*樹(shù)即使面對(duì)分布

47、非常不規(guī)則的數(shù)據(jù)時(shí)也能表現(xiàn)得十分穩(wěn)定。又由于強(qiáng)制插入算法的使用，避免了不必要的分裂，這樣一來(lái)，R*樹(shù)就得到了動(dòng)態(tài)的重構(gòu)，使得存儲(chǔ)效率得到了提升。但是R*的實(shí)現(xiàn)代價(jià)僅比R樹(shù)的實(shí)現(xiàn)代價(jià)稍高。4.1.2 KD樹(shù)系列kd樹(shù)是每個(gè)節(jié)點(diǎn)都為k維點(diǎn)的二叉樹(shù)。所有的非葉子節(jié)點(diǎn)都可以視為用一個(gè)超平面把空間分區(qū)成兩個(gè)半空間。節(jié)點(diǎn)左邊的子樹(shù)代表在超平面左邊的點(diǎn)，節(jié)點(diǎn)右邊的子樹(shù)代表在超平面右邊的點(diǎn)。選擇超平面的方法如下：每個(gè)節(jié)點(diǎn)都與k維中垂直于超平面的那一維有關(guān)。因此，如果選擇按照x軸來(lái)進(jìn)行劃分，所有x值小于指定值的節(jié)點(diǎn)都會(huì)出現(xiàn)在左子樹(shù)，所有x值大于指定值的節(jié)點(diǎn)都會(huì)出現(xiàn)在右子樹(shù)。這樣一來(lái)，超平面可以用這個(gè)x值來(lái)確定，

48、其法線(xiàn)就是x軸的單位向量。KD樹(shù)能夠非常被方便的用來(lái)解決K近鄰問(wèn)題，因此應(yīng)用也十分的廣泛。對(duì)KD樹(shù)也有相當(dāng)多的優(yōu)化方案，比如用B樹(shù)來(lái)對(duì)KD樹(shù)進(jìn)行擴(kuò)展，通過(guò)采納B樹(shù)面向塊的存儲(chǔ)方式，使得KD樹(shù)的文件讀寫(xiě)次數(shù)得以減少，進(jìn)而優(yōu)化其外部?jī)?nèi)存的訪(fǎng)問(wèn)，這就得到了KDB樹(shù)。如果考慮到對(duì)空間的極度優(yōu)化，還有BKD樹(shù)20，通過(guò)組合多個(gè)KD樹(shù)可以提供更高的空間利用率，更高性能的查詢(xún)和更新。BKD樹(shù)目前已經(jīng)成功過(guò)應(yīng)用在著名的搜索引擎Lucene以及著名的搜索框架ElasticSearch中了。它使得es處理數(shù)值型數(shù)據(jù)和高維數(shù)據(jù)性能提高了約30%，空間節(jié)約了約60%。4.2 對(duì)時(shí)間序列的存儲(chǔ)方法4.2.1 對(duì)點(diǎn)的倒排

49、索引倒排索引也常被稱(chēng)為反向索引、置入檔案或反向檔案，是一種索引方法，被用來(lái)存儲(chǔ)在全文搜索下某個(gè)單詞在一個(gè)文檔或者一組文檔中的存儲(chǔ)位置的映射。它是文檔檢索系統(tǒng)中最常用的數(shù)據(jù)結(jié)構(gòu)。對(duì)于時(shí)間序列的數(shù)據(jù)來(lái)說(shuō)，由于時(shí)間序列與文檔類(lèi)似，都是由多個(gè)元素組成，因此我們也可對(duì)時(shí)間序列數(shù)據(jù)采用倒排索引。將每一個(gè)時(shí)間序列看成是一份文檔，將每一個(gè)時(shí)間點(diǎn)看成是一個(gè)單詞，那么在存儲(chǔ)的時(shí)候只需要存儲(chǔ)每一個(gè)時(shí)間點(diǎn)，以及這個(gè)時(shí)間點(diǎn)對(duì)應(yīng)的時(shí)間序列的編號(hào)即可。也可以將時(shí)間點(diǎn)擴(kuò)展為一個(gè)小的時(shí)間序列段，這樣使得對(duì)時(shí)間序列的索引更有意義。對(duì)于采取了倒排索引的時(shí)間序列，當(dāng)我們需要進(jìn)行最近鄰查詢(xún)的時(shí)候，就可以利用倒排索引，計(jì)算待查詢(xún)軌跡中所

50、有軌跡段包含的軌跡，然后在這個(gè)子集合中再精細(xì)的查詢(xún)，達(dá)到“先過(guò)濾，后查詢(xún)”的目的。通過(guò)這種方法能夠比較高效的進(jìn)行軌跡查找，而不需要進(jìn)行全表掃描。4.2.2 對(duì)特征維度的索引除了對(duì)時(shí)間序列進(jìn)行倒排索引，我們還可以通過(guò)特征提取的方法，利用各種特征提取的函數(shù)，從時(shí)間序列中提取出重要的數(shù)據(jù)或者是問(wèn)題域關(guān)注的特征值，并運(yùn)用前面介紹的多維數(shù)據(jù)索引方法進(jìn)行索引。在這類(lèi)算法中，對(duì)時(shí)間序列進(jìn)行特征提取的算法十分重要。由于應(yīng)用場(chǎng)景不同，特征提取的算法也不同。對(duì)于較短的時(shí)間序列，甚至可以將每一個(gè)數(shù)據(jù)點(diǎn)看成是一個(gè)特征，但是一定要保證特征值的個(gè)數(shù)遠(yuǎn)小于數(shù)據(jù)量，否則就會(huì)造成維度災(zāi)難。通常我們會(huì)采用一些固定的特征提取方法，

51、比如類(lèi)似PAA的采樣方式，或者是一些基于極值或者特征值的計(jì)算。第五章 基于軌跡相似度的軌跡推薦方法為了更高效的解決相似軌跡的查詢(xún)問(wèn)題，本章提出了一個(gè)基于DTW相似度的相似軌跡搜索算法，在保證對(duì)相似軌跡的推薦不存在遺漏的前提下，極大優(yōu)化了搜索效率，準(zhǔn)確并高效的完成了對(duì)相似軌跡的推薦。45.1 相似度模型考慮到目前各種關(guān)于軌跡相似度的距離定義中效果最好的就是DTW算法，因此在我們的方法中，我們也采用DTW作為距離度量標(biāo)準(zhǔn)。但是，作為通用的距離比較標(biāo)準(zhǔn)，不同軌跡之間，常用的DTW距離的尺度是不一樣的。原本DTW距離被定義為兩條軌跡之間的軌跡點(diǎn)，兩兩順序組合，并計(jì)算這些軌跡點(diǎn)對(duì)的距離之和。這就導(dǎo)致了軌

52、跡點(diǎn)對(duì)數(shù)的不同會(huì)直接導(dǎo)致DTW距離尺度的不同。這就不方便我們?cè)诮y(tǒng)一的尺度下進(jìn)行比較。對(duì)DTW距離進(jìn)行歸一化是一個(gè)不錯(cuò)的方法，但是這樣又會(huì)使得計(jì)算變得復(fù)雜。所以在這個(gè)基礎(chǔ)上，我們提出了擴(kuò)展的DTW算法。在擴(kuò)展的DTW算法中，對(duì)于給定兩個(gè)軌跡S和Q，DTW距離定義如下：Dtw,=0DtwS,=Dtw,Q=DtwS,Q=DbaseFirst(S),First(Q)+minDtw(S,Rest(Q)Dtw(RestS,Q)Dtw(RestS,Rest(Q) (5.1)其中First(S)表示軌跡S的第一個(gè)元素，Rest(S)表示軌跡S的最后一個(gè)元素。Dbase表示一個(gè)用來(lái)組合各個(gè)對(duì)應(yīng)點(diǎn)的函數(shù)。當(dāng)Dba

53、se采用l1norm時(shí)，這個(gè)DTW距離就是我們傳統(tǒng)的DTW距離:Dtwl1,=0Dtwl1S,=Dtw,Q=Dtwl1S,Q=|FirstSFirst(Q)|+minDtwl1(S,Rest(Q)Dtwl1(RestS,Q)Dtwl1(RestS,Rest(Q) (5.2)當(dāng)Dbase采用lnorm時(shí)，這個(gè)DTW距離就變成了一個(gè)新的距離函數(shù)：Dtw_l,=0Dtw_lS,=Dtw,Q=Dtw_lS,Q=max|FirstSFirst(Q)|minDtw_l(S,Rest(Q)Dtw_l(RestS,Q)Dtw_l(RestS,Rest(Q) (5.3)相比Dtw_l1，Dtw_l本身就已經(jīng)是歸

54、一化的，而且利用Dtw_l，我們可以延伸出一個(gè)更加平凡，更加簡(jiǎn)單的下界函數(shù)Dtwllb用來(lái)進(jìn)行高效索引。在我們的方法中，我們將采用Dtwl來(lái)作為相似度衡量標(biāo)準(zhǔn)。5.2 索引策略雖然我們改進(jìn)了DTW距離度量算法，但是Dtw_l也并不能直接用來(lái)構(gòu)建索引，因?yàn)镈twl不滿(mǎn)足三角形不等式，也就不具備作為索引的基本條件。為了能夠?qū)崿F(xiàn)對(duì)Dtwl距離的快速索引，我們采用了Dtwl的一個(gè)下限函數(shù)Dtwllb來(lái)作為索引函數(shù)。對(duì)于從軌跡數(shù)據(jù)集中取出的軌跡S=,而言，我們可以從軌跡中抽取一個(gè)八元組的特征向量FeatureS=。其中，maxxi，maxyi，minxi，minxi，分別表示橫坐標(biāo)、縱坐標(biāo)的最大、最小值

55、。根據(jù)Feature(S)的定義，給定兩條軌跡S和Q，Dtwllb定義如下DtwllbS,Q=LFeatureS,FeatureQ (5.4)根據(jù)Dtwl的定義，Dtwl(S,Q)表示S和Q兩條軌跡中軌跡點(diǎn)一一對(duì)應(yīng)后使總體距離最小的匹配方案中的最大的距離，而在任意一種匹配方案中，一定有Sx1與Qx1匹配，Sy1與Qy1匹配，Sx|S|與Qx|S|匹配，Sy|S|與Qy|S|匹配。因此必然有：DtwlS,QL(,) (5.5)同時(shí)，在DtwlS,Q的對(duì)應(yīng)匹配點(diǎn)中，Smaxxi對(duì)應(yīng)的點(diǎn)必然不超過(guò)Qmaxxi，Smaxyi對(duì)應(yīng)的點(diǎn)必然不超過(guò)Qmaxyi，Sminxi對(duì)應(yīng)的點(diǎn)必然不低于Qminxi，Sminyi對(duì)應(yīng)的點(diǎn)必然不超過(guò)Qminyi。因此必然有:DtwlS,QL(,)DtwlS,QL,DtwllbS,Q (5.6)所以，DtwllbS,Q可以作為DtwlS,Q的下界函數(shù)。那么，對(duì)于任意的一個(gè)可容忍的誤差，必然有:DtwlS,QDtwllbS,Q (5.7)同時(shí)，由于DtwllbS,Q=L(FeatureS,FeatureQ)，而L是滿(mǎn)足三角形不等式的，那么對(duì)于任意的三個(gè)序列X,Y,Z，下面的三