王成 崔紫薇 杜梓林 高悅爾

摘 要：針對缺失公交到站信息修補方法考慮因素較少、準確度低、魯棒性差的現(xiàn)狀，提出了基于DBSCAN算法和多源數(shù)據(jù)的缺失公交到站數(shù)據(jù)修補方法。該方法使用公交全球定位系統(tǒng)（GPS）、公交集成電路卡（IC）等多源數(shù)據(jù)進行缺失到站信息的修補。對于缺失的到站名稱、到站經緯度數(shù)據(jù)，用已有完整到站數(shù)據(jù)和靜態(tài)線路信息關聯(lián)分析進行修補。對于缺失的到站時刻數(shù)據(jù)，則按以下步驟進行修補：首先，對每一個缺失數(shù)據(jù)站點與其最近的未缺失數(shù)據(jù)站點，將這兩站點間歷史完整到站數(shù)據(jù)的行程時間和班次時序進行基于DBSCAN算法的聚類;其次，判斷研究班次的兩個相鄰的數(shù)據(jù)完整的班次所屬簇是否為同一個簇，若為同一個簇則不作改變，否則將兩個簇合并;最后，將簇中點對應最大行程時間作為缺失行程時間判斷是否有乘客在該站點上車刷卡，若有則由乘客開始刷卡時刻推算到站時刻，若無則將簇中點對應最大、最小行程時間的均值作為缺失行程時間推算到站時刻。以廈門市公交到站數(shù)據(jù)為例，在缺失到站名稱、經緯度修補中，基于GPS數(shù)據(jù)聚類的方法、基于極大概率估計的方法和所提方法皆可進行100%的修補;在缺失到站時刻修補中，所提方法的平均相對誤差比兩種對比方法分別低0.030-1%和0.000-4%，相關系數(shù)比對比方法分別高0.005和0.007-5。實驗結果表明，所提算法在缺失公交到站數(shù)據(jù)修補中能有效提高修補的準確度，降低缺失站點個數(shù)變化對于準確度的影響。

關鍵詞：缺失到站數(shù)據(jù)修補;DBSCAN算法;到站經緯度;到站時刻;多源數(shù)據(jù)

中圖分類號： TP311

文獻標志碼：A

Repairing of missing bus arrival data based on DBSCAN algorithm and multisource data

WANG Cheng1*， CUI Ziwei1， DU Zilin1， GAO Yueer2

1.College of Computer Science and Technology， Huaqiao University， Xiamen Fujian 361021， China;

2.School of Architecture， Huaqiao University， Xiamen Fujian 361021， China

Abstract：

In order to solve the problem that the existing repair methods for missing bus arrival information have little factors considered， low accuracy and poor robustness， a method to repair missing bus arrival data based on DBSCAN （DensityBased Spatial Clustering of Applications with Noise） algorithm and multisource data was proposed. Bus GPS （Global Positioning System） data， IC （Integrated Circuit） card data and other source data were used to repair the missing arrival information. For the name， longitude and latitude data of the missing arrival station， the association analysis of complete arrival data and static line information were carried out to repair. For the missing arrival time data， the following steps were taken to repair. Firstly， for every missing data station and its nearest nonmissing data station， the travel time and schedule in the historical complete arrival data between the two stations were clustered based on DBSCAN algorithm. Secondly， whether the two adjacent runs of the studied bus with complete data belonged to the same cluster was judged， and if they belonged to the same cluster， th cluster would not change， otherwise the two clusters would be merged. Finally， the maximum travel time corresponding to the cluster midpoint was used as the missing travel time to determine whether there was a passenger swiping his card to board the bus at this station or not， if so， the arrival time was calculated from the time of swiping cards， and if not， the mean of the maximum and minimum travel time corresponding to the cluster midpoint was used as the missing travel time to calculate the arrival time. Taking Xiamen bus arrival data as examples， in the repair of name， longitude and latitude of the missing arrival station， the clustering method based on GPS data， the maximum probability estimation method and the proposed method can repair the data by 100.00%. In the repair of missing arrival time， the mean relative error of the proposed method is 0.030-1% and 0.000-4% lower than that of two comparison methods respectively， and the correlation coefficient of the proposed method is 0.005 and 0.007-5 higher than that of two comparison methods respectively. The simulation results show that the proposed method can effectively improve the accuracy of repair of missing bus arrival data， and reduce the impact of the number of missing stations on accuracy.

Key words：

bus missing arrival data repair; DensityBased Spatial Clustering of Applications with Noise （DBSCAN） algorithm; longitude and latitude of arrival station; arrival time; multisource data

