汪永旗，王惠嬌

（1.杭州電子科技大學(xué) 自動(dòng)化學(xué)院，浙江 杭州310018；2.浙江旅游職業(yè)學(xué)院 旅行社管理系，浙江 杭州311231；3.浙江理工大學(xué) 機(jī)械與自動(dòng)控制學(xué)院，浙江 杭州310018）

在Web 2.0技術(shù)和移動(dòng)互聯(lián)網(wǎng)快速發(fā)展等因素的影響下，國(guó)內(nèi)大型旅游OTA 的業(yè)務(wù)量以前所未有的速度增長(zhǎng).在黃金周等旅游高峰期，每天的酒店預(yù)訂量可達(dá)到幾十萬(wàn)間.伴隨著旅游消費(fèi)產(chǎn)生了大量的過(guò)程采集、消費(fèi)點(diǎn)評(píng)和產(chǎn)品推薦等數(shù)據(jù)，這些數(shù)據(jù)以各種形式保存到中心服務(wù)器上，包括文本、圖片、聲音、視頻等.分階段地對(duì)這些旅游過(guò)程中產(chǎn)生的海量數(shù)據(jù)進(jìn)行挖掘和分析是對(duì)大型線(xiàn)上旅游企業(yè)提出的迫切挑戰(zhàn)［1－2］.目前，我國(guó)大型在線(xiàn)旅游企業(yè)數(shù)據(jù)挖掘的數(shù)據(jù)規(guī)模已達(dá)GB級(jí)甚至TB級(jí)，傳統(tǒng)的分析手段已難以滿(mǎn)足現(xiàn)實(shí)的需要，迫切需要一種針對(duì)旅游大數(shù)據(jù)的客戶(hù)細(xì)分方法，從而可以進(jìn)行有效的旅游客戶(hù)細(xì)分、旅游客戶(hù)維護(hù)和精準(zhǔn)營(yíng)銷(xiāo)等商業(yè)活動(dòng).本文在應(yīng)用中改進(jìn)了K－means算法，提出了基于MapReduce模型的分布式聚類(lèi)算法.

1 MapReduce和Hadoop

圖1 MapReduce處理過(guò)程Fig.1 Processing of MapReduce

MapReduce是Google在2004年的OSDI會(huì)議上提出的分布式并行編程模型，適用于分析處理海量數(shù)據(jù)集.MapReduce把并行計(jì)算過(guò)程抽象為兩個(gè)函數(shù)：映射（Map）和化簡(jiǎn)（Reduce）.MapReduce就是“任務(wù)分解”模型，它通過(guò)Map把任務(wù)分解，用Reduce把處理好的結(jié)果匯總起來(lái)，得到最終結(jié)果［3－4］.在大數(shù)據(jù)處理過(guò)程中，如果一個(gè)數(shù)據(jù)集可以分解成許多小的數(shù)據(jù)集，每個(gè)小的數(shù)據(jù)集都可以完全并行地進(jìn)行處理，那么這個(gè)任務(wù)就可以用MapReduce來(lái)處理.MapReduce的處理過(guò)程，如圖1所示.

Hadoop是Apache組織發(fā)布的基于MapReduce模型的分布式計(jì)算框架.該架構(gòu)可以在大量廉價(jià)硬件設(shè)備組成的集群上運(yùn)行應(yīng)用程序，為應(yīng)用程序提供一組穩(wěn)定可靠的接口，旨在構(gòu)建一個(gè)具有高可靠性和良好擴(kuò)展性的分布式系統(tǒng)［5］.隨著云計(jì)算的逐漸流行，這一項(xiàng)目被越來(lái)越多的企業(yè)所運(yùn)用.Hadoop的核心是HDFS，MapReduce和HBase［6］.

2 聚類(lèi)算法的MapReduce實(shí)現(xiàn)

K－means算法是最經(jīng)典的劃分聚類(lèi)算法，由于其諸多的優(yōu)點(diǎn)，被廣泛應(yīng)用于客戶(hù)細(xì)分等聚類(lèi)應(yīng)用中［7］.因?yàn)镵－means聚類(lèi)算法具有可分解和重組的特點(diǎn)，所以也適合于在分布式架構(gòu)下運(yùn)行.

