張沛朋 魏 楠

（濟(jì)源職業(yè)技術(shù)學(xué)院 河南濟(jì)源 459000）

基于巨量軌跡數(shù)據(jù)的熱點(diǎn)挖掘算法

張沛朋 魏 楠

（濟(jì)源職業(yè)技術(shù)學(xué)院 河南濟(jì)源 459000）

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

巨量軌跡數(shù)據(jù)；挖據(jù)算法；子軌跡；模糊C均值聚類(lèi)

隨著工業(yè)4.0全自動(dòng)化技術(shù)被日益提及，越來(lái)越多的學(xué)者開(kāi)始關(guān)注傳感器，射頻識(shí)別技術(shù)以及定位系統(tǒng)的實(shí)時(shí)位置捕捉問(wèn)題。但是這些實(shí)時(shí)位置點(diǎn)均鑲嵌于空間、時(shí)間相關(guān)聯(lián)的節(jié)點(diǎn)中，通常此類(lèi)位置點(diǎn)也被稱為空間點(diǎn)，而空間點(diǎn)所攜帶的數(shù)據(jù)就是現(xiàn)在被大量研究的時(shí)空數(shù)據(jù)，也被稱為軌跡數(shù)據(jù)。如何挖掘軌跡數(shù)據(jù)中有效信息以及潛在的有用信息是當(dāng)前數(shù)據(jù)挖掘的研究熱點(diǎn)。[1]本文主要研究了巨量軌跡數(shù)據(jù)的處理方法以及子軌跡數(shù)據(jù)挖掘算法。

一、軌跡數(shù)據(jù)結(jié)構(gòu)

軌跡是隨著移動(dòng)對(duì)象在時(shí)間領(lǐng)域中移動(dòng)時(shí)被記錄的一組記錄序列。因此，軌跡可以通過(guò)節(jié)點(diǎn)與節(jié)點(diǎn)相連接，節(jié)點(diǎn)也是軌跡的捕捉點(diǎn)，其中，可以將節(jié)點(diǎn)根據(jù)軌跡的時(shí)間變化分為起點(diǎn)，錨點(diǎn)以及終點(diǎn)，如圖1-1所示。

圖1-1 軌跡結(jié)構(gòu)示意圖

圖1-1中示意的錨點(diǎn)是軌跡駐留時(shí)間相對(duì)其他節(jié)點(diǎn)較長(zhǎng)的節(jié)點(diǎn)，表示移動(dòng)對(duì)象到達(dá)此位置的頻次。主要用來(lái)統(tǒng)計(jì)移動(dòng)對(duì)象的時(shí)空規(guī)律以及預(yù)測(cè)移動(dòng)對(duì)象的下一個(gè)實(shí)時(shí)位置。

二、基于巨量軌跡數(shù)據(jù)的挖掘算法

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

（一）算法基本思想?；诰蘖慷嗑S子軌跡聚類(lèi)算法基本思想：

Step3：根據(jù)拐點(diǎn)的位置，將整段移動(dòng)對(duì)象軌跡劃分為n+1段子軌跡；

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

Step5：采用模糊聚類(lèi)算法的思想，對(duì)子軌跡進(jìn)行聚類(lèi)，挖掘軌跡數(shù)據(jù)中所包含的有效信息。

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

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

2.價(jià)值函數(shù)。聚類(lèi)過(guò)程是否已經(jīng)終止需要通過(guò)價(jià)值函數(shù)對(duì)其進(jìn)行判斷。模糊C均值算法中的價(jià)值函數(shù)為：

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

利用拉格朗日乘子法構(gòu)造模糊C均值算法的最小目標(biāo)函數(shù)，表示為：

則可得到實(shí)現(xiàn)目標(biāo)函數(shù)的條件為：

（三）軌跡劃分。根據(jù)本文算法思想，將每一個(gè)移動(dòng)對(duì)象軌跡數(shù)據(jù)錄入到一個(gè)矩陣，并標(biāo)記每一個(gè)移動(dòng)軌跡數(shù)據(jù)為記錄點(diǎn)，通過(guò)計(jì)算每個(gè)記錄之間的曲率變化以及速度變化，尋找到軌跡數(shù)據(jù)的拐點(diǎn)。[6-8]算法如下：

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

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