0?引言

受城市建筑陰影效應等影響，公交到站數(shù)據(jù)會出現(xiàn)缺失現(xiàn)象，嚴重影響公交車輛運營特征的分析、乘客上車站點識別等。現(xiàn)有研究表明，3.75%的公交到站數(shù)據(jù)缺失即可造成超過25%的乘客上車站點匹配失敗[1]，因此公交缺失到站數(shù)據(jù)修補是必要的，本文對于公交到站數(shù)據(jù)的到站名稱、經緯度和時刻數(shù)據(jù)進行修補。

公交到站數(shù)據(jù)的修補可根據(jù)使用數(shù)據(jù)類型分為僅使用公交全球定位系統(tǒng)（Global Positioning System， GPS）數(shù)據(jù)和使用多源數(shù)據(jù)兩大類。僅使用公交GPS數(shù)據(jù)方法分為基于統(tǒng)計分析的填充和基于數(shù)據(jù)挖掘的填充?；诮y(tǒng)計分析的填充通過熟悉數(shù)據(jù)集的研究者構建擬合模型、估計統(tǒng)計參數(shù)實現(xiàn)對缺失數(shù)據(jù)的填充，常見方法有線性擬合填充法[2]、均值填充法[3]、概率估算法[4]等，但只用于小樣本數(shù)據(jù)集中，難以適應交通大數(shù)據(jù)分析的需求。基于數(shù)據(jù)挖掘的填充可充分利用海量數(shù)據(jù)的特點、不受研究者對數(shù)據(jù)集熟悉程度的影響進行修補缺失值，常見方法有k最 近 鄰 填 充[5-6]、雙向循環(huán)神經網絡[7]、貝葉斯網絡[8]、聚類方法填充[9-14]等; 但僅使用公交GPS數(shù)據(jù)的方法所使用的數(shù)據(jù)少，獲得的信息不夠全面，因此修補準確度低?；诙嘣磾?shù)據(jù)的修補可分為間接修補和直接修補兩種：間接修補首先通過對伴隨的集成電路（Integrated Circuit， IC）卡刷卡數(shù)據(jù)中缺失信息進行修補，以此推算缺失的GPS到站數(shù)據(jù)，但沒有乘客上（下）車刷卡的站點無法進行修補，常見的方法有基于行程的網絡多模態(tài)特性研究方法[15]、基于刷卡數(shù)據(jù)分離和序列約束站點匹配的方法[16]、基于車輛運營時刻表方法[17]等;直接修補可從根本上對于缺失到站數(shù)據(jù)進行修補，對于無乘客上下車的缺失到站數(shù)據(jù)也可進行修補，修補范圍更廣，可以更好地進行公交運營特征的挖掘，常見的方法有基于車輛運營時刻表、基于極大概率估計的方法[18]等，但這些方法受路段狀況等隨機因素的影響過大、沒有剔除噪聲數(shù)據(jù)的影響，因此缺失值修補的準確度不高。

本文的主要貢獻如下：

1）選擇獲得信息更全面、修補數(shù)據(jù)范圍更廣的多源數(shù)據(jù)進行缺失到站數(shù)據(jù)的直接修補，使用的數(shù)據(jù)為GPS數(shù)據(jù)、IC卡數(shù)據(jù)和靜態(tài)線路信息數(shù)據(jù);

2）對于現(xiàn)有方法噪聲數(shù)據(jù)影響較大的情況，依賴同類數(shù)據(jù)對缺失數(shù)據(jù)進行修補以此降低噪聲影響。獲取同類數(shù)據(jù)時，采用聚類的方法，并且結合了站點間行程時間和完整到站班次時序，以此將后者反映的缺失數(shù)據(jù)班次所在時段內路況、天氣等影響因素信息加入考慮，使修補值更接近實際;

3）同類數(shù)據(jù)常見的聚類方法有基于密度聚類方法[19]和基于劃分聚類方法（如Kmeans聚類算法）[20]等，根據(jù)本文數(shù)據(jù)的特點：聚集數(shù)量不明確和噪聲點影響較大選擇了密度聚類中的DBSCAN（DensityBased Spatial Clustering of Applications with Noise）算法對于數(shù)據(jù)進行聚類;

4）對于現(xiàn)有研究將站點間行程時間取值范圍設置為相同數(shù)值的情況，本文對任意兩站點間的行程時間和完整到站時序進行聚類，使得每一對站點間的行程時間取值范圍具有個性化，以此獲得更準確的同類數(shù)據(jù)和修補值，并使得修補數(shù)據(jù)準確度受缺失站點個數(shù)變化的影響程度低、普適性高。