2.1 K－means聚類(lèi)算法及改進(jìn)

設(shè)有n個(gè)對(duì)象，劃分成k類(lèi)，經(jīng)過(guò)t次迭代，則經(jīng)典K－means算法的時(shí)間復(fù)雜度為O（nkt）.從算法過(guò)程可以看出：算法在處理大數(shù)據(jù)集時(shí)是相對(duì)有效的，具有較好的擴(kuò)展性.計(jì)算耗時(shí)主要集中在兩個(gè)環(huán)節(jié)上：一是計(jì)算各對(duì)象到中心的距離；二是將對(duì)象歸類(lèi)到距離最近的中心點(diǎn)類(lèi)的過(guò)程.對(duì)于后者，如果能減少不必要的比較和計(jì)算，則可以有效地節(jié)省時(shí)間開(kāi)支.為此，可以借用三角形三邊關(guān)系定理的思想簡(jiǎn)化比較和計(jì)算過(guò)程.具體有如下3個(gè)改進(jìn)步驟.

步驟1給定含有n個(gè)對(duì)象的數(shù)據(jù)集X，cl為k個(gè)初始中心，l＝1，2，…，k.

步驟2計(jì)算每個(gè)聚類(lèi)中心的距離d（ci，cj），其中，i，j＝1，2，…，k.

步驟3計(jì)算對(duì)象xi與當(dāng)前所在類(lèi)中心的距離d（xi，cm）.考察新的聚類(lèi)中心cj，如果d（cm，cj）≥2d（xi，cm），說(shuō)明cj不是新的中心，可以不用計(jì)算d（xi，cj）；否則，計(jì)算d（xi，cj），并與d（xi，cm）比較.繼續(xù)步驟3，直到將xi歸屬到最近的聚類(lèi)中心.

該改進(jìn)算法時(shí)間復(fù)雜度為O（nβd）.其中：1≤β≤k是對(duì)象到中心點(diǎn)的計(jì)算次數(shù).最好的情況是計(jì)算1次，最壞情況下是計(jì)算k次，當(dāng)n較大時(shí)，效率提高是可觀的.

圖2 K－means算法的MapReduce流程Fig.2 Process in MapReduce of K－means algorithm

2.2 算法的MapReduce實(shí)現(xiàn)

用MapReduce處理的數(shù)據(jù)應(yīng)具備以下條件：大的數(shù)據(jù)集可以被分成一個(gè)個(gè)小數(shù)據(jù)集，而且這些小數(shù)據(jù)集可以獨(dú)立地被并行處理，不相互影響.在K－means算法中，計(jì)算各對(duì)象到中心點(diǎn)的距離是被獨(dú)立操作的，各對(duì)象之間沒(méi)有關(guān)聯(lián)［8］.所以，K－means算法非常適用于分布式并行計(jì)算.K－means算法的編程思路，如圖2所示.由圖2可知：在用MapReduce處理前，需將客戶(hù)數(shù)據(jù)以行形式存儲(chǔ)，使數(shù)據(jù)能夠分片，并且各分片間數(shù)據(jù)不相關(guān)，分片過(guò)程可由Hadoop完成，無(wú)需另外編程.2.2.1 Map函數(shù)設(shè)計(jì) Map函數(shù)從特定分塊中逐行讀取每條記錄，計(jì)算它與k個(gè)中心點(diǎn)的距離，并標(biāo)明它所屬的新中心類(lèi)別.Map函數(shù)的輸入為原始客戶(hù)數(shù)據(jù)文件和k個(gè)初始中心點(diǎn).原始客戶(hù)數(shù)據(jù)以〈key，value〉對(duì)表示，其中：key為記錄相對(duì)于文件起始點(diǎn)的偏移量；value為當(dāng)前記錄各維值組成的字符串.Map函數(shù)的偽碼［9］如下：

