譚夢茜， 邵雄凱, 劉　春,2

(1 湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院， 湖北 武漢 430068; 2 深圳市豪恩電子科技股份有限公司 廣東 深圳 518109)

基于時(shí)空分析的位置大數(shù)據(jù)挖掘方法研究

譚夢茜1， 邵雄凱1, 劉春1,2

(1 湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院， 湖北 武漢 430068; 2 深圳市豪恩電子科技股份有限公司 廣東 深圳 518109)

[摘要]位置數(shù)據(jù)的高維特性及其數(shù)據(jù)海量的特點(diǎn)，使得對位置數(shù)據(jù)的挖掘較為困難。為解決這一難題，首先對高維位置數(shù)據(jù)采用基于時(shí)空約束的頻率剪枝算法進(jìn)行數(shù)據(jù)清洗；然后設(shè)定時(shí)間維上興趣時(shí)間段的約束條件，提取興趣位置點(diǎn)；再根據(jù)歐式距離劃分與聚類劃分的原理相似性，引入K-Means聚類，實(shí)現(xiàn)對車主地理位置關(guān)系的挖掘。通過試驗(yàn)可以看出，該方法較為簡便的實(shí)現(xiàn)了對鄰里、同事關(guān)系的挖掘,結(jié)果符合該區(qū)居民的地理位置分布情況，證明了該方法的適用性。

[關(guān)鍵詞]時(shí)空分析；K-Means聚類算法；數(shù)據(jù)挖掘

位置數(shù)據(jù)是具有時(shí)空特性的數(shù)據(jù)，而時(shí)空數(shù)據(jù)挖掘是指從具有海量、高維(經(jīng)度、緯度、海拔、時(shí)間、ID、加速度等維度)、高噪聲和非線性等特性的時(shí)空數(shù)據(jù)中提取出隱含的、人們事先不知道的、但又潛在有用的信息及知識的過程。[1]隨著集成定位系統(tǒng)的智能手機(jī)和車機(jī)的普及、以及位置服務(wù)應(yīng)用的逐步推廣，時(shí)空數(shù)據(jù)急劇增加，尋找快速高效的時(shí)空數(shù)據(jù)挖掘方法成了數(shù)據(jù)挖掘的熱點(diǎn)和難點(diǎn)。

對海量的位置數(shù)據(jù)進(jìn)行時(shí)空分析，可以提取其中的用戶位置關(guān)系、軌跡關(guān)系、行為模式等，并可根據(jù)這些信息進(jìn)行針對性信息推薦。[2]考慮到時(shí)空數(shù)據(jù)具有時(shí)間和空間的高維特性，本文首先使用基于時(shí)空約束的頻率剪枝算法[3]進(jìn)行數(shù)據(jù)去噪和預(yù)處理，再在時(shí)間維上設(shè)置興趣時(shí)間段的約束條件，以縮減興趣位置點(diǎn)范圍，這樣處理后就只需考慮移動(dòng)對象位置點(diǎn)間的分布，從而實(shí)現(xiàn)了降維效果。然后利用K-Means聚類算法[4]根據(jù)位置點(diǎn)間的歐氏距離來劃分位置數(shù)據(jù)中聚集的類，從而定義地理位置上的關(guān)聯(lián)關(guān)系，并推導(dǎo)得出鄰里關(guān)系、同事關(guān)系等隱含信息。

1位置數(shù)據(jù)預(yù)處理

1.1數(shù)據(jù)描述

試驗(yàn)中所用到的數(shù)據(jù)來自2013-2014年武漢市車聯(lián)網(wǎng)測試項(xiàng)目中用戶車輛導(dǎo)航收集的車輛位置數(shù)據(jù)。原始數(shù)據(jù)表中主要保存了車輛裝配的導(dǎo)航終端采集的數(shù)據(jù)，這些數(shù)據(jù)包括記錄ID、設(shè)備通訊地址、時(shí)間、經(jīng)維度、加速度等字段信息。原始數(shù)據(jù)結(jié)構(gòu)定義見表1。

