基于過濾-精煉策略的用戶特定時(shí)間段移動(dòng)軌跡特征提?、?/h1>

2017-10-13 12:04:34楊東山張曉濱

計(jì)算機(jī)系統(tǒng)應(yīng)用訂閱 2017年1期 收藏

關(guān)鍵詞：時(shí)間段軌跡學(xué)報(bào)

楊東山, 張曉濱

?

基于過濾-精煉策略的用戶特定時(shí)間段移動(dòng)軌跡特征提取①

楊東山, 張曉濱

(西安工程大學(xué)計(jì)算機(jī)科學(xué)學(xué)院, 西安 710048)

發(fā)現(xiàn)移動(dòng)用戶在特定時(shí)間段的軌跡特征是實(shí)現(xiàn)用戶個(gè)性化推薦服務(wù)的關(guān)鍵之一. 采用過濾--精煉策略, 研究了如何從單用戶的大量軌跡數(shù)據(jù)中發(fā)現(xiàn)其在較長時(shí)間內(nèi)的特定時(shí)間段的興趣點(diǎn). 在過濾階段, 將用戶連續(xù)若干天中同一特定時(shí)間段內(nèi)的軌跡數(shù)據(jù)進(jìn)行基于密度的聚類, 從而得到用戶在這些天中每天的該特定時(shí)間段的停留點(diǎn). 在精煉階段, 對所有的停留點(diǎn)再一次聚類, 進(jìn)而得到用戶在這些天中該特定時(shí)間段的興趣點(diǎn). 最后, 通過實(shí)驗(yàn)驗(yàn)證了該方法的有效性.

軌跡; 聚類; 停留點(diǎn); 興趣點(diǎn)

移動(dòng)設(shè)備的廣泛使用和GPS技術(shù)的迅猛發(fā)展使得海量的時(shí)空數(shù)據(jù)因運(yùn)而生. 這些數(shù)據(jù)給人們的生活和學(xué)者的科研帶來了新的機(jī)遇與挑戰(zhàn). 通過對用戶的海量的時(shí)空數(shù)據(jù)分析, 我們可以得到用戶在日常生活中感興趣的地點(diǎn), 從而在許多基于位置的服務(wù)中更好地為用戶推薦貼心的個(gè)性化服務(wù)[1,2]. 而如何高效準(zhǔn)確地從海量的時(shí)空數(shù)據(jù)中得到用戶感興趣的地點(diǎn)是研究用戶移動(dòng)行為的可預(yù)見性和獨(dú)一性[3,4]進(jìn)而實(shí)現(xiàn)用戶個(gè)性化推薦的關(guān)鍵問題之一[5,6]. 該問題已經(jīng)引起了眾多學(xué)者的關(guān)注和思考.

Palma等人[7]基于改進(jìn)的DBSCAN算法提出了一種根據(jù)用戶移動(dòng)速度的快慢來識別用戶停留點(diǎn)的算法. 該算法將傳統(tǒng)的DBSCAN算法中的鄰域改為基于路程的Eps-linear-neighborhood, 結(jié)合時(shí)間MinTime, 對空間數(shù)據(jù)進(jìn)行聚類, 所得到的簇作為該用戶的停留點(diǎn). 此外, 該算法還給出了聚類時(shí)所需半徑的計(jì)算方法. Zhao Xiuli等人[8]在Palma等人的基礎(chǔ)上對聚類時(shí)所需半徑的計(jì)算方法做了改進(jìn). Zhao等人[8]認(rèn)為聚類時(shí)所需的半徑計(jì)算方法應(yīng)該根據(jù)用戶移動(dòng)的速度快慢分為兩種情況, 而不是Palma等人所認(rèn)為的只有一種情況. Jose Antonio M.R.Rocha等人[9]提出了一種根據(jù)方向變化來識別停留點(diǎn)的方法并且成功地應(yīng)用于識別漁船的停留點(diǎn). 上述文獻(xiàn)只是對移動(dòng)對象的單條軌跡進(jìn)行了分析, 從而發(fā)現(xiàn)一些具有重要意義的位置[10]. 而實(shí)際生活中, 用戶某一天的活動(dòng)規(guī)律并不能代表該用戶長期以來一直遵循這條活動(dòng)規(guī)律. 例如: 某用戶有一天去某個(gè)商店購物, 然而在接下來的3個(gè)月沒有再去該商店購物. 此外, 許多研究旨在找出大量移動(dòng)對象在一個(gè)較長時(shí)間段內(nèi)的相似行為, 用來指導(dǎo)決策[11]. 然而這些方法取決于多個(gè)移動(dòng)對象, 只能用于對熱門區(qū)域的分析, 如: 預(yù)測到某條路線交通狀況[12,13].

