軌跡聚類算法及其應(yīng)用

曹鑫磊 馮鋒

摘要：為了提高交通工具的利用率，通過獲取軌跡數(shù)據(jù)使移動點對象軌跡聚類分析在保證反映其相互之間正確的空間關(guān)系、時態(tài)關(guān)系、運動關(guān)系的基礎(chǔ)上，提出合理有效的相似性度量公式的結(jié)果。歐氏距離與設(shè)定的閾值a用于判定兩點之間是否處于同一位置，轉(zhuǎn)換為計算軌跡最長公共子序列問題求得相似度并作為最大生成樹聚類的權(quán)值。經(jīng)過軌跡聚類分析，得到聚類結(jié)果。

關(guān)鍵詞：軌跡；最大生成樹聚類；相似性度量；軌跡聚類分析

中圖分類號：TP311 文獻標(biāo)識碼：A 文章編號：1009-3044（2018）29-0009-03

Abstract： In order to improve the utilization rate of vehicles， the trajectory data is obtained to make the moving point object trajectory clustering analysis to propose a reasonable and effective similarity metric formula on the basis of ensuring the correct spatial relationship， temporal relationship and motion relationship. the result of. The Euclidean distance and the set threshold a are used to determine whether the two points are in the same position， and are converted to the longest common subsequence of the calculated trajectory to obtain the similarity and as the weight of the maximum spanning tree cluster. After trajectory clustering analysis， the clustering results are obtained.

Key words： Trajectory；maximum spanning tree clustering；similarity measure；trajectory clustering analysis

近年來，交通擁堵的問題越來越嚴(yán)重，合理的引導(dǎo)民眾選擇合理的交通出行方式已經(jīng)成為政府部門的責(zé)任。為此政府在大量的公共交通方式上安裝了GPS衛(wèi)星定位、北斗衛(wèi)星定位等設(shè)備。因此在極短的時間內(nèi)就積聚了海量的空間數(shù)據(jù)。伴隨著GPS、北斗等一系列的定位技術(shù)上的不斷成熟，能夠輕松地獲取到城鎮(zhèn)居民選取出行活動的各種軌跡數(shù)據(jù)。為了達到能夠了解城鎮(zhèn)居民出行情況的目的，為了解決交通擁堵的問題，諸如GPS、北斗衛(wèi)星等等的定位設(shè)備被有關(guān)部門越來越多的安裝在新型出租工具上。城鎮(zhèn)居民決定新型出租工具行駛的起點和終點，新型出租工具的運行軌跡能夠很好地反映城鎮(zhèn)居民出行特點。GPS、北斗衛(wèi)星軌跡具有數(shù)據(jù)易獲取、分布范圍地域廣闊、數(shù)據(jù)量特別巨大等特點，所以，GPS軌跡數(shù)據(jù)能夠成為城鎮(zhèn)居民出行方式分析的極佳數(shù)據(jù)來源。通過對這些GPS設(shè)備的信息采集，生成的大量的新型出租工具軌跡數(shù)據(jù)。明確新型出租工具軌跡數(shù)據(jù)中的大量信息才能夠分析城鎮(zhèn)居民的出行信息，才能夠達到優(yōu)化交通、改善路況的目的。

1 相關(guān)研究

分布式計算方法目前已成為大數(shù)據(jù)處理可行的辦法之一，此方法需要結(jié)合批量計算技術(shù)。因此，這次課程設(shè)計針對軌跡大數(shù)據(jù)將軌跡聚類，Li和Zheng在早年間就提出了一種基于密度的軌跡聚類算法TRACLUS，TRACLUS首先劃分軌跡，再將軌跡段進行聚類，

分析結(jié)果找出聚集的子線段簇。TRACLUS雖然是基于密度的軌跡聚類算法，結(jié)果可以顯示為任意軌跡簇，但是也有只考慮軌跡數(shù)據(jù)中空間信息而忽略時間信息得不足。

軌跡聚類分析屬于無監(jiān)督的一種學(xué)習(xí)方法，通過數(shù)據(jù)探索，給出數(shù)據(jù)描述，在其他方面還可以用于數(shù)據(jù)預(yù)測和內(nèi)容檢索等等。數(shù)據(jù)挖掘中研究極廣的課題之一包含聚類分析，聚類分析技術(shù)經(jīng)常用在語音識別、字符識別[1]等新型應(yīng)用上，將聚類分析技術(shù)按照不同的類別劃分：在圖像處理[2]方面，代表有Photoshop、美圖、濾鏡等，聚類主要用于數(shù)據(jù)的壓縮和信息的檢索，聚類過程需要把用戶拍好的照片中的像素點存入緩存器中；在機器學(xué)習(xí)方面，代表有機器人、人工智能產(chǎn)品，聚類主要的算法應(yīng)用在圖像分割和機器視覺上。經(jīng)過多年的發(fā)展聚類研究已經(jīng)深入到統(tǒng)計科學(xué)的領(lǐng)域。值得一提的是，聚類分析通過大數(shù)據(jù)研究也用在心理學(xué)、地質(zhì)學(xué)、考古學(xué)、生物學(xué)、地理學(xué)以及市場營銷等領(lǐng)域。

2 聚類算法

2.1 歐幾里得距離

歐幾里得距離無論在理學(xué)中還是工學(xué)中都是最常用的計算距離的公式，特別適用于數(shù)據(jù)量巨大且很密集的時候。

2.2 基于動態(tài)規(guī)劃的度量方法

動態(tài)規(guī)劃是求解最優(yōu)化問題的一種途徑、一種方法。動態(tài)規(guī)劃并不是算法，是因為它沒有指定的數(shù)學(xué)表達式，沒有像其他算法那樣清晰的解題步驟，因此動態(tài)規(guī)劃程序設(shè)計只能根據(jù)各種問題的性質(zhì)結(jié)合求此問題最優(yōu)解的條件，產(chǎn)生對此問題特定的解題方法。

2.2.1 基本模型

1） 首先要明確問題是什么，找出決策對象，進行下一步確認；

2） 根據(jù)問題所屬類型，對此類決策過程劃分成不同階段；

3） 根據(jù)問題所屬類型，設(shè)置問題所需變量并分發(fā)到各階段；

4） 根據(jù)狀態(tài)變量確定費用函數(shù)和目標(biāo)函數(shù)；

5） 根據(jù)問題所屬類型，建立此類問題各階段的狀態(tài)變量，通過變量確定狀態(tài)轉(zhuǎn)移方程。