基于多維度數(shù)據(jù)建模及空間相似性分析研究

吳斌 張守震

摘 要：高維空間中，數(shù)據(jù)投影算法難以從高維空間獲取信息并將其關聯(lián)到形象直觀的低維空間。面對具有復雜性和動態(tài)性特征的高維空間數(shù)據(jù)挖掘和可視化建模時，理論依據(jù)和高效算法有待于更加深入廣泛地研究。本文分析研究了低維軌跡數(shù)據(jù)的可視化理論和方法，實現(xiàn)了軌跡相關的高維軌跡數(shù)據(jù)的信息挖掘算法和可視化模型。改進基于編輯距離和層次聚類的異常軌跡檢測方法，以相似性度量和歷史標記數(shù)據(jù)對軌跡進行段分割，將基于點堆疊的停留點位置和數(shù)量的計算方法進行重設計。以此為基礎，檢測了相似性軌跡的特性，評估了異常軌跡的行為模式，繪制了停留點的地理點圖，定義了語義軌跡的挖掘模型;以堆疊軌跡為基礎，建立了基于移動對象軌跡的回歸高程模型，實現(xiàn)了基于靜態(tài)可視化和動態(tài)可視化的多屬性關聯(lián)分析。

關鍵詞：多維度;數(shù)據(jù)建模;軌跡挖掘

一、深層語義軌跡數(shù)據(jù)模型

移動數(shù)據(jù)的時空和屬性聚集方法可以只作用于單個維度，如空間聚集（S）、時間聚集（T）、屬性聚集（A），也可作用于多個維度，如時空聚集（SxT）、時間屬性聚集（TxA）、空間數(shù)據(jù)聚集（SxA）和時空厲性聚集（SxTxA），將客種M性定義為“A+”。移動對象軌跡中S、T和A+成分之間的相互關系，即相對于空間和時間的多屬性行為。這些行為共同依賴于給定軌跡的特征，并表現(xiàn)出多種相關性：

1）行為搜索。觀察A+的異常值，檢測分析人員感興趣的特定行為發(fā)生時間或位置，并將它們在S和T中定位。例如某區(qū)域在某個時間段出現(xiàn)多個屬性值（方向、速度、加速度等）同時異常的情況，則對應區(qū)域可能發(fā)生了交通事故。?

2）行為比較。比較S內不同區(qū)域或T內不同間隔或軌跡集T的不同子集的A+的行為。例如，比較春季航線與冬季航線航船的航速行為、載重行為等。?

3）行為組合。觀察軌跡集的不同子集在S內的相同區(qū)域或T內相同間隔同時發(fā)生不A+的行為。

二、多目標動態(tài)標準規(guī)劃位置匹配算法

為了匹配大規(guī)模的浮動車軌跡數(shù)據(jù)，本文提出的多標準動態(tài)規(guī)劃地圖匹配算法的處理框架如圖所示，主要分為5個步驟，分別為路網(wǎng)初始化、車輛軌跡跟蹤、備選匹配點生成、備選路徑生成以及最優(yōu)匹配路徑選取。為了提高地圖匹配過程中最短路徑分析算法的計算效率，本文從2個方面改進了傳統(tǒng)的最短路徑分析算法。首先，利用一個全局路徑分析標識避免了標記初始化步驟;另外，使用多起點到一個終點的路徑分析過程計算備選匹配路徑，避免了重復調用傳統(tǒng)的路徑分析算法。

（一）單維度點圖算法的改進

原始的單維度點圖算法有三個限制：（1）該算法通過從最小觀測值;移動到最大觀測值;（從左到右）生成點圖。以類似的方式，也可以通過相反順序（從右到左）生成點圖。這些不同的移動方向在同一批數(shù)據(jù)上可能產生不同的點圖;（2）對稱分布的數(shù)據(jù)可能會導致不對稱的點圖;（3）由于該算法在單一數(shù)值軸上本質上是一維的，因此難以擴展到多維數(shù)據(jù)。但是，通過一種無向算法可以克服原始點圖算法的缺點：避免從最小的觀測值（從左到右）或從最大的觀測值（從右到左）開始，而是從一個點半徑鄰域中具有最大領域的數(shù)據(jù)點開始。以下是該算法的偽代碼，可以有效降低點的位置偏差，并將點圖擴展到更高維度。?

