基于智能刷卡數據的乘客上車站點估計研究

高萬晨，路世昌，李丹

(遼寧工程技術大學，工商管理學院，遼寧葫蘆島 125000)

0 引言

科技的進步與發展使自動數據收費系統成為可能，并在城市公交系統中得到廣泛運用，尤其是自動收費系統(Automatic Fare Collection,AFC)和自動車輛位置系統(Automatic Vehicle Location,AVL)。AFC 系統不僅可以實現收費的目的，還可以實時地收集到巨量的乘客刷卡交易數據。AVL系統可以實時記錄公交車輛的到離站時間、經緯度坐標、瞬時速度及方向角等內容。因此，公交企業試圖將收集到的海量數據應用于城市公共交通的線網規劃、運營、控制與管理等方面，以使公交系統達到最優狀態[1]。

但是，如何將海量數據轉化成公交企業想要獲得的直接可以應用的數據便成為研究者主要關注的內容。在過去的幾十年內，學者基于公交企業提供的數據將OD 估計和調度優化等內容開展了一系列研究。就OD估計而言，BARRY等[2]基于紐約市的智能刷卡數據，提出兩個假設算法，估計一票制公交系統的OD。馬曉磊等[3]將車輛分為已安裝GPS和未安裝GPS設備兩類，針對前者采用數據融合算法估計乘客上車站點，針對后者采用貝葉斯決策樹算法估計上車站點，并利用馬爾科夫鏈降低算法復雜度。陳君等[4]將自動收費系統數據與智能調度系統數據進行關聯，估計乘客的上車站點，并進行了準確度分析和算法實現。就車輛調度優化而言，TANG 等[5]基于自動收費系統和車輛位置系統數據，獲取與時間相關的變量，構建公交時刻表的多目標優化模型，優化現有公交時刻表。ZHANG等[6]基于智能刷卡數據，構建單條線路時刻表優化的非線性模型，采用無導數約束羅盤搜索算法求解模型。

但是，在上述研究中，公交OD 估計是最基礎且最重要的研究內容之一，因為，公交OD 估計是后續研究的主要數據輸入，所以，公交OD 估計的準確率直接關乎后續研究，因此，本文選取公交OD矩陣估計中的O估計(即上車站點估計)作為主要研究內容，D估計作為將來的研究工作。

AFC系統主要包含一票制與分段計費兩類，前者，乘客在上車時需要進行刷卡付費，下車無需再次付費。后者，乘客在上車和下車均需要完成刷卡付費。針對上車站點估計，國內外學者根據公交企業提供的原始數據類型和屬性字段內容的差異開展了一系列研究工作，主要分為上車時間和上車站點均已知，上車時間已知而上車位置未知及上車時間和上車位置均未知[1]。

就第一類而言，乘客的上車時間和站點均為已知，因此，不需要進行上車站點估計研究，但是，ALSGER 等[7]提出上車站點估計方法，運用真實的上車站點數據，驗證了估算方法的有效性。針對第二類，由于AFC 系統缺乏上車站點屬性字段的記錄，僅有上車時間字段，因此，柳伍生等[8]使用時間窗方法進行上車站點估計研究，并未對估計準確性進行度量。TANG等[9]采用多階段深度學習方法估計乘客的上車站點，確定總的上車需求，采用真實的總需求進行驗證。在此類別中，由于AFC 系統中缺少個體乘客真實的上車站點數據，因此，無法采用個體真實上車站點驗證不同算法估計每個乘客上車站點的準確性。最后一類也是最難估計的一類，因為，AFC 等系統既沒有提供上車時間也沒有提供上車站點數據，因此，CHENG等[10]根據城市公交系統的相關數據，采用概率模型估計乘客的上車站點。

針對不同算法估計乘客上車站點準確性而言，已有研究中，部分學者采用實際調查法進行驗證，但是該方法由于僅調查少部分樣本用于驗證，當總體數量達到一定量級時，無法真實反映總體的準確性。另一部分研究僅做了上車站點估計研究，并未對估計結果進行準確性度量。已有研究中，僅有少數學者采用乘客真實的上車站點進行驗證。由于大多數乘客出行具有一定的規律性，因此，可以把乘客多日出行的所有上車站點數據按照時間順序進行排序，形成一個上車站點序列。如果能夠采用合理的方法度量此上車站點序列的出行規律性，便可進一步確定某種算法估計乘客上車站點的準確性。在信息論中，熵率可以度量事件發生的平均不確定性，熵率越大，則不確定性越高。崔洪軍等[11]采用熵率度量人們出行時間序列的重復性，研究表明，出行事件序列的熵率越小，出行規律性越強，反之亦然。因此，本文采用熵率方法度量不同算法確定乘客上車站點的準確性，為確定乘客上車站點和后續研究提供參考。

