劉志,劉輝平,趙大鵬,王曉玲

(華東師范大學(xué)計算機科學(xué)與軟件工程學(xué)院數(shù)據(jù)科學(xué)與工程研究院,上海200062)

基于移動軌跡數(shù)據(jù)的商圈消費者規(guī)模分析

劉志,劉輝平,趙大鵬,王曉玲

(華東師范大學(xué)計算機科學(xué)與軟件工程學(xué)院數(shù)據(jù)科學(xué)與工程研究院,上海200062)

隨著城市化的推進以及大數(shù)據(jù)技術(shù)的不斷發(fā)展,智慧商圈成為智慧城市建設(shè)的重要組成部分.智慧商圈的熱門程度、消費者的規(guī)模、消費層次等因素成為智慧商圈建設(shè)的關(guān)注熱點.然而,傳統(tǒng)的消費者規(guī)模的統(tǒng)計,還是基于傳統(tǒng)的問卷調(diào)查或者抽樣等,這些方法不僅成本昂貴而且效率低下.但隨著數(shù)據(jù)挖掘技術(shù)的發(fā)展,使得通過分析用戶行為軌跡來確定商圈消費者規(guī)模成為可能.本文提出了一種基于軌跡數(shù)據(jù)分析的商圈消費者規(guī)模分析方法.本文的主要工作包括：①在軌跡數(shù)據(jù)中,如何確定商圈的邊界這是一個首要的問題,基于此,才能確定一位消費者是在商圈內(nèi)活動,還是在商圈外面.本文提出了根據(jù)商圈內(nèi)基站點的位置分布,運用k-Nearest Neighbor(k NN)分類算法,對該商圈的范圍進行圈定的方法.②由于軌跡數(shù)據(jù)的不確定性特點,確定一個用戶與商圈的關(guān)系也是一個難題.本文利用計算不規(guī)則多邊形面積的方法計算基站點的權(quán)重值,結(jié)合時間閾值分析該區(qū)域內(nèi)每天的消費者規(guī)模.③最后,鑒于軌跡數(shù)據(jù)的海量性,本文提出了一個大數(shù)據(jù)計算框架BPDA(Business-Circle Parallel Distributed Algorithm),基于Hadoop大數(shù)據(jù)處理平臺和Kafka分布式消息系統(tǒng),實現(xiàn)了基于移動軌跡數(shù)據(jù)的商圈消費者規(guī)模分析系統(tǒng),并使用中山公園商圈基站數(shù)據(jù),展示了本文所提方法的可行性.

移動軌跡數(shù)據(jù);消費者規(guī)模分析;k NN分類算法;商圈輪廓

0 引言

商圈作為城市的消費集中地,是一個城市經(jīng)濟水平高低的重要標(biāo)志.一個商圈經(jīng)營的好壞,往往可以通過商圈的消費者規(guī)模大小來直觀的反應(yīng),商圈的消費者規(guī)模分析對于商圈的經(jīng)濟發(fā)展走勢預(yù)測、商圈的熱門店鋪推薦等工作都具有重要的意義.除此之外,對于商圈自身來講,統(tǒng)計消費人群的規(guī)模,可以準(zhǔn)確的發(fā)現(xiàn)商圈的消費者人數(shù)變化規(guī)律,從而對商圈的規(guī)劃提供更加合理有效的指導(dǎo),促進商圈更加快速、穩(wěn)步地發(fā)展.

商圈的消費者規(guī)模統(tǒng)計方法中,傳統(tǒng)方法是采樣技術(shù)或者問卷調(diào)查等人工方法,這對于商圈的消費者規(guī)模進行大數(shù)據(jù)意義上的統(tǒng)計,是一個難題.此外,還有很多人可能僅僅是路過商圈,并不是來商圈消費,另外還有很多的人是在商圈上班或者居住在附近,這些因素都會對傳統(tǒng)方法的準(zhǔn)確度產(chǎn)生一定的影響.因此,傳統(tǒng)方法不僅調(diào)查范圍為有限,需要耗費大量的資源,而且測定的商圈范圍存在較大的誤差.

近些年,基于時空軌跡數(shù)據(jù)的挖掘技術(shù)不斷產(chǎn)生,通過分析用戶空間移動軌跡來對商圈消費者流量進行統(tǒng)計成為了研究商圈消費者規(guī)模分析的一種新的方法.同時,這種研究方法也存在諸多挑戰(zhàn).

(1)商圈范圍不確定性.商圈是一個集消費、娛樂、購物等為一體的多功能區(qū)域,多分布于商業(yè)活動頻繁度高、人口密度大、面向客流量多、交通便利的街道,沒有明確的邊界范圍劃分.

(2)軌跡數(shù)據(jù)模糊性.用戶在確定的時間點連接某商圈基站,只能說明用戶在該時間處于該基站的覆蓋范圍內(nèi),并不能獲知用戶準(zhǔn)確位置,因而不能準(zhǔn)確的判斷用戶與商圈的位置關(guān)系.特殊的,存在信號“跳變”現(xiàn)象,即用戶在短時間段內(nèi)與多個基站連接信號頻繁切換,這就更加導(dǎo)致了用戶移動準(zhǔn)確位置難以確定.

(3)軌跡數(shù)據(jù)海量性.隨著硬件技術(shù)的提高和完善,越來越多的移動智能設(shè)備得到普及使用.如此大量的移動智能設(shè)備每天會產(chǎn)生大量的時空移動軌跡數(shù)據(jù).據(jù)2008年的N ature?？痛髷?shù)據(jù)提出問題,“人類已經(jīng)進入了海量存儲PB時代,并預(yù)測下一個IT巨頭的主營業(yè)務(wù)將會是大數(shù)據(jù)管理”.

