陳 凱，于彥偉，趙金東，宋 鵬

（1.煙臺(tái)大學(xué)計(jì)算機(jī)與控制工程學(xué)院，山東煙臺(tái) 264005；2.中國海洋大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系，山東青島 266100）

0 引言

隨著各種智能設(shè)備（例如車載全球定位系統(tǒng)（Global Positioning System，GPS）、智能手機(jī)、攝像頭監(jiān)控等）的快速發(fā)展以及移動(dòng)社交網(wǎng)絡(luò)（例如微博、微信、Twitter 等）的廣泛普及，人們的時(shí)空軌跡數(shù)據(jù)能夠從越來越多的資源中獲取到。針對(duì)這些時(shí)空軌跡數(shù)據(jù)的挖掘與行為分析，已經(jīng)在交通調(diào)度、醫(yī)療健康、城市計(jì)算、推薦系統(tǒng)等各方面得到了廣泛應(yīng)用。推理用戶的工作位置在實(shí)際應(yīng)用中也變得越來越重要，在產(chǎn)品推薦、精確營銷、交通管控以及城市規(guī)劃等方面都有著非常重要的應(yīng)用前景。例如，如果能夠推理出用戶的工作位置，就可以為他們推薦工作區(qū)域附近商場或者娛樂場所的熱門活動(dòng)。

目前，已存在很多基于不同時(shí)空數(shù)據(jù)源的位置推理研究，主要包括基于移動(dòng)社交網(wǎng)絡(luò)數(shù)據(jù)的位置推理［1-2］、基于GPS 軌跡數(shù)據(jù)的位置推理［3-4］、基于智能手機(jī)的位置推理［5-6］以及基于智能乘車卡的位置推理［7-8］。

盡管已經(jīng)存在大量基于時(shí)空數(shù)據(jù)的位置推理方法，但是這些方法在基于城市交通監(jiān)控大數(shù)據(jù)的車輛位置推理方面仍存在問題。首先，移動(dòng)社交媒體數(shù)據(jù)中并不包含用戶駕駛車輛的位置數(shù)據(jù)，所以不能用于車輛的位置推理；其次，雖然連續(xù)的GPS 軌跡數(shù)據(jù)在推理用戶位置方面有著很高的精度，但是由于存在隱私保護(hù)等原因，很難獲取到私家車大量的GPS軌跡數(shù)據(jù)進(jìn)行科學(xué)研究。

近些年，在國內(nèi)各大小城市，交通攝像頭被廣泛部署以監(jiān)控城市的實(shí)時(shí)交通狀況，這些智能化的攝像頭能夠?qū)崟r(shí)捕獲到交通車輛的各種信息，比如車牌號(hào)、速度以及行駛方向等。因此，無論車輛是否裝有GPS設(shè)備，都能夠通過城市的交通監(jiān)控系統(tǒng)獲取到整個(gè)城市所有車輛的行駛軌跡信息。雖然城市交通監(jiān)控系統(tǒng)的部署正在逐步完善，但是由于安裝和維護(hù)的成本問題，交通監(jiān)控?cái)z像頭的覆蓋范圍仍然有限。此外，交通監(jiān)控?cái)?shù)據(jù)是從固定部署的監(jiān)控?cái)z像頭獲得的，因此觀察到的車輛軌跡數(shù)據(jù)并不是完整的車輛行駛軌跡。

盡管工作位置推理在當(dāng)前現(xiàn)代城市管理中非常重要，但是基于交通監(jiān)控?cái)?shù)據(jù)的工作位置推理還尚未被探索，這主要因?yàn)榛诔鞘薪煌ūO(jiān)控大數(shù)據(jù)的位置推理問題面臨著巨大挑戰(zhàn)：

1）稀疏性。交通監(jiān)控?cái)z像頭只部署在城市的部分路口和道路處，所以每輛車每天的行駛軌跡只能被很少的攝像頭記錄到。因此基于交通監(jiān)控?cái)z像頭的車輛軌跡在時(shí)間和空間上都是不完整且稀疏的。

2）噪聲。交通監(jiān)控?cái)z像頭收集到的信息充滿噪聲。例如，車輛在不同天的工作時(shí)間可能出現(xiàn)在多個(gè)區(qū)域，有些攝像頭因?yàn)楣收显蚩赡苡行r(shí)段并沒有抓拍到經(jīng)過的車輛，都會(huì)導(dǎo)致數(shù)據(jù)的不一致問題。

3）固定性。由于部署攝像頭的位置是固定的，因此獲取到的車輛空間信息也是固定的。也就是說，車輛軌跡中的位置點(diǎn)僅由固定的攝像頭位置構(gòu)成。

為了解決上述挑戰(zhàn)，本文提出了一種基于交通攝像頭監(jiān)控大數(shù)據(jù)的車主工作位置推理方法。首先，收集了路網(wǎng)、興趣點(diǎn)等上下文數(shù)據(jù)，通過路網(wǎng)匹配預(yù)處理獲得了一個(gè)含有攝像頭、興趣點(diǎn)等豐富語義信息的真實(shí)路網(wǎng)；其次，通過聚類車輛軌跡中所提取到的起點(diǎn)-終點(diǎn)（Origin-Destination，O-D），獲得車輛重要的停留區(qū)域，即候選工作區(qū)域；之后，利用所提的訪問時(shí)間模式約束，從多個(gè)候選區(qū)域選擇出最大可能的工作區(qū)域；最后，利用所獲取的路網(wǎng)信息及周圍興趣點(diǎn)分布信息提取出車主可達(dá)興趣點(diǎn)（Reachable Point Of Interests，RPOI），進(jìn)一步縮小車主的工作位置范圍。

