基于膨脹運(yùn)算的移動(dòng)對(duì)象興趣點(diǎn)檢測(cè)方法

王清， 丁赤飚， 付琨， 任文娟

(1.中國(guó)科學(xué)院 電子學(xué)研究所， 北京 100190； 2.中國(guó)科學(xué)院 空間信息處理與應(yīng)用系統(tǒng)技術(shù)重點(diǎn)實(shí)驗(yàn)室， 北京 100190; 3.中國(guó)科學(xué)院大學(xué) 電子電氣與通信工程學(xué)院， 北京 100049)

基于膨脹運(yùn)算的移動(dòng)對(duì)象興趣點(diǎn)檢測(cè)方法

王清1,2,3， 丁赤飚1,3， 付琨1,2,3， 任文娟1,2,3

(1.中國(guó)科學(xué)院 電子學(xué)研究所， 北京 100190； 2.中國(guó)科學(xué)院 空間信息處理與應(yīng)用系統(tǒng)技術(shù)重點(diǎn)實(shí)驗(yàn)室， 北京 100190; 3.中國(guó)科學(xué)院大學(xué) 電子電氣與通信工程學(xué)院， 北京 100049)

針對(duì)傳統(tǒng)興趣點(diǎn)檢測(cè)算法在準(zhǔn)確性和效率方面的不足，提出基于膨脹運(yùn)算的移動(dòng)對(duì)象興趣點(diǎn)檢測(cè)方法(DMDO)。通過(guò)矩陣二值化操作濾除停留點(diǎn)噪聲，提高預(yù)測(cè)準(zhǔn)確率，并用膨脹運(yùn)算替代傳統(tǒng)方法中的聚類(lèi)算法提高算法效率。將DMDO在開(kāi)放空間數(shù)據(jù)集AMSA和IMIS3Days上進(jìn)行仿真實(shí)驗(yàn)，結(jié)果表明：DMDO相比基于密度的空間聚類(lèi)算法，在數(shù)據(jù)集AMSA上準(zhǔn)確率平均提高17.94%，算法效率提高6.63倍；在數(shù)據(jù)集IMIS3Days上準(zhǔn)確率平均提高19.98%，算法效率提高9.13倍；相比以聚類(lèi)點(diǎn)排序結(jié)果確定聚類(lèi)結(jié)構(gòu)算法，DMDO在數(shù)據(jù)集AMSA上準(zhǔn)確率平均提高20.04%，算法效率提高14.61倍；在數(shù)據(jù)集IMIS3Days上準(zhǔn)確率平均提高16.60%，算法效率提高42.19倍；DMDO相比傳統(tǒng)方法均表現(xiàn)出較高的預(yù)測(cè)準(zhǔn)確性、較低的時(shí)間開(kāi)銷(xiāo)，適用于解決大數(shù)據(jù)背景下的移動(dòng)對(duì)象興趣點(diǎn)檢測(cè)問(wèn)題。

信息處理技術(shù)； 軌跡數(shù)據(jù)挖掘； 興趣點(diǎn)檢測(cè)； 膨脹運(yùn)算； 開(kāi)放空間

0 引言

隨著通信技術(shù)、全球定位導(dǎo)航系統(tǒng)的迅猛發(fā)展，可以通過(guò)多種途徑獲得不同類(lèi)型的軌跡數(shù)據(jù)。例如通過(guò)智能手機(jī)、車(chē)載導(dǎo)航系統(tǒng)獲取行人、汽車(chē)等城市軌跡數(shù)據(jù)[1-3]，通過(guò)衛(wèi)星、雷達(dá)、船舶自動(dòng)識(shí)別系統(tǒng)(AIS)等定位技術(shù)獲得船舶、飛機(jī)的軌跡數(shù)據(jù)[4]。軌跡表達(dá)了移動(dòng)對(duì)象一段時(shí)間內(nèi)的位置信息，蘊(yùn)含著移動(dòng)對(duì)象的行為習(xí)慣。挖掘海量軌跡數(shù)據(jù)有助于深入了解移動(dòng)對(duì)象行為習(xí)慣、感知社會(huì)需求[5]。為解決軌跡數(shù)據(jù)挖掘問(wèn)題，實(shí)現(xiàn)位置大數(shù)據(jù)的應(yīng)用價(jià)值，基于位置的服務(wù)(LBS)應(yīng)運(yùn)而生。研究區(qū)域中的興趣點(diǎn)是指具有特殊含義的停留區(qū)域，例如城市中的教學(xué)樓、宿舍、商城，海域沿岸的港口、補(bǔ)給站等。一部分LBS依賴(lài)興趣點(diǎn)的挖掘與檢測(cè)，例如，根據(jù)用戶(hù)常訪(fǎng)興趣點(diǎn)計(jì)算用戶(hù)間相似度，從而進(jìn)行用戶(hù)社交網(wǎng)絡(luò)的挖掘與研究；預(yù)測(cè)用戶(hù)即將前往的興趣點(diǎn)，從而推送相關(guān)廣告信息等[6-8]。本文主要圍繞如何快速、準(zhǔn)確地挖掘興趣點(diǎn)展開(kāi)研究。