2.2.2 Combine函數(shù)設(shè)計(jì) Combine函數(shù)作用是對(duì)每個(gè)Map函數(shù)產(chǎn)生的結(jié)果進(jìn)行本地化預(yù)處理，從而在Reduce時(shí)，減少不必要的通信代價(jià)，以提高整個(gè)MapReduce的運(yùn)行性能.Reduce函數(shù)的作用是從所有Map函數(shù)的結(jié)果中統(tǒng)計(jì)和計(jì)算出各個(gè)聚類(lèi)的新中心.為了減少通信代價(jià)，可以預(yù)先對(duì)本地Map函數(shù)結(jié)果進(jìn)行計(jì)算，得出本地結(jié)果中各聚類(lèi)對(duì)象的個(gè)數(shù)及各維數(shù)值之和，作為Reduce函數(shù)的輸入［10－11］.Combine函數(shù)的偽碼如下

2.2.3 Reduce函數(shù)設(shè)計(jì) Reduce函數(shù)的輸入是combine函數(shù)的輸出，key是聚簇ID，value中包含該簇的對(duì)象數(shù)num 和這些對(duì)象的各維數(shù)據(jù)之和.Reduce函數(shù)累加同一key的各num 之和，并求各分量的均值，得到新的聚類(lèi)中心，輸出〈key，value〉對(duì)［12］.Reduce函數(shù)的偽碼為

在每次reduce之后，判斷偏差是否小于給定的閾值.如果小于則算法收斂；否則，把本輪reduce結(jié)果作為map的輸入進(jìn)行下一輪的迭代.

3 實(shí)驗(yàn)與分析

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

文中所用實(shí)驗(yàn)平臺(tái)是由11 臺(tái)計(jì)算機(jī)組成的千兆以太網(wǎng).其中：1 臺(tái)作為master；另外10 臺(tái)為slaves.各節(jié)點(diǎn)硬件配置：3.2GHz Intel雙核CPU；4GB內(nèi)存.軟件配置：JDK 1.6.0；Hadoop 0.21.0.

實(shí)驗(yàn)所用的數(shù)據(jù)是46維的人工數(shù)據(jù).為了測(cè)試算法的性能，實(shí)驗(yàn)中構(gòu)造了不同大小的數(shù)據(jù)集，包括1，2，4，8G.采用加速比（speedup）作為主要的算法評(píng)價(jià)指標(biāo).

3.2 集群加速比性能實(shí)驗(yàn)

加速比是衡量并行系統(tǒng)優(yōu)劣及穩(wěn)定性的重要指標(biāo)，是指在并行系統(tǒng)中，對(duì)于同一個(gè)任務(wù)，在單處理機(jī)上運(yùn)行時(shí)間與在并行系統(tǒng)上處理時(shí)間的比率.一方面，可以用加速比考察當(dāng)系統(tǒng)硬件資源增加時(shí)，對(duì)相同規(guī)模任務(wù)的處理能力；另一方面，考察處理任務(wù)與硬件資源同比近似增加時(shí)，并行系統(tǒng)處理能力.

4組大小成比例增長(zhǎng)的46維人工數(shù)據(jù)的記錄數(shù)和數(shù)據(jù)塊數(shù)，如表1所示.分別選擇了1，2，4，5，6個(gè)計(jì)算節(jié)點(diǎn)，考量在不斷增加計(jì)算節(jié)點(diǎn)（n）的情況下，算法的運(yùn)行時(shí)間（t），得到運(yùn)行時(shí)間走勢(shì)圖，如圖3所示.

由圖3可知：隨著計(jì)算節(jié)點(diǎn)的增加，每個(gè)任務(wù)的運(yùn)行時(shí)間都有顯著地減少，可見(jiàn)K－means算法在Hadoop上運(yùn)行具有較好的加速比，說(shuō)明了系統(tǒng)的可用性.另外，為了考察系統(tǒng)的擴(kuò)展性，針對(duì)a，b，c三組數(shù)據(jù)，實(shí)驗(yàn)分別選擇2，4，8個(gè)節(jié)點(diǎn)（n）進(jìn)行運(yùn)算，得到的運(yùn)行時(shí)間（t），如圖4所示.由圖4可知：當(dāng)數(shù)據(jù)規(guī)模呈正比增長(zhǎng)時(shí)，只要相應(yīng)地增加計(jì)算節(jié)點(diǎn)，即可保持系統(tǒng)的相同處理水平，體現(xiàn)了該MapReduce算法的可擴(kuò)展性.