本文針對于上述商圈消費者規(guī)模分析的挑戰(zhàn),提出了新的解決方案.該方案包括兩個部分:商圈邊界劃分模塊和商圈消費者規(guī)模統(tǒng)計分析模塊.提出了新的商圈范圍圈定算法以及基于規(guī)則的大數(shù)據(jù)計算框架BPDA來對商圈消費者規(guī)模進行統(tǒng)計分析.

本文主要貢獻在以下幾個方面.

(1)基于商圈基站的位置分布,采用k NN分類算法并結(jié)合輪廓優(yōu)化算法對商圈的范圍進行圈定,確保生成的商圈輪廓更加清晰.

(2)針對軌跡數(shù)據(jù)模糊性問題,提出通過計算不規(guī)則多邊形面積的方法來依次計算基站點的權(quán)重值,并且結(jié)合不同的時間閾值以及軌跡判定規(guī)則來對用戶的行為軌跡進行建模分析,從而對商圈消費者規(guī)模進行統(tǒng)計.

(3)基于大數(shù)據(jù)統(tǒng)計分析平臺Hadoop以及消息流收集系統(tǒng)Apache Kafka(簡稱Kafka),提出了一種高效的分布式大數(shù)據(jù)計算框架BPDA來對商圈消費者規(guī)模進行統(tǒng)計分析,克服了傳統(tǒng)方法的成本昂貴、效率低下以及誤差大的缺點,并且以中山公園商圈為例,對算法的有效性以及可行性進行了準(zhǔn)確分析.

本文剩余部分的組織結(jié)構(gòu)如下:第1節(jié)描述相關(guān)工作;第2節(jié)介紹本文的商圈、基站、移動軌跡等概念以及研究的問題定義;第3節(jié)簡要介紹商圈邊界劃分模塊和商圈消費者規(guī)模統(tǒng)計分析模塊;第4節(jié)詳細介紹商圈邊界劃分模塊;第5節(jié)詳細介紹商圈消費者規(guī)模統(tǒng)計分析模塊;第6節(jié)報告實驗結(jié)果;第7節(jié)總結(jié)全文.

1 相關(guān)工作

目前,與商圈消費者規(guī)模統(tǒng)計分析研究相關(guān)的是城市功能化模塊劃分以及動態(tài)時空數(shù)據(jù)聚/分類兩大領(lǐng)域.

關(guān)于功能化模塊劃分這一領(lǐng)域,已經(jīng)有了很好的研究.文獻[1]中提到基于人們的移動軌跡數(shù)據(jù)及POI數(shù)據(jù),利用TF-IDF向量對城市的功能區(qū)進行了不同的劃分,分為居住區(qū),商業(yè)區(qū),教育區(qū)等.文獻[2]利用CPF向量以及新的topic模型對功能區(qū)進行了更準(zhǔn)確的劃分.文獻[3]基于出租車上下車記錄以及行駛軌跡數(shù)據(jù),采用簡單的分類算法,來對城市主功能區(qū)和非主功能區(qū)進行分類.文獻[4]通過對倫敦市出租車的行駛軌跡數(shù)據(jù)分析,挖掘出租車的運動模式,來劃分倫敦市的主要購物街道.文獻[5]對比不同的機器學(xué)習(xí)方法,例如簡單邏輯回歸、決策樹模型、貝葉斯分類器等,對城區(qū)地表覆蓋物的圖片進行了分類,根據(jù)分類結(jié)果分類不同的城市功能區(qū).文獻[6]中詳細的介紹了城市功能區(qū)域的概念,并且給出了城市功能區(qū)劃分的依據(jù).文獻[7]從cluster角度上介紹了城市功能區(qū)的特點、聚類方法、以及聚類的策略.

關(guān)于動態(tài)時空數(shù)據(jù)聚/分類方面目前也有比較成熟的研究.在時空數(shù)據(jù)聚類方面,文獻[8]提出了基于密度的聚類算法ST-DBSCAN用于空間移動軌跡數(shù)據(jù)聚類分析,可以屏蔽噪音點,自動將中心點和邊緣點聚成一個完整的簇.文獻[9]提出了four-step時空數(shù)據(jù)聚類算法,自動去除數(shù)據(jù)中的噪音以及補齊缺失數(shù)據(jù).文獻[10]基于聚類方法DBSCAN提出了新的方法STDBSCAN對空間時空軌跡進行聚類,用于發(fā)掘潛在的POI.文獻[11]提出了single-link的時空數(shù)據(jù)聚類算法,該方法是譜系聚類圖的一種,可以方便的轉(zhuǎn)換為樹圖來分析參數(shù)相似性問題.在時空數(shù)據(jù)分類方面,文獻[12]提出了一種懶惰學(xué)習(xí)模型ML-k NN來解決文本分類問題.文獻[13]將SVM和k NN模型結(jié)合到一起提出了混合模型SVM-k NN來降低可視化分類識別領(lǐng)域的計算復(fù)雜性,并提高了分類結(jié)果的準(zhǔn)確性.文獻[14]提出了GA-k NN分類算法,并優(yōu)化算法的參數(shù)來成功解決基因分類問題.

然而,以上基于用戶移動軌跡數(shù)據(jù)的城市功能區(qū)劃分以及時空數(shù)據(jù)聚類方面的研究都是基于用戶準(zhǔn)確的GPS(Global Position System)坐標(biāo)位置或者準(zhǔn)確的上下車刷卡記錄,針對存在位置模糊性的時空軌跡數(shù)據(jù)而言,以上方法都不適用.本文中研究的是用戶與基站連接的空間移動軌跡數(shù)據(jù),不能準(zhǔn)確的定位用戶的實時位置,借鑒了以上工作研究方法,文中提出了有效的大數(shù)據(jù)計算框架BPDA,對商圈輪廓范圍進行了圈定,并且對商圈的消費者規(guī)模進行了統(tǒng)計和分析.

