張安勤, 田秀霞, 張 挺

(上海電力學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 上海 200090)

基于手機(jī)位置數(shù)據(jù)的個(gè)體行為規(guī)律研究

張安勤, 田秀霞, 張 挺

(上海電力學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 上海 200090)

研究個(gè)體在不同時(shí)間的行為規(guī)律性,以及不同個(gè)體行為之間的相似性,可以為個(gè)性化推薦以及基于位置的服務(wù)提供幫助.從手機(jī)的基站位置數(shù)據(jù)中,通過(guò)聚類方法找到參考位置,并根據(jù)參考位置,將人們雜亂無(wú)章的行為轉(zhuǎn)變?yōu)榈竭_(dá)和離開(kāi)的二進(jìn)制時(shí)間序列.定義二進(jìn)制時(shí)間序列的相似度,利用異或算法檢測(cè)個(gè)體行為模式.在Reality數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明,該方法是有效且可靠的.

手機(jī)數(shù)據(jù); 參考位置; 異或運(yùn)算; 個(gè)體行為模式

每個(gè)人的活動(dòng)就像分子運(yùn)動(dòng),看起來(lái)是雜亂無(wú)序,實(shí)際上存在潛在的模式.對(duì)于很多個(gè)體來(lái)說(shuō),工作日的活動(dòng)就是上班、工作、下班這種循環(huán)往復(fù)的運(yùn)動(dòng)模式,具有很強(qiáng)的規(guī)律性和周期性.但周末時(shí)間,人們可以出游,也可以在家休息,這時(shí)其活動(dòng)模式就具有較強(qiáng)的隨機(jī)性.

隨著帶有定位功能的移動(dòng)設(shè)備和視頻監(jiān)控技術(shù)的廣泛應(yīng)用,產(chǎn)生了大量帶有時(shí)間信息和位置信息標(biāo)記的數(shù)據(jù),如手機(jī)通話數(shù)據(jù)、視頻監(jiān)控?cái)?shù)據(jù)、公交車刷卡數(shù)據(jù)、出租車軌跡數(shù)據(jù)、社交網(wǎng)站簽到數(shù)據(jù)、銀行卡刷卡數(shù)據(jù)等,這就為長(zhǎng)時(shí)間高效地跟蹤個(gè)體移動(dòng)提供了可能[1].機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘技術(shù)的發(fā)展增強(qiáng)了個(gè)體時(shí)空軌跡的直觀顯示和隱含模式的識(shí)別與分析,而個(gè)體行為模式識(shí)別與分析對(duì)城市規(guī)劃、交通規(guī)劃、社區(qū)規(guī)劃、信息與疾病傳播、旅游規(guī)劃和管理等領(lǐng)域的研究具有重要價(jià)值.

隨著智能手機(jī)的普及,手機(jī)與個(gè)人具有很高的耦合性,手機(jī)的使用模式可以在某種程度上反映人的活動(dòng)模式.海量的手機(jī)用戶定位數(shù)據(jù)為人們的行為規(guī)律研究提供了豐富的數(shù)據(jù)源.目前,已經(jīng)有一些學(xué)者開(kāi)始利用手機(jī)數(shù)據(jù)對(duì)個(gè)體的活動(dòng)模式進(jìn)行研究.

文獻(xiàn)[2]給出了個(gè)體行為模式在時(shí)間方面的規(guī)律.通過(guò)統(tǒng)計(jì)居民的通話和活動(dòng)頻率發(fā)現(xiàn),無(wú)論是工作日還是非工作日,居民在一天內(nèi)的行為變化規(guī)律如下:上午9點(diǎn)到11點(diǎn)是活動(dòng)頻繁時(shí)段,中午12點(diǎn)到下午3點(diǎn)活動(dòng)頻繁度減弱,下午4點(diǎn)到6點(diǎn)活動(dòng)又開(kāi)始頻繁,下午6點(diǎn)后活動(dòng)頻繁度慢慢變?nèi)?晚上11點(diǎn)到第2天5點(diǎn)活動(dòng)的頻繁度最弱.

