分布式聚類算法在航空客票代理人細(xì)分中的應(yīng)用

樊 瑋，張 偉

（中國民航大學(xué)計算機科學(xué)與技術(shù)學(xué)院，天津 300300）

2011年，麥肯錫全球研究報告《大數(shù)據(jù)：創(chuàng)新、競爭和生產(chǎn)力的下一個前沿領(lǐng)域》掀起了大數(shù)據(jù)熱潮。在民航領(lǐng)域，大數(shù)據(jù)還處于起步階段，有許多未知的應(yīng)用途徑需要進一步探索和發(fā)現(xiàn)。

對于整個民用航空市場，隨著客票代理服務(wù)范圍的擴大及其市場地位的提升，客票代理人已經(jīng)掌握了大部分客源[1]，是航空公司客票市場份額中最主要的來源和支撐，在客票銷售領(lǐng)域中擁有巨大的影響力。調(diào)查數(shù)據(jù)顯示，目前約75%的航空客票銷售訂單來自航空公司以外的銷售渠道，只有約25%是由各航空公司的官方訂票網(wǎng)站或APP 完成，其余都是通過各種在線銷售代理（如攜程等）完成的。客戶是航空公司發(fā)展與盈利的關(guān)鍵所在，在當(dāng)前以網(wǎng)絡(luò)銷售為主渠道的形勢下，各類銷售代理具有極高的市場價值。處理好航空公司與客票代理人的關(guān)系，可有效提高經(jīng)濟效益。

目前，大數(shù)據(jù)相關(guān)技術(shù)多應(yīng)用于旅客信息的挖掘與分析[2-3]以及航線航路的優(yōu)化設(shè)計[4]，對于航空客票代理人的數(shù)據(jù)挖掘較少。聚類分析是一種常用且重要的數(shù)據(jù)挖掘手段，而K-means 算法因其簡單高效被廣泛使用。同時，為應(yīng)對大數(shù)據(jù)時代數(shù)據(jù)量急劇增長的情況，如何將傳統(tǒng)聚類算法在其核心組件——MapReduce編程模式下實現(xiàn)，成為當(dāng)前研究的新熱點。Chu 等[5]對各類算法以MapReduce 編程模式在集群上做了運行測試，結(jié)果表明，具有統(tǒng)計查詢特征的算法均可以在分布式集群上實現(xiàn)，且算法的運行速度有了明顯提升。謝雪蓮等[6]、江小平等[7]給出了基于Hadoop 的分布式Kmeans 算法實現(xiàn)策略，結(jié)果表明MapReduce 編程模型下的分布式K-means 算法擁有更快的運行速度和更好的拓展性。賈瑞玉等[8]設(shè)計實現(xiàn)了分布式遺傳Kmeans 算法，結(jié)果表明處理大規(guī)模數(shù)據(jù)時該算法的執(zhí)行效率和聚類效果均有明顯提高。Yang 等[9]介紹了Cop-K-means，即一種改進K-means 算法在MapReduce 上的實現(xiàn)。

基于上述研究成果，為了更好地處理越來越龐大和復(fù)雜的數(shù)據(jù)，針對K-means 算法的缺陷，提出了分布式Canopy-K-means 聚類算法，以便能夠快速有效地分析航空客票代理人。該算法依靠Canopy 算法進行粗聚類，從而優(yōu)化傳統(tǒng)K-means 算法隨機選取聚類中心點和聚類個數(shù)、依靠主觀經(jīng)驗的缺點。通過分布式Canopy-K-means 算法對客票代理人進行準(zhǔn)確細(xì)致的刻畫，有效挖掘航空代理人數(shù)據(jù)，為航空公司制定代理人銷售計劃提供參考。

1 Canopy-K-means 算法

1.1 K-means 簡介及其不足

