姚辰達(dá), 王景升*, 楊政陶, 葛帥杰

(1.中國人民公安大學(xué)交通管理學(xué)院, 北京 100038; 2.中國人民公安大學(xué)偵查學(xué)院, 北京 100038)

由于經(jīng)濟(jì)成本低、維護(hù)方便等優(yōu)點(diǎn),定時控制仍是目前中國大部分城市信號交叉口所采取的控制模式。單點(diǎn)定時控制根據(jù)交通流特性,將交叉口劃分為若干個重點(diǎn)時段進(jìn)行分別管理,在實(shí)際的道路交通管理中,一般可分為低峰、平峰和高峰時期的管理,然后根據(jù)劃分的時段分別進(jìn)行最優(yōu)化的信號配時。然而交叉口流量很大程度上受到出行需求的影響,考慮到不同路段出行需求的異同,將交叉口簡單分為3個時段進(jìn)行控制未必合理——過少的時段劃分無法適應(yīng)交通流的變化特征,過多的時段劃分又會導(dǎo)致控制方案的頻繁切換,造成交通流紊亂,控制效率反而降低。

事實(shí)證明,合理的時段劃分方案能夠在成本低廉的情況下實(shí)現(xiàn)和自適應(yīng)控制類似的效果。因此為了進(jìn)一步提升定時控制的效果,必須解決如何對交叉口進(jìn)行時段劃分的問題。Ratrout[1]基于檢測器流量數(shù)據(jù),創(chuàng)新性地使用非監(jiān)督學(xué)習(xí)的K-means算法進(jìn)行時段劃分,相較于傳統(tǒng)的分層聚類算法要更加快速有效,但由于K-means算法對噪聲和離群點(diǎn)較為敏感的特性,對檢測器數(shù)據(jù)的要求高,普適性較弱,同時有可能會陷入局部最優(yōu)解。在此基礎(chǔ)上,李英等[2]采用了抗噪能力更強(qiáng)的圍繞中心點(diǎn)劃分(partitioning around medoids,PAM)算法,較好地解決了K-means算法對噪聲敏感的特性,對檢測器提供的數(shù)據(jù)質(zhì)量要求降低,普適性進(jìn)一步提高。杜長海等[3]將每個數(shù)據(jù)分配到聚類中心上并引入模糊度,使模糊C均值聚類(fuzzy C-means, FCM)算法能夠更好地處理數(shù)據(jù)的不確定性和復(fù)雜性。于德新等[4]和田秀娟[5]在此基礎(chǔ)上利用模擬退火算法和遺傳算法對聚類中心進(jìn)行優(yōu)化,提出改進(jìn)FCM算法,有效解決FCM算法對初值敏感的問題。馮斌等[6]運(yùn)用Fisher有序聚類按照時間順序劃分信號時段。官國宇等[7]提出了基于周期數(shù)據(jù)的雙截斷高斯混合模型的EM算法的信號多時段劃分方法。趙偉明等[8]運(yùn)用離群點(diǎn)的修正后的改進(jìn)譜聚類NJW算法,得到給定聚類數(shù)目下的時段劃分。

上述研究已經(jīng)基本解決了傳統(tǒng)K-means算法存在的問題,但聚類簇數(shù)的選取仍需通過手動選取,主觀操作不當(dāng)會對最終的時段劃分方案產(chǎn)生極大的影響;當(dāng)方案之間的交通流發(fā)生突變時忽略了交通流的時間特性,沒有考慮方案與方案之間的過渡問題。基于此,李文婧等[9]使用了一種自底向上的有序聚類方法,逐一合并相似的數(shù)據(jù)點(diǎn)或簇,直到形成一個包含所有數(shù)據(jù)點(diǎn)的大簇,解決了需要手動選擇簇的數(shù)量以及被忽略的交通流時間特性的問題。姚佼等[10]使用了一種基于快速搜索算法的K-means改進(jìn)型,在兼顧自動選取簇的數(shù)量的基礎(chǔ)上進(jìn)一步降低算法的時間復(fù)雜度。宋仁旺等[11]通過冒泡排序法排除噪聲,并優(yōu)化聚類中心點(diǎn)的選擇,提高了K-means算法的效率,降低迭代次數(shù)和噪聲影響。王博文等[12]利用K-means++算法解決初始化種子點(diǎn)的問題,大大減少尋找最優(yōu)解所需運(yùn)行算法的次數(shù)。別一鳴等[13]從方案過渡的角度出發(fā),根據(jù)交通流的時間序列給出一套時段之間是否需要拆分、合并或是需要增加過渡周期的方法,并通過交通仿真驗(yàn)證了其有效性。胡凡瑋等[14]綜合考慮交叉口通行效率及環(huán)境因素,建立多目標(biāo)多時段控制模型,用改進(jìn)的螢火蟲算法求解,實(shí)現(xiàn)交叉口車流量多時段控制。

