[發明專利]一種基于后綴樹誤差有界的軌跡預測方法

在審

• 申請號: 202011309993.2
• 申請日: 2020-11-20
• 公開（公告）號: CN112380400A
• 公開（公告）日: 2021-02-19
• 發明（設計）人: 龐志飛;魯鵬;姚暢;伍賽;陳剛
• 申請（專利權）人: 浙江大學計算機創新技術研究院
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06F16/906;G06F16/909
• 代理公司: 杭州求是專利事務所有限公司 33200
• 代理人: 林超

本發明公開了一種基于后綴樹誤差有界的軌跡預測方法。歷史軌跡輸入到深度學習模型中進行處理獲得預測軌跡，將歷史軌跡存儲到后綴樹中，當有新的預測請求時，在后綴樹中找到相似的軌跡作為預測結果，由后綴樹直接返回預測結果。本發明能在后綴樹中找到相似軌跡，由后綴樹直接返回預測結果，無需進入神經網絡進行預測，極大提高了軌跡預測的效率。

技術領域

本發明涉及數據庫領域中的時空索引方法，具體涉及到一種基于后綴樹誤差有界的軌跡預測方法。

背景技術

隨著近年來移動互聯網的迅速崛起，智能手機、車載GPS系統等持續不斷地記錄著用戶的位置信息，眾多服務商們利用這些軌跡數據來更好的為用戶們提供商品以及服務，因此極大促進了軌跡大數據的發展。軌跡的最普遍形式是一個由位置坐標和相應時間組成的序列，其中坐標通常為二維坐標，例如經度和緯度。

在軌跡大數據的應用中，一個熱門問題就是對軌跡數據的預測。隨著人工智能技術的興起，越來越多的研究工作使用神經網路對移動物體的軌跡進行預測，即將該對象的歷史軌跡輸入模型，模型輸出該對象在未來一段時間內的預測軌跡。雖然利用神經網絡對軌跡進行預測取得了比傳統線性模型更好的準確率，但是一個最主要的問題就是其預測性能相較于線性模型是非常低下的。

發明內容

為了解決背景技術中存在的問題，本發明的目的在于針對現有技術的不足，提供一種基于后綴樹誤差有界的軌跡預測方法，將神經網絡的預測結果以鍵值對的方式存儲到后綴樹中。

本發明解決其技術問題采用的技術方案如下：

歷史軌跡輸入到深度學習模型中進行預測處理獲得預測軌跡，將歷史軌跡存儲到后綴樹中，當有新的預測請求時，在后綴樹中找到相似的軌跡作為預測結果，由后綴樹直接返回預測結果，無需進入復雜的深度模型進行預測，極大的提高了軌跡預測的效率。

所述的方法步驟如下：

軌跡是由移動對象所產生的位置坐標沿時間順序所構成的序列，信息由平面二維坐標(x，y)和對應的時間組成，軌跡分為歷史軌跡和預測軌跡。

具體實施的位置坐標例如為緯度坐標。

軌跡包含事先已知的歷史軌跡以及由深度學習模型輸出的預測軌跡兩部分。

所述的深度學習模型采用神經網絡模型。

1)確定軌跡集合的位置坐標的取值范圍并轉為網格坐標表示

1.1)由所有歷史軌跡和預測軌跡組成軌跡集合，針對軌跡集合的所有軌跡的位置坐標中選取橫坐標和縱坐標的最小值x_min、y_min和最大值x_max、y_max，由以上坐標組成四角頂點坐標分別為(x_min，y_min)、(x_min，y_max)、(x_max，y_max)、(x_min，y_max)的矩形，作為路網區域；

1.2)根據粒度將路網區域劃分為相等的格子，各個格子按照自身在路網區域中的行列順序進行橫縱坐標的坐標編號；

1.3)將歷史軌跡轉換成路網區域的格子坐標：歷史軌跡上的各個位置坐標替換為所在格子的格子坐標編號，從而將歷史軌跡轉換為路網歷史軌跡序列；

2)使用局部敏感性哈希函數將路網歷史軌跡序列進行聚類：

使用局部敏感性哈希函數聚類時，使得每一個類中任意兩條估計的距離不大于d：