日常生活中, 由于移動(dòng)通訊網(wǎng)絡(luò)使用傳統(tǒng)工作模式(如: 短信服務(wù)、廣播服務(wù))[14], 用戶總會隨時(shí)隨地收到大量的垃圾信息, 而不是在相應(yīng)的時(shí)間段和相應(yīng)的地點(diǎn)得到自己感興趣的信息. 這樣, 一方面致使自己所關(guān)心的信息被淹沒, 另一方面容易引起用戶對該服務(wù)強(qiáng)烈的厭惡和不滿. 因此, 如何從單用戶已有的移動(dòng)軌跡數(shù)據(jù)中得到其在特定時(shí)間段的興趣點(diǎn)成為解決上述問題的關(guān)鍵. 目前, 雖然學(xué)者們就如何分析時(shí)空數(shù)據(jù)已經(jīng)提出了許多改進(jìn)的基于密度的聚類方法, 但是只采用其中一種算法難以發(fā)掘出用戶在較長時(shí)間內(nèi)(如: 3個(gè)月)的同一特定時(shí)間段(如: 每天的8:00~10:00)的興趣點(diǎn). 為此, 本文采用過濾--精煉策略, 分兩個(gè)階段運(yùn)用基于密度的聚類, 較好地解決了該問題. 在過濾階段, 對某用戶的連續(xù)若干天中的同一特定時(shí)間段的軌跡數(shù)據(jù)聚類, 從而得出該用戶在每一天的該特定時(shí)段內(nèi)的停留點(diǎn). 在精煉階段, 對這些停留點(diǎn)聚類, 進(jìn)而得到該用戶在該特定時(shí)間段的興趣點(diǎn).

1 問題描述

定義1 (GPS軌跡). GPS軌跡是由一組連續(xù)的GPS點(diǎn)組成的有序序列, 可表示為={(1,1,1),..., (x,y,t)}. 其中(x,y,t)表示用戶的第個(gè)GPS點(diǎn). 在(x,y,t)中,x、y分別表示在時(shí)刻用戶的經(jīng)度和緯度.

定義2 (停留點(diǎn)). 在某段GPS軌跡中, 如果用戶在該段GPS軌跡的子軌跡={(x,y,t),...,(x,y,t)}中的速度, 則為停留點(diǎn). 其中,為閾值. 由此, 可得出的總路程不能超過閾值, 且該段子軌跡的持續(xù)時(shí)間.

在實(shí)際生活中, 定位系統(tǒng)以恒定的、短暫的時(shí)間間隔(通常為2-5秒)采集移動(dòng)用戶的GPS數(shù)據(jù), 所采集數(shù)據(jù)的位置屬性精度可以達(dá)到1m. 通過聚類所獲取的停留點(diǎn)中任意兩個(gè)相鄰時(shí)間的GPS點(diǎn)之間的距離非常小, 即所包含的GPS點(diǎn)在二維坐標(biāo)下不僅是密集的, 而且具有一定形狀. 因此, 為了便于計(jì)算, 通過計(jì)算中、的平均值以獲得的中心位置坐標(biāo), 從而將壓縮, 以減少計(jì)算量.

圖1 某用戶連續(xù)三天8:00~10:00的停留點(diǎn)

定義3 (移動(dòng)點(diǎn)). 在某段GPS軌跡中, 如果出現(xiàn)下列情況, 則視為移動(dòng)點(diǎn): (1)兩個(gè)時(shí)間相鄰的停留點(diǎn)之間所夾著的那段連續(xù)的GPS軌跡點(diǎn); (2)GPS軌跡的起始點(diǎn)和第一個(gè)停留點(diǎn)之間所夾著的那段連續(xù)的GPS軌跡點(diǎn); (3)GPS軌跡的終止點(diǎn)和最后一個(gè)停留點(diǎn)之間所夾著的那段連續(xù)的GPS軌跡點(diǎn); (4)如果整條GPS軌跡沒有一個(gè)停留點(diǎn), 則這條GPS軌跡中所有的點(diǎn)都是移動(dòng)點(diǎn).

