結合Canopy-K-means算法和出租車軌跡數據的公交車站預測方法

劉 旭，陳云波，施 昆，黃 強

(1. 昆明理工大學，云南 昆明 650093； 2. 昆明市規劃編制與信息中心，云南 昆明 650500； 3. 成都理工大學，四川 成都 610059)

隨著城市化進程的加快、城市規模的急劇擴張、人口數量的迅猛增長，公共交通對居民出行的意義顯得越來越重要[1]。據統計，公共交通在城市中肩負著20%的全方位出行比例，并且這一比例仍在提升中[2]。為了在有限的空間中讓公共交通的作用全部發揮，公交站點的合理選取和預測顯得至關重要。出租車GPS數據是由每一臺搭載衛星定位系統的出租車在一定的時間間隔點獲取的，它能客觀真實地反映居民出行乘車的熱點區域、道路暢通情況、居民出行高峰期等[3]。因此，用其預測公交站點位置已經成為研究的熱點。

目前，國內外許多學者基于出租車GPS數據展開了各種研究。針對公共交通站點預測，主要包括以下3個方面：①基于采集的實時GPS數據，針對公交車到站時間進行研究。如周雪梅等[7]通過采集的實時車輛定位信息，并考慮潛藏的平均瞬時速度及停留時間，建立了基于前車的預測模型，提出一種可能發生的延誤模型；王武等[8]基于出租車軌跡數據改進了基于密度的聚類算法(DBSCAN)，找到上下車的具體位置，通過這種方法發現熱點出行區域并判斷公交車的候選地址。②通過研究客源的分布特征，預測客流量情況。Koshy和Arasan考慮公交站點的構成，開發了一個仿真擬模型來檢驗公交站點對交通流的影響[9]。③通過建立回歸模型和預測模型對公共交通站點進行預測。周洋等[9]考慮網絡節點的拓撲關系、路徑和軌跡密度，構建了一種街道網絡的基于移動軌跡數據提取網絡位置關鍵功能的地理空間方法。

綜上所述，雖然各種研究方法都對公交車站作了相關預測,但少有對公交車路線中各個站點位置的合理預測，以及公交車發車最優時間的預測。本文在已有的研究基礎上，提出一種基于Canopy-K-means算法的公交車站預測方法。以武漢市13 d的出租車軌跡數據作為研究對象，取乘車點坐標數據作為研究內容，通過高效聚類獲取居民出行熱點區域，并采用數據統計和對比分析的方法預測公交站點分布的合理性和高峰期公交的發車時間間隔，為緩解交通擁堵現象和決策者合理分配公共交通資源提供決策輔助。

1 方 法

1.1 總體設計

為了預測公交站點位置，需要先找到居民出行的熱點區域，再結合統計數據進行分析。本文基于出租車數據設計的公交車站方法如下：首先使用Hadoop分布式處理平臺對海量GPS數據進行處理，得到居民出行點數據，以提取數據記錄中每臺車狀態變化的臨界點作為出行點坐標數據[11]；其次引入Canopy-K-means改進聚類算法，將提取出的出行熱點區域按一定的參數進行聚類，獲取出行熱點區域；然后將出行熱點區域中心點與已有的公交站點進行對比，分析已有公交站點的合理性，預測公交站臺設定點的合理位置；最后結合數理統計方法，統計1 d中12個時段(每個時段2 h)的出行總量，預測公交車合適的發車頻率。設計原理如圖1所示。

圖1 方法流程

1.2 基于Hadoop的Canopy-K-means算法原理

1.2.1 K-means算法

K-means算法是一種基于距離的聚類算法。簇的個數k由使用者提前給定，每一個簇是通過其質心(centroid)，即每個簇的中心點來描述。

K-means算法的工作流程為：首先隨機確定k個初始點作為質心，然后將數據集中的每個點都分配到一個滿足條件的簇中，即為每個點尋找距離其最近的質心，并將其分配給該質心所對應的簇。該步完成后，每個簇的質心更新為該簇中所有點的坐標的平均值[12]。K-means算法是聚類算法中使用最為廣泛的算法之一，其用到的數學思想簡單，但效率高，且在對“圓形-球形”性質集合進行分類時，可以達到良好的聚類結果[13]。

