張 永，朱建生，馮 梅，呂曉艷，賈新茹，王煒煒

ZHANG Yong，ZHU Jian-sheng，F(xiàn)ENG Mei，LYU Xiao-yan，JIA Xin-ru，WANG Wei-wei

（1.中國鐵道科學(xué)研究院 研究生部，北京 100081；2.中國鐵道科學(xué)研究院 電子計(jì)算技術(shù)研究所，北京 100081；3.中國民用航空華北地區(qū)空中交通管理局 通信網(wǎng)絡(luò)中心，北京 100710）

(1.Postgraduate Department，China Academy of Railway Sciences，Beijing 100081，China； 2.Institute of Computing Technology，China Academy of Railway Sciences，Beijing 100081，China； 3.Center for Communication Networks，CAAC North China Regional Administration，Beijing 100710，China)

鐵路旅客列車客座率的目標(biāo)通常是根據(jù)現(xiàn)有列車運(yùn)行信息下達(dá)的，傳統(tǒng)的做法是將這些列車信息輸入到電子表格中，利用人工進(jìn)行列車信息的處理、分類和客座率的預(yù)估，形成一張決策表。在實(shí)際工作中，這樣的做法存在誤差較大、決策信息不一致等問題。在既有的客座率或客運(yùn)量的預(yù)測研究中，主要利用 BP 神經(jīng)網(wǎng)絡(luò)、多元非參數(shù)回歸模型、時(shí)空序列和灰色線性回歸算法，根據(jù)歷史客座率或客運(yùn)量作為訓(xùn)練集進(jìn)行預(yù)測，并沒有根據(jù)列車屬性挖掘出目標(biāo)變量的生成規(guī)則[1-3]?；谏鲜鰡栴}，提出一種基于隨機(jī)森林算法的旅客列車客座率分類及預(yù)測模型，并以 2013 年和2014 年全路開行的 5 種類型的列車 (非臨客) 數(shù)據(jù)作為訓(xùn)練集，2015 年新開行的列車 (非臨客) 開行前一個(gè)月的數(shù)據(jù)作為測試集，對新運(yùn)行圖列車進(jìn)行日均客座率的分類和預(yù)測。

1 旅客列車客座率分類及預(yù)測模型

1.1 數(shù)據(jù)預(yù)處理

首先，收集列車基礎(chǔ)信息，包括列車類型、始發(fā)時(shí)間、終到時(shí)間、停站個(gè)數(shù)、列車運(yùn)行里程、運(yùn)行時(shí)間、始發(fā)站等級(jí) (始發(fā)站日均發(fā)送人數(shù))、終到站等級(jí) (終到站日均發(fā)送人數(shù))，并將這 8 個(gè)因素作為輸入屬性。可以看出，除第 1 個(gè)屬性為離散型變量外，后 7 個(gè)變量和目標(biāo)變量客座率均為連續(xù)型變量。其次，根據(jù)隨機(jī)森林算法的要求，通過離散化算法將連續(xù)型變量轉(zhuǎn)化為離散型變量。數(shù)據(jù)離散化可以有效地克服數(shù)據(jù)中隱藏的缺陷，避免極端值影響分類結(jié)果。

1.1.1 目標(biāo)變量的離散化

離散化算法分為非監(jiān)督離散化算法和監(jiān)督離散化算法[4]。非監(jiān)督離散化算法，如等頻、K 個(gè)區(qū)間比例加權(quán)離散化算法 (WPKID)[5]和基于聚類的算法[6]等；監(jiān)督離散化算法，如 CACC 算法[7]、ChiMerge 算法[8]、Hellinger 算法[9]和基于信息熵的離散化算法[10]等。由于目標(biāo)變量為連續(xù)型變量，因而需要對目標(biāo)變量進(jìn)行非監(jiān)督的離散化。但是，上述非監(jiān)督離散化算法忽略了數(shù)據(jù)分布信息，區(qū)間邊界的確定不具有代表性。

