基于K-means聚類算法的公交運營時段分析

沈吟東，張仝輝，徐 甲

（華中科技大學(xué) 自動化學(xué)院，圖像信息處理與智能控制教育部重點實驗室,武漢 430074）

1 引言

近年來，我國的城市交通面臨著日益嚴(yán)峻的挑戰(zhàn).公交作為城市交通一個重要的組成部分，也是城市居民正常出行最重要的交通工具之一.分析并研究公交運營情況，對公交規(guī)劃、時刻表的制定及改善公交服務(wù)質(zhì)量有十分重要的作用[1，2].

公交線路在不同時段的運營時間和客流規(guī)律通常存在很大差異，所以一般需要對高低平峰等不同時段分別進(jìn)行分析.因此，運營時段劃分是公交運營分析的重要基礎(chǔ).運營時段的劃分研究始于上世紀(jì)80年代，Salicrú等[3]對其做了歸納總結(jié).Carey[4]做了單程運營時間的隨機(jī)性研究，將其歸并到總運營成本中.國內(nèi)對時段劃分的研究較少，楊新苗等[5]用fisher聚類做了運營時段劃分,徐甲和沈吟東[6]基于車輛定位數(shù)據(jù)采用貪心策略劃分運營時段.而在現(xiàn)實中，公交公司基本都是根據(jù)客流和線路運營環(huán)境采用手工方式憑經(jīng)驗劃分時段[7].然而，完全根據(jù)經(jīng)驗人工劃分的時段一般比較粗略，與現(xiàn)實的運營規(guī)律之間很可能存在偏差.隨著GPS定位系統(tǒng)的普及應(yīng)用，公交企業(yè)已積累了大量的運營數(shù)據(jù).人們逐漸認(rèn)識到這些數(shù)據(jù)能夠更為實時準(zhǔn)確地反映運營狀況，因此，如何合理利用大規(guī)模的數(shù)據(jù)進(jìn)行運營分析成為研究的熱點和難點[8].

本文擬基于GPS運營數(shù)據(jù)，利用K-means算法具有解決大規(guī)模數(shù)據(jù)聚類問題的能力，設(shè)計基于K-means聚類算法的公交運營時段劃分方法，以期實現(xiàn)自動、準(zhǔn)確地劃分公交運營時段，為進(jìn)一步的分時段運營分析和優(yōu)化調(diào)度奠定基礎(chǔ).

2 公交運營時段分析算法

現(xiàn)實中，公交線路在不同時段的運營狀況、擁堵情況和客流量等往往存在較大差異，致使一天內(nèi)的車輛單程（從起點到終點）的運營時間變化很大[6].圖1給出了從GPS記錄中抽取出的一條線路一天的單程時間樣本.

圖1 一天的單程時間示意圖Fig.1 Illustration of trip times during a day

從圖1可見，一天的單程運營時間在不同時段存在明顯差異.我國公交企業(yè)在制定運營計劃時普遍將一條線路的單程時間設(shè)置為一個固定值，這顯然與現(xiàn)實情況不太吻合，因此，編制的運營計劃通常也很難按時執(zhí)行，運營混亂現(xiàn)象難以消除.

為了編制出能夠符合實際運營規(guī)律、具有高執(zhí)行率的運營方案，本文采用定量的方法對公交線路全天的運營時間進(jìn)行聚類分段.其中，K-means聚類算法是解決聚類問題的一種經(jīng)典算法，具有效率高和易實現(xiàn)的特點，被廣泛應(yīng)用于地球科學(xué)、信息技術(shù)、決策科學(xué)、醫(yī)學(xué)和商業(yè)智能等領(lǐng)域的對大規(guī)模數(shù)據(jù)聚類[9].因此，本文擬設(shè)計出能夠有效劃分運營時段的K-means聚類算法.

2.1 基于K-means聚類的運營時段劃分方法

K-means聚類算法的基本思路是：設(shè)有k個簇，依據(jù)一定的測度標(biāo)準(zhǔn)，將一組給定的對象逐個賦予或重新賦予最類似的簇，該過程不斷迭代直至滿足預(yù)設(shè)的終止條件.下面定義K-means聚類算法的主要元素.