本文的研究工作屬于第二類，即上車時間已知，而上車位置未知。已有研究中，少有學者采用多種算法進行對比分析，且少有采用熵率方法度量乘客上車站點的準確率。因此，本文首先采用兩階段算法、改進K近鄰算法和改進模糊C均值聚類算法估計乘客的上車站點。其次，就乘客上車站點的匹配率而言，將3種算法與傳統時間窗算法進行對比分析。最后，采用熵率方法度量3種算法估計乘客上車站點的準確率。

1 數據描述與預處理

本文所使用的公交原始數據來自于珠海市城市公交系統，數據由AFC 和AVL 兩個系統收集。在系統中截取2021年9月6日～10日的數據作為研究使用，獲取了公交線路、站點及車輛編號等靜態數據。

1.1 AFC數據

由于珠海市所有公交線路均為一票制，乘客每完成1 次有效刷卡，AFC 系統便會記錄1 條刷卡數據，如表1 所示，包括：乘客的上車刷卡時間、線路編號、車輛編號、卡號及交易類型等主要字段，但AFC 系統并未記錄乘客具體的上車站點信息。

表1 AFC數據示例Table 1 Example of AFC data

1.2 AVL數據

AVL系統通過將GPS設備裝于公交車上，用于公交車實時監控，便于調度人員了解公交車的實際運行狀況。目前，珠海市所有運營公交車均已安裝車載GPS設備，該系統可以實時地收集公交車運行數據，并按照固定的時間間隔將數據上傳至服務器，包括：公交車到站時間、公交車離站時間、經緯度坐標、速度及方向角等字段數據，如表2所示。

表2 AVL數據樣例Table 2 Example of AVL data

1.3 數據預處理

設備失效和人為錯誤是導致部分數據異常的主要原因，在數據產生、上傳及存儲等過程中均可能發生。設備失效包括：刷卡設備、GPS 設備及系統設備等問題。人為錯誤包括：乘客上車忘記刷卡和多次刷卡等。由于上述錯誤，可能會導致數據缺失、數據重復、數據錯誤及相同字段在不同系統之間的數據不一致等錯誤形式。如果對其不進行科學的數據清洗操作，將會影響最終的研究結果。因此，需要對AVL 和AFC 系統中獲取的原始數據進行預處理，具體如下。

(1)針對數據缺失情況，需要判斷缺失數據能否通過其他已有數據代替，如果不能，則需要進一步判斷能否運用插值、均值及經驗判斷等補全。如果上述方法均無法補全缺失數據，則需要刪除缺失數據。

(2)針對數據重復情況，根據實際情況進行刪除，數據重復常見于起始站或終點站。

(3)針對數據錯誤情況，常見的錯誤主要有公交到站時間大于離站時間、站點不屬于此線路、時間錯誤、僅有部分GPS 數據及僅有GPS 數據無IC卡數據，或僅有IC 卡數據無GPS 數據等。如果是靜態數據發生錯誤，則需要通過歷史數據進行更改；如果是動態數據發生錯誤，可以酌情進行刪除。

(4)針對相同字段在不同系統之間的數據不一致情況，首先，利用兩個系統中字段相同且數據格式一致的數據將兩個系統的數據進行關聯操作；然后，對相同字段存在差異的數據進行標準化處理，或者選取其中一列數據作為基準。

經過數據清洗后，可以采用合理的算法對AFC和AVL數據進行匹配操作，以科學合理地估計每天每條線路每輛車在運營時間內的乘客上車站點。

2 方法