綜上所述，本文主要工作如下：1）提出并正式定義了基于城市攝像頭交通監(jiān)控大數(shù)據(jù)的工作位置推理問題；2）提出了一種基于城市交通監(jiān)控大數(shù)據(jù)的工作區(qū)域推理方法，通過對(duì)車輛軌跡中提取出的O-D 點(diǎn)聚類獲取到可能的候選工作區(qū)域，之后利用訪問時(shí)間模式約束匹配出最大可能的工作區(qū)域。

1 相關(guān)工作

本章主要從不同數(shù)據(jù)源上的位置推理研究介紹相關(guān)工作。

1）基于社交網(wǎng)絡(luò)數(shù)據(jù)的位置推理。目前，已存在很多基于社交網(wǎng)絡(luò)媒體數(shù)據(jù)的位置推理方法研究。其中一類工作是基于用戶的推文內(nèi)容來推理用戶的位置［9-12］；但是這些方法只能實(shí)現(xiàn)城市級(jí)的位置推理。另外一類研究使用用戶的簽到數(shù)據(jù)或文本信息來推理用戶的位置［2，13-15］。文獻(xiàn)［2］提出了一種利用帶有地理標(biāo)記的推文數(shù)據(jù)推理工作位置和家庭位置的方法，準(zhǔn)確率達(dá)到80%時(shí)，誤差范圍在10 km。這類方法主要利用用戶簽到數(shù)據(jù)的時(shí)間、頻率等信息推理用戶的重要位置（例如：家庭和工作地點(diǎn)），由于用戶更喜歡在新到達(dá)的興趣點(diǎn)簽到，這類方法推理的準(zhǔn)確率往往比較低。還有很多工作利用移動(dòng)社交網(wǎng)絡(luò)中用戶的好友位置信息來推理用戶的位置［1，16-19］。這類研究主要基于半監(jiān)督學(xué)習(xí)的框架，利用好友的位置以及社交網(wǎng)絡(luò)中好友關(guān)系影響傳播模型推理用戶的家庭位置等信息。最近，還有一些研究［20-21］基于社交媒體數(shù)據(jù)對(duì)時(shí)空軌跡數(shù)據(jù)進(jìn)行語義探索。Yuan 等［20］提出W4（Who+Where+When+What）概率模型，利用地理標(biāo)記的推文數(shù)據(jù)，從時(shí)間、空間和參與的活動(dòng)方面標(biāo)注用戶的移動(dòng)行為；Wu 等［21］使用高斯混合模型和核密度估計(jì)獲取移動(dòng)記錄在社交媒體數(shù)據(jù)上相關(guān)的語義詞為用戶的移動(dòng)記錄進(jìn)行語義標(biāo)注。

2）基于密集GPS數(shù)據(jù)的位置推理。當(dāng)前也存在很多基于密集GPS 軌跡進(jìn)行位置推理和軌跡理解的研究工作［3-4，22-26］。Krumm 等［3］使用4 種啟發(fā)式算法從GPS 軌跡中推理用戶的重要位置，誤差范圍大約60 m。Xiao 等［25］提出了一個(gè)通過停留點(diǎn)檢測來為用戶的GPS軌跡進(jìn)行語義位置建模的方法，例如，為用戶的GPS 軌跡建模成：購物中心→餐館→電影院。Wan等［4］提出了一種基于車輛GPS 數(shù)據(jù)和興趣點(diǎn)（Point Of Interest，POI）數(shù)據(jù)從私家車軌跡中挖掘時(shí)空語義移動(dòng)模式的方法，他們?cè)O(shè)計(jì)了一個(gè)基于潛在變量的概率生成模型來描述車輛的語義移動(dòng)性。由于GPS 軌跡數(shù)據(jù)遠(yuǎn)比交通監(jiān)控點(diǎn)密集，且采樣點(diǎn)任意，因此，這些方法都不適用于交通監(jiān)控?cái)?shù)據(jù)中的位置推理研究。

3）基于手機(jī)數(shù)據(jù)的位置推理。一類方法利用手機(jī)呼叫詳細(xì)記錄（Call Detail Record，CDR）來推理用戶的重要位置［5，27］。Isaacman 等［5］通過聚類的方法將用戶的CDR 數(shù)據(jù)進(jìn)行聚類獲得多個(gè)簇，之后通過分析數(shù)據(jù)的多種因素并使用邏輯回歸模型來推理哪些簇是重要的，這些重要的簇就代表用戶的一些重要位置。Alhasoun 等［27］利用CDR 來發(fā)現(xiàn)人們?cè)诔鞘蟹秶鷥?nèi)的移動(dòng)模式，通過識(shí)別用戶在白天和晚上花費(fèi)時(shí)間最多的位置來推理用戶的工作位置和家庭位置。另外一類研究工作基于智能手機(jī)的各類傳感器數(shù)據(jù)進(jìn)行用戶的位置推理［6，28-29］。Do 等［28］利用手機(jī)多種傳感器數(shù)據(jù)（地理坐標(biāo)、APP日志、藍(lán)牙記錄等）對(duì)用戶日常訪問的場所進(jìn)行自動(dòng)標(biāo)注。Zhao 等［6］提出了一個(gè)基于手機(jī)WiFi 掃描列表數(shù)據(jù)的位置推理方法，具體來說，首先從移動(dòng)軌跡數(shù)據(jù)中檢測出活動(dòng)區(qū)域并引入活躍度和多樣性度量來衡量個(gè)人的移動(dòng)性，其次結(jié)合用戶在家中的停留時(shí)間、晚上外出活動(dòng)以及工作日和休息日的工作時(shí)間等特征來識(shí)別用戶的家庭位置和工作位置。