1?問題描述及分析

1.1?公交到站數(shù)據(jù)介紹

某班次完整公交GPS到站數(shù)據(jù)包括到站編號（本文中用到站編號代替到站名稱說明問題）、車牌號、線路號、站點（東）經度、站點（北）緯度、到站日期、班次和到站時刻（如表1所示）;若某班次缺失1號站點和2號站點到站數(shù)據(jù)，則其原始數(shù)據(jù)僅包含其余站點的到站數(shù)據(jù)（如表1點線以下部分所示）。

1.2?刷卡數(shù)據(jù)及線路數(shù)據(jù)介紹

目前，大部分城市公交乘客只在上車刷卡、下車不刷卡，因此本文使用乘客上車IC刷卡數(shù)據(jù)進行分析，則有某班次同一站點乘客上車IC刷卡數(shù)據(jù)包括卡號、刷卡日期、刷卡時刻、乘坐的線路號和乘坐車輛的車牌號（如表2所示）。

某線路某運營車輛靜態(tài)線路信息示例包括到站編號、車牌號、線路號、站點（東）經度和站點（北）緯度（如表3所示）。

1.3?公交到站數(shù)據(jù)的缺失情況

設S1，S2，…，Sk，…，SK為公交某班次運行中連續(xù)缺失到站GPS數(shù)據(jù)的站點，Sbefore為S1之前到達的最后一個數(shù)據(jù)完整站點，Safter為SK之后到達的第一個數(shù)據(jù)完整站點。如圖1所示，對于某班次，公交到站數(shù)據(jù)的缺失通常分為三種情況：

缺失前半部分數(shù)據(jù)?即公交某班次運行中連續(xù)經過的站點為S1，S2，…，Sk，…，SK，Safter。

缺失中間部分數(shù)據(jù)?又分為連續(xù)多個缺失和單個缺失，后者可視為前者的一種特例，即公交某班次運行中連續(xù)經過的站點為Sbefore，S1，S2，…，Sk，…，SK，Safter。

缺失后半部分數(shù)據(jù)?即公交某班次運行中連續(xù)經過的站點為Sbefore，S1，S2，…，Sk，…，SK。

對于缺失中間部分數(shù)據(jù)，可由缺失數(shù)據(jù)站點前（后）最近的完整到站數(shù)據(jù)站點后推（前推）得到缺失站點相關數(shù)據(jù)，因此可視為缺失前（后）半部分數(shù)據(jù)的特例，本質都為由第一條（最后一條）完整到站數(shù)據(jù)推得未知到站數(shù)據(jù)。因此，后面僅對連續(xù)缺失前半部分到站數(shù)據(jù)的情況進行敘述。

2?缺失公交到站數(shù)據(jù)修補

2.1?缺失到站名稱、經緯度修補

鑒于公交運營線路固定、?？空军c固定的實際情況，可結合完整到站數(shù)據(jù)與靜態(tài)線路信息修補缺失到站名稱、經緯度。三者之間進行關聯(lián)分析修補的方法如圖2所示，對于某班次到站數(shù)據(jù)修補的具體流程為：根據(jù)完整到站數(shù)據(jù)和靜態(tài)線路信息得到缺失到站數(shù)據(jù)的站點編號，再以此對于缺失站點編號的缺失名稱、經緯度進行修補，直至本班次全部站點的到站名稱、經緯度修補完畢（如表4所示），此時，僅有到站時刻數(shù)據(jù)未進行修補。

2.2?缺失到站時刻修補

在連續(xù)缺失前半部分到站數(shù)據(jù)的情況下，設到達站點Safter時刻為Tafter，則從站點Sk到Safter的行程時間為tk，after，取值范圍為Tk，after。設缺失到站數(shù)據(jù)班次所在線路同一行駛方向同一天內，有N班次同時在缺失到站數(shù)據(jù)站點Sk與站點Safter有完整到站數(shù)據(jù)，將N班次按照到達站點Safter的先后排序即有集合{l1，l2，…，ln，…，lN}，對應到達站點Safter的時刻為{Tl1after，Tl2after，…，Tlnafter，…，TlNafter}，并且對應從Sk到Safter的行程時間為{tl1k，after，tl2k，after，…，tlnk，after，…，tlNk，after}。某班次在第k個站點Sk的缺失到站時刻Tk修補步驟如下所示：

