李艷云，牛保寧，康家興

(太原理工大學 信息與計算機學院，太原 030024)

時空熱點是指交通流量較大、居民來往次數較多的時空區(qū)域。不同于二維平面區(qū)域，時空熱點是特定的三維空間,是具有時間信息的熱點地理區(qū)域，如7:00-9:00的長風街是時空熱點，但其他時間段的長風街有可能不是時空熱點。本文以出租車軌跡數據為對象，通過對其進行時空分析[1]和數據挖掘[2]，從而發(fā)現城市時空熱點[3-4]。城市時空熱點發(fā)現對城市規(guī)劃[5]、交通管理、打擊犯罪等一系列基于位置的服務有重要的參考價值。

為此，針對第一階段map-reduce嚴重耗時及資源空閑的問題，本文提出一種對軌跡數據采樣的方法S-RSampling.通過分析軌跡數據隨時間的變化，得到其分布規(guī)律，確定采樣分層數和采樣比例。在每條軌跡數據映射成〈k,v〉時，根據其分層數、分層比例進行采樣，大幅度降低查詢時間。為降低任務空閑等待時間，在k值相同的〈k,v〉聚合時，對所有〈k,v〉隨機采樣，緩解數據分布不均勻的影響，減少資源等待時間。針對第二階段map-reduce計算浪費的問題，本文提出一種閾值過濾方法TFiltering.根據單元格屬性值的分布，動態(tài)確定閾值T，并將屬性值從大到小排序top-T的立方單元格作為熱點候選集，僅計算熱點候選集中立方單元格的熱度值，從而減少計算浪費，提高時空熱點查詢效率。本文的創(chuàng)新點如下。

1) 提出一種對軌跡數據采樣的方法S-RSampling.在軌跡數據映射成〈k,v〉時，根據軌跡數據分布規(guī)律分層采樣，大幅降低查詢時間；在k值相同的〈k,v〉聚合時，為減少資源等待時間，對所有〈k,v〉隨機采樣，緩解數據分布不均勻的影響。

2) 提出一種閾值過濾方法TFiltering.探索出一種確定閾值的方法，依據立方單元格屬性值的分布規(guī)律,動態(tài)確定閾值T；選擇熱點候選集，將屬性值從大到小排序top-T的立方單元格，作為熱點候選集，減少計算浪費，提高時空熱點查詢效率。

1 研究現狀

時空熱點查詢在ACM SIGSPATIAL GISCUP 2016編程競賽[11]中被要求提出高效、快速的算法，以實現對紐約市出租車軌跡數據的熱點分析，開發(fā)運行于Spark分布式集群的map-reduce算法。目前，對于這類高效時空熱點查詢的研究并不多，其思想都是基于Spark分布式計算框架和Getis-Ord公式的熱度統(tǒng)計法。根據應用場景不同，可以將現有算法分為兩類，一類是無約束條件的查詢，這類查詢不需要用戶指定查詢參數,而是對全部軌跡數據進行一次性計算；另一類是有約束條件的多參數查詢，這類查詢可以由用戶指定查詢參數，如地理范圍、時間范圍等，針對不同的查詢參數處理不同的軌跡數據，返回用戶指定個數的時空熱點。

無約束條件類算法中，NIKITOPOULOS[12]提出BigCAB算法，嚴格遵循熱度統(tǒng)計法思想，將每個立方單元格作為RDDs元素，每一步都精確計算。SALLES et al[13]提出的K-H-CP算法在BigCAB算法基礎上將城市時空分區(qū)，將分區(qū)作為RDDs元素。因為大部分立方單元格及鄰居作為一個RDDs元素被存儲在同一節(jié)點中，所以在計算鄰居間相互影響時，節(jié)點間的通信開銷降低。PARAS et al[14]提出的STG算法與K-H-CP算法類似，該算法通過將時空鄰接的立方單元格組成25×25×25的組。一個組的立方單元格存儲在同一節(jié)點上，從而降低節(jié)點間的通信開銷。K-H-CP和STG算法都是通過改變RDDs元素來降低節(jié)點間的通信開銷，均為精確算法。不同于上述三個算法，SHANGFU et al[15]提出的SR-K-M算法是在BigCAB算法的基礎上加了過濾和細化策略。由于過濾掉大部分立方單元格，所以計算量和網絡通信開銷大幅度降低。