文獻(xiàn)[3]提出,從用戶的通話記錄中可以獲取手機(jī)所用的基站ID.因?yàn)樵诓煌瑫r(shí)刻同一手機(jī)用戶在同一地點(diǎn)可能感應(yīng)到不同的基站,通過(guò)統(tǒng)計(jì)用戶多次在同一地點(diǎn)感應(yīng)到該基站的方法,可以計(jì)算出基站的概率密度,從而對(duì)個(gè)體進(jìn)行定位.然后,基于信息熵對(duì)個(gè)體的活動(dòng)模式進(jìn)行研究,判斷個(gè)體的行為是否具有規(guī)律性.

在文獻(xiàn)[4]中,GONZALEZ M通過(guò)研究10萬(wàn)手機(jī)用戶6個(gè)月的移動(dòng)軌跡來(lái)挖掘個(gè)人活動(dòng)模式.當(dāng)用戶撥通或接聽(tīng)電話,接收或發(fā)送短信時(shí),研究者可以通過(guò)提供該服務(wù)的基站對(duì)用戶的當(dāng)前位置進(jìn)行定位,進(jìn)而得到手機(jī)用戶隨時(shí)間變化的位置軌跡.

對(duì)個(gè)體行為規(guī)律性的研究也有了一些研究成果.SCHLICH R和AXHAUSEN K W[5]分析了300多人6個(gè)星期的出行數(shù)據(jù),研究結(jié)果表明70%的出行以2～4個(gè)地點(diǎn)為目的地.SONG C等人[6]分析了幾個(gè)月的手機(jī)使用數(shù)據(jù),研究顯示人們大多數(shù)時(shí)間在少量的幾個(gè)地方(例如家和工作單位)活動(dòng).盡管這些研究使用了不同類型、不同時(shí)間段的數(shù)據(jù),但結(jié)論卻是相似的,即人們大多數(shù)時(shí)間只訪問(wèn)少量的幾個(gè)地方.

對(duì)個(gè)體活動(dòng)模式的研究也引起了很多復(fù)雜網(wǎng)絡(luò)領(lǐng)域的關(guān)注,主要針對(duì)個(gè)體活動(dòng)模式的幾何度量的統(tǒng)計(jì)分布特征,以及活動(dòng)的時(shí)間和空間分布特征,例如個(gè)體活動(dòng)的步長(zhǎng)分布是否具有重尾特征或冪律分布特征等[7].

1 個(gè)體行為模式檢測(cè)的算法

從短期來(lái)看,個(gè)體的行為是雜亂無(wú)章、毫無(wú)規(guī)律的.但通過(guò)長(zhǎng)時(shí)間的觀察可以發(fā)現(xiàn),個(gè)體的行為具有一定的規(guī)律性,符合一定的行為模式.根據(jù)手機(jī)基站位置數(shù)據(jù),可以發(fā)現(xiàn)個(gè)體在一段時(shí)間內(nèi)的主要行為規(guī)律,判斷個(gè)體的行為是否發(fā)生巨大變化,研究個(gè)體在不同時(shí)間段的行為相似程度及在相同時(shí)間段內(nèi)不同個(gè)體行為的相似程度,從而對(duì)個(gè)體行為進(jìn)行預(yù)測(cè).本文給出了個(gè)體行為參考位置的定義,并提出了發(fā)現(xiàn)參考位置的方法.定義了兩個(gè)二進(jìn)制序列的相似度,并在此基礎(chǔ)上給出了檢測(cè)個(gè)體行為模式的算法.

通過(guò)了解個(gè)體的行為模式,有利于提供基于位置的服務(wù)以及個(gè)性化推薦等,為人們的生活創(chuàng)造更多的便利.本文使用了美國(guó)MIT媒體實(shí)驗(yàn)室研究團(tuán)隊(duì)提供的手機(jī)基站位置數(shù)據(jù)進(jìn)行實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果表明該方法是可行且有效的.