4）基于智能乘車卡數(shù)據(jù)的位置推理。還有一類相關(guān)研究工作就是基于智能乘車卡數(shù)據(jù)的用戶位置推理方法研究［7-8，30-33］。龍瀛等［7］使用智能乘車卡數(shù)據(jù)、居民出行調(diào)查數(shù)據(jù)和土地利用圖來識(shí)別公交持卡人的居住地、工作地以及通勤出行模式。Munizaga等［31］通過將智能乘車卡數(shù)據(jù)和GPS數(shù)據(jù)結(jié)合起來，推理乘客在不同情景下的一個(gè)起點(diǎn)-終點(diǎn)（上車位置和下車位置）位置矩陣。Ma等［32］使用北京智能卡數(shù)據(jù)生成用戶的旅行鏈（trip chains），基于構(gòu)建的旅行鏈，應(yīng)用聚類算法提取乘客的旅行模式和旅行規(guī)律。Tian 等［8］提出了一種從智能乘車卡數(shù)據(jù)中識(shí)別住宅和工作場所位置的方法。該方法首先識(shí)別數(shù)據(jù)中的停車點(diǎn)，其次識(shí)別出停車點(diǎn)的路口，接下來考慮停車點(diǎn)附近有沒有其他停車點(diǎn)，最后利用地塊級(jí)土地利用地圖進(jìn)一步細(xì)化住宅和工作場所位置的識(shí)別。上述方法都是基于公共通勤車數(shù)據(jù)的重要位置推理研究，公共通勤車在時(shí)間和空間上都具有很強(qiáng)的規(guī)律性，并且?？康恼军c(diǎn)位置固定，而私家車相對(duì)來說行車線路不固定，出行的時(shí)間也相對(duì)隨意，因此這些方法也不能直接應(yīng)用于基于交通監(jiān)控?cái)?shù)據(jù)的工作位置推理問題。

2 問題定義

本章首先給出本文重要的概念定義，其次對(duì)基于交通監(jiān)控大數(shù)據(jù)的工作位置推理問題進(jìn)行了定義。

定義1攝像頭記錄。一個(gè)攝像頭記錄被定義為一個(gè)三元組（vehid，camj，ts），它表示車輛vehid在時(shí)間ts時(shí)刻經(jīng)過了攝像頭camj。

定義2車輛軌跡。車輛vehid的軌跡是一個(gè)根據(jù)時(shí)間排序的攝像頭記錄序列，表示為其中每個(gè)記錄表示車輛vehid在tsi時(shí)刻經(jīng)過了軌跡中的第i個(gè)攝像頭cami。

由定義2 可知，車輛軌跡由經(jīng)過的所有攝像頭的時(shí)間序列構(gòu)成，考慮車輛的周期性特點(diǎn)，將每一天的數(shù)據(jù)記為車輛的一條車輛軌跡。一輛車vehid所有的車輛軌跡集合記作TRid。所有車輛的軌跡集合記作TRs。

定義3路網(wǎng)。一個(gè)路網(wǎng)表示為G=(N，E)，其中：N={n1，n2，…，nm}表示所有路口的集合，E表示路口之間所有路段的集合，ei，j∈E表示從路口ni到路口nj的一條路段。需要注意的是，每個(gè)路段都是有方向的，例如路段是不同于路段的，因?yàn)樗鼈兊姆较虿煌?/p>

定義4興趣點(diǎn)（poi）。每個(gè)興趣點(diǎn)表示為(poiid，loc，cat)，其中：poiid是興趣點(diǎn)的名稱，loc表示興趣點(diǎn)的地理位置信息（例如經(jīng)度和緯度），cat表示興趣點(diǎn)的類別。

所有的興趣點(diǎn)構(gòu)成了興趣點(diǎn)集合POI。本文將基于交通監(jiān)控大數(shù)據(jù)的工作位置推理問題定義如下：

問題定義工作位置推理。給定路網(wǎng)G、興趣點(diǎn)集合POI以及車輛的軌跡集合TRs，本文的目標(biāo)是推理出每位車主最大可能的工作區(qū)域位置，并通過對(duì)可達(dá)興趣點(diǎn)的提取進(jìn)一步縮小車主的工作位置范圍。

3 基于交通監(jiān)控?cái)?shù)據(jù)的工作位置推理方法

3.1 工作位置推理總體框架

圖1 給出了本文提出的工作位置推理方法的總體框架，該框架主要包括3 部分：數(shù)據(jù)預(yù)處理、工作區(qū)域推理以及基于外圍信息的可達(dá)興趣點(diǎn)提取。數(shù)據(jù)預(yù)處理主要從交通監(jiān)控?cái)?shù)據(jù)中提取車輛軌跡，以及將攝像頭和poi映射到路網(wǎng)上；工作區(qū)域推理首先提取車輛軌跡中的停留點(diǎn)（例如起點(diǎn)攝像頭和終點(diǎn)攝像頭）進(jìn)行聚類，獲得候選工作區(qū)域，其次使用訪問時(shí)間模式約束推理出車主最大可能的工作區(qū)域；可達(dá)興趣點(diǎn)提取則結(jié)合外圍信息將車輛不能達(dá)到的興趣點(diǎn)剪枝掉，進(jìn)一步縮小工作位置范圍。

圖1 本文方法總體框架Fig.1 Overall framework of the proposed method

3.2 數(shù)據(jù)預(yù)處理

3.2.1 提取車輛軌跡

在交通監(jiān)控?cái)?shù)據(jù)中，每個(gè)攝像頭監(jiān)控記錄表示為一輛車在某個(gè)時(shí)間經(jīng)過某個(gè)攝像頭。由定義2 可知，通過車輛的車牌號(hào)并根據(jù)時(shí)間排序的攝像頭記錄可得到車輛軌跡。一般來說，人們的活動(dòng)往往是遵循以天為周期的，很多研究也驗(yàn)證了這一點(diǎn)［34-35］。因此本文將每輛車每天經(jīng)過的攝像頭作為一條車輛軌跡，從原始數(shù)據(jù)庫提取車輛軌跡，所有的車輛軌跡形成軌跡集合。

3.2.2 路網(wǎng)匹配