算法步驟如下所示：

三、實(shí)驗(yàn)結(jié)果分析

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

表3-1 數(shù)據(jù)初始化

（二）實(shí)驗(yàn)結(jié)果評(píng)價(jià)。對(duì)于聚類(lèi)質(zhì)量的評(píng)估需要綜合評(píng)價(jià)，本文選擇簇內(nèi)方差評(píng)價(jià)，公式如下：

ci表示簇S的核心點(diǎn)

dis表示距離度量函數(shù)式

最優(yōu)的簇內(nèi)聚類(lèi)是簇的期望值盡可能等于0。

為了進(jìn)一步反應(yīng)新算法在聚類(lèi)中的優(yōu)勢(shì)，本文考慮了在不同維度下，變化時(shí)間和維度后新算法與以往聚類(lèi)算法在巨量數(shù)據(jù)下的誤差比較。

圖3-1 聚類(lèi)結(jié)果效果比較

圖3-1表示軌跡數(shù)據(jù)在不同維度下聚類(lèi)結(jié)果的質(zhì)量。其中，圖3-1（a）表示了不考慮速度維度時(shí)的算法質(zhì)量比較結(jié)果，圖3-1（b）表示了不考慮速度和時(shí)間維度的算法質(zhì)量比較結(jié)果。

新算法與之前算法的運(yùn)行時(shí)間比較結(jié)果如圖3-2所示。該實(shí)驗(yàn)環(huán)境是，增加初始狀態(tài)的簇?cái)?shù)量，則結(jié)果如下：

圖3-2 新舊算法運(yùn)行時(shí)間比較

由圖3-2可以清楚的看出，新算法的運(yùn)行時(shí)間相比較舊算法在不斷增加簇?cái)?shù)量的情況下有所降低，但是從圖3-1可以看出算法質(zhì)量并沒(méi)用降低。因此新算法對(duì)于巨量軌跡數(shù)據(jù)的挖掘有一定的效率以及質(zhì)量?jī)?yōu)勢(shì)。

四、結(jié)語(yǔ)

對(duì)于多維巨量軌跡數(shù)據(jù)的挖掘算法來(lái)說(shuō)，主要是集中于對(duì)子軌跡的劃分以及最后對(duì)子軌跡的聚類(lèi)。本文在前人的基礎(chǔ)上，通過(guò)軌跡的速度以及曲率變化標(biāo)記了軌跡的拐點(diǎn)，然后由拐點(diǎn)將軌跡劃分成若干子軌跡，最終使用改進(jìn)的模糊C聚類(lèi)算法對(duì)子軌跡進(jìn)行了聚類(lèi)。并評(píng)價(jià)了新算法的挖掘效果，最終得出新算法更適用于軌跡數(shù)據(jù)挖掘的結(jié)論。

[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]潘綱,李心堅(jiān),齊觀德，等.移動(dòng)軌跡數(shù)據(jù)分析與智慧城市[J].中國(guó)計(jì)算機(jī)學(xué)會(huì)通訊，2012（5）.

[7]劉大有,陳慧靈,齊紅,等.時(shí)空數(shù)據(jù)挖掘研究進(jìn)展[J].計(jì)算機(jī)研究與進(jìn)展，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.

[責(zé)任編輯 鄭麗娟]

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-），男，河南開(kāi)封人，濟(jì)源職業(yè)技術(shù)學(xué)院講師，碩士，研究方向：計(jì)算機(jī)應(yīng)用；魏楠（1983-)，女，河南濟(jì)源人，濟(jì)源職業(yè)技術(shù)學(xué)院講師，碩士，研究方向：計(jì)算機(jī)應(yīng)用。

2015年度河南省高等學(xué)校青年骨干教師資助計(jì)劃（編號(hào)：2015GGJS-282）。