基于巨量軌跡數據的熱點挖掘算法

張沛朋 魏 楠

（濟源職業技術學院 河南濟源 459000）

基于巨量軌跡數據的熱點挖掘算法

張沛朋 魏 楠

（濟源職業技術學院 河南濟源 459000）

軌跡數據挖據算法目前主要集中于對有限維度屬性軌跡數據的挖據。對于巨量多維度情況下的軌跡數據挖據算法的研究還處于起步階段，較多研究結果均利用了常規性聚類算法，然而多維條件下的軌跡數據逐漸出現時空概念，常規的距離聚類已經不能有效地進行信息挖據。基于此背景，適時地提出了新的挖掘算法，是具有一定實際意義的。新算法加入時間維度，每個軌跡點的速度以及曲率屬性，將整條軌跡劃分為若干條子軌跡，再結合模糊C均值聚類，對子軌跡進行了聚類，與傳統算法相比較，新算法在聚類質量以及運行時間上均有一定的提升，新算法更適合巨量軌跡數據的挖據。

巨量軌跡數據；挖據算法；子軌跡；模糊C均值聚類

隨著工業4.0全自動化技術被日益提及，越來越多的學者開始關注傳感器，射頻識別技術以及定位系統的實時位置捕捉問題。但是這些實時位置點均鑲嵌于空間、時間相關聯的節點中，通常此類位置點也被稱為空間點，而空間點所攜帶的數據就是現在被大量研究的時空數據，也被稱為軌跡數據。如何挖掘軌跡數據中有效信息以及潛在的有用信息是當前數據挖掘的研究熱點。[1]本文主要研究了巨量軌跡數據的處理方法以及子軌跡數據挖掘算法。

一、軌跡數據結構

軌跡是隨著移動對象在時間領域中移動時被記錄的一組記錄序列。因此，軌跡可以通過節點與節點相連接，節點也是軌跡的捕捉點，其中，可以將節點根據軌跡的時間變化分為起點，錨點以及終點，如圖1-1所示。

圖1-1 軌跡結構示意圖

圖1-1中示意的錨點是軌跡駐留時間相對其他節點較長的節點，表示移動對象到達此位置的頻次。主要用來統計移動對象的時空規律以及預測移動對象的下一個實時位置。

二、基于巨量軌跡數據的挖掘算法

目前處理巨量的軌跡數據常用算法為聚類算法，通過聚類移動對象的相似軌跡，從而提取移動對象的運動特征，進一步預測移動對象的運動軌跡。[2]較成熟的軌跡聚類算法有歐式距離的軌跡聚類算法，豪斯多夫聚類算法以及最小外包矩形算法。但是此類聚類算法也有一些缺陷，例如，軌跡數據作為一種時空數據，歐式距離在時空領域逐漸失效。為此，本文提出了加入時間維度，將整個軌跡聚類劃分為子軌跡聚類的算法。

（一）算法基本思想。基于巨量多維子軌跡聚類算法基本思想：

Step3：根據拐點的位置，將整段移動對象軌跡劃分為n+1段子軌跡；

Step4：結合每段子軌跡的空間信息以及速度信息，度量子軌跡的距離；

Step5：采用模糊聚類算法的思想，對子軌跡進行聚類，挖掘軌跡數據中所包含的有效信息。

（二）算法概念解釋。本文巨量軌跡數據的挖掘核心點在于對子軌跡數據的模糊聚類，目前較為完善的聚類算法為模糊C均值算法[3-5]，因此本文的模糊聚類算法采用模糊C均值算法，其中的特定術語解釋如下：

1.隸屬度矩陣。設一個研究集合W中包含了m個元素wi(i=1,2,3…,m)。若將集合W劃分為z個子集J1,J2,J3…,Jz。則隸屬度矩陣D是由元素wi聚集到子集Jz的隸屬度dik，該矩陣是一個z行m列的矩陣，且0dik1。聚類之后，可以通過隸屬度劃分每個元素的類別。

2.價值函數。聚類過程是否已經終止需要通過價值函數對其進行判斷。模糊C均值算法中的價值函數為：

式中：表示模糊C均值算法中的模糊程度。

利用拉格朗日乘子法構造模糊C均值算法的最小目標函數，表示為：

則可得到實現目標函數的條件為：

（三）軌跡劃分。根據本文算法思想，將每一個移動對象軌跡數據錄入到一個矩陣，并標記每一個移動軌跡數據為記錄點，通過計算每個記錄之間的曲率變化以及速度變化，尋找到軌跡數據的拐點。[6-8]算法如下：

（四）子軌跡距離度量。兩條軌跡之間的距離需要通過三個子變量計算：位置距離，速度距離以及時間距離，除此之外還需軌跡數據的隸屬度屬性維度，則距離度量公式表示為：

（五）子軌跡聚類。巨量軌跡數據一般均是重疊或者部分重疊于一起。[9]在模型中的具體表現是隸屬度，且隸屬度是一個0于1之間的數值。

算法步驟如下所示：

三、實驗結果分析

（一）數據初始化。實驗所使用的數據為真實數據集，來源于2015年10月由數據堂提供的背景出租車GPS記錄的軌跡數據。該數據完整的記錄了出租車在北京市的運行軌跡，原始數據包含屬性維度較多，本文只是選擇了：車輛ID，GPS時間，GPS經度，GPS緯度，GPS速度，GPS方向屬性。數據初始化之后，如表3-1所示。

