基于時空分析的位置大數據挖掘方法研究

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

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

基于時空分析的位置大數據挖掘方法研究

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

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

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

[關鍵詞]時空分析；K-Means聚類算法；數據挖掘

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

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

1位置數據預處理

1.1數據描述

試驗中所用到的數據來自2013-2014年武漢市車聯網測試項目中用戶車輛導航收集的車輛位置數據。原始數據表中主要保存了車輛裝配的導航終端采集的數據，這些數據包括記錄ID、設備通訊地址、時間、經維度、加速度等字段信息。原始數據結構定義見表1。

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

MOID=(idObj,lat,lon,time)

1.2基于頻率剪枝算法的時空數據清洗

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

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

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

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

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

for each user in 數據集合MO[]

idObj = Cur_user

for each point in idObj的位置點集合

MO[n] = Cur_point

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

n++

end if

end for

if n < Fremin

idObj為無效用戶，刪除其相關信息

end if

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

1.3時空數據的降維處理

為了從每天的位置數據中提取出車主小區位置點和公司位置點，需要對位置數據的時變特征進行直觀的定性描述[8]。

本文將以上數據按每10 min

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

圖1　時間分布規律圖

經過上述處理后，選取各用戶上傳的30 d數據。這樣，數據挖掘的對象是滿足時間約束條件的各用戶上傳天數達30 d的坐標位置數據，數據挖掘的過程只用考慮移動對象位置點的分布。

綜上，研究的對象從具有時空關系的四元組對象轉換為表示二維空間中的移動對象位置點的三元組：

MOID=(idObj,lat,lon)

1.4數據可視化

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

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

圖 2　清洗前的數據分布圖

圖 3　 清洗后的數據分布圖

2基于K-Means聚類的位置數據挖掘方法

2.1k-Means算法的適用性

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

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

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

2.2時空分析流程

基于上述分析，本文設計出針對坐標位置數據的時空關系分析流程[12-13]：

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

步驟2在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個聚類；即把位置點調整到K個類別中的離它最近的類別；

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

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

通過K-Means算法分別對鄰里位置和公司位置進行聚類后，將同一個聚類中位置點的車主間關系定義為鄰里關系或同事關系。

3結果分析

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

圖 4　江漢區和江岸區的研究范圍

圖 5　鄰里關系聚類圖

圖 6　同事關系聚類圖

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

4結束語

通過分析具有時空關系的位置數據，可以發現、提取或總結出很多有價值的信息，從而幫助我們更好地研究車輛駕駛人的聚類關系、行為關系，并可以進行針對性的個性化數據推薦。本文對位置數據進行數據清洗后，提取上下班時間段的位置點，并采用K-Means聚類方法挖掘位置數據之間隱藏的車主間地理位置關系的信息。以上對位置數據進行的試驗，能較好地分析出位置點聚集的簇，證明了該方法在實踐中的適用性。

[參考文獻]

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

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

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

[4]席景科,譚海樵.空間聚類分析及評價方法[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.范明,孟小峰,譯.數據挖掘概念與北京：機械工業出版社,2012:55-79.

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

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

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

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

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

[12] 黃韜,劉勝輝,譚艷娜.基于k-means聚類算法的研究[J].計算機技術與發展， 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.

[責任編校： 張巖芳]

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

[基金項目]湖北省自然科學基金(2014CFB594)

[作者簡介]譚夢茜(1991-)， 女，湖北宜城人，湖北工業大學碩士研究生，研究方向為大數據分析與挖掘

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

[中圖分類號]TP311

[文獻標識碼]：A

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