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

任丹萍 劉 琳 陳湘國

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

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

0 引 言

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

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

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

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

1 數(shù)據(jù)預處理

1.1 數(shù)據(jù)描述

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

表1 出租車GPS軌跡數(shù)據(jù)屬性

1.2 數(shù)據(jù)處理環(huán)境

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

1.3 數(shù)據(jù)清洗

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

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

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

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

1.4 載客點提取

出租車軌跡數(shù)據(jù)的車載狀態(tài)發(fā)生變化的具體表現(xiàn)為,當數(shù)值從“0”變?yōu)椤?”時,表示當前時刻出租車的車載狀態(tài)從空載變?yōu)檩d客,說明此時有乘客上車,其值為“1”對應的經(jīng)緯度位置為出租車載客上車點位置。數(shù)值從“1”變?yōu)椤?”,表示當前時刻出租車的車載狀態(tài)從載客變?yōu)榭蛰d,說明此時有乘客下車,其值為“0”對應的經(jīng)緯度位置則為下車點位置。

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

1.5 數(shù)據(jù)篩選

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

圖1 出租車載客行駛時長

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

1.6 坐標轉(zhuǎn)換

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

表2 坐標系說明

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

2.1 載客時間特征分析

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

圖2 出租車載客高峰分析

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

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

圖3 出租車載客時長分布數(shù)

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

2.2 載客空間特征分析

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

圖4 每時段載客空間分布

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

因此,根據(jù)出租車載客的空間分布隨時間的變化呈現(xiàn)出的遞增和遞減規(guī)律,分析其載客空間分布圖,具體結(jié)果如表3所示。

表3 出租車載客區(qū)域統(tǒng)計表

3 出租車載客熱點區(qū)域挖掘

3.1 算法思想

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

3.2 算法步驟

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

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

(1)

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

(2)

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

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

(3)

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

(4)

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

γi=ρi×δi

(5)

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

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

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

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

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

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

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

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

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

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

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

3.3 參數(shù)確定

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

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

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

(6)

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

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

圖5 Eps參數(shù)候選列表和K值關系

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

(7)

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

圖6 MinPts參數(shù)候選列表和K值關系

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

圖7 聚類簇數(shù)和K值關系

可以看出,當簇數(shù)為6時聚類結(jié)果趨于穩(wěn)定,直至簇數(shù)再次發(fā)生變化前取得最優(yōu)K值,此時K=12,結(jié)合圖5、圖6可知,對應的最優(yōu)Eps=0.006 593 03,MinPts=18。

3.4 結(jié)果分析

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

(a) 原始數(shù)據(jù) (b) DBSCAN算法

表4 參數(shù)選取和聚類結(jié)果分析

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

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

3.5 實驗結(jié)果展示

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

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

表5 工作日載客高峰分析結(jié)果

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

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

表6 非工作日載客高峰分析結(jié)果

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

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

4 結(jié) 語

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

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

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

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

此次研究僅對載客熱點區(qū)域進行挖掘,沒有考慮出租車載客其他影響因素。結(jié)合自然環(huán)境、網(wǎng)約車發(fā)展等各方面影響因素,建立不同因素影響模型,是下一步出租車軌跡數(shù)據(jù)的研究重點。