K-means 算法假設(shè)原始數(shù)據(jù)的集合為{x1，x2，…，xn}，且每個數(shù)據(jù)對象xi是一個d 維的向量。K-means 算法開始運行時，根據(jù)主觀經(jīng)驗人為確定聚類數(shù)量k，隨后從整個數(shù)據(jù)集中隨機選出k 個數(shù)據(jù)對象作為K-means聚類算法的初始聚類中心。然后，K-means 聚類算法遍歷整個數(shù)據(jù)集，計算每個數(shù)據(jù)對象與聚類中心的距離（如歐氏距離），將數(shù)據(jù)對象劃分給與其距離最近的聚類中心所屬的類中，遍歷結(jié)束后，根據(jù)各類中的數(shù)據(jù)對象重新計算類的中心，作為下一次迭代的聚類中心。反復(fù)迭代多次，直至迭代次數(shù)達到用戶設(shè)定次數(shù)或聚類中心的變化小于規(guī)定閾值（即聚類中心不再改變），算法結(jié)束。

K-means 聚類算法雖然十分簡潔且效率極高，但仍存在一些不足，主要體現(xiàn)為以下3 點。

1）聚類數(shù)量k 值的選取主要依靠人工確定，這要求用戶必須對數(shù)據(jù)集有充分的了解才能使選擇的k值符合數(shù)據(jù)集實際情況，而該條件在絕大多數(shù)實驗與應(yīng)用中無法滿足。

2）初始聚類中心通過隨機方法選取，使聚類算法在進行多次實驗時結(jié)果相差較大，不夠穩(wěn)定，且該選取策略極易使算法陷入局部最優(yōu)解。

3）該算法對孤立數(shù)據(jù)節(jié)點異常敏感，若孤立數(shù)據(jù)節(jié)點在K-means 算法應(yīng)用場景對最終結(jié)果分析無任何幫助，屬于噪音數(shù)據(jù)，將會對K-means 聚類算法的收斂速度產(chǎn)生極大影響。

1.2 Canopy 算法

與K-means 算法不同，Canopy 算法最大的特點是不需要事先指定k 值，因此可對K-means 算法進行有效優(yōu)化。與其他聚類算法相比，Canopy 聚類雖然精確度較低，但在速度上有很大優(yōu)勢，因此可以使用Canopy 算法先對數(shù)據(jù)進行“粗”聚類，得到k 值和初始聚類中心，然后再用K-means 進一步“細(xì)”聚類。Canopy 算法的思想及步驟如下。

1）確定兩個閾值t1和t2（要求t1＞t2）。

2）算法中有1 個Canopy 集合，從數(shù)據(jù)集合中隨機選出1 個數(shù)據(jù)，計算該數(shù)據(jù)到Canopy 集合中每個Canopy 的距離（集合初始為空，則將第1 個數(shù)據(jù)直接作為1 個Canopy）。

3）如果距離小于t1，則將該數(shù)據(jù)分配到該Canopy（1 個數(shù)據(jù)可以分配給多個Canopy）。

4）如果距離小于t2，則認(rèn)為該數(shù)據(jù)與該Canopy 的距離已足夠近，不可能成為新的Canopy，將其從數(shù)據(jù)集合中刪除。

5）如果大于t1，則作為新的Canopy 加入集合。

6）重復(fù)步驟2）～步驟5），直至數(shù)據(jù)集合中的數(shù)據(jù)全部被刪除。

Canopy 聚類結(jié)果如圖1所示，其中包含5 個Canopy 集合，實線大圓表示t1的范圍，虛線小圓表示t2的范圍。

圖1 Canopy 聚類示例圖Fig.1 Canopy clustering instance

1.3 分布式Canopy-K-means 算法

MapReduce 編程模型主要由map 和reduce 兩個部分組成，兩部分任務(wù)分配到各個節(jié)點后均并行執(zhí)行，節(jié)點執(zhí)行結(jié)果相互之間不產(chǎn)生影響。程序啟動后，數(shù)據(jù)被分片，然后分派到集群中各個執(zhí)行map 函數(shù)的節(jié)點，map 階段處理產(chǎn)生的中間結(jié)果經(jīng)過重新整合后，再分配到各個執(zhí)行reduce 函數(shù)的節(jié)點上。

結(jié)合Canopy 算法以及分布式MapReduce 程序處理流程，分布式Canopy-K-means 算法的設(shè)計如下：

1）通過Canopy 算法進行粗聚類，得到初始聚類中心和聚類數(shù)量k 值，將其作為輸入數(shù)據(jù)傳遞到分布式K-means 算法中，Canopy 算法的具體實現(xiàn)細(xì)節(jié)見1.2部分。

