[發明專利]基于公共分片子序列的軌跡離群點檢測方法

有效

• 申請號: 201711099171.4
• 申請日: 2017-11-09
• 公開（公告）號: CN107944475B
• 公開（公告）日: 2021-05-14
• 發明（設計）人: 俞慶英;羅永龍;陳傳明;陳付龍;汪小寒;胡桂銀
• 申請（專利權）人: 安徽師范大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 蕪湖安匯知識產權代理有限公司 34107
• 代理人: 馬榮

本發明公開了一種基于公共分片子序列的軌跡離群點檢測方法，根據軌跡的方向特征，構建軌跡方向碼序列，獲取軌跡的分段序列和分片序列；計算軌跡間的CSS距離，根據預設離群軌跡分片和軌跡離群點的度量方法，檢測出離群軌跡分片和軌跡離群點。本發明的優點在于：本發明設計了軌跡的方向碼序列、軌跡的分片特征序列以及軌跡間公共分片子序列的距離，實現了軌跡分片離群點檢測和離群軌跡的檢測。算法適用于具有時間屬性和空間位置屬性的時空軌跡數據集，理論分析與實驗結果均表明，本發明是能夠準確而有效的檢測出軌跡離群點。

技術領域

本發明涉及數據挖掘領域，具體地，涉及一種基于公共分片子序列的軌跡離群點檢測方法。

背景技術

隨著衛星、移動終端、各種定位技術(GPS、GSM、RFID等)和存儲技術的應用與發展，大量移動對象的軌跡數據被搜集和存儲，例如車輛運行軌跡、移動用戶活動軌跡、颶風軌跡、動物遷徙軌跡數據等。軌跡數據中包含豐富的時空語義信息，共享和發布這些數據可以使分析人員獲取有用信息，并應用于智能交通、用戶行為分析、城市和道路規劃、旅游推薦、天氣預測、動物習性研究等多個領域，對這些軌跡數據進行挖掘分析已經成為一個有意義的課題。其中，軌跡離群點檢測是最典型的軌跡數據分析手段之一。

軌跡離群點檢測屬于時空數據離群點檢測的范疇，廣泛應用于惡劣天氣預測和智能交通領域。軌跡離群點(也稱為離群軌跡)是指基于相似的評價機制，在一定的時間間隔內，空間位置偏離絕大多數軌跡的軌跡，是非常少見的模式，可能表明一個反常的事件，離群軌跡的檢測結果可以起到預測和警示作用。同時，離群位置點或離群軌跡的檢測和移除對于提高基于相似性聚類的軌跡隱私保護算法的效率很有意義。因此，軌跡離群點檢測是本發明關注的研究問題。

目前，軌跡離群點檢測已取得一些研究成果。從處理的基本單元看，可以分為軌跡分段后檢測和軌跡整體檢測兩大類方法。從側重的研究屬性看，可以分為以空間位置屬性為主要特征的軌跡離群點檢測和以時間屬性為主要特征的軌跡離群點檢測。其中，軌跡分段后檢測較軌跡整體檢測的準確率更高。然而，現有離群軌跡檢測方法存在很多不足，例如：以整條軌跡作為研究對象的方法，對于子軌跡異常的情形往往無法檢測，離群子軌跡的特征可能在整條軌跡中被均化。目前以子軌跡為研究對象的軌跡分段后檢測方法則主要強調空間位置特征的重要性，忽視了軌跡時間屬性的重要性；另一方面，孤立地考慮軌跡的分段，忽視了軌跡分段之間的連續性特征。現有方法，一般是按照相同采樣點的個數對軌跡進行劃分，無法反映軌跡的真實特征信息。所以，現有檢測算法的性能無法得到保證。

本發明基于公共分片子序列的模型構建，提出一種更為準確有效的軌跡離群點檢測方法。

發明內容

本發明的目的在于克服現有技術的不足，提供一種基于公共分片子序列的軌跡離群點檢測方法，既考慮到了軌跡的分片效果又突出了軌跡連續分片特征的重要性。具體來說，提出的該方法包含了兩個功能，第一個是針對時空軌跡數據集進行建模，獲取軌跡的分段和分片特征序列。另外，引入了一種新的基于公開分片子序列CSS的軌跡距離計算方法，用于檢測離群的軌跡分片和離群軌跡。

為了實現上述目的，本發明采用的技術方案為：一種軌跡離群點檢測方法，根據軌跡的方向特征，構建軌跡方向碼序列，獲取軌跡的分段序列和分片序列；

計算軌跡間的CSS距離，根據預設離群軌跡分片和軌跡離群點的度量方法，檢測出離群軌跡分片和軌跡離群點。

具體包括如下步驟，

步驟1：軌跡的形式化表示

對軌跡數據集進行形式化預處理，生成如下軌跡數據集：

T＝{Tid,(t₁,x₁,y₁),(t₂,x₂,y₂),…,(t_n,x_n,y_n)}