楊健兵

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

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

中圖分類號(hào)：TP301? ? ?文獻(xiàn)標(biāo)識(shí)碼：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ù)通過(guò)問卷調(diào)查獲得，這種調(diào)查方法原始、相對(duì)落后，耗費(fèi)大量的人力、物理和財(cái)力，并且最終獲得的數(shù)據(jù)也不精確，往往為最終決策帶來(lái)一定誤差。而伴隨著智能公共交通系統(tǒng)的發(fā)展和普及，公交IC卡收費(fèi)系統(tǒng)、GPS監(jiān)控系統(tǒng)、車輛監(jiān)控系統(tǒng)中積累了大量原始的公交數(shù)據(jù)，特別是公交IC卡收費(fèi)系統(tǒng)，里面保存在每位乘客的上車刷卡信息，這些海量的刷卡信息內(nèi)部蘊(yùn)含著真實(shí)、全面的公交客流信息[1，2]，如何利用數(shù)據(jù)挖掘技術(shù)從這些海量的公交IC卡數(shù)據(jù)中快速獲取真實(shí)全面的公交客流信息，也是研究的熱點(diǎn)問題。

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

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

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

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

由于公交車在行駛過(guò)程中依次?？抗桓鱾€(gè)站點(diǎn)，在?？康倪^(guò)程中乘客依次上車刷卡，又由于公交IC卡刷卡消費(fèi)數(shù)據(jù)所記錄乘客刷卡時(shí)間具有一定的次序性，早上車的乘客刷卡時(shí)間早于后上車的乘客，其上車的站點(diǎn)順序只有兩種狀況。

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

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

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

3? ?聚類算法（Clustering algorithm）

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

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

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

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

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

兩個(gè)樣本之間的歐式距離d（xi，xj）按照（1）式來(lái)計(jì)算。

3.3? ?Hadoop平臺(tái)下的改進(jìn)的k-means算法實(shí)現(xiàn)過(guò)程

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

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

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

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

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

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

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

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

4? ?實(shí)驗(yàn)結(jié)果（Experiment results）

4.1? ?實(shí)驗(yàn)環(huán)境

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

4.2? ?實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)數(shù)據(jù)來(lái)自南通公交2018年8月份南通公交某線路的刷卡數(shù)據(jù)，刷卡數(shù)據(jù)包括IC卡編號(hào)、IC卡類型、刷卡時(shí)間、線路編號(hào)等四個(gè)字段。

4.3? ?實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

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

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

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

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

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