1.1 確定參考位置

人工生成一個(gè)運(yùn)動(dòng)數(shù)據(jù)集模擬一個(gè)人的日常活動(dòng),圖1顯示了此人的移動(dòng)軌跡[8].從圖1可以看出,這個(gè)人的移動(dòng)軌跡是雜亂無(wú)章的,沒(méi)有任何的移動(dòng)規(guī)律.如果以某個(gè)特定的地方作為參考位置,就可以將其行為分為在參考位置和不在參考位置兩類.

圖1 原始移動(dòng)軌跡

圖2是將此人的原始移動(dòng)軌跡轉(zhuǎn)變?yōu)閺膮⒖嘉恢糜^察到的二進(jìn)制軌跡序列.“1”代表在參考位置,“0”代表離開(kāi)參考位置.這個(gè)二進(jìn)制軌跡序列比原始的移動(dòng)軌跡圖更具有規(guī)律性.在將原始軌跡轉(zhuǎn)變成二進(jìn)制序列的過(guò)程中,空間噪聲數(shù)據(jù)就同時(shí)被過(guò)濾掉,原本需要在二維空間中檢測(cè)人的行為模式,就轉(zhuǎn)變?yōu)樵谝痪S空間中進(jìn)行.

假設(shè)D={(x1,y1,t1),(x2,y2,t2),(x3,y3,t3),…}是此人的原始移動(dòng)數(shù)據(jù)集,其中xi和yi分別代表其所在位置的二維坐標(biāo),ti代表某個(gè)時(shí)刻.如果只考慮運(yùn)動(dòng)的空間信息,參考位置就是經(jīng)常到達(dá)的位置.因此,參考位置就是二維原始軌跡圖中包含點(diǎn)密度更大的區(qū)域.按照觀察的粒度要求,將整個(gè)二維空間分成大小一樣的網(wǎng)格,計(jì)算每個(gè)網(wǎng)格的密度.

圖2 從參考位置觀察的二進(jìn)制軌跡序列

輸入:活動(dòng)序列(x1,y1),(x2,y2),(x3,y3),…,(xn,yn)和網(wǎng)格大小L.

輸出:參考位置.

算法步驟如下:

(1) 將整個(gè)二維空間分成大小一樣的網(wǎng)格,每個(gè)網(wǎng)格有一個(gè)計(jì)數(shù)器;

(2) 判斷活動(dòng)序列(x1,y1),(x2,y2),(x3,y3),…,(xn,yn)中的每個(gè)點(diǎn)位于哪個(gè)網(wǎng)格,則相應(yīng)網(wǎng)格的計(jì)數(shù)器增加1;

(3) 計(jì)算所有網(wǎng)格計(jì)數(shù)器的最大值;

(4) 位于計(jì)數(shù)器最大值的網(wǎng)格中的點(diǎn)就是參考位置點(diǎn).

將以上算法記為算法1,圖3中帶有星號(hào)的點(diǎn)就是利用算法1找到的參考位置.

圖3 參考位置

1.2 相似性度量

在二進(jìn)制序列中,只有1和0兩個(gè)符號(hào),因此能夠很方便地度量?jī)蓚€(gè)二進(jìn)制序列的相似性.