假設(shè)已知一個單程時間樣本集合，定義其為對象集合P，其中每一個單程時間就是一個對象p∈P.任意一個簇Ci?P(i=1,2,...,k)表示一組相似對象的集合，即，k表示簇的總數(shù).在公交運營時段劃分問題中，可以設(shè)定k=4.因為公交線路的高低峰時段一般都可以分為如下四類：低峰、平峰、小高峰和高峰，因此單程時間樣本集合中的每個對象都可以分別歸入其中一類（簇）.每個簇的聚類中心稱為簇中心mi(i=1,2,...,k)，定義為簇中對象的平均值，即該簇中全部單程時間的平均值.

為了使k個簇各自盡可能緊湊獨立，本文使用歐幾里得距離dp,mi= ||p-mi表示對象p到簇中心mi的距離，并采用平方誤差準(zhǔn)則[9],把標(biāo)準(zhǔn)測度E定義為全部對象的誤差平方總和，其公式為

基于上述定義，本文設(shè)計出基于K-means聚類算法的運營時段劃分方法，具體流程如下.

步驟1 從對象集合P中任意選擇k個對象作為每個簇的初始簇中心;

步驟2 對每個對象 p∈P，計算其與各個簇中心的距離dp,mi，并將 p賦予最類似（對應(yīng)dp,mi最?。┑拇?；

步驟3 更新簇中心 mi(i=1,2,...,k).

步驟4 根據(jù)式（1）計算標(biāo)準(zhǔn)測度E，如果相鄰兩次迭代的E的差值的絕對值小于給定限定值，則算法終止，否則，重復(fù)步驟2.

明朝繼承元朝的東北疆域后，于明成祖永樂七年(1409)置奴兒干都指揮使司(簡稱奴兒干都司)，統(tǒng)轄包括今庫頁島、北海道在內(nèi)的黑龍江流域。

在大量的公交單程時間樣本數(shù)據(jù)中通常存在著一些臟數(shù)據(jù)或異常數(shù)據(jù)（本文統(tǒng)稱異常數(shù)據(jù)）[10]，例如因GPS設(shè)備故障或信號不好造成部分記錄丟失，從而形成了一些超長單程時間記錄；因GPS定位誤差或匹配誤差造成異常的單程時間記錄；因車輛故障或交通事故等造成的異常單程時間.上述設(shè)計的K-means時段劃分算法無法區(qū)別這些異常數(shù)據(jù)，因而，需要在數(shù)據(jù)預(yù)處理時，將這些數(shù)據(jù)事先加以剔除，否則，容易造成時段劃分的偏差.

另外，在高低峰之間一般存在一些過渡時間段，期間，單程時間會逐漸變長或變短.由于該算法屬于硬聚類算法，對于介于高低峰之間的中間值可能會造成較大的聚類誤差.

為了有效處理異常數(shù)據(jù)和過渡時間段的聚類問題，以及減少不必要的距離運算，下面，我們設(shè)計了一個改進(jìn)的K-means時段劃分方法.

2.2 改進(jìn)的K-means算法

對K-means算法的改進(jìn)主要包括以下三個方面：初始簇中心的選擇，優(yōu)化距離計算和簇中心的更新.

(1)改進(jìn)的初始簇中心選擇方法.

隨機(jī)選擇k個初始簇中心，可能會造成簇中心過于集中或者不能均勻地分散在整個數(shù)據(jù)空間，從而導(dǎo)致收斂所需的迭代次數(shù)增多，甚至陷入局部最優(yōu)解，影響聚類結(jié)果的準(zhǔn)確性.為了盡量避免上述問題，下面設(shè)計了一個改進(jìn)的初始簇中心選擇方法，使得初始簇中心之間能夠保持一定的間距、分布更為均勻.具體步驟如下：

首先，從單程時間集合P中隨機(jī)選擇一個初始簇中心，作為第一個簇中心m1.然后，按式(3),根據(jù)已確定的 j-1(2≤j≤k)個簇中心,逐個選擇第 j個簇中心mj,直到選擇出k個簇中心.

式中 dp,mj——對象 p到簇中心mj(j=1,2,...,k)的距離.

在步驟2中，需要計算每個對象p與各個簇中心的距離.然而ELKAN等人研究分析后發(fā)現(xiàn)很多距離的計算都是不必要的，因而提出了基于三角形不等式原理來避免冗余的距離計算[11]，其中三角形不等式定理即兩邊之差小于第三邊和三角形兩邊之和大于第三邊.用其來避免基礎(chǔ)K-means算法中冗余距離計算的兩個定理如下[11].