2）在map 階段每獲取到1 個數(shù)據(jù)對象，計算其與所有類別聚類中心之間的歐氏距離，將數(shù)據(jù)對象劃分到與其距離最近的聚類中心所代表的類中，然后將該類的標(biāo)簽作為key 值，將數(shù)據(jù)對象作為value 值，形成＜key，value＞鍵值對輸出。

3）在reduce 階段的輸入數(shù)據(jù)為＜key，list（value）＞，其中key 值是類標(biāo)簽，list（value）是同一類數(shù)據(jù)對象的集合列表，利用式（1）計算同一類中所有數(shù)據(jù)對象屬性值的均值，將其作為新的聚類中心并輸出，即

其中：data 為數(shù)據(jù)對象；Ci為第i 類聚類；data 的m 維屬性為（a1，a2，…，am），Ni為第i 類中數(shù)據(jù)對象的個數(shù)。

4）reduce 得到的新聚類中心與原聚類中心進行比較，判斷聚類算法是否已經(jīng)收斂。若新聚類中心與原聚類中心的差值不符合閾值要求，則清空原聚類中心的數(shù)據(jù)文件，將reduce 的輸出結(jié)果寫到中心文件中，作為下次迭代時的聚類中心，然后跳轉(zhuǎn)到第二步進行迭代；若差值符合閾值要求，則運行一個沒有reduce的任務(wù)將聚類結(jié)果輸出，并結(jié)束程序。

該算法是一個迭代算法，第4）步要使式（2）中的函數(shù)最小化，假設(shè)原始數(shù)據(jù)的集合為{x1，x2，…，xN}，xi為d 維向量，這N 個數(shù)據(jù)點需要分為k 個分類。

其中：rnk在數(shù)據(jù)點n 被歸類到分類k 時為1，否則為0；μk為第k 類聚類的中心；J 為目標(biāo)函數(shù)值。K-means 算法的目標(biāo)是使J 值最小，即聚類結(jié)果中數(shù)據(jù)點與其所屬類的聚類中心之間的距離最小。

算法的實現(xiàn)需要建立2 個Job：Job1用于執(zhí)行Canopy 算法，以實現(xiàn)粗聚類，然后將Job1產(chǎn)生的結(jié)果，即初始聚類中心傳遞到Job2中。Job2的主要任務(wù)就是執(zhí)行K-means 算法，通過多次迭代，使聚類中心的變化符合閾值要求或達到預(yù)定迭代次數(shù)，算法完成。分布式Canopy-K-means 聚類算法的流程如圖2所示。

圖2 Canopy-K-means 算法流程圖Fig.2 Flow chart of Canopy-K-means algorithm

2 數(shù)據(jù)屬性

采用國內(nèi)某航空公司單季度銷售記錄作為原始數(shù)據(jù)，處理后得到對7 000 多個代理人的銷售評價結(jié)果，數(shù)據(jù)各屬性含義如表1所示。

表1 數(shù)據(jù)屬性Tab.1 Data attributes

表1中，代理人的出度入度之和反映了代理人的活躍度；代理人日銷售額占市場銷售總額的比例及其占比的標(biāo)準(zhǔn)差反映了代理人的市場地位，并可用于推測代理人的銷售能力是否穩(wěn)定。由于代理人之間的銷售能力和綜合實力差異較大，使得代理人每日銷售額占比之間的差距十分懸殊，故采用異常系數(shù)來比較代理人之間的銷售能力穩(wěn)定性，異常系數(shù)計算方法為

其中：SD（x）為x 的標(biāo)準(zhǔn)差，mean（x）為x 的均值；代理人的平均售票價格及其標(biāo)準(zhǔn)差反映了代理人銷售機票的傾向：如果代理人的平均售票價格偏低，且方差較小，則該代理人可能主要銷售近程機票。代理人與代理人、乘客、航空公司之間的買賣交易占比反映了代理人的購票渠道偏好和銷售渠道偏好。

3 仿真研究

3.1 實驗環(huán)境

實驗使用包含5 個節(jié)點的Hadoop 集群，Hadoop版本為2.5.2，各節(jié)點的性能參數(shù)如表2所示。

表2 節(jié)點性能參數(shù)Tab.2 Node performance parameters