興趣點(diǎn)檢測(cè)技術(shù)主要分為兩類(lèi)，即靜態(tài)提取和動(dòng)態(tài)挖掘方法[9]。靜態(tài)提取方法需要人工標(biāo)注類(lèi)似教學(xué)樓、商城、港口、補(bǔ)給站等有特殊含義的停留位置[10-11]。動(dòng)態(tài)挖掘方法不需要研究區(qū)域的先驗(yàn)知識(shí)作為輸入條件，僅根據(jù)原始軌跡數(shù)據(jù)的時(shí)空特征發(fā)現(xiàn)潛在興趣點(diǎn)，這些時(shí)空特征包括經(jīng)緯度、速度、加速度和軌跡前進(jìn)方向等。

動(dòng)態(tài)挖掘算法一直是國(guó)內(nèi)外學(xué)者的研究重點(diǎn)。主要思路是首先檢測(cè)大量歷史軌跡的停留點(diǎn)，然后對(duì)停留點(diǎn)進(jìn)行聚類(lèi)，每類(lèi)對(duì)應(yīng)一個(gè)興趣點(diǎn)。興趣點(diǎn)檢測(cè)主要分為兩部分內(nèi)容：停留點(diǎn)檢測(cè)和停留點(diǎn)聚類(lèi)。

在停留點(diǎn)檢測(cè)方面，Agamennoni等[11]根據(jù)靜態(tài)速度閾值檢測(cè)停留點(diǎn)，小于速度閾值的軌跡點(diǎn)被認(rèn)為是停留點(diǎn)。鄭宇等[12]提出根據(jù)時(shí)間閾值和距離閾值從歷史軌跡中提取停留點(diǎn)。羅庭等[13]根據(jù)移動(dòng)對(duì)象軌跡曲折程度判斷其是否低速行駛，移動(dòng)對(duì)象軌跡短時(shí)間內(nèi)曲折程度較高時(shí)，認(rèn)為其行駛速度較低，處于“停留”狀態(tài)。

在停留點(diǎn)聚類(lèi)方面，由于不同移動(dòng)對(duì)象到達(dá)同一興趣點(diǎn)可能產(chǎn)生不同停留點(diǎn)，這些停留點(diǎn)距離很近，可利用聚類(lèi)方法將停留點(diǎn)聚集為各個(gè)點(diǎn)簇，每個(gè)興趣點(diǎn)用點(diǎn)簇表示。大量研究工作圍繞采用不同的聚類(lèi)方法及其改進(jìn)方法展開(kāi)。Ashbrook等[14]采用K均值(K-Means)聚類(lèi)算法對(duì)歷史軌跡數(shù)據(jù)中提取的停留點(diǎn)進(jìn)行聚類(lèi)。K-Means算法是一種劃分聚類(lèi)算法，需要用戶(hù)預(yù)先設(shè)定興趣點(diǎn)的數(shù)目K，但是從雜亂無(wú)章的軌跡中預(yù)先準(zhǔn)確指定興趣點(diǎn)個(gè)數(shù)并非易事；并且，K-Means算法抗噪能力較差，易受離群點(diǎn)影響。由于K-Means算法存在參數(shù)設(shè)定、抗噪性差的問(wèn)題，Palma 等[15]采用一種抗噪聲的基于密度的空間聚類(lèi)(DBSCAN)算法對(duì)停留點(diǎn)進(jìn)行聚類(lèi)。DBSCAN算法可以避免預(yù)先設(shè)定興趣點(diǎn)數(shù)目并剔除噪聲點(diǎn)，但是需要設(shè)定數(shù)量閾值和距離閾值，并且算法時(shí)間復(fù)雜度隨著數(shù)據(jù)量的增加而大幅增加，不適宜大數(shù)據(jù)量環(huán)境下的興趣點(diǎn)檢測(cè)問(wèn)題。Zimmermann等[16]采用一種以聚類(lèi)點(diǎn)排序結(jié)果確定聚類(lèi)結(jié)構(gòu)(OPTICS)的算法挖掘興趣點(diǎn)。OPTICS算法屬于基于密度的聚類(lèi)算法，相比DBSCAN算法的改進(jìn)之處在于，無(wú)需預(yù)先設(shè)定閾值，能獲得任何閾值的DBSCAN聚類(lèi)結(jié)果。