2 問題定義

問題描述:給定商圈基站點的集合以及用戶的移動軌跡數(shù)據(jù),對商圈范圍進行圈定以及對商圈的消費者規(guī)模進行統(tǒng)計和分析.

定義1基站:一個基站sta(id,loc)是移動用戶通信的節(jié)點,其中id表示該基站的標(biāo)識, loc表示該基站的實際地理位置,通常用經(jīng)緯度表示.如(C1270,(121.247 82,31.392 36))表示基站C1270位于東經(jīng)121.247 82°,北緯31.392 36°位置.如圖1(a),存在3個基站點.

基站有宏站和微站之分,宏站的信號覆蓋范圍比較大,大約為2.5 km,而微站的信號覆蓋范圍比較小,大約為500 m.

多個分散的基站交錯構(gòu)成了基站覆蓋區(qū)域,將覆蓋區(qū)域的邊緣位置基站相互連接形成的一個多邊形區(qū)域稱為商圈.

定義2移動軌跡:一個移動軌跡Tr是指一系列的有時間標(biāo)記的基站數(shù)據(jù),Tr: p1→p2→p3→···→pn,其中pi表示有時間標(biāo)記的移動軌跡點,pi=(sta,t).如((C1270, (121.247 82,31.392 36)),20130519134542)表示在時間點20130519134542該用戶連接基站C1270.如圖1(b),13#13:16:47～18#17:33:36存在往返軌跡1和軌跡2.

此外,存在不規(guī)則的用戶軌跡—–“跳變”,即一個用戶在短時間內(nèi)與多個基站連接信號頻繁切換的現(xiàn)象,這種情況下,不能明確地看出用戶的移動軌跡,而是構(gòu)成一個局部的環(huán)路.如圖1(c),用戶在2#16:58:50～18#19:21:18時間內(nèi)不停地在基站a和基站b之間進行信號切換.

定義3商圈覆蓋點集合:用于覆蓋商圈范圍的標(biāo)示點組成的最小矩形,該矩形覆蓋點用于確定商圈的范圍.如圖1(d).

定義4商圈消費者規(guī)模:特意來商圈消費的消費者規(guī)模數(shù)量的統(tǒng)計,不包括工作或者居住在商圈附近以及路過商圈的人群.

圖1 示例圖Fig.1 Sample

3 模塊介紹

為了解決上述問題,本文首先基于基站數(shù)據(jù)集對商圈的范圍進行劃分,然后利用計算多邊形面積的方法計算各基站的權(quán)重值,最后基于基站點的權(quán)重值以及用戶移動軌跡判定規(guī)則來統(tǒng)計用戶在商圈內(nèi)的停留時間,根據(jù)停留時間統(tǒng)計出不同時間段的商圈內(nèi)的消費者規(guī)模大小.

本文涉及商圈邊界劃分和商圈消費者規(guī)模統(tǒng)計分析兩大模塊.商圈邊界劃分模塊又包括商圈網(wǎng)格化覆蓋和商圈輪廓劃分,商圈消費者規(guī)模統(tǒng)計分析模塊包括權(quán)重計算和消費者規(guī)模統(tǒng)計.具體功能模塊流程圖如圖2.

圖2 功能模塊流程圖Fig.2 Function module process

商圈網(wǎng)格化覆蓋:用于校驗人工標(biāo)注的商圈基站點的完整性以及生成覆蓋商圈范圍的矩形區(qū)域覆蓋點.

商圈輪廓劃分:用于生成商圈的輪廓以及對輪廓的優(yōu)化.

權(quán)重計算:通過計算多邊形面積來計算商圈基站點的權(quán)重值.

消費者規(guī)模統(tǒng)計:利用大數(shù)據(jù)計算框架BPDA結(jié)合不同軌跡模式判定規(guī)則來對商圈消費者規(guī)模進行統(tǒng)計分析.

本節(jié)簡要介紹文章中要做的工作是商圈輪廓的劃分(即商圈識別)以及商圈中有效消費者規(guī)模的統(tǒng)計,在接下來的章節(jié)中將會詳細介紹如何通過算法和大數(shù)據(jù)統(tǒng)計分析工具來對這兩部分進行實現(xiàn).

4 商圈邊界確定

本節(jié)先描述商圈基站點的預(yù)處理以及商圈最小矩形覆蓋點的生成,再介紹如何利用KNN分類算法對商圈覆蓋點進行分類以確定商圈的輪廓范圍.

4.1 商圈最小矩形覆蓋

對存在Kafka上的基站數(shù)據(jù),通過消息拉取的方式將消息從Kafka中取出并保存在HDFS中,利用數(shù)據(jù)倉庫處理工具Hive篩選出所有上海市的基站點,保留每個基站點ID,經(jīng)、緯度坐標(biāo)以及基站的類別(宏、微站)字段.由于人工標(biāo)注過的商圈基站點集合可能沒有完全包括所有的商圈基站點或者存在非商圈基站點,為了能夠更加清晰地劃分出商圈輪廓,需要利用百度地圖API對人工標(biāo)注的商圈基站點進行打點校驗,并對未能標(biāo)注出的基站點進行補充.如圖3所示,紅色點為某通信運營商標(biāo)注的商圈基站點,藍色點為所有的基站點(商圈基站點和非商圈基站點).

圖3 人工標(biāo)注的商圈基站點圖Fig.3 Business circle base station