路網(wǎng)匹配包括攝像頭與路網(wǎng)的匹配以及poi與路網(wǎng)的匹配。首先，從開源的地圖平臺(tái)OpenStreetMap［36］上獲取真實(shí)路網(wǎng)。如定義3 所示，一個(gè)路網(wǎng)包括路口集合以及路口之間的路段集合。通常來說，監(jiān)控?cái)z像頭被部署在鄰近路口處的位置，用來獲得所有經(jīng)過此路段的車輛信息。因此，通過使用攝像頭的位置信息（例如經(jīng)度和緯度）將攝像頭匹配到相應(yīng)路段上，就能夠獲得車輛在路網(wǎng)上的不完整軌跡以及行駛方向。

其次，本文從百度地圖上爬取到poi信息，利用經(jīng)緯度信息將poi匹配到路網(wǎng)中距離它最近的路段上。最終，通過路網(wǎng)匹配獲取得到了一個(gè)含有poi和攝像頭等豐富語義信息的真實(shí)路網(wǎng)，以方便后續(xù)的工作區(qū)域推理與可達(dá)興趣點(diǎn)的提取。

3.3 工作區(qū)域推理

本節(jié)將介紹如何為每位車主推理出最大可能的工作區(qū)域。推理方法主要包括3 個(gè)步驟：1）提取出車輛軌跡中的O-D 對(duì)；2）使用密度聚類算法對(duì)提取到的O-D點(diǎn)聚類；3）使用訪問時(shí)間模式約束推理出車主的最大可能工作區(qū)域。

3.3.1 提取O-D對(duì)

上班工作是人們每天中最重要的活動(dòng)之一，通常情況下，人們每天早上從家里出發(fā)去工作地點(diǎn)上班，下班后離開工作地點(diǎn)。因此，車主的工作區(qū)域往往就隱含在車輛軌跡中的起點(diǎn)和終點(diǎn)附近。雖然基于攝像頭監(jiān)控的車輛軌跡在時(shí)間和空間上都非常稀疏，但可以根據(jù)車輛軌跡中的停留點(diǎn)來將整個(gè)軌跡劃分成多個(gè)子軌跡，這樣可以最大化地利用整個(gè)車輛軌跡。具體方法為：判斷車輛軌跡中兩個(gè)相鄰攝像頭的時(shí)間間隔是否超出了給定的閾值τ，來將整個(gè)軌跡劃分成多個(gè)子軌跡。其中每個(gè)子軌跡中的起點(diǎn)和終點(diǎn)稱為一個(gè)O-D對(duì)。需要注意的是，O-D 對(duì)中的起點(diǎn)和終點(diǎn)其實(shí)是監(jiān)控?cái)z像頭的固定位置。

為了確定時(shí)間閾值τ的合理取值，本文統(tǒng)計(jì)分析了車輛軌跡中相鄰攝像頭間的時(shí)間間隔分布情況。從圖2 可以看出，時(shí)間間隔在1 min 以內(nèi)情況僅占了21%，時(shí)間間隔占比最高的區(qū)間為1～5 min，占38%左右，可能的原因是相鄰攝像頭之間的距離較遠(yuǎn)或者是車輛需要等紅綠燈或堵車等情況。時(shí)間間隔在1～2 h 和大于2 h 占比較小，長時(shí)間間隔表示車輛在此處有較長時(shí)間停留，此位置可能為工作位置或其他重要位置等。

圖2 車輛經(jīng)過相鄰攝像頭的時(shí)間間隔分布Fig.2 Time interval distribution of a vehicle of passing adjacent cameras

3.3.2 聚類O-D點(diǎn)

如前面所述，交通監(jiān)控?cái)z像頭數(shù)據(jù)是稀疏的并且存在很多噪聲。為了減少數(shù)據(jù)稀疏以及噪聲的影響，本文使用DBSCAN（Density-Based Spatial Clustering of Applications with Noise）算法為每輛車提取的O-D 點(diǎn)進(jìn)行聚類，通過聚類能夠?qū)④囕v不經(jīng)常去的一些地點(diǎn)以及一些因?yàn)閿z像頭故障原因產(chǎn)生的異常O-D 點(diǎn)排除掉，從而獲得車主經(jīng)常去的一些重要區(qū)域。將所有O-D 點(diǎn)的位置（經(jīng)緯度）作為輸入數(shù)據(jù)，通過聚類獲得的包含攝像頭信息的每個(gè)簇就代表車主經(jīng)常訪問的一個(gè)區(qū)域，工作區(qū)域作為最重要的區(qū)域之一就隱含在這些簇中。接下來將討論如何從這些簇中選擇最大可能的工作區(qū)域。

3.3.3 訪問時(shí)間模式約束推理工作區(qū)域

通過聚類O-D 點(diǎn)能夠找出車主常去的一些重要區(qū)域，例如工作區(qū)域、家庭區(qū)域、常去的購物商場等。為了進(jìn)一步從這些區(qū)域中找到最大可能的工作區(qū)域，本文將利用訪問時(shí)間模式約束來推理車主最大可能的工作區(qū)域。

通常來講，絕大部分的人都是早上從家里去上班，下午或晚上下班離開工作地點(diǎn)，有時(shí)人們也可能中午離開工作地點(diǎn)去吃午飯，下午繼續(xù)返回工作地點(diǎn)上班。因此本文提出了一個(gè)in/out 訪問時(shí)間模式分別表示車主訪問每個(gè)區(qū)域（簇）中終點(diǎn)攝像頭和起點(diǎn)攝像頭的時(shí)間模式，其中，in時(shí)間模式記錄著車主進(jìn)入該區(qū)域的時(shí)間模式（對(duì)應(yīng)訪問該區(qū)域內(nèi)終點(diǎn)攝像頭的時(shí)間），out 時(shí)間模式相應(yīng)地表示離開該區(qū)域時(shí)的時(shí)間模式（對(duì)應(yīng)訪問該區(qū)域內(nèi)起點(diǎn)攝像頭的時(shí)間）。如果一個(gè)簇中in時(shí)間模式中大部分時(shí)間是在上午（5：00～11：00），并且out時(shí)間模式中大部分的時(shí)間是在下午（16：00～22：00），那么這個(gè)簇相比于其他的簇來說，更可能是車主的工作區(qū)域。