數(shù)據(jù)結(jié)構(gòu)的屬性值可以看作是不同的維度，通過維度的組合分析可以提供不同視角的信息。如對加速度維度和路徑(經(jīng)緯度組合)維度的分析，可以推斷車輛駕駛員的駕駛習(xí)慣等。本文目標(biāo)是分析車主間地理位置關(guān)系，因此通過選取ID、IdObj、Latitude、Longitude、CreateTime的維度組合來進(jìn)行挖掘分析。于是，二維空間中的一個(gè)移動(dòng)對象(Moving Object，縮寫MO)在某一時(shí)刻的位置狀態(tài)可以用一個(gè)四元組表示[5]：

MOID=(idObj,lat,lon,time)

1.2基于頻率剪枝算法的時(shí)空數(shù)據(jù)清洗

從海量數(shù)據(jù)中提取興趣信息，首先需要對數(shù)據(jù)進(jìn)行過濾和清洗[6]。針對提取鄰里關(guān)系和同事關(guān)系的要求，對數(shù)據(jù)進(jìn)行預(yù)處理，去除其中無意義的點(diǎn)、非工作日上傳的數(shù)據(jù)等，可以縮減處理工作量，大大加快處理速度。

本文采用結(jié)合時(shí)間和空間約束的概率剪枝策略實(shí)現(xiàn)對車輛位置數(shù)據(jù)的預(yù)處理。其中，概率剪枝算法[7]不同于以往的有嚴(yán)格剪枝條件的剪枝算法，而是根據(jù)具體問題中的概率因素來決定剪枝條件，對不太可能影響結(jié)果的最小-最大值的子樹進(jìn)行剪枝。

概率剪枝算法中的空間和時(shí)間約束主要是指設(shè)置在所研究空間的最小外包矩形MBR，包括經(jīng)緯度大小以及所研究時(shí)間段的區(qū)間。[3]此方法降噪的基本思想是，設(shè)定所研究的空間和時(shí)間范圍，對在該范圍上傳位置數(shù)據(jù)的每個(gè)用戶分別計(jì)算每天上傳的位置數(shù)據(jù)量，如果小于每天最低上傳頻率值Fremin，則判為無效數(shù)據(jù)，刪除用戶該天的位置信息。

基于時(shí)空約束的頻率剪枝算法如下：

限定時(shí)間約束(time[])為非節(jié)假日時(shí)間，空間約束為武漢市江漢區(qū)和江岸區(qū)部分區(qū)域所在的經(jīng)緯度lat[]∈(30.589325-30.648855),lon[]∈(114.22754-114.317568),頻率約束Fremin= 1000。

for each user in 數(shù)據(jù)集合MO[]

idObj = Cur_user

for each point in idObj的位置點(diǎn)集合

MO[n] = Cur_point

if MO[n].t∈{time[]} && MO[n].l∈{lat[],lon[]}

n++

end if

end for

if n < Fremin

idObj為無效用戶，刪除其相關(guān)信息

end if

通過隨機(jī)抽取10組用戶上傳的位置數(shù)據(jù)集合，采用上述方法進(jìn)行預(yù)處理，結(jié)果如表2所示，證明該剪枝算法的有效性。經(jīng)過上述處理后，可以得到江漢區(qū)和江岸區(qū)部分區(qū)域范圍內(nèi)工作日上傳的有效位置數(shù)據(jù)。

1.3時(shí)空數(shù)據(jù)的降維處理

為了從每天的位置數(shù)據(jù)中提取出車主小區(qū)位置點(diǎn)和公司位置點(diǎn)，需要對位置數(shù)據(jù)的時(shí)變特征進(jìn)行直觀的定性描述[8]。

本文將以上數(shù)據(jù)按每10 min