K-means算法雖然高效，但缺點也很明顯，主要分為兩個方面：

(1) 中心點k個數的選取存在隨機性，難以界定，對于需要處理的海量數據，無法判斷數據中所有簇的個數。

(2) 使用這種算法對計算機的資源占用太高，計算每個點到中心點的距離時存在太多冗余。如果計算機資源消耗巨大，可能存在計算機死機的危險。

本文針對傳統K-means算法主要的兩個缺點進行改進，引入一種改進的K-means算法，提高算法聚類性能。

1.2.2 Canopy-K-means算法

傳統的K-means算法由于初始聚類中心選擇的隨機性，算法結果隨著中心點選擇的不同而改變，最終會導致結果的不穩定性，因此可能會造成聚類結果的最優值不穩定的問題[14]。Canopy-K-means聚類算法是通過引入Canopy算法，初始化K-means算法的聚類中心，形成無數個相互重疊的簇，不在簇的范圍內包含的點則視為噪聲點被剔除。不斷迭代多次后，簇的中心不斷變化直至收斂，得到每個簇的中心點，中心點數據則被視為K-means數據的中心點。這樣在聚類過程中，減少了隨機中心點選取對聚類結果的主觀影響。整個聚類流程如圖2所示。

由圖2可知，算法步驟為：

(1) 創建Job1,使用Canopy算法進行聚類。首先，在Map-reduce中創建第一個工作任務Job1。給定數據集A作為Canopy算法中心，并給Canopy算法指定閾值T1、T2(T1、T2表示以A集合中的點為中心的圓的半徑)，再使用算法對數據集A=(a1，a2，…，an)進行聚類，收斂的迭代中心，即為聚類中心。

(2) 明確每個點所屬類別。這里的類別指中心點所在的區域。若數據點Xi距Canopy的中心點Ai的距離小于T2，則認為Xi屬于Ai類；若數據點Xi距中心點Ai的距離小于T1，則數據點Xi可能屬于多個Ai,這時判斷Xi距離哪個Ai最近則認為Xi屬于該Ai。

圖2 算法流程

(3) 得到K-means算法中心點。對步驟(2)得到的每個簇中的所有點求均值，把它們作為K-means算法的中心。

(4) 合并K-means中心。這一步是為了降低步驟(1)中確定T1、T2時的誤差。由于半徑過小會導致聚類后的中心點過多的問題，因此選擇一定的范圍，將中心點間距離過小的點合并求均值，即為K-means的中心點。

(5) 創建Job2,循環迭代產生Canopy中心，直至收斂。設立Flag作為判斷依據，將步驟(4)中得到的中心點作為Canopy中心，產生新的簇。若收斂Flag值為true，則不需要再處理；若Flag值為false，證明還沒有收斂，再代入步驟(2)中開始執行，直至收斂。該過程命名Job2,后面名稱依次加1，作為文件命名，并且記錄算法循環次數。

(6) 對每個Canopy內的點使用K-means算法進行精確聚類，這樣就能避免傳統的算法中對所有點進行精確聚類而產生的計算機開銷過大的情況，從而求得熱點出行區域。

Canopy-K-means算法在Hadoop上運行流程，如圖3所示。

1.2.3 如何預測公交車站點和發車時間間隔

公交車站不合理分布會導致道路交通阻塞、客流量流通停滯等多方面危害[15]。在上文聚類中得到了乘客出行的熱點分布區域，公交站點則最好設置在熱點區域附近，才能有效緩解道路交通壓力。通過對熱點區域和已有站點的坐標位置進行對比，使用歐式距離，求得公交站點與聚類中心點的距離，從而有效分析公共交通站點分布的合理性。

圖3 Canopy-K-means算法在Hadoop上的運行流程

利用上車點軌跡數據，將一天的時間分為12個不同時間段，統計每個時段內的客流量，分析客流量高峰存在的時間段和出現的原因。引入分析公式(1)，變量H表示客流總量，D表示車載總數，M為劃分統計段的分鐘數，求得最佳時間間隔t(保留整數),0.2為公交車承載量占總量的百分比。

(1)

2 試 驗

2.1 數據集

