K-means聚類算法在公交IC卡數據分析中的應用研究

楊健兵

摘? ?要：文章通過收集南通市區公交線路名稱和站點名稱，在不依賴GPS定位數據的基礎上，通過采用K-means聚類算法分析乘客上車時間序列來建立乘客上車站點的理論模型，并跟車記錄該線路每站點的實際上車乘客人數，進而驗證所提理論的可行性。

關鍵詞：公共交通;IC卡;K-means;聚類

1? ? 公交IC卡相關研究

在城市公共交通規劃和管理的過程中，公交客流量特別是每個站點上車人數是城市公交線網規劃和管理的基礎數據，它為公交線網優化、站點設置、運營調度提供最可靠的數據支持。傳統的公交客流調查大多數通過問卷調查獲得，這種調查方法相對原始、落后，耗費大量的人力、物力和財力，并且最終獲得的數據也不精確，往往為最終決策帶來一定誤差。而伴隨著智能公共交通系統的發展和普及，公交IC卡收費系統、GPS監控系統、車輛監控系統中積累了大量原始的公交數據，特別是公交IC卡收費系統保存了每位乘客的上車刷卡信息，這些海量的刷卡信息內部蘊含真實、全面的公交客流信息[1-2]，如何利用數據挖掘技術從這些海量的公交IC卡數據中快速獲取真實、全面的公交客流信息，特別是每個站點上車人數，從而發現隱含在其中的乘客乘車規律，也是研究的熱點問題。

最近幾年，國內外學者在公交IC卡數據分析中做了大量的研究工作。在國外，Jinhua結合AFC及AVC數據獲取上車站點，然而國外的城市公交系統與國內的相差很大。在國內，戴宵等[3]提出了對公交卡乘客的刷卡時間進行聚類分析來判斷乘客上車站點的方法，于勇等[4]結合公交運營調度時刻表所提供的車輛及其發車信息，推算各車次到達各站點的時間，提高了上車站點推算精度。周銳[5]提出了基于IC卡數據的公交站點客流推算方法。趙鵬[6]基于成都公交IC卡數據的乘客上下車站點推算方法進行研究。徐文遠等[7]基于公交IC卡數據的公交客流統計方法進行研究。以上的研究存在數據不完整、準確率偏低等問題，研究的正確性很難得到保證。

目前國內大部分城市乘客乘車采用刷卡收費辦法，乘客在坐車時刷卡，下車后不要刷卡，所以在IC數據庫中僅記錄乘客刷卡上車時間，沒有乘客下車時間。在缺乏GPS定位數據的前提下，利用數據挖掘中聚類算法對IC卡刷卡數據進行聚類，將聚類結果結合公交線路信息和站點信息來推算公交乘客的上車站點，實現IC卡數據有效合理利用。

2? ? 數據預處理

本文需要預處理的數據主要涉及公交IC卡刷卡數據、公交車輛基本信息數據和公交線路站點數據。公交IC卡刷卡數據包括運營公司、IC卡編號、刷卡時間、刷卡金額、卡類型、線路編號、IC卡設備編號、公交車輛編號等字段。在本文的研究過程中，選取IC卡編號、IC卡類型，刷卡時間、線路編號4個字段屬性。公交刷卡數據庫如表1所示。

由于公交車在行駛過程中依次停靠公交的各個站點，乘客刷卡上車，且公交IC卡刷卡消費數據所記錄乘客刷卡時間具有一定的次序性，即刷卡時間早的乘客早于刷卡時間晚的乘客上車，因此，乘客上車的站點順序只有兩種狀況。

（1）乘車站點相同：該站點所有的乘客刷卡時間相差不大，相鄰兩位乘客間的刷卡間隔非常短，大概在幾秒之間。該站點第一個上車乘客和最后一個上車乘客刷卡時間差也不是很大。

（2）乘車站點不同：前面的站點刷卡時間早于后面站點刷卡時間。在這種情況下，由于公交車從一個站點行駛到另外一個站點，所以相鄰兩個刷卡間隔比較長。

通過分析乘客刷卡記錄，可以看到公交乘客在相同站點乘車，刷卡時間間隔較短，乘客在不同站點乘車，其刷卡時間間隔較長，這樣可以通過乘客刷卡記錄用K-means方法進行聚類，使乘客的刷卡上車時間序列與公交線路的站點序列一一匹配，建立符合邏輯的乘客上車站點估計模型。

3? ? 相關工作

3.1? 數據挖掘

數據挖掘是知識發現中的一個步驟[8]。數據挖掘技術一般是指從海量的數據中通過一定的算法進行計算，在算法的幫助下發現隱藏于其中的、有規律信息的過程。數據挖掘技術和計算機科學技術密切相關，可以通過數據庫技術、統計技術、在線分析技術、機器學習、模式識別等諸多方法來實現上述目標。

3.2? 聚類算法和K-means聚類算法

聚類算法是一種非監督機器學習算法，其實質是將數據對象劃分成子集的過程。聚類分析的算法有多種，如劃分法、層次法、基于密度的方法、基于網格的方法、基于模型的方法[9]。K-means算法屬于劃分方法中的一種，采用距離作為相似性的評價指標，該算法認為簇是由距離靠近的對象組成的，因此，把得到緊湊且獨立的簇作為最終目標。