由于不同職業(yè)會(huì)存在不同的上下班時(shí)間的情況，為了最大限度地適應(yīng)更多職業(yè)的上下班時(shí)間，本文設(shè)置了兩個(gè)較長的上下班時(shí)間段，上班時(shí)間段設(shè)為5：00～11：00，下班時(shí)間段設(shè)為16：00～22：00。

本文采用了基于高斯核的核密度估計(jì)（Kernel Density Estimation，KDE）方法去估計(jì)每個(gè)簇中in和out時(shí)間模式中訪問時(shí)間的分布情況。將經(jīng)過攝像頭的時(shí)間作為輸入，KDE 可統(tǒng)計(jì)出車輛訪問每個(gè)簇的時(shí)間分布。利用KDE 時(shí)間分布，可進(jìn)一步找出每個(gè)簇中in 時(shí)間模式中峰值對(duì)應(yīng)的時(shí)間ti以及在out時(shí)間模式中峰值對(duì)應(yīng)的時(shí)間to。通過峰值對(duì)應(yīng)的時(shí)間可估算出車輛進(jìn)入這個(gè)區(qū)域以及離開這個(gè)區(qū)域的大概時(shí)間區(qū)間。根據(jù)國家統(tǒng)計(jì)局［37］數(shù)據(jù)統(tǒng)計(jì)可知，各類企業(yè)就業(yè)人員的周平均工作時(shí)間約為46 h，平均每天為9 h左右。本文設(shè)置了一個(gè)日工作時(shí)長閾值tw，也就是說，如果to-ti≥tw時(shí)，則認(rèn)為滿足日平均工作時(shí)長，可推理出這個(gè)區(qū)域是車主的一個(gè)可能工作區(qū)域。由于9 h是各類企業(yè)就業(yè)人員的平均日工作時(shí)長，本文設(shè)定日工作時(shí)長閾值為tw=7 h。

如果有多個(gè)簇符合該時(shí)間約束條件，則選擇車輛訪問攝像頭次數(shù)最多的簇作為車主最大可能的工作區(qū)域。

圖3 展示了對(duì)一輛車O-D 點(diǎn)聚類所獲得的三個(gè)最大簇的in/out 時(shí)間模式分布情況。圖中第一行為三個(gè)簇中所有攝像頭的總體訪問時(shí)間分布，第二行和第三行分別是in和out時(shí)間模式的訪問時(shí)間分布。從總體訪問時(shí)間分布來看，簇1和簇3在早晚都各有一個(gè)時(shí)間峰值，簇2 的訪問時(shí)間較為分散，沒有明顯峰值；而從in 和out 時(shí)間模式分布來看，簇1（真正的工作區(qū)域）的in 時(shí)間模式在9：00 左右出現(xiàn)了一個(gè)明顯峰值，而out時(shí)間模式在19：00 左右也出現(xiàn)了明顯峰值，日工作時(shí)長為10 h 左右。盡管簇3 的總體時(shí)間分布與簇1 相似，但是in 和out 時(shí)間模式中訪問時(shí)間峰值是完全相反的。根據(jù)本文所提的時(shí)間模式約束，簇1 更可能是車主的工作區(qū)域，而簇3 更可能是車主的家庭區(qū)域。

圖3 in/out時(shí)間模式的例子Fig.3 Examples of in/out time pattern

3.4 提取可達(dá)興趣點(diǎn)

車輛軌跡中存在兩種重要的攝像頭：起點(diǎn)攝像頭（O）和終點(diǎn)攝像頭（D）。設(shè)定Ω=為工作區(qū)域內(nèi)的起點(diǎn)攝像頭集合，Φ=為工作區(qū)域內(nèi)的終點(diǎn)攝像頭集合，需要注意的是，有些雙向攝像頭既是起點(diǎn)攝像頭又是終點(diǎn)攝像頭。結(jié)合路網(wǎng)中攝像頭以及各興趣點(diǎn)在路網(wǎng)中的位置，獲得車輛經(jīng)過Φ中攝像頭之后能夠到達(dá)哪些興趣點(diǎn)，以及車輛在離開工作區(qū)域時(shí)從哪些興趣點(diǎn)出發(fā)會(huì)經(jīng)過Ω中攝像頭。下面結(jié)合起點(diǎn)攝像頭和終點(diǎn)攝像頭，給出車主在工作區(qū)域內(nèi)可達(dá)興趣點(diǎn)的定義。

定義5可達(dá)興趣點(diǎn)。給定工作區(qū)域內(nèi)的一個(gè)興趣點(diǎn)pi，如果車輛經(jīng)過Φ中攝像頭進(jìn)入這個(gè)區(qū)域后，不需要經(jīng)過其他攝像頭可直接到達(dá)pi，同時(shí)車輛離開這個(gè)區(qū)域時(shí)從pi出發(fā)可直接到達(dá)Ω中的攝像頭，則pi被稱作該車主的一個(gè)可達(dá)興趣點(diǎn)。

下面給出在工作區(qū)域內(nèi)提取可達(dá)興趣點(diǎn)的算法。

算法1 提取可達(dá)興趣點(diǎn)算法。

如算法1 所示，首先，找出工作區(qū)域內(nèi)距離Ω和Φ中攝像頭r范圍內(nèi)的所有興趣點(diǎn)作為候選可達(dá)興趣點(diǎn)集合，記為P；其次，從集合P中篩選出能直達(dá)起點(diǎn)Ω攝像頭的興趣點(diǎn)集合Po，如6）～11）行所示。RoadNet(poi，camo)表示在路網(wǎng)中獲取興趣點(diǎn)poi到攝像頭camo的最短路徑；之后，再篩選出從終點(diǎn)Φ攝像頭出發(fā)能直達(dá)的興趣點(diǎn)集合Pd，如12）～16）行；最后求出Po與Pd的交集，獲得該車輛的可達(dá)興趣點(diǎn)集合RP。