對于已修正過的商圈基站點集合,分別計算出基站點的最大經(jīng)度lngmax、最小經(jīng)度lngmin、最大緯度latmax、最小緯度latmin,然后根據(jù)經(jīng)緯度的范圍確定一個可以覆蓋所有基站的最小矩形,經(jīng)度坐標(biāo)范圍為(lngmax,lngmin),緯度坐標(biāo)范圍為(latmax,latmin).需要設(shè)置矩形內(nèi)部的分辨率m×n,即對該矩形經(jīng)度坐標(biāo)進行m次等分,緯度進行n次等分,分別生成m×n個坐標(biāo)點,即m×n個商圈覆蓋點.

關(guān)于矩形分辨率中m和n的取值,m和n越大,商圈識別算法要處理的點數(shù)越多,耗時越長,但是得到的商圈輪廓更加清晰自然.因此考慮到算法耗時問題,實驗中m和n值的選擇只要大小合適、商圈輪廓清晰自然便可.

4.2 商圈識別

本節(jié)中,首先使用k NN[15]即k最近鄰分類對商圈最小矩陣覆蓋點進行分類,從而確定粗略的商圈邊界.具體做法是基于商圈基站點和非商圈基站點這兩種類別對第4.1節(jié)中整個商圈覆蓋點集合進行二分類,得到商圈輪廓的覆蓋點集合和非商圈輪廓的覆蓋點集合.因為所要計算得到的是輪廓邊界,不是完整區(qū)域,因此k NN分類器k值設(shè)置為3,即與一覆蓋點最相鄰的3個基站點(Top3)中,滿足count商圈＞count非商圈,且Top2中count商圈=1, count非商圈=1,該覆蓋點保留.

商圈識別算法如算法1所示,其中,序號1至序號4確定商圈經(jīng)緯度范圍;序號5至序號9生成最小矩陣覆蓋點;序號10至序號11依次計算m×n個覆蓋點與所有基站點(包括商圈基站以及非商圈基站)之間的歐式距離di;序號12對距離值di進行升序排序;序號13至序號16取集合Di前3個即d1,d2,d3對應(yīng)的3個基站點進行判斷,如果這3個基站點當(dāng)中count商圈＞count非商圈,且d1,d2對應(yīng)的基站點滿足count商圈=1,count非商圈=1,保留該覆蓋點,否則,刪除.

算法1 商圈識別算法

對于算法1,由于需要對所有的商圈覆蓋點與每個基站點進行歐式距離計算,然后根據(jù)距離進行快速排序,并且只排序至最小的k個元素(Top k)就停止排序.由于快速排序的最優(yōu)時間復(fù)雜度為O(n log2n),最壞時間復(fù)雜度為O(n2),所以時間復(fù)雜度為O(m×n+(m×n)2),其中m為商圈覆蓋點數(shù),n為商圈基站數(shù).

從算法1中可以看到商圈識別算法利用了k NN分類器對商圈覆蓋點進行分類,保留位于商圈基站和非商圈基站之間的覆蓋點,并且最終通過閾值τ的判斷只保留位于接近兩類基站點連線的中間位置的商圈覆蓋點,這樣做的好處是使得生成的商圈輪廓貫穿兩類基站點的中間位置.

然而對于算法1得到的商圈輪廓點通過調(diào)用百度API打點之后會發(fā)現(xiàn)存在覆蓋點堆積的問題,即在小范圍內(nèi)存在多個點的經(jīng)度或者緯度相同的情況,多個覆蓋點聚集在一起,使得商圈的輪廓變得不均勻.因此,需要刪除冗余的覆蓋點,對商圈輪廓進行進一步優(yōu)化,使其更加規(guī)整自然,優(yōu)化過程如算法2所示,其中序號1選取k NN分類算法所得到的覆蓋點集中任意一個覆蓋點為初始點a;序號2至序號9找到與該初始點a之間距離小于閾值τ2的另一覆蓋點b,如果存在多點情況下,可任選其中一個覆蓋點;序號10至序號14重新以覆蓋點b為初始點,繼續(xù)循環(huán)以上操作,直到找到的下一覆蓋點為最開始的初始點a為止.

算法2 商圈輪廓優(yōu)化算法

算法2需要對算法1的結(jié)果集進行遍歷,對于每個覆蓋點ai,分別計算該覆蓋點與結(jié)果集中的其他覆蓋點的歐式距離di,直到找到任何一個歐式距離di小于閾值τ2的覆蓋點dj為止.結(jié)果集中刪除di,然后以覆蓋點dj為新的起點,進行下一輪迭代查詢.如果每輪迭代結(jié)果集第一個元素就滿足與起點ai的歐氏距離小于τ2,那么最優(yōu)時間復(fù)雜度為O(n);如果是結(jié)果集的最后一個元素,最壞時間復(fù)雜度為O(n2).因此,算法2的時間復(fù)雜度為O(n2).

5 商圈消費者規(guī)模統(tǒng)計

本節(jié)首先計算出每個基站點的權(quán)重值,然后結(jié)合基站點的權(quán)重以及用戶移動軌跡判定規(guī)則來確定商圈消費者規(guī)模.

不同基站有不同權(quán)重值可以很好地解決軌跡數(shù)據(jù)位置模糊性問題.根據(jù)用戶與商圈基站連接時間與基站點的權(quán)重值的乘積來計算用戶軌跡在商圈的停留總時間,結(jié)合用戶軌跡模式判定規(guī)則來進行商圈內(nèi)有效消費者規(guī)模統(tǒng)計.

5.1 基站權(quán)重值計算

由于商圈的基站有一定的覆蓋范圍,因此僅僅通過用戶軌跡數(shù)據(jù)無法有效地定位用戶的地理位置.另外,由于基站的覆蓋范圍存在一定的交叉重疊,導(dǎo)致存在信號“跳變”的情況,所以僅僅通過用戶與商圈基站的連接時長這一個維度來進行商圈消費者規(guī)模統(tǒng)計是不足的,需要加入另一個維度—–商圈基站的權(quán)重值.

