汪永旗，王惠嬌

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

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

1 MapReduce和Hadoop

圖1 MapReduce處理過程Fig.1 Processing of MapReduce

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

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

2 聚類算法的MapReduce實現(xiàn)

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

2.1 K－means聚類算法及改進

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

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

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

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

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

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

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

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

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

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

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

3 實驗與分析

3.1 實驗環(huán)境

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

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

3.2 集群加速比性能實驗

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

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

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

表1 實驗數(shù)據(jù)Tab.1 Experimental data

圖3 算法的運行時間走勢Fig.3 Running time trend of the algorithm

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

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

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

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

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

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

表3 客戶聚類Tab.3 Customer clustering

4 結(jié)束語

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

［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］.計算機研究與發(fā)展，2013，50（1）：146－165.

［3］劉鵬.實戰(zhàn)Hadoop：開啟通向云計算的捷徑［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聚類算法的MapReduce并行化實現(xiàn)［J］.華中科技大學(xué)學(xué)報：自然科學(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.