為解決上述問題，提出一個(gè)解決目標(biāo)變量離散化的算法模型：譜聚類-CACC 模型。該算法首先對客座率利用譜聚類進(jìn)行非監(jiān)督的劃分，譜聚類是一種基于圖論劃分[11]的聚類算法，它將數(shù)據(jù)點(diǎn)和點(diǎn)間距離看做帶權(quán)無向圖，并根據(jù)定義的 K 值進(jìn)行子圖的分割。分割結(jié)束后，呈現(xiàn)出同簇內(nèi)部節(jié)點(diǎn)之間相互連接密集，不同簇的節(jié)點(diǎn)之間連接稀疏的特征。根據(jù)聚類之后的類標(biāo)號(hào)，利用 CACC 算法對目標(biāo)變量進(jìn)行監(jiān)督的離散化。目標(biāo)變量離散化結(jié)果和切分點(diǎn)如表 1 所示。

表1 目標(biāo)變量離散化結(jié)果及切分點(diǎn)Tab.1 Discretization of target variables and segmentation points

1.1.2 因素?cái)?shù)據(jù)離散化

在對目標(biāo)變量離散化結(jié)束之后，根據(jù)目標(biāo)變量離散化結(jié)果，對因素?cái)?shù)據(jù)進(jìn)行監(jiān)督離散化。CACC算法是一個(gè)自底向上的算法，充分考慮了數(shù)據(jù)的分布，在后續(xù)的決策樹算法中準(zhǔn)確率更高[4]。將連續(xù)型數(shù)據(jù)中相鄰元素的均值作為備選切分點(diǎn)，每次計(jì)算數(shù)據(jù)被切分后，通過公式 ⑴，計(jì)算各個(gè)區(qū)間中目標(biāo)變量分布的相關(guān)性。

式中：C 為 CACC 算法的類-屬性相關(guān)指數(shù)；y' 為目標(biāo)變量分類在屬性變量切分區(qū)間的分布；M 為樣本總數(shù)；S 為目標(biāo)分類個(gè)數(shù)；n 為切分區(qū)間的個(gè)數(shù)；qir為目標(biāo)變量第 i 類，切分區(qū)間 [dr-1，dr] 中的樣本數(shù)；Mi+為目標(biāo)變量 i 中的樣本數(shù)；M+r為切分區(qū)間 [dr-1，dr] 中的樣本數(shù)。

在該算法的每次迭代過程中，總是選取相關(guān)性最大的點(diǎn)作為切分點(diǎn)，剩下的備選點(diǎn)重復(fù)上述步驟，直到全局的相關(guān)性達(dá)到最大，則切分停止。

對于因素?cái)?shù)據(jù)，在進(jìn)行離散化之前，先將始發(fā)時(shí)間、終到時(shí)間和運(yùn)行時(shí)長 3 個(gè)與時(shí)間有關(guān)的屬性數(shù)據(jù)進(jìn)行取整，如始發(fā)時(shí)間是 8 ∶ 57，處理為9 ∶ 00，記為 9；再如列車運(yùn)行時(shí)長為 1 h 45 min，轉(zhuǎn)變?yōu)樾?shù) 1.75，四舍五入結(jié)果為 2 等。屬性變量離散化結(jié)果及切分點(diǎn)如表 2 所示。

1.2 分類結(jié)果中最優(yōu)客座率選取

由于業(yè)務(wù)的需求，不僅要按照列車不同的屬性將客座率進(jìn)行分類，還要找出在不同客座率分類目標(biāo)中能滿足一定誤差的客座率準(zhǔn)確取值。在訓(xùn)練集中，經(jīng)過目標(biāo)變量的離散化后，每個(gè)客座率分類對應(yīng)一個(gè)客座率集合，在這個(gè)集合中，要找出一個(gè)能使一個(gè)分類中在誤差范圍內(nèi)樣本數(shù)達(dá)到最大的最優(yōu)客座率取值。設(shè)計(jì)一個(gè)基于誤差區(qū)間交集和樣本密度的最優(yōu)客座率選取算法，其在給定的誤差范圍內(nèi)，計(jì)算每個(gè)類中每個(gè)值的誤差范圍，并對它們進(jìn)行交集運(yùn)算，統(tǒng)計(jì)其中的樣本數(shù)，最終得到數(shù)據(jù)密度最大的區(qū)間，計(jì)算得到最優(yōu)值。

