基于密度分區的出租車載客熱點區域聚類分析

任丹萍 劉 琳 陳湘國

(河北工程大學信息與電氣工程學院 河北 邯鄲 056038)

(河北省安防信息感知與處理重點實驗室 河北 邯鄲 056038)

0 引 言

近年來,由于國家政策對城市化發展的大力扶持,城市人口急劇增長,城市居民收入增加、生活水平改善,出租車逐漸成為城市居民出行的重要選擇方式[1]。同時隨著車載GPS的普及[2],交通軌跡大數據愈發受到重視,出租車GPS軌跡數據作為其中一項重要組成部分,成為該領域研究熱點[3]。

通過對出租車軌跡數據內在規律的挖掘,可以得到城市人口活動特征。例如在城市人口活動的時空規律分析方面,張俊濤等[4]提出將高斯定律引入出租車軌跡挖掘,通過軌跡的方向和數量特征,基于不同時間段對出租車軌跡數據進行挖掘。當然,城市居民的活動并非一成不變,在城市居民出行特征差異性方面[5],鄭曉琳等[6]根據出租車軌跡數據中的時空分布差異、行程距離差異、空間社團結構差異三個方面,反映出城市人口活動模式的差異性,從而提升該研究在城市道路規劃等領域的應用。出租車軌跡數據對城市人口活動規律的分析也不局限于日?；顒?對于特殊的出行場景,例如旅游[7]、購物[8]等行為亦可以進行規律的挖掘。

基于不同應用場景,采用不同研究方法。結合出租車GPS軌跡數據的特點,選取聚類算法對熱點區域進行挖掘,會達到更好的熱點區域分布效果[9]?；诿芏鹊木垲愃惴ǜm用于移動軌跡數據的聚類,對軌跡數據進行劃分,例如DBSCAN(Density-Based Spatial Clustering of Applications with Noise)算法[10]可以從隨機分布的出租車軌跡數據中發現聚類簇。在出租車載客熱點區域的分析過程中,劉盼盼[11]提出了一種帶有范圍控制的算法,可以對空間數據快速聚類,實現出租車軌跡數據的細聚類;王貝貝[12]則是從時間的角度結合聚類算法對熱點區域進行挖掘。但是由于該聚類算法采用的全局參數會導致聚類結果的精確度不高[13],所以,Kumar等[14]便對DBSCAN的聚類結果進行二次加工,使用最近原型規則將其擴展至數據集的其余部分。蔡莉等[15]則是從時空特征的角度,融合了位置數據,該模型基于數據層面,解決了軌跡數據分布不均勻的問題。

在針對出租車軌跡數據的研究中,挖掘的載客熱點區域精確度不高,本文根據出租車GPS軌跡數據分布不均勻的特點,提出一種基于密度分區的聚類算法,對出租車軌跡數據進行聚類分析,得到城市人口活動熱點區域。

1 數據預處理

1.1 數據描述

出租車軌跡數據集源于成都市1.4萬多輛出租車的實際行駛軌跡,平均每天會產生5 000多萬條出租車GPS軌跡數據?；谘芯坑布h境的限制,選取成都市一周內的出租車GPS原始軌跡數據集,即以2014年8月18日至2014年8月24日的軌跡數據為例,作為實驗數據。該數據集包含五個屬性,具體如表1所示。

表1 出租車GPS軌跡數據屬性

1.2 數據處理環境

基于出租車軌跡數據量較大,為提高軌跡數據處理速度,結合Spark部署模式的特點和硬件條件的限制,搭建Spark平臺的local模式作為數據預處理的計算環境。具體過程為下載ApacheSpark并解壓tra包,上傳至集群的每個節點,設置PySpark模式的環境變量,從而可以在該模式下進行基于Python的數據預處理工作。

1.3 數據清洗

目前出租車原始軌跡數據采集過程中,主要依靠車載GPS傳感器進行數據采集與傳輸,但由于各種外部或內部因素的影響,例如傳感器故障、GPS信號較差、人為干預等,會導致GPS信號斷傳、重傳,原始數據源缺失、重復或者存在異常值等。針對出租車軌跡數據中的“噪聲”數據進行數據清洗,是數據預處理的第一步,也是獲取準確的軌跡數據集的必要步驟。針對原始軌跡數據存在的問題,具體清洗過程如下：

(1) 去空。出租車GPS原始軌跡數據中包含部分缺失字段,影響數據分析的準確度。通過Python編程,篩選并刪除缺失字段及字段所在的數據行,從而實現了數據集的完整性。

(2) 排序。出租車GPS原始軌跡數據呈無序排列。通過將出租車軌跡數據先以出租車序號升序排列,再以當前時刻升序排列,可以得到一天內有序的軌跡數據,達到了軌跡數據集的有序性的目的。