現(xiàn)有的研究大多是基于檢測器數(shù)據(jù),利用聚類算法對具有類似交通流特征的時段進(jìn)行同質(zhì)化處理,然而現(xiàn)有的研究尚存在以下不足。

(1)聚類算法的簇數(shù)大多需要預(yù)先選取,主觀的簇數(shù)選取往往會對時段劃分產(chǎn)生巨大的影響。

(2)目前大多數(shù)研究使用了輪廓系數(shù)用以解決問題(1),但是由于Silhouette系數(shù)是基于歐氏距離計算相似度的度量,因此它無法處理非凸形狀的聚類。而在交通時段劃分中經(jīng)常會出現(xiàn)兩個圓環(huán)形狀簇的數(shù)據(jù)集,其中兩個圓環(huán)部分有所重疊的情況,因此將輪廓系數(shù)作為算法終止閾值在交通時段劃分領(lǐng)域適用條件有所不符;

(3)由于時段劃分方案是基于檢測器的自然數(shù)據(jù),數(shù)據(jù)質(zhì)量往往參差不齊,因此對數(shù)據(jù)清洗、補(bǔ)全以及算法的抗噪性提出了很高的要求。然而目前研究領(lǐng)域所使用的絕大多數(shù)非監(jiān)督學(xué)習(xí)類算法[如K-means算法、自組織映射(self-organizing maps,SOM)算法、FCM算法]都不具備較強(qiáng)的抗噪性。

(4)未來可面向基于檢測器數(shù)據(jù)的短時交通流預(yù)測,因此需要在傳統(tǒng)非監(jiān)督類學(xué)習(xí)算法中進(jìn)一步增加算法的時效性,在確保準(zhǔn)確性的同時有效降低時間復(fù)雜度。

(5)大多數(shù)研究未考慮到相鄰方案之間的過渡問題。

針對上述問題,提出一種基于KD-tree加速索引以及GridsearchCV的DBSCAN算法的改良型kagscv-DBSCAN(KD-tree accelerated density-based spatial clustering of applications with noise and grid search cross validation)算法,對基于檢測器的交通流數(shù)據(jù)進(jìn)行快速聚類得到時段劃分的初步方案。然后以交叉口總延誤為指標(biāo),考慮相鄰方案間的過渡問題,對初步方案進(jìn)行時段的拆分、合并以及考慮是否加入過渡周期,得到最終時段劃分方案,并以陜西省西安市某交叉口的實(shí)際算例對方法進(jìn)行驗(yàn)證。研究成果對于確定合理的交通多時段定時控制方案、有效提高交叉口運(yùn)行效率具有重要意義,同時為基于檢測器數(shù)據(jù)的實(shí)時短時交通流預(yù)測具有一定的參考價值。

1 基于kagscv-DBSCAN算法的單點(diǎn)交叉口時段劃分方法

kagscv-DBSCAN算法是基于KD-tree加速索引以及GridsearchCV超參數(shù)尋優(yōu)的DBSCAN算法改良型。相較于在交叉口時段劃分領(lǐng)域中使用較多的K-means算法,kagscv-DBSCAN算法的優(yōu)勢有:一是不需要預(yù)先選取簇的數(shù)量;二是對基于檢測器交通流數(shù)據(jù)的抗噪能力更強(qiáng);三是運(yùn)算效率顯著提升。分別從DBSCAN算法、基于KD-tree加速索引步驟以及基于GridsearchCV的DBSCAN超參數(shù)尋優(yōu)步驟對kagscv-DBSCAN算法進(jìn)行說明。

