基于IC卡數(shù)據(jù)的公交路線(xiàn)聚合算法

戚陽(yáng) 黃信程 張錦旺 何煦 于海洋

【摘 要】公交運(yùn)行線(xiàn)路的制定需要了解區(qū)域內(nèi)乘客最常用的通勤線(xiàn)路，本文提出了一種基于Apriori算法、DBSCAN算法和模糊支撐樹(shù)聚類(lèi)的公交路線(xiàn)聚合算法，可以在已知路網(wǎng)拓?fù)浣Y(jié)構(gòu)以及區(qū)域內(nèi)客流OD特征的條件下，求解區(qū)域內(nèi)的典型路線(xiàn)。本文基于深圳市公交IC卡數(shù)據(jù)驗(yàn)證了所提出方法的有效性。

【關(guān)鍵詞】公交路線(xiàn)聚合；典型路線(xiàn)；Apriori算法；DBSCAN算法；模糊支撐樹(shù)聚類(lèi)

1.引言

隨著經(jīng)濟(jì)的發(fā)展和人口數(shù)量的增加，我國(guó)一線(xiàn)城市逐漸暴露出公共交通運(yùn)載能力與出行需求不匹配的問(wèn)題，交通區(qū)域發(fā)展出現(xiàn)了不平衡的態(tài)勢(shì)。以深圳市為例，城市內(nèi)不同的地區(qū)職住分離特征愈來(lái)愈明顯。目前深圳市以福田、南山、羅湖為主要就業(yè)地，以寶安、龍華、龍崗為主要居住地，因上班導(dǎo)致的平均通勤距離達(dá)到17.9公里。特殊的城市空間結(jié)構(gòu)，給深圳市的城市交通帶來(lái)大規(guī)模潮汐性出行需求。而由于傳統(tǒng)的公交網(wǎng)絡(luò)的布設(shè)不符合如今的出行需求總量，導(dǎo)致有效的供給能力不能滿(mǎn)足群眾多樣化、多層次的出行需求，使得有條件的市民傾向于選擇個(gè)體化出行方式。大量私家車(chē)的上路給交通運(yùn)輸網(wǎng)絡(luò)帶來(lái)極大的壓力，加重了城市道路的擁堵現(xiàn)象，也加劇了空氣污染等問(wèn)題。

為了應(yīng)對(duì)上述問(wèn)題，在當(dāng)今互聯(lián)網(wǎng)+興起的大背景下，定制公交的概念被提出。定制公交可以以用戶(hù)提交的需求數(shù)據(jù)為主，結(jié)合公共交通數(shù)據(jù)、小區(qū)住房數(shù)據(jù)以及地理信息等多維度數(shù)據(jù)，通過(guò)人工智能、機(jī)器學(xué)習(xí)、聚合算法等各種大數(shù)據(jù)技術(shù)，聚合生成線(xiàn)路，為白領(lǐng)用戶(hù)提供一人一座，家（住宅區(qū)）和公司（辦公區(qū)）之間直達(dá)的定制出行服務(wù)。大數(shù)據(jù)技術(shù)的應(yīng)用有助于公交車(chē)線(xiàn)路的高效配置，提高車(chē)輛的有效路段里程，進(jìn)而提高交通運(yùn)輸效率；此外，大數(shù)據(jù)分析也具有較高預(yù)測(cè)能力，可降低誤報(bào)和漏報(bào)的概率，可隨時(shí)針對(duì)公共交通的動(dòng)態(tài)性給予實(shí)時(shí)監(jiān)控。因此，在駕駛者無(wú)法預(yù)知交通的擁堵可能性時(shí)，大數(shù)據(jù)亦可幫助用戶(hù)預(yù)先了解。除了提升用戶(hù)的出行體驗(yàn)，也對(duì)緩解交通擁堵有很大價(jià)值。

為了合理地設(shè)置定制公交的線(xiàn)路，需要對(duì)行人的出行需求進(jìn)行調(diào)查，掌握乘客的出行規(guī)律，并從需求中分析典型的出行路線(xiàn)用于制定行車(chē)路線(xiàn)。目前，很多研究者致力于研究基于公交IC卡等數(shù)據(jù)提取出出行需求特征的方法，一般將出行特征表示為OD矩陣的形式，矩陣中各個(gè)元素表示所研究區(qū)域的兩個(gè)區(qū)塊之間的出行需求。然而，如何基于提取的OD矩陣分析挖掘出最典型的車(chē)輛行車(chē)線(xiàn)路，仍然是需要不斷研究的一個(gè)問(wèn)題，目前，大多研究都將這個(gè)問(wèn)題轉(zhuǎn)化為聚類(lèi)問(wèn)題，例如K-means聚類(lèi)等。