(3) 降重。出租車GPS原始軌跡數據含有重復數據。將出租車序號和當前時刻兩個字段屬性共同作為去除重復數據的評判標準,實現出租車軌跡數據的正確降重。

1.4 載客點提取

出租車軌跡數據的車載狀態發生變化的具體表現為,當數值從“0”變為“1”時,表示當前時刻出租車的車載狀態從空載變為載客,說明此時有乘客上車,其值為“1”對應的經緯度位置為出租車載客上車點位置。數值從“1”變為“0”,表示當前時刻出租車的車載狀態從載客變為空載,說明此時有乘客下車,其值為“0”對應的經緯度位置則為下車點位置。

具體地,通過Python編程將每行數據的車載狀態減去上一行數據的車載狀態,通過其差值判斷此時刻出租車的車載狀態。若計算差值結果為“1”,表示該過程為乘客上車過程,選取車載狀態為“1”的數據行為上車點。若計算差值結果為“-1”,表示該過程為乘客下車過程,選取車載狀態為“0”的數據行為下車點,從而得到出租車載客點數據集。

1.5 數據篩選

出租車一次有效載客行駛時長是取決于乘客的實際出行需求,因此基于出租車上下車載客點數據集,計算乘客下車對應時刻與上車對應時刻之間的時間差值,得到一次有效載客行駛時長。出租車載客時長的變化趨勢如圖1所示。

圖1 出租車載客行駛時長

由圖1分析可知,出租車載客行駛時長的高峰集中于10至20 min內。隨著出租車載客行駛時長增加,載客量逐漸減少,變化曲線呈現出先增后減的規律。結合實際,選取載客行駛時長在2 min至2 h以內的軌跡數據。同時限定出租車載客行駛范圍,取東經103°95′～104°18′和北緯30°54′～30°733′為研究區域。

1.6 坐標轉換

為保證信息安全,不同地圖采用不同的坐標系,因此軌跡數據匹配地圖時需要進行坐標轉換[16],即軌跡數據在同一地球的映射下,通過坐標的加密和解密,進行不同坐標系統間的相互轉換。本文應用的坐標系種類如表2所示。

表2 坐標系說明

2 出租車載客行為時空分析

2.1 載客時間特征分析

城市居民的基本出行規律具有周期性,并且考慮到一天的出租車載客量存在偶然性,所以計算一周內工作日和非工作日的出租車平均載客量作為出租車載客高峰時段的分析數據,得到工作日和非工作日不同時段內出租車載客量隨時間的變化規律如圖2所示。

圖2 出租車載客高峰分析

由圖2分析可知,工作日和非工作日出租車載客量曲線變化趨勢總體相似。根據高峰期特征,即在某時間段內出租車載客量明顯增多且高于相鄰時段內出租車的載客量可知,工作日出租車每時段平均載客量共出現三個高峰期,分別為早高峰(9：00-11：00)、午高峰(13：00-15：00)和晚高峰(20：00-22：00),符合成都居民“早九晚十”的生活節奏。非工作日載客高峰期則分為午高峰(13：00-15：00)和晚高峰(20：00-22：00)。

此外,通過載客時長,應用數學統計方法計算載客時長分布數,得到工作日和非工作日不同時間間隔內出租車的載客量變化如圖3所示。

圖3 出租車載客時長分布數

由圖3分析可知,在工作日和非工作日期間,出租車載客時長數的變化趨勢基本一致,隨著載客時長的增加,載客次數增長,至載客時長為5至15 min內,載客次數達到高峰;超過30 min的時段內,出租車載客量僅占全部的5%左右。由此可知,出租車載客時長大部分集中在30 min以內,選擇出租車出行更多的是短途出行。

2.2 載客空間特征分析

出租車載客空間,即出租車載客的上車點位置空間分布。結合出租車載客的時序特征,通過核密度分析不同時間段內出租車載客空間分布規律如圖4所示。

圖4 每時段載客空間分布

由圖4分析可知,每時段的出租車載客空間分布不盡相同,比如在非高峰期時段內,出租車的載客區域分布較為平均;臨近載客高峰時段,載客的熱點區域分布逐漸凸顯。而在早高峰、午高峰和晚高峰期間,載客空間的分布層次最為分明,熱點區域分布集中。

因此,根據出租車載客的空間分布隨時間的變化呈現出的遞增和遞減規律,分析其載客空間分布圖,具體結果如表3所示。

表3 出租車載客區域統計表

3 出租車載客熱點區域挖掘

3.1 算法思想