本文研究數據主要是基于2014年7月31日—2014年8月12日13 d的武漢市出租車軌跡數據，約3172萬條，見表1。原始數據包含車輛ID、記錄時間、車輛坐標經度、車輛坐標緯度、車輛速度、車頭方向、車輛狀態等12個字段信息。安裝在出租車上的GPS信號接收器以30 s/次的采樣速度采集數據。表1展示了數據記錄模板。為了保護數據隱私，將經緯度坐標部分內容用“***”表示。車輛狀態表示出租車是否載客，包括“1”和“0”值。“1”值意味著出租車有乘客，而“0”值意味著出租車里沒有乘客。原始出租車軌跡數據必須經過數據過濾，主要包括兩個方面：①出租車大多在市區活動，高層建筑容易影響GPS信號并阻礙信號的接收；②GPS接收機在通過地下隧道時不能接收信號，因此信號會中斷[16]。

表1 出租車GPS數據的樣本記錄

由于這些問題，需要對原始數據進行預處理，步驟如下：①驗證經緯度屬性，查詢緯度和經度數據是否在有效區域內。以武漢為研究區，武漢市的全緯度和經度范圍為：經度113°41′—115°05′E和緯度29°58′—31°22′N。②需要核實旅客的狀態，出租車的載客狀態是“0”或“1”，刪除了不在這個范圍內的數據。③根據所選擇的公交線路，找出該地區的出租車數據。本文以武漢580公交線(如圖4所示)為試驗對象，公交線路位于武漢漢陽區(如圖5所示)，漢陽地區的數據足以支持整個試驗，提取30°28′35″—30°36′34″N，114°7′—114°18′E范圍內的數據。

圖4 武漢市580路公交車路線

圖5 武漢市漢陽區

2.2 公交車站點合理性分析

使用13 d內武漢市2046輛出租車的軌跡數據，并提取乘客在出租車上的坐標作為基本數據。利用Canopy-K-means均值聚類算法，分析了武漢市580條公交線路公交車站選址的合理性，并預測了公交站點的位置。分析過程分為以下兩個步驟：①利用Canopy-K-means均值聚類算法，對武漢市漢陽區所有乘客點的坐標數據進行聚類，得到580路公交線路上的聚類中心點，聚類中心用于確定乘客的熱點出行區域；②在地圖上對公交站點的坐標數據和聚類后的坐標數據(包括聚類中心)進行可視化顯示，并計算得到車站與集群中心之間的距離，然后進一步比較分析公交站點選址的合理性。

2.2.1 運用Canopy-K-means聚類算法確定聚類中心

首先，獲取出租車上車地點數據，對數據進行預處理后，數據已經按車輛ID和時間排列，需要通過Map-reduce分布式處理系統提取載客信息由0變成1的節點數據，即為上車點坐標數據。其次，Canopy-K-means聚類算法需要分兩步使用，Canopy算法聚類過程包含兩個參數T1、T2(T1>T2)，其中T1、T2都表示數據集中的點距Canopy算法中心點Ci的距離,若距離小于T1，則將軌跡數據點放入以Ci為中心的限定范圍中；若距離小于T1且小于T2,則將該點與Ci強關聯，在使用K-means算法時則不需要計算數據點到給定隨機點的距離，只需要計算數據點到Canopy中心點的距離即可。T1、T2的選取將影響聚類結果的效果。最后，經過多次迭代試驗，確定T1的值為500 m、T2的值為250 m時，得到的效果最佳。

基于預處理后的上車點坐標數據得到聚類結果，并將結果進行可視化顯示，如圖6所示。由于本文研究主要對比了580路公交線路中公交站點位置的合理性，因此選取580路公交線路附近的Canopy聚類中心點進行可視化顯示，否則顯示的數據太多，消耗的計算機資源過多，不利于試驗的順利進行。可以看到，在580路公交車路線上出現了不同形狀、不同位置的點集，特別地將聚類中心點用黑色點標注出來。

圖6 算法聚類結果

2.2.2 對比公交站點地址和聚類中心點，預測合理的公交車站點

將現有的23個公交站點在地圖上顯示(如圖7所示)，并和已獲取的一系列中心點對比，求得現有公交站點和聚類中心的距離Xi,若Xi距離小于10 m，則認為該站點符合出行公共交通路線選擇，若大于10 m，則認為該站點可以進行改進。試驗結果如圖8所示，23個公交站點中，Xi小于10 m的有18個，大于10 m的站點有5個。故23個公交點中有18個為合理公交站點，5個為不合理公交站點，預測成功率達78.26%。