1.1 DBSCAN算法

單點(diǎn)交叉口時段劃分時,由于交通隨時間的變化規(guī)律性較強(qiáng),反映在圖像上的變化情況為非球面狀簇,因此貿(mào)然使用基于歐氏距離的聚類算法可能會導(dǎo)致聚類效果不佳。另一方面,圖像在交通性質(zhì)相似時段的點(diǎn)位密度也較為相近,這與基于密度的聚類算法——DBSCAN的原理不謀而合。DBSCAN (density-based spatial clustering of applications with noise) 是一種基于密度的聚類算法[15],算法的基本思路如下。

設(shè)數(shù)據(jù)集D={x1,x2,…,xn},ε為鄰域半徑,MinPts為鄰域內(nèi)最少點(diǎn)數(shù)。對于數(shù)據(jù)集D中的點(diǎn)p,其ε鄰域Nε(p)表示與p的距離不超過ε的所有點(diǎn)構(gòu)成的集合[16]。即

Nε={q∈D∣dist(p,q)≤ε}

(1)

式(1)中:dist(p,q)表示點(diǎn)p與點(diǎn)q之間的歐氏距離。

若數(shù)據(jù)集D中的點(diǎn)p的ε鄰域中至少包含MinPts個點(diǎn),則稱點(diǎn)p為核心對象;若點(diǎn)q在點(diǎn)p的ε鄰域中,且點(diǎn)p是核心對象,則稱點(diǎn)q相對于點(diǎn)p是直接密度可達(dá)的;若存在一個點(diǎn)序列p1,p2,…,pn,滿足p1=q,pn=p,且對于任意i=1,2,…,n-1,pi和pi+1是直接密度可達(dá)的,則稱點(diǎn)q相對于點(diǎn)p是密度可達(dá)的。

DBSCAN算法的具體步驟如下。

步驟1遍歷數(shù)據(jù)集中的每一個點(diǎn)p。

步驟2若點(diǎn)p是核心對象,則從點(diǎn)p開始,通過密度可達(dá)關(guān)系尋找所有密度相連的點(diǎn),將它們?nèi)考尤胪粋€簇中。

步驟3重復(fù)步驟1和步驟2,直到數(shù)據(jù)集中所有點(diǎn)都被訪問過。

步驟4所有不屬于任何簇的點(diǎn)被標(biāo)記為噪聲點(diǎn)。

1.2 基于KD-tree加速索引步驟

由于DBSCAN在計算速度上存在劣勢,出于交通領(lǐng)域的時效性要求,需要在保證聚類精度的同時提升DBSCAN的計算速度,而利用KD-tree進(jìn)行加速的步驟在別的算法上已表現(xiàn)出了較為穩(wěn)定的效果[17]。參考KD-Tree在其他算法中的應(yīng)用思路,可以將數(shù)據(jù)集中的點(diǎn)存儲到KD-Tree中,并通過查詢其最近的k個鄰居來確定每個點(diǎn)的ε鄰域。這樣,在給定半徑ε和最小點(diǎn)數(shù)MinPts的條件下,可以確定哪些點(diǎn)是核心點(diǎn),并將它們標(biāo)記為已訪問,避免重復(fù)計算。然后利用 KD-Tree 查找核心點(diǎn)的ε鄰域,以及擴(kuò)展密度可達(dá)點(diǎn)的操作,可以在較短時間內(nèi)完成聚類過程。

應(yīng)用KD-Tree進(jìn)行DBSCAN聚類的具體流程如下。

步驟1將數(shù)據(jù)集中的點(diǎn)存儲到 KD-Tree 中。

步驟2對于每個點(diǎn)p,查詢其最近的k個鄰居,并將其距離小于ε的鄰居標(biāo)記為已訪問。

步驟3根據(jù)最小點(diǎn)數(shù)MinPts和以p為核心點(diǎn)的鄰域內(nèi)的已訪問點(diǎn)數(shù)確定p是否為核心點(diǎn)。

步驟4針對每個核心點(diǎn),擴(kuò)展其密度可達(dá)的所有點(diǎn),并將其分配到不同的聚類簇中。