定 理1 ?mi,mj(1≤i,j≤k),?p∈P ，如 果2dp,mi≤dmi,mj，那么dp,mi≤dp,mj.其中，dmi,mj表示簇中心mi到mj之間的距離.

定 理2 對 ?mi,mj(1≤i,j≤k) ，都 有dp,mj≥max{0,dp,mi-dmi,mj}成立.

由定理1可知，如果對象 p 滿足2dp,mi≤dmimj，根據(jù)定理1可以判定dp,mi≤dp,mj，因此沒有必要繼續(xù)計算 dp,mj.特別地，如果 2dp,mi≤mini≠jdmi,mj，根據(jù)定理1可以判定mi是對象p距離最近的中心，因而沒必要計算對象p和其它聚類中心的距離，這樣避免了多余的距離計算.

由定理2可知，如果dp,mj的下界max{0,dp,mi-dmi,mj}大于dp,mi，則沒有必要計算dp,mj，這樣也可以避免多余的距離計算，達(dá)到優(yōu)化計算的目的.

(3)改進(jìn)的簇中心更新算法.

基本的K-means算法屬于硬聚類算法，對介于高低峰之間的中間值可能會造成較大的聚類誤差[12].為了減少硬聚類的誤差，本文改進(jìn)了簇中心mi的更新策略,即對于介于兩個簇Ci和Cj之間的任意對象p，用式(4)替代式(2)更新簇中心mi.

式(4)中采用了一個模糊因子αi(0≤αi≤1)，表示對象p對簇中心的影響程度，αi越大則影響越大.ε為臨界值參數(shù)，當(dāng)|dp,mi-dp,mj|/max{dp,mi,dp,mj}小于該臨界值時，對象p對簇中心的影響被減弱.

3 案例分析

3.1 湖北十堰4路案例分析

本中通過對十堰市公交4路2011年10月一整月的數(shù)據(jù)的分析，在對23437條單程數(shù)據(jù)按天分上下行統(tǒng)計處理過程中發(fā)現(xiàn)，國慶期間、平日和周末的單程時間的區(qū)段分布特點有比較大的不同，故分別加以分析.由于平日、周末和國慶的分析方法大體相同，所以案例分析中只以平日分析為例.此外，為了避免異常數(shù)據(jù)對時段劃分準(zhǔn)確性的影響，必須事先將各種異常數(shù)據(jù)加以剔除.通過設(shè)置樣本數(shù)據(jù)的上下限閾值，即限定正常情況下樣本可能出現(xiàn)的最大、最小值.從而使得在聚類過程中自動剔除異常數(shù)據(jù)，從而增強(qiáng)算法的適應(yīng)性、降低異常數(shù)據(jù)對算法的影響.對該線路的數(shù)據(jù)研究分析后，正常的單程樣本的下限為20分，上限為70分.因而異常數(shù)據(jù)的自動過濾中所取的下限為20分，上限為70分.數(shù)據(jù)預(yù)處理后平日上下行的單程時間樣本數(shù)據(jù)分別如圖2和圖3所示.圖2和圖3分別給出了平日上下行的單程時間樣本數(shù)據(jù)的散點圖.

根據(jù)公交線路特點,設(shè)定簇的個數(shù)k=4，分別對應(yīng)低峰、平峰、小高峰和高峰時段.臨界值選取了四種情形，即ε∈{0,0.25,0.5,1}分別進(jìn)行運營時段劃分，結(jié)果詳見表1.

表1 利用改進(jìn)的K-means算法依據(jù)不同ε值的運營時段劃分Table 1 The time periods generated by the improved K-means algorithm with differentε