步驟1?將N趟班次按照到達站點Safter的先后順序，與對應從Sk到Safter的行程時間，整合成為包含N趟班次的二維空間點集，如下所示：

P={（l1，tl1k，after），…，（ln，tlnk，after），…，（lN，tlNk，after）}（1）

步驟2?給定半徑ε，以及最小個數(shù)M，對步驟1的空間點集合進行聚類得到Nsum個簇，即為{C1，C2，…，Cnsum，…，CNsum}。

步驟3?N趟班次中，缺少數(shù)據(jù)班次在Tafter到達站點Safter后第一個到達此站點的班次為：

laftern=argmin{Tlnafter|Tlnafter>Tafter，

ln∈{l1，l2，…，ln，…，lN}}（2）

缺少數(shù)據(jù)班次在Tafter到達站點Safter前最后一個到達此站點的班次為（如圖3所示）：

lbeforen=argmax{Tlnafter|Tlnafter

ln∈{l1，l2，…，ln，…，lN}}（3）

步驟4?由步驟2可得，第laftern班次屬于簇Cone，則有Cone中全部點的縱坐標取值范圍，即為行程時間取值范圍為TCone;第lbeforen班次屬于簇Ctwo，則有Ctwo中全部點的縱坐標取值范圍，即為行程時間取值范圍為TCtwo。因此從站點Sk到Safter的行程時間取值范圍為：

Tk，after=TCone∪TCtwo（4）

步驟5?行程時間取值范圍Tk，after的最小值為：

tmink，after=minTk，after（5）

行程時間取值范圍Tk，after的最大值為：

tmaxk，after=maxTk，after（6）

則根據(jù)已知的到達站點Safter時刻為Tafter，判斷在時間段[Tafter-tmaxk，after，Tafter]內是否有乘客刷卡：

如果有，可得第一位刷卡乘客的刷卡時刻為tICk，則有從站點Sk到Safter的行程時間為：

tk，after=Tafter-（tICk-Tp）（7）

其中：Tp表示乘客開始刷卡時刻與車輛進站的時間間隔，如圖4所示;tICk-Tp即為某班次在第k個缺失到站數(shù)據(jù)站點的到站時刻;如果沒有，則從站點Sk到Safter的行程時間為：

tk，after=tmink，after+tmaxk，after2（8）

步驟6?某班次在第k個缺失到站數(shù)據(jù)站點的到站時刻為：

Tk=Tafter-tk，after（9）

2.3?缺失公交到站數(shù)據(jù)修補流程

實際情況中，缺失到站名稱、經緯度與缺失到站時刻同時存在，需要進行基于DBSCAN和多源數(shù)據(jù)的缺失公交到站數(shù)據(jù)修補，流程如圖5所示。

2.4?算法的理論分析與比較

設置基于GPS數(shù)據(jù)聚類的方法[9-14]作為對比實驗的原因在于改變是否使用IC卡刷卡數(shù)據(jù)，可以更好地說明使用伴隨IC卡刷卡數(shù)據(jù)對于缺失到站數(shù)據(jù)修補的影響，因此將對比實驗聚類方法選擇與本文一致的DBSCAN方法?，F(xiàn)有研究表明，多源數(shù)據(jù)可以將多種環(huán)境或對象進行綜合，可以獲得比單一信息源更高質量、更精確、更完全的信息，因此本文方法理論上修補準確度及普適性優(yōu)于基于GPS數(shù)據(jù)聚類的方法。在時、空復雜度方面，本文方法雖對缺失站點行程時間范圍內IC卡刷卡數(shù)據(jù)進行了排序，但此操作遠低于聚類算法的時、空復雜度，因此本文方法的時、空復雜度即為對于N班次歷史行程時間及順序進行基于DBSCAN聚類的時、空復雜度，與使用DBSCAN對GPS數(shù)據(jù)聚類方法的時、空復雜度一樣，與其他常見聚類修補數(shù)值方法的時、空復雜度比較如表5所示。

極大概率估計方法本文方法GPS、IC卡刷卡

相鄰刷卡記錄的固定分離閾值O（NIC）O（NIC）中低

ε、MO（N2）O（N）高高

！根據(jù)情況左右加

注：基于GPS數(shù)據(jù)kmeans聚類的參數(shù)表示迭代次數(shù)、表示聚類類別個數(shù);基于GPS數(shù)據(jù)DBSCAN聚類和本文方法中的參數(shù)ε表示半徑、

M表示最小個數(shù);極大概率估計方法的時、空復雜度中NIC表示某缺失數(shù)據(jù)班次的全部刷卡數(shù)據(jù)。