傳統的時間窗算法作為識別乘客上車站點的一種基本方法，具有簡單明了和易于理解的特點。正常情況下，乘客上車后，需要進行刷卡操作，第j名乘客的刷卡時間為Tj(j=1,…,μ)，公交車到達第i站時間為Ti,A(i=1,…,m)，離站時間為Ti,L(i=1,…,m)，顯然，乘客的刷卡時間應該介于區間[Ti,A,Ti,L] 內。但是，在公交車的實際運營過程中，往往會出現因設備誤差或故障，高峰期間擁堵產生的車輛提前開門或乘客因車內擁擠產生的滯后刷卡，相鄰兩個公交站之間距離較近等問題，進一步導致了部分乘客的刷卡時間在公交車到站和離站時間窗之外，如圖1所示。

圖1 公交站點和乘客刷卡數據時空分布Fig.1 Spatial and temporal distribution of bus stops and passengers'swiping card time

由于部分乘客的刷卡時間置于車輛到站和離站時間窗之外，因此，部分學者引入了閾值[12]，改進公交車的到站和離站時間窗，以提高時間窗外刷卡數據的匹配率，但是該方法在高峰期間可能會遇到某一站點上車人數過多或某一站點上車人數過少的情況，進而可能因閾值過大導致調整后的時間窗與后續時間窗存在交集或因閾值較小導致調整后的時間窗與調整前的時間窗相差不大，因此，可能會影響匹配準確率。

改進的公交車到站和離站時間窗為

式中：θ為時間窗閾值。

綜上，無論時間窗算法是否有閾值，都會有一定比例的刷卡數據無法匹配，需要人工匹配。當樣本數據達到一定數量時，該方法的效率會降低。因此，本文設計兩階段算法、改進K 近鄰算法和改進模糊C均值聚類算法對城市公交1條線路上所有車輛的刷卡數據進行上車站點估計。由于熵率可以度量乘客出行的規律性，因此，為驗證3 種算法的準確率，采用了熵率方法。

2.1 兩階段算法

第1階段，算法采用可變閾值的時間窗方法初次匹配乘客刷卡數據和車輛到站離站時間；第2階段，算法對第1階段未匹配成功的乘客刷卡數據進行二次匹配，確定所有刷卡數據的上車站點。

2.1.1 第1階段算法

基于式(2)和式(3)，繼續進行優化研究?；诘趇站的離站時間Ti,L(i=1,…,m)與第(i+1) 站的到站時間T(i+1),A(i=1,…,m)，提出帶有可變閾值的時間窗方法，進一步提高乘客上車站點的匹配精度，具體算法如下。

Step 1 獲取所有公交運營線路集合L={L0,…,Ly,…,Lk}，k為線路總數，y為線路編號。