從表1可見，由于高低峰過渡時段中居中的部分（即高峰時段的1/4部分）單程時間變化率較大，因而臨界值選取ε=0.25與現(xiàn)實規(guī)律更為符合.為了驗證上述時段分析結(jié)果的合理性，下面闡述實際調(diào)研結(jié)果，以驗證聚類算法劃分運營區(qū)段的合理性.十堰4路實際的公交運營狀況是第一個高峰出現(xiàn)在早上7:00到8:30之間，這個時候的單程時間增加迅速，從開始的30分增加到45分左右，有的甚至達(dá)到了1個小時.這個時間段單程時間出現(xiàn)高峰的原因主要是，此時處于早高峰時期，客流主要是上班上學(xué)人群，不管是乘坐公交還是駕私家車的人群都達(dá)到了一天中最多的時候，加上路面的交通狀況擁堵，公交運營中很容易產(chǎn)生大間隔，造成單程時間大幅度增加.由此可見，改進(jìn)的K-means算法與現(xiàn)實中的規(guī)律較為吻合，驗證了其理論的正確性.而傳統(tǒng)的K-means算法則劃分的早高峰時間段較小，與現(xiàn)實不太吻合.同理，其它的高峰時間段K-means算法所劃分的時間段均出現(xiàn)了高峰時間段劃分區(qū)間較小的現(xiàn)象，而改進(jìn)算法則很好地克服了這個問題，其時間段的劃分及各時段內(nèi)的單程均值與上述介紹的十堰4路公交實際情況基本吻合.

本文利用K-means聚類算法和改進(jìn)的K-means聚類算法分別進(jìn)行了時段劃分，結(jié)果如圖2和圖3所示，其中，虛線和黑細(xì)線分別代表K-means和改進(jìn)的K-means聚類算法(ε=0.25)所計算出的時段劃分結(jié)果，黑粗線代表兩種方法的分割線重合.

從圖2和圖3中我們可以看出，單程時間的全天分布都呈現(xiàn)出四個波峰段，早高峰、兩個午高峰、晚高峰.其中，在上行的晚高峰時段單程時間明顯最長，高峰時段也持續(xù)最長.

圖2 十堰4路單程時間樣本及兩種K-means聚類算法的時段劃分結(jié)果（平日上行）Fig.2 Trip times and time periods produced by two K-means algorithms(Weekday,outbound)

圖3 十堰4路單程時間樣本及兩種K-means聚類算法的時段劃分結(jié)果（平日下行）Fig.3 Trip times and time periods produced by two K-means algorithms(Weekday,inbound)

3.2 海南?？?路案例分析

本中通過對海口市公交4路2010年7月平日上行4237條單程數(shù)據(jù)的研究分析，設(shè)置樣本數(shù)據(jù)的上下限閾值，即異常數(shù)據(jù)的自動過濾中所取的下限為30分，上限為80分.數(shù)據(jù)預(yù)處理后平日上行的單程時間樣本數(shù)據(jù)分別如圖4所示.對臨界值ε∈{0,0.25,0.5,1}這四種情形分別劃分出的運營時段如表2所示.

由于高低峰過渡時段中居中的部分(即高峰時段的1/4部分)單程時間變化率較大，因而臨界值選取ε=0.25與現(xiàn)實規(guī)律更為符合.本文利用K-means聚類算法和改進(jìn)的K-means聚類算法分別進(jìn)行了時段劃分，結(jié)果如圖4所示.其中，虛線和黑細(xì)線分別代表K-means和改進(jìn)的K-means聚類算法(ε=0.25)所計算出的時段劃分結(jié)果，黑粗線代表兩種方法的分割線重合了.文中K-means聚類算法和改進(jìn)的K-means聚類算法所得出的結(jié)果與實際公交規(guī)律均較為符合，改進(jìn)的K-means聚類算法更貼合實際一些.

圖4 海口4路單程時間樣本及兩種K-means聚類算法的時段劃分結(jié)果（平日上行）Fig.4 Trip times and time periods produced by two K-means algorithms(Weekday,outbound)

4 研究結(jié)論

本文圍繞公交運營時段劃分展開了深入研究，創(chuàng)新性地提出基于聚類方式的公交運營時段劃分方法.利用聚類方法能夠更為客觀準(zhǔn)確地劃分運營時段，克服了手工劃分方法主觀性和精度不高的缺點.通過對公交GPS運營記錄數(shù)據(jù)的挖掘，提出了一個基于K-means聚類方法的公交運營時段劃分方法，并進(jìn)一步從初始簇中心點的選擇、異常數(shù)據(jù)的自動過濾、基于三角形不等式和模糊聚類的簇中心的更新等三個方面改進(jìn)了該K-means聚類時段劃分方法.