目前國(guó)內(nèi)外挖掘興趣點(diǎn)所采用的主流方法可總結(jié)為首先檢測(cè)停留點(diǎn)，然后采用DBSCAN算法等基于密度的聚類(lèi)算法對(duì)停留點(diǎn)進(jìn)行聚類(lèi)，以停留點(diǎn)簇表示各興趣點(diǎn)。主流算法存在問(wèn)題主要為興趣點(diǎn)檢測(cè)準(zhǔn)確率較低、算法時(shí)間復(fù)雜度較高：首先，算法易將移動(dòng)對(duì)象偶然的停留誤判為停留點(diǎn)，在停留點(diǎn)檢測(cè)中存在大量誤判現(xiàn)象，影響了聚類(lèi)結(jié)果，從而降低興趣點(diǎn)檢測(cè)的準(zhǔn)確性；其次，以DBSCAN算法為代表的基于密度的聚類(lèi)算法時(shí)間復(fù)雜度較高，數(shù)據(jù)規(guī)模較大時(shí)耗費(fèi)時(shí)間長(zhǎng)，不適用于大數(shù)據(jù)背景下的聚類(lèi)問(wèn)題。

針對(duì)傳統(tǒng)方法的不足，本文提出了基于膨脹運(yùn)算的移動(dòng)對(duì)象興趣點(diǎn)檢測(cè)算法(DMDO)，旨在通過(guò)矩陣二值化操作濾除誤判的停留點(diǎn)噪聲，并用膨脹運(yùn)算替代聚類(lèi)算法提高算法效率。

1 DMDO流程

在介紹具體算法之前，首先描述方法涉及的基本概念。

定義1停留點(diǎn)。移動(dòng)對(duì)象的速度小于速度閾值speedThreshold時(shí)所在的具體經(jīng)緯度。若對(duì)于軌跡點(diǎn)p，滿(mǎn)足vp

定義2網(wǎng)格。將研究區(qū)域等距離劃分所形成的二維規(guī)則區(qū)域。

定義3停留網(wǎng)格。包含停留點(diǎn)的數(shù)目大于一定閾值的網(wǎng)格。

定義4興趣點(diǎn)。具有特殊含義的區(qū)域，例如教學(xué)樓、商城、港口、補(bǔ)給站等。本文根據(jù)停留點(diǎn)及停留網(wǎng)格挖掘興趣點(diǎn)。

算法流程如圖1所示。

圖1 DMDO流程圖Fig.1 Algorithm flow of DMDO

將研究區(qū)域離散化，均等劃分為等距網(wǎng)格。

計(jì)算合理的速度閾值，用于歷史軌跡中的檢測(cè)停留點(diǎn)。

遍歷歷史軌跡集合中的軌跡點(diǎn)，計(jì)算其速度值，并與速度閾值speedThreshold進(jìn)行比較，若軌跡點(diǎn)速度值小于speedThreshold，則將其判定為停留點(diǎn)，映射至研究區(qū)域網(wǎng)格中，并將相應(yīng)網(wǎng)格的停留點(diǎn)計(jì)數(shù)增一。完成遍歷后，形成停留點(diǎn)計(jì)數(shù)矩陣Matrix.

根據(jù)閾值θ二值化停留點(diǎn)計(jì)數(shù)矩陣Matrix，獲得矩陣Matrix′. 二值化保留停留點(diǎn)數(shù)目較多的停留網(wǎng)格，濾除移動(dòng)對(duì)象偶然停留所產(chǎn)生的誤判噪聲。

對(duì)矩陣Matrix′進(jìn)行膨脹運(yùn)算，連通空間位置較近的停留網(wǎng)格，形成各個(gè)連通區(qū)域。將覆蓋網(wǎng)格數(shù)量大于w×w(w表示膨脹運(yùn)算模板寬度)的連通區(qū)域作為興趣點(diǎn)預(yù)測(cè)結(jié)果，將連通區(qū)域中包含停留點(diǎn)數(shù)目最多的網(wǎng)格設(shè)定為興趣點(diǎn)的中心。輸出興趣點(diǎn)預(yù)測(cè)結(jié)果，至此，DMDO流程結(jié)束。

DMDO用膨脹運(yùn)算替代DBSCAN聚類(lèi)，一方面膨脹運(yùn)算能夠替代DBSCAN聚類(lèi)實(shí)現(xiàn)連通、聚集的目的，另一方面，膨脹運(yùn)算降低時(shí)間開(kāi)銷(xiāo)。假設(shè)停留點(diǎn)數(shù)目為n，停留網(wǎng)格數(shù)目為m(m?n)，DBSCAN聚類(lèi)的時(shí)間復(fù)雜度為O(n2)，膨脹運(yùn)算的時(shí)間復(fù)雜度為O(m)，算法效率大幅提高。

計(jì)算合理速度閾值的算法流程如圖2所示。遍歷歷史軌跡集合中的軌跡點(diǎn)，根據(jù)當(dāng)前點(diǎn)和相鄰點(diǎn)經(jīng)緯度計(jì)算其速度，然后采用K-Means算法將速度值聚為“高速”、“低速”兩類(lèi)，并取兩類(lèi)臨界值作為速度閾值speedThreshold.

