鄭林江 趙 欣 蔣朝輝 鄧建國 夏 冬 劉衛(wèi)寧

1(重慶大學(xué)計算機(jī)學(xué)院 重慶 400030) 2(信息物理社會可信服務(wù)計算教育部重點實驗室(重慶大學(xué)) 重慶 400030) 3(重慶城市綜合交通樞紐開發(fā)投資有限公司 重慶 401121)

0 引 言

出租車是城市居民日常出行中重要的交通工具之一。區(qū)別于公交車和軌道等其他交通出行方式，出租車沒有固定的線路和站點，提供了便捷和定制化的個人出行服務(wù)。因此，出租車行駛過程中的軌跡信息能夠很好地反映城市居民出行特點以及城市交通運行狀況，是城市交通分析重要的數(shù)據(jù)來源[1]。近年來，出租車軌跡數(shù)據(jù)研究引起了廣泛關(guān)注，這也促使了諸如路徑規(guī)劃[3-4]，基于位置的社交網(wǎng)絡(luò)[5]，智能交通系統(tǒng)[6]，以及城市計算[7-9]的快速發(fā)展。

根據(jù)韋氏詞典中的定義，熱點區(qū)域是指一個比其他區(qū)域具有更多的興趣點、人類活動的地理區(qū)域。在現(xiàn)代城市中，城市中的熱點區(qū)域往往代表著人們出入次數(shù)較多、交通流量較大，出行需求較高的區(qū)域，是人們頻繁、密集出行的直接體現(xiàn)。因此，城市中的熱點區(qū)域?qū)τ诔鞘泄芾矶跃哂蟹浅Ｖ匾膬r值。從移動數(shù)據(jù)中發(fā)現(xiàn)城市居民出行熱點區(qū)域更是成為了一個新的研究關(guān)注點。在現(xiàn)有的研究工作中，熱點區(qū)域發(fā)現(xiàn)主要有三種方法，即：傳統(tǒng)的問卷調(diào)查的方法[10]，空間聚類的方法[11-14]，以及空間統(tǒng)計分析的方法[15-16]。其中，傳統(tǒng)的問卷調(diào)查的方法是指通過制作問卷和調(diào)查訪問的方式收集數(shù)據(jù)，通過匯總分析，發(fā)現(xiàn)人們頻繁活動的區(qū)域范圍。但是，這種方法相對滯后，存在時效性差，準(zhǔn)確度低等問題，獲得的結(jié)果往往參考意義不大。空間聚類的方法隸屬于數(shù)據(jù)挖掘研究領(lǐng)域，該方法通過測算空間數(shù)據(jù)對象之間的距離從而對輸入數(shù)據(jù)進(jìn)行分類，探索對象的空間聚集模式。該方法主要是利用數(shù)據(jù)挖掘中的聚類算法如K-MEANS算法、K-MEDOIDS算法、BIRCH算法、DBSCAN算法等對空間數(shù)據(jù)進(jìn)行聚類分析，從而得到空間聚集的點集合，形成密集區(qū)域。然而，聚類算法大多采用了數(shù)據(jù)驅(qū)動的計算方法，在處理大規(guī)?？臻g數(shù)據(jù)時，往往需要更大的計算內(nèi)存，耗費更長的計算時間，存在著對輸入敏感、伸縮性差等缺點?？臻g統(tǒng)計分析方法是應(yīng)用統(tǒng)計學(xué)方法分析空間單元，通過計算空間單元之間的關(guān)聯(lián)度以及相似性進(jìn)而發(fā)掘熱點區(qū)域。例如局部空間自相關(guān)統(tǒng)計量方法[15]通過測算相鄰空間單元之間的相關(guān)系數(shù)，從而分析它們之間的相關(guān)性和相似性，識別不同空間位置的上可能存在的空間聚集模式；空間掃描統(tǒng)計法[16]主要借鑒滑動窗口的思想，通過建立可變大小的滑動窗口對研究區(qū)域范圍內(nèi)的數(shù)據(jù)進(jìn)行掃描統(tǒng)計，測算區(qū)域內(nèi)所有位置在不同大小的窗口下的最大對數(shù)似然比值，進(jìn)而探測最有可能存在聚集性的區(qū)域?？臻g統(tǒng)計分析方法存在復(fù)雜度高、實現(xiàn)難度大和可行性較低等問題，實際情況中并沒有得到廣泛的應(yīng)用。