基于密度分區的DBSCAN聚類算法主要是通過求取每個出租車上車點位置數據的局部密度,得到密度峰值點作為簇中心。計算剩余軌跡點與密度峰值點間的歐氏距離,將其歸入到距離最小的峰值點鄰域內,實現對軌跡數據集基于密度的快速劃分,得到不同密度的軌跡數據集。計算不同軌跡數據集對應的參數Eps和MinPts,實現基于密度分區的局部DBSCAN聚類,最后輸出合并聚類結果。

3.2 算法步驟

基于密度分區的DBSCAN算法的相關定義如下：

定義1(局部密度) 對于給定的數據集D,其內對象i的局部密度如下：

(1)

對于χ(x)函數定義為：

(2)

式中：dij表示對象i與j之間的歐氏距離;dc表示截斷距離,且由于該參數對實驗結果影響較小,因此該參數的取值為使得數據集D內的每個對象的相鄰平均對象數約為數據集內數據總數的2%[17]。

定義2(高局部密度點間的距離) 對于數據集D中的任意對象i,與局部更高密度點間的距離定義為：

(3)

其中,存在一種極端情況,即對象i本身的局部密度到達最高時,則該點的δi值定義為：

(4)

定義3(決策值) 對于數據集D中的任意對象i,結合該點的局部密度ρi和高局部密度距離δi得到其決策值,定義如下：

γi=ρi×δi

(5)

基于上述算法定義的闡述,基于密度分區的DBSCAN算法具體步驟如下：

步驟1輸入出租車上車點位置數據集D,計算任意上車位置間的距離矩陣。

步驟2根據距離矩陣和截斷距離dc,計算每個上車位置的局部密度ρi。

步驟3計算與高密度上車位置點的最小距離δi。

步驟4計算決策值γi,判斷決策值差值是否大于其均值,若是,則標記為簇中心。

步驟5將剩余上車位置數據點按其局部密度降序排列,依次判斷并劃分到距離自己最近的簇中心,生成不同密度的上車點位置數據集Di。

步驟6計算不同密度上車點密度數據集Di對應的參數Epsi和MinPtsi。

步驟7將上車點密度數據集內的所有數據點均標記為未訪問狀態,任選一個未訪問的上車點,判斷該上車點以Epsi為半徑的鄰域內是否包含MinPtsi個上車點。若是,標記為核心點,建立新簇C,將鄰域內所有的上車點加入簇C;否則,標記為噪聲點。

步驟8將簇C中尚未訪問的上車點依次計算其鄰域內是否包含至少MinPtsi個上車點。若是,則將鄰域內未歸入任何一個簇的上車點加入到簇C中。

步驟9重復步驟8,繼續檢查C中未訪問的上車點,直至沒有新的上車點加入簇C為止。

步驟10重復步驟7-步驟9,直到所有上車點都加入某個簇或者標記為噪聲點。合并不同密度上車點位置數據集Di的聚類結果,輸出。

3.3 參數確定

本文利用出租車軌跡數據集自身的空間特性,自適應地求取參數值[18]。

(1) 確定Eps參數候選列表。參數Eps的選取,通過計算輸入的出租車上車點位置數據集D中每個元素間的歐氏距離,得到其距離分布矩陣DISTn×n如下：

DISTn×n={dist(i,j)|1≤i≤n,1≤j≤n}

(6)

式中：n表示數據集D中對象數量;DISTn×n矩陣內的每一個元素為數據集D中的對象i和對象j間的歐氏距離。

將距離分布矩陣DISTn×n內的每一行元素按照升序進行排列,則第K列(K=1,2,…,n)的元素即為數據集D內所有對象的K-最近鄰距離向量,表示為DISTn×k。對DISTn×k內的元素求數學期望,得到K-最近鄰的平均距離作為參數Eps的候選參數列表,如圖5所示。

圖5 Eps參數候選列表和K值關系

(2) 確定MinPts參數列表。參數MinPts的選取,在參數Eps的基礎上,求出每個Eps對應的鄰域內包含的對象數,采用數學期望法計算所有對象數的均值,即為數據集D的鄰域密度閾值MinPts的值,計算公式如下：

(7)

式中：n為數據集D中的對象總數;Pi為對象i在以Eps為半徑的鄰域內包含的對象數量。MinPts參數候選列表與K值的關系曲線如圖6所示。

圖6 MinPts參數候選列表和K值關系

(3) 確定最優參數。根據上述內容確定的參數列表,依次選取K列元素對應的Eps值和MinPts值作為輸入進行DBSCAN算法聚類,可以得到不同K值對應的最終聚類結果和生成的簇數。當同一個簇數連續出現三次及以上次數時,聚類結果趨于穩定,直至簇數再發生變化前,選取最后的K值最為最優K值,此時最優K值對應的Eps和MinPts的值作為最優參數。通過該計算方法得到的聚類簇數與K值之間的關系如圖7所示。

圖7 聚類簇數和K值關系