的時(shí)間片段等間隔統(tǒng)計(jì)各片段內(nèi)上傳的數(shù)據(jù)，得到時(shí)間曲線圖(圖 1)。圖中，橫軸表示等間隔取樣的片段，縱軸表示每間隔中上傳的數(shù)據(jù)量。從圖中可看出上下班高峰期分別在7∶20-9∶20和17∶00-19∶00時(shí)間段。所以，將時(shí)間維上的約束條件限定為7∶00-9∶40、16∶50-23∶59時(shí)間段范圍內(nèi)，并且各時(shí)間段開始后20 min、結(jié)束前20 min的任一時(shí)間段內(nèi)無上傳數(shù)據(jù)，以確保所選的兩個(gè)上下班時(shí)間段內(nèi)的第一和最后一條數(shù)據(jù)能代表小區(qū)坐標(biāo)位置和公司坐標(biāo)位置。通過限定正常情況下上下班位置數(shù)據(jù)出現(xiàn)的時(shí)間，使得在聚類過程中進(jìn)一步剔除噪聲數(shù)據(jù)，降低噪聲數(shù)據(jù)對算法的影響。

圖1　時(shí)間分布規(guī)律圖

經(jīng)過上述處理后，選取各用戶上傳的30 d數(shù)據(jù)。這樣，數(shù)據(jù)挖掘的對象是滿足時(shí)間約束條件的各用戶上傳天數(shù)達(dá)30 d的坐標(biāo)位置數(shù)據(jù)，數(shù)據(jù)挖掘的過程只用考慮移動(dòng)對象位置點(diǎn)的分布。

綜上，研究的對象從具有時(shí)空關(guān)系的四元組對象轉(zhuǎn)換為表示二維空間中的移動(dòng)對象位置點(diǎn)的三元組：

MOID=(idObj,lat,lon)

1.4數(shù)據(jù)可視化

對清洗前和清洗后的數(shù)據(jù)進(jìn)行可視化表達(dá)分別如圖2、圖3。從圖中可以看出，圖2中的原始數(shù)據(jù)分布符合武漢主城區(qū)沿長江和湖泊分布的情況。經(jīng)過清洗后，圖3中的數(shù)據(jù)量明顯減少，但是能更準(zhǔn)確地反映位置數(shù)據(jù)分布情況。針對清洗后的數(shù)據(jù)，選取上班時(shí)間段內(nèi)前三分鐘的坐標(biāo)和下班時(shí)間段內(nèi)最后三分鐘的坐標(biāo)，作為鄰里位置表；選取上班時(shí)間段最后三分鐘內(nèi)的坐標(biāo)和下班時(shí)間段內(nèi)前三分鐘的坐標(biāo)，作為公司位置表。然后，分別對鄰里位置表和公司位置表進(jìn)行K-Means聚類分析。

取剪跨比λ為4，配筋率ρl為0.96%、壁厚t為100 mm，不同軸壓比ηk的三種矩形空心墩，軸壓比分別為0.1、0.2、0.3，進(jìn)行Pushover分析，其對應(yīng)的能力曲線如圖10所示，由圖10可知，軸壓比增加1倍，空心墩的承載能力增加近50%，同時(shí)空心墩位移延性隨著軸壓比的提高而有所降低。

圖 2　清洗前的數(shù)據(jù)分布圖

圖 3　 清洗后的數(shù)據(jù)分布圖

2基于K-Means聚類的位置數(shù)據(jù)挖掘方法

2.1k-Means算法的適用性