綜上所述，為了更好地挖掘城市中的熱點區(qū)域，提升方法的可伸縮性以及計算效率，受基于密度的聚類算法以及文獻(xiàn)[17-20]中區(qū)域網(wǎng)格化方法的啟發(fā)，本文提出了一種基于網(wǎng)格密度的熱點區(qū)域探測方法：GScan算法。該方法通過劃分網(wǎng)格單元將大量空間GPS數(shù)據(jù)離散化，再利用密度閾值篩選熱點網(wǎng)格單元，并對臨近可達(dá)的熱點網(wǎng)格進(jìn)行合并，從而挖掘出城市中的熱點區(qū)域。

1 相關(guān)定義

首先對相關(guān)概念進(jìn)行定義。

定義1研究區(qū)域(Area)：給定一個空間數(shù)據(jù)集合Sd={p1,p2,…,pn}，其中，pi(1≤i≤n)代表一個空間數(shù)據(jù)采樣點，那么包含該空間數(shù)據(jù)集合的區(qū)域范圍可用式(1)定義如下：

(1)

式中：lonmin、lonmax、latmin、latmax分別代表數(shù)據(jù)集合中的經(jīng)緯度的最小值與最大值；相應(yīng)地，我們定義覆蓋全部經(jīng)緯度位置數(shù)據(jù)的區(qū)域D為：

D=[lonmin,lonmax]×[latmin,latmax]

(2)

定義2網(wǎng)格單元：對于區(qū)域D，假設(shè)其經(jīng)度的取值范圍為[lonmin,lonmax]，緯度的取值范圍為[latmin,latmax]，對區(qū)域D分別從經(jīng)度以及緯度兩個維度對進(jìn)行劃分，把每個屬性維的取值范圍等分為長度為k的小區(qū)間，經(jīng)過這樣的劃分，區(qū)域D被劃分成了若干個k×k大小的正方形單元，由小區(qū)間組成的正方形單元被定義為網(wǎng)格單元。圖1是我們對重慶市南岸區(qū)部分地區(qū)以不同的分辨率網(wǎng)格化的結(jié)果。

圖1 網(wǎng)格化示例

定義3網(wǎng)格單元的數(shù)量：對于區(qū)域D，由于我們將其劃分成了k×k大小的網(wǎng)格單元，所以緯度區(qū)間被劃分成了m1個小區(qū)間，其中m1的計算可用式(3)表示；相應(yīng)地，經(jīng)度區(qū)間被劃分成了m2個小區(qū)間，其中m2的計算可用式(4)表示，所以區(qū)域網(wǎng)格化后，被劃分成的網(wǎng)格單元總個數(shù)為兩者的乘積，即m=m1×m2。

(3)

(4)

式中：lonmin、lonmax、latmin、latmax分別代表數(shù)據(jù)集合中的經(jīng)緯度的最小值與最大值，k為網(wǎng)格單元的大小。

定義4映射關(guān)系：對于從屬于區(qū)域D范圍內(nèi)的空間數(shù)據(jù)集合Sd，令集合Sd中的一個空間數(shù)據(jù)點p的經(jīng)緯度坐標(biāo)為[lat,lon]，則空間數(shù)據(jù)點p與對應(yīng)網(wǎng)格單元的所屬關(guān)系可用公式表示：

(5)

根據(jù)數(shù)據(jù)點與網(wǎng)格單元的所屬關(guān)系，空間數(shù)據(jù)點p和網(wǎng)格的映射函數(shù)被定義為：

(6)

式中：indlat是網(wǎng)格單元的緯度索引，indlon是網(wǎng)格單元的經(jīng)度索引，lat和lon分別代表GPS點p的精度和緯度。因此，我們可以用“indlat-indlon”唯一確定一個網(wǎng)格單元。

定義5網(wǎng)格密度：對于網(wǎng)格單元Ui，計算屬于該劃分網(wǎng)格單元的空間數(shù)據(jù)點，其空間數(shù)據(jù)點的總數(shù)就叫做網(wǎng)格單元Ui的網(wǎng)格密度，記作den(Ui)。當(dāng)den(Ui)=0時，稱其為空網(wǎng)格單元；當(dāng)den(Ui)>0時，稱其為非空網(wǎng)格單元。

定義6熱點網(wǎng)格單元：對于網(wǎng)格單元Ui，如果其網(wǎng)格密度滿足：