對(duì)于同一個(gè)人,如果在不同的時(shí)間段都在參考位置處,那么兩個(gè)二進(jìn)制序列中相應(yīng)的位置值都是1;如果在不同的時(shí)間段都不在參考位置處,那么兩個(gè)二進(jìn)制序列中相應(yīng)的位置值都是0.對(duì)于不同的人,如果他們?cè)谕粫r(shí)間段停留在同一個(gè)參考位置,那么這兩個(gè)二進(jìn)制序列相應(yīng)的位置都是1;如果在同一時(shí)間段不停留在同一個(gè)參考位置,這兩個(gè)二進(jìn)制序列的對(duì)應(yīng)位置都為0.因此,兩個(gè)二進(jìn)制序列的同一位置的相同符號(hào)1或0,可以表示相同的行為模式,兩個(gè)二進(jìn)制序列的同一位置的不同符號(hào)可以表示不同的行為模式.根據(jù)以上事實(shí),可以使用異或運(yùn)算來(lái)決定兩個(gè)二進(jìn)制序列是相同還是不同的符號(hào).

此外,由于1表示在參考位置處,人所處的位置很明確.而0只是表示不在參考位置處,則可以在其他任意地方,所以0對(duì)于研究行為相似性的作用沒(méi)有1大.兩個(gè)二進(jìn)制序列中1的比例之差可以表示相異性.

兩個(gè)二進(jìn)制序列中1的比例之差可以定義為:

(1)

式中:B1,B2——二進(jìn)制序列;n(B1),n(B2)——二進(jìn)制序列B1和B2中1的個(gè)數(shù);

l(B1),l(B2)——二進(jìn)制序列B1和B2的長(zhǎng)度函數(shù).

兩個(gè)二進(jìn)制序列的長(zhǎng)度差別越大,表示兩個(gè)序列越不同,因此長(zhǎng)度差也可以用來(lái)衡量?jī)蓚€(gè)序列的相異性,計(jì)算公式為:

(2)

兩個(gè)二進(jìn)制序列中同一位置不是同為1或0,可以表示兩個(gè)序列的相應(yīng)時(shí)刻不在同一位置,所以不是同為1或0的數(shù)字個(gè)數(shù)可以表示相異性.計(jì)算公式如下:

(3)

因此,總的不相似度可以定義為:

(4)

式中:w1,w2,w3——預(yù)先給定的權(quán)值,w1+w2+w3= 1.

這樣相似度可以定義為:

S=1-ds

(5)

1.3 二進(jìn)制異或算法

許多現(xiàn)象表明,人類在各自的活動(dòng)中經(jīng)常表現(xiàn)出一定程度的規(guī)律性.一個(gè)人可能多次訪問(wèn)一些特定的地方,在不同的時(shí)間段過(guò)著相似的生活.不同的人在相同的時(shí)間段內(nèi),可能有相似的生活規(guī)律,在某種程度上他們可以被視為相似的人.但我們很難從人們的原始活動(dòng)序列中發(fā)現(xiàn)活動(dòng)規(guī)律.

從參考位置的角度來(lái)看,原始的運(yùn)動(dòng)序列可以被轉(zhuǎn)換成一個(gè)二進(jìn)制序B=b1,b2,b3,…,bn,其中bi=1時(shí),表示這個(gè)人在該時(shí)刻在參考位置處,否則bi=0.

使用算法1可以從人的原始活動(dòng)序列中找到參考位置,然后從參考位置的角度將原始序列轉(zhuǎn)變成二進(jìn)制時(shí)間序列,進(jìn)而根據(jù)下列算法從二進(jìn)制時(shí)間序列中挖掘出運(yùn)動(dòng)規(guī)律性.

輸入:多個(gè)人的活動(dòng)序列(x1,y1),(x2,y2),(x3,y3),…,(xn,yn),每個(gè)人的參考位置,和0≤w1≤1,0≤w2≤1,0≤w3≤1.

輸出:一個(gè)人在不同時(shí)間段的相似性和不同人在相同時(shí)間段的相似性.

算法的步驟如下:

(1) 根據(jù)參考位置,每個(gè)人的原始活動(dòng)序列被轉(zhuǎn)變?yōu)槎M(jìn)制序列,二進(jìn)制序列中1代表在參考位置,0代表離開(kāi)參考位置;

(2) 根據(jù)式(1),式(2),式(3)計(jì)算do,dl,dx;