極大概率估計方法[18]首先擬合缺失站點對間的歷史行程時間分布;其次，根據(jù)相鄰刷卡記錄的固定分離閾值將同一輛車同方向各站的乘客刷卡記錄分離;然后，判斷若有乘客在缺失站點上車刷卡，則將缺失站點的第一條刷卡數(shù)據(jù)時刻作為時間戳，選擇參考點出站時刻到該時間戳的行程時間內，概率最大的到達站點即為缺失到站站點;最后，對于無乘客上車刷卡的站點，通過高斯分布函數(shù)等擬合參考點至站點的歷史行程時間集合，選擇概率最大的歷史行程時間作為缺失行程時間。對于有乘客上車的站點，極大概率估計方法對缺失站點的第一條刷卡數(shù)據(jù)判斷準確度依賴程度較高，此方法相鄰刷卡記錄的固定分離閾值無法根據(jù)不同站點之間的實際情況進行調節(jié)，噪聲點影響較大;對于無乘客上車刷卡的站點，極大概率估計方法將全部歷史行程時間進行擬合分布，但實際中大部分線路早、晚高峰時段的班次總數(shù)少于平峰時段的，因此概率最大的歷史行程時間最有可能為平峰時段的行程時間，不適用于發(fā)生擁堵概率最高的早晚高峰時段缺失數(shù)據(jù)的修補。

與極大概率估計方法相比，本文對歷史行程時間及班次順序進行了聚類，使得相似的數(shù)據(jù)同簇，以此發(fā)現(xiàn)其內在聯(lián)系，基于缺失數(shù)據(jù)班次的相似數(shù)據(jù)推算行程時間取值范圍，隨后再判斷行程時間取值范圍內是否有IC卡刷卡數(shù)據(jù)，若有則根據(jù)第一條刷卡數(shù)據(jù)確定缺失到站時刻，若無則根據(jù)相似行程時間數(shù)據(jù)確定缺失到站時刻。本文基于聚類后的相似數(shù)據(jù)對行程時間取值范圍個性化設置，比基于全部歷史數(shù)據(jù)的行程時間確定更符合實際，因此本文方法理論上修補準確度及普適性優(yōu)于極大概率估計方法。在時、空間復雜度方面，由前文敘述已知，本文方法對于N班次歷史行程時間及順序進行了基于DBSCAN的聚類，所以時間復雜度為O（N2）、空間復雜度為O（N），而極大概率方法雖無需進行聚類且擬合用時較少，但需要對于某缺失數(shù)據(jù)班次的全部NIC條刷卡數(shù)據(jù)進行判斷相鄰刷卡的時間間隔大小，因此時、空復雜度皆為O（NIC）。實際情況中一條線路某天某班次的刷卡數(shù)據(jù)量遠大于該天的班次數(shù)量，因此本文方法的空間復雜度遠低于極大概率方法的空間復雜度，并且在早晚高峰時段缺失數(shù)據(jù)班次的刷卡數(shù)量較多時，本文方法的時間復雜度與極大概率方法的相近。

3?實驗與結果

3.1?數(shù)據(jù)集介紹

本文以廈門市2018年某日為例，對于8*9路上行方向的68個班次2-584條到站數(shù)據(jù)進行統(tǒng)計（每班次38個到站站點），發(fā)現(xiàn)GPS數(shù)據(jù)缺失情況如表6所示。選取到站數(shù)據(jù)完整的8*9路上行方向到達第35個站點時刻為19：33：07的班次，以及此班次GPS到站數(shù)據(jù)的（東）經度、（北）緯度和乘客IC刷卡數(shù)據(jù)。

3.2?檢驗方法和評價標準

檢驗方法?根據(jù)第35個站點的到站數(shù)據(jù)，推得第24～34個站點的到站數(shù)據(jù)，并與真實到站數(shù)據(jù)比較進行方法檢驗。

評價標準?1）使用錯誤修補的比率（False Classify Rate， FCR）[21]對修補的到站名稱、到站經緯度進行檢驗。2）用平均相對誤差指標與相關系數(shù)指標對修補的到站時刻進行檢驗：設平均相對誤差指標為δave，其代表修補值可信程度，數(shù)值越小越說明修補值與真實值差距越小、修補準確度越高;設相關系數(shù)指標為R，其代表修補值與真實值相關性的相關性系數(shù)，數(shù)值越接近1越說明修補方法準確度受缺失站點個數(shù)變化的影響程度越低，即隨著缺失數(shù)據(jù)站點與完整到站數(shù)據(jù)站點的距離變化、修補準確率變化較小。