4 實(shí)驗(yàn)與結(jié)果分析

本章將在真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)評(píng)估驗(yàn)證本文所提工作區(qū)域推理方法WorkInf（Work Inference）的有效性。

4.1 實(shí)驗(yàn)數(shù)據(jù)集

本文實(shí)驗(yàn)數(shù)據(jù)集采用了一個(gè)省會(huì)城市上的交通監(jiān)控?cái)?shù)據(jù)集，以及從多個(gè)數(shù)據(jù)源收集的外圍數(shù)據(jù)。

1）交通監(jiān)控?cái)?shù)據(jù)。該數(shù)據(jù)集包括2016 年8 月1 號(hào)到8 月31 號(hào)總共31 d 的從1 704 個(gè)監(jiān)控?cái)z像頭抓拍的4 億多條數(shù)據(jù)記錄。

2）路網(wǎng)。路網(wǎng)是從開源地圖OpenStreetMap［36］上采集的，選取的路網(wǎng)包括1 034個(gè)路口和4 350個(gè)路段。

3）興趣點(diǎn)。在百度地圖API（Application Programming Interface）上爬取了相應(yīng)路網(wǎng)區(qū)域內(nèi)的興趣點(diǎn)集合，包括17 個(gè)大類、120個(gè)小類。

4.2 實(shí)驗(yàn)設(shè)置

4.2.1 真實(shí)數(shù)據(jù)標(biāo)注

評(píng)估實(shí)驗(yàn)需要知道車主真實(shí)的工作位置來評(píng)估本文方法的有效性，然而在原始交通監(jiān)控?cái)?shù)據(jù)中并不包含這部分信息。因此，利用人工標(biāo)注方法，邀請(qǐng)了實(shí)驗(yàn)室10 名研究生，標(biāo)注了570 個(gè)車主的工作區(qū)域位置。人工標(biāo)記的過程主要分為兩部分：首先將聚類O-D點(diǎn)獲得的簇映射到百度地圖上，并將車輛訪問每個(gè)簇的時(shí)間進(jìn)行可視化處理；其次采用投票的方式，讓邀請(qǐng)的同學(xué)投票，將票數(shù)最多的簇作為該車主真實(shí)的工作區(qū)域，用以評(píng)估本文方法的有效性。

據(jù)統(tǒng)計(jì)，在交通監(jiān)控?cái)?shù)據(jù)中，車輛出現(xiàn)21～31 d 的數(shù)據(jù)是最多的，因此重點(diǎn)評(píng)估該數(shù)據(jù)區(qū)間的車輛，共選取240 輛。為了評(píng)估數(shù)據(jù)稀疏性對(duì)方法的影響，又分別在僅出現(xiàn)5～10 d、11～15 d、16～20 d三個(gè)數(shù)據(jù)區(qū)間的車輛中各標(biāo)注了110輛車的工作區(qū)域位置。最后，獲得了車輛數(shù)據(jù)區(qū)間為5～31 d 總計(jì)570輛車的工作位置區(qū)域。

4.2.2 對(duì)比算法

根據(jù)文獻(xiàn)檢索，目前尚未有使用城市交通監(jiān)控?cái)?shù)據(jù)推理重要位置的相關(guān)工作。因此本文使用了基本統(tǒng)計(jì)方法StatInf（Statistic Inference）作為對(duì)比算法。

StatInf方法將車輛的每次停留的位置記為D-O對(duì)，D為該停留的最后經(jīng)過的攝像頭，O 為該停留結(jié)束離開時(shí)經(jīng)過的攝像頭，因此，每個(gè)D-O對(duì)可以認(rèn)為是車主去往的一個(gè)區(qū)域。其次，根據(jù)訪問頻率，對(duì)每個(gè)D-O 對(duì)進(jìn)行統(tǒng)計(jì)，頻率越高的D-O對(duì)表示該車主更頻繁訪問該區(qū)域，所以將該D-O 對(duì)所在區(qū)域作為車主的工作區(qū)域。

StatInf+time 方法在StatInf 算法的基礎(chǔ)上，考慮了本文所提的in/out訪問時(shí)間模式約束推理最大可能的工作區(qū)域。

4.2.3 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)?zāi)J(rèn)參數(shù)設(shè)置：停留點(diǎn)時(shí)間間隔閾值r=120 min，KDE 模型帶寬設(shè)為h=2，DBSCAN 算法參數(shù)設(shè)置MinPts=20，Eps=1000 m。

4.2.4 評(píng)估指標(biāo)

本文采用準(zhǔn)確率評(píng)估方法的有效性，定義如下：

其中：N為車輛的總數(shù)；若第i輛車的推理工作位置與標(biāo)注的工作位置區(qū)域一致，則ri=1；否則，ri=0。

4.3 性能評(píng)估

本節(jié)首先評(píng)估了所提工作區(qū)域推理方法以及對(duì)比算法的總體性能，其次評(píng)估了數(shù)據(jù)稀疏性對(duì)本文方法的影響。

