[發明專利]基于歐式距離和相對方向的不確定移動對象軌跡分組方法

在審

• 申請號: 202011590233.3
• 申請日: 2020-12-29
• 公開（公告）號: CN112579923A
• 公開（公告）日: 2021-03-30
• 發明（設計）人: 李博涵;張夢茜;戴天倫;王高旭;秦小麟
• 申請（專利權）人: 南京航空航天大學
• 主分類號: G06F16/9537
• 分類號: G06F16/9537;G06K9/62
• 代理公司: 南京業騰知識產權代理事務所(特殊普通合伙) 32321
• 代理人: 繆友益

本發明公開一種基于歐式距離和相對方向的不確定移動對象軌跡分組方法，包括如下步驟：(1)通過移動對象軌跡相似度算法將歷史一段時間內具有相似運動軌跡的移動對象劃分為一個群組；(2)將同一個分組的移動對象放入索引結構中；(3)當移動對象的空間位置發生變化時，索引結構借助哈希表實現自底向上的查詢；(4)當移動對象發出位置更新請求時，更新記錄；(5)對索引結構的數據進行周期性更新。本發明通過實時定位移動對象并由其有序定位數據形成不確定移動對象軌跡，通過SMMS算法計算得到相似軌跡并進行以聚類中心為原點的聚類，聚類后獲得移動對象信息同時取為一組別，同組別移動對象位置更新數據同時進行。

技術領域

本發明屬于時空數據領域不確定移動對象研究方向，具體是涉及一種基于歐式距離和相對方向的不確定移動對象軌跡分組方法。

背景技術

軌跡相似度度量是軌跡數據挖掘與分析的重要問題，在交通管制、道路規劃、行程推薦等較多空間領域都有著重要的影響。在交通管理方面，通過移動對象軌跡相似度方法可以發現一些道路是易堵車路段，可以對此路道進行人為交通疏導或者以此優化該路段的路況；在道路規劃方面，可以通過用戶的日常軌跡推導出用戶的出行模式，發現其中的相似性，借此作為城市功能區域劃分的重要指標。在行程推薦方面，聚類分析軌跡相似的用戶可以更精準地挖掘用戶可能的偏好，規劃更合理的出行日程。

在過去的幾年中，移動對象的軌跡研究領域出現了許多針對軌跡的相似性度量方法，它們在考慮時空信息的情況下比較兩條軌跡之間的相似性。兩個軌跡之間的相似度是這兩個軌跡相似程度的度量指數，相異度則是兩個對象差異程度的度量指數，距離通常視作相異度的方面兩個對象相似度越高，相似度越高，相異度就越低，距離越小。現有的時空軌跡相似度度量算法主要有：基于歐氏距離的相似度算法。AGRAWALR等在1993年提出了基于歐式距離的軌跡間相似度的標識方法。該方法要求計算的兩條軌跡的采樣點是一一對應的。采用間隔相同、采樣點數即軌跡長度一致。軌跡間的距離由軌跡上對應各點間的距離通過求和或取最大或者最小值得到。之后的研究對于該算法的效率方面進行了改進，利用數字信號處理的相關知識，提出利用離散傅里葉變換、離散小波變換等方法提高運算效率。但這些方法與其基類方法一樣，都對軌跡的采樣點有嚴格的要求，因此該方法也存在這對噪聲敏感等缺點。基于時間動態規劃的軌跡相似度算法主要是解決上述算法中對采樣條件過于嚴格的問題。通過采用前面采樣點相同的數據去填補空缺的節點，實現求出最小距離，以此作為衡量軌跡相似度的度量。基于時間動態規劃的相似度算法解決了基于歐式距離的軌跡間相似度方法對采樣條件嚴格的問題，但是對噪聲敏感。

基于歐式距離和動態規劃的相似度算法都對軌跡的個別點差異性非常敏感，如果兩個軌跡的節點在大多數時間段具有相似的形態，僅僅在很短的時間具有一定的差異，那么基于歐式距離和動態規劃的相似度算法都無法準確度量這兩個時間序列的相似度。因此最長公共子序列方法應運而生。其目標是找出無需任何操作即相似的最長軌跡片段。最長公共子序列也是一種運用了動態規劃的算法。編輯距離原本是一種源于文本處理的概念，它指的是將一個文本序列通過添加、刪除、替換三種操作變成另外一個序列所需的最小操作數。CHEN L等在編輯距離的基礎上進行了改進，提出了ERP和EDR。

此外，弗雷歇距離即狗繩距離，即主人走路徑1，狗走路徑2，各自走完兩條路徑過程中所需要的最短狗繩長度。同樣提供了一種簡單直觀的度量相似性的方式，也能達到較好的效果。但是弗雷歇距離方法對噪聲依舊敏感。單向距離的基本思想在于觀察兩條軌跡所圍成圖形的面積，當面積較大時，表明兩個軌跡之間距離較遠，相似度就低；反之，若圍成的形狀面積為0，則說明兩條軌跡重合，相似度最高。多線位置距離方法：當某區域面積的周長占總長比重大時權重也自然就大，當面積均為0時，說明兩條軌跡重合沒有縫隙，距離為0；當面積加權和大時，則說明兩條軌跡之間縫隙較大，距離也就大。此外，權重由區域周長占總長比重決定，也一定程度對抗了噪音點的干擾。