為了挖掘位置點(diǎn)空間意義上的相近關(guān)系，即鄰里關(guān)系、同事關(guān)系，本文依據(jù)位置點(diǎn)間的歐式距離的遠(yuǎn)近來劃分位置數(shù)據(jù)集中聚集的類。而K-Means聚類算法采用距離作為相似性的評價(jià)指標(biāo)，即認(rèn)為兩個(gè)對象之間的距離越近，其相似性就越大。這與本文對位置點(diǎn)聚類所要達(dá)到的效果一致。同時(shí)，K-Means算法在處理大規(guī)模數(shù)據(jù)集時(shí)，其算法效率較高，適合對大規(guī)模數(shù)據(jù)集進(jìn)行高效聚類。[9]所以本文選用K-Means聚類算法進(jìn)行位置鄰近關(guān)系的劃分[10]。

對經(jīng)緯度位置數(shù)據(jù)進(jìn)行K-Means聚類的流程[11]如下：在位置數(shù)據(jù)中隨機(jī)抽取K個(gè)點(diǎn)作為聚類中心，然后遍歷其余位置并根據(jù)歐式距離來找到距離各自最近的聚類中心點(diǎn)，將其加入到該聚類中。然后各聚類通過誤差平方和這個(gè)準(zhǔn)則函數(shù)E來調(diào)整該聚類的聚類中心點(diǎn)，并將這個(gè)點(diǎn)作為下一次聚類的聚類中心。依次迭代，直到某一次迭代出的聚類中心和上一次的聚類中心相差的距離小于某個(gè)標(biāo)準(zhǔn)，則迭代結(jié)束。

在K-Means 聚類中，影響聚類效果的關(guān)鍵因素是聚類中心點(diǎn)的選取和類別數(shù)目的確定。隨機(jī)選擇聚類中心可能造成聚類中心過于居中或者不能均勻地分散在整個(gè)數(shù)據(jù)空間，導(dǎo)致收斂所需迭代次數(shù)增多，甚至陷入局部最優(yōu)解，影響聚類結(jié)果的準(zhǔn)確性。[9]而從圖3中，可以看出位置數(shù)據(jù)分布在部分區(qū)域密集，部分區(qū)域相對分散，所以本文結(jié)合位置數(shù)據(jù)分布的特點(diǎn)利用最小最大法來選擇聚類中心，即首先選擇所有對象點(diǎn)中相距最遠(yuǎn)的兩個(gè)對象點(diǎn)作為聚類中心，然后選擇第三個(gè)聚類中心點(diǎn)，使得它與之前確定的兩個(gè)點(diǎn)距離的較小值大于其余對象點(diǎn)與這兩個(gè)聚類中心點(diǎn)距離的較小值，以后的聚類中心點(diǎn)也按照同樣的原則選取。[11]而對于類別數(shù)目的確定，通過試驗(yàn)證明聚類數(shù)為12時(shí)，聚類效果最好。

2.2時(shí)空分析流程

基于上述分析，本文設(shè)計(jì)出針對坐標(biāo)位置數(shù)據(jù)的時(shí)空關(guān)系分析流程[12-13]：

步驟1在位置數(shù)據(jù)集合MO[]中依據(jù)最小最大法選取k個(gè)初始聚類中心點(diǎn)Zj(MOID), ID=1,2,3,…,n;j=1,2,3,…,k.經(jīng)試驗(yàn)證明k=12時(shí)，聚類效果最好，所以令k=12；

步驟2在n次迭代中，計(jì)算每個(gè)位置點(diǎn)與各聚類中心點(diǎn)的歐式距離D(MOID,Zj(MOID)),ID=1,2,3,…,n;j=1,2,3,…,k.若滿足D(MOID,Zk(MOID))=min{D(MOID,Zj(MOID)),

j=1,2,3,…,k}，則MOID∈wk,其中Wk為第k個(gè)聚類；即把位置點(diǎn)調(diào)整到K個(gè)類別中的離它最近的類別；

步驟3由步驟2得到新的聚類，計(jì)算誤差平方和準(zhǔn)則函數(shù)Jc(I)，I表示迭代次數(shù)。按照使Jc(I)最小的原則確定新的聚類中心。Jc(I)的表達(dá)式為:

步驟5如此重復(fù)步驟2，直到前后兩次迭代得到的聚類中心一模一樣。

通過K-Means算法分別對鄰里位置和公司位置進(jìn)行聚類后，將同一個(gè)聚類中位置點(diǎn)的車主間關(guān)系定義為鄰里關(guān)系或同事關(guān)系。

3結(jié)果分析

本文對武漢市江漢區(qū)和江岸區(qū)部分區(qū)域(圖4)的車輛位置大數(shù)據(jù)采用K-Means聚類分析后，將聚類數(shù)據(jù)進(jìn)行可視化表示，得到鄰里關(guān)系聚類圖(圖5)、同事關(guān)系聚類圖(圖6)，圖中不同的圖標(biāo)形狀代表了不同的聚類。從聚類結(jié)果圖中可發(fā)現(xiàn)，圖5中的聚類主要集中在江漢區(qū)和江岸區(qū)的小區(qū)住宅處，并呈現(xiàn)沿各主干道和江岸分布的特點(diǎn)，圖6中的聚類分布較為分散，符合該地區(qū)公司較多且分散的事實(shí)。通過以上分析，聚類結(jié)果能準(zhǔn)確反映武漢市該地區(qū)居民的鄰里位置和公司位置分布情況。

圖 4　江漢區(qū)和江岸區(qū)的研究范圍

圖 5　鄰里關(guān)系聚類圖

圖 6　同事關(guān)系聚類圖

本文所使用的基于K-Means位置數(shù)據(jù)分析方法也存在一定的不足：首先，該方法僅使用了K-Means空間聚類法，并沒有與現(xiàn)有的道路地圖相結(jié)合[10]；其次，該方法通過在時(shí)間維上設(shè)置約束條件的方式，來選取小區(qū)位置點(diǎn)、公司位置點(diǎn)，這種選取辦法適用于居民正常上下班的情況，而對于上晚班或上班時(shí)間自由等情況，則不適用。這些都是今后的改進(jìn)方向。

4結(jié)束語

通過分析具有時(shí)空關(guān)系的位置數(shù)據(jù)，可以發(fā)現(xiàn)、提取或總結(jié)出很多有價(jià)值的信息，從而幫助我們更好地研究車輛駕駛?cè)说木垲愱P(guān)系、行為關(guān)系，并可以進(jìn)行針對性的個(gè)性化數(shù)據(jù)推薦。本文對位置數(shù)據(jù)進(jìn)行數(shù)據(jù)清洗后，提取上下班時(shí)間段的位置點(diǎn)，并采用K-Means聚類方法挖掘位置數(shù)據(jù)之間隱藏的車主間地理位置關(guān)系的信息。以上對位置數(shù)據(jù)進(jìn)行的試驗(yàn)，能較好地分析出位置點(diǎn)聚集的簇，證明了該方法在實(shí)踐中的適用性。

[參考文獻(xiàn)]

[1]劉大有,陳慧靈,齊紅,等.時(shí)空數(shù)據(jù)挖掘研究進(jìn)展[J].計(jì)算機(jī)研究與發(fā)展，2013,50(2):225-239.

[2]龔璽,裴韜,孫嘉,等.時(shí)空軌跡聚類方法研究進(jìn)展[J].地理科學(xué)進(jìn)展，2011,30(5):522-534.

[3]鄒永貴,萬建斌,夏英.基于路網(wǎng)的LBSN用戶移動(dòng)軌跡聚類挖掘方法[J].計(jì)算機(jī)應(yīng)用研究, 2013,30 (08):2410-2414.

[4]席景科,譚海樵.空間聚類分析及評價(jià)方法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2009,30(07):1712-1715.

[5]Liu Xiaohua, Huang Jiejun, Wan Youchuan, et al. Logical expression of feature-based spatio-temporal data model research: 2nd international conference on information engineering and computer science - proceedings, ICIECS .2010[C]. IEEE Computer Society, 2010.