以上這些算法都需要對全部軌跡數據進行計算，由于軌跡數據量巨大，所以遍歷一遍軌跡數據是造成整個查詢過程耗時的主要原因。而且對于數據分布不均導致的資源空閑等待，以及計算大量無用立方單元格造成計算浪費的問題，上述算法沒有相應的優(yōu)化。

有約束條件的多參數查詢算法如康家興等[16]提出的多參數城市時空熱點查詢，該算法對軌跡數據建立三維網格索引，能靈活地滿足不同的查詢。根據用戶指定的不同參數，處理不同的軌跡數據，返回用戶指定個數的時空熱點。雖然處理不同的軌跡數據，但仍要對相應的全部軌跡數據進行一次遍歷，當所需的軌跡數據量較大時，耗時問題仍然存在。而且對于計算浪費問題，該算法沒有相應優(yōu)化策略。

2 預備知識

2.1 Getis-Ord公式

Getis-Ord統(tǒng)計量常用來進行熱點分析，其計算公式如下：

(1)

(2)

(3)

(4)

2.2 熱度統(tǒng)計法

熱度統(tǒng)計法是將城市時空按設定好的單元格粒度，劃分為若干相同大小的立方單元格，根據坐標映射公式，將軌跡數據映射到立方單元格中，統(tǒng)計立方單元格的屬性值，利用Getis-Ord公式計算出各立方單元格的熱度值。

出租車軌跡數據p記錄了乘客下車經緯度、下車時間點以及乘客數等有用信息。將這些重要信息提取出來用(plon,plat,pt,pv)表示，(plon,plat)表示下車位置經緯度信息；pt表示下車時間點，記錄了年、月、日、和時間等信息；pv表示乘客數。

軌跡數據p到立方單元格坐標(x,y,t)(x,y分別表示經緯度坐標軸，t表示時間軸)的映射公式為：

{p→(x,y,t)|x=?plon/x0」,

y=?plat/y0」,t=?pt/t0」} .

(5)

式中：x0，y0，t0分別為單元格經度、緯度和時間軸劃分粒度[16]。

熱度統(tǒng)計法的大致流程如圖1所示。第一階段map-reduce：map函數根據坐標映射公式將每條軌跡數據映射到立方單元格中，即將軌跡數據處理成〈k,v〉(其中k表示單元格坐標(x,y,t)，v表示乘客數)；reduce函數將k相同的〈k,v〉聚合得到〈k,vnum〉，計算出各立方單元格的屬性值vnum(即公式(1)中的xj).

圖1 基于Getis-Ord公式的熱度統(tǒng)計法流程圖Fig.1 Flowsheet of heat statistics method based on Getis-Ord formula

3 優(yōu)化方法

針對現有算法存在的第一階段map-reduce耗時且效率低，以及第二階段map-reduce計算浪費的問題，本文提出一種對軌跡數據采樣的方法S-RSampling和一種閾值過濾方法TFiltering.為了方便后續(xù)理解，先解釋現有算法第一階段map-reduce的具體步驟。

1) 從hdfs(即Hadoop分布式文件系統(tǒng))讀取軌跡數據。

2) 用map()函數將每條軌跡數據根據坐標映射公式處理成〈k,v〉的形式。相同k對應的〈k,v〉不止一個，因為多條軌跡數據會映射到同一個立方單元格中。

3) 通過reduceBykey()函數將k值相同的〈k,v〉聚合成〈k,vnum〉.〈k,vnum〉代表坐標為k的立方單元格屬性值為vnum.

由于算法是查詢top-k時空熱點，只需對單元格的熱度值進行排序，不需要計算出每個單元格的實際熱度值，所以不一定要對全部軌跡數據進行處理。另外，由于軌跡數據量巨大，每條軌跡被映射成〈k,v〉后，數據量仍然很大，而且數據分布不均勻導致計算效率降低。為此，本文提出S-RSampling方法。該方法分為兩步，第一步是在步驟2)之前，對軌跡數據進行規(guī)律采樣。具體地，分析軌跡數據隨時間的分布規(guī)律，根據其分布規(guī)律確定采樣分層數及采樣比例，按分層數和比例對軌跡數據進行分層采樣，使得樣本能夠反映全部軌跡數據的分布。第二步是在步驟2)之后，對〈k,v〉數據進行隨機采樣。具體地，通過Sample算子對〈k,v〉數據進行隨機采樣，每個〈k,v〉被采到的概率相同。

3.1 S-RSampling方法

S-RSampling方法分為兩步，第一步是在軌跡數據映射前，根據軌跡數據分布規(guī)律，對軌跡數據進行分層采樣，稱為規(guī)律采樣。第二步是在軌跡數據映射后(即map后)，對〈k,v〉數據進行隨機采樣，稱為map隨機采樣。

