基于帶時間約束頻繁路徑的離群軌跡檢測.pdf

1、近年來，便攜GPS設(shè)備的蓬勃發(fā)展使得我們可以輕易地收集到大量的時空軌跡數(shù)據(jù)，通過分析這些數(shù)據(jù)，我們可以發(fā)現(xiàn)隱藏在這些數(shù)據(jù)后面的秘密，從而更好地為我們的生產(chǎn)生活提供指導(dǎo)和幫助。本文的著眼點就是如何基于這些大規(guī)模時空軌跡數(shù)據(jù)進(jìn)行離群軌跡的挖掘和檢測。近年來，國內(nèi)外在離群軌跡檢測方面已經(jīng)取得了許多的成果，但是這些研究主要存在兩大不足之處：一、大部分離群軌跡檢測算法的時間復(fù)雜度較高，只適合處理小規(guī)模的數(shù)據(jù)集，面對日益增長的大規(guī)模數(shù)據(jù)集無從下手；

2、二、許多算法只考慮了空間上的離群，而忽略了時間因素對離群檢測的影響，從而產(chǎn)生誤判。
　　本文為了解決上述兩個問題，提出了基于帶時間約束頻繁路徑的離群軌跡檢測方法。此方法將空間離群與時間離群綜合考慮，并且適用于大規(guī)模軌跡數(shù)據(jù)集的檢測。此方法有兩個主要任務(wù)：一、給定一個大規(guī)模時空軌跡數(shù)據(jù)集，要能夠快速準(zhǔn)確地找到這個數(shù)據(jù)集中所有的離群軌跡；二、基于一個大規(guī)模時空軌跡數(shù)據(jù)集，能夠?qū)崟r快速準(zhǔn)確地判斷一條當(dāng)前正在行走的軌跡是否具有離群的趨勢，

3、并且當(dāng)軌跡停止之后，如果此軌跡是離群的，需要指出此軌跡的哪個部分導(dǎo)致了軌跡的離群。針對上述的兩個任務(wù)，分別提出了離線檢測算法TPROO和實時檢測算法TPROR。TPROO算法摒棄了兩兩軌跡對比的思想，而是采取了分組檢測的思想，避免了大量不必要的計算，有效地縮短了離群檢測所需時間。除此之外，TPROO中提出了一種帶時間約束的軌跡編輯距離計算方法，充分考慮了空間和時間因素對離群檢測的影響。TPROR在TPROO的基礎(chǔ)之上進(jìn)行了許多優(yōu)化，增加