圖2 速度閾值計(jì)算流程圖Fig.2 Calculation flow of speed threshold

2 DMDO實(shí)驗(yàn)結(jié)果與分析

2.1 實(shí)驗(yàn)環(huán)境及數(shù)據(jù)集

實(shí)驗(yàn)的軟硬件條件如下：CPU為酷睿i3(2核，2.50 GHz)，內(nèi)存4.00 GB；操作系統(tǒng)為32位Windows10，仿真軟件為PyCharm 5.0.1.

為驗(yàn)證DMDO挖掘興趣點(diǎn)的準(zhǔn)確性及算法效率，本文將采用兩組開(kāi)放空間數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。兩組數(shù)據(jù)集均為船舶軌跡數(shù)據(jù)，特征如表1所示。

數(shù)據(jù)集1 AMSA是由澳洲海事安全局提供的2015年8月至2015年11月的澳大利亞附近海域民用船舶軌跡數(shù)據(jù)，包含3 327條軌跡，458 716個(gè)軌跡點(diǎn)，平均采樣間隔為34.25 min. 數(shù)據(jù)集2 IMIS3Days是由IMIS Hellas S.A.公司提供的愛(ài)琴海海域民用船舶軌跡數(shù)據(jù)，包含933條軌跡，3 095 254個(gè)軌跡點(diǎn)，采樣間隔為10 s.

表1 實(shí)驗(yàn)數(shù)據(jù)集特征

本文通過(guò)World Port Source網(wǎng)站獲取兩組數(shù)據(jù)集所在區(qū)域的真實(shí)興趣點(diǎn)作為評(píng)估標(biāo)準(zhǔn)，用于評(píng)估算法挖掘興趣點(diǎn)的準(zhǔn)確性。兩組數(shù)據(jù)集真實(shí)興趣點(diǎn)的提取結(jié)果如表2所示。

表2 真實(shí)興趣點(diǎn)提取結(jié)果

2.2 實(shí)驗(yàn)結(jié)果

本文從興趣點(diǎn)檢測(cè)的準(zhǔn)確性和效率兩個(gè)方面對(duì)DMDO與兩種傳統(tǒng)算法DBSCAN及OPTICS進(jìn)行對(duì)比，分別采用F1值、算法運(yùn)行時(shí)間T量化算法準(zhǔn)確性和效率。傳統(tǒng)方法DBSCAN的思路是首先通過(guò)速度閾值檢測(cè)歷史軌跡中的停留點(diǎn)，然后采用DBSCAN聚類(lèi)算法對(duì)停留點(diǎn)進(jìn)行聚類(lèi)；OPTICS算法的思路是首先檢測(cè)停留點(diǎn)，然后采用OPTICS算法根據(jù)停留點(diǎn)之間的距離對(duì)其進(jìn)行排序，再采用自動(dòng)聚類(lèi)方法根據(jù)排序結(jié)果對(duì)停留點(diǎn)進(jìn)行聚類(lèi)。

2.2.1 評(píng)估指標(biāo)

本文用F1值評(píng)估興趣點(diǎn)檢測(cè)的準(zhǔn)確性，其計(jì)算方法為

(1)

式中：P為準(zhǔn)確率，表征興趣點(diǎn)檢測(cè)的查準(zhǔn)率，即預(yù)測(cè)出的真實(shí)興趣點(diǎn)占算法預(yù)測(cè)結(jié)果總量的比率；R為召回率，表征興趣點(diǎn)檢測(cè)的查全率，即預(yù)測(cè)出的真實(shí)興趣點(diǎn)占真實(shí)興趣點(diǎn)總量的比率。若集合TD={TD1,TD2,…,TDn}表示研究區(qū)域中提前標(biāo)注的真實(shí)興趣點(diǎn)，集合PD={PD1,PD2,…}表示算法的興趣點(diǎn)預(yù)測(cè)結(jié)果，則P和R的具體計(jì)算分別為

(2)

(3)

式中：函數(shù)H(PD,TDi)表示算法預(yù)測(cè)結(jié)果是否命中真實(shí)興趣點(diǎn)TDi. 若在預(yù)測(cè)結(jié)果集合PD中存在一個(gè)預(yù)測(cè)結(jié)果PDj，覆蓋真實(shí)興趣點(diǎn)TDi，則H(PD,TDi)=1，否則為0，即

(4)

2.2.2 實(shí)驗(yàn)結(jié)果及分析

DMDO涉及的兩個(gè)重要參數(shù)為二值化閾值θ和膨脹運(yùn)算模板寬度w. 閾值θ反映過(guò)濾停留點(diǎn)噪聲的力度，值越大表明過(guò)濾的力度越強(qiáng)；模板寬度w反映相鄰兩個(gè)停留點(diǎn)連通的難易程度，值越大表明越易連通。傳統(tǒng)DBSCAN算法中包含兩個(gè)參數(shù)eps和minPts；OPTICS算法中包含一個(gè)參數(shù)minPts. 其中，minPts與閾值θ具有類(lèi)似含義，eps與模板寬度w具有類(lèi)似含義。d表示網(wǎng)格劃分寬度，轉(zhuǎn)換關(guān)系可近似表示為

