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

楊健兵

摘? ?要：通過收集南通市市區公交線路名稱和站點名稱，在不依賴GPS定位數據的基礎上，采用Canopy和K-means聚類算法分析乘客上車時間序列，從而建立乘客上車站點的理論模型，并在Hadoop平臺上用MapReduce框架實現算法的并行化。最后，以南通公交IC刷卡記錄為例，用Canopy算法和K-means算法對IC卡刷卡記錄進行分析。實驗表明，在Hadoop平臺，用Canopy和K-means算法分析公交IC卡數據運行穩定、可靠，具有很好的聚類效果。

關鍵詞：IC卡;Canopy;K-means;聚類

1? ? 國內外關于公交IC卡的研究

傳統的公交客流調查大多數通過問卷調查獲得，這種調查方法相對原始、落后，耗費大量的人力、物理和財力，并且最終獲得的數據也不精確，往往為最終決策帶來一定誤差。伴隨著智能公共交通系統的發展和普及，公交IC卡收費系統、全球定位系統（Global Positioning System，GPS）監控系統、車輛監控系統中積累了大量原始的公交數據，特別是公交IC卡收費系統，里面保存每位乘客的上車刷卡信息，這些海量的刷卡信息內部蘊含著真實、全面的公交客流信息[1-2]，如何利用數據挖掘技術從這些海量的公交IC卡數據中快速獲取真實、全面的公交客流信息，是研究的熱點問題。

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

本文針對公交IC卡中海量的刷卡數據，利用Canopy和K-means聚類算法，在底層分布式文件系統（Hadoop Distributed File System，HDFS）支持下利用MapReduce框架，先用Canopy聚類算法對公交IC卡數據進行預處理，根據得到的類別數再用K-mean算法對公交IC卡刷卡數據進行分析。

2? ? 數據預處理

本文需要處理的數據來源于于南通公交IC刷卡記錄，IC卡刷卡數據如表1所示。

公交在行駛的過程中停靠站點具有單一性，即從起點站依次經過各個站點最終達到終點站。同時，乘客的刷卡記錄具有次序性，即上車站點前的刷卡時間早于上車站點后的刷卡時間。如果乘客乘車站點相同，該站點乘客間刷卡時間相差不大，如果乘客乘車站點不同，則乘客刷卡時間相差很多。

所以可以得出結論：如果乘車站點相同，則乘客刷卡時間相差間隔不大;如果乘車站點不同，則刷卡時間間隔很多。這樣可以把刷卡間隔差距不大的進行聚類，使得相同乘車站點的刷卡記錄聚為一類，不同乘車站點的刷卡記錄為不同類。

3? ? 聚類算法

3.1? 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之間的歐式距離為： d（xi，xj）=（1）

誤差函數平方和如下：

Jc=（2）

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

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

K-means算法的優點是算法簡單，易于實現，而且收斂速度快，計算工作很快就能完成。但是K-means算法也存在著一些缺點，在聚類之前K-means算法需要提前制定k的值，在k值沒有確定的情況下，K-means算法無法運行。

3.2? Canopy算法

與傳統的聚類算法（K-means）不同，Canopy聚類最大的特點是不需要事先指定k值（即clustering的個數），因此，具有很大的實際應用價值。與其他聚類算法相比，Canopy聚類算法雖然精度較低，但在速度上有很大優勢，因此，可以使用Canopy聚類先對數據進行“粗”聚類，得到k值，以及大致的k個中心點，再使用K-means進行進一步“細”聚類。Canopy算法的具體步驟如下。

（1）原始數據集合list按照一定的規則進行排序（該規則是任意的，一旦確定就不再更改），初始距離閾值為T1和T2，且T1>T2（T1，T2的設置可以根據用戶的需要或者使用交叉驗證獲得）。

（2）在list中隨機挑選一個數據向量A，使用一個粗糙距離dist計算方式計算A與list中其他樣本數據向量之間的距離d。

（3）根據（2）中的距離d，把d小于T1的樣本數據向量劃分到一個Canopy中，同時，把d小于T2的樣本數據向量從候選中心向量名單（這里理解為list）中移除。

（4）重復步驟（2）和（3），直到候選中心名單為空，即list空，算法結束。

算法原理比較簡單，就是對數據進行不斷遍歷，T2