den(Ui)≥λ

(7)

式中：λ是網(wǎng)格密度閾值，則稱網(wǎng)格單元Ui為熱點網(wǎng)格單元，否則，稱其為普通網(wǎng)格單元。

定義7網(wǎng)格的位置：對于一個網(wǎng)格單元Ui，它的空間位置受其所屬空間數(shù)據(jù)點分布的影響，因此它的位置不能簡單的定義為網(wǎng)格單元的中心，為了反映網(wǎng)格中數(shù)據(jù)點的分布情況，我們定義網(wǎng)格單元的空間位置為經(jīng)緯度坐標(biāo)的平均值：

(8)

式中：n是網(wǎng)格單元中空間數(shù)據(jù)點的數(shù)量，lat(pi)和lon(pi)分別代表空間數(shù)據(jù)點pi的緯度和經(jīng)度，lat(Ui)和lon(Ui)代表網(wǎng)格單元的位置。

定義8空間距離：在計算空間數(shù)據(jù)之間的距離時，由于空間數(shù)據(jù)受高維空間的稀疏性影響，用歐幾里德距離計算得到的結(jié)果并不能真實反映空間數(shù)據(jù)之間的距離，為了提高計算準(zhǔn)確性，我們定義兩個空間數(shù)據(jù)點之間的距離計算如公式所示：

dis(pA,pB)=Δη×R

(9)

(10)

式中：dis(pA,pB)代表空間數(shù)據(jù)點pA和pB之間的距離，R代表地球的半徑，Δη代表兩點與地球中心連線的夾角，ψ和γ分別代表緯度和經(jīng)度，Δψ和Δγ分別代表兩空間數(shù)據(jù)點緯度和經(jīng)度之間的差值。

定義9網(wǎng)格直接可達(dá)：對于網(wǎng)格集合G，若存在網(wǎng)格單元Ui∈G，網(wǎng)格單元Uj∈G，且滿足：

dis(Ui,Uj)≤?·k

(11)

則我們稱網(wǎng)格單元Ui和Uj直接密度可達(dá)。其中k為網(wǎng)格單元的大小，?為距離系數(shù)，顯然，?不能太大，以我們的經(jīng)驗，通常取?∈[1,2]，在我們的實驗中取?=1.3。

定義10網(wǎng)格可達(dá)：對于網(wǎng)格單元Ui和Uj，如果存在網(wǎng)格序列U1,U2,…,Un-1,Un，使得U1=Ui，Un=Uj，且對1≤r

定義11熱點區(qū)域：對于網(wǎng)格單元集合G中的一個非空子集H，如果滿足：

(1) 稠密性：對于?Ui∈H，其中Ui是一個熱點網(wǎng)格單元。

(2) 連通性：對于?Ui∈H，?Uj∈H，Ui是從Uj網(wǎng)格密度可達(dá)的。

(3) 極大性：對于?Uj∈H，只要Ui是從Uj網(wǎng)格密度可達(dá)的，則存在Ui∈H。

綜上所述，若存在滿足上述三個條件的網(wǎng)格集合H，則稱由網(wǎng)格集合H構(gòu)成的區(qū)域為熱點區(qū)域。

2 基于網(wǎng)格密度的GScan聚類算法

2.1 算法的總體描述

將研究區(qū)域或者數(shù)據(jù)范圍網(wǎng)格化，并用劃分生成的網(wǎng)格代替原有的數(shù)據(jù)集合是一種有效地規(guī)約大規(guī)模數(shù)據(jù)的方法。因此，基于網(wǎng)格密度的GScan聚類算法的思想是：首先，對空間數(shù)據(jù)對象所占的區(qū)域進(jìn)行網(wǎng)格劃分，將研究區(qū)域范圍劃分成互不重疊的若干個大小為k×k的正方形網(wǎng)格單元；其次，遍歷原有數(shù)據(jù)集，將原始空間數(shù)據(jù)通過映射函數(shù)映射到所屬的網(wǎng)格單元；接著，通過計算所屬網(wǎng)格單元中的數(shù)據(jù)密度，識別網(wǎng)格集合中的熱點網(wǎng)格單元，剔除其中的普通網(wǎng)格單元；最后，根據(jù)熱點網(wǎng)格單元中的數(shù)據(jù)點的分布計算熱點網(wǎng)格單元的位置，并通過計算網(wǎng)格單元間的距離來合并熱點網(wǎng)格單元從而得到熱點區(qū)域。由于原始的空間數(shù)據(jù)被網(wǎng)格單元所替代，大大規(guī)約了所需處理的數(shù)據(jù)的規(guī)模。因此，本文提出的GScan算法具有較好的伸縮性，能夠克服基于密度的方法在處理大規(guī)?？臻g數(shù)據(jù)時存在的不足。