K-means算法把對象組織成多個互斥的組或簇，采用距離作為相似性的評價指標。假設數據集D包含n個歐式空間中的對象。聚類的目的是把D的對象分配到k個簇C1，…，Ck中，使得對于1≤i，j≤k，Ci∈D且Ci∩Cj=￠。聚類的劃分的目的使得簇內高相似性和簇間低相似性為目標。

設數據集集合D={x1，x2，…，xn}，xi={xi1，xi2，…，xir}，xj={xj1，xj2，…，xjr }，則樣本xi和xj之間的歐式距離為：

誤差函數平方和如下：

其中，k為聚類數目，ri是第i類樣本的個數，ni是i類樣本的平均值。

K-mean均值的算法復雜度為O（nkt），其中，n是對象總數，k是用戶指定的簇數，t為迭代次數。通常情況下，k<

K-means算法的優點是算法簡單，易于實現，而且收斂速度快，計算工作很快就能完成。

3.3? 乘客上車站點判斷

由于我國絕大多數城市公交乘車采用上車刷卡的形式，并且刷卡記錄只是記錄上車時刻，并無上車站點，所以可以通過K-means聚類算法對居民上車站點進行判斷，計算得出每個站點上車人數。在進行K-means聚類算法之前，先要對原始IC卡數據進行預處理，具體步驟如下。

（1）讀取數據庫中乘客刷卡數據，并將單個乘客刷卡記錄匹配到各線路。

（2）將乘客的刷卡記錄分線路車輛按照刷卡時間進行排序。

（3）讀取駕駛員刷卡時間，位于兩次駕駛員刷卡時間之間記錄就是該線路，該車次乘客刷卡記錄如表2所示，該記錄就是要用K-means聚類算法進行計算的記錄。

（4）由于表2乘客刷卡記錄表中刷卡時間是時間格式，為了便于聚類，需要把它轉換成文本格式，設時間格式為HH∶MM∶SS，時間字段值為3 600×HH+60×MM+SS，并且刪除其他字段表，轉換后的刷卡記錄如表3所示。

（5）聚類計算：根據南通18路公交線路營運情況，南通18路公交共有23個站點，假設除了終點沒有人刷卡以外，其他線路都有人上車刷卡，這樣使用K-means聚類時k的值為22。

根據給定的公式，K-means算法的具體實現過程如下。在初始化的過程中，在數據集中任意選擇k個對象，k的值為22，每個對象代表該簇的中心點，對其余的每個對象，根據其與各簇中心的距離，將該對象劃分到最近的簇。然后對于k個簇，重新計算其均值。更新后的均值作為該簇新的簇中心。迭代繼續，直到分配穩定，K-means聚類算法的串行計算流程如圖1所示。

4? ? 實驗結果

4.1? 實驗環境

在本實驗中，使用2臺服務器搭建hadoop集群，每臺機器CPU為Intel Xeon E5520×2，內存32 G。機器上安裝Centos7操作系統，搭建ambari大數據管理平臺，在ambari平臺下安裝mahout數據挖掘系統，來運行K-means數據挖掘算法。

4.2? 實驗結果

實驗數據選取南通18路公交2018年7月18日一次行駛過程的刷卡記錄，數據記錄共81條，通過匹配南通18路公交22個站點，經過分析后得出每個站點刷卡人數，具體如表4所示。

5? ? ?結語

本文針對南通公交缺乏GPS調度數據的情況，利用公交IC卡刷卡記錄，通過聚類算法來對刷卡記錄進行聚類，根據聚類的結果來推算每個站點刷卡人數，實驗表明，該算法可靠、有效，可以精確地匹配到每個站點上車人數。通過對數據的研究，可以合理地安排公交調度，極大地提高公交的運行效率。

[參考文獻]

[1]孫慈嘉，李嘉偉，凌興宏.基于云計算的公交OD矩陣構建方法[J].江蘇大學學報（自然科學版），2016（4）：456-461.

[2]陳鋒，劉劍鋒.基于IC卡數據的公交客流特征分析—以北京市為例[J].城市交通，2016（1）：51-58，64.

[3]BARRY J J，FREIMER R，SLAVIN H.Use of entry-only automatic fare collection data to estimate linked transit trips in New York City[J].Transportation Research Record，2009（6）：28-33.

[3]戴霄，陳學武，李文勇.公交IC卡信息處理的數據挖掘技術研究[J].交通與計算機，2006（24）：40-42.

[4]于勇，鄧天民，肖裕民.一種新的公交乘客上車站點確定方法[J].重慶交通大學學報，2009（1）：121-125.

[5]周銳.基于IC卡數據的公交站點客流推算方法[D].北京：北京交通大學，2012.

[6]趙鵬.基于成都公交IC卡數據的乘客上下車站點推算方法研究[D].成都：西南交通大學，2012.

[7]徐文遠，鄧春瑤，劉寶義.基于公交IC卡數據的公交客流統計方法[J].中國公路學報，2013（5）：158-163.

[8]JIAWEI H，MICHELINE K，JIANPEI.數據挖掘概念與技術[M].北京：機械工業出版社，2012.

[9]謝雪蓮，李蘭友.基于云計算的并行K-means聚類算法研究[J].計算機測量與控制，2014（5）：1510-1512.

Abstract：By collecting the name of the bus line and the name of the site of the city of Nantong， on the basis of not relying on the GPS location data， the K-means clustering algorithm is used to analyze the passenger traffic time sequence and establish the theoretical model of the passenger boarding station， and record the number of passengers on the bus in the actual station， and then verify the feasibility of the proposed theory.

Key words：public transport; IC card; K-means; clustering