對于任意基站點stai,其權(quán)重值等于該基站點覆蓋范圍和商圈的重疊面積與基站點覆蓋面積的比值,計算公式為

其中,A重疊代表基站點覆蓋范圍和商圈的重疊面積,S代表基站點覆蓋面積.

由于商圈輪廓是不規(guī)則的多邊形,計算基站stai覆蓋范圍與商圈的重疊面積比較復(fù)雜,所以采用隨機拋灑樣本點的方式,在基站覆蓋范圍圓內(nèi)拋灑若干樣本點,統(tǒng)計在商圈范圍內(nèi)的樣本點數(shù)目占所有樣本點的比例并作為基站stai的權(quán)重值大小.計算基站權(quán)重值步驟如算法3所示,其中,序號1至序號9遍歷所有商圈基站,如果為宏站,則以該基站點為圓點,以宏站最大信號覆蓋范圍r1=2 500 m為半徑建立覆蓋圓,在圓內(nèi)隨機生成m個隨機點,計算落入商圈輪廓范圍內(nèi)的隨機點數(shù)目與m的比值;序號10至序號17基站點為微站,則以微站最大信號覆蓋范圍r2=500 m為半徑建立覆蓋圓,其他步驟同上.

算法3 計算基站權(quán)重值算法

對于算法3,需要對商圈基站點集合S5進行遍歷,以Si為圓心,r為半徑建立覆蓋范圍圓,在圓中隨機生成m個點,統(tǒng)計位于商圈范圍內(nèi)的基站點數(shù).因此,該算法的時間復(fù)雜度為O(m×n),n為商圈基站點數(shù),m為每次隨機生成的樣本點數(shù).

5.2商圈消費者規(guī)模統(tǒng)計

該模塊利用Kafka、Hadoop[16]大數(shù)據(jù)平臺,提出基于MapReduce的計算框架BPDA.整體算法思想:首先通過文獻[17]所提出的工作地和居住地挖掘方法,在統(tǒng)計過程中去除工作或居住在商圈附近這部分用戶;然后基于用戶軌跡來統(tǒng)計用戶與各個商圈基站點的連接時間ti,乘以相應(yīng)基站點的權(quán)重值wi,求和,得到用戶在商圈內(nèi)停留總時間∑若停留時間超過閾值§,則認為用戶在該時間段來商圈消費.數(shù)據(jù)處理流程圖如圖4.

圖4 用戶軌跡數(shù)據(jù)處理流程圖Fig.4 Trajectory data processing

由于用戶移動軌跡中存在“跳變”現(xiàn)象,即用戶信號在不同的基站之間形成了局部的“環(huán)”.根據(jù)“環(huán)”中基站點與商圈的不同位置關(guān)系,做不同的處理規(guī)則,具體如下.

(1)用戶與多個商圈基站點連接.分別統(tǒng)計用戶與各個基站點連接時間乘以權(quán)重值,然后求和.

(2)用戶短時間內(nèi)頻繁在商圈基站和非商圈基站進行信號切換.分別統(tǒng)計用戶與商圈基站和非商圈基站的連接時間,如果用戶與商圈基站連接時間明顯大于非商圈基站連接時間,則將與非商圈基站連接時間歸為商圈基站的時間來統(tǒng)計;反之,則認為該用戶未在商圈停留,只是簡單的基站信號跳變.

(3)用戶與商圈基站和非商圈基站切換連接,且每次切換連接時間較長.如果與商圈基站和非商圈基站的連接時間差超過1 h,則認為用戶在與商圈基站的最后一個連接時間點離開了商圈,與非商圈基站的連接時間不計入統(tǒng)計;否則,則認為是信號跳變,計入統(tǒng)計.

軌跡判定規(guī)則流程圖如圖5所示.

基于以上的規(guī)則,利用大數(shù)據(jù)計算框架BPDA對商圈消費者規(guī)模進行統(tǒng)計.BPDA算法需要運行3輪MapReduce計算模型:第一輪是對所有用戶的移動軌跡數(shù)據(jù)按照每個用戶手機號碼進行分組處理,得到每個用戶按照時間排序的有序移動軌跡數(shù)據(jù)集;第二輪是對第一輪的結(jié)果數(shù)據(jù)集進行處理,結(jié)合軌跡判定規(guī)則和商圈基站的權(quán)重值來計算每個用戶在商圈的停留時間,將該停留時間按照1 h為步長劃分成多個時間段,從而得到各個日期不同時間段商圈的消費者規(guī)模數(shù)據(jù)集;第三輪是對第二輪的不同時刻商圈消費者規(guī)模數(shù)據(jù)集按照日期進行分組處理,對每個分組內(nèi)的24個時間段進行排序,結(jié)合MapReduce模型本身的內(nèi)部排序特點對日期進行排序,得到日期和時間段均有序的商圈消費者規(guī)模數(shù)據(jù)集.整個BPDA計算框架處理步驟如圖6.

BPDA計算框架第二輪詳細處理過程如算法4所示,其中,序號1至序號9用于判斷一條軌跡記錄的基站stai是否是商圈基站,如果是,保存該基站點,并且對該基站點的連接時長乘以基站權(quán)重值進行累加;序號10至序號19判斷基站stai不是商圈基站,需要判定前一條記錄的基站staraserved是否為商圈基站,如果不是,不作處理,如果是,則需要對基站staraserved的連接時長與時間閾值§1進行判定,小于時間閾值§1,則累加連接時長.否則,不作處理;序號20至序號26對用戶與商圈基站的連接時長(tbegin,tend,?ttotal)與閾值§2進行判定,對時間長度tbegin到tend基于1 h為單位進行拆分,分成〈ti,1〉作為Map部分的輸出;序號31至序號32對輸入〈ti,[1,1,1,···]〉按照時間點ti進行聚合成〈ti,numi〉.