3.3?缺失公交到站數(shù)據(jù)修補結果

首先，確定DBSCAN聚類算法中最小個數(shù)M的取值，對于研究的N=56班次假設缺失數(shù)據(jù)站點34和完整到站數(shù)據(jù)站點35，隨著最小個數(shù)的取值不同，簇的數(shù)量隨著半徑的變化如圖6所示：大部分情況下，簇的個數(shù)與最小個數(shù)的大小成反比。由現(xiàn)實情況可知，一天中公交兩站點間行程時間，可根據(jù)普遍的工作時間與休息時間理論上至少可分為早高峰、上午平峰、午高峰、下午平峰、晚高峰、晚上平峰6種，即為6個簇，則當M=2或M=3時符合此現(xiàn)狀。但是簇的個數(shù)過多會造成聚類效果差，缺失數(shù)據(jù)補全時依據(jù)的歷史數(shù)據(jù)過少，使得修補效果差的情況，因此本文令M=3。

其次，在確定M=3后，當缺失數(shù)據(jù)站點與完整數(shù)據(jù)站點相距不同時，即為站點對不同時，簇的數(shù)量隨半徑的變化呈現(xiàn)不規(guī)則變化，如圖7所示：當M=3時，缺失數(shù)據(jù)站點與完整數(shù)據(jù)站點相距不同所對應的最大簇的數(shù)量是可接受的個數(shù)，大于理論最小值6且沒有過大造成聚類效果差。因此，本文選擇最大簇的個數(shù)作為行程時間聚類后的簇個數(shù)，但此時對應的半徑可能為多個值。由于最小個數(shù)、簇的數(shù)量一定的情況下，半徑越大、噪聲點的數(shù)量越少，可以利用的歷史數(shù)據(jù)量越多，因此本文選擇簇個數(shù)最大時的最大半徑作為缺失站點數(shù)據(jù)進行行程時間聚類時的半徑ε。基于上述分析，本文對于56班次第24～34個站點的到站數(shù)據(jù)分別進行修補時，得到聚類結果如表7所示。

最后，對于2018年某日廈門市全部線路的已識別上車站點數(shù)據(jù)，本文進行乘客開始刷卡與到站的時間間隔統(tǒng)計：乘客開始刷卡時刻與到站時刻間隔的均值為1.03s;有80.04%的時間間隔在1s及以內（如表8所示）。因此，本文選擇乘客開始刷卡與到站的時間間隔Tp=1.00s。

根據(jù)實驗參數(shù)的設置結果，本文方法與兩種對比方法的修補到站時刻如圖8所示、檢驗結果如表9所示，并且不同方法修補到站時刻相對誤差如圖9所示（時刻皆已轉換成為一天00：00：00為參照以秒為單位的數(shù)值）。

3.4?結果分析

1）由表9可得，對于FCR指標代表的缺失到站名稱、經緯度修補，三種方法皆可以進行100%的正確修補。說明是否使用多源數(shù)據(jù)和聚類后的歷史相似班次數(shù)據(jù)進行推算，對于缺失到站名稱、經緯度修補的影響較小。

2）圖8可得，本文方法在三種方法中，大部分站點的修補到站時刻與真實到站時刻相距最近，且由表9可得本文方法平均相對誤差δave=0.113-5%是三種方法中最小、修補準確度最高的。同時發(fā)現(xiàn)，僅使用單一GPS數(shù)據(jù)源的基于DBSCAN和多源數(shù)據(jù)方法的平均相對誤差，遠大于另外兩種基于多源數(shù)據(jù)的方法，說明使用多源數(shù)據(jù)對于缺失到站時刻修補的準確度產生了有益的影響;并且與本文同樣使用多源數(shù)據(jù)，但基于全部歷史班次數(shù)據(jù)確定行程時間取值范圍的極大概率估計方法平均相對誤差比本文方法的大，說明使用聚類后的相似班次數(shù)據(jù)對于缺失到站時刻修補的準確度產生了有益的影響。

3）圖9可得，本文方法的相對誤差隨缺失站點個數(shù)的變化趨勢最平穩(wěn)，且由表9可得本文方法的R值最接近1，因此是三種方法中準確度受缺失站點個數(shù)變化的影響程度最低、普適性最高的。同時發(fā)現(xiàn)，極大概率估計方法R值最小，說明本文方法使用聚類后的相似班次數(shù)據(jù)進行推算，對于缺失到站時刻修補的普適性產生了有益的影響，并且得到是否使用多源數(shù)據(jù)對于缺失到站時刻修補的普適性影響較小的結論。