本文提出了一種公交路線(xiàn)聚合算法，在分析得到交通路網(wǎng)拓?fù)浣Y(jié)構(gòu)的情況下，采用Apriori算法[1]和DBSCAN算法[2]對(duì)人們的公共交通出行路線(xiàn)、公交站點(diǎn)、出行時(shí)段進(jìn)行分析歸類(lèi)。隨后分析現(xiàn)有公交信息，確定候選典型行車(chē)路線(xiàn)，最后根據(jù)模糊支撐樹(shù)聚類(lèi)算法實(shí)現(xiàn)出行路線(xiàn)最優(yōu)化，本文所提出的算法的流程圖如圖1。

2.算法介紹

2.1 城市道路網(wǎng)絡(luò)拓?fù)浣７椒?/p>

將城市道路網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)抽象為網(wǎng)絡(luò)模型，目前主要有兩種方法：一種稱(chēng)為為主方法（Primal aproach），是將道路的交叉口抽象為圖的節(jié)點(diǎn)，連接交叉口之間的路段抽象為邊或??；這種方法的特定是簡(jiǎn)單直觀，保留了較完整的地理相關(guān)性，是傳統(tǒng)交通網(wǎng)絡(luò)建模方法，也是目前大部分GIS軟件所采用的建模方法。另一種為對(duì)偶法（Dual approach），可以認(rèn)為是主方法的對(duì)偶，即將道路抽象為節(jié)點(diǎn)，道路與道路的連接關(guān)系表示為圖的邊或弧。一條完整道路的構(gòu)建是將連續(xù)的路段按一定的規(guī)則綜合而成，目前主要有軸線(xiàn)法、名稱(chēng)法和角度法。其中，軸線(xiàn)法采用軸線(xiàn)代表道路，是依據(jù)人的視覺(jué)將近似直線(xiàn)的路段合并為一條道路并用一條軸線(xiàn)表示；名稱(chēng)法是指在合并路段時(shí)依據(jù)道路的名稱(chēng)，將具有相同名稱(chēng)的路段連接在一起；角度法的合并原則是依據(jù)格斯塔的連續(xù)性原則，通過(guò)計(jì)算路段與路段的夾角，并根據(jù)設(shè)定的夾角閾值生成道路。

實(shí)踐中這兩種建模方法各有特點(diǎn)。主方法直觀簡(jiǎn)單，保留了路網(wǎng)的布局特點(diǎn)；對(duì)偶法忽略了地理實(shí)體的一些地理意義，如地理位置、道路長(zhǎng)寬等，更適合探索網(wǎng)絡(luò)結(jié)構(gòu)下的功能意義。對(duì)偶法中合并路段的幾種方法也各有優(yōu)缺點(diǎn)。例如，軸線(xiàn)法軸線(xiàn)的生成主要依據(jù)人的視覺(jué)判斷，合并規(guī)則引入主觀因素，因此不同的人可能得到不同的軸線(xiàn)地圖，即方法不具有唯一性；名稱(chēng)法的局限性在于合并規(guī)則完全依賴(lài)屬性信息，忽略了空間特性并喪失了直觀性，在缺少道路名稱(chēng)信息或信息不準(zhǔn)確的情況下無(wú)法完成；角度法的合并則完全從圖形角度考慮，不受人為因素和屬性因素影響。

2.2 基于Apriori算法和DBSCAN算法的公交路線(xiàn)聚類(lèi)

（1）Aprioi算法

Apriori算法是常用的用于挖掘出數(shù)據(jù)關(guān)聯(lián)規(guī)則的算法，它用來(lái)找出數(shù)據(jù)值中頻繁出現(xiàn)的數(shù)據(jù)集合，找出這些集合的模式有助于我們做一些決策。比如在常見(jiàn)的超市購(gòu)物數(shù)據(jù)集，或者電商的網(wǎng)購(gòu)數(shù)據(jù)集中，如果我們找到了頻繁出現(xiàn)的數(shù)據(jù)集，那么對(duì)于超市，我們可以?xún)?yōu)化產(chǎn)品的位置擺放，對(duì)于電商，我們可以?xún)?yōu)化商品所在的倉(cāng)庫(kù)位置，達(dá)到節(jié)約成本，增加經(jīng)濟(jì)效益的目的。

Aprior算法的目標(biāo)是找到樣本中最大K值的K項(xiàng)頻繁集，本文采用支持度作為頻繁集的判定標(biāo)準(zhǔn)。例如如果找到符合支持度的頻繁集AB和ABE，就保留ABE，因?yàn)锳B是2項(xiàng)頻繁集，而ABE是3項(xiàng)頻繁集。