2.2 算法流程

通過第1節(jié)的定義可以得知，區(qū)別于基于密度的方法，GScan算法處理的最小單位是網(wǎng)格單元，由于網(wǎng)格單元有效地規(guī)約了空間數(shù)據(jù)，減少了數(shù)據(jù)的規(guī)模，所以能夠提高計算的速度。接下來，我們將進(jìn)一步介紹基于網(wǎng)格密度的GScan算法的具體流程。在GScan算法中，需要設(shè)定兩個參數(shù)：k和λ，其中k是網(wǎng)格的大小，而λ是網(wǎng)格密度閾值，對于給定的輸入空間數(shù)據(jù)集合Sd，我們的方法將最終生成熱點區(qū)域的集合，熱點區(qū)域集合代表了空間數(shù)據(jù)的聚集模式。實現(xiàn)GScan軌跡聚類算法主要包括3個階段：

1) 遍歷空間數(shù)據(jù)集合，確定研究區(qū)域范圍，并將原始空間數(shù)據(jù)映射到相應(yīng)的k×k大小的網(wǎng)格單元。

2) 根據(jù)參數(shù)λ，篩選出網(wǎng)格單元集合中密度值大于λ的熱點網(wǎng)格，并將得到的熱點網(wǎng)格集合進(jìn)行排序。

3) 遍歷熱點網(wǎng)格集合，對熱點網(wǎng)格集合中網(wǎng)格可達(dá)的網(wǎng)格單元進(jìn)行合并，形成熱點區(qū)域集合。

GScan算法偽代碼如下所示：

輸入：

空間數(shù)據(jù)集合Sd={p1,p2,…,pn}，網(wǎng)格單元的大小k，網(wǎng)格單元的密度閾值λ

輸出：

熱點區(qū)域的集合O={HA1,HA2,…，HAm}

算法步驟：

1：初始化哈希表HT為空；

2：for each pi∈Sddo

3： 計算得到集合中的最小、最大經(jīng)緯度值，確定區(qū)域范圍D；

4：end for

5：for each pi∈Sddo

6： 根據(jù)定義4中的映射函數(shù)計算其所屬網(wǎng)格索引index；

7： if index∈HT then

8： 將pi插入鍵值index對應(yīng)的列表；

9： else

10： 以網(wǎng)格索引index為鍵，將包含數(shù)據(jù)點pi的列表插入哈希表HT；

11： end if

12：end for

13：初始化熱點網(wǎng)格集合G為空;

14：for each k∈HT do

15： if |HT(k)| <λthen

16： continue；

17： else

18： 將其寫入集合G；

19： end if

20：end for

21：G <-根據(jù)網(wǎng)格密度對集合G進(jìn)行逆序排序；

22：初始化i等于0，集合O為空；

23：while G≠? do

24： 初始化集合HAi；

25： 將集合G中第一個元素等于G1插入HAi，并將其從G中刪除；

26： if G≠? then

27： for each g∈G do

28： for each h∈HAido

29： if Dis(g,h)

30： 將網(wǎng)格g插入集合HAi；

31： 將網(wǎng)格g從集合G中刪除；

32： end if

33： end for

34： end for

35： end if

36： 將HAi插入集合O；

37： i自增1；

38：end while

End

在第1階段(第1行～第12行)，首先，算法遍歷原始空間數(shù)據(jù)集合，找到集合中的最大、最小經(jīng)緯度的值，從而確定區(qū)域，接著根據(jù)定義4的映射函數(shù)，將原始空間數(shù)據(jù)轉(zhuǎn)化為網(wǎng)格單元。第2階段(第13行～第21行)，遍歷網(wǎng)格單元集合，根據(jù)參數(shù)λ獲取集合中的熱點網(wǎng)格單元集合，并對熱點網(wǎng)格單元進(jìn)行排序，之所以進(jìn)行排序，是因為密度大的網(wǎng)格單元之間往往通過密度可達(dá)可以生成較大的熱點區(qū)域，將密度大的網(wǎng)格集中排列有利于減少對集合遍歷的次數(shù)。第3階段(第22行～第38行)，遍歷熱點網(wǎng)格集合，并對網(wǎng)格之間網(wǎng)格可達(dá)的網(wǎng)格進(jìn)行合并，形成熱點區(qū)域集合，算法結(jié)束。

