齊 帥, 單桂華, 田 東, 劉 俊

(中國科學(xué)院 計(jì)算機(jī)網(wǎng)絡(luò)信息中心,北京 100190)

基于基站數(shù)據(jù)挖掘個(gè)人駐留規(guī)律①

齊 帥, 單桂華, 田 東, 劉 俊

(中國科學(xué)院 計(jì)算機(jī)網(wǎng)絡(luò)信息中心,北京 100190)

個(gè)人移動(dòng)通訊設(shè)備和位置感知設(shè)備的廣泛應(yīng)用,使得運(yùn)營商積累了大量的用戶位置數(shù)據(jù).后前對(duì)位置數(shù)據(jù)的研究大都關(guān)注于活動(dòng)軌跡的挖掘,而少量對(duì)于個(gè)人駐留規(guī)律的研究也只停留在識(shí)別出駐留點(diǎn),卻缺乏進(jìn)一步的挖掘.本文基于基站采集的位置數(shù)據(jù)進(jìn)行研究,依據(jù)基站數(shù)據(jù)的特點(diǎn),提出了一種簡單的識(shí)別駐留點(diǎn)的方法.繼而提出了兩種挖掘駐留規(guī)律的方法.最后使用真實(shí)數(shù)據(jù)對(duì)算法效果進(jìn)行了驗(yàn)證.

基站數(shù)據(jù);活動(dòng)停留;密度聚類;最大頻繁項(xiàng)集挖掘算法

隨著跟蹤定位技術(shù)的迅速發(fā)展,人們可以通過很多方式獲取客體位置的數(shù)據(jù),從而激發(fā)了位置數(shù)據(jù)在諸多領(lǐng)域中的應(yīng)用.手機(jī)作為采集人們位置數(shù)據(jù)的天然信號(hào)接收裝置,在國內(nèi)被普遍使用.一般情況下一部手機(jī)只被一個(gè)人使用,手機(jī)便成為個(gè)人隨身攜帶的定位器.運(yùn)營商根據(jù)自身的需求,會(huì)采集大量用戶的位置信息,這為挖掘人們的出行規(guī)律提供了豐富的數(shù)據(jù)源.另一方面,大量的研究已經(jīng)證實(shí),人們的出行是有規(guī)律的.這些研究發(fā)現(xiàn),盡管個(gè)體存在差異,但他們大多數(shù)時(shí)間只訪問少量的幾個(gè)地方.更確切的說,Schlich and Axhausen的研究揭示70%的出行是到2到4個(gè)不同的地方,90%的出行是以8個(gè)不同的地方為后的地;Song的研究顯示,人們大多數(shù)時(shí)間停留在少量幾個(gè)地方,具體一點(diǎn)說,75%的時(shí)間用在最頻繁訪問的5個(gè)地方.這些研究為我們挖掘出有意義的結(jié)果提供了理論支持.

后前關(guān)于駐留規(guī)律的研究基本停留在識(shí)別出駐留點(diǎn)的階段.關(guān)于識(shí)別出駐留點(diǎn)的研究方法大致分為以下幾種:行進(jìn)速度、方向變化、信號(hào)缺失、軌點(diǎn)密度、K-中值算法、DJ-Cluster算法、CB-SMoT算法.對(duì)于在駐留點(diǎn)駐留的時(shí)段和時(shí)長的研究卻非常缺乏.本文提出了兩種方法來挖掘出個(gè)人在駐留點(diǎn)駐留的時(shí)段和時(shí)長,填補(bǔ)了這方面的空白.

1 基站數(shù)據(jù)特點(diǎn)

基站數(shù)據(jù)即通過基站采集的數(shù)據(jù),主要提供了以下三方面的信息:個(gè)人加密后的ID,采樣時(shí)用戶的位置(經(jīng)度,緯度)和時(shí)間.基站數(shù)據(jù)有以下兩個(gè)特點(diǎn):

(1)用戶在某個(gè)基站的信號(hào)覆蓋范圍內(nèi)活動(dòng),基站會(huì)定位到同一個(gè)位置點(diǎn).

(2)采樣時(shí)間間隔長且隨機(jī).