可以看出,當簇數為6時聚類結果趨于穩定,直至簇數再次發生變化前取得最優K值,此時K=12,結合圖5、圖6可知,對應的最優Eps=0.006 593 03,MinPts=18。

3.4 結果分析

選用的出租車實際上車點位置數據集含有7 824個數據,對其進行不同聚類分析,聚類參數的選取和聚類結果如表4所示,具體聚類結果如圖8所示。

(a) 原始數據 (b) DBSCAN算法

表4 參數選取和聚類結果分析

從參數選取方面對比可知,DBSCAN聚類算法的參數需要依靠人工經驗確定,上述參數在MinPts一定的情況下,以0.01為初始值,5×10-6為步長,需經過18 675次調參得出。KANN-DBSCAN算法和基于密度分區的聚類算法則可以通過計算自適應得到最優參數。

從聚類結果方面對比可知,本文算法的精確率有所提高,主要因為在針對數據密度分布不均勻情況下,無論是DBSCAN聚類算法還是KANN-DBSCAN算法,兩者均采用全局參數,得出的結果只能反映研究范圍內最熱門的乘車區域,無法精確地反映出再往下一級的熱門乘車區域。但這并不符合實際情況,如果出租車都集中于圖8(b)和圖8(c)所示的熱門區域,這不僅會造成打車供需的不平衡,還會導致交通擁堵,反而得不償失?；诿芏确謪^的聚類算法很好地解決了這一問題,針對同一等級的局部密度自適應生成對應的局部參數,進行局部數據的聚類后合并,聚類的結果如表4所示?；诿芏确謪^的聚類算法共生成20個簇,也就是20個相對熱門的乘車區域,相較于其他兩種算法,對全城出租車的調度、平衡乘車供求都具有一定的積極作用。但也由于該算法是針對局部密度進行討論,所以在時間復雜度方面并未有所提高。

3.5 實驗結果展示

基于上述研究內容,對工作日和非工作日的各時段載客高峰期進行基于密度分區的聚類分析和結果展示。

(1) 工作日各時段載客高峰期聚類結果。工作日各時段載客高峰期經過基于密度分區的聚類分析,具體聚類分析結果如表5所示。

表5 工作日載客高峰分析結果

可以看出,工作日每時段載客高峰期對應的數據量即為載客次數,聚類簇數為出租車載客熱點區域數,噪聲數則為非載客熱點區域的載客次數。其中,早高峰和午高峰的熱點區域數量較為相近,除了載客量上的變化,更多的是因為工作日白天出行主要是為了上班和上學等,出行熱點區域較為固定。晚上出行更多的是個人因素,可供選擇的目的地增多,出行熱點區域也隨著增多。而在非載客熱點區域,則是早高峰和晚高峰載客次數較多。

(2) 非工作日各時段載客高峰期聚類結果。非工作日各時段載客高峰期經過基于密度分區的聚類分析,具體聚類分析結果如表6所示。

表6 非工作日載客高峰分析結果

可以看出,相較于非工作日載客午高峰的載客熱點區域數量而言,非工作日載客晚高峰的載客熱點區域增加了16個,較多為三環附近的居民區。其次,非載客熱點區域也是晚高峰載客的可能性更高。

綜上所述,基于工作日和非工作日載客高峰期的實驗數據,實現了基于密度分區的聚類分析,其聚類結果不僅驗證了出租車載客高峰期空間特征分析結果的準確性,并更進一步精確細化了載客熱點區域,以及在非載客熱點區域,早晚高峰期時段的載客率更高。

4 結 語

隨著經濟的快速發展和居民生活水平的提高,城市居民選擇出租車作為出行方式的需求量增加,隨之出租車行業規模也逐漸擴大且管理也愈加規范。但是為了進一步提高資源的利用率,減少乘客乘車的等待時間,基于成都市出租車的歷史軌跡數據的處理與分析,得到結論如下。

(1) 出租車GPS原始軌跡數據集預處理。為了保證下一步數據分析結果的準確性,對出租車原始軌跡數據集進行數據清洗、篩選有效載客行駛時長和范圍、載客點提取、坐標轉換。

(2) 出租車載客行為時空特征分析?；陬A處理后的出租車載客上車點軌跡數據集,從時間和空間兩方面,分析得到出租車載客高峰時段和載客特點,以及每時段出租車載客空間分布特征。為出租車載客熱點區域的分析提供依據。

(3) 出租車載客的熱點分析。針對出租車軌跡數據密度分布不均勻的特點,提出基于密度分區的聚類算法,有效提高了載客區域分布的精確度。

此次研究僅對載客熱點區域進行挖掘,沒有考慮出租車載客其他影響因素。結合自然環境、網約車發展等各方面影響因素,建立不同因素影響模型,是下一步出租車軌跡數據的研究重點。