表3-1 數據初始化

（二）實驗結果評價。對于聚類質量的評估需要綜合評價，本文選擇簇內方差評價，公式如下：

ci表示簇S的核心點

dis表示距離度量函數式

最優的簇內聚類是簇的期望值盡可能等于0。

為了進一步反應新算法在聚類中的優勢，本文考慮了在不同維度下，變化時間和維度后新算法與以往聚類算法在巨量數據下的誤差比較。

圖3-1 聚類結果效果比較

圖3-1表示軌跡數據在不同維度下聚類結果的質量。其中，圖3-1（a）表示了不考慮速度維度時的算法質量比較結果，圖3-1（b）表示了不考慮速度和時間維度的算法質量比較結果。

新算法與之前算法的運行時間比較結果如圖3-2所示。該實驗環境是，增加初始狀態的簇數量，則結果如下：

圖3-2 新舊算法運行時間比較

由圖3-2可以清楚的看出，新算法的運行時間相比較舊算法在不斷增加簇數量的情況下有所降低，但是從圖3-1可以看出算法質量并沒用降低。因此新算法對于巨量軌跡數據的挖掘有一定的效率以及質量優勢。

四、結語

對于多維巨量軌跡數據的挖掘算法來說，主要是集中于對子軌跡的劃分以及最后對子軌跡的聚類。本文在前人的基礎上，通過軌跡的速度以及曲率變化標記了軌跡的拐點，然后由拐點將軌跡劃分成若干子軌跡，最終使用改進的模糊C聚類算法對子軌跡進行了聚類。并評價了新算法的挖掘效果，最終得出新算法更適用于軌跡數據挖掘的結論。

[1]Y.F.Li,J.W.Han,J.Yang.Clustering Moving Objects[M].In Proceedingsofthe10thACMSIGKDDInternationalConferenceon Knowledge Discovery and Data Mining,Seattle,WA,USA,2004, 617-622.

[2]Q.Zhang,X.Lin.Clustering Moving Objects for Spatiotemporal Selectivity Estimation[J].In Proceedings of the 15th Australasian Database Conference,Dunedin,New Zealand,2004：123-130.

[3]P.Kalnis,N.Mamoulis,S.Bakiras.On Discovering Moving Clusters in Spatio-temporal Data[J].In Proceedings of the 9th International Symposium on Spatial and Temporal Databases, AngradosReis,Brazil,2005：364-381.

[4]J.Chen,C.Lai,X.Meng,J.Xu,H.Hu.ClusteringMovingObjectsinSpatialNetworks[J].Inproceedingsofthe12thInternational Conference on Database Systems for Advanced Applications (DASFAA2007),Bangkok,Thailand,2007.

[5]J.Lee,J.Han,X.Li,H.Gonzalez.TraClass:TrajectoryClassification Using Hierarchical Region-Based and Trajectory-Based Clustering[J].InProc.VLDB2008：140-149.

[6]潘綱,李心堅,齊觀德，等.移動軌跡數據分析與智慧城市[J].中國計算機學會通訊，2012（5）.

[7]劉大有,陳慧靈,齊紅,等.時空數據挖掘研究進展[J].計算機研究與進展，2013,50(2):225-239.

[8]D.Chudova,S.Gaffney,E.Mjolsness,and P.Smyth.Translation-invariantmixture modelsforcurveclustering[J].In Proceedings of the 9th International Conference on Knowledge Discovery and Data Mining(KDD’03).ACM,New York,2003：79-88.

[9]T.Tzouramanis,M.Vassilakopoulos,and Y.Manolopoulos. Overlapping Linear Q uadtrees:A Spatio-Temporal Access Method[J].In Proc.of the ACM workshop on Adv.in Geographic Info.Sys.,ACMGIS,Nov.1998：1-7.

[責任編輯 鄭麗娟]

A Hotspot Mining Algorithm Based on Large Amount of Trajectory Data

Zhang Peipeng1Wei Nan2
(1.Department of Art and Design,Jiyuan Vocational and Technical College;2.Undergraduate Teaching Office, Jiyuan Vocational and Technical College,Jiyuan,Henan 459000)

The trajectory data mining algorithm is mainly focused on the mining of finite-dimensional attribute trajectory data.In this paper,we use the conventional clustering algorithm,but the trajectory data under the multi-dimensional condition gradually appear the concept of time and space,and the conventional distance clustering Has been unable to effectively carry out information digging.Based on this background,it is of practical significance to put forward a new mining algorithm in time.The new algorithm adds the time dimension,the velocity of each track point and the curvature attribute,divides the whole trajectory into several sub-trajectories,and then combines the fuzzy C-means clustering to cluster the sub-trajectories.Compared with the traditional algorithm,The clustering quality and the running time have some improvement,the new algorithm is more suitable for the huge amount of trajectory data.

huge amount of trajectory data;digging algorithm;sub-trajectory;fuzzy C-means clustering

TP393

A

2095-0438（2017）06-0150-04

2017-03-05

張沛朋（1983-），男，河南開封人，濟源職業技術學院講師，碩士，研究方向：計算機應用；魏楠（1983-)，女，河南濟源人，濟源職業技術學院講師，碩士，研究方向：計算機應用。

2015年度河南省高等學校青年骨干教師資助計劃（編號：2015GGJS-282）。