Step 2 選取某線路Ly，獲取線路Ly在運營時間內的車輛集合B={By0,…,Byz,…,Bys}，s為車輛總數，z為車輛編號。刷卡數據匹配上車站點集合P={P0,…,Px',…,Pt}，t為匹配上車站點總數，x'為匹配上車站點編號。

Step3 選取某車輛Byz，獲取車輛Byz的刷卡時間集合I={Iyz0,…,Iyzx',…,Iyzt}，車輛到站和離站時間集合T={Tyz0c,…,Tyzic,…,Tyzmc}，c={A,L}，L 為車輛離站，A 為車輛到站，站點集合S={Syz0,…,Syzi,…,Syzm} 。

Step 4 確定可變閾值ψ。

(1)根據式(1)，對某條線路全天的乘客刷卡數據進行第一次匹配，存在一定比例的刷卡數據匹配失敗。

(3)由于刷卡數據介于兩站之間，要么屬于前者，要么屬于后者。因此，選擇集合tB中小于30 s的數據組成新集合tB_new，tB_new的平均值為σB。它將用于確定車輛B在線路Ly全天的可變閾值ψB=

(4)重復Step 2和Step 3，直到確定線路Ly所有車輛的可變閾值ψ。

Step 5 對車輛Byz在運營時間內的所有刷卡時間數據I和車輛到站離站時間數據T進行匹配運算。

(1)當i=1時(始發站)

如果Iyzx'≤(Tyz,1L+Ψ0)，Ψ0為始發站的可變閾值，Ψ0=ψ(Tyz,2A-Tyz,1L)，則乘客Px'在第1 站(始發站)上車，即Px'=1。

否則，i=i+2，繼續進行匹配操作。

(2)當i ＞1時

Ψw和Ψq分別為中間站車輛到達和離開的可變閾值，Ψw=ψ(Tyzi,A-Tyz(i-1),L)，Ψq=ψ(Tyz(i+1),A-Tyzi,L)。

如果Syzi=Syz(i+1)，則需要做出如下判斷：

① 如果Iyzx'≤(Tyzi,L+Ψq)且Iyzx'≥(Tyzi,A-Ψw)，則乘客Px'在i站上車，即Px'=i。

②如果Iyzx'≥(Tyzi,A-Ψw)且Iyzx'＜(Tyzi,A-Ψw)，則乘客Px'上車站點匹配失敗，即Px'=Null。

③如果Iyzx'＞(Tyz(i+1),L+Ψq)，則i=i+2，繼續匹配。

④除上述3種情況外，i=i+1，繼續匹配。

否則：

①如果Iyzx'≤Tyzi,A，則Px'=i-1。

②否則，如果Iyzx'≤Tyz(i+1),A，則Px'=i+1；反之，i=i+1，繼續匹配。

(3)當i=m(終點站)時

如果Iyzx'≤Tyzm,A時，乘客Px'在第(m-1) 站上車，即Px'=m-1。

Step 6 如果集合B中仍有未匹配成功的刷卡數據，轉至Step 3；否則，執行Step 2，直到所有線路的刷卡數據全部完成上車站點匹配。

2.1.2 第2階段算法

經過第1階段算法后，由于存在部分刷卡時間Iyzx'無法準確匹配公交車到離站時間Tyzic，因此，需要進一步設計一種算法，處理匹配失敗的刷卡數據，實現每天所有運營公交線路的所有車輛的全部乘客的刷卡數據的完全匹配，具體如下。

Step 1 獲取所有公交運營線路集合L={L0,…,Ly,…,Lk} 。

Step 2 選取某一線路Ly，獲取線路Ly在運營時間內的所有刷卡數據I={Iyz0,…,Iyzx',…,Iyzt} 匹配上車站點的集合P={P0,…,Px',…,Pt}，并對其進行完全匹配運算，將完全匹配后的上車站點集合定義為Pb={Pb0,…,Pbx',…,Pbt} 。

Step 3 進行數據完全匹配運算。

(1) 如果Px'=Null，在集合P'={Px'-1,…,0} 中尋找第1個不為Null 的元素，并記錄此元素的位置d。同時，在集合P″={Px'+1,…,Pt} 中尋找第1個不為Null 的元素，并記錄此元素的位置e。如果(Iyzx'-Iyzd)＜(Iyze-Iyzx')，則Pbx'=Pd；否則，Pbx'=Pe。

(2)如果Px'!=Null，則無需再次進行完全匹配運算，即Pbx'=Px'。

Step 4 如果集合L中仍有未完成匹配運算的線路，轉至Step 2；否則，算法終止。

2.2 改進K近鄰算法

AFC系統中實時記錄乘客的刷卡數據，包括刷卡時間和IC卡號等主要字段。由于不同乘客在同一站點上車的刷卡時間具有一定的連續性，因此，可以采用最近鄰聚類算法識別乘客的上車站點。其中，數據集樣本為某條公交線路全天的刷卡數據，選擇曼哈頓距離作為距離計算的依據，聚類中心個數(K值)不超過公交站點總數S，因為，可能存在某站點無人刷卡的現象，且終點站乘客只下不上，具體運算步驟如下。

Step 1 算法初始化

刷卡數據I為線路Ly車輛Bz的上行或下行方向運行一次所產生的t條刷卡記錄，上車刷卡時間I={Iyz0,…,Iyzx',…,Iyzt} 。選取Iyz0為聚類中心K0的初始值，即Iyz0∈K0。

Step 2 計算分類閾值ψ

以相鄰公交站點之間的最小行駛時間為分類閾值，ψ=min{Tyzi,A-Tyz(i-1),L}，i=2,…,S。

Step 3 計算距離

采用曼哈頓距離計算相鄰兩次刷卡數據之間的距離。假設Iyz(i-1)∈Ki，如果Di(i-1)=|Iyzi-Iyz(i-1)|＞ψ，則Iyzi∈K(i+1)；反之，Iyzi∈Ki。

Step 4 迭代操作

執行Step 1，Step 2 和Step 3，直至所有線路所有車輛的所有刷卡數據全部完成歸類。

Step 5 站點匹配

首先，將第1 個刷卡數據Iyzx'與公交車到站離站時間數據T={Tyz0c,…,Tyzic,…,Tyzrc} 進行匹配操作。其次，如果Iyzx'與Iyz(x'+1)均屬于Ki類，則Iyz(x'+1)的匹配結果與Iyzx'相同；反之，Iyz(x'+1)與公交車到站離站時間數據進行匹配。直至所有線路所有車輛的所有刷卡數據全部完成站點匹配。

2.3 改進模糊C均值聚類算法

模糊C 均值聚類算法是應用比較廣泛且較成功的無監督機器學習的算法，通過優化目標函數得到每個樣本點對所有類中心的隸屬度，從而決定樣本點的類屬，達到自動對樣本數據進行分類的目的。已有研究中，鮮有學者采用模糊C均值聚類算法估計研究乘客上車站點。因此，本文采用該方法進行上車站點估計，并將計算結果與其他算法進行對比。由于乘客上車刷卡數據是一系列的時間點，因此，對傳統的模糊C均值聚類算法進行改變，針對兩點距離的計算，采用曼哈頓距離替代歐式距離。

模糊C均值聚類算法通過引入隸屬度矩陣，用于衡量當前樣本屬于某一類別的可能性大小，并不是完全絕對屬于哪一類。當前樣本可能屬于第1類，也可能屬于第2 類。假如樣本數據F=(f1,f2,…,fg,…,fG)被劃分為C=(c1,c2,cε,…,cρ)個類別，那么每個類別會有1 個類中心，即共C 個類中心，uεg為樣本fg屬于某一類別cε的隸屬度，U=(u1g,u2g,uεg,…,uρg)，數學模型為

利用拉格朗日乘數法對uεg和cε分別求偏導，即

具體運算步驟如下。

Step 1 算法初始化。根據式(6)初始化一個隸屬度矩陣U(a)，根據U(a)計算初始聚類中心C(a)，確定模糊因子ξ，最大迭代次數和迭代停止閾值τ。

Step 2 根據U(a)和C(a)計算并更新隸屬度矩陣U(a+1)，然后，根據U(a+1)計算并更新聚類中心C(a+1)。

Step 4 站點匹配。首先，將第1個刷卡數據fg與公交 車到站 離站時 間數據T={Tyz0c,…,Tyzic,…,Tyzmc} 進行匹配操作。其次，如果fg與f(g+1)均屬于cε類，則f(g+1)的匹配結果與fg相同；反之，f(g+1)與公交車到站離站時間數據進行匹配。直至所有線路所有車輛的所有刷卡數據全部完成站點匹配。

2.4 熵率法

上述3 種算法均可以估計乘客上車站點，但是，不同的算法表現出不同的準確性。因此，本文采用前文敘述的熵率方法進一步確定不同算法估計乘客上車站點的準確性。將每個乘客多天的所有出行的上車站點按照時間進行排序，形成一個上車站點序列X={X1,X2,X3,…,Xn-2,Xn-1,Xn}，稱之為上車鏈，因此，僅需要計算上車鏈的熵率。通過比較熵率大小，便可以確定不同算法估計乘客上車站點準確率關系。熵率方法的具體描述如下。

隨機向量或隨機變量X需要在有限集合E中取值，集合E是乘客可以選擇的上車站點，概率分布為P(x)=Pr{X=x},x∈E，X的熵[13]為

X={… ,X-1,X0,X1,X2,…} 是一個隨機過程，{Xn}是隨機變量的序列，對于一個連續的部分過程(可能是無限的)(Xρ,Xρ+1,…,Xη), -∞≤ρ≤η≤+∞，H=H(X)為X的熵率，即的熵隨n變化的漸近率，即

H(X1,X2,…,Xn)為隨機變量(X1,X2,…,Xn)的熵。對于平穩的隨機過程，熵率存在，為式(9)條件熵，即

本文假設乘客長期的公交出行是一個平穩的隨機過程X。隨機變量X表示乘客在某站點上車，用離散概率p(x) 表示。在實際中，上述公式中的聯合概率分布和往往難以計算，通常采用估算方法進行熵率計算，常用的熵率估算方法有Plug-in Estimator、Lempel-Ziv Estimators、Context-Tree Weighting 及Burrows-Wheeler Transform(BWT)等。

由于BWT 是目前最好的無損壓縮方法之一，且BWT能夠把有限的記憶序列轉化成分段平穩的無記憶序列，以此過程為基礎估算原始序列的熵率。因此，本文選用Burrows-Wheeler Transform方法估算熵率[14]，具體計算步驟如下。

圖2 BWT例子Fig.2 Example of BWT

Step 2 將新的序列分為r段，每段長度不必相同，但是分段長度相同是非常有效的。

Step 3 估計每段內的一階分布。本文用Nr(x)表示符號x在第r段中出現的次數，用表示符號x在第r段中的概率估計，用表示第r段的熵估計，即

Step 4 通過各段熵的均值求出隨機過程X，即乘客上車站點出行序列的熵率為

乘客N在3 d內乘坐線路A的出行序列如圖3所示。圖3(a)為上車鏈，可以看出該序列有2 個未知參數X1和X2。假設以下4 種情況，X1=2，X2=3；X1=2，X2=6；X1=5，X2=3 和X1=5，X2=6。通過計算4 條上車鏈的熵率，結果如圖3(b)～(e)所示?？梢园l現，乘客上車鏈1 比上車鏈2、上車鏈3和上車鏈4具有更低的熵率，因此，上車鏈1表現出更強的出行規律性。上述案例可以進一步說明，熵率可以測度人們出行的規律性，熵率越小，出行規律性越強，能夠反映不同算法估計乘客上車站點的準確率。

圖3 不同序列的熵率對比Fig.3 Comparison of entropy rates of different sequences

3 案例與結果分析

選取珠海市2021年9月6日～10日AFC和AVL系統中18 路公交車(6:30-21:15)的運營數據，統計該線路運營時間內所有乘客的上車站點，線路布局如圖4 所示。經過數據清洗后，刷卡數據共27028條。刷卡數據包括：普通卡、老人卡、學生卡、二維碼、殘疾人卡、員工卡及其他卡7 種類型。不同類型IC卡占比如圖5(a)所示，18路公交運營期間刷卡數據具有早晚高峰特征，每天客流變化不明顯，具有一定的規律性，如圖5(b)所示。

圖4 珠海市18路Fig.4 Line 18 in Zhuhai

圖5 18路公交不同類型IC卡占比及不同時間段的客流分布Fig.5 Proportion of different types of IC cards and passenger flow distribution in different time periods of No.18 bus

3.1 不同算法的匹配結果

采用傳統時間窗算法、兩階段算法、改進K近鄰算法及改進模糊C均值聚類算法對18路5 d的刷卡數據進行匹配計算，匹配結果如圖6所示，圖中，P0為傳統的時間窗算法，P1為第1階段算法，P1+2為兩階段算法，P3為改進K近鄰算法，P4為改進模糊C均值聚類算法；虛線為5 d內P0與P1的平均匹配率。

圖6 乘客上車站點的匹配率Fig.6 Matching rate of passengers'boarding stops

由圖6 可知，各種算法的匹配結果為P0＜P1＜P1+2=P3=P4。18 路刷卡數據匹配平均增長率為P1，比P0增長31.3%，P1+2、P3、P4較P0高36.3%，P1+2、P3、P4較P1增加了5.0%。發現P1+2、P3、P4這3種算法均可以實現所有刷卡數據的完全匹配。

3.2 熵率計算結果

雖然3 種算法均可以實現上車站點的完全匹配，但無法判斷各種算法的匹配準確率。因此，可以通過熵率進行判斷。本文采用熵率方法，結合3個維度的樣本數據，深入探討各種算法估計乘客上車站點的準確率。

(1)維度I

首先，根據IC 卡號，統計5 d 內的所有刷卡數據；其次，將統計后的刷卡總數按降序排序；然后，選擇累計刷卡次數大于5次的前10%的IC卡號；最后，基于篩選后的IC卡號，采用3種算法分別計算，獲取每個IC 卡號的上車鏈，并以此為基礎計算各上車鏈的熵率。3種算法對維度I數據的熵率計算結果分布如圖7所示，圖中，虛線表示平均熵率。

圖7 3種算法在維度I的熵率分布Fig.7 Entropy rate distribution of three algorithms in dimension I

由圖7 可知，3 種算法的平均熵率分別為H(1+2)＜H3＜H4。如前文所述，熵率越小，乘客出行的規律性越強。因此，從平均熵率來看，3種算法匹配乘客上車站點的準確率關系為P1+2＞P3＞P4。而P1+2和P3的平均熵率差異不大，匹配精度比較接近。

(2)維度II

首先，經過傳統算法P0計算后，在所有匹配失敗的刷卡數據中，選擇累計刷卡次數大于5次的IC卡號；然后，根據篩選后的IC卡號，采用3種算法獲取每個IC 卡號的上車鏈用于熵率計算。在維度II的數據中，3 種算法的熵率計算結果分布如圖8 所示，圖中，虛線表示平均熵率。

圖8 3種算法在維度II的熵率分布Fig.8 Entropy rate distribution of three algorithms in dimension II

由圖8 可知，維度II 的平均熵率結果與維度I相似，即H(1+2)＜H3＜H4，P1+2＞P3＞P4。

(3)維度III

首先，根據IC卡類型，對所有刷卡數據按照IC卡類型進行分類，選擇每種類型中5 d 內累計刷卡次數大于5次的IC卡號；然后，根據篩選后的IC卡號，采用3種算法獲取每種類型中每個IC卡號的上車鏈用于計算熵率。在維度III數據中，3種算法的熵率計算結果分布如圖9 所示，圖中，虛線表示平均熵率。

由圖9 可知，除員工卡外，其他類型IC 卡的平均熵率分布結果與維度I和維度II相同。對于員工卡而言，熵率結果為H(1+2)=H3＜H4。因此，從熵率的平均值來看，3 種算法匹配乘客上車站點的準確率關系為P1+2=P3＞P4。由于P1+2和P3的平均熵率相等，因此，匹配精度相同。

為進一步驗證上述某種算法更加適合于公交企業的實際應用，進行如下操作。首先，在數據庫中，選擇3個IC卡卡號，對應3名乘客；其次，采用3種算法統計3名乘客5 d的上車站點，形成9條上車鏈；最后，分別計算所有上車鏈的熵率，如圖10所示。

圖10 3名乘客上車鏈的熵率Fig.10 Entropy rate of three passengers'boarding chain

由圖10可知，就乘客1而言，3種算法對乘客1形成了相同的上車鏈，且熵率相同，因此，選取其中一種算法產生的上車鏈作為乘客1 的最終上車站點估計結果。就乘客2而言，P1+2和P3形成的上車鏈相同，與 P4不同，熵率計算結果為H(1+2)=H3＜H4，因此，選擇P1+2或P3產生的上車鏈作為乘客2的最終上車站點估計結果。就乘客3而言，P1+2形成的上車鏈與P3、P4不同，熵率計算結果為H(1+2)＜H3=H4，因此，選擇P1+2產生的上車鏈作為乘客3的最終上車站點估計結果。綜上，并非某種算法完全優于或劣于其他算法，前文敘述的結果是基于3 個維度樣本數據的平均熵率而言。因此，公交企業在實際應用的過程中，應該選擇3 種算法中的最小熵率作為乘客上車站點估計的最終結果。

4 結論

(1) 熵率方法不僅可以反映乘客出行的規律性，還可以確定不同算法估計乘客上車站點的準確率。是一種估計乘客上車站點準確率的新方法。熵率越小，乘客上車站點估計的準確率越高。

(2)通過對比不同算法獲取上車鏈的平均熵率發現，兩階段算法的準確率高于改進K 近鄰算法，改進K 近鄰算法的準確率高于改進模糊C 均值聚類算法。兩階段算法與改進K 近鄰算法的準確率差異不大。

(3)公交企業在沒有更好的方法可供選擇時，可以采用熵率方法確定乘客上車站點估計的準確率，在具體應用時，應選擇熵率最小的估計算法確定乘客的上車站點。

(4)在兩階段算法中，基于可變閾值設計了時間窗算法，克服了傳統時間窗算法的不足。同時，兩階段、改進K近鄰算法和改進模糊C 均值聚類這3種算法均可估計所有乘客的上車站點，與傳統時間窗算法相比，進一步提升了乘客上車站點估計的匹配率。