表2 屬性變量離散化結(jié)果及切分點(diǎn)Tab.2 Discretization of factor variable and segmentation points

設(shè)在第 k 個(gè)客座率分類中，對應(yīng) N 個(gè)實(shí)際的客座率，存在按照樣本中客座率降序排列樣本數(shù)據(jù)集D = {( y0,k，m0,k，x0,k)，( y1,k，m1,k，x1,k)，…，( yj,k，mj,k，xj,k)，…，( yN,k，mN,k，xN,k)}。其中，yj,k為第k 個(gè)客座率分類中第 j 個(gè)客座率；mj,k為第 k 個(gè)客座率分類中第 j 個(gè)客座率所對應(yīng)的樣本個(gè)數(shù)；xj,k為第 k 個(gè)客座率分類中第 j 個(gè)客座率所對應(yīng)的一個(gè)客座率取值，使得其在誤差范圍 [b，a] 內(nèi)滿足集合Aj,k={xj,k| xj,k∈[b + yj,k，a + yj,k]}，其中 Aj,k為包含第 k 個(gè)客座率分類中第 j 個(gè)客座率所在誤差范圍內(nèi)的所有客座率取值，則在樣本數(shù)據(jù)集內(nèi)，存在集合A ={A0,k，A1,k，…，Aj,k，…，AN,k}包括樣本集中各個(gè)客座率分類中每個(gè)客座率實(shí)際值在規(guī)定誤差下所包含的客座率取值。如果在 A 中同一個(gè)客座率分類存在幾個(gè)集合的交集，則滿足交集部分的取值覆蓋了幾個(gè)集合所有的樣本數(shù)?；谡`差區(qū)間交集和樣本密度的最優(yōu)客座率選取算法步驟如下。

（1）初始化 j = 0，i = 0。

（2）第一重迭代開始，從集合{A0,k，A1,k，…，Aj,k，…，AN,k}中取 Aj,k，并初始化交集集合={Aj,k}，計(jì)數(shù)器 count = 0。

（3）i = j + 1；從原結(jié)合中截取子集合{Ai,k，Ai+1,k，…，AN,k}。

（4）第二重迭代開始，從子集合中取 Ai,k。

（5）如果 Ai,k與存在交集，則利用它們的交集更新，更新計(jì)數(shù)累加器 count = count + length ()，更新和保存計(jì)數(shù)器值最大的交集 max_。

（6）i = i + 1。

（7）第二重迭代結(jié)束，j = j + 1。

（8）所有迭代結(jié)束后，得到一個(gè)交集集合。如果初始化時(shí)每個(gè)客座率對應(yīng)的樣本數(shù)相同，且計(jì)數(shù)器最終得到的值也為這個(gè)樣本數(shù)，則表明在誤差范圍內(nèi)數(shù)據(jù)無交集，計(jì)數(shù)器沒有累加，最優(yōu)值為全部數(shù)據(jù)的均值；否則，利用交集所覆蓋的樣本數(shù)除以對應(yīng)區(qū)間的長度計(jì)算樣本密度，樣本密度最大的交集為最優(yōu)值存在的集合。

利用訓(xùn)練集計(jì)算出每個(gè)分類對應(yīng)的最優(yōu)值，當(dāng)利用測試集進(jìn)行驗(yàn)證時(shí)，使預(yù)測分類與這些最優(yōu)值相對應(yīng)，這樣不僅可以為決策者提供一個(gè)參考的分類 (離散化后為客座率取值范圍)，也為其提供了一個(gè)參考的客座率取值 (誤差范圍為 [-10%，10%])。分類結(jié)果中客座率最優(yōu)值計(jì)算結(jié)果如表 3 所示。

表3 分類結(jié)果中客座率最優(yōu)值計(jì)算結(jié)果Tab.3 Optimal occupancy rates among classi fi cation results

1.3 基于隨機(jī)森林算法的預(yù)測

隨機(jī)森林算法由 Breiman[12]于 2001 年提出。該算法主要是通過隨機(jī)重采樣技術(shù)-自助法(bootstrap) 進(jìn)行采樣和隨機(jī)子空間的思想進(jìn)行特征的選取，構(gòu)建多個(gè)互相沒有關(guān)聯(lián)的決策樹，通過投票得到最終分類結(jié)果。近年來，隨機(jī)森林算法在很多領(lǐng)域發(fā)揮了重要作用[13]，其優(yōu)點(diǎn)主要表現(xiàn)在：①由于在每次迭代之前引入隨機(jī)采樣，使得算法不容易陷入過擬合，并且具有很好的抗噪能力，同時(shí)，由于很好地解決了過擬合問題，在算法執(zhí)行之前和結(jié)束不用再進(jìn)行前或后的剪枝處理；②由于采取了隨機(jī)子空間的方法進(jìn)行特征選取，使得在進(jìn)入算法前不必再進(jìn)行特征選擇的預(yù)處理。隨機(jī)森林算法流程如下。

（1）當(dāng)訓(xùn)練集進(jìn)入算法之前，利用 bootstrap 方法進(jìn)行隨機(jī)采樣，對于大小為 N 的樣本，隨機(jī)地有放回地選取大小為 k (k << N) 的樣本，隨機(jī)選取多個(gè)這樣的樣本構(gòu)建多個(gè)決策樹。

（2）在全部的 M 個(gè)特征中，每一顆樹的每一個(gè)節(jié)點(diǎn)隨機(jī)抽取 m (m << M) 作為決策樹的決策屬性。

（3）利用決策樹 C4.5[14]算法對每顆決策樹進(jìn)行分類，使決策樹進(jìn)行最大限度的增長，不做任何剪枝操作。利用決策樹 C4.5 算法主要原因是，其利用信息增益率進(jìn)行節(jié)點(diǎn)的分裂，防止了選擇屬性時(shí)偏向選擇取值多的屬性的不足。

（4）將生成的多顆分類樹組成隨機(jī)森林，用隨機(jī)森林算法分類器對新的數(shù)據(jù)進(jìn)行判別與分類，分類結(jié)果按樹分類器的投票多少而定。分類器投票公式可表示為

式中：H (x) 為組合分類模型；hi(x) 為單個(gè)決策樹模型；Y 為目標(biāo)變量；I (·) 為示性函數(shù)，當(dāng)預(yù)測某個(gè)分類器預(yù)測結(jié)果超過總預(yù)測結(jié)果的百分之 50%，則保留該結(jié)果，否則拒絕預(yù)測。

2 實(shí)驗(yàn)結(jié)果及分析

2.1 分類精度評(píng)估

利用 Kappa 指數(shù)檢驗(yàn)分類的精度是否在可接受的范圍內(nèi)，Kappa 指數(shù)的計(jì)算公式可表示為

式中：Pii為對角線二者完全一致占樣本數(shù)的比值；Pi＋和 P＋i分別為第 i 個(gè)檢驗(yàn)數(shù)據(jù)點(diǎn)的合計(jì)數(shù)和列合計(jì)數(shù)占總樣本數(shù)的比值。

利用實(shí)際客座率分類和預(yù)測的客座率分類頻數(shù)建立一張二維表。不同列車類型的 Kappa 指數(shù)如表 4 所示。

表4 不同列車類型條件下的分類 Kappa 指數(shù)Tab.4 Kappa coef fi cients for different types of train

Landis 等[15]提出 Kappa 值在 0.21 至 0.40 之間被認(rèn)為是可接受的；在 0.40 至 0.60 之間被認(rèn)為是中等的；在 0.61 至 0.80 之間被認(rèn)為是精度較優(yōu)的；大于0.81 被認(rèn)為是完美的分類。根據(jù)表 4，可以看出對于不同類型列車的分類精度均在中等或中等以上的一致性范圍內(nèi)。

2.2 目標(biāo)變量離散化算法有效性驗(yàn)證

為了驗(yàn)證提出的基于譜聚類-CACC 的目標(biāo)變量離散化模型是否有效，保持模型中的其他模塊方法不變，只是將目標(biāo)變量離散化的方法替換成對比實(shí)驗(yàn)中的等頻，WPKID 和聚類算法這幾個(gè)主流的非監(jiān)督離散化方法。為了驗(yàn)證 CACC 能否改進(jìn)譜聚類算法的離散化精度，保持?jǐn)?shù)據(jù)中的分布信息，在對照的聚類離散化方法中選取譜聚類算法。目標(biāo)變量離散化算法預(yù)測結(jié)果如表 5 所示。

表5 目標(biāo)變量離散化算法預(yù)測結(jié)果Tab.5 Comparison of predicted results from discretization algorithm of target variables

從上述實(shí)驗(yàn)可以看出，譜聚類-CACC目標(biāo)變量離散化方法相比于其他方法能夠顯著提高預(yù)測的分類精度；譜聚類離散化算法自身較等頻和WPKID 算法有著更高的預(yù)測精度，經(jīng)過 CACC 的優(yōu)化，使模型具有更高的預(yù)測精度。

2.3 因素變量離散化有效性驗(yàn)證

將 CACC 算法與主流的監(jiān)督離散化算法ChiMerge、基于信息熵的離散化算法、基于 Hellinger的算法等相比較，來驗(yàn)證所選用方法的有效性。因素變量離散化算法預(yù)測結(jié)果如表 6 所示。

從表 6 的實(shí)驗(yàn)結(jié)果可以看出，CACC 算法較其他有監(jiān)督的離散化算法在分類精度上表現(xiàn)更優(yōu)。

2.4 分類算法有效性驗(yàn)證

為了驗(yàn)證論選取的隨機(jī)森林算法的是否合理，是否較其他分類算法能突出其優(yōu)點(diǎn)，將隨機(jī)森林算法的分類預(yù)測結(jié)果與支持向量機(jī) SVM 和決策樹C4.5 算法分類結(jié)果相比較。不同分類算法預(yù)測結(jié)果如表 7 所示。

從表 7 可以看出，相對于其他分類算法，隨機(jī)森林算法在分類預(yù)測方面有著較高的精度。特別是相對于決策樹 C4.5 算法，隨機(jī)森林算法的特征隨機(jī)選取過程和投票機(jī)制是一種改進(jìn)和優(yōu)化。

2.5 客座率預(yù)測精度

分類結(jié)束后，利用之前的基于誤差區(qū)間交集和樣本密度的算法對最優(yōu)客座率進(jìn)行選取，考慮不同類型的列車，在相對誤差范圍 [-10%，10%] 內(nèi)的開行列車數(shù)占總開行列車趟數(shù)的占比作為正確率。為了驗(yàn)證提出算法的有效性，提出的選取方法與選取對象所計(jì)算的正確率相比較，客座率預(yù)測結(jié)果如表 8 所示。

從表 8 可以看出，提出的選取客座率的方法能夠顯著地提高客座率的預(yù)測精度。同時(shí)，對于不同的列車類型，在誤差范圍內(nèi)的列車數(shù)占總開行列車數(shù)量的 2/3 以上，這也是符合業(yè)務(wù)需求的。

表7 不同分類算法預(yù)測結(jié)果Tab.7 Comparison of predicted results from different classi fi cation algorithms

表8 客座率預(yù)測結(jié)果對比Tab.8 Comparison of predicted passenger occupancy rates

3 結(jié)束語

旅客列車客座率分類及預(yù)測可以為清算部門下達(dá)新開行列車客座率目標(biāo)提供依據(jù)，同時(shí)可以為制定旅客列車開行方案提供支撐。新開行旅客列車客座率分類及預(yù)測模型的研究，能夠得到一張簡明、易于理解的決策表，直觀地為相關(guān)管理部門下達(dá)客運(yùn)指標(biāo)，比原有方法提高了工作效率和結(jié)果的準(zhǔn)確性。隨著我國高速鐵路的快速發(fā)展，應(yīng)進(jìn)一步收集更多的旅客出行信息進(jìn)行分析[16-17]，以便為鐵路旅客運(yùn)輸提供更為科學(xué)合理的決策依據(jù)，優(yōu)化列車開行方案，提升旅客運(yùn)輸效率及效益。

[1] 王 卓，王艷輝，賈利民，等. 改進(jìn)的 BP 神經(jīng)網(wǎng)絡(luò)在鐵路客運(yùn)量時(shí)間序列預(yù)測中的應(yīng)用[J]. 中國鐵道科學(xué)，2005，26(2)：127-131.WANG Zhuo，WANG Yan-hui，JIA Li-min，et al. The Application of Improved BP Neural Network in the Prediction of Railway Passenger Volume Time Serial[J]. China Railway Science，2005，26(2)：127-131.

[2] 徐廣巖. 高速鐵路動(dòng)車組列車客座率預(yù)測及盈虧分析[D].北京：北京交通大學(xué)，2016.

[3] 侯麗敏，馬國峰. 基于灰色線性回歸組合模型鐵路客運(yùn)量預(yù)測[J]. 計(jì)算機(jī)仿真，2011，28(7)：1-3.HOU Li-min，MA Guo-feng. Forecast of Railway Passenger Traffic based on a Grey Linear Regression Combined Model[J]. Computer Simulation，2011，28(7)：1-3.

[4] 張鈺莎，蔣盛益. 連續(xù)屬性離散化算法研究綜述[J]. 計(jì)算機(jī)應(yīng)用與軟件，2014，31(8)：6-8.ZHANG Yu-sha，JIANG Sheng-yi. Survey on Continuous Feature Discretization Algorithm[J]. Computer Applications and Software，2014，31(8)：6-8.

[5] YANG Y，WEBB G I. Weighted Proportional K-Interval Discretization for Naive-Bayes Classi fi ers[M]. Heidelberg：Springer，2003.

[6] GUPTA A，MEHROTRA K G，MOHAN C. A Clusteringbased Discretization for Supervised Learning[J]. Statistics &Probability Letters，2010，80(9)：816-824.

[7] CHENGJUNG T C I L，WEI P Y. A Discretization Algorithm based on Class-Attribute Contingency Coefficient[J].Information Sciences，2008，178(3)：714-731.

[8] SU C T，HSU J H. An Extended Chi2 Algorithm for Discretization of Real Value Attributes[J]. IEEE Transactions on Knowledge & Data Engineering，2005，17(3)：437-441.

[9] LEE C H. A Hellinger-based Discretization Method for Numeric Attributes in Classi fi cation Learning[J]. Knowledgebased Systems，2007，20(4)：419-425.

[10] 高建國，崔業(yè)勤. 基于信息熵理論的連續(xù)屬性離散化方法[J]. 微電子學(xué)與計(jì)算機(jī)，2011，28(7)：187-189.GAO Jian-guo，CUI Ye-qin. A New Discretization Method for Continuous Attributes based on Information Entropy[J].Micro Electronics & Computer，2011，28(7)：187-189.

[11] LUXBURG U V. A Tutorial on Spectral Clustering[J].Statistics and Computing，2007，17(4)：395-416.

[12] BERIMAN L. Random Forests[J]. Machine Learning，2001，45(1)：5-32.

[13] 方匡南，吳見彬，朱建平，等. 隨機(jī)森林方法研究綜述[J].統(tǒng)計(jì)與信息論壇，2011，26(3)：32-36.FANG Kuang-nan，WU Jian-bin，ZHU Jian-ping，et al. Survey on Random Forest Methods[J]. Statistics &Information Forum，2011，26(3)：32-36.

[14] QUINLAN J R. C4.5：Programs for Machine Learning[M].San Mateo：Morgan Kaufmann，1993.

[15] LANDIS J R，KOCH G G. The Measurement of Observer Agreement for Categorical Data[J]. Biometrics，1977，33(1)：159-174.

[16] 張 航，趙 鵬，喬 珂，等. 高速鐵路旅客出行時(shí)間選擇 Logit 模型與分析[J]. 鐵道運(yùn)輸與經(jīng)濟(jì)，2017， 39(1)：55-60.ZHANG Hang，ZHAO Peng，QIAO Ke，et al. Analysis on Logit Model of High-speed Railway Passengers` Travel Time Choice[J]. Railway Transport and Economy ，2017，39(1)：55-60.

[17] 潘玲巧. 基于集對分析的鐵路大客戶等級(jí)模糊綜合評(píng)價(jià)[J].鐵道貨運(yùn)，2017，35(5)：36-40.PAN Ling-qiao. Fuzzy Comprehensive Evaluation of Railway Major Client Level based on SPA[J]. Railway Freight Transport，2017，35(5)：36-40.