GScan算法的總體流程如圖2所示。

圖2 GScan聚類算法流程圖

2.3 算法復(fù)雜度

通過分析GScan算法的執(zhí)行步驟，我們可以很容易地得出GScan算法的時間復(fù)雜度為O(n+m2)。其中，n代表數(shù)據(jù)集中GPS數(shù)據(jù)對象的數(shù)目，m表示通過劃分區(qū)域得到的網(wǎng)格單元的個數(shù)。GScan算法的時間復(fù)雜度是關(guān)于數(shù)據(jù)點數(shù)n的線性函數(shù)，與m成正比，然而，通常情況下，由于數(shù)據(jù)點n較大，并且網(wǎng)格單元有效地規(guī)約了數(shù)據(jù)點的數(shù)目，總是會有m小于或者遠(yuǎn)小于n。因此在最差情況下，GScan算法的時間復(fù)雜度為O(n+m2)，低于DBSCAN算法的時間復(fù)雜度O(n2)。

3 實驗分析

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

實驗中使用的數(shù)據(jù)集來源于重慶市10 000輛出租車GPS軌跡數(shù)據(jù)，數(shù)據(jù)的起始采集時間在2014年8月4日，終止時間在2014年8月17日，為期2周，共14天。其中，車載GPS設(shè)備數(shù)據(jù)采集的時間間隔范圍大約為15～20 s，每天每輛車的數(shù)據(jù)采集的時間涵蓋全天24小時，產(chǎn)生的數(shù)據(jù)量大約在3～5 GB大小(dmp數(shù)據(jù)格式)。每個數(shù)據(jù)記錄主要包括11個屬性，例如車輛的所處的經(jīng)度、緯度，數(shù)據(jù)采集時間和車輛載客狀態(tài)、車牌號、海拔高度、行駛的瞬時速度等信息。

首先，根據(jù)出租車載客狀態(tài)的變化，我們提取了數(shù)據(jù)中的上車點和下車點數(shù)據(jù)。具體方法是：將車輛原始軌跡數(shù)據(jù)按照車輛ID和時間排序，如果數(shù)據(jù)記錄的狀態(tài)由“空載”狀態(tài)變成“載客”狀態(tài)，那么這個軌跡點為上車點。反之，如果數(shù)據(jù)記錄的狀態(tài)由“載客”狀態(tài)變成“空載”狀態(tài)，那么這個軌跡點為下車點。除去噪聲數(shù)據(jù)等無效數(shù)據(jù)，我們一共從原始數(shù)據(jù)中提取了上下車數(shù)據(jù)，圖3是我們提取的上下車點數(shù)據(jù)通過百度地圖進(jìn)行可視化展示的結(jié)果。

圖3 載客/卸客點數(shù)據(jù)展示

3.2 性能對比實驗

為了說明GScan算法的有效性，本節(jié)特將GScan算法與DBSCAN算法進(jìn)行了性能對比分析。圖4展示了DBSCAN算法和GScan算法在不同規(guī)模數(shù)據(jù)量下運行時間的對比，實驗中我們對兩種算法設(shè)置了相同的參數(shù)。從圖中可以明顯的看到，當(dāng)數(shù)據(jù)量大約小于42 000時，DBSCAN算法的運行時間略低于GScan算法，這是因為GScan算法需將原始空間數(shù)據(jù)集合映射為網(wǎng)格單元，當(dāng)數(shù)據(jù)量較小時，數(shù)據(jù)的分布往往較為稀疏，將數(shù)據(jù)點轉(zhuǎn)化為網(wǎng)格并沒有很好地規(guī)約原始數(shù)據(jù)，相對于DBSCAN算法而言，網(wǎng)格映射便成了額外的步驟消耗了一定的時間。然而，當(dāng)數(shù)據(jù)量大于42 000時，隨著數(shù)據(jù)量的增加，GScan算法的運行時間呈現(xiàn)緩慢增長，逐漸體現(xiàn)出可伸縮性，這是因為大量的空間數(shù)據(jù)被網(wǎng)格單元所替換，替換產(chǎn)生的網(wǎng)格數(shù)量遠(yuǎn)遠(yuǎn)小于原始數(shù)據(jù)的數(shù)量，有效地減少了原始數(shù)據(jù)的規(guī)模，提高了計算的效率。同時，我們在實驗中發(fā)現(xiàn)GScan算法的時間消耗主要產(chǎn)生于網(wǎng)格映射階段，而網(wǎng)格映射階段可以通過數(shù)據(jù)劃分進(jìn)而對其進(jìn)行并行化處理。因此，對于不同規(guī)模的數(shù)據(jù)，我們將原始數(shù)據(jù)劃分為三份對網(wǎng)格映射操作進(jìn)行并行化，如圖4所示，相比為未并行化的GScan算法，并行化后的GScan算法計算速度平均提升了42.48%。

