楊健兵

摘? 要：針對傳統(tǒng)k-means算法中初始聚類中心隨機確定的問題，提出k-means改進(jìn)算法。首先，定義變量權(quán)值，權(quán)值的大小等于樣本密度乘以簇間距離除以簇內(nèi)樣本平均距離，通過最大權(quán)值來確定聚類中心，克服了隨機確定聚類中心的不穩(wěn)定性。然后在Hadoop平臺上用Map-Reduce框架下實現(xiàn)算法的并行化。最后以南通公交IC刷卡記錄為例，通過改進(jìn)的k-means聚類算法進(jìn)行IC卡刷卡記錄的分析。實驗表明，在Hadoop平臺下改進(jìn)k-means算法運行穩(wěn)定、可靠，具有很好的聚類效果。

關(guān)鍵詞：MapReduce;改進(jìn)k-means算法;k-means;聚類

中圖分類號：TP301? ? ?文獻(xiàn)標(biāo)識碼：A

Abstract：Aiming at the problem of random determination of initial clustering centers in traditional k-means algorithm，an improved k-means algorithm is proposed in this paper.First，the weight value of the variable is defined.The weight value is equal to the sample density multiplied by the distance between clusters and then divided by the average distance within the cluster.The clustering center is determined by the maximum weight，and the instability of the cluster center is determined randomly.Then the parallelization of the algorithm is implemented under the Map-Reduce framework on the Hadoop platform.Finally，taking the Nantong bus IC card record as an example，an improved k-means clustering algorithm is used to analyze the IC card record.Experiments show that the improved k-means algorithm is stable and reliable under the Hadoop platform，with a good clustering effect.

Keywords：MapReduce;improved k-means algorithm;k-means;clustering

1? ?引言（Introduction）

傳統(tǒng)的公交客流調(diào)查大多數(shù)通過問卷調(diào)查獲得，這種調(diào)查方法原始、相對落后，耗費大量的人力、物理和財力，并且最終獲得的數(shù)據(jù)也不精確，往往為最終決策帶來一定誤差。而伴隨著智能公共交通系統(tǒng)的發(fā)展和普及，公交IC卡收費系統(tǒng)、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é)合AFC及AVC數(shù)據(jù)獲取上車站點，然而國外的城市公交系統(tǒng)與國內(nèi)的相差很大。在國內(nèi)，戴宵等[3]提出了對公交卡乘客的刷卡時間進(jìn)行聚類分析判斷乘客上車站點的方法，于勇等[4]結(jié)合公交運營調(diào)度時刻表所提供的車輛及其發(fā)車信息，推算各車次到達(dá)各站點的時間，提高了上車站點推算精度。周銳[5]提出了基于IC卡數(shù)據(jù)的公交站點客流推算方法。趙鵬[6]基于成都公交IC卡數(shù)據(jù)的乘客上下車站點推算方法研究。徐文遠(yuǎn)[7]等基于公交IC卡數(shù)據(jù)的公交客流統(tǒng)計方法。以上的研究存在數(shù)據(jù)不完整、準(zhǔn)確率偏低等問題，所以研究的正確性很難得到保證。

本文針對公交IC卡中海量的刷卡數(shù)據(jù)，提出了基于hadoop平臺的改進(jìn)k-means算法，在底層HDFS文件系統(tǒng)的支持下，通過k-means算法對公交IC卡刷卡數(shù)據(jù)進(jìn)行分析。利用MapReduce算法進(jìn)行并行計算，通過MapReduce算法極大地聚類算法的效率，為公交公司制定合理的調(diào)度方案提供了重要的依據(jù)。

2? ?數(shù)據(jù)預(yù)處理（Data preprocessing）

本文需要進(jìn)行計算的數(shù)據(jù)是南通市公共交通IC卡刷卡數(shù)據(jù)。公交IC卡刷卡數(shù)據(jù)字段包括運營公司、IC卡編號、刷卡時間、刷卡金額、卡類型、線路編號、IC卡設(shè)備編號和公交車輛編號等字段。在本文的研究過程中，選取IC卡數(shù)據(jù)的IC卡編號、IC卡類型、刷卡時間、線路編號四個字段屬性。數(shù)據(jù)庫表的格式如表1所示。

由于公交車在行駛過程中依次停靠公交各個站點，在停靠的過程中乘客依次上車刷卡，又由于公交IC卡刷卡消費數(shù)據(jù)所記錄乘客刷卡時間具有一定的次序性，早上車的乘客刷卡時間早于后上車的乘客，其上車的站點順序只有兩種狀況。

①第一，乘車站點相同。在這種情況下，該站點所有的乘客刷卡時間相差不大，相鄰兩位乘客間的刷卡間隔非常短，大概在幾秒之間。該站點第一個上車乘客和該站點最有一個上車乘客刷卡時間差也不是很大，可以歸屬為同一類。

②第二，刷卡時間早的乘客上車時所在的站點位于刷卡時間晚的之前。在這種情況下，由于公交車從一個站點行駛到另外一個站點，所以相鄰兩個刷卡間隔比較長。

通過分析乘客刷卡記錄，我們可以得出結(jié)論，相同站點乘車乘客，刷卡時間間隔較短，乘客在不同站點乘車，其刷卡時間間隔較長，這樣可以通過對乘客刷卡記錄進(jìn)行聚類，使得相同站點的刷卡記錄歸于一類，不同站點的刷卡記錄不在一類。