(5)

minPts=2θ.

(6)

在檢測(cè)出相同停留點(diǎn)的前提下，比較DMDO與兩傳統(tǒng)算法DBSCAN及OPTICS對(duì)于兩個(gè)數(shù)據(jù)集AMSA及IMIS3Days在不同參數(shù)組合(θ，w)下的準(zhǔn)確性F1值和運(yùn)行效率T. 實(shí)驗(yàn)結(jié)果如圖3所示，圖3(a)表示采取不同參數(shù)組合時(shí)，3種算法在數(shù)據(jù)集AMSA上的F1值，圖3(b)表示3種算法在數(shù)據(jù)集AMSA上的運(yùn)行時(shí)間T，圖3(c)和圖3(d)表示3種算法在數(shù)據(jù)集IMIS3Days上的F1值及運(yùn)行時(shí)間T.

對(duì)于數(shù)據(jù)集AMSA，設(shè)置二值化閾值θ取值范圍為1～29，膨脹運(yùn)算模板寬度w取值為1、3、5. 分析圖3(a)，當(dāng)w為1、3、5時(shí)，DMDOF1值的變動(dòng)范圍分別為[0.37, 0.45]、[0.58, 0.74]、[0.78, 0.83]，傳統(tǒng)算法DBSCAN變動(dòng)范圍為[0.04, 0.15]、[0.42, 0.57]、[0.59, 0.77]，傳統(tǒng)算法OPTICS變動(dòng)范圍為[0.34, 0.51]。當(dāng)參數(shù)一致時(shí)，DMDO的F1值均顯著優(yōu)于DBSCAN算法。原因是兩種算法預(yù)測(cè)準(zhǔn)確的興趣點(diǎn)數(shù)目相近，而DBSCAN算法預(yù)測(cè)的興趣點(diǎn)總數(shù)遠(yuǎn)大于DMDO，因此DMDO的準(zhǔn)確率遠(yuǎn)高于DBSCAN算法，DMDO的F1值優(yōu)勢(shì)顯著。當(dāng)w>1時(shí)，DMDO的F1值顯著優(yōu)于傳統(tǒng)算法OPTICS. 原因是OPTICS算法未對(duì)停留點(diǎn)連通的難易程度設(shè)置明確的閾值，僅根據(jù)停留點(diǎn)之間的距離自動(dòng)聚類(lèi)，導(dǎo)致挖掘結(jié)果包含較多的噪聲點(diǎn)，預(yù)測(cè)的興趣點(diǎn)數(shù)量過(guò)多，致使OPTICS算法的準(zhǔn)確性下降。DMDO準(zhǔn)確率的顯著優(yōu)勢(shì)表明將停留點(diǎn)噪聲誤判為興趣點(diǎn)的錯(cuò)誤率較低，從而說(shuō)明本文通過(guò)網(wǎng)格二值化過(guò)濾停留點(diǎn)噪聲的處理方法更為有效，剔除噪聲的力度更強(qiáng)。

分析圖3(b)，當(dāng)w為1、3、5時(shí)，DMDO運(yùn)行時(shí)間基本分布在1 s以?xún)?nèi)，DBSCAN算法運(yùn)行時(shí)間均大于2 s，效率平均提高7.63倍，而OPTICS算法由于涉及停留點(diǎn)排序及停留點(diǎn)聚類(lèi)，運(yùn)行時(shí)間基本分布于10 s以上。表明DMDO效率大幅提高。

對(duì)于數(shù)據(jù)集IMIS3Days，能夠獲得相似的結(jié)論。設(shè)置二值化閾值θ取值范圍為50～1 000，膨脹運(yùn)算模板寬度w取值為1、3、5. 如圖3(c)所示，DMDO的F1值優(yōu)勢(shì)顯著，F(xiàn)1均值為0.67，DBSCAN算法的F1均值為0.47，OPTICS算法的F1均值為0.50，準(zhǔn)確性大幅提高；如圖3(d)所示，DMDO的運(yùn)行時(shí)間平均為0.26 s，DBSCAN算法的運(yùn)行時(shí)間平均為2.57 s，算法效率平均提高9.13倍，OPTICS算法的運(yùn)行時(shí)間平均為10.78 s.

上述比較分析了DMDO相比兩種傳統(tǒng)算法DBSCAN及OPTICS在準(zhǔn)確性和效率上的優(yōu)勢(shì)，下文將通過(guò)圖3(a)和圖3(c)分析參數(shù)二值化閾值θ及膨脹運(yùn)算模板寬度w對(duì)DMDOF1值的影響。