圖4 算法性能對比

3.3 熱點區(qū)域挖掘

利用基于網(wǎng)格密度的GScan算法，本節(jié)我們對重慶市的時空熱點區(qū)域進(jìn)行分析與挖掘。如圖5所示，圖中展現(xiàn)的是2014年8月4日到2014年8月17日重慶市出租車載客點與卸客點數(shù)據(jù)隨時間的分布情況。通過觀察并結(jié)合領(lǐng)域知識，我們可以將載客點與卸客點數(shù)據(jù)按照時間劃分為三個部分進(jìn)行分析：第一個部分是早上7點到早上11點，這個時段通常是人們出門上班的高峰期，乘車需求較大，在交通領(lǐng)域稱之為早間出行時段；第二部分是中午12點到下午16點，此時段出行需求分布相對比較均勻，一般稱之為午間出行時段；最后一部分是下午17點到晚上23點，此時段與早間出行時段相對應(yīng)，稱之為晚間出行時段，是人們下班回家、參與夜間活動的密集時段。

圖5 數(shù)據(jù)隨時間的分布

在對不同時段的熱點區(qū)域進(jìn)行分析和挖掘時，我們還需要對GScan算法中的參數(shù)進(jìn)行合理的設(shè)置，正如前文理論部分介紹的那樣，在GScan算法中主要有網(wǎng)格大小k以及網(wǎng)格密度閾值λ兩個參數(shù)，以早間出行時段的數(shù)據(jù)為例，圖6展示了設(shè)置不同的參數(shù)值對計算結(jié)果的影響。從圖6(a)和(c)中可以看出，對于給定的密度閾值λ，熱點區(qū)域的數(shù)量首先隨著網(wǎng)格大小k的增加而增加，當(dāng)熱點區(qū)域的數(shù)量達(dá)到某一最大值之后，隨著網(wǎng)格大小k的增加，熱點區(qū)域的數(shù)量逐漸減少。這一現(xiàn)象不難理解，因為當(dāng)k的值較小時，網(wǎng)格的密度往往難以滿足網(wǎng)格密度閾值的約束，因此產(chǎn)生了較少的熱點區(qū)域；而k值過大時，一些熱點區(qū)域被合并為更大的熱點區(qū)域，從而導(dǎo)致了熱點區(qū)域數(shù)量的減少。接著，我們再來看看網(wǎng)格密度閾值λ對結(jié)果的影響。從圖6(a)和(c)中可以明顯的看到，對于給定的網(wǎng)格大小k，較小的λ值產(chǎn)生了較多的熱點區(qū)域。結(jié)合圖6(b)和(d)熱點區(qū)域中數(shù)據(jù)的累積百分比分布進(jìn)行進(jìn)一步分析，我們發(fā)現(xiàn)：當(dāng)λ較小時，GScan算法得到大多是包含較少數(shù)據(jù)點的熱點區(qū)域，這些范圍較小的熱點區(qū)域占到了結(jié)果總數(shù)的85%以上，對于整個城市范圍來說，包含數(shù)十個點的熱點區(qū)域顯然是不合理的；而當(dāng)λ增大時，區(qū)域內(nèi)點的數(shù)量也逐漸增多，這說明較大的熱點區(qū)域被生成，并且隨著λ的增大熱點區(qū)域的數(shù)量逐漸減少，熱點區(qū)域的數(shù)量的變化的趨勢也趨于平穩(wěn)。例如在圖6(a)中，λ=135和λ=150有著相似的走勢，我們認(rèn)為此時計算得到的結(jié)果比較穩(wěn)定，具有較高的參考價值，因此在設(shè)置參數(shù)時中，我們可以取k=140，λ=135或λ=150。同理，對于卸客點數(shù)據(jù)而言，可以設(shè)置參數(shù)k=120，λ=150或λ=160。