基站采樣效果如圖1所示,圖中每個(gè)藍(lán)色短線表示一個(gè)采樣點(diǎn).本文為了避免采樣點(diǎn)重合,將短線設(shè)置成360度隨機(jī)擺動(dòng).特點(diǎn)(1)意味著采集的位置數(shù)據(jù)和真實(shí)位置存在一定偏移,且一個(gè)采樣點(diǎn)標(biāo)識(shí)的是用戶在一定范圍內(nèi)的活動(dòng),范圍大小由最近基站的信號(hào)覆蓋范圍決定.也就意味著地圖由于各個(gè)基站的信號(hào)覆蓋范圍不同,被劃分成大小不規(guī)則的塊.特點(diǎn)(2)意味著用戶發(fā)生位置變化的時(shí)間點(diǎn)很不明確.基站數(shù)據(jù)采樣時(shí)間間隔平均在20分鐘以上,具體的采樣時(shí)間間隔因個(gè)人會(huì)有差異.比如某人規(guī)律性的在早晨八點(diǎn)離開家去公司,但由于采樣的隨機(jī)性,七點(diǎn)采樣一次,用戶在家,下次采樣間隔兩個(gè)小時(shí),九點(diǎn)采樣時(shí)用戶在公司,我們只能得到用戶在七點(diǎn)到九點(diǎn)的時(shí)間段內(nèi)離開家,而不能得到更準(zhǔn)確的離開家的時(shí)間點(diǎn)信息.

圖1 基站對(duì)一個(gè)人七個(gè)月的采樣結(jié)果展示

2 識(shí)別駐留點(diǎn)

駐留點(diǎn)就是一個(gè)人長期頻繁駐留的區(qū)域,比如家,公司,餐廳等.后前識(shí)別駐留點(diǎn)的方法很多,但是都不能直接用來解決基站數(shù)據(jù)的駐留點(diǎn)識(shí)別問題.根據(jù)基站數(shù)據(jù)的特點(diǎn),本文提出了一種簡單的統(tǒng)計(jì)方法來識(shí)別駐留點(diǎn).

因?yàn)橛脩粼谝欢ǚ秶鷥?nèi)的活動(dòng),基站會(huì)定位到同一個(gè)位置點(diǎn)上,采樣點(diǎn)有自動(dòng)聚類的效果.因此我們可以輕松的得到用戶在某個(gè)區(qū)域停留的時(shí)長.比如某人7:50在A點(diǎn),8:02在B點(diǎn),8:10在B點(diǎn),8:30在C點(diǎn),我們可以簡單的理解為8:02此人出現(xiàn)在B點(diǎn),8:30離開了B點(diǎn).那么此人在B點(diǎn)的停留時(shí)長為28分鐘.統(tǒng)計(jì)一天中停留時(shí)長超過半小時(shí)的點(diǎn),我們把這些點(diǎn)定義為一天的停留點(diǎn).

假如我們?cè)O(shè)置一個(gè)閾值(比如0.5),統(tǒng)計(jì)一個(gè)人被基站記錄以來,A點(diǎn)作為一天中的駐留點(diǎn)的天數(shù)超過了設(shè)置的閾值乘以記錄天數(shù),那么我們就可以把A點(diǎn)定義為駐留點(diǎn).簡單來說,設(shè)閾值為0.5,若記錄時(shí)長為六個(gè)月,一個(gè)人有90天以上在A點(diǎn)停留時(shí)間超過了半個(gè)小時(shí),我們就把A點(diǎn)定義為駐留點(diǎn).我們使用openstreetmap開源地圖來驗(yàn)證找到的駐留點(diǎn),發(fā)現(xiàn)大都定位在居住區(qū)和工作區(qū)內(nèi).這說明我們的方法是有效的.

3 挖掘駐留規(guī)律

3.1 分割時(shí)間段挖掘駐留規(guī)律

駐留規(guī)律是指個(gè)人在駐留點(diǎn)頻繁的駐留時(shí)段和時(shí)長.因?yàn)闀r(shí)間是一個(gè)連續(xù)的變量,如果要對(duì)時(shí)間進(jìn)行頻繁模式挖掘,首先需要把它轉(zhuǎn)換為離散的變量.因此本部分的思路為,先將一天的時(shí)間劃分為時(shí)間段,然后將一天的位置和時(shí)間點(diǎn)歸到相應(yīng)的時(shí)間段內(nèi).最后使用頻繁項(xiàng)集挖掘算法找到頻繁的駐留時(shí)段和時(shí)長.

(1)劃分時(shí)間段