Apriori算法采用了迭代的方法，先搜索出候選1項(xiàng)集及對(duì)應(yīng)的支持度，剪枝去掉低于支持度的1項(xiàng)集，得到頻繁1項(xiàng)集。然后對(duì)剩下的頻繁1項(xiàng)集進(jìn)行連接，得到候選的頻繁2項(xiàng)集，篩選去掉低于支持度的候選頻繁2項(xiàng)集，得到真正的頻繁2項(xiàng)集，以此類(lèi)推，迭代下去，直到無(wú)法找到頻繁k+1項(xiàng)集為止，對(duì)應(yīng)的頻繁K項(xiàng)集的集合即為算法的輸出結(jié)果。

（2）DBSCAN算法

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）是一個(gè)比較有代表性的基于密度的聚類(lèi)算法。與劃分和層次聚類(lèi)方法不同，它將簇定義為密度相連的點(diǎn)的最大集合，能夠把具有足夠高密度的區(qū)域劃分為簇，并可在噪聲的空間數(shù)據(jù)庫(kù)中發(fā)現(xiàn)任意形狀的聚類(lèi)。

DBSCAN的幾個(gè)概念：

Ε鄰域：給定對(duì)象半徑為Ε內(nèi)的區(qū)域稱(chēng)為該對(duì)象的Ε鄰域；

核心對(duì)象：如果給定對(duì)象Ε鄰域內(nèi)的樣本點(diǎn)數(shù)大于等于MinPts，則稱(chēng)該對(duì)象為核心對(duì)象；

直接密度可達(dá)：對(duì)于樣本集合D，如果樣本點(diǎn)q在p的Ε鄰域內(nèi)，并且p為核心對(duì)象，那么對(duì)象q從對(duì)象p直接密度可達(dá)；

密度可達(dá)：對(duì)于樣本集合D，給定一串樣本點(diǎn)p1，p2….pn，p= p1，q= pn，假如對(duì)象pi從pi-1直接密度可達(dá)，那么對(duì)象q從對(duì)象p密度可達(dá)；

密度相連：存在樣本集合D中的一點(diǎn)o，如果對(duì)象o到對(duì)象p和對(duì)象q都是密度可達(dá)的，那么p和q密度相聯(lián)。

2.3 基于模糊支撐樹(shù)聚類(lèi)算法生成區(qū)域內(nèi)典型行車(chē)路線(xiàn)

區(qū)域典型行車(chē)路線(xiàn)庫(kù)由模糊支撐樹(shù)聚類(lèi)算法實(shí)現(xiàn)。根據(jù)OD站點(diǎn)信息利用模糊支撐樹(shù)聚類(lèi)算法的程序生成最優(yōu)定制公交出行路線(xiàn)。最終該區(qū)域中各OD間的最優(yōu)公交出行線(xiàn)路通過(guò)聚合構(gòu)成區(qū)域典型行車(chē)路線(xiàn)。下面是對(duì)模糊支撐樹(shù)聚類(lèi)算法的介紹：

（1）支撐樹(shù)

支撐樹(shù)算法也叫生成樹(shù)算法，在圖論的數(shù)學(xué)領(lǐng)域中，如果連通圖 G的一個(gè)子圖是一棵包含G 的所有頂點(diǎn)的樹(shù)，則該子圖稱(chēng)為G的生成樹(shù)（SpanningTree）。生成樹(shù)是連通圖的包含圖中的所有頂點(diǎn)的極小連通子圖。圖的生成樹(shù)不唯一。從不同的頂點(diǎn)出發(fā)進(jìn)行遍歷，可以得到不同的生成樹(shù)。常用的生成樹(shù)算法有DFS生成樹(shù)、BFS生成樹(shù)、PRIM 最小生成樹(shù)和Kruskal最小生成樹(shù)算法。

（2）模糊支撐樹(shù)聚類(lèi)方法

模糊決策樹(shù)算法是傳統(tǒng)決策樹(shù)算法的一個(gè)擴(kuò)充和完善，使得決策樹(shù)學(xué)習(xí)的應(yīng)用范圍擴(kuò)大到了能處理不確定性。模糊決策樹(shù)學(xué)習(xí)的歸納結(jié)果與傳統(tǒng)的比較，由于合理地處理了不精確信息，從而有著更強(qiáng)的分類(lèi)能力及穩(wěn)健性，使得知識(shí)表示的方式更為自然。由于能生成不同水平和不同置信度的推理規(guī)則，故而提供了一種構(gòu)造專(zhuān)家系統(tǒng)的有效途徑，并可為決策者提供豐富的決策信息。