(3) 根據(jù)式(4)計(jì)算兩個(gè)二進(jìn)制序列的不相似度;

(4) 根據(jù)式(5)計(jì)算相似度.

上述對(duì)個(gè)體行為模式的挖掘算法記為算法2.

2 實(shí)驗(yàn)和結(jié)果

為了保證算法的可重復(fù)性,在公共可獲取的Reality Mining 數(shù)據(jù)集[3]上實(shí)現(xiàn)算法.

Reality Mining數(shù)據(jù)集研究的是手機(jī)用戶,它為大量的研究工作提供了基礎(chǔ),而且它是目前研究最多的手機(jī)數(shù)據(jù)集之一.它記錄了97個(gè)MIT媒體實(shí)驗(yàn)室和MIT商業(yè)學(xué)校的學(xué)生和工作人員9個(gè)月的手機(jī)使用數(shù)據(jù).每當(dāng)一個(gè)用戶的手機(jī)服務(wù)基站發(fā)生了改變,為他服務(wù)的基站ID就被記錄下來(lái).數(shù)據(jù)集中的cellspan表的結(jié)構(gòu)包括下面幾個(gè)部分:oid是基站自動(dòng)檢測(cè)到手機(jī)信號(hào)時(shí)的記錄編號(hào),這個(gè)值是自動(dòng)增加值;endtime是自動(dòng)檢測(cè)到手機(jī)信號(hào)的結(jié)束時(shí)間;starttime是自動(dòng)檢測(cè)到手機(jī)信號(hào)的開(kāi)始時(shí)間;person_oid是手機(jī)用戶的編號(hào);celltower_oid是當(dāng)前的基站編號(hào).

本文對(duì)數(shù)據(jù)集的cellspan表中97個(gè)手機(jī)用戶的基站數(shù)據(jù)進(jìn)行實(shí)驗(yàn).

2.1 個(gè)體在不同時(shí)間段的活動(dòng)規(guī)律

以編號(hào)為29的個(gè)體為例,使用Reality Mining數(shù)據(jù)集cellspan表中從2004-07-26到2004-08-26的數(shù)據(jù).首先利用算法1,找到29#個(gè)體經(jīng)常出現(xiàn)的位置,如圖4所示.然后以這個(gè)位置作為參考位置,根據(jù)cellspan表中29#個(gè)體在2004-07-26到2004-08-26這段時(shí)間是否在參考位置,就可以得到一個(gè)二進(jìn)制時(shí)間序列.

圖4 編號(hào)29的個(gè)體所處的基站以及參考位置

根據(jù)算法1找出了參考位置為家和辦公室,即為圖4中帶有星號(hào)標(biāo)識(shí)的部分,這與實(shí)際情況是一致的.

圖5為29#個(gè)體在4個(gè)不同時(shí)間段的活動(dòng)規(guī)律.從圖5可以看出,29#個(gè)體在2004-08-09 到2004-08-15這個(gè)時(shí)間段的活動(dòng)規(guī)律與2004-08-23到2004-08-29是相似的,相似度為0.7.而2004-08-02到2004-08-08這個(gè)時(shí)間段的活動(dòng)規(guī)律與2004-08-16到2004-08-22的差別較大,相似度為0.3.這個(gè)結(jié)果表明,29#個(gè)體在2004-08-02到2004-08-08時(shí)間段的活動(dòng)規(guī)律與其他時(shí)間段相差較大,這個(gè)時(shí)間段可能有些特殊事情發(fā)生.

圖5 29#個(gè)體在4個(gè)不同時(shí)間段的活動(dòng)規(guī)律

2.2 同一時(shí)間段不同個(gè)體的行為規(guī)律

對(duì)97個(gè)不同個(gè)體在相同時(shí)間段進(jìn)行實(shí)驗(yàn),以編號(hào)分別為43,75,94,96的4個(gè)個(gè)體為例.圖6是4個(gè)不同個(gè)體在2004-11-01到2004-11-07一周內(nèi)的實(shí)驗(yàn)結(jié)果.