（二）空間擴展的高程模型建立

過去的堆疊可視化模型將一幅2D地圖放置在一個虛擬的3D空間，忽略了高程維對軌跡數(shù)據(jù)帶來的影響。然而，在實際用例中，表示三維時空域中的移動對象形成的路徑為時空路徑，時空路徑的空間位置由地面位置和高程共同界定。因此，對軌跡空間的需求分析應在傳達時間信息的前提下保持三維地理空間位置的可視化，這對處理三維軌跡集數(shù)據(jù)的時空可視化技術提出了更高的要求。此外，如果考慮在堆疊軌跡條帶的上方體現(xiàn)高程信息，會出現(xiàn)軌跡條帶在Z軸上的波動幅度變大，從而導致直觀性變差，無法實現(xiàn)軌跡堆疊。

在生成軌跡的高程視圖中，由于使用3D場景的透視投影和立體渲染，軌跡點的高度信息很難感知，尤其是用戶在觀察可視化視圖時使用了非立體顯示工具?？紤]這個因素，在渲染軌跡高程帶時基于高程的分帶設色，以漸變過渡保證地勢起伏的連續(xù)性，可以展示出良好的三維可視化效果。?

三、最短路徑分析優(yōu)化過程

MDP-MM算法中，調用了FCOSP算法來計算從上一個GPS的備選路徑集合及W到當前備選匹配點的備選路徑其中具有最優(yōu)路徑評價指標值。在本文中，假設浮動車在連續(xù)的兩個GPS之間行駛的是具有最短距離的路徑，這種假設是合理的，因為連續(xù)2個GPS點間的時間間隔是相對較短的，二者之間的距離不會過遠，可選路徑相對較少，因此選擇最短路徑的可能性最高?；谶@種假設，利用考慮了路網(wǎng)轉向限制條件的基于邊的Dijkstra算法來計算兩個備選匹配點之間的最短路徑。

FCGSP過程中路徑分析的起點和終點不僅可以是路網(wǎng)節(jié)點，也可以在路網(wǎng)邊上。在傳統(tǒng)Dijkstra算法中，起點和終點只能位于節(jié)點上，然而GPS點的備選匹配點可能位于路網(wǎng)邊的任意位置。FCGSP過程通過添加虛擬的節(jié)點和邊到路網(wǎng)中來解決該問題，MDP-MM算法的計算性能如表1所示，在不考慮數(shù)據(jù)的讀寫時間時，MDP-MM算法的運行時間為30.7秒，處理速度達5590點/秒，具有很高的計算性能。即使考慮軌跡數(shù)據(jù)的讀寫時間，MDP-MM算法在僅使用單CPU的情況下可以在12.6分鐘內處理完15分鐘的浮動車軌跡數(shù)據(jù)，表明MDP-MM算法可以實時匹配大規(guī)模的浮動車軌跡數(shù)據(jù)。?

四、總結

圍繞低維數(shù)據(jù)在地理空間中構建的軌跡數(shù)據(jù)模型展開討論，研究內容主要是：改進了軌跡聚類和異常檢測算法并實現(xiàn)了軌跡段的有效檢測和行為模式推理、基于MADS的時空數(shù)據(jù)建模實現(xiàn)了語義軌跡的時空和屬性對象豐富、建立了停留點的點堆棧模型以繪制停留點的地理點圖、建立了回歸高程模型以實現(xiàn)堆疊軌跡的三維特性、設計了屬性的動態(tài)提取方式，以多個視角挖掘了軌跡數(shù)據(jù)的行為知識和運動模式等。?

參考文獻：

[1] 齊佳倩. 基于視頻監(jiān)控數(shù)據(jù)的人群行為分析和異常軌跡檢測[D].北京交通大學，2018.

[2] 吳星. 運動軌跡時空模式挖掘與可視化[D].東華理工大學，2018.

[3] 趙如意. 面向GIS的多維時空可視化Web組件庫的開發(fā)與應用[D].華東師范大學，2018.

[4] 宋英華. 基于圖像處理與遺傳算法的視頻內容3D可視化瀏覽系統(tǒng)[D].天津大學，2018.