3? ?聚類算法（Clustering algorithm）

3.1? ?聚類算法和k-means聚類算法

聚類算法[8]是一種非監(jiān)督機器學(xué)習(xí)算法，其實質(zhì)就是對數(shù)據(jù)對象劃分成子集的過程。聚類分析的算法有多種，可以分為劃分法、層次法、基于密度的方法、基于網(wǎng)格的方法、基于模型的方法。k-means算法是屬于劃分方法中的一種，采用距離作為相似性的評價指標(biāo)，該算法認(rèn)為簇是由距離靠近的對象組成的，因此把得到緊湊且獨立的簇作為最終目標(biāo)。

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)。

3.2? ?改進(jìn)的k-means算法

改進(jìn)的k-means算法在選取初始中心點的時候不采用隨機選擇的方式，而是通過計算數(shù)據(jù)集的密度來考慮初始中心點。與傳統(tǒng)k-means算法隨機選取聚類中心點的方法比，減少了選取數(shù)據(jù)中心點的隨機性和盲目性。步驟如下：

兩個樣本之間的歐式距離d（xi，xj）按照（1）式來計算。

3.3? ?Hadoop平臺下的改進(jìn)的k-means算法實現(xiàn)過程

在hadoop程序開發(fā)中最重要的就是MapReduce程序的實現(xiàn)，MapReduce程序的開發(fā)分為map程序開發(fā)和reduce程序開發(fā)兩個過程。MapReduce的程序設(shè)計與實現(xiàn)如圖1所示。

首先，將公交IC卡刷卡數(shù)據(jù)存儲在Hadoop分布式文件系統(tǒng)中，然后通過MapReduce并行處理模型計算出K-means算法的輸入?yún)?shù)，輸入?yún)?shù)是初始聚類中心和k值，然后將計算任務(wù)再分配給Map任務(wù)節(jié)點，完成數(shù)據(jù)的并行聚類計算。具體步驟如下。

①對存儲在HDFS中的IC卡刷卡數(shù)據(jù)進(jìn)行初始化操作，產(chǎn)生鍵值對。

②Map任務(wù)節(jié)點計算數(shù)據(jù)塊中樣本密度，并根據(jù)式（1）—式（7），計算出最大權(quán)值w，并得到一些聚集，計算出每個聚類均值，并把該均值作為該簇的鍵值Key，Reduce算法根據(jù)鍵值key將具有相同Key值的簇集進(jìn)行數(shù)據(jù)合并。

③重新計算出每個簇集的均值，并把計算的結(jié)果設(shè)置為Value的值，同時對key進(jìn)行編號，key的號即為簇號。

④通過Map函數(shù)計算特征向量與k個初始聚類中心的歐氏距離，根據(jù)距離最小原則，找出其距離最小對應(yīng)簇的簇號，從而得到更新的鍵值對〈Key，Value1〉。

⑤Reduce函數(shù)將每個分區(qū)中具有相同Key值的信息進(jìn)行最后的合并。

⑥重復(fù)步驟④和步驟⑤，直到最終聚類結(jié)果的誤差平方和達(dá)到穩(wěn)定狀態(tài)，并輸出最終k個簇的相應(yīng)信息。

4? ?實驗結(jié)果（Experiment results）

4.1? ?實驗環(huán)境

在本實驗中，使用兩臺服務(wù)器搭建hadoop集群，每臺機器CPU為Intel Xeon處理器，內(nèi)存128GB。操作系統(tǒng)采用Centos7，搭建ambari大數(shù)據(jù)管理平臺，包括一個master節(jié)點和一個slaver節(jié)點，來運行k-means和改進(jìn)的k-means算法。

4.2? ?實驗數(shù)據(jù)

實驗數(shù)據(jù)來自南通公交2018年8月份南通公交某線路的刷卡數(shù)據(jù)，刷卡數(shù)據(jù)包括IC卡編號、IC卡類型、刷卡時間、線路編號等四個字段。

4.3? ?實驗結(jié)果

本實驗使用精度作為評價聚類性能的評價標(biāo)準(zhǔn)。通過對公交IC卡使用傳統(tǒng)的k-means方法和改進(jìn)的k-means方法進(jìn)行分析，并計算其精確度，為了更好評價聚類性能，本實驗共進(jìn)行聚類五次。具體的分析如表2所示。

5? ?結(jié)論（Conclusion）

本文以海量公交IC刷卡數(shù)據(jù)為基礎(chǔ)，提出了一種在hadoop平臺下改進(jìn)的k-means算法，針對傳統(tǒng)的k-means聚類算法中存在的問題，提出了采用一種采用密度參數(shù)的改進(jìn)方法，在選取聚類中心的時候，充分考慮樣本數(shù)據(jù)密度，同時定義了權(quán)值，權(quán)值的大小有樣本密度乘以簇間距離然后除以簇內(nèi)樣本距離而得，通過最大權(quán)值來確定聚類初始中心和k值，提高了聚類的準(zhǔn)確性和精確性。

參考文獻(xiàn)（References）

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

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

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

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

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

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

[7] 徐文遠(yuǎn)，鄧春瑤，劉寶義.基于公交IC卡數(shù)據(jù)的公交客流統(tǒng)計方法[J].中國公路學(xué)報，2013，26（5）：158-163.

[8] Jiawei Han，MichelineKamber，JianPei.數(shù)據(jù)挖掘概念與技術(shù)[M].北京：機械工業(yè)出版社，2012：4-5.