當(dāng)w保持不變時(shí)，隨著二值化閾值θ增大，DMDO的F1值均存在先增后減的變化趨勢(shì)。原因是當(dāng)二值化閾值θ增大時(shí)，算法能夠有效濾除移動(dòng)對(duì)象偶然停留所產(chǎn)生的噪聲，使得算法準(zhǔn)確率增大，F(xiàn)1值增大；當(dāng)θ持續(xù)增大，可能將真實(shí)的興趣點(diǎn)當(dāng)作噪聲濾除，使得算法準(zhǔn)確率、召回率均下降，F(xiàn)1值降低。

當(dāng)二值化閾值θ不變時(shí)，隨著膨脹運(yùn)算模板寬度w的增大，DMDO的F1值顯著增大(表現(xiàn)為w=5曲線(xiàn)在w=3曲線(xiàn)之上，w=3曲線(xiàn)在w=1曲線(xiàn)之上)。原因是膨脹運(yùn)算模板寬度反映膨脹程度，模板越寬，表明距離較近的停留網(wǎng)格越易連通。當(dāng)模板寬度w增大時(shí)，相鄰的興趣點(diǎn)連通，使得預(yù)測(cè)的興趣點(diǎn)總數(shù)減少，提高預(yù)測(cè)準(zhǔn)確率；另一方面，連通相鄰興趣點(diǎn)時(shí)覆蓋了興趣點(diǎn)之間的間隙，預(yù)測(cè)的興趣點(diǎn)區(qū)域涵蓋真實(shí)興趣點(diǎn)的可能性更高，從而提高了召回率。準(zhǔn)確率、召回率的提高使得F1值增大。

圖3 實(shí)驗(yàn)結(jié)果Fig.3 Experimental results

另外，F(xiàn)1對(duì)參數(shù)θ的敏感程度較低，對(duì)w的敏感程度較高，也即參數(shù)w對(duì)F1的影響更為顯著。

最后，討論網(wǎng)格劃分寬度d對(duì)算法DMDO精度和效率的影響。圖4(a)和圖4(b)分別表示在數(shù)據(jù)集AMSA和IMIS3Days上改變網(wǎng)格劃分寬度d對(duì)F1值和運(yùn)行時(shí)間T的影響。

圖4 網(wǎng)格劃分寬度d對(duì)實(shí)驗(yàn)結(jié)果的影響Fig.4 Influence of cell width d on experimental results

網(wǎng)格劃分寬度d主要影響目的地挖掘的精細(xì)程度。調(diào)節(jié)網(wǎng)格劃分寬度d時(shí)應(yīng)相應(yīng)調(diào)整二值化閾值θ和膨脹運(yùn)算模板寬度w，以分別保持算法過(guò)濾停留點(diǎn)噪聲的力度和停留點(diǎn)連通的難易程度基本不變。例如，當(dāng)網(wǎng)格劃分寬度d增大至原來(lái)的2倍時(shí)，網(wǎng)格覆蓋區(qū)域的實(shí)際面積變?yōu)樵瓉?lái)的4倍，若此時(shí)二值化閾值θ和膨脹運(yùn)算模板寬度w保持不變，則網(wǎng)格將更易滿(mǎn)足二值化閾值θ，更易于被判定為停留網(wǎng)格，從而降低了算法過(guò)濾停留點(diǎn)噪聲的力度，并且由于網(wǎng)格覆蓋面積增大，距離較遠(yuǎn)的停留點(diǎn)更容易連通，從而增大了算法連通停留點(diǎn)的能力。為了保持算法過(guò)濾停留點(diǎn)噪聲的力度和停留點(diǎn)連通的難易程度基本不變，如圖4(a)所示，當(dāng)網(wǎng)格劃分寬度d從0.1增大至原來(lái)的2倍時(shí)，二值化閾值θ也應(yīng)從27增大至原來(lái)的4倍，膨脹運(yùn)算模板寬度w應(yīng)從9相應(yīng)減小至5.

如圖4(a)和圖4(b)所示，當(dāng)減小網(wǎng)格劃分寬度d并相應(yīng)調(diào)整其他兩個(gè)參數(shù)時(shí)，算法DMDO的精度增高，算法效率降低。原因是減小網(wǎng)格劃分寬度d時(shí)，停留點(diǎn)將映射至更為精細(xì)的網(wǎng)格，覆蓋面積較小的興趣點(diǎn)更易被算法檢測(cè)出來(lái)，算法查全率提高，F(xiàn)1值增大。同時(shí)，由于網(wǎng)格劃分更為精細(xì)，算法需要處理的網(wǎng)格數(shù)量增多，因而運(yùn)行時(shí)間變長(zhǎng)，算法效率降低。

兩數(shù)據(jù)集興趣點(diǎn)檢測(cè)結(jié)果分別如圖5和圖6所示。從圖5和圖6可直觀(guān)看出，DMDO挖掘興趣點(diǎn)的準(zhǔn)確性較高。

