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

吳斌 張守震

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

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

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

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

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

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

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

二、多目標(biāo)動(dòng)態(tài)標(biāo)準(zhǔn)規(guī)劃位置匹配算法

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

（一）單維度點(diǎn)圖算法的改進(jìn)

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

（二）空間擴(kuò)展的高程模型建立

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

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

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

MDP-MM算法中，調(diào)用了FCOSP算法來(lái)計(jì)算從上一個(gè)GPS的備選路徑集合及W到當(dāng)前備選匹配點(diǎn)的備選路徑其中具有最優(yōu)路徑評(píng)價(jià)指標(biāo)值。在本文中，假設(shè)浮動(dòng)車在連續(xù)的兩個(gè)GPS之間行駛的是具有最短距離的路徑，這種假設(shè)是合理的，因?yàn)檫B續(xù)2個(gè)GPS點(diǎn)間的時(shí)間間隔是相對(duì)較短的，二者之間的距離不會(huì)過(guò)遠(yuǎn)，可選路徑相對(duì)較少，因此選擇最短路徑的可能性最高。基于這種假設(shè)，利用考慮了路網(wǎng)轉(zhuǎn)向限制條件的基于邊的Dijkstra算法來(lái)計(jì)算兩個(gè)備選匹配點(diǎn)之間的最短路徑。

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

四、總結(jié)

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

參考文獻(xiàn)：

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

[2] 吳星. 運(yùn)動(dòng)軌跡時(shí)空模式挖掘與可視化[D].東華理工大學(xué)，2018.

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

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