定義4 (興趣點(diǎn)). 將集合{11,12,...,1k;21,22,...,2m;...;T1,T2,...,T’}中的停留點(diǎn)聚類, 所形成的每一個(gè)簇代表用戶在這連續(xù)的若干天內(nèi)同一特定時(shí)間段經(jīng)常訪問的地點(diǎn), 即用戶在該特定時(shí)間段的興趣點(diǎn). 其中, (11,12,...,1k)表示在第一天中用戶在該特定時(shí)間段共有個(gè)停留點(diǎn). 類似的, (T1,T2,...,T’)表示在第天中用戶在該特定時(shí)間段共有個(gè)停留點(diǎn).

2 特定時(shí)間段軌跡特征提取

與其它聚類方法相比, 基于密度的聚類可以發(fā)現(xiàn)任意形狀的簇. 這更符合用戶造訪某地的實(shí)際情況. 然而, 只采用一種現(xiàn)有的基于密度的聚類算法難以準(zhǔn)確地從單用戶的大量軌跡數(shù)據(jù)中發(fā)現(xiàn)其較長時(shí)間內(nèi)同一特定時(shí)間段的興趣點(diǎn). CB-SMoT[7]算法只適合提取用戶單條移動(dòng)軌跡的停留點(diǎn). 而ST-DBSCAN[15]算法在處理單條移動(dòng)軌跡時(shí), 由于無法在時(shí)間維度得到適合的半徑, 所以不能發(fā)現(xiàn)用戶單條移動(dòng)軌跡的停留點(diǎn), 但是它可以對多條移動(dòng)軌跡進(jìn)行聚類分析. 綜上, 本文采用過濾--精煉策略, 分為兩個(gè)階段(過濾階段和精煉階段)來有效地解決上述問題. 在過濾階段, 從某用戶連續(xù)若干天中同一特定時(shí)間段的GPS數(shù)據(jù)中過濾掉用戶每一天該特定時(shí)段的移動(dòng)點(diǎn), 進(jìn)而篩選出每一天該特定時(shí)段的停留點(diǎn). 在精煉階段, 從壓縮后的所有停留點(diǎn)中提取出用戶在這些天該特定時(shí)間段的興趣點(diǎn).

2.1 獲取停留點(diǎn)

用戶在運(yùn)動(dòng)時(shí), 當(dāng)其速度在某地變小時(shí), 說明該用戶在此地有停留, 對此地周圍的景物感興趣. 反之, 當(dāng)用戶的速度變大時(shí), 說明該用戶正忙著趕路, 無暇顧及周圍的景物. 因此, 當(dāng)用戶一條GPS軌跡中的某一段子軌跡的總路程不能超過閾值, 且該段子軌跡的持續(xù)時(shí)間大于等于閾值Δ時(shí), 則該段子軌跡被認(rèn)為是該用戶的停留點(diǎn).

根據(jù)上述理論, 本文在獲取停留點(diǎn)時(shí), 采用Eps-linear-neighborhood鄰域, 即: 在某段子軌跡中, 點(diǎn)的鄰域?yàn)?/p>

2.2 獲取興趣點(diǎn)

將上一小節(jié)所得的所有停留點(diǎn)壓縮, 然后對其聚類, 從而得到用戶在這些天該特定時(shí)間段的興趣點(diǎn). 本次聚類需要三個(gè)參數(shù), 它們分別是、、. 其中,用來判斷某一停留點(diǎn)在經(jīng)緯度維度是否屬于另一停留點(diǎn)的鄰域; 而用來判斷某一停留點(diǎn)在時(shí)間維度是否屬于另一停留點(diǎn)的鄰域.、的計(jì)算公式如下:

(4)

3 實(shí)驗(yàn)與分析

本文采用微軟(亞洲研究所)對外公開的GeoLife數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)集. 隨機(jī)選取1名用戶A的連續(xù)3個(gè)月中每天8:00~10:00的GPS數(shù)據(jù)作為研究對象.