圖5 用戶軌跡判定規(guī)則流程圖Fig.5 Trajectory decision rules

圖6 BPDA整體處理流程圖Fig.6 BPDA processing flow

算法4 商圈消費者規(guī)模統(tǒng)計算法

6 實驗

這一節(jié)給出具體實驗.實驗是以中山公園商圈為例,對該商圈的輪廓進行圈定,計算商圈基站的權(quán)重值以及對該商圈消費者規(guī)模進行統(tǒng)計與分析.

6.1 實驗數(shù)據(jù)

實驗數(shù)據(jù):本文使用上海某通訊運營商提供的用戶連接基站OIDD數(shù)據(jù)以及商圈基站點數(shù)據(jù).這些數(shù)據(jù)包括3 200 000名用戶從2014年8月15日至2015年3月1日(共208 d)期間用戶連接基站OIDD數(shù)據(jù),數(shù)據(jù)源大小約為1.6 TB,以及238個用戶標(biāo)注的商圈基站點.具體數(shù)據(jù)格式如下.

此外,本文還隨機選取了96名志愿者的移動軌跡數(shù)據(jù)對BPDA計算框架的準(zhǔn)確性和精確度進行驗證.志愿者每月平均商圈消費次數(shù)分布情況和志愿者每月平均經(jīng)過商圈次數(shù)分布情況如表1和表2所示.

表1 志愿者商圈消費次數(shù)分布Tab.1 Business consumption time distribution

表2 志愿者經(jīng)過商圈次數(shù)分布Tab.2 Business passing time distribution

6.2 實驗環(huán)境及相關(guān)設(shè)置

本實驗采用的是40個節(jié)點的Hadoop集群,每個節(jié)點運行的操作系統(tǒng)為RedHat Linux version 6.7,處理器為Intel(R)Xeon(R)CPU E5620,主頻為2.40 GHZ,軟件版本為Hadoop2.6.

對于商圈輪廓識別模塊,設(shè)置商圈識別算法的閾值τ為30,商圈輪廓優(yōu)化算法的閾值τ2為15.對于消費者規(guī)模統(tǒng)計模塊,通過多次實驗分別計算用戶離開商圈的閾值§1以及商圈的停留時間閾值§2所對應(yīng)的F1-score,最終設(shè)置§1為30 min,§2為60 min.

6.3 閾值確定

在判定用戶來商圈消費的規(guī)則當(dāng)中,對商圈停留時間閾值的選取做了如下計算.采樣1 000個用戶在30 d里的不同用戶移動軌跡數(shù)據(jù),通過人工標(biāo)注的方式得到有581 d存在用戶來商圈消費行為,以10 min為步長,遞增時間閾值,進行多組實驗,然后分別計算每組實驗的Recall和Precision值;再通過公式來計算F1-score,公式為

其中,i代表停留時長,Pi代表i停留時長的準(zhǔn)確率,Ri代表i停留時長的召回率,Tp代表計算出來的真實商圈消費行為,Fp代表錯誤商圈消費行為,Fn代表未計算出來的真實商圈消費行為.

通過實驗分析可以得出,當(dāng)時間閾值§2選擇為接近60 min的時候,如圖7中的紅色三角形位置,F1-score為最高值0.859.

(1)圖8是商圈識別算法的性能示意圖,該算法的時間復(fù)雜度為O(m×n+n2),m為基站數(shù),n為商圈覆蓋點數(shù),k為k NN分類器參數(shù).圖中對比了k NN算法k分別值為3,5,7的時候,不同分辨率(即不同數(shù)目的商圈覆蓋點)對應(yīng)的時間性能.從圖中可以看出,隨著k值的增大,由于算法要判斷的排序之后的Top k的個數(shù)增加,算法耗時也相應(yīng)增大.例如,當(dāng)分辨率為100×100的時候,k=3的耗時為1.974 s,k=7的耗時為2.441 s.同時,也可以看出,對于同一個k值而言,隨著分辨率成倍增長,算法的耗時以二次方增長.例如,對于k=3,當(dāng)分辨率為100×100時,時耗為1.974 s,當(dāng)分辨率為1 000×1 000時,耗時為191.15 s,分辨率增長10倍,耗時也增長接近100倍.

圖7 F1-score隨時間閾值變化圖Fig.7 F1-score threshold value

6.4 算法性能分析

圖8 商圈識別算法時間代價Fig.8 Business recognition time complexity

(2)圖9是商圈輪廓優(yōu)化算法的性能示意圖,該算法時間復(fù)雜度為O(n2),n為商圈識別算法所保留的商圈覆蓋點.從圖中可以看出,隨著分辨率的增加,算法耗時也接近線性增長.圖中舉例k=3的時候,當(dāng)分辨率為1 000×1 000,算法處理時間為40 s,算法性能比較好.

圖9 商圈輪廓優(yōu)化算法時間代價Fig.9 Business optimizing time complexity

(3)表3是時間閾值§1和§2分別為不同值時BPDA計算框架的準(zhǔn)確度、召回率以及F1-score的變化情況.隨著閾值§1的增大,更多用戶在商圈外部邊緣的停留時間被計入統(tǒng)計,從而可能導(dǎo)致更多經(jīng)過商圈的移動軌跡無效記錄被計入統(tǒng)計,進而導(dǎo)致統(tǒng)計的準(zhǔn)確率降低,同時也會使得小于停留時間閾值§2的有效移動軌跡記錄納入統(tǒng)計,從而召回率增大;隨著閾值§2的增大,更多經(jīng)過商圈小于時間閾值的無效記錄被刪除,保留更多在商圈停留時間大于時間閾值的有效記錄,因此統(tǒng)計的準(zhǔn)確率會增大,同時會有小于停留時間閾值§2的有效移動軌跡記錄沒有計入統(tǒng)計,從而導(dǎo)致召回率下降.由圖8中紅色記錄可以看出當(dāng)§1為1 800 s、§2為3 600 s時, F1-score為最高值0.859.