[6]Han J, Kamber M, PEI J. Data Mining：Concepts and Techniques [M]. 3nd ed.范明,孟小峰,譯.數(shù)據(jù)挖掘概念與北京：機(jī)械工業(yè)出版社,2012:55-79.

[7]紀(jì)洪生.基于概率的剪枝算法[J].電腦知識與技術(shù)，2006,32(11):99-100.

[8]王濤,王俊峰,羅積玉,等.基于時(shí)空分析的復(fù)雜交通流數(shù)據(jù)挖掘算法[J].四川大學(xué)學(xué)報(bào)(工程科學(xué)版)，2011,43(5):153-158.

[9]沈吟東,張仝輝,徐甲.基于K-means聚類算法的公交運(yùn)營時(shí)段分析[J].交通運(yùn)輸系統(tǒng)工程與信息，2014,14(2):87-93.

[10] 呂玉強(qiáng),秦勇,賈利民,等.基于出租車GPS數(shù)據(jù)聚類分析的交通小區(qū)動(dòng)態(tài)劃分方法研究[J].物流技術(shù)，2010(5):86-88,135.

[11] 熊忠陽,陳若田,張玉芳.一種有效的K-means聚類中心初始化方法[J].計(jì)算機(jī)應(yīng)用研究，2011, 28(11):4188-4190.

[12] 黃韜,劉勝輝,譚艷娜.基于k-means聚類算法的研究[J].計(jì)算機(jī)技術(shù)與發(fā)展， 2011,21 (7):54-57,62.

[13] Manish V, Mauly S, Neha C, et al. A comparative study of various clustering algorithms in data mining [J]. International Journal of Engineering Research and Applications. 2012,2(3):1379-1384.

[責(zé)任編校： 張巖芳]

Big Location Data Mining Research Based on Spatial and Time Analysis

TAN Mengxi1, SHAO Xiongkai1, LIU Chun1,2

(1SchoolofComputerScience,HubeiUniv.ofTech.,Wuhan430068;2LonghornTechnologyCo.,Ltd,Shenzhen518109,China)

Abstract：The multi-dimensional and massive characteristics of location data result in the difficulty of location data mining. In the study, we firstly used the frequency pruning method based on spatial-time constraints to clean and trim the data. Secondly, we extracted the position data we’re interested in by setting the constraint condition on the time dimension. Finally, according to the similarity between clustering and location coordinate classification, we used K-Means cluster analysis to mine the geographic relationship among cars owners from the location data. The experimental results show that the K-Means cluster analysis on the location data is able to quickly mine the geographic relationship among car owners, and the result conforms to the location distribution in the researched area.

Keywords：Spatial-time analysis; K-Means algorithm: Data mining

[收稿日期]2015-06-23

[基金項(xiàng)目]湖北省自然科學(xué)基金(2014CFB594)

[作者簡介]譚夢茜(1991-)， 女，湖北宜城人，湖北工業(yè)大學(xué)碩士研究生，研究方向?yàn)榇髷?shù)據(jù)分析與挖掘

[文章編號]1003-4684(2016)02-0053-05

[中圖分類號]TP311

[文獻(xiàn)標(biāo)識碼]：A

通訊地址表1原始數(shù)據(jù)結(jié)構(gòu)定義字段名含義ID記錄IDIdObj終端Latitude緯度Longitude經(jīng)度Altitude海拔Accelerometer_X緯度方向上的加速度Accelerometer_Y經(jīng)度方向上的加速度Accelerometer_Z海拔方向上的加速度CreateTime時(shí)間戳 其中，下標(biāo)ID表示這是移動(dòng)對象的第ID條記錄；idObj是移動(dòng)對象的終端，也可代表不同用戶；time是當(dāng)前記錄的時(shí)間戳；lat和lon表示移動(dòng)對象在time時(shí)刻所處經(jīng)緯度坐標(biāo)。