旅游大數據的MapReduce客戶細分應用

汪永旗，王惠嬌

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

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

1 MapReduce和Hadoop

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

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

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

2 聚類算法的MapReduce實現

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

2.1 K－means聚類算法及改進

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

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

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

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

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

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

2.2 算法的MapReduce實現

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

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

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

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

3 實驗與分析

3.1 實驗環(huán)境

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

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

3.2 集群加速比性能實驗

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

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

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

表1 實驗數據Tab.1 Experimental data

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

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

3.3 旅游大數據客戶細分實驗及結果分析

實驗數據來自國內某大型在線旅游網站的查詢預訂、過程跟蹤和服務點評等數據.為了客戶細分實驗需要，提取了約5 200萬條數據，涵蓋了超過120萬的客戶.

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

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

表2 多指標的RFM 細分模型Tab.2 RFM model including multi index

表3 客戶聚類Tab.3 Customer clustering

4 結束語

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

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

［2］孟小峰，慈祥.大數據管理：概念、技術與挑戰(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并行化實現［J］.華中科技大學學報：自然科學版，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.