由于在實(shí)際生活中人們造訪某地時(shí)的速度是在一定范圍內(nèi)的, 所以在獲取用戶停留點(diǎn)時(shí)所需的參數(shù)對所有用戶具有通用性. 因此, 本文在獲取用戶停留點(diǎn)時(shí), 根據(jù)已有的文獻(xiàn)和先驗(yàn)知識, 選取了具有通用性的實(shí)驗(yàn)所需的參數(shù). 由于每個(gè)用戶的生活習(xí)慣不同, 他們在特定時(shí)間段內(nèi)的停留點(diǎn)個(gè)數(shù)、停留時(shí)間的長短不同, 而這些都會直接地對獲取用戶興趣點(diǎn)造成影響, 因此在獲取某用戶興趣點(diǎn)時(shí), 需要尋求適合該用戶的最佳參數(shù), 而不是一概而論. 為此, 本文通過實(shí)驗(yàn)得到適合用戶A在獲取興趣點(diǎn)時(shí)所需的最佳參數(shù), 進(jìn)而驗(yàn)證了所提出的方法的有效性.

圖2 用戶A某天8:00~10:00的軌跡

圖3 用戶A某天8:00~10:00的停留點(diǎn)

(a)MinPts=2

(b)MinPts=3

(c)MinPts=4

(d)MinPts=5

圖4 用戶A在不同參數(shù)下聚類的平均值

使用上述最佳參數(shù)組合, 對已經(jīng)得到的用戶A所有停留點(diǎn)聚類, 得到如圖5所示的結(jié)果. 從圖5中可以看出來, 該用戶在這90天中這一時(shí)間段內(nèi)的興趣點(diǎn)共有8個(gè).

圖5 用戶A90天8:00~10:00經(jīng)常停留的地點(diǎn)

4 結(jié)語

本文采用過濾—精煉策略, 運(yùn)用基于密度的聚類對單用戶在特定時(shí)間段的移動(dòng)軌跡數(shù)據(jù)進(jìn)行分析, 從而得到該用戶在指定時(shí)間段的興趣點(diǎn). 這為實(shí)現(xiàn)基于位置的個(gè)性化推薦服務(wù)提供了扎實(shí)的基礎(chǔ). 在實(shí)際應(yīng)用中, 服務(wù)商可以根據(jù)用戶在特定時(shí)間段所處的位置為其提供更準(zhǔn)確的個(gè)性化推薦服務(wù).

1 宋國杰,唐世渭,楊冬青,等.一種無線通信環(huán)境中的用戶移動(dòng)模式的挖掘算法.軟件學(xué)報(bào),2002,13(8):1465–1471.

2 孟祥武,胡勛,王立才,等.移動(dòng)推薦系統(tǒng)及其應(yīng)用.軟件學(xué)報(bào),2013,24(1):91–108.

3 郭遲,劉經(jīng)南,方媛,等.位置大數(shù)據(jù)的價(jià)值提取與協(xié)同挖掘方法.軟件學(xué)報(bào),2014,25(4):713–730.

4 Song C, Qu Z, Blumm N, et al. Limits of predictability in human mobility. Science, 2010, 327(5968): 1018–1021.

5 劉樹棟,孟祥武.一種基于移動(dòng)用戶位置的網(wǎng)絡(luò)服務(wù)推薦方法.軟件學(xué)報(bào),2014,25(11):2556–2574.

6 劉樹棟,孟祥武.基于位置的社會化網(wǎng)絡(luò)推薦系統(tǒng).計(jì)算機(jī)學(xué)報(bào),2015,38(2):322–336.

7 Palma T, Bogorny V, Kuijpers B, et al. A clustering-based approach for discovering interesting places in trajectories. Proc. of the 2008 ACM Symp. on Applied Computing. New York. ACM. 2008. 863–868.

8 Zhao XL, Xu WX. A clustering-based approach for discovering interesting places in a single trajectory. 2009 Second International Conference on Intelligent Computation Technology and Automation. New York. IEEE. 2009. 429–432.

9 Rocha JAMR, Times VC, Oliveira G, et al. DB-SMOT: A direction-based spatio-temporal clusteringmethod. IEEE Conference of Intelligent Systems. New York. IEEE. 2010. 114–119.

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