從表1 中的實(shí)驗(yàn)結(jié)果來看，本文所提的WorkInf 方法在不同稀疏的數(shù)據(jù)以及總的5～31 d數(shù)據(jù)上的表現(xiàn)都要優(yōu)于對(duì)比算法。在總的5～31 d 數(shù)據(jù)上，WorkInf 方法準(zhǔn)確率達(dá)到了89.8%，相比StatInf 算法和StatInf+time 算法分別提升了17 個(gè)百分點(diǎn)和6 個(gè)百分點(diǎn)，這說明本文所提WorkInf 方法在推理車主工作區(qū)域問題上具有較好的性能。主要的原因是因?yàn)楸疚姆椒ㄍㄟ^提取車輛軌跡中所有的停留點(diǎn)，最大限度地利用了整個(gè)車輛軌跡，并且使用聚類算法對(duì)提取的停留點(diǎn)進(jìn)行聚類有效獲取到了車輛常去的一些區(qū)域，相較于簡單的統(tǒng)計(jì)方法來說能夠更好地利用數(shù)據(jù)的空間信息。另一方面，城市中絕大多數(shù)人們的工作都是早出晚歸的，本文提出的in/out訪問時(shí)間模式方法充分考慮了工作時(shí)間的規(guī)律特性，考慮了in/out時(shí)間模式的StatInf+time算法的準(zhǔn)確率比StatInf算法有明顯的提升（在5～31 d 數(shù)據(jù)上提升了11 個(gè)百分點(diǎn)）也驗(yàn)證了這一點(diǎn)。通過對(duì)車輛軌跡數(shù)據(jù)時(shí)間和空間信息的充分利用，使得本文所提的WorkInf方法達(dá)到了較好的性能。

表1 各方法在不同區(qū)間的車輛數(shù)據(jù)上正確推理出工作位置的準(zhǔn)確率對(duì)比Tab.1 Accuracy comparison of different methods to infer correct work location on vehicle data with different intervals

表1中第2～4列數(shù)據(jù)展示了所提WorkInf方法和對(duì)比算法在不同稀疏的數(shù)據(jù)上的實(shí)驗(yàn)結(jié)果。從實(shí)驗(yàn)結(jié)果來看，本文方法在不同稀疏數(shù)據(jù)上的結(jié)果都要優(yōu)于對(duì)比算法，并且WorkInf算法在5～10 d 數(shù)據(jù)上的結(jié)果相比于11～15 d 的結(jié)果只降低了1.8 個(gè)百分點(diǎn)，而兩個(gè)對(duì)比算法在5～10 d 數(shù)據(jù)上的結(jié)果相對(duì)于11～15 d 的結(jié)果有非常明顯的性能下降。這是因?yàn)楸M管在5～10 d數(shù)據(jù)上獲取的停留點(diǎn)數(shù)量明顯減少，但是WorkInf算法使用的聚類算法對(duì)停留點(diǎn)進(jìn)行聚類依然能夠有效獲取到一些重要區(qū)域。而StatInf 算法僅僅對(duì)D-O 對(duì)的統(tǒng)計(jì)次數(shù)作為每個(gè)區(qū)域的重要程度，當(dāng)車主在多次進(jìn)入/離開某個(gè)區(qū)域時(shí)，如果經(jīng)過了該區(qū)域附近不同的攝像頭時(shí)，統(tǒng)計(jì)方法無法將這些不同的攝像頭歸結(jié)為同一區(qū)域，而是根據(jù)每個(gè)D-O 對(duì)將此區(qū)域劃分成多個(gè)區(qū)域；因此隨著車輛軌跡數(shù)量的減少，數(shù)據(jù)稀疏性的增加，噪聲對(duì)對(duì)比算法產(chǎn)生的影響越來越大。而本文所提出的WorkInf方法在稀疏的數(shù)據(jù)上依然表現(xiàn)出很好的性能。

通常來說，車輛的軌跡數(shù)據(jù)越少，提供的信息就越有限，但是從表1 的實(shí)驗(yàn)結(jié)果中可以發(fā)現(xiàn)，WorkInf 方法在5～10 d 和11～15 d 的數(shù)據(jù)中性能并沒有明顯下降，反而比16～20 d 的數(shù)據(jù)有一定的提升，可能的原因有兩點(diǎn)：1）正如前面所提到的，本文方法最大限度地利用了稀疏數(shù)據(jù)的時(shí)間和空間信息，降低了稀疏數(shù)據(jù)對(duì)本文方法的影響；2）雖然車輛數(shù)據(jù)增加了，但是數(shù)據(jù)中的噪聲也會(huì)隨之增加。16～20 d 數(shù)據(jù)中可能還存在部分車輛經(jīng)過的區(qū)域攝像頭覆蓋范圍有限，導(dǎo)致車輛軌跡更加稀疏，使得準(zhǔn)確率有所下降。

4.4 參數(shù)敏感性評(píng)估

本節(jié)將評(píng)估參數(shù)變化對(duì)本文方法的影響。評(píng)估的參數(shù)包括時(shí)間間隔參數(shù)τ、聚類算法參數(shù)MinPts和Eps以及KDE算法帶寬參數(shù)h。

圖4是本文方法在參數(shù)τ從60 min變化到300 min的準(zhǔn)確率曲線。從圖4 中可以看出，當(dāng)120 ≤τ≤240 時(shí)達(dá)到最佳性能，而當(dāng)τ=60 和τ=300 時(shí)，準(zhǔn)確率有明顯的下降，這是因?yàn)椋寒?dāng)τ=60時(shí)，可能會(huì)有很多間隔較短與工作位置不相關(guān)的停留點(diǎn)被提取出來，影響了結(jié)果的準(zhǔn)確性；當(dāng)τ=300 時(shí)準(zhǔn)確率是最低的，這是因?yàn)闀r(shí)間間隔設(shè)置太長，很多重要停留點(diǎn)被丟失。比如，對(duì)于那些上午上班、中午回家休息、然后下午繼續(xù)工作的人來說，每次在工作地點(diǎn)停留時(shí)間一般不會(huì)超過300 min，因此工作區(qū)域的停留點(diǎn)會(huì)被丟棄掉，導(dǎo)致本文方法不能夠正確推理出工作區(qū)域。