表1 實(shí)驗(yàn)數(shù)據(jù)Tab.1 Experimental data

圖3 算法的運(yùn)行時(shí)間走勢(shì)Fig.3 Running time trend of the algorithm

圖4 節(jié)點(diǎn)數(shù)與數(shù)據(jù)同比增長(zhǎng)下算法的運(yùn)行時(shí)間Fig.4 Running time of the algorithm in same proportion of nodes and data scale

3.3 旅游大數(shù)據(jù)客戶(hù)細(xì)分實(shí)驗(yàn)及結(jié)果分析

實(shí)驗(yàn)數(shù)據(jù)來(lái)自國(guó)內(nèi)某大型在線(xiàn)旅游網(wǎng)站的查詢(xún)預(yù)訂、過(guò)程跟蹤和服務(wù)點(diǎn)評(píng)等數(shù)據(jù).為了客戶(hù)細(xì)分實(shí)驗(yàn)需要，提取了約5 200萬(wàn)條數(shù)據(jù)，涵蓋了超過(guò)120萬(wàn)的客戶(hù).

首先，基于在線(xiàn)旅游數(shù)據(jù)的特點(diǎn)，在傳統(tǒng)RFM 模 型 的 基 礎(chǔ) 上［13－14］，構(gòu) 建 了 多 指 標(biāo) 的RFM 細(xì)分模型，如表2所示.進(jìn)行因子分析和權(quán)重設(shè)置［15］，在對(duì)初始數(shù)據(jù)進(jìn)行歸一化處理后，交于Hadoop集群處理.經(jīng)過(guò)MapReduce算法處理后，得到16個(gè)客戶(hù)聚類(lèi)，其中的4 個(gè)聚類(lèi)在各因子上的得分和客戶(hù)數(shù)（N），如表3所示.

由表3可知：C2類(lèi)是1年來(lái)一直較活躍的用戶(hù)，其消費(fèi)額很大，頻率也很高，用戶(hù)較少，是公司應(yīng)該重點(diǎn)維護(hù)的企業(yè)級(jí)客戶(hù)；C5類(lèi)最近很活躍，但消費(fèi)額度不大，應(yīng)該是在公司點(diǎn)評(píng)返現(xiàn)推廣活動(dòng)（公司開(kāi)展的促銷(xiāo)活動(dòng)）下，開(kāi)拓的大量新進(jìn)客戶(hù)，這類(lèi)客戶(hù)的網(wǎng)上點(diǎn)評(píng)較活躍，應(yīng)屬于手機(jī)APP用戶(hù)，也是企業(yè)未來(lái)發(fā)展的基石；C8類(lèi)客戶(hù)曾經(jīng)較活躍，有較高的消費(fèi)，但最近消費(fèi)很低，很可能是在今年激烈行業(yè)競(jìng)爭(zhēng)下流失的客戶(hù)；數(shù)量較大的C11類(lèi)則屬于一般價(jià)值客戶(hù).以上結(jié)果較好地反映了一年來(lái)行業(yè)的背景和企業(yè)決策所產(chǎn)生的影響，即在線(xiàn)旅游市場(chǎng)競(jìng)爭(zhēng)加??；點(diǎn)評(píng)返現(xiàn)措施帶來(lái)較大業(yè)務(wù)增長(zhǎng)；移動(dòng)APP推廣不僅吸引了大量的新客戶(hù)，同時(shí)，在整個(gè)業(yè)務(wù)中的比重也有明顯提高.因此，分析結(jié)果對(duì)公司新的決策有較大的參考價(jià)值.