3.1.1規(guī)律采樣

本文根據時間找到軌跡數據分布規(guī)律并依據分布規(guī)律進行采樣。在針對同樣數據集的其它熱點查詢任務中，直接根據其分布規(guī)律進行采樣，極大地降低查詢時間。出租車軌跡數據包含下車經緯度、下車時間點以及乘客數等字段。根據下車時間點字段將軌跡數據以1 h為單位分割成24份，分別統(tǒng)計每個時間段內的乘客數。具體步驟如下：

1) 從hdfs讀取軌跡數據；

2) 分割軌跡數據的每個字段；

3) 取出下車地點經緯度、時間、乘客數等重要信息；

4) 根據時間字段的空格分割數據，并統(tǒng)計每個時間段內的乘客數。

對12個月的數據進行實驗，取平均值得到一天(24 h)中不同時間段的軌跡數量，從而得到軌跡數據隨時間的分布規(guī)律，如圖2所示。橫軸代表時間，縱軸代表軌跡數據數量。實驗中不會特殊考慮周末節(jié)假日等軌跡數量峰值的時間段情況。這是由于一方面將軌跡數據中的時間字段轉換成周末節(jié)假日等信息需要大量的額外消耗；另一方面周末節(jié)假日的軌跡數量本來就比較多，按比例采樣時周末節(jié)假日數據被采到的概率本來就大，所以不需要特殊處理周末節(jié)假日的數據。

圖2 軌跡數據數量隨時間分布圖Fig.2 Distribution of trajectory data over time

根據分布圖的極小值點，本文將軌跡數據根據極小值點對應的時間劃分為l1,l2,…,lm+1(m為極小值個數)多層，統(tǒng)計各層軌跡數據數量之比r1∶r2∶…∶rm+1.規(guī)律采樣策略對l1,l2,…,lm+1層的軌跡數據進行r1∶r2∶…∶rm+1分層采樣，使得樣本符合原始軌跡數據的分布規(guī)律，保證使用小數據集也能得到精確的結果。規(guī)律采樣過程如算法1.

算法1規(guī)律采樣算法

輸入：不同層的軌跡數據和采樣比例

輸出：分層采樣后的軌跡數據

/*從hdfs讀取不同層的軌跡數據，rdd1、rdd2和rdd3為不同層數據*/

1) val rdd1 = sc.textFile ("hdfs://master:9000 /input/2015green/1green")

2) val rdd2 = sc.textFile ("hdfs://master:9000 /input/2015green/3green")

3) val rdd3 = sc.textFile ("hdfs://master:9000 /input/2015green/6green")

/*對不同層數據進行分層采樣，并合并，以便后續(xù)將不同數據一同處理，rdd5為合并后的數據集*/

4) val rdd4 = rdd1.sample(false,r1).union (rdd2.sample(false,r2))

5) val rdd5 = rdd4.union(rdd3.sample(false, r3))

6) rdd5.saveAsTextFile("hdfs://master:9000/output/OutputRegular") /*保存數據*/

3.1.2map隨機采樣

由于軌跡數據量巨大，經過規(guī)律采樣后〈k,v〉仍舊很多，而且〈k,v〉數據分布不均勻造成計算效率低。本文在第一階段map后對所有〈k,v〉進行隨機采樣，減少計算量和資源等待時間。具體地，在第一階段map之后，通過Sample算子對這一階段產生的〈k,v〉進行隨機采樣，實驗中通過調整采樣率來比較查詢結果準確率。map隨機采樣計算過程描述如算法2.

算法2map隨機采樣算法

輸入：第一階段map后的〈k,v〉和采樣率

輸出：采樣后的〈k,v〉

1) val conf = new SparkConf().setAppName

2) val sc = new SparkContext(conf)

3) val rdd2 = rdd1.sample(false,r) /*rdd1為算法輸入的〈k,v〉，r為采樣率*/

4) rdd2.saveAsTextFile("hdfs://master:9000/output/OutputMap") /*保存數據*/

3.2 TFiltering方法

對12個月的數據進行實驗，得到立方單元格熱度值和數量的長尾分布，如圖3所示，橫軸代表立方單元格熱度值區(qū)間(×102)，縱軸代表立方單元格的數量(×104)。如熱度值在100到200的立方單元格有16萬多個。可以看出，大部分立方單元格的熱度值很小，計算這些不可能成為時空熱點的立方單元格，無疑會造成計算浪費。