表3 BPDA算法性能統(tǒng)計Tab.3 BPDA performance

(4)表4所示是BPDA計算框架與其他文獻中的消費者規(guī)模統(tǒng)計算法的性能對比.文獻[18]和文獻[19]是利用數(shù)據(jù)庫存儲過程來計算分析用戶移動軌跡數(shù)據(jù)進而統(tǒng)計指定區(qū)域的消費者規(guī)模,沒有特意考慮排除對商圈工作人員、居住和工作在商圈附近以及路過商圈的人的統(tǒng)計.此外,沒有充分考慮用戶移動軌跡信號“跳變”的問題,因而沒有結(jié)合不同的軌跡判定規(guī)則以及時間閾值對商圈消費者規(guī)模進行分類分析統(tǒng)計,準(zhǔn)確率以及召回率比較低;文獻[20]是通過統(tǒng)計監(jiān)控視頻中行人的數(shù)量來對商圈消費者規(guī)模進行統(tǒng)計,能夠準(zhǔn)確判定用戶的存在,因而準(zhǔn)確率和召回率都比較高,但是該種方法在適用范圍上具有局限性,且投入成比較大.

(5)圖10是BPDA計框架基于不同商圈停留時間閾值以及不同集群計算節(jié)點的運算時間圖.可以看出,隨著計算節(jié)點數(shù)的成倍增加,框架整體運算時間大幅度減少,計算節(jié)點數(shù)由10變?yōu)?0時候,運算時間接近成倍減少,計算節(jié)點繼續(xù)增加,框架運算時間減少幅度變小;從對比時間閾值為600 s的黑線和3600 s的藍線可以看出,相同數(shù)目的計算節(jié)點對應(yīng)的計算時間相差較大,可以得出真實用戶移動軌跡中存在大量的短時間商圈停留,即用戶經(jīng)過商圈的記錄.

表4 BPDA算法性能對比Tab.4 BPDA performance contrast

圖10 BPDA算法運行效率示意圖Fig.10 BPDA time cost

6.5 實驗結(jié)果分析

(1)圖11是中山公園商圈輪廓.圖11(a)是商圈矩形覆蓋點示意圖;圖11(b)是k NN分類器分類之后的商圈輪廓,可以看出該輪廓中黑線標(biāo)注的部分存在明顯的覆蓋點堆積的現(xiàn)象;圖11(c)是利用輪廓優(yōu)化算法優(yōu)化過的商圈輪廓,可以看出圖中的商圈輪廓更加清晰自然.

圖11 商圈輪廓精細化示意圖Fig.11 Business outline sample

(2)圖12是BPDA計算框架統(tǒng)計中山公園商圈的正常工作日與周末消費者規(guī)模對比圖.橫軸為一天不同的時間段,縱軸為商圈有效消費者規(guī)模大小.圖中有4條曲線,黑色曲線代表周六的時候消費者規(guī)模變化情況,紅色曲線代表周日的消費者規(guī)模變化情況,藍色和紫色曲線分別代表正常工作日周三和周五的消費者規(guī)模變化情況.

由圖12中可以看出,總體來講,中山公園商圈周末比工作日的消費者規(guī)模大很多.周末的消費者規(guī)模高峰期出現(xiàn)在14:00左右,只有一個波峰,而且高峰期兩端分布比較均勻,呈高斯分布.周六消費者規(guī)模比周日消費者規(guī)模稍大,這與很多消費者周六選擇逛街消費,周日選擇休息的生活習(xí)慣吻合.周三和周五消費者規(guī)模分別有兩個波峰,第一個高峰期出現(xiàn)在13:00左右,第二個高峰期出現(xiàn)在晚上18:00左右,這與上班族下班之后去商圈消費比較符合,而且周五高峰期的消費者規(guī)模比周三相對較大,這也符合大多數(shù)人會選擇在周五晚上商圈聚餐、娛樂、消費的習(xí)慣.

圖12 商圈的不同時段消費者規(guī)模分布圖Fig.12 Human traffi c distribution

7 總結(jié)

本文基于Kafka、Hadoop大數(shù)據(jù)平臺,提出了對商圈消費者規(guī)模進行統(tǒng)計分析的大數(shù)據(jù)處理方法.首先,對于商圈范圍不確定性,利用分類模型k NN對商圈的輪廓范圍進行了有效圈定;其次,由于用戶移動軌跡模糊性,根據(jù)商圈基站的不同位置,計算不同基站點的權(quán)重值;最后,利用大數(shù)據(jù)計算框架BPDA結(jié)合用戶軌跡判定規(guī)則以及時間閾值,對商圈有效消費者規(guī)模按時段進行統(tǒng)計分析.在未來的研究工作中,將會基于當(dāng)前的研究工作,采用更多的分類和聚類模型,對商圈內(nèi)消費者的性別、年齡、收入情況等信息進行挖掘,從而有助于提高商家廣告投放的精準(zhǔn)性,幫助商家創(chuàng)造更大的經(jīng)濟價值.

[1]YUAN J,ZHENG Y,XIE X.Discovering regions of diff erent functions in a city using human mobility and pois[C]//Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.2012:186-194.