3.2 數(shù)據(jù)預(yù)處理

由于表1所示的代理人各評價指標(biāo)量綱和單位不同，數(shù)值相差較為懸殊，這將對分析結(jié)果造成影響。為消除指標(biāo)之間的量綱影響，需要對數(shù)據(jù)進行標(biāo)準(zhǔn)化處理，以解決數(shù)據(jù)指標(biāo)之間的可比性。采用0-1 標(biāo)準(zhǔn)化，根據(jù)指標(biāo)平均值和標(biāo)準(zhǔn)差來進行規(guī)范化，即

其中：μ 為該指標(biāo)的均值；σ 為該指標(biāo)的標(biāo)準(zhǔn)差，經(jīng)過處理的數(shù)據(jù)符合標(biāo)準(zhǔn)正態(tài)分布，即均值為0，方差為1。

3.3 實驗結(jié)果分析

經(jīng)過Canopy-K-means 聚類算法計算，最終將所有代理人聚集為6 類。這6 個聚類的聚類中心數(shù)據(jù)分析如圖3所示。由圖3可推測各類代理人的特征，從而說明分布式Canopy-K-means 算法在航空代理人細(xì)分應(yīng)用上的合理性。其中：C 為航空公司，A 為代理人，P 為乘客。

從業(yè)務(wù)范圍、經(jīng)營規(guī)模、經(jīng)銷模式3 個方面劃分航空客票代理人。根據(jù)航空客票代理人的銷售業(yè)務(wù)范圍，可將其分為兩類：一類客票銷售代理人主要負(fù)責(zé)國際航線或港澳臺地區(qū)航線的航空客票代理銷售業(yè)務(wù)；二類客票銷售代理人主要負(fù)責(zé)國內(nèi)除港澳臺地區(qū)以外的航空客票代理銷售業(yè)務(wù)。根據(jù)經(jīng)營規(guī)模，可將航空客票代理人分為大型、中型和小型代理人。根據(jù)航空客票代理人的經(jīng)銷模式，可以將其分為批發(fā)性代理人、差旅管理公司和在線分銷[10]。

圖3 聚類結(jié)果分析圖Fig.3 Analysis diagram of clustering results

根據(jù)圖3，從代理人的活躍度、市場地位及能力、市場定位和買賣交易偏好4 個方面對聚類結(jié)果進行分析，將分析結(jié)果結(jié)合機票銷售市場實際情況，對各個類別在市場中屬于何種代理人身份進行推測，從而得到如表3所示結(jié)果。

對相關(guān)代理人的研究與考核表明，實驗結(jié)果與考核結(jié)果相符合，證明算法具有實際應(yīng)用價值，適用于銷售代理人分類。

表3 各聚類特點描述及推測結(jié)果Tab.3 Characteristic description and conjectural result of each cluster

根據(jù)表3分析，首先針對第2、4 類小型的、市場占比低的代理人，需要航空公司對其進行調(diào)查、整頓，取消資質(zhì)不佳、有經(jīng)常拖欠票款等不良行為、業(yè)務(wù)水平低下者的代理人資格；培訓(xùn)其他代理人，以提高其素質(zhì)和銷售能力，逐漸提高其市場地位。針對第3、5、6類大型優(yōu)秀代理人，航空公司可以加大技術(shù)、資金和場地投入，增強代理人的信心與忠誠度，使雙方形成較為牢固的戰(zhàn)略合作關(guān)系。同時，航空公司還可與代理人共同發(fā)現(xiàn)和開發(fā)高收益用戶，針對該類用戶制定更優(yōu)質(zhì)的服務(wù)策略；針對第1 類代理人，航空公司可為其制定各種優(yōu)惠套餐和會員優(yōu)惠，將更多的用戶吸納進來。

4 結(jié)語

為了對航空客票代理人進行準(zhǔn)確定位，方便航空公司進行管理，在分布式系統(tǒng)上使用Canopy-K-means算法，對航空公司代理人的銷售數(shù)據(jù)進行處理與聚類。結(jié)果證明該方法能夠?qū)推贝砣诉M行有效細(xì)分，聚類結(jié)果符合實際情況，為航空公司管理代理人、制定銷售方案提供了參考。