圖6 4個(gè)不同個(gè)體在同一時(shí)間段的活動(dòng)規(guī)律

從圖6可以看出,94#和96#個(gè)體在相同時(shí)間段(2004-11-01到2004-11-07)有著截然不同的活動(dòng)規(guī)律,利用算法2可以計(jì)算出其相似度為0.08;43#和96#的活動(dòng)規(guī)律比較相似,利用算法2計(jì)算出其相似度為0.65.這個(gè)結(jié)果表明,用算法2能夠得出不同個(gè)體在相同時(shí)間段的活動(dòng)規(guī)律或行為的相似程度.

3 結(jié) 論

(1) 提出了參考位置的概念,并給出了尋找參考位置的方法;

(2) 基于參考位置將個(gè)體原始的雜亂無(wú)章的活動(dòng)軌跡轉(zhuǎn)變成二進(jìn)制時(shí)間序列;

(3) 給出了二進(jìn)制序列的二進(jìn)制異或算法,以及檢測(cè)人們的活動(dòng)規(guī)律和不同人活動(dòng)的相似程度.

[1] LU Y,LIU Y.Pervasive location acquisition technologies:Opportunities and challenges for geospatial studies[J].Computers Environment and Urban Systems,2012,36(2):105-108.

[2] AHAS R,AASA A,SILM S,etal.Daily rhythms of suburban commuters′ movements in the Tallinn metropolitan area:case study with mobile positioning data[J].Transportation Research Part C Emerging Technologies,2010,18(1):45-54.

[3] EAGLE N,PENTLAND A.Reality mining:sensing complex social systems[J].Personal and Ubiquitous Computing,2006,10(4):255-268.

[4] GONZALEZ M,HIDALGO C,BARABASI L A.Understanding individual human mobility patterns[J].Nature 2008,458:779-782.

[5] SCHLICH R,AXHAUSEN K W.Habitual travel behavior:evidence from a six-week travel diary[J].Transportation,2003,30(1):13-36.

[6] SONG C,QU Z,BLUMM N,etal.Limits of predictability in human mobility[J].Science,2010,327:1 018-1 021.

[7] 劉瑜,康朝貴,王法輝.大數(shù)據(jù)驅(qū)動(dòng)的人類移動(dòng)模式和模型研究[J].武漢大學(xué)學(xué)報(bào)(信息科學(xué)版),2014,39(6):660-666.

[8] LI Z,HAN J,JI M,etal.MoveMine:mining moving object data for discovery of animal movement patterns[J].Acm Transactions on Intelligent Systems & Technology,2011,2(4):135-136.

(編輯 白林雪)

ResearchonIndividualBehaviorPatternsBasedonMobileLocationData

ZHANGAnqin,TIANXiuxia,ZHANGTing

(SchoolofComputerScienceandTechnology,ShanghaiUniversityofElectricPower,Shanghai200090,China)

The regularity of the behavior of the same individual at different times and the similarity of different individual behaviors can provide help for personalized recommendation and location-based services.According to the location data of the mobile phone,the reference position is found by the clustering method.And then people′s behavior is transformed into the arrival and departure of the binary time series based on the reference position.The similarity of binary sequences is defined and then individual behavior patterns are detected using XOR algorithm.Experiments on Reality mining data sets show that the proposed method is effective and reliable.

mobile data; view locations; XOR; individual behavior patterns

10.3969/j.issn.1006-4729.2017.04.003

2017-03-09

張安勤(1974-),女,博士,副教授,安徽霍邱人.主要研究方向?yàn)槠者m計(jì)算.E-mail:aqz612@sina.com.

國(guó)家自然科學(xué)基金(61532021);上海市自然科學(xué)基金(16ZR1413200).

TP391.4;TN929.53

A

1006-4729(2017)04-0320-05