綜上，本文基于DBSCAN和多源數(shù)據(jù)的缺失公交到站數(shù)據(jù)修補方法，在缺失到站時刻修補的準確度和普適性方面均優(yōu)于基于GPS數(shù)據(jù)聚類的方法和極大概率估計方法。同時得到結論：多源數(shù)據(jù)對于缺失到站時刻修補的準確度產生了有益的影響、但對于普適性影響較小;使用歷史數(shù)據(jù)聚類后的相似班次數(shù)據(jù)進行推算，對于缺失到站時刻修補的準確度和普適性都產生了有益的影響。

4?結語

本文提出了一種基于DBSACN和多源數(shù)據(jù)的缺失到站數(shù)據(jù)修補方法，可對缺失的公交到站經緯度、到站時刻數(shù)據(jù)進行修補。實例及檢驗結果表明，本文方法使用了多源數(shù)據(jù)和聚類后的相似班次數(shù)據(jù)進行推算，比現(xiàn)有的基于GPS數(shù)據(jù)聚類的方法、基于極大概率估計方法，具有更好的修補準確度和普適性。

本方法的缺陷為無法對于整班次的到站時刻丟失數(shù)據(jù)進行修補，也無法對于缺失的到站時刻數(shù)據(jù)進行實時預測或修補，且DBSCAN聚類算法中有較多參數(shù)需要調整，與其他方法的時、空復雜度可在不同地區(qū)不同數(shù)據(jù)集上進行應用對比，如有條件還可將由乘客經驗得到的先驗知識加入考慮，未來可對這些情況進行深入研究。

參考文獻 （References）

[1]LIU Y， WENG X， WAN J， et al. Exploring data validity in transportation systems for smart cities[J]. IEEE Communications Magazine， 2017， 55（5）： 26-33.

[2]ZHANG H， ZHANG Y， LI Z， et al. Spatialtemporal traffic data analysis based on global data management using MAS[J]. IEEE Transactions on Intelligent Transportation Systems， 2004， 5（4）： 267-275.

[3]吳昊，唐振軍.加權殼近鄰填充數(shù)學模型[J].華南師范大學學報（自然科學版），2013，45（3）：45-48.（WU H， TANG Z J. Weighted shellneighbor imputation models[J]. Journal of South China Normal University （Natural Science Edition）， 2013， 45（3）： 45-48.）

[4]ZHOU Y， YAO L， CHEN Y， et al. Bus arrival time calculation model based on smart card data[J]. Transportation Research Part C： Emerging Technologies， 2017， 74： 81-96.

[5]CHEN J， SHAO J. Nearest neighbor imputation for survey data[J]. Journal of Official Statistics， 2000， 16（2）： 113-131.

[6]郝勝軒，宋宏，周曉鋒.基于近鄰噪聲處理的KNN缺失數(shù)據(jù)填補算法[J]. 計算機仿真，2014，31（7）：264-268. （HAO S X，SONG H，ZHOU X F. Predicting missing values with KNN based on the elimination of neighbor noise[J]. Computer Simulation，2014，31（7）：264-268.）

[7]陳奔.基于雙向遞歸神經網絡的軌跡數(shù)據(jù)修復[D].濟南：山東大學， 2018.（CHEN B. Trajectory data repair based on bidirectional recurrent neural network [D]. Jinan： Shandong University， 2018.）

[8]QU L， ZHANG Y， HU J， et al. A BPCA based missing value imputing method for traffic flow volume data[C]// Proceedings of the 2008 IEEE Intelligent Vehicles Symposium. Piscataway： IEEE， 2008： 985-990.

[9]趙霞，張勇，尹寶才，等.基于改進k*means 算法的不完整公交到站時間填充[J]. 北京工業(yè)大學學報， 2018， 44（1）： 135-143. （ZHAO X， ZHANG Y， YIN B C， et al. Imputation of incomplete bus arrival time based on the improvedk*means algorithm [J]. Journal of Beijing University of Technology， 2018， 44（1）： 135-143.）

[10]王妍，王鳳桐，王俊陸，等.基于泛化中心聚類的不完備數(shù)據(jù)集填補方法[J]. 小型微型計算機系統(tǒng)， 2017， 38（9） ：2017-2021. （WANG Y， WANG F T， WANG J L， et al. Missing data imputation approach based on generalized centroids clustering algorithm[J]. Journal of Chinese Computer Systems， 2017， 38（9） ：2017-2021.）