圖3 單元格熱度值與數量分布圖Fig.3 Distribution of cubes,heat and number

3.2.1閾值確定方法

由于立方單元格的熱度值越大其屬性值通常也較大，所以根據單元格的屬性值選擇熱點候選集。具體地，本文在第一階段map-reduce后將立方單元格根據屬性值從大到小排序得到單元格屬性值的分布規(guī)律，如圖4(數據量為12個月)，橫軸代表單元格編號(單元格按屬性值從大到小的排序編號)，縱軸代表單元格屬性值。計算分布曲線的拐點坐標(xid,yvalue)，并將xid作為閾值基數。

圖4 單元格屬性值分布Fig.4 Distribution of cubes,value

考慮兩種極端情況：一是top-xid個單元格緊密相鄰；二是top-xid個單元格互不相鄰，互不影響。

第一種情況，屬性值排序top-xid的單元格中，除了極少數邊界單元格，其余單元格的鄰居貢獻都能在這xid個單元格中計算得到，所以本文取xid作為閾值，屬性值排序top-xid的單元格作為熱點候選集。

第二種情況，屬性值排序top-xid的單元格中，每個單元格鄰居貢獻的計算都需要額外的26個鄰居單元格，所以本文取27xid作為閾值，屬性值排序top-27xid的單元格作為熱點候選集。

綜合上述兩種情況，本文取閾值T為兩種極端情況下的平均值(xid+27xid)/2，即14xid.數據集不同，分布曲線就不同，所以閾值T也不同，閾值T隨著數據集的不同而動態(tài)變化。實驗表明，這種閾值選取方法在不同數據集下的算法結果準確率為100%.閾值選取的具體步驟如下：

1) 將單元格按屬性值從大到小排序；

2) 得到單元格屬性值分布曲線f(x)；

3) 計算曲線f(x)的拐點坐標(xid,yvalue)；

4) 根據T=14xid，計算得到閾值T.

3.2.2熱點候選集的選取

在確定了閾值T后，根據單元格屬性值和閾值選取熱點候選集。具體地，對map隨機采樣后的數據進行聚合，并對聚合得到的〈k,vnum〉，按vnum值從大到小對立方單元格排序，將top-T的立方單元格作為時空熱點候選集。熱點候選集選擇過程如算法3.

算法3熱點候選集選擇

輸入：map隨機采樣后的〈k,v〉和閾值T

輸出：熱點候選集〈k,vnum〉

1) val rdd2 = rdd1.reduceByKey((x,y)=〉x+y) /*對輸入的數據rdd1按k進行聚合*/

2) val rdd3=rdd2.sortBy(_._2,false)/*對聚合后的數據rdd2按vnum進行排序*/

3) val rdd4=rdd3.top(T)/*取vnum排序top-T的單元格作為熱點候選集*/

4) rdd4.saveAsTextFile("hdfs://master:9000/output/OutputFilter") /*保存數據*/

4 實驗分析與驗證

本文實驗運行在Spark2.2.0集群，集群有2個實際工作節(jié)點，每個工作節(jié)點有2個核，4 G內存。實驗數據為2015年的紐約市出租車數據，約15×108條記錄，共計約24 G，覆蓋范圍為緯度40.5 N-40.9 N，經度73.7 W-74.25 W.本文實驗中立方單元格劃分了約36×104個，經緯度和時間方向網格粒度分別為：200 m、200 m和2 h.實驗評價指標為結果準確率和查詢響應時間。為了在實驗結果中方便書寫，這里將規(guī)律采樣、map隨機采樣和閾值過濾分別用符號SS、RS和TF表示。

4.1 規(guī)律采樣

為了比較不同采樣率下算法的查詢響應時間和結果準確率，本文進行了多種規(guī)律采樣率下的對比實驗。通過實驗發(fā)現，在采樣率為10%的情況下，查詢響應時間和結果準確率達到較好的平衡，實驗結果如表1所示。

表1 規(guī)律采樣采樣率選取Table 1 Selection of regular sampling rate

為了驗證規(guī)律采樣的有效性，本文分別對BigCAB算法與加入SS(采樣率為10%)的BigCAB算法、STG算法與加入SS(采樣率為10%)的STG算法進行對比實驗。在不同數據量下對查詢響應時間進行比較，實驗結果如圖5所示(橫軸表示數據量，以月份數量代表數據量大小，縱軸表示查詢響應時間，下同)。加入SS的BigCAB算法較BigCAB算法查詢響應時間平均降低34.0%，最大降低42.3%；加入SS的STG算法較STG算法查詢響應時間平均降低34.8%，最大降低41.0%.