圖5 展示了在21～31 d 數(shù)據(jù)集上變化聚類算法參數(shù)MinPts從5到40，Eps從500 m 到1 500 m 的準(zhǔn)確率結(jié)果。如圖5 所示，隨著MinPts的增加，各個(gè)Eps結(jié)果的準(zhǔn)確率均呈現(xiàn)先升后降趨勢。這可能是因?yàn)楫?dāng)MinPts數(shù)值較小時(shí)，聚類之后會(huì)獲得很多個(gè)不相關(guān)的簇，對(duì)實(shí)驗(yàn)準(zhǔn)確率產(chǎn)生一定影響；而當(dāng)MinPts值（MinPts＞20）太大時(shí)，使得很多重要的簇（包含工作區(qū)域）被合并，因此導(dǎo)致準(zhǔn)確率急劇下降。

圖4 時(shí)間間隔τ與準(zhǔn)確率的關(guān)系Fig.4 Relationship between time interval τ and accuracy

圖5 核心點(diǎn)數(shù)量MinPts和鄰域半徑Eps與準(zhǔn)確率的關(guān)系Fig.5 Relationship between core point number MinPts and neighborhood radius Eps and accuracy

接下來分析當(dāng)MinPts=20 時(shí)，Eps變化對(duì)準(zhǔn)確率的影響。從實(shí)驗(yàn)結(jié)果中可以看出，Eps=1000 時(shí)達(dá)到最佳性能。Eps=500 時(shí)，準(zhǔn)確率最低，這是因?yàn)镋ps=500 時(shí)范圍較小，通過聚類之后可能很多重要區(qū)域被劃分成了多個(gè)子區(qū)域，導(dǎo)致準(zhǔn)確率降低；當(dāng)Eps≥1250 時(shí)，相比于Eps=1000 來說準(zhǔn)確率略有降低，這是因?yàn)榫垲惙秶^大，通過聚類獲得的簇中會(huì)包含很多不相關(guān)的停留點(diǎn)，這也會(huì)對(duì)本文方法性能產(chǎn)生一定影響。

圖6展示了本文方法在帶寬參數(shù)h從1～5 h變化時(shí)的準(zhǔn)確率。從圖6 中可以看出，隨著橫坐標(biāo)帶寬變化，準(zhǔn)確率基本都保持平穩(wěn)的狀態(tài)。這是因?yàn)閹捵兓瘜?duì)訪問時(shí)間分布中峰值影響不大，也就是說，峰值點(diǎn)對(duì)應(yīng)的大體時(shí)間沒有變化，因此參數(shù)h的變化對(duì)本文方法準(zhǔn)確率影響不大。

圖6 帶寬h與準(zhǔn)確率的關(guān)系Fig.6 Relationship between bandwidth h and accuracy

4.5 案例分析

本節(jié)以案例分析的方式展示所提可達(dá)興趣點(diǎn)提取方法的有效性。首先，利用所提的工作區(qū)域推理方法可獲取到車主的最大可能工作區(qū)域，如圖7 所示為獲取某車輛的工作區(qū)域，其中起點(diǎn)攝像頭集合和終點(diǎn)攝像頭集合分別為：Ω=圖中實(shí)線箭頭表示車輛在經(jīng)過Φ中攝像頭之后可能去往的方向，虛線箭頭表示經(jīng)過Ω中攝像頭離開工作區(qū)域的方向。表2 為該工作區(qū)域內(nèi)各興趣點(diǎn)和可達(dá)興趣點(diǎn)的數(shù)量。設(shè)p1和p2表示圖中兩個(gè)興趣點(diǎn)的位置。當(dāng)車輛經(jīng)過Φ中攝像頭進(jìn)入這個(gè)區(qū)域時(shí)，根據(jù)實(shí)線箭頭可以看出，車輛可以往三個(gè)方向行駛，因此車輛能夠到達(dá)興趣點(diǎn)p1和p2。而車輛在離開這個(gè)區(qū)域時(shí)，需經(jīng)過Ω中攝像頭，根據(jù)圖中的路線能夠看出，車輛在離開p2時(shí)，是很難直接到達(dá)Ω中攝像頭，而需要繞過幾個(gè)其他攝像頭，因此p2不是可達(dá)興趣點(diǎn)，要被剪枝掉。最后獲取到的該車主在該區(qū)域各類別的可達(dá)興趣點(diǎn)如表2 所示。對(duì)比表2 中各類POI 數(shù)量可以看出，POI 總的數(shù)量從49 減少到24，POI 類別從7 類減少到6 類，驗(yàn)證了可達(dá)興趣點(diǎn)提取方法在縮小車主工作位置范圍及興趣點(diǎn)類別方面是有效的。

圖7 提取可達(dá)興趣點(diǎn)案例Fig.7 Case of extracting RPOI

表2 各類興趣點(diǎn)和可達(dá)興趣點(diǎn)數(shù)量Tab.2 Number of POIs and RPOIs of different categories

5 結(jié)語

本文提出了一個(gè)基于城市交通監(jiān)控大數(shù)據(jù)的車輛工作位置推理方法。該方法首先通過路網(wǎng)匹配的方法得到了一個(gè)含有攝像頭、興趣點(diǎn)等豐富語義信息的真實(shí)路網(wǎng)；其次，通過聚類方法獲取車輛一些重要的經(jīng)常訪問的區(qū)域；之后，利用所提的in/out訪問時(shí)間模式約束，從多個(gè)候選區(qū)域選擇出最大可能的工作區(qū)域；最后利用所獲取的路網(wǎng)信息及周圍興趣點(diǎn)分布提取出工作區(qū)域中的可達(dá)興趣點(diǎn)，進(jìn)一步縮小車主工作位置的范圍。在真實(shí)數(shù)據(jù)上的實(shí)驗(yàn)評(píng)估和案例分析驗(yàn)證了本文方法的有效性。

城市交通監(jiān)控?cái)?shù)據(jù)不僅包含車輛的工作位置信息，還包含其他有趣的活動(dòng)信息，如購物活動(dòng)和娛樂活動(dòng)等，因此，在之后的工作中，將城市交通監(jiān)控?cái)?shù)據(jù)與上下文興趣點(diǎn)數(shù)據(jù)相結(jié)合來探索挖掘車輛的移動(dòng)模式。