11 劉奎恩,肖俊超,治明,等.軌跡數(shù)據(jù)庫中熱門區(qū)域的發(fā)現(xiàn).軟件學(xué)報(bào),2013,24(8):1816–1835.

12 喬少杰,金琨,韓楠,等.一種基于高斯混合模型的軌跡預(yù)測算法.軟件學(xué)報(bào),2015,26(5):1048–1063.

13 李國徽,鐘細(xì)亞.一種基于固定網(wǎng)格的移動(dòng)對象運(yùn)動(dòng)軌跡索引模型.計(jì)算機(jī)研究與發(fā)展,2006,43(5):828–833.

14 孟祥武,王凡,史艷翠,等.移動(dòng)用戶需求獲取技術(shù)及其應(yīng)用.軟件學(xué)報(bào),2014,25(3):439–456.

15 Birant D, Kut A. ST-DBSCAN: An algorithm for clustering spatial-temporal data. Data & Knowledge Engineering, 2007, 60(1): 208–221.

Feature Extraction for Users’ Trajectories in a Period Based on Filter-Refinement Strategy

YANG Dong-Shan, ZHANG Xiao-Bin

(School of Computer Science, Xi’an Polytechnic University, Xi’an 710048, China)

Finding features of users’ trajectories in a period of time is one of the key point to realize user’s personalized recommendation service. In this paper, how to find the interests in a period from the large amount of user’s trajectories is presented with a filter-refinement strategy. In the filter step, the user’s trajectories in the same period for several certain days are clustered based on density to obtain the user’s stops; in the refinement step, the stops are clustered to obtain the user’s interests. Finally, experiments show the effectiveness of this work.

trajectories; clustering; stop and move; interest

陜西省教育廳科學(xué)研究計(jì)劃(14JK1307);陜西省自然科學(xué)基金(2015JQ5157);西安工程大學(xué)研究生創(chuàng)新基金(CX201630)

2016-04-07;收到修改稿時(shí)間:2016-05-16

[10.15888/j.cnki.csa.005525]

猜你喜歡

時(shí)間段軌跡學(xué)報(bào)

軌跡

讀友·少年文學(xué)(清雅版)(2020年4期)2020-08-24 07:36:26

夏天曬太陽防病要注意時(shí)間段

今日農(nóng)業(yè)(2020年13期)2020-08-24 07:35:24

軌跡

讀友·少年文學(xué)(清雅版)(2020年3期)2020-07-24 08:57:04

致敬學(xué)報(bào)40年

泰山學(xué)院學(xué)報(bào)(2019年6期)2020-01-14 02:34:34

軌跡

現(xiàn)代裝飾(2018年5期)2018-05-26 09:09:39

進(jìn)化的軌跡（一）——進(jìn)化，無盡的適應(yīng)

中國三峽(2017年2期)2017-06-09 08:15:29

發(fā)朋友圈沒人看是一種怎樣的體驗(yàn)

意林(2017年8期)2017-05-02 17:40:37

不同時(shí)間段顱骨修補(bǔ)對腦血流動(dòng)力學(xué)變化的影響

醫(yī)學(xué)研究雜志(2015年5期)2015-06-10 06:43:26

學(xué)報(bào)簡介

天津商務(wù)職業(yè)學(xué)院學(xué)報(bào)(2015年2期)2015-02-28 16:47:22

學(xué)報(bào)簡介

天津商務(wù)職業(yè)學(xué)院學(xué)報(bào)(2015年1期)2015-02-28 16:47:12

計(jì)算機(jī)系統(tǒng)應(yīng)用2017年1期

計(jì)算機(jī)系統(tǒng)應(yīng)用的其它文章

基于實(shí)時(shí)技術(shù)的大氣顆粒物在線分析系統(tǒng)①

基于視覺注意和改進(jìn)隸屬度的FSVM彩色圖像分割①

復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)相似性算法及其在癲癇病輔助診斷的應(yīng)用①

一種快速單幅圖像去霧新方法①

基于RTX的實(shí)時(shí)數(shù)據(jù)處理系統(tǒng)①

基于壓縮感知的圖片壓縮與加密GUI系統(tǒng)①