步驟5初始化聚類簇計數(shù)器和未訪問點(diǎn)集合;對于每個點(diǎn)p,如果它沒有被訪問過,則將其標(biāo)記為已訪問,并獲取其ε鄰域內(nèi)的所有點(diǎn);如果該鄰域包含至少M(fèi)inPts個點(diǎn),則將p標(biāo)記為核心點(diǎn),并將它及其鄰域內(nèi)的所有點(diǎn)分配到一個新的聚類簇中;否則,將p標(biāo)記為噪聲點(diǎn)。

1.3 基于GridsearchCV的DBSCAN超參數(shù)尋優(yōu)步驟

在使用DBSCAN時一般選取的是算法默認(rèn)超參數(shù)值,但超參數(shù)值的選用應(yīng)當(dāng)根據(jù)實(shí)際交通數(shù)據(jù)進(jìn)行變化。超參數(shù)值選取不當(dāng)既會影響時段劃分的數(shù)量,也會具體影響到某一時段所屬的控制方案,因此需要尋找一種超參數(shù)尋優(yōu)的方法。GridsearchCV是一種基于網(wǎng)格搜索的超參數(shù)優(yōu)化技術(shù),它在生物科學(xué)領(lǐng)域已有應(yīng)用并表現(xiàn)出良好效果[18]。為了使算法更加適應(yīng)交通數(shù)據(jù)集,參考生物領(lǐng)域的超參數(shù)尋優(yōu)思路,引入GridsearchCV對DBSCAN進(jìn)行超參數(shù)尋優(yōu)操作。

GridsearchCV會遍歷所有可能的超參數(shù)組合,并返回一個最優(yōu)解。因此,結(jié)合GridsearchCV和DBSCAN算法可以確定最佳的ε和MinPts的超參數(shù)組合,從而提高DBSCAN算法的聚類性能。

在選取評價指標(biāo)時,有別于使用較多的Silhouette輪廓系數(shù),選取基于簇間方差與簇內(nèi)方差比值的CH(Calinski-Harabasz)指標(biāo)[19]。相較于Silhouette輪廓系數(shù),CH指標(biāo)的計算速度較快,而且對于噪聲數(shù)據(jù)不敏感,因此在處理大型數(shù)據(jù)集時表現(xiàn)良好,更適用于基于檢測器的自然交通流數(shù)據(jù)。

Calinski-Harbasz Score是通過評估類之間方差和類內(nèi)方差來計算得分。

(2)

式(2)中:k為簇數(shù);N為數(shù)據(jù)集;SSB為類間方差;SSW為類內(nèi)方差。

SSB的計算公式為

(3)

SSW的計算方法為

(4)

式中:Cq為類q中所有數(shù)據(jù)的集合;cq為類q的質(zhì)點(diǎn);cE為中心點(diǎn);nq為類q數(shù)據(jù)點(diǎn)的總數(shù)。

使用GridsearchCV進(jìn)行超參數(shù)調(diào)整的主要步驟如下。

步驟1定義算法模型和需要調(diào)整的超參數(shù)范圍。

步驟2定義評價指標(biāo)Calinski-Harabasz系數(shù)。

步驟3定義交叉驗(yàn)證的折數(shù)K。

步驟4在 GridSearchCV中傳遞算法模型、超參數(shù)范圍、評價指標(biāo)和折數(shù)K,獲取最優(yōu)的超參數(shù)組合和相應(yīng)的評價指標(biāo)。

2 考慮方案間過渡的時段劃分優(yōu)化方法

目前,大部分研究成果和方法是基于交通量進(jìn)行聚類劃分,再將聚類得到的結(jié)果進(jìn)行分別信號配時[5-10]。雖然聚類算法可以將交通流數(shù)據(jù)依照其特征進(jìn)行分類并加以時段劃分,但也應(yīng)該充分考慮到交通流變化的時間連續(xù)性。例如,如果方案與方案間的控制周期差距過大,則會導(dǎo)致控制方案的突變,容易造成控制方案與當(dāng)前交通流狀態(tài)極不匹配的情況。因此當(dāng)相鄰兩方案周期差距過大時,應(yīng)增加過渡周期來避免信號控制方案之間的突變。由于過渡方案不是最佳方案,因此其控制效果會有波動。當(dāng)相鄰控制間隔的方案周期差距不是很大時可以不加設(shè)過渡周期。具體操作方法如下。