將一天的時(shí)間劃分為時(shí)間段,以一小時(shí)為間隔舉例,那么一天劃分為0～1,1～2,2～3…23～24共 24 個(gè)時(shí)間段.

(2)時(shí)間點(diǎn)轉(zhuǎn)化為時(shí)間段

將時(shí)間點(diǎn)和位置用相應(yīng)的時(shí)間段表示,將有駐留點(diǎn)存在時(shí)間段標(biāo)記為此駐留點(diǎn),沒有記錄的時(shí)間段標(biāo)記為None,有記錄但不在駐留點(diǎn)的時(shí)間段標(biāo)記為M.比如A點(diǎn)和B點(diǎn)為駐留點(diǎn),以一小時(shí)為間隔劃分時(shí)間,某人一天的記錄如下所示:

00:01 A,01:10 A,06:05 A,08:10 C,09:20 B,11:15 B,13:12 D,15:16 B,17:10 B,19:02 E,20:10 A

那么這一天的記錄轉(zhuǎn)化為:

A,A,None,None,None,None,A,None,M,B,None,B,None,M,None,B,None,B,None,M,A,None,None,None.

通過轉(zhuǎn)化,可以直觀的得到一天中一個(gè)人在相應(yīng)的時(shí)段所在的位置.

(3)填補(bǔ)無記錄時(shí)間段

為減少隨機(jī)記錄造成的影響,我們將前后有相同駐留點(diǎn)標(biāo)記的,而中間沒有記錄的時(shí)間段,標(biāo)記為此駐留點(diǎn).如上例所示,1～2時(shí)間段為A點(diǎn),6～7時(shí)間段也為A點(diǎn),中間的時(shí)間段都為None,則中間的時(shí)間段全部標(biāo)記為A,上面的例子轉(zhuǎn)化為:

A,A,A,A,A,A,A,None,M,B,B,B,None,M,None,B,B,B,None,M,A,None,None,None.

因?yàn)榛緮?shù)據(jù)的特點(diǎn)是,對(duì)于對(duì)象發(fā)生移動(dòng)時(shí),基站更可能去采樣.而對(duì)于長時(shí)間的靜止,基站則不會(huì)去記錄.通過這種方法,來填補(bǔ)記錄的一部分空白.

(4)標(biāo)記時(shí)間屬性

為降低算法的復(fù)雜度,為每個(gè)時(shí)間段標(biāo)記上時(shí)間屬性,把求頻繁序列問題轉(zhuǎn)化為求頻繁組合問題.上面的例子轉(zhuǎn)化為:

0 A,1 A,2 A,3 A,4 A,5 A,6 A,7 None,8 M,9 B,10 B,11 B,12 None,13 M,14 None,15 B,16 B,17 B,18 None,19 M,20 A,21 None,22 None,23 None.

(5)挖掘頻繁時(shí)段和時(shí)長

將每天的記錄按照上述步驟轉(zhuǎn)化為步驟四的樣式,之后對(duì)長期的記錄采用最大頻繁項(xiàng)集挖掘算法就可以得到在駐留點(diǎn)頻繁的駐留時(shí)段和時(shí)長,效果如下所示:

0點(diǎn)～7點(diǎn)A,9點(diǎn)～17點(diǎn)B,20點(diǎn)～24點(diǎn)A

通過挖掘的結(jié)果,我們可以推測A點(diǎn)為此人的居住地,B點(diǎn)為此人的工作地.

分割時(shí)間段挖掘駐留規(guī)律的方法優(yōu)點(diǎn)是簡單,計(jì)算量小.缺點(diǎn)也很明顯,只能挖掘出粗糙的結(jié)果.比如某人每天在8:00～8:10離開家,我們只能得到其在8點(diǎn)到9點(diǎn)發(fā)生了位置變化.而且此方法切割了時(shí)間的連續(xù)性.比如某人每天到家的時(shí)間在18:50～19:20之間,離開家的時(shí)間在8:40～9:10之間,造成同樣的規(guī)律可能被分割成不同的記錄,繼而造成需要降低頻繁項(xiàng)的閾值來挖掘最大頻繁項(xiàng)集.

3.2 密度聚類挖掘駐留規(guī)律