通過對十堰市4路和?？谑?路的實際公交運營數(shù)據(jù)進(jìn)行案例分析，基本的K-means算法和改進(jìn)的K-means算法都能夠基于單程時間樣本求解出運營時段的劃分結(jié)果.實驗結(jié)果表明：兩種算法得到的時段劃分與現(xiàn)實規(guī)律都基本吻合.但是，基本的K-means算法劃分的高峰時間段有些偏窄，而改進(jìn)的K-means算法所劃分的時間段及其單程均值與現(xiàn)實規(guī)律更加吻合.在編制車輛運營計劃時，必須確定時刻表中所有單程任務(wù)的時間，目前國內(nèi)企業(yè)操作時均采用人工經(jīng)驗法.文中案例分析部分中的十堰4路和?？?路就是基于人工經(jīng)驗的方法，而在實際運營中的單程時間是受道路交通條件、客流等多方面因素影響的，變化規(guī)律復(fù)雜，憑借人工經(jīng)驗難以精確把握，必須基于大量的真實數(shù)據(jù)，采用科學(xué)的統(tǒng)計工具來分析，這種工作量是人工難以負(fù)擔(dān)的.從該角度上來說，本方法的優(yōu)點就是可以從大量的現(xiàn)實的運營紀(jì)錄中，準(zhǔn)確分析單程時間的變化規(guī)律，劃分時間段，并求出每個時間段中的平均單程時間，這為進(jìn)一步的分時段進(jìn)行運營分析，以及編制高準(zhǔn)點率的運營調(diào)度方案奠定了重要基礎(chǔ).

[1]Ceder A.Public-transport vehicle scheduling with multi vehicle-type[J].Journal of Transportation Research,2011,19(3),485-497.

[2]Hickman M,Mirchandani P,Vo? S(Eds).Computer-aid?ed systems in public transport[C]//Lecture Notes in Eco?nomics and Mathematical Systems,Volume 600.Berlin:Springer,2008.

[3]Salicrú M,Fleurent C,Armengol J M.Timetable-based operation in urban transport:Run-time optimisation and improvements in the operating process[J].Transporta?tion Research Part A,2011,45(8):721-740.

[4]Carey M.Reliability of interconnected scheduled servic?es[J].European Journal of Operational Research,1994,79(1):51-72.

[5]楊新苗，王煒，尹紅亮，等.基于公交調(diào)度峰值曲線的優(yōu)化方法[J].東南大學(xué)學(xué)報，2001，31(3):31-35.[YANGX M,WANG W,YIN H L,et al.A new method for transit peak value curve optimization[J].Journal of Southeast University,2011,31(3):31-35.]

[6]徐甲，沈吟東.基于AVL數(shù)據(jù)的單程時間參數(shù)設(shè)置方法[J].交通運輸系統(tǒng)工程與信息，2012,12(5):39-45.[XU J,SHEN Y D.Setting scheduled trip time based on AVL data[J].Jo urnal of Transportation Systems Engi?neering and Information Technology 2012,12(5):39-45.]

[7]張景，沈吟東.基于定位數(shù)據(jù)的公交時間站點自動選擇方法[J].交通運輸系統(tǒng)工程與信息，2012,12(6):60-65.[ZHANG J,SHEN Y D.Auto?matic selection of time points based on AVL data[J].Journal of Transportation Systems Engineering and Infor?mation Technology 2012,12(6):60-65.]

[8]Shen Y,Xia J.Integrated bus transit scheduling for the Beijing bus group based on a unified mode of operation[J].International Transactions in Operational Research,2009,16(2):227-242.

[9]黃震華，向陽，張波.一種進(jìn)行K-Means聚類的有效方法[J].模式識別與人工智能，2010,23(4):516-521.[HUANG Z H,XIANG Y,ZHANG B.An effecient meth?od for K-means clustering[J].Pattem Recognition and Aitificial Intelligence,2010,23(4):516-521.]

[10]Ceder A.Optimal multi-vehicle type transit timetabling and vehicle scheduling[J].Procedia Social and Behavior?al Sciences,2011,20(0)：19-30.

[11]Elkan C.Using the trangle inequality to accelerate K-means[C]//Proceedings of Twentieth International Con?ference on Machine Learning.Washington,DC,USA,2003:1-7.

[12] 劉健，張寧.基于模糊聚類的城際高鐵乘客出行行為實證研究[J].交通運輸系統(tǒng)工程與信息，2012,12(6):100-105.[LIU J,ZHANG N.Empirical research of inter?city high-speed rail passengers’travel behavior based on fuzzy clustering model[J].2012,12(6):100-105.]