表2 多指標(biāo)的RFM 細(xì)分模型Tab.2 RFM model including multi index

表3 客戶(hù)聚類(lèi)Tab.3 Customer clustering

4 結(jié)束語(yǔ)

利用K－means算法中各對(duì)象到中心點(diǎn)的距離是獨(dú)立運(yùn)算的特點(diǎn)，運(yùn)用三邊關(guān)系定理的思想改進(jìn)了對(duì)象歸類(lèi)的過(guò)程，并給出了算法的MapReduce實(shí)現(xiàn)，通過(guò)加速比實(shí)驗(yàn)證明了該算法的可用性及可擴(kuò)展性.在旅游大數(shù)據(jù)客戶(hù)細(xì)分應(yīng)用中，構(gòu)建了多指標(biāo)的RFM 擴(kuò)展模型，經(jīng)過(guò)實(shí)驗(yàn)，得到了預(yù)期結(jié)果.文中這種實(shí)現(xiàn)方法不僅可以為大型線(xiàn)上旅游企業(yè)提供決策支持，同時(shí)也是旅游主管部門(mén)監(jiān)控、管理旅游市場(chǎng)的有效方法.今后將對(duì)旅游大數(shù)據(jù)挖掘中的信息安全和隱私保護(hù)問(wèn)題開(kāi)展研究.

［1］PINTO J.Analyzing Big Data is becoming a key competitive advantage［J］.Process and Control Engineering，2014，67（5）：4.

［2］孟小峰，慈祥.大數(shù)據(jù)管理：概念、技術(shù)與挑戰(zhàn)［J］.計(jì)算機(jī)研究與發(fā)展，2013，50（1）：146－165.

［3］劉鵬.實(shí)戰(zhàn)Hadoop：開(kāi)啟通向云計(jì)算的捷徑［M］.北京：電子工業(yè)出版社，2011：60－74.

［4］LAM C.Hadoop in action［M］.Greenwich：Manning Publications Co，2011：65－72.

［5］SRIRAMA S N，JAKOVITS P，VAINIKKO E.Adapting scientific computing problems to clouds using MapReduce［J］.Future Generations Computer Systems，2012，28（1）：184－192.

［6］WHITE T.Hadoop：The definitive guide［M］.Sebastopol：O′Reilly Media Inc，2012：1－39.

［7］HAN J，KAMBER M，PEI J.Data mining：Concepts and techniques［M］.Burlington：Morgan Kaufmann，2011：451－456.

［8］江小平，李成華，向文.K－means聚類(lèi)算法的MapReduce并行化實(shí)現(xiàn)［J］.華中科技大學(xué)學(xué)報(bào)：自然科學(xué)版，2011，39（1）：120－124.

［9］KHOUSSAINOVA N，BALAZINSKA M，SUCIU D.PerfXplain：Debugging MapReduce job performance［J］.PVLDB，2012，5（7）：598－609.

［10］DEAN J，GHEMAWAT S.MapReduce：Simplified data processing on large clusters［J］.Communications of the ACM，2008，51（1）：107－113.

［11］HUGHES，ARTHUR M.Strategic database marketing［M］.New York：McGraw－Hill Inc，2012：85－104.

［12］GUO Qi，LI Yan，LIU Tao.Correlation－based performance analysis for full－system MapReduce optimization［C］∥Proceedings of IEEE International Conference on Big Data.Washington D C：IEEE Computer Society，2013：753－761.

［13］CUADROS A J，DOMINGUEZ V E.Customer segmentation model based on value generation for marketing strategies formulation［J］.Estudios Gerenciales，2014，30（130）：25－30.

［14］KHOBZI H，AKHONDZADEH－NOUGHABI E.A new application of RFM clustering for guild segmentation to mine the pattern of using banks′e－payment services［J］.Journal of Global Marketing，2014，27（3）：178－190.

［15］KLAS H，BJIRN L，DAG E，et al.Customer segmentation based on buying and returning behaviour［J］.International Journal of Physical Distribution and Logistics Management，2013，42（10）：852－865.