圖7 聚類中心和公交站點

2.3 預測公交車間隔時間

2.3.1 客源量的變化特征

目前，在上下班高峰期，公共交通路段經常面臨大面積堵車現象[17]。據統計，一部分原因是因為路段中間經常會有公交車將路口卡死，或因路段上公交車太多導致交通擁堵。合理的安排公交車發車頻率可有效緩解交通堵塞問題，降低公交車因為體積大而帶來的問題，為人們出行提供便利。為研究人們在一周內不同時間的變化特征，將周一至周日的出行總量進行統計，如圖9所示。由該圖可知，乘客的出行規律與載客的時間分布緊密相關。除周一、周二、周三工作日上班時間外，出租車載客量始終處于較高的水平，以周六、周日出行總量最多。周六出行水平高于周日，這是由于周六處于假期的第一天，人們出游、購物、聚會正值高峰；相比較而言，周日載客量明顯減少，因為部分人們在收假上班的狀態，部分潛在乘客會選擇在家休息以準備完成周一的新任務。

圖8 聚類中心與公交站點對比

圖9 一周內客流量變化

2.3.2 一天中不同時間段的客流量分析

為對一天中不同時段的客流量的變化特征進行分析，筆者對所有的乘車點位置數據進行了時間統計，以2 h作為時間間隔，統計12個時間段內的上車次數，然后進行對比分析，如圖10所示。

由圖10數據分析可得：

(1) 一周內每天的數據變化量的趨勢相近，但依時段不同，客源量有較大的波動。工作日和周末的客源量有明顯區別。周末在6:00以后出行的人數減少，且周末的波動更加平穩，工作日波動更為劇烈。

(2) 從出行時間上來看，0:00—6:00均處在客源量下降的趨勢當中，這與人們的作息時間緊密相關；而6：00以后，人們開始出門上班，故在6：00—8：00區間為出行高峰期；8：00—10：00客源量達到頂峰，意味著堵車最有可能發生在這段時間內；接下來從10：00—16：00客源量相對平穩；16：00左右，客源量又開始呈小幅上升趨勢，因為上班族下班、學生放學等因素；20：00開始，是夜生活最繁忙的時候，人們的出行量相對增多，變化最突出的是星期五，因為正逢下班放假時間，客流量出現短暫高峰期。

圖10 一天中不同時段客流量變化

(3) 結合以上分析，8：00—10：00、14：00—16：00和20：00—22：00這3個時間段為客流量高峰期，分別對應的客流總量為10 000、8000、8500。式(1)中各參數值為：2 h是120 min，一輛普通公交車載客人數約為55人，則8：00—10：00區間內發車時間間隔為3 min，14：00—16：00區間發車時間間隔為4 min，20：00—22：00區間發車時間間隔為4 min。在其他時間段中適當地降低發車頻率以減少道路擁堵情況。

3 結 語

本文研究以武漢市2014年7月31日—2014年8月12日總計13 d 2064臺出租車的GPS軌跡數據為研究對象，通過Map-reduce分布式平臺提取出租車客源上車位置數據，再結合Canopy-K-means算法對數據進行聚類，并對提取的出租車客源進行了量化；再結合武漢市580路公交車站點設站位置，對比分析了公共交通站點選址合理性，討論分析了在不同時段公交車發車頻率。研究表明：①武漢市580路公交路線中總共23個站點，其中18個站點設置合理，5個站點有待改進，預測準確度達到78.26%。在將來的規劃中，選擇在本試驗中得出熱點區域的中心作為公交車站選址是合適的。②在每天的8：00—10：00、14：00—16：00和20：00—22：00這3個時段可以適度提高公交車的發車頻率，時間間隔分別為3、4、4 min，其他時段適當降低公交車發車頻率，以減緩交通擁堵情況。

分析公共交通站點選址、公共交通發車頻率能為城市規劃者提供決策支持，真實反映客源的時空分布特性。該方法同時也存在一定的不足，如未考慮到乘客位置的不確定性對公交車站選址的影響，未利用多源數據進行綜合性行分析，這將是后續研究的內容。