[2]YUAN N J,ZHENG Y,XIE X,et al.Discovering urban functional zones using latent activity trajectories[J]. IEEE Transactions on Knowledge&Data Engineering,2015,27(3):712-725.

[3]QI G,LI X,LI S,et al.Measuring social functions of city regions from large-scale taxi behaviors[C]//IEEE International Conference on Pervasive Computing and Communications Workshops.IEEE,2011:384-388.

[4]GODDARD J B.Functional regions within the city centre:A study by factor analysis of taxi fl ows in central London[J].Transactions of the Institute of British Geographers,1970,49(49):161-182.

[5]VATSAVAI R R,BRIGHT E,VARUN C,et al.Machine learning approaches for high-resolution urban land cover classifi cation:A comparative study[C]//Proceedings of the 2nd International Conference on Computing for Geospatial Research&Applications.ACM,2011:Article No 11.

[6]ANTIKAINEN J.The concept of functional urban area(Findings on the ESPON project 1.1.1)[J].Informationen Zur Raumentwicklung,2005,7:447-456.

[7]KARLSSON C.Clusters,functional regions and cluster policies[R/OL].JIBS CESIS Electron,Working Paper Ser(84).[2016-06-01].https://www.researchgate.net/publication/5094404.

[8]BIRANT D,KUT A.ST-DBSCAN:An algorithm for clustering spatial–temporal data[J].Data&Knowledge Engineering,2007,60(1):208-221.

[9]CHEN X C,FAGHMOUS J H,KHANDELWAL A.Clustering dynamic spatio-temporal patterns in the presence of noise and missing data[C]//Proceedings of the 24th International Joint Conference on Artifi cial Intelligence (IJCAI 2015).2015:2575-2581.

[10]BIRANT D,KUT A.ST-DBSCAN:An algorithm for clustering spatial-temporal data[J].Data&Knowledge Engineering,2007,60(1):208-221.

[11]SLINK S R.An optimally effi cient algorithm for the single-link cluster method[J].The Computer Journal,1973, 16(1):30-34.

[12]ZHANG M L,ZHOU Z H.ML-k NN:A lazy learning approach to multi-label learning[J].Pattern recognition, 2007,40(7):2038-2048.

[13]ZHANG H,BERG A C,MAIRE M,et al.SVM-KNN:Discriminative nearest neighbor classifi cation for visual category recognition[C]//IEEE Computer Society Conference on Computer Vision and Pattern Recognition. IEEE Computer Society,2006:2126-2136.

[14]LI L,WEINBERG C R,DARDEN T A.Gene selection for sample classifi cation based on gene expression data: study of sensitivity to choice of parameters of the GA/k NN method[J].Bioinformatics,2001,17(12):1131-1142.

[15]李秀娟.k NN分類算法研究[J].科技信息,2009,31:81+383.

[16]WBITE T.O’Reilly:Hadoop權(quán)威指南[M].周敏奇,王曉玲,金澈清,等,譯.第2版.北京:清華大學(xué)出版社,2011.

[17]章志剛,金澈清,王曉玲,等.面向海量低質(zhì)手機軌跡數(shù)據(jù)的重要位置發(fā)現(xiàn)[J].軟件學(xué)報,2016，7:1700-1714.

[18]吳松,雒江濤,周云峰,等.基于移動網(wǎng)絡(luò)信令數(shù)據(jù)的實時人流量統(tǒng)計方法[J].計算機應(yīng)用研究,2014(3):776-779.

[19]沈澤,吳松,楊勇,等.移動通信網(wǎng)信令處理平臺的實時人流量統(tǒng)計方法[J].廣東通信技術(shù),2013,8:56-60.

[20]肖江,丁亮,束鑫,等.一種基于計算機視覺的行人流量統(tǒng)計方法[J].信息技術(shù),2015,8:22-25.

(責(zé)任編輯：李藝)

Business circle population mobility statistics based on mobile trajectory data

LIU Zhi,LIU Hui-ping,ZHAO Da-peng,WANG Xiao-ling
(Institute for Data Science and Engineering,School of Computer Science and Software Engineering,East China Normal University,Shanghai 200062,China)

With the advancement ofurbanization and continentaldevelopment ofbig data technology,smart business has become an important part of smart city construction.The popularity,consumer number scale and consumption level of smart business also become the hot spot in the construction of smart city.However,traditional consumer statistics method is based on traditional survey and sampling,etc.All of these traditional methods are high-cost and ineffi cient.Fortunately,the fast development of data mining technology makes statistics in business circle by analyzing user behavior trajectory data possible.In this paper,we propose a consumer scale analysis method on business circle using usertrajectory data.There are three mainly work parts：①How to determine the realboundary of business circle in trajectory data analysis domain is a primary problem,and we can judge a consumer activity within or outside the business circle based on it.Facing this issue,we raise a new method to delineate business circle using k-Nearest Neighbor(k NN) classifi cation algorithm based on the location of base station within business circle.②How to determine the relationship between user and business circle is also a new problem due to uncertainty of trajectory characteristics.We calculate irregular polygon area to evaluate the weight of each base station and also combine with time threshold in order to analyze consumer scale every day.③Finally,considering large amounts in trajectory data, we propose a big data computing framework BPDA(Business-Circle Parallel Distributed Algorithm),which is based on Hadoop big data platform and Kafka distributed message system,to implement business circle consumers scale analysis system.Moreover,we take Zhongshan Park business circle as an instance to verify the feasibility of our algorithm.

mobile trajectory data;consumer scale analysis;k NN classification algorithm;business circle outline

TP311

A

10.3969/j.issn.1000-5641.2017.04.009

1000-5641(2017)04-0097-17

2016-07-20

劉志,男,碩士研究生,研究方向為數(shù)據(jù)挖掘.E-mail：lyz8538350@126.com.