圖5 數(shù)據(jù)集AMSA興趣點(diǎn)標(biāo)注及挖掘結(jié)果圖Fig.5 Extracted and predicted results of interest points on dataset AMSA

圖6 數(shù)據(jù)集IMIS3Days興趣點(diǎn)標(biāo)注及挖掘結(jié)果圖Fig.6 Extracted and predicted results of interest points on dataset IMIS3Days

實(shí)驗(yàn)結(jié)果表明，本文提出的DMDO能夠快速、準(zhǔn)確挖掘出研究區(qū)域的真實(shí)興趣點(diǎn)。相比DBSCAN算法，對(duì)于數(shù)據(jù)集AMSA，準(zhǔn)確率平均提高17.94%，算法效率提高6.63倍；對(duì)于數(shù)據(jù)集IMIS3Days，準(zhǔn)確率平均提高19.98%，算法效率提高9.13倍。相比OPTICS算法，對(duì)于數(shù)據(jù)集AMSA，準(zhǔn)確率平均提高20.04%，算法效率提高14.61倍；對(duì)于數(shù)據(jù)集IMIS3Days，準(zhǔn)確率平均提高16.60%，算法效率提高42.19倍。

3 結(jié)論

本文旨在研究準(zhǔn)確、高效的興趣點(diǎn)檢測(cè)方法。傳統(tǒng)算法易將移動(dòng)對(duì)象偶然的停留誤判為停留點(diǎn)，興趣點(diǎn)檢測(cè)的準(zhǔn)確性較低，并且對(duì)停留點(diǎn)聚類(lèi)的時(shí)間復(fù)雜度較高，時(shí)間開(kāi)銷(xiāo)大。針對(duì)傳統(tǒng)算法的不足，本文提出了DMDO，通過(guò)矩陣二值化操作濾除停留點(diǎn)噪聲，提高算法準(zhǔn)確性，并用膨脹運(yùn)算替代聚類(lèi)算法提高算法效率。在開(kāi)放空間數(shù)據(jù)集AMSA和IMIS3Days上進(jìn)行實(shí)驗(yàn)，得到如下結(jié)論：

1)DMDO在預(yù)測(cè)準(zhǔn)確性方面表現(xiàn)出顯著優(yōu)勢(shì)。相比DBSCAN算法，在數(shù)據(jù)集AMSA上準(zhǔn)確率平均提高17.94%，在數(shù)據(jù)集IMIS3Days上準(zhǔn)確率平均提高19.98%；相比OPTICS算法，在數(shù)據(jù)集AMSA上準(zhǔn)確率平均提高20.04%，在數(shù)據(jù)集IMIS3Days上準(zhǔn)確率平均提高16.60%. 表明本文提出的二值化操作濾除停留點(diǎn)噪聲的力度更強(qiáng)。

2)DMDO在保證預(yù)測(cè)準(zhǔn)確性的同時(shí)，大幅降低了時(shí)間開(kāi)銷(xiāo)。相比DBSCAN算法，在數(shù)據(jù)集AMSA上算法效率提高6.63倍，在數(shù)據(jù)集IMIS3Days上算法效率提高9.13倍。相比OPITCS算法，在數(shù)據(jù)集AMSA上算法效率提高14.61倍，在數(shù)據(jù)集IMIS3Days上算法效率提高42.19倍。表明算法適用于解決大數(shù)據(jù)背景下的移動(dòng)對(duì)象興趣點(diǎn)檢測(cè)問(wèn)題。

未來(lái)的研究工作包括：

1)DMDO適用于開(kāi)放空間的興趣點(diǎn)檢測(cè)問(wèn)題，應(yīng)用于城市軌跡數(shù)據(jù)時(shí)，易將城市路口誤判為興趣點(diǎn)，在未來(lái)工作中將擴(kuò)展算法的適用范圍。

2)將研究區(qū)域興趣點(diǎn)劃分層次，例如劃分為重要、較重要、非重要興趣點(diǎn)等，將算法擴(kuò)展為分層次檢測(cè)興趣點(diǎn)的方法。

References)

[1] Danalet A, Farooq B, Bierlaire M. A Bayesian approach to detect pedestrian destination-sequences from WiFi signatures[J]. Transportation Research Part C: Emerging Technologies, 2014, 44: 146-170.

[2] Liao L, Fox D, Kautz H. Extracting places and activities from GPS traces using hierarchical conditional random fields[J]. International Journal of Robotics Research, 2007, 26(1): 119-134.

[3] Cao X, Cong G, Jensen C S. Mining significant semantic locations from GPS data[J]. Proceedings of the VLDB Endowment, 2010, 3(1): 1009-1020.

[4] Qi L, Zheng Z. Trajectory prediction of vessels based on data mining and machine learning[J]. Journal of Digital Information Management, 2016, 14(1): 33-40.