兩間隔到達(dá)的流量分別為qi和qi+1,最佳周期分別為Ci和Ci+1,定義兩間隔周期之間的差距不能大于ΔC,實(shí)際過渡周期個數(shù)為m。

(1)當(dāng)|Ci-Ci+1|≤ΔC時,兩間隔之間的周期差異較小,不需要設(shè)置過渡周期,m=0。

當(dāng)聚類方案之間信號周期差異過大時,可以通過此方法對方案間做平滑處理,方案切換更加平滑,最大程度減少了多時段控制對交通流的干擾。

3 實(shí)例驗(yàn)證

為驗(yàn)證本文方法的有效性,選取車總延誤為指標(biāo),以陜西省西安市某交叉口為例進(jìn)行運(yùn)算并進(jìn)行對比分析。此交叉口幾何特征如圖1所示。

圖1 交叉口幾何特征Fig.1 Geometric feature of intersection

該交叉口的檢測器采集間隔已被固定為5 min,然而時間劃分過于零碎時容易導(dǎo)致控制方案頻繁突變的情況。因此,將交叉口每5 min的流量合并為每15 min的流量后[13],數(shù)據(jù)分布情況如圖2所示。

圖2 交叉口流量分布情況Fig.2 Traffic flow distribution of intersection

選取交叉口總流量,利用kagscv-DBSCAN算法對數(shù)據(jù)集進(jìn)行計算,得到GridsearchCV曲線如圖3所示。

圖3 GridsearchCV曲線Fig.3 GridsearchCV curve

可以看出,從聚類數(shù)為3時曲線開始平滑,因此可判定3是最佳聚類簇數(shù)。通過kagscv-DBSCAN算法得到聚類結(jié)果如圖4所示。

圖4 kagscv-DBSCAN算法聚類結(jié)果Fig.4 Clustering result of kagscv-DBSCAN

分別利用文獻(xiàn)綜述中之前研究所采用的K-means、PAW、FCM、RSAGA-FCM和所提出的kagscv-DBSCAN算法對該交叉口進(jìn)行時段劃分。為橫向?qū)Ρ然诿芏纫约盎跉W氏距離的聚類結(jié)果,同時能夠更加直觀地看出時段劃分方案間的差別,將K-means與PAW的簇數(shù)統(tǒng)一設(shè)置為3,對比結(jié)果如圖5所示。

圖5 各聚類結(jié)果對比圖Fig.5 Comparison of different clustering results

對kagscv-DBSCAN算法得到的聚類結(jié)果進(jìn)行考慮過渡方案的修正,得到最終時段劃分方案。由于在諸多交通指標(biāo)當(dāng)中,交叉口通行能力和車總延誤是較為直觀的,同時加入對時段劃分方法時間復(fù)雜度的考慮,因此選取交叉口通行能力、車總延誤為評價和計算時長3個指標(biāo)用以評價方案劃分的優(yōu)劣。