在上一部分中,我們?yōu)榱藢⑦B續(xù)型的時(shí)間變量轉(zhuǎn)化為離散型,采取了分割時(shí)間段的方法,但是效果并不好.為了克服這個(gè)方法的缺點(diǎn),我們提出了密度聚類挖掘駐留規(guī)律的方法.本方法的思路是:首先將離開或到達(dá)駐留點(diǎn)的時(shí)間點(diǎn)進(jìn)行密度聚類.然后將一天的記錄轉(zhuǎn)化為用類名來表示.最后使用最大頻繁項(xiàng)集挖掘算法找到在駐留點(diǎn)頻繁的駐留時(shí)段和時(shí)長.

(1)DBSCAN密度聚類

我們對(duì)離開或到達(dá)一個(gè)駐留點(diǎn)的時(shí)間點(diǎn)進(jìn)行聚類,在聚類方法的選擇中,我們發(fā)現(xiàn)DBSCAN密度聚類更適合解決我們的問題.DBSCAN算法的后的在于過濾低密度的區(qū)域,發(fā)現(xiàn)密度高的區(qū)域.跟傳統(tǒng)的基于層次聚類和劃分聚類的凸形聚類簇不同,該算法可以發(fā)現(xiàn)任意形狀的聚類簇.與傳統(tǒng)的算法相比,它有如下優(yōu)勢能更好的解決我們的問題.

一:聚類簇的形狀沒有偏倚;

二:與K-MEANS比較,不需要輸入要?jiǎng)澐值木垲悅€(gè)數(shù).

我們首先找到所有的離開或到達(dá)駐留點(diǎn)的時(shí)間點(diǎn),其中離開駐留點(diǎn)的時(shí)間點(diǎn)由發(fā)生位置變化后的那個(gè)時(shí)間點(diǎn)來確定,比如A點(diǎn)為駐留點(diǎn),若8:02在A點(diǎn),8:15在B點(diǎn),則離開A點(diǎn)的時(shí)間點(diǎn)為8:15.對(duì)于到達(dá)駐留點(diǎn)的時(shí)間點(diǎn)也由發(fā)生位置變化后的那個(gè)時(shí)間點(diǎn)來確定.比如A點(diǎn)為駐留點(diǎn),20:02在B點(diǎn),20:16在A點(diǎn),則到達(dá)A點(diǎn)的時(shí)間點(diǎn)為20:16.對(duì)離開或到達(dá)駐留點(diǎn)的時(shí)間點(diǎn)進(jìn)行DBSCAN密度聚類后,用類中的最小值和最大值組成的區(qū)間來表示這個(gè)類.比如,對(duì)某人離開A點(diǎn)的時(shí)間點(diǎn)進(jìn)行DBSCAN密度聚類得到的效果為:

類1:7:30,7:35,7:40,7:32,7:45,7:39,8:00,8:02

類2:8:30,8:32,8:35,8:40,8:29,8:42,8:45

那么類1表示為[7:30,8:02],類2表示為[8:29,8:45].

挖掘結(jié)果說明,此人頻繁的在[7:30,8:02]和[8:29,8:45]這兩個(gè)時(shí)間區(qū)間內(nèi)離開A點(diǎn).

(2)時(shí)間點(diǎn)轉(zhuǎn)化為類

我們把一天的記錄轉(zhuǎn)化為用聚類后的類名表示.比如某人有A,B兩個(gè)駐留點(diǎn),對(duì)離開A點(diǎn)的時(shí)間點(diǎn)聚類后分成兩個(gè)類:類1[7:30,8:02],類2[8:29,8:45].對(duì)到達(dá)A點(diǎn)時(shí)間點(diǎn)聚類后分成兩類:類3[19:45,20:10],類4[20:30,20:59].離開或到達(dá)B點(diǎn)的時(shí)間點(diǎn)聚類都為一個(gè)類,分別為類5[17:02:17:30],類6[9:10,9:45].若此人一天的記錄為:7:35離開A點(diǎn),9:10到達(dá)B點(diǎn),17:10離開B點(diǎn),20:35到達(dá)A點(diǎn).那么此人一天的記錄應(yīng)轉(zhuǎn)化為:類1,類6,類5,類4.

(3)挖掘頻繁的駐留時(shí)段和時(shí)長

將每天的記錄用類名表示后,對(duì)長期的記錄采用最大頻繁項(xiàng)集挖掘算法,得到的效果如下所示:

[7:35,8:10]離開A點(diǎn),[9:12,9:25]到達(dá)B點(diǎn),[17:40,18:03]離開B點(diǎn),[20:02,20:34]到達(dá)A點(diǎn).

由此我們可以知道此人在A點(diǎn)頻繁的停留時(shí)間段大約在晚上八點(diǎn)到第二天八點(diǎn)之間,在B點(diǎn)頻繁的停留時(shí)間段為上午九點(diǎn)到下午六點(diǎn).并且可以推測A點(diǎn)為此人的居住地,B點(diǎn)為此人的工作地.

4 實(shí)驗(yàn)分析

后前我們的數(shù)據(jù)為運(yùn)營商基站數(shù)據(jù),因?yàn)樯婕暗奖Ｃ軉栴},不可能通過運(yùn)營商獲得特定某個(gè)人的數(shù)據(jù).為了驗(yàn)證我們提出方法的效果,我們通過GPS數(shù)據(jù)來模擬基站數(shù)據(jù).根據(jù)基站數(shù)據(jù)的特點(diǎn)一,用戶在某個(gè)基站的信號(hào)覆蓋范圍內(nèi)活動(dòng),基站會(huì)定位到同一個(gè)位置點(diǎn),我們將地圖分塊來模擬基站將地圖分塊的效果.我們以緯度跨度0.003為高,經(jīng)度跨度0.0025為寬將地圖分塊,落在某個(gè)塊的采樣點(diǎn),將這個(gè)采樣點(diǎn)定位到這個(gè)塊的中心.通過這種方式,GPS數(shù)據(jù)滿足了基站數(shù)據(jù)的第一個(gè)特點(diǎn).根據(jù)基站數(shù)據(jù)的特點(diǎn)二,采樣時(shí)間間隔長且隨機(jī),我們將一天24小時(shí)分割成半小時(shí)為一個(gè)單位,其中每個(gè)單位內(nèi)隨機(jī)選取一個(gè)采樣點(diǎn).這樣我們一天之內(nèi)可以采樣48個(gè)點(diǎn),且采樣點(diǎn)的時(shí)間間隔隨機(jī)且保持在小于一個(gè)小時(shí)的范圍內(nèi).通過這種方式,GPS數(shù)據(jù)滿足了基站數(shù)據(jù)的第二個(gè)特點(diǎn).

我們征集了十個(gè)志愿者,在他們的手機(jī)上下載GOOGLE開發(fā)的“我的足跡”APP來記載他們每天的軌跡.記錄時(shí)間為2016年11月01號(hào)到2016年12月01號(hào)一個(gè)月的時(shí)間.我們從中選取周一到周五的數(shù)據(jù),經(jīng)過上面介紹的兩項(xiàng)處理之后,將GPS數(shù)據(jù)轉(zhuǎn)變?yōu)榛緮?shù)據(jù).經(jīng)過我們提出的方法處理得到的結(jié)果與志愿者后期自己填寫的規(guī)律性表格來對(duì)比,從而來評(píng)估我們方法的有效性.

4.1 識(shí)別駐留點(diǎn)

我們首先選取其中一個(gè)志愿者的數(shù)據(jù)來具體分析方法的效果.通過簡單的統(tǒng)計(jì)方法來識(shí)別駐留點(diǎn),得到兩個(gè)駐留點(diǎn),其中一個(gè)落在青年公寓所在的方格,一個(gè)落在騰達(dá)大廈所在的方格.經(jīng)過與此志愿者填寫的表格對(duì)比,發(fā)現(xiàn)得到的結(jié)果是正確的.在分別對(duì)這十個(gè)志愿者的數(shù)據(jù)做處理后,得到的正確率為90%,即十個(gè)志愿者的結(jié)果中有九個(gè)是正確的.其中有一個(gè)錯(cuò)誤是因?yàn)榇酥驹刚咴谶@段時(shí)間在外地出差.錯(cuò)誤是由于采樣時(shí)間太短造成的.

4.2 分割時(shí)間段挖掘駐留規(guī)律

為驗(yàn)證分割時(shí)間段挖掘駐留規(guī)律的方法,我們還是首先選取其中一個(gè)志愿者的數(shù)據(jù)來具體分析效果.以一小時(shí)為間隔對(duì)一天的時(shí)間分段.以總記錄個(gè)數(shù)*0.2為最大頻繁項(xiàng)集挖掘算法的閾值,得到最大頻繁項(xiàng)集有四十多條記錄.數(shù)據(jù)量比較大,這是由于時(shí)間間隔設(shè)置帶來的問題.我們限定挖掘出的記錄長度大于等于16,則結(jié)果如下所示:

[‘0 116.34296,39.98840’,‘1 116.34296,39.98840’,

‘2 116.34296,39.98840’,‘3 116.34296,39.98840’,

‘4 116.34296,39.98840’,‘5 116.34296,39.98840’,

‘6 116.34296,39.98840’,‘7 116.34296,39.98840’,

‘9 116.33312,39.94396’,‘10 116.33312,39.94396’,

‘11 116.33312,39.94396’,‘14 116.33312,39.94396’,

‘15 116.33312,39.94396’,‘16 116.33312,39.94396’,

‘17 116.33312,39.94396’,‘19 116.34296,39.98840’,

‘20 116.34296,39.98840’,‘21 116.34296,39.98840’,

‘22 116.34296,39.98840’,‘23 116.34296,39.98840’]

語言表述為:晚上七點(diǎn)到早晨七點(diǎn)在家,九點(diǎn)到達(dá)工作地點(diǎn),到上午十一點(diǎn),午休,下午兩點(diǎn)到五點(diǎn)在工作地點(diǎn),晚上七點(diǎn)到家.

通過這個(gè)實(shí)驗(yàn),我們可以看到這個(gè)方法帶來的問題,挖掘出的頻繁項(xiàng)過多,并且此人大約在七點(diǎn)多到八點(diǎn)多到家,通過這個(gè)方法把一個(gè)規(guī)律割裂成兩種不同的規(guī)律.由于這個(gè)方法存在太多的缺陷,我們不再對(duì)這個(gè)方法的有效性做評(píng)估.

4.3 密度聚類挖掘駐留規(guī)律

我們選取一個(gè)志愿者的數(shù)據(jù),以離開居住地點(diǎn)為例,首先找到所有離開居住地點(diǎn)的時(shí)間點(diǎn),可視化在時(shí)間軸上如圖2(a)所示,使用DBSCAN密度聚類,我們?cè)O(shè)置半徑為5分鐘,最小點(diǎn)數(shù)為10.對(duì)所有離開居住地點(diǎn)的時(shí)間點(diǎn)進(jìn)行密度聚類,聚類效果如圖2(b)所示.

可以得到,離開家的時(shí)間分為兩類,分別為[6:29,7:08]和[7:35,7:48].以同樣的方法對(duì)其他駐留點(diǎn)的離開到達(dá)時(shí)間進(jìn)行密度聚類,將每天的記錄替換為類號(hào),使用最大頻繁項(xiàng)集挖掘算法,最后得到的結(jié)果為:

6:29-7:08 離開居住地點(diǎn) 7:40-8:12到達(dá)工作地點(diǎn)11:18-11:34 離開工作地點(diǎn) 14:02-14:34回到工作地點(diǎn)18:20-19:10 離開工作地點(diǎn) 19:15-19:46 回到居住地點(diǎn)

而此志愿者填寫的規(guī)律性表格為:

6:30-7:00 離開居住地點(diǎn) 7:45-8:00 到達(dá)工作地點(diǎn)11:10-11:30 離開工作地點(diǎn) 14:20-14:40 回到工作地點(diǎn)18:40-19:00 離開工作地點(diǎn) 19:30-19:50 回到居住地點(diǎn).

圖2 志愿者數(shù)據(jù)的聚類分析結(jié)果

我們以挖掘的結(jié)果與表格的結(jié)果重合的時(shí)間段長度除以挖掘結(jié)果的時(shí)間段長度來評(píng)估算法的準(zhǔn)確率.那么此志愿者離開居住地點(diǎn)時(shí)間段的準(zhǔn)確率為重合時(shí)間段長度30 min除以挖掘結(jié)果的時(shí)間段長度39 min,即為77%.其他時(shí)間段的準(zhǔn)確率分別為47%,80%,43%,40%,52%.最后我們?nèi)∷麄兊钠骄鶖?shù)作為最終的準(zhǔn)確率,其結(jié)果為57%.其他九個(gè)志愿者的準(zhǔn)確率分別為34%,60%,45%,43%,33%,55%,38%,41%,52%.

此方法消除了分割時(shí)間段方法的缺點(diǎn),非常詳盡的挖掘出對(duì)象的駐留規(guī)律.

