基于過(guò)濾-精煉策略的用戶特定時(shí)間段移動(dòng)軌跡特征提?、?/h1>
2017-10-13 12:04:34楊東山張曉濱
計(jì)算機(jī)系統(tǒng)應(yīng)用 2017年1期
楊東山, 張曉濱
?
基于過(guò)濾-精煉策略的用戶特定時(shí)間段移動(dòng)軌跡特征提取①
楊東山, 張曉濱
(西安工程大學(xué)計(jì)算機(jī)科學(xué)學(xué)院, 西安 710048)
發(fā)現(xiàn)移動(dòng)用戶在特定時(shí)間段的軌跡特征是實(shí)現(xiàn)用戶個(gè)性化推薦服務(wù)的關(guān)鍵之一. 采用過(guò)濾--精煉策略, 研究了如何從單用戶的大量軌跡數(shù)據(jù)中發(fā)現(xiàn)其在較長(zhǎng)時(shí)間內(nèi)的特定時(shí)間段的興趣點(diǎn). 在過(guò)濾階段, 將用戶連續(xù)若干天中同一特定時(shí)間段內(nèi)的軌跡數(shù)據(jù)進(jìn)行基于密度的聚類, 從而得到用戶在這些天中每天的該特定時(shí)間段的停留點(diǎn). 在精煉階段, 對(duì)所有的停留點(diǎn)再一次聚類, 進(jìn)而得到用戶在這些天中該特定時(shí)間段的興趣點(diǎn). 最后, 通過(guò)實(shí)驗(yàn)驗(yàn)證了該方法的有效性.
軌跡; 聚類; 停留點(diǎn); 興趣點(diǎn)
移動(dòng)設(shè)備的廣泛使用和GPS技術(shù)的迅猛發(fā)展使得海量的時(shí)空數(shù)據(jù)因運(yùn)而生. 這些數(shù)據(jù)給人們的生活和學(xué)者的科研帶來(lái)了新的機(jī)遇與挑戰(zhàn). 通過(guò)對(duì)用戶的海量的時(shí)空數(shù)據(jù)分析, 我們可以得到用戶在日常生活中感興趣的地點(diǎn), 從而在許多基于位置的服務(wù)中更好地為用戶推薦貼心的個(gè)性化服務(wù)[1,2]. 而如何高效準(zhǔn)確地從海量的時(shí)空數(shù)據(jù)中得到用戶感興趣的地點(diǎn)是研究用戶移動(dòng)行為的可預(yù)見(jiàn)性和獨(dú)一性[3,4]進(jìn)而實(shí)現(xiàn)用戶個(gè)性化推薦的關(guān)鍵問(wèn)題之一[5,6]. 該問(wèn)題已經(jīng)引起了眾多學(xué)者的關(guān)注和思考.
Palma等人[7]基于改進(jìn)的DBSCAN算法提出了一種根據(jù)用戶移動(dòng)速度的快慢來(lái)識(shí)別用戶停留點(diǎn)的算法. 該算法將傳統(tǒng)的DBSCAN算法中的鄰域改為基于路程的Eps-linear-neighborhood, 結(jié)合時(shí)間MinTime, 對(duì)空間數(shù)據(jù)進(jìn)行聚類, 所得到的簇作為該用戶的停留點(diǎn). 此外, 該算法還給出了聚類時(shí)所需半徑的計(jì)算方法. Zhao Xiuli等人[8]在Palma等人的基礎(chǔ)上對(duì)聚類時(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ù)方向變化來(lái)識(shí)別停留點(diǎn)的方法并且成功地應(yīng)用于識(shí)別漁船的停留點(diǎn). 上述文獻(xiàn)只是對(duì)移動(dòng)對(duì)象的單條軌跡進(jìn)行了分析, 從而發(fā)現(xiàn)一些具有重要意義的位置[10]. 而實(shí)際生活中, 用戶某一天的活動(dòng)規(guī)律并不能代表該用戶長(zhǎng)期以來(lái)一直遵循這條活動(dòng)規(guī)律. 例如: 某用戶有一天去某個(gè)商店購(gòu)物, 然而在接下來(lái)的3個(gè)月沒(méi)有再去該商店購(gòu)物. 此外, 許多研究旨在找出大量移動(dòng)對(duì)象在一個(gè)較長(zhǎng)時(shí)間段內(nèi)的相似行為, 用來(lái)指導(dǎo)決策[11]. 然而這些方法取決于多個(gè)移動(dòng)對(duì)象, 只能用于對(duì)熱門(mén)區(qū)域的分析, 如: 預(yù)測(cè)到某條路線交通狀況[12,13].
日常生活中, 由于移動(dòng)通訊網(wǎng)絡(luò)使用傳統(tǒng)工作模式(如: 短信服務(wù)、廣播服務(wù))[14], 用戶總會(huì)隨時(shí)隨地收到大量的垃圾信息, 而不是在相應(yīng)的時(shí)間段和相應(yīng)的地點(diǎn)得到自己感興趣的信息. 這樣, 一方面致使自己所關(guān)心的信息被淹沒(méi), 另一方面容易引起用戶對(duì)該服務(wù)強(qiáng)烈的厭惡和不滿. 因此, 如何從單用戶已有的移動(dòng)軌跡數(shù)據(jù)中得到其在特定時(shí)間段的興趣點(diǎn)成為解決上述問(wèn)題的關(guān)鍵. 目前, 雖然學(xué)者們就如何分析時(shí)空數(shù)據(jù)已經(jīng)提出了許多改進(jìn)的基于密度的聚類方法, 但是只采用其中一種算法難以發(fā)掘出用戶在較長(zhǎng)時(shí)間內(nèi)(如: 3個(gè)月)的同一特定時(shí)間段(如: 每天的8:00~10:00)的興趣點(diǎn). 為此, 本文采用過(guò)濾--精煉策略, 分兩個(gè)階段運(yùn)用基于密度的聚類, 較好地解決了該問(wèn)題. 在過(guò)濾階段, 對(duì)某用戶的連續(xù)若干天中的同一特定時(shí)間段的軌跡數(shù)據(jù)聚類, 從而得出該用戶在每一天的該特定時(shí)段內(nèi)的停留點(diǎn). 在精煉階段, 對(duì)這些停留點(diǎn)聚類, 進(jìn)而得到該用戶在該特定時(shí)間段的興趣點(diǎn).
1 問(wèn)題描述
定義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). 其中,為閾值. 由此, 可得出的總路程不能超過(guò)閾值, 且該段子軌跡的持續(xù)時(shí)間.
在實(shí)際生活中, 定位系統(tǒng)以恒定的、短暫的時(shí)間間隔(通常為2-5秒)采集移動(dòng)用戶的GPS數(shù)據(jù), 所采集數(shù)據(jù)的位置屬性精度可以達(dá)到1m. 通過(guò)聚類所獲取的停留點(diǎn)中任意兩個(gè)相鄰時(shí)間的GPS點(diǎn)之間的距離非常小, 即所包含的GPS點(diǎn)在二維坐標(biāo)下不僅是密集的, 而且具有一定形狀. 因此, 為了便于計(jì)算, 通過(guò)計(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軌跡沒(méi)有一個(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)常訪問(wèn)的地點(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)其較長(zhǎng)時(shí)間內(nèi)同一特定時(shí)間段的興趣點(diǎn). CB-SMoT[7]算法只適合提取用戶單條移動(dòng)軌跡的停留點(diǎn). 而ST-DBSCAN[15]算法在處理單條移動(dòng)軌跡時(shí), 由于無(wú)法在時(shí)間維度得到適合的半徑, 所以不能發(fā)現(xiàn)用戶單條移動(dòng)軌跡的停留點(diǎn), 但是它可以對(duì)多條移動(dòng)軌跡進(jìn)行聚類分析. 綜上, 本文采用過(guò)濾--精煉策略, 分為兩個(gè)階段(過(guò)濾階段和精煉階段)來(lái)有效地解決上述問(wèn)題. 在過(guò)濾階段, 從某用戶連續(xù)若干天中同一特定時(shí)間段的GPS數(shù)據(jù)中過(guò)濾掉用戶每一天該特定時(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í), 說(shuō)明該用戶在此地有停留, 對(duì)此地周圍的景物感興趣. 反之, 當(dāng)用戶的速度變大時(shí), 說(shuō)明該用戶正忙著趕路, 無(wú)暇顧及周圍的景物. 因此, 當(dāng)用戶一條GPS軌跡中的某一段子軌跡的總路程不能超過(guò)閾值, 且該段子軌跡的持續(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)壓縮, 然后對(duì)其聚類, 從而得到用戶在這些天該特定時(shí)間段的興趣點(diǎn). 本次聚類需要三個(gè)參數(shù), 它們分別是、、. 其中,用來(lái)判斷某一停留點(diǎn)在經(jīng)緯度維度是否屬于另一停留點(diǎn)的鄰域; 而用來(lái)判斷某一停留點(diǎn)在時(shí)間維度是否屬于另一停留點(diǎn)的鄰域.、的計(jì)算公式如下:
(4)
3 實(shí)驗(yàn)與分析
本文采用微軟(亞洲研究所)對(duì)外公開(kāi)的GeoLife數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)集. 隨機(jī)選取1名用戶A的連續(xù)3個(gè)月中每天8:00~10:00的GPS數(shù)據(jù)作為研究對(duì)象.
由于在實(shí)際生活中人們?cè)煸L某地時(shí)的速度是在一定范圍內(nèi)的, 所以在獲取用戶停留點(diǎn)時(shí)所需的參數(shù)對(duì)所有用戶具有通用性. 因此, 本文在獲取用戶停留點(diǎn)時(shí), 根據(jù)已有的文獻(xiàn)和先驗(yàn)知識(shí), 選取了具有通用性的實(shí)驗(yàn)所需的參數(shù). 由于每個(gè)用戶的生活習(xí)慣不同, 他們?cè)谔囟〞r(shí)間段內(nèi)的停留點(diǎn)個(gè)數(shù)、停留時(shí)間的長(zhǎng)短不同, 而這些都會(huì)直接地對(duì)獲取用戶興趣點(diǎn)造成影響, 因此在獲取某用戶興趣點(diǎn)時(shí), 需要尋求適合該用戶的最佳參數(shù), 而不是一概而論. 為此, 本文通過(guò)實(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ù)組合, 對(duì)已經(jīng)得到的用戶A所有停留點(diǎn)聚類, 得到如圖5所示的結(jié)果. 從圖5中可以看出來(lái), 該用戶在這90天中這一時(shí)間段內(nèi)的興趣點(diǎn)共有8個(gè).
圖5 用戶A90天8:00~10:00經(jīng)常停留的地點(diǎn)
4 結(jié)語(yǔ)
本文采用過(guò)濾—精煉策略, 運(yùn)用基于密度的聚類對(duì)單用戶在特定時(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 宋國(guó)杰,唐世渭,楊冬青,等.一種無(wú)線通信環(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 劉樹(shù)棟,孟祥武.一種基于移動(dòng)用戶位置的網(wǎng)絡(luò)服務(wù)推薦方法.軟件學(xué)報(bào),2014,25(11):2556–2574.
6 劉樹(shù)棟,孟祥武.基于位置的社會(huì)化網(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ù)庫(kù)中熱門(mén)區(qū)域的發(fā)現(xiàn).軟件學(xué)報(bào),2013,24(8):1816–1835.
12 喬少杰,金琨,韓楠,等.一種基于高斯混合模型的軌跡預(yù)測(cè)算法.軟件學(xué)報(bào),2015,26(5):1048–1063.
13 李國(guó)徽,鐘細(xì)亞.一種基于固定網(wǎng)格的移動(dòng)對(duì)象運(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]
猜你喜歡
軌跡讀友·少年文學(xué)(清雅版)(2020年4期)2020-08-24 07:36:26 夏天曬太陽(yáng)防病要注意時(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)化，無(wú)盡的適應(yīng)中國(guó)三峽(2017年2期)2017-06-09 08:15:29 發(fā)朋友圈沒(méi)人看是一種怎樣的體驗(yàn)意林(2017年8期)2017-05-02 17:40:37 不同時(shí)間段顱骨修補(bǔ)對(duì)腦血流動(dòng)力學(xué)變化的影響醫(yī)學(xué)研究雜志(2015年5期)2015-06-10 06:43:26 學(xué)報(bào)簡(jiǎn)介天津商務(wù)職業(yè)學(xué)院學(xué)報(bào)(2015年2期)2015-02-28 16:47:22 學(xué)報(bào)簡(jiǎn)介天津商務(wù)職業(yè)學(xué)院學(xué)報(bào)(2015年1期)2015-02-28 16:47:12
楊東山, 張曉濱
?
基于過(guò)濾-精煉策略的用戶特定時(shí)間段移動(dòng)軌跡特征提取①
楊東山, 張曉濱
(西安工程大學(xué)計(jì)算機(jī)科學(xué)學(xué)院, 西安 710048)
發(fā)現(xiàn)移動(dòng)用戶在特定時(shí)間段的軌跡特征是實(shí)現(xiàn)用戶個(gè)性化推薦服務(wù)的關(guān)鍵之一. 采用過(guò)濾--精煉策略, 研究了如何從單用戶的大量軌跡數(shù)據(jù)中發(fā)現(xiàn)其在較長(zhǎng)時(shí)間內(nèi)的特定時(shí)間段的興趣點(diǎn). 在過(guò)濾階段, 將用戶連續(xù)若干天中同一特定時(shí)間段內(nèi)的軌跡數(shù)據(jù)進(jìn)行基于密度的聚類, 從而得到用戶在這些天中每天的該特定時(shí)間段的停留點(diǎn). 在精煉階段, 對(duì)所有的停留點(diǎn)再一次聚類, 進(jìn)而得到用戶在這些天中該特定時(shí)間段的興趣點(diǎn). 最后, 通過(guò)實(shí)驗(yàn)驗(yàn)證了該方法的有效性.
軌跡; 聚類; 停留點(diǎn); 興趣點(diǎn)
移動(dòng)設(shè)備的廣泛使用和GPS技術(shù)的迅猛發(fā)展使得海量的時(shí)空數(shù)據(jù)因運(yùn)而生. 這些數(shù)據(jù)給人們的生活和學(xué)者的科研帶來(lái)了新的機(jī)遇與挑戰(zhàn). 通過(guò)對(duì)用戶的海量的時(shí)空數(shù)據(jù)分析, 我們可以得到用戶在日常生活中感興趣的地點(diǎn), 從而在許多基于位置的服務(wù)中更好地為用戶推薦貼心的個(gè)性化服務(wù)[1,2]. 而如何高效準(zhǔn)確地從海量的時(shí)空數(shù)據(jù)中得到用戶感興趣的地點(diǎn)是研究用戶移動(dòng)行為的可預(yù)見(jiàn)性和獨(dú)一性[3,4]進(jìn)而實(shí)現(xiàn)用戶個(gè)性化推薦的關(guān)鍵問(wèn)題之一[5,6]. 該問(wèn)題已經(jīng)引起了眾多學(xué)者的關(guān)注和思考.
Palma等人[7]基于改進(jìn)的DBSCAN算法提出了一種根據(jù)用戶移動(dòng)速度的快慢來(lái)識(shí)別用戶停留點(diǎn)的算法. 該算法將傳統(tǒng)的DBSCAN算法中的鄰域改為基于路程的Eps-linear-neighborhood, 結(jié)合時(shí)間MinTime, 對(duì)空間數(shù)據(jù)進(jìn)行聚類, 所得到的簇作為該用戶的停留點(diǎn). 此外, 該算法還給出了聚類時(shí)所需半徑的計(jì)算方法. Zhao Xiuli等人[8]在Palma等人的基礎(chǔ)上對(duì)聚類時(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ù)方向變化來(lái)識(shí)別停留點(diǎn)的方法并且成功地應(yīng)用于識(shí)別漁船的停留點(diǎn). 上述文獻(xiàn)只是對(duì)移動(dòng)對(duì)象的單條軌跡進(jìn)行了分析, 從而發(fā)現(xiàn)一些具有重要意義的位置[10]. 而實(shí)際生活中, 用戶某一天的活動(dòng)規(guī)律并不能代表該用戶長(zhǎng)期以來(lái)一直遵循這條活動(dòng)規(guī)律. 例如: 某用戶有一天去某個(gè)商店購(gòu)物, 然而在接下來(lái)的3個(gè)月沒(méi)有再去該商店購(gòu)物. 此外, 許多研究旨在找出大量移動(dòng)對(duì)象在一個(gè)較長(zhǎng)時(shí)間段內(nèi)的相似行為, 用來(lái)指導(dǎo)決策[11]. 然而這些方法取決于多個(gè)移動(dòng)對(duì)象, 只能用于對(duì)熱門(mén)區(qū)域的分析, 如: 預(yù)測(cè)到某條路線交通狀況[12,13].
日常生活中, 由于移動(dòng)通訊網(wǎng)絡(luò)使用傳統(tǒng)工作模式(如: 短信服務(wù)、廣播服務(wù))[14], 用戶總會(huì)隨時(shí)隨地收到大量的垃圾信息, 而不是在相應(yīng)的時(shí)間段和相應(yīng)的地點(diǎn)得到自己感興趣的信息. 這樣, 一方面致使自己所關(guān)心的信息被淹沒(méi), 另一方面容易引起用戶對(duì)該服務(wù)強(qiáng)烈的厭惡和不滿. 因此, 如何從單用戶已有的移動(dòng)軌跡數(shù)據(jù)中得到其在特定時(shí)間段的興趣點(diǎn)成為解決上述問(wèn)題的關(guān)鍵. 目前, 雖然學(xué)者們就如何分析時(shí)空數(shù)據(jù)已經(jīng)提出了許多改進(jìn)的基于密度的聚類方法, 但是只采用其中一種算法難以發(fā)掘出用戶在較長(zhǎng)時(shí)間內(nèi)(如: 3個(gè)月)的同一特定時(shí)間段(如: 每天的8:00~10:00)的興趣點(diǎn). 為此, 本文采用過(guò)濾--精煉策略, 分兩個(gè)階段運(yùn)用基于密度的聚類, 較好地解決了該問(wèn)題. 在過(guò)濾階段, 對(duì)某用戶的連續(xù)若干天中的同一特定時(shí)間段的軌跡數(shù)據(jù)聚類, 從而得出該用戶在每一天的該特定時(shí)段內(nèi)的停留點(diǎn). 在精煉階段, 對(duì)這些停留點(diǎn)聚類, 進(jìn)而得到該用戶在該特定時(shí)間段的興趣點(diǎn).
1 問(wèn)題描述
定義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). 其中,為閾值. 由此, 可得出的總路程不能超過(guò)閾值, 且該段子軌跡的持續(xù)時(shí)間.
在實(shí)際生活中, 定位系統(tǒng)以恒定的、短暫的時(shí)間間隔(通常為2-5秒)采集移動(dòng)用戶的GPS數(shù)據(jù), 所采集數(shù)據(jù)的位置屬性精度可以達(dá)到1m. 通過(guò)聚類所獲取的停留點(diǎn)中任意兩個(gè)相鄰時(shí)間的GPS點(diǎn)之間的距離非常小, 即所包含的GPS點(diǎn)在二維坐標(biāo)下不僅是密集的, 而且具有一定形狀. 因此, 為了便于計(jì)算, 通過(guò)計(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軌跡沒(méi)有一個(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)常訪問(wèn)的地點(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)其較長(zhǎng)時(shí)間內(nèi)同一特定時(shí)間段的興趣點(diǎn). CB-SMoT[7]算法只適合提取用戶單條移動(dòng)軌跡的停留點(diǎn). 而ST-DBSCAN[15]算法在處理單條移動(dòng)軌跡時(shí), 由于無(wú)法在時(shí)間維度得到適合的半徑, 所以不能發(fā)現(xiàn)用戶單條移動(dòng)軌跡的停留點(diǎn), 但是它可以對(duì)多條移動(dòng)軌跡進(jìn)行聚類分析. 綜上, 本文采用過(guò)濾--精煉策略, 分為兩個(gè)階段(過(guò)濾階段和精煉階段)來(lái)有效地解決上述問(wèn)題. 在過(guò)濾階段, 從某用戶連續(xù)若干天中同一特定時(shí)間段的GPS數(shù)據(jù)中過(guò)濾掉用戶每一天該特定時(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í), 說(shuō)明該用戶在此地有停留, 對(duì)此地周圍的景物感興趣. 反之, 當(dāng)用戶的速度變大時(shí), 說(shuō)明該用戶正忙著趕路, 無(wú)暇顧及周圍的景物. 因此, 當(dāng)用戶一條GPS軌跡中的某一段子軌跡的總路程不能超過(guò)閾值, 且該段子軌跡的持續(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)壓縮, 然后對(duì)其聚類, 從而得到用戶在這些天該特定時(shí)間段的興趣點(diǎn). 本次聚類需要三個(gè)參數(shù), 它們分別是、、. 其中,用來(lái)判斷某一停留點(diǎn)在經(jīng)緯度維度是否屬于另一停留點(diǎn)的鄰域; 而用來(lái)判斷某一停留點(diǎn)在時(shí)間維度是否屬于另一停留點(diǎn)的鄰域.、的計(jì)算公式如下:
(4)
3 實(shí)驗(yàn)與分析
本文采用微軟(亞洲研究所)對(duì)外公開(kāi)的GeoLife數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)集. 隨機(jī)選取1名用戶A的連續(xù)3個(gè)月中每天8:00~10:00的GPS數(shù)據(jù)作為研究對(duì)象.
由于在實(shí)際生活中人們?cè)煸L某地時(shí)的速度是在一定范圍內(nèi)的, 所以在獲取用戶停留點(diǎn)時(shí)所需的參數(shù)對(duì)所有用戶具有通用性. 因此, 本文在獲取用戶停留點(diǎn)時(shí), 根據(jù)已有的文獻(xiàn)和先驗(yàn)知識(shí), 選取了具有通用性的實(shí)驗(yàn)所需的參數(shù). 由于每個(gè)用戶的生活習(xí)慣不同, 他們?cè)谔囟〞r(shí)間段內(nèi)的停留點(diǎn)個(gè)數(shù)、停留時(shí)間的長(zhǎng)短不同, 而這些都會(huì)直接地對(duì)獲取用戶興趣點(diǎn)造成影響, 因此在獲取某用戶興趣點(diǎn)時(shí), 需要尋求適合該用戶的最佳參數(shù), 而不是一概而論. 為此, 本文通過(guò)實(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ù)組合, 對(duì)已經(jīng)得到的用戶A所有停留點(diǎn)聚類, 得到如圖5所示的結(jié)果. 從圖5中可以看出來(lái), 該用戶在這90天中這一時(shí)間段內(nèi)的興趣點(diǎn)共有8個(gè).
圖5 用戶A90天8:00~10:00經(jīng)常停留的地點(diǎn)
4 結(jié)語(yǔ)
本文采用過(guò)濾—精煉策略, 運(yùn)用基于密度的聚類對(duì)單用戶在特定時(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 宋國(guó)杰,唐世渭,楊冬青,等.一種無(wú)線通信環(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 劉樹(shù)棟,孟祥武.一種基于移動(dòng)用戶位置的網(wǎng)絡(luò)服務(wù)推薦方法.軟件學(xué)報(bào),2014,25(11):2556–2574.
6 劉樹(shù)棟,孟祥武.基于位置的社會(huì)化網(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ù)庫(kù)中熱門(mén)區(qū)域的發(fā)現(xiàn).軟件學(xué)報(bào),2013,24(8):1816–1835.
12 喬少杰,金琨,韓楠,等.一種基于高斯混合模型的軌跡預(yù)測(cè)算法.軟件學(xué)報(bào),2015,26(5):1048–1063.
13 李國(guó)徽,鐘細(xì)亞.一種基于固定網(wǎng)格的移動(dòng)對(duì)象運(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]
猜你喜歡
讀友·少年文學(xué)(清雅版)(2020年4期)2020-08-24 07:36:26
今日農(nóng)業(yè)(2020年13期)2020-08-24 07:35:24
讀友·少年文學(xué)(清雅版)(2020年3期)2020-07-24 08:57:04
泰山學(xué)院學(xué)報(bào)(2019年6期)2020-01-14 02:34:34
現(xiàn)代裝飾(2018年5期)2018-05-26 09:09:39
中國(guó)三峽(2017年2期)2017-06-09 08:15:29
意林(2017年8期)2017-05-02 17:40:37
醫(yī)學(xué)研究雜志(2015年5期)2015-06-10 06:43:26
天津商務(wù)職業(yè)學(xué)院學(xué)報(bào)(2015年2期)2015-02-28 16:47:22
天津商務(wù)職業(yè)學(xué)院學(xué)報(bào)(2015年1期)2015-02-28 16:47:12