3.3? K-means和Canopy算法在Hadoop平臺下的實現過程

在Hadoop平臺中K-means算法和Canopy算法可以用MapReduce程序來實現。首先，用Canopy程序開發實現k類簇，這個k個類簇可以作為K-means算法初始化條件，最終使用K-means聚類實現最終的結果。Mapreduce的程序設計與實現如圖1所示。

3.4? 乘客上車站點判斷

由于我國絕大多數城市公交乘車采用上車刷卡的形式，并且刷卡記錄只是記錄上車時刻，并無上車站點信息，所以通過Canopy算法和K-means聚類算法對刷卡時間序列進行聚類分析后，可以得出這些刷卡記錄被分為k種不同的類簇，在同一類簇中，上車站點相同，不同的類簇上車地點不同。因此，下一階段要完成類和公交站點的匹配。在公交行駛過程中，有時候所有站點都有人刷卡上車，有時候有些站點沒有人刷卡上車，所以要實現類簇和站點匹配需要分兩種情況進行討論。

設站點總數為S，站點從始發站到終點站的序列依次為s={1，2，3，……，S}，第i個站點和第i+1個站點的長度記為d（i，i+1）。該線路的總長可以通過累加相鄰兩個站點的距離所得：D=

（1）第一種情況，所得聚類數=公交站點總數-1，即k=S-1。此情況表明每個站點都有人進行刷卡，所以可以根據刷卡時間的先后次序，將類簇中的刷卡時間與各個站點依次進行匹配即可。

（2）第二種情況，通過Canopy算法得到的聚類數數量小于公交站點總數-1，即k

由于公交車在行駛啟動時由駕駛員刷卡，所以聚類后第一類刷卡記錄所對應的站點是公交線路的第一個站點，所以可以從第二類開始進行估計。

當估計第二類的上車站點時，設可以匹配的站點序號為{2，3，4，…，S-1}，其中，沒有乘客上車的站點有S-1-k個，記為Δs1，即Δs1=S-1-k，因此，第二類的上車站點要從候選站點序列（2，2+1，2+2，……，2+Δs1）站點中選擇一個。

設公交車全程行駛距離是D，根據駕駛員兩次刷卡記錄（即始發站刷卡和終點站刷卡）可以計算出公交車全程運行時間T，這樣公交車平均速度V=D/T。

在估計第二類的上車站點時，設第一類與第二類之間的行駛距離Δd （l，2），Δd （l，2）=V×（Tk1-Tk2）， Tk1和Tk2為第一類和第二類刷卡時間的平均值。

以第一類上車站點與每一個候選站點間的固定距離d（k1，k1+i），再依次計算公交車行駛距離Δd（l，2）與每一個固定距離d（k1，k1+i）之間差的絕對值，絕對值最小的即為第二類的上車站點。

完成第二類上車站點的估計后，用同樣的方法來估計第三類的上車站點，以此類推，當無刷卡記錄站點減少為零時，表明剩余的待匹配站點都有乘客上車，則可以實現剩余站點刷卡記錄與余下公交站點一一匹配。

4? ? 實驗結果

4.1? 實驗環境

在本實驗中，使用2臺服務器搭建Hadoop平臺，每臺服務器采用intel至強處理器，內存大小為128 G，使用Centos7作為網絡操作系統，搭建ambari大數據管理平臺，包括一個master節點和一個slaver節點，來運行K-means和改進的K-means算法。

4.2? 實驗結果

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

5? ? 結語

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

[參考文獻]

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

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

[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.

Research of canopy and K-means clustering algorithm in data analysis of the bus IC card

Yang Jianbing

（Nantong College of Science and Technology， Nantong 226007， China）

Abstract：By collecting the names of bus routes and stations in Nantong city， this paper uses canopy and K-means clustering algorithm to analyze passenger boarding time series， and then establishes the theoretical model of passenger boarding point on the basis of not relying on GPS positioning data. Then the parallel algorithm is implemented in the framework of MapReduce on Hadoop platform. Finally， taking the IC card record of Nantong bus as an example， the paper uses canopy algorithm and K-means algorithm to analyze the IC card record. Experiments show that using canopy and K-means algorithm to analyze bus IC card data on Hadoop platform runs steadily and reliably， and has good clustering effect.

Key words：IC card; Canopy; K-means; clustering