Canopy和K-means聚類算法在公交IC卡數(shù)據(jù)分析中的應(yīng)用研究

楊健兵

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

關(guān)鍵詞：IC卡;Canopy;K-means;聚類

1? ? 國內(nèi)外關(guān)于公交IC卡的研究

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

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

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

2? ? 數(shù)據(jù)預(yù)處理

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

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

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

3? ? 聚類算法

3.1? K-means算法

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

設(shè)數(shù)據(jù)集集合D={x1，x2，…，xn}，xi={xi1，xi2，…，xir}，xj={xj1，xj2，…，xjr}，則樣本xi和xj之間的歐式距離為： d（xi，xj）=（1）

誤差函數(shù)平方和如下：

Jc=（2）

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

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

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

3.2? Canopy算法

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

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

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

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

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

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

3.3? K-means和Canopy算法在Hadoop平臺下的實現(xiàn)過程

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

3.4? 乘客上車站點判斷

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

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

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

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

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

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

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

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

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

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

4? ? 實驗結(jié)果

4.1? 實驗環(huán)境

在本實驗中，使用2臺服務(wù)器搭建Hadoop平臺，每臺服務(wù)器采用intel至強處理器，內(nèi)存大小為128 G，使用Centos7作為網(wǎng)絡(luò)操作系統(tǒng)，搭建ambari大數(shù)據(jù)管理平臺，包括一個master節(jié)點和一個slaver節(jié)點，來運行K-means和改進的K-means算法。

4.2? 實驗結(jié)果

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

5? ? 結(jié)語

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

[參考文獻]

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

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

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

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

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

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

[7]徐文遠(yuǎn)，鄧春瑤，劉寶義.基于公交IC卡數(shù)據(jù)的公交客流統(tǒng)計方法[J].中國公路學(xué)報，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