[11]冷泳林，陳志奎，張清辰，等.不完整大數(shù)據(jù)的分布式聚類填充算法[J].計算機工程， 2015， 41（5）：19-25. （LENG Y L， CHEN Z K， ZHANG Q C， et al. Distributed clustering and filling algorithm of incomplete big data[J]. Computer Engineering， 2015，41（5）：19-25.）

[12]趙亮，陳志奎，張清辰.基于分布式減法聚類的不完整數(shù)據(jù)填充算法[J].小型微型計算機系統(tǒng)， 2015， 36（7）：1409-1414. （ZHAO L， CHEN Z K， ZHANG Q C. Incomplete data imputation algorithm based on distributed subtractive clustering[J]. Journal of Chinese Computer Systems， 2015， 36（7）：1409-1414.）

[13]韓飛，沈鎮(zhèn)林.基于不完備集雙聚類的缺失數(shù)據(jù)填補算法[J].計算機工程， 2016， 42（4）： 20-26. （HAN F， SHEN Z L. Missing data filling algorithm based on incomplete set biclustering[J]. Computer Engineering， 2016， 42（4）： 20-26.）

[14]劉思謙，陳志奎，蔣昆佑，等.一種混雜的多核估計數(shù)據(jù)填充方法[J].小型微型計算機系統(tǒng)， 2017， 38（7）：1523-1527. （LIU S Q， CHEN Z K，JIANG K Y， et al. Hybrid multikernels estimation method for data imputation[J]. Journal of Chinese Computer Systems， 2017， 38（7）：1523-1527.）

[15]VIGGIANO C， KOUTSOPOULOS H N， WILSON N H M， et al. Journeybased characterization of multimodal public transportation networks[J]. Public Transport， 2017， 9（1/2）： 437-461.

[16]LI M， DU B， HUANG J， et al. Public transport smart card data analysis and passenger flow distribution[EB/OL].[2019-05-20].https：//ascelibrary.org/doi/abs/10.1061/9780784412442.170。.

[17]BARRY J J， FREIMER R， SLAVIN H L. Use of entryonly automatic fare collection data to estimate linked transit trips in New York city[J]. Transportation Research Record Journal of the Transportation Research Board， 2009， 2112：53-61.

[18]劉永鑫.基于多源數(shù)據(jù)融合的城市公交系統(tǒng)乘客出行模式挖掘及其應用研究[D].廣州： 華南理工大學，2018.（LIU Y X. Study on key technologies of transit passengers travel pattern mining and applications based on multiple sources of data[D]. Guangzhou： South China University of Technology，2018.）

[19]潘冬明，黃德才.基于相對密度的不確定數(shù)據(jù)聚類算法[J].計算機科學，2015，42（11A）： 72-88. （PAN D M， HUANG D C. Relative densitybased clustering algorithm over uncertain data[J]. Computer Science，2015，42（11A）： 72-88.）

[20]張建民，姚亮，胡學鋼.一種面向數(shù)據(jù)缺失問題的Kmeans 改進算法[J].合肥工業(yè)大學學報（自然科學版）， 2008， 31（9）： 1455-1457. （ZHAN J M， YAO L， HU X G. An improvedKmeans algorithm for the datamissing problem[J]. Journal of Hefei University of Technology （Natural Science）， 2008， 31（9）： 1455-1457.）

[21]應臻奕.基于AP聚類的不完備數(shù)據(jù)處理方法的研究與實現(xiàn)[D]. 北京：北京郵電大學，2018.（YING Z Y. Research and implementation of incomplete data processing based on AP clustering[D]. Beijing： Beijing University of Posts and Telecommunications，2018.）

This work is partially supported by the National Natural Science Foundation of China Youth Fund （51608209）， the Project of Natural Science Foundation of Fujian Province （2017J01090）， the Project of Guiding Plan of Fujian Province （2019H0017）， the Project of Quanzhou Science and Technology Plan （2018Z008）， the Project of Postgraduate Research Innovation Ability Cultivation of Huaqiao University （17013083017）.

WANG Cheng， born in 1984， Ph. D.， associate professor. His research interests include traffic big data， data mining， machine learning.

CUI Ziwei， born in 1995， M. S. candidate. Her research interests include traffic big data， data mining.

DU Zilin， born in 1997. His research interests include traffic big data， data mining.

GAO Yueer， born in 1983， Ph. D.， associate professor. Her research interests include traffic big data， data mining.