5 結(jié)語

本文首先分析了基站數(shù)據(jù)的特點(diǎn),根據(jù)基站數(shù)據(jù)的特點(diǎn),提出了一種簡單的統(tǒng)計(jì)方法來識(shí)別駐留點(diǎn).然后提出了時(shí)間段分割挖掘駐留規(guī)律的方法,但是這個(gè)方法出現(xiàn)了挖掘的頻繁項(xiàng)太多,割裂時(shí)間連續(xù)性的缺點(diǎn).為了消除這些缺點(diǎn),本文又提出了密度聚類挖掘駐留規(guī)律的方法.最后通過實(shí)驗(yàn)驗(yàn)證,發(fā)現(xiàn)密度聚類的方法能有效詳細(xì)的挖掘出個(gè)人的駐留規(guī)律.

1 Cao HP,Mamoulis N,Cheung DW.Discovery of periodic patterns in spatiotemporal sequences.IEEE Trans.on Knowledge and Data Engineering,2007,19(4):453–467.[doi:10.1109/TKDE.2007.1002]

2 Elgethun K,Fenske RA,Yost MG,et al.Time-location analysis for exposure assessment studies of children using a novel global positioning system instrument.Environmental Health Perspectives,2003,111(1):115–122.

3 Spaccapietra S,Parent C,Damiani ML,et al.A conceptual view on trajectories.Data &Knowledge Engineering,2008,65(1):126–146.

4 Stopher PR.Collecting and processing data from mobile technologies.Proc.of the 8th International Conference on Survey Methods in Transport.Annecy,France.2008.

5 H?gerstrand T.What about people in regional science?Papers of the Regional Science Association,1970,24(1):6–21.[doi:10.1007/BF01936872]

6 Goulias K,Janelle D.GPS tracking and time-geography:Applications for activity modeling and microsimulation.Final Report of an FHWA-sponsored Peer Exchange and CSISS Specialist Meeting.Santa Barbara,CA,USA.2005.

7 Schuessler N,axhausen KW.Processing raw data from global positioning systems without additional information.Transportation Research Record:Journal of the Transportation Research Board,2009,(2105):28–36.[doi:10.3141/2105-04]

8 Stopher PR,Jiang Q,FitzGerald C.Processing GPS data from travel surveys.Proc.of the 2nd International Colloquium on the Behavioural Foundations of Integrated Land-Use and Transportation Models:Frameworks,Models and Applications.Toronto,Canada.2005.

9 Schuessler N,Axhausen KW.Processing raw data from global positioning systems without additional information.Transportation Research Record:Journal of the Transportation Research Board,2009,(2105):28–36.[doi:10.3141/2105-04]

10 張治華.基于GPS軌跡的出行信息提取研究[博士學(xué)位論文].上海:華東師范大學(xué),2010.

11 張用川.基于手機(jī)定位數(shù)據(jù)的用戶出行規(guī)律分析[碩士學(xué)位論文].昆明:昆明理工大學(xué),2013.

Mining the Pattern of Personal Stay Based on the Base-Station Data

QI Shuai,SHAN Gui-Hua,TIAN Dong,LIU Jun
(Computer Network Information Center,Chinese Academy of Sciences,Beijing 100190,China)

With the widespread use of personal mobile communication devices and location-aware devices,the mobile communication service provider has accumulated a lot of its users’ location data.At present,most researches on location data are focused on the mining of active trajectories.A small amount of researches on the pattern of personal stay only determine activity stops,but lack further mining.We conduct researches based on the base station data and propose a simple method to identify the activity stops according to the characteristics of the base station data.Then we propose two methods for mining the pattern of personal stay.Finally,the real data are used to verify the effectiveness of the algorithm.

base-station data;activity stops;density-based clustering;mining algorithm for maximum frequent itemsets

齊帥,單桂華,田東,劉俊.基于基站數(shù)據(jù)挖掘個(gè)人駐留規(guī)律.計(jì)算機(jī)系統(tǒng)應(yīng)用,2017,26(9):176–180.http://www.c-s-a.org.cn/1003-3254/5955.html

① 基金項(xiàng)后:國家自然科學(xué)基金(91530324);國家高技術(shù)研究發(fā)展計(jì)劃(2015AA01A302)

2016-12-28;采用時(shí)間:2017-01-18