這是因為，本文根據分層數和分層比例對原始軌跡數據進行合理采樣，使采樣得到的數據能較好地代表原始數據。從而，在不降低查詢結果準確率的基礎上，大幅減低查詢響應時間。

圖5 規(guī)律采樣實驗結果Fig.5 Experimental result of regular sampling

4.2 map隨機采樣

為了比較在第一階段map后，隨機采樣在不同采樣率下算法的查詢響應時間和結果準確率，本文在無規(guī)律采樣的基礎上進行了多種隨機采樣率下的對比實驗。通過實驗發(fā)現，在采樣率為10%的情況下，查詢響應時間和結果準確率達到較好的平衡，實驗結果如表2所示。

表2 map隨機采樣采樣率選取Table 2 Selection of map random sampling rate

為了驗證map隨機采樣的有效性，本節(jié)對BigCAB算法以及加入各優(yōu)化策略的BigCAB算法、STG算法以及加入各優(yōu)化策略的STG算法進行對比實驗(采樣率均為10%)。在不同數據量下比較查詢響應時間，實驗結果如圖6所示。加入RS的BigCAB算法較BigCAB算法查詢時間平均降低25.7%，最大降低35.2%；加入SS和RS的BigCAB算法較BigCAB算法查詢時間平均降低43.7%，最大降低52.3%；加入RS的STG算法較STG算法查詢時間平均降低25.2%，最大降低31.0%；加入SS和RS的STG算法較STG算法查詢時間平均降低43.3%，最大降低49.5%.

因為規(guī)律采樣后的數據較好地代表了原始軌跡數據，映射后的〈k,v〉數據也具有代表性?？紤]到需要降低查詢響應時間，本文僅對〈k,v〉數據進行簡單的隨機采樣。所以能在查詢結果準確率不下降的情況下，減少查詢響應時間。

圖6 map隨機采樣實驗結果Fig.6 Experimental result of map random sampling

4.3 閾值過濾

為了驗證閾值過濾的有效性，本文對BigCAB算法與加入各優(yōu)化策略的BigCAB算法、STG算法與加入各優(yōu)化策略的STG算法(采樣率均為10%)在不同數據量下進行查詢響應時間對比實驗，實驗結果如圖7所示。加入TF的BigCAB算法較BigCAB算法查詢響應時間平均降低31.3%，最大降低43.3%；加入SS、RS和TF的BigCAB算法較BigCAB算法查詢響應時間平均降低55.4%，最大降低58.7%；加入TF的STG算法較STG算法查詢響應時間平均降低30.5%，最大降低43.0%；加入SS、RS和TF的STG算法較STG算法查詢響應時間平均降低54.9%，最大降低58.3%.

由于熱點區(qū)域周圍通常也較熱，熱點單元格不可能存在于熱度值都小的區(qū)域。所以，存在大量不可能成為時空熱點，且對鄰居單元格的貢獻沒有意義的單元格。本文通過閾值過濾，將這些無用的立方單元格過濾，減少計算浪費，從而在查詢結果準確率不降低的情況下，減少了查詢響應時間。

圖7 閾值過濾實驗結果Fig.7 Experimental result of threshold filter

5 總結與展望

本文針對現有算法對全部軌跡數據遍歷耗時巨大，以及單元格熱度值與數量呈現長尾分布導致的效率低和計算浪費等問題，提出如下優(yōu)化方法：一是對軌跡數據采樣的方法S-RSampling，一是閾值過濾方法TFiltering.通過對軌跡數據進行規(guī)律采樣，避免對全部數據的遍歷，大幅降低時間消耗。map隨機采樣減少〈k,v〉數據量，減少shuffle傳輸開銷以及reduce計算量，緩解數據分布不均勻導致計算效率低的問題；找到一種確定閾值的方法，通過閾值過濾選擇熱點候選集，減少對不可能成為時空熱點的立方單元格的計算，避免計算浪費。對于具有相同數據集的熱點查詢任務，使用上述優(yōu)化策略能在保證結果準確率的基礎上有效降低查詢時間。不足之處是鄰居貢獻的計算耗費存儲空間，計算鄰居貢獻時所需的空間是第一階段map-reduce后〈k,v〉數據所占空間的27倍，后續(xù)將繼續(xù)研究，找到一種能簡化鄰居貢獻的代替Getis-Ord公式的方法。