樊 瑋，張 偉

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

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

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

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

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

1 Canopy-K-means 算法

1.1 K-means 簡(jiǎn)介及其不足

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

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

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

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

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

1.2 Canopy 算法

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

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

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

3）如果距離小于t1，則將該數(shù)據(jù)分配到該Canopy（1 個(gè)數(shù)據(jù)可以分配給多個(gè)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 個(gè)Canopy 集合，實(shí)線大圓表示t1的范圍，虛線小圓表示t2的范圍。

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

1.3 分布式Canopy-K-means 算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 仿真研究

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

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

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

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

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

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

3.3 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

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

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

4 結(jié)語

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