從表1可以看出,考慮方案間過渡的kagscv-DBSCAN時段劃分方法將一天劃分為8個時段進(jìn)行控制,并在必要的方案之間加設(shè)了若干過渡周期。有別于傳統(tǒng)的夜間低峰、早平峰、早高峰、午平峰、午高峰、晚平峰、晚高峰的劃分方案,考慮方案間過渡的kagscv-DBSCAN時段劃分方法對交通流數(shù)據(jù)的特征挖掘能力更加出色。受行人過街時間影響,交叉口在夜間以及早平峰時的最佳周期近乎相同,交通流特征也較為類似,此時將夜間方案和早平峰進(jìn)行刻意的分別控制是沒有必要的,因此該方法選擇將夜間與早平峰時段進(jìn)行統(tǒng)一管理。而從08:30開始,交叉口流量開始激增,基于K-means、PAW和FCM的時段劃分方法很難應(yīng)對這種控制方案間的斷層現(xiàn)象,相鄰控制方案之間的周期時長差距都在60 s。雖然RSAGA-FCM選擇將早高峰前期的時間段包含在前一個控制方案當(dāng)中以縮小這種差距,但相鄰方案周期的時長差距仍是達(dá)到40 s,這個數(shù)據(jù)依然是被認(rèn)為有極大概率會對交通流起到擾動作用?？紤]方案間過渡的kagscv-DBSCAN時段劃分方法較為精確地捕捉到了早高峰和午高峰的時間,在1 h的時間內(nèi)針對高峰時段做了更為精細(xì)化的控制,確保高峰時段交叉口的平穩(wěn)運(yùn)行。同時在平峰和高峰控制方案間加入了若干過渡周期,周期與周期之間的差距縮小到15 s,能夠確保方案間的平穩(wěn)切換,大大降低方案切換對交通流的擾動作用。從運(yùn)算時間上來看,基于KD-tree加速索引的kagscv-DBSCAN算法有明顯的優(yōu)勢,而當(dāng)把數(shù)據(jù)集做更加精細(xì)的劃分時(如間隔由15 min變?yōu)? min或2 min),數(shù)據(jù)標(biāo)簽更多,基于KD-tree加速索引的kagscv-DBSCAN算法的速度優(yōu)勢會體現(xiàn)得更加明顯。

表1 交叉口控制時段劃分結(jié)果對比Table 1 Comparison of results of intersection control period division

從表2中可以看出,相較于傳統(tǒng)的基于K-means、PAW和FCM算法的時段劃分方法,考慮方案間過渡的kagscv-DBSCAN時段劃分方法在減小車總延誤和提升通行能力方面具有明顯優(yōu)勢。從運(yùn)算速度的方面來說,kagscv-DBSCAN算法速度明顯優(yōu)于FCM,即使是相較于計算復(fù)雜度為線性的K-means聚類算法也具有一定的優(yōu)勢。

表2 效率提升計算結(jié)果Table 2 Efficiency improvement calculation results

為了驗(yàn)證所提方法的魯棒性,選取陜西省西安市另一交叉口為實(shí)驗(yàn)對象進(jìn)行對比實(shí)驗(yàn),效率提升計算結(jié)果如表3所示。

表3 效率提升計算結(jié)果Table 3 Efficiency improvement calculation results

對比表2和表3的計算結(jié)果,發(fā)現(xiàn)算法在對比模糊聚類時效果有所提升,但對比K-means以及PAW算法時效果略有降低,分析可能是由于該交叉口的流量分布更貼近球面簇的形狀,因此K-means和PAW兩種基于歐氏距離的聚類算法在該交叉口場景下表現(xiàn)略有提升?？傮w來看,本文算法在各種場景下的表現(xiàn)較為穩(wěn)定,魯棒性較強(qiáng)。

4 結(jié)論

(1)針對傳統(tǒng)非監(jiān)督學(xué)習(xí)類聚類算法需要預(yù)先選擇簇數(shù)以及抗噪性不強(qiáng)的問題,提出了kagscv-DBSCAN算法,引入了KD-tree對算法進(jìn)行加速索引,同時將Silhouttte輪廓系數(shù)更換為Calinski-Harbasz系數(shù),并利用Grid-searchCV對超參數(shù)進(jìn)行尋優(yōu),大大降低算法的時間復(fù)雜度,提高準(zhǔn)確率,使算法更加適應(yīng)交通數(shù)據(jù)特征,也可為短時交通流預(yù)測提供借鑒價值。

(2)目前大多數(shù)研究沒有考慮到方案之間的過渡問題,在(1)的基礎(chǔ)上增加了對方案間過渡的考慮,對聚類算法得到的初步時段劃分方案進(jìn)行調(diào)整,以降低控制方案間的突變對交通流的擾動。

(3)通過實(shí)例驗(yàn)證了所提出的考慮方案間過渡的kagscv-DBSCAN單點(diǎn)定時控制時段劃分方法。與基于K-means、PAW、FCM以及RSAGA-FCM的時段劃分方法相比,車總延誤降低分別為6.95%、6.61%、3.68%和1.04%,通行能力提升效率分別為5.39%、5.07%、3.48%、1.69%,并在運(yùn)算速度上具備明顯優(yōu)勢。