圖6 參數(shù)分析

通過上述參數(shù)設(shè)置的方法，我們利用GScan算法對早間出行時段、午間出行時段，以及晚間出行時段的出行熱點區(qū)域進(jìn)行了挖掘，結(jié)果如圖7所示。從圖中我們明顯地可以看到，早間和午間的出行熱點區(qū)域相對比較集中，數(shù)量較少；而晚間的熱點區(qū)域相對比較分散，數(shù)量較多。這點與我們所掌握的常識是吻合的，因為白天人們往往處于工作狀態(tài)，出行的地點往往集中于城市的大型商圈和住宅區(qū)周圍，而晚間人們的活動較為豐富，活動的地點選擇也較多，所以熱點區(qū)域的分布也就相對分散。

圖7 熱點區(qū)域

為了進(jìn)一步分析熱點區(qū)域的時空分布特點，我們根據(jù)重慶市的功能區(qū)域特征將熱點區(qū)域劃分為商務(wù)區(qū)、住宅區(qū)、休閑娛樂場所、餐飲購物場所、醫(yī)療機(jī)構(gòu)、旅游景點、教育機(jī)構(gòu)、交通樞紐等8個類別。通過結(jié)合城市POI數(shù)據(jù)，我們發(fā)現(xiàn)：在早上，出行熱點區(qū)域主要集中在解放碑-江北嘴-彈子石等中央商務(wù)區(qū)，觀音橋商圈、紅旗河溝、兩路口等交通樞紐周圍，這些區(qū)域包含大量的商務(wù)區(qū)寫字樓、居民住宅區(qū)以及重要的交通設(shè)施，是人們早上出門上班的密集區(qū)域。除此之外，我們還注意到在這個時段諸如西南醫(yī)院等大型醫(yī)療機(jī)構(gòu)也是人流量較高的區(qū)域。在午間時段，由于時值暑假期間，除了一些中央商務(wù)區(qū)形成的熱點區(qū)域之外，南山植物園、三峽博物館、磁器口古鎮(zhèn)、洪崖洞等文化風(fēng)景區(qū)成了出行的熱點。同時，相比早間出行時段，楊家坪購物中心、南坪萬達(dá)廣場等一些娛樂購物場所附近的人流量也有了大幅度的增加。而在晚間時段，大型商務(wù)區(qū)和住宅區(qū)再次成為了乘車的熱點區(qū)域，然而，有所不同的是，龍湖時代天街、北城天街、三峽廣場、解放碑步行街等休閑娛樂、餐飲購物集中的場所成為了人們夜間活動的主要區(qū)域。

縱觀整天熱點區(qū)域的分布，重慶市的熱點區(qū)域主要集中在江北國際機(jī)場、重慶北火車站、觀音橋商圈、南坪商圈、沙坪壩商圈、楊家坪商圈、石橋鋪商圈以及兩路口交通樞紐等地，這些熱點區(qū)域在一天中具有較大的人流量，以及較高出行需求，是人們密集出行的直接體現(xiàn)。另一方面，這些熱點的分布也從一定程度上反映了重慶市“山城”的地理環(huán)境以及以商圈為核心的城市發(fā)展策略。

4 結(jié) 語

本文基于網(wǎng)格密度的思想提出了一種城市中熱點區(qū)域的探測方法。該方法通過劃分城市網(wǎng)格單元將大量空間數(shù)據(jù)離散化，相比已有方法，該方法能夠有效提升計算的效率和伸縮性。在此基礎(chǔ)之上，本文采用真實的出租車軌跡數(shù)據(jù)進(jìn)行了實驗分析，對方法中的參數(shù)設(shè)置做了討論，進(jìn)一步結(jié)合POI數(shù)據(jù)和時空因素對重慶市人們的出行行為進(jìn)行了挖掘，實驗結(jié)果驗證了該方法的可行性。需要指出的是，受限于實驗數(shù)據(jù)來源，本文實驗僅使用出租車軌跡來分析城市熱點區(qū)域與居民通勤的時空模式還具有一定的局限性。未來的研究可將各種導(dǎo)航定位終端產(chǎn)生的用戶歷史軌跡數(shù)據(jù)、個人情感數(shù)據(jù)和天氣數(shù)據(jù)相融合更加詳盡地分析城市中人們的頻繁活動的熱點區(qū)域。