3.實(shí)驗(yàn)結(jié)果

本文采用深圳市2012年8月6日至2012年8月10日的全市公交 IC 卡刷卡數(shù)據(jù)，以及相應(yīng)時(shí)期的車(chē)站坐標(biāo)、線(xiàn)路長(zhǎng)度以及站距數(shù)據(jù)，來(lái)驗(yàn)證本文所提出的算法。選用這五天數(shù)據(jù)的原因?yàn)?，這五天為連續(xù)工作日（周一至周五），并且沒(méi)有假期。而在此階段，學(xué)生大多已經(jīng)放假，其中的通勤乘客主要是以上班為主，滿(mǎn)足本文的研究對(duì)象。

對(duì)該周工作日的地鐵刷卡卡數(shù)及記錄數(shù)進(jìn)行統(tǒng)計(jì)，得到表格如下：

隨后統(tǒng)計(jì)每張卡的刷卡次數(shù)，統(tǒng)計(jì)結(jié)果如圖3：

通過(guò)設(shè)置合理的支持度閾值，基于Aprioi算法可以成功地識(shí)別乘客的通勤線(xiàn)路

為了解決共站問(wèn)題，即有些車(chē)站實(shí)質(zhì)上是一個(gè)車(chē)站，卻因?yàn)榫€(xiàn)路不同，有不同的站號(hào)；有些車(chē)站距離很近，乘客有多種出行選擇，而不同車(chē)站識(shí)別結(jié)果卻不同；本文采取利用 DBSCAN 算法對(duì)站點(diǎn)進(jìn)行聚類(lèi)。算法輸入的數(shù)據(jù)為深圳公交車(chē)站站距位置表，其中包括了公交、地鐵的車(chē)站站距以及坐標(biāo)。全表共有 61136 個(gè)不同的車(chē)站，將車(chē)站標(biāo)識(shí)以及坐標(biāo)輸入算法程序，之后新建字段―新車(chē)站標(biāo)識(shí)‖，將算法識(shí)別后的結(jié)果，每個(gè)簇賦新值存入新車(chē)站標(biāo)識(shí)中。在運(yùn)行完算法后，最終得到新車(chē)站標(biāo)識(shí) 7264 個(gè)。將全部 61136 個(gè)站點(diǎn)壓縮為 7264個(gè)站點(diǎn)，壓縮率 11.88%，為解決共站問(wèn)題起到了很好的效果。

通勤乘客的出行時(shí)段雖然較為規(guī)律和固定，但是卻又有波動(dòng)性，尤其是下班時(shí)間。一般上班時(shí)間是有要求固定的，而下班時(shí)間卻并不固定，因?yàn)闀?huì)有加班或是下班后有活動(dòng)的特殊情況。因此，采用時(shí)段模糊處理。改進(jìn)方法后，再次對(duì)通勤乘客進(jìn)行了識(shí)別，識(shí)別結(jié)果如下：

隨后我們基于模糊支撐樹(shù)聚類(lèi)生成了區(qū)域內(nèi)的典型行車(chē)路線(xiàn)，所得到的結(jié)果與我們先驗(yàn)的認(rèn)知較為相符。

4.結(jié)束語(yǔ)

本文提出了一種公交路線(xiàn)聚合算法，基于交通路網(wǎng)拓?fù)浣Y(jié)構(gòu)和出行客流OD特征，采用Apriori算法、DBSCAN算法和模糊支撐樹(shù)聚類(lèi)算法分析區(qū)域內(nèi)每位乘客的通勤路線(xiàn)并最終求解了區(qū)域內(nèi)的典型行車(chē)路線(xiàn)。本文、基于深圳市公交IC卡刷卡數(shù)據(jù)對(duì)所提出的算法進(jìn)行了驗(yàn)證，證明了本文提出的算法的有效性。

基金項(xiàng)目：深圳市科技計(jì)劃項(xiàng)目（KJYY20160331162313860）

參考文獻(xiàn)：

[1] Agrawal R，Srikant R.Fast algorithms for mining association rules[M]// Readings in database systems（3rd ed.）.Morgan Kaufmann Publishers Inc.1996.

[2] Ester M，Kriegel H P，Xu X.A density-based algorithm for discovering clusters a density-based algorithm for discovering clusters in large spatial databases with noise[C]// International Conference on Knowledge Discovery & Data Mining.1996.

（作者單位：深圳市東部公共交通有限公司）