[5] 喬少杰, 李天瑞, 韓楠, 等. 大數(shù)據(jù)環(huán)境下移動(dòng)對(duì)象自適應(yīng)軌跡預(yù)測(cè)模型[J]. 軟件學(xué)報(bào), 2015, 26(11): 2869-2883.

QIAO Shao-jie, LI Tian-rui, HAN Nan,et al. Self-adaptive trajectory prediction model for moving objects in big data environment[J]. Journal of Software, 2015, 26(11): 2869-2883.(in Chinese)

[6] Li Y, Guo A, Liu S, et al. A location based reminder system for advertisement[C]∥Proceedings of the 18th ACM International Conference on Multimedia. NY, US: ACM, 2010: 1501-1502.

[7] Chung J, Schmandt C. Going my way: a user-aware route planner[C]∥Proceedings of the SIGCHI Conference on Human Factors in Computing Systems.NY, US: ACM, 2009: 1899-1902.

[8] Zheng Y, Zhang L Z, Ma Z X, et al. Recommending friends and locations based on individual location history[J]. ACM Transactions on the Web (TWEB), 2011, 5(1): 5.

[9] 楊潔. 基于歷史軌跡的位置預(yù)測(cè)方法研究[D]. 杭州:杭州電子科技大學(xué), 2015.

YANG Jie. The research on technologies of predicting next location based on historical trajectory[D]. Hangzhou:Hangzhou Dianzi University, 2015.(in Chinese)

[10] Xie K, Deng K, Zhou X. From trajectories to activities: a spatio-temporal join approach[C]∥Proceedings of the 2009 International Workshop on Location Based Social Networks.NY, US: ACM, 2009: 25-32.

[11] Agamennoni G, Nieto J, Nebot E. Mining GPS data for extracting significant places[C]∥IEEE International Conference on Robotics and Automation. NJ, US: IEEE, 2009: 855-862.

[12] Zheng Y, Zhang L Z, Xie X, et al. Mining interesting locations and travel sequences from GPS trajectories[C]∥Proceedings of the 18th International Conference on World Wide Web. NY, US: ACM, 2009: 791-800.

[13] Luo T, Zheng X W, Xu G L, et al. An improved DBSCAN algorithm to detect stops in individual trajectories[J]. ISPRS International Journal of Geo-Information, 2017, 6(3): 63.

[14] Ashbrook D, Starner T. Using GPS to learn significant locations and predict movement across multiple users[J]. Personal and Ubiquitous Computing, 2003, 7(5): 275-286.

[15] Palma A T, Bogorny V, Kuijpers B, et al. A clustering-based approach for discovering interesting places in trajectories[C]∥Proceedings of the 2008 ACM Symposium on Applied Computing. NY, US: ACM, 2008: 863-868.

[16] Zimmermann M, Kirste T, Spiliopoulou M. Finding stops in error-prone trajectories of moving objects with time-based clustering[M]. Berlin, Germany: Springer, 2009: 275-286.

InterestPointDetectionMethodBasedonDilationOperation

WANG Qing1,2,3， DING Chi-biao1,3， FU Kun1,2,3， REN Wen-juan1,2,3
(1.Institute of Electronics, Chinese Academy of Sciences, Beijing 100190, China; 2.Key Laboratory of Technology in GEO-Spatial Information Processing and Application System, Chinese Academy of Sciences, Beijing 100190, China; 3.School of Electronic, Electrical and Communication Engineering, University of Chinese Academy of Sciences, Beijing 100049, China)

An interest point detection method based on dilation operation (DMDO) is proposed to improve the efficiency and accuracy of interest point detection, in which binarization is used to filter the noise, and the dilation operation is used to replace the clustering approach to enhance the efficiency of algorithm. DMDO is applied to two datasets of open space-AMSA and IMIS3Days. Compared to Density-Based Spatial Clustering of Applications with Noise (DBSCAN) , the accuracy of DMDO is increased by 17.94% on dataset AMSA, and by 19.98% on dataset IMIS3Days, while the efficiency is improved by 6.63 times on dataset AMSA, and by 9.13 times on dataset IMIS3Days. Compared to Ordering Point To Identify the Cluster Structure (OPTICS), the accuracy of DMDO is increased by 20.04% on dataset AMSA, and by 16.60% on dataset IMIS3Days, while the efficiency is improved by 14.61 times on dataset AMSA, and by 42.19 times on dataset IMIS3Days. Experimental results demonstrate that, compared with traditional methods, DMDO has higher accuracy with less time overhead. DMDO is applicable to detect the interest points in the era of big data.

information processing technology; trajectory data mining; interest point detection; dilation operation; open space

2017-04-13

王清(1992—)，女，碩士研究生。E-mail: wangqing36@126.com

丁赤飚(1969—)，男，研究員，博士生導(dǎo)師。E-mail: cbding@mail.ie.ac.cn

TP181

A

1000-1093(2017)10-2041-07

10.3969/j.issn.1000-1093.2017.10.021