[1] 齊觀德,潘綱,李石堅,等.當(dāng)出租車軌跡挖掘遇見智能交通[J].中國計算機(jī)學(xué)會通訊,2013,9(8):30-36.

[2] Castro P S,Zhang D,Chen C,et al.From taxi GPS traces to social and community dynamics:A survey[J].ACM Computing Surveys (CSUR),2013,46(2):17.

[3] Ziebart B D,Maas A L,Dey A K,et al.Navigate like a cabbie:probabilistic reasoning from observed context-aware behavior[C]//UBICOMP 2008:Ubiquitous Computing,International Conference,Seoul,Korea,September 21-24,2008,Proceedings.DBLP,2008:322-331.

[4] Yuan J,Zheng Y,Xie X,et al.T-drive:Enhancing driving directions with taxi drivers’ intelligence[J].IEEE Transactions on Knowledge and Data Engineering,2013,25(1):220-232.

[5] 連德富.基于位置社交網(wǎng)絡(luò)的數(shù)據(jù)挖掘[D].中國科學(xué)技術(shù)大學(xué),2014.

[6] Yuan W,Deng P,Taleb T,et al.An unlicensed taxi identification model based on big data analysis[J].IEEE Transactions on Intelligent Transportation Systems,2016,17(6):1703-1713.

[7] Zheng Y,Liu Y,Yuan J,et al.Urban computing with taxicabs[C]//Proceedings of the 13th international conference on Ubiquitous computing.ACM,2011:89-98.

[8] Pan G,Qi G,Wu Z,et al.Land-use classification using taxi GPS traces[J].IEEE Transactions on Intelligent Transportation Systems,2013,14(1):113-123.

[9] Zheng Y,Capra L,Wolfson O,et al.Urban Computing:Concepts,Methodologies,and Applications[J].Acm Transactions on Intelligent Systems & Technology,2014,5(3):1-55.

[10] 石飛,陸建,王煒,等.居民出行調(diào)查抽樣率模型[J].交通運輸工程學(xué)報,2004,4(4):72-75.

[11] Zhang M,Liu J,Liu Y,et al.Recommending Pick-up Points for Taxi-drivers Based on Spatio-temporal Clustering[C]//IEEE,International Conference on Cloud and Green Computing.IEEE Computer Society,2012:67-72.

[12] Gui Z,Yu H.Mining traffic hot spots from massive taxi trace[J].Journal of Computational Information Systems,2014,10(7):2751-2760.

[13] 王亮,胡琨元,庫濤,等.隨機(jī)采樣移動軌跡時空熱點區(qū)域發(fā)現(xiàn)及模式挖掘[J].吉林大學(xué)學(xué)報:工學(xué)版,2015(3):913-920.

[14] Tang J,Liu F,Wang Y,et al.Uncovering urban human mobility from large scale taxi GPS data[J].Physica A Statistical Mechanics & Its Applications,2015,438:140-153.

[15] 王培安,羅衛(wèi)華,白永平.基于空間自相關(guān)和時空掃描統(tǒng)計量的聚集比較分析[J].人文地理,2012(2):119-127.

[16] 李小洲,王勁峰.空間掃描統(tǒng)計量方法中候選聚集區(qū)域生成的快速算法[J].地球信息科學(xué)學(xué)報,2013,15(4):505-511.

[17] 周勍,秦昆,陳一祥,等.基于數(shù)據(jù)場的出租車軌跡熱點區(qū)域探測方法[J].地理與地理信息科學(xué),2016,32(6):51-56.

[18] Rong H,Zhou X,Yang C,et al.The Rich and the Poor:A Markov Decision Process Approach to Optimizing Taxi Driver Revenue Efficiency[C]//ACM International on Conference on Information and Knowledge Management.ACM,2016:2329-2334.

[19] Chen C,Zhang D,Castro P S,et al.iBOAT:Isolation-Based Online Anomalous Trajectory Detection[J].IEEE Transactions on Intelligent Transportation Systems,2013,14(2):806-818.

[20] Yang W,Wang X,Rahimi S M,et al.Recommending Profitable Taxi Travel Routes Based on Big Taxi Trajectories Data[M]//Advances in Knowledge Discovery and Data Mining.Springer International Publishing,2015:370-382.