趙倩蕓，李擁軍

（1.華南理工大學(xué)數(shù)學(xué)學(xué)院，廣州 510006；2.華南理工大學(xué)計算機(jī)科學(xué)與工程學(xué)院，廣州 510006）

0 引言

隨著互聯(lián)網(wǎng)技術(shù)的快速發(fā)展，各行業(yè)實現(xiàn)信息化服務(wù)已成為大勢所趨，當(dāng)然，航空行業(yè)也不例外。目前，我國航空業(yè)的電子信息系統(tǒng)已較為健全，同時，各個航空公司的數(shù)據(jù)庫中也都存有大量的包含旅客身份信息以及出行行為信息的統(tǒng)計數(shù)據(jù)[1]，但是這些數(shù)據(jù)就如同“散沙”般堆在數(shù)據(jù)倉庫中，隨著時間的日積月累，數(shù)據(jù)量也越來越大，在對客戶進(jìn)行細(xì)分時，傳統(tǒng)的K-means算法在K值選取以及聚類中心方面存在缺陷，針對此進(jìn)行優(yōu)化改進(jìn)，提出了Canopy-Kmeans算法。本文通過改進(jìn)的聚類算法將客戶細(xì)分，以便于為公司的市場營銷活動創(chuàng)建有針對性的便于管理的分組，并且可以識別各客戶分組的屬性與需求，比較不同細(xì)分群體的特征，從而確定針對各細(xì)分客戶的特定行動，最終開發(fā)適合航空業(yè)務(wù)部門使用的“客戶分群模型”，在為客戶提供更好服務(wù)的同時，也為提高公司的效益以及進(jìn)一步的發(fā)展做出貢獻(xiàn)。

1 K-means算法聚類

聚類是數(shù)據(jù)挖掘領(lǐng)域中的一種技術(shù)，是各企業(yè)進(jìn)行客戶細(xì)分比較常用的方法，它把一個沒有類別標(biāo)簽的樣本集按照某種準(zhǔn)則劃分成若干個子集，使得相似的樣本盡可能被歸為一類，而不相似的樣本盡量被劃分到不同類別中。在多種聚類算法中，最著名的一個算法便是K-means（K均值）算法，它也是最常被用于進(jìn)行客戶細(xì)分的聚類方法。K-means聚類是由Mac Queen在1967年提出的一種實時無監(jiān)督的硬聚類算法，此算法假定在歐氏空間下，并且以最小化誤差函數(shù)為約束條件，將數(shù)據(jù)對象劃分為k類（k為預(yù)先給定的）[2]，算法的初始中心點是隨機(jī)選取的，具有很大的隨機(jī)性和盲目性，一旦選取不好，會直接影響聚類效果，選取欠佳時，同樣會使得算法運行時間過長，影響算法的執(zhí)行效率。K-means算法的偽代碼如下：

從K-means算法的思想和偽代碼可以看出算法的時間復(fù)雜度為：

O（nkd）=所有對象數(shù)目*聚類簇數(shù)*迭代的總次數(shù)

其中，n表示所有數(shù)據(jù)對象的數(shù)目，k表示聚類的簇數(shù)，d則代表迭代的總次數(shù)。這便意味著：

算法的時間復(fù)雜度與聚類簇數(shù)k成正比。而在實際應(yīng)用中，k的選取一般都是憑借經(jīng)驗以主觀意愿為主的，當(dāng)k的值過大時，時間復(fù)雜度會很高，直接影響算法效率，當(dāng)k過小時，又會有損聚類的準(zhǔn)確度。這個標(biāo)準(zhǔn)很難把握。

算法的時間復(fù)雜度還與數(shù)據(jù)對象的總數(shù)目n成正比。當(dāng)要處理的數(shù)據(jù)量過大時，不可能將所有的數(shù)據(jù)同時加入內(nèi)存進(jìn)行處理，只能在硬盤與內(nèi)存之間頻繁交換，這就使得算法效率降低，耗費系統(tǒng)資源過多[3]。

由于航空公司提供的數(shù)據(jù)量相對較大，K-means算法的多次迭代，必然會使得算法的效率不夠高，為了提高效率，將K-means進(jìn)行優(yōu)化實現(xiàn)，便十分有必要了。

2 改進(jìn)算法：Canopy-Kmeans算法聚類

2.1 Canopy算法

Canopy算法是從數(shù)據(jù)集中隨機(jī)選取一個數(shù)據(jù)對象A，計算數(shù)據(jù)對象之間的距離確定相似性，將距離小于等于閾值T1（即數(shù)據(jù)對象之間相近）的數(shù)據(jù)對象劃分到同一個Canopy區(qū)域中，同時，距離比閾值T2小的數(shù)據(jù)點將不能再作為下一個數(shù)據(jù)子集Canopy的中心點，其中，T1＞T2。這樣，便生成了若干個Canopy子集（如B、C、D、E），這些 Canopy子集允許有交集，即每個數(shù)據(jù)對象可以同時歸于一個或多個Canopy子集，但是，每個Canopy子集必須至少包含一個數(shù)據(jù)對象。

算法步驟如下：

（1）將所有的數(shù)據(jù)對象預(yù)處理后放入一個集合D中，選取距離閾值T1和T2，其中，T1＞=T2；

（2）從數(shù)據(jù)集合D中隨機(jī)選取一個數(shù)據(jù)點P，計算P與所有Canopy子集中心點間的距離（若Canopy子集不存在，則將數(shù)據(jù)點P作為一個新Canopy的中心點，同時加入到Canopy中心點列表中，然后將其從集合D中刪除），若P和某個Canopy中心點之間的距離小于或等于T1，則將P加入到此中心點所屬的Canopy中；

（3）當(dāng)數(shù)據(jù)對象P和某個Canopy的中心點之間的距離小于等于T2時，將此數(shù)據(jù)對象從列表D中刪除，因為此時，它與這個Canopy很接近，不適合再作為其他Canopy子集的中心點；

（4）反復(fù)迭代此過程，重復(fù)執(zhí)行（2）-（3），直到集合D為空時，迭代過程結(jié)束。

2.2 Canopy-Kmeans算法

本次研究選用Canopy算法來對傳統(tǒng)的K-Means算法做出優(yōu)化[4]，即改進(jìn)后的Canopy-Kmeans算法，Canopy-Kmeans算法不需要我們?nèi)藶榈亟o定K值，會根據(jù)自身的迭代主動聚成類簇，因此可以先用Canopy算法對數(shù)據(jù)預(yù)處理，將得到的Canopy中心點直接作為聚類的初始中心點，這在某種程度上解決了傳統(tǒng)的K-means在k值以及初始中心點的選取方面的問題[5]，從而提高算法的迭代效率和準(zhǔn)確率。

本文將此優(yōu)化后的算法稱為Canopy-Kmeans算法，該算法分為兩個部分：首先，由Canopy算法進(jìn)行粗聚類，將數(shù)據(jù)集分為k個Canopy，每個Canopy都有一個中心點；其次，用K-means算法進(jìn)行細(xì)聚類，將第一步產(chǎn)生的Canopy中心點直接作為聚類初始中心點，在每一個Canopy中使用K-means算法計算數(shù)據(jù)點和中心點的距離，將數(shù)據(jù)點重新歸類。其詳細(xì)聚類步驟如下：

Canopy-Kmeans算法步驟

（1）將所有的數(shù)據(jù)預(yù)處理后放入集合D中，選取距離閾值：T1、T2，其中 T1＞T2;

（2）從數(shù)據(jù)集合D中隨機(jī)地選取一個數(shù)據(jù)點作為第一個Canopy的中心點，并將其從集合D中去除；

（3）計算D中其他的數(shù)據(jù)點和全部的Canopy子集中心點之間的距離，如果得到的距離小于等于T1，則將這個數(shù)據(jù)對象加入到此中心點對應(yīng)的Canopy子集中。若距離小于等于T2，則將這個數(shù)據(jù)對象從集合D中刪除。若距離大于T1，則將這個數(shù)據(jù)點作為一個新的Canopy中心點，加入到中心點列表中。

（4）重復(fù)迭代步驟（3），直到數(shù)據(jù)集合D為空集。通過以上幾步可以將集合D中的所有數(shù)據(jù)點劃分為k個Canopy子集，其中，每個數(shù)據(jù)點可以屬于一個甚至多個Canopy，并且k個Canopy包含所有的數(shù)據(jù)點，沒有數(shù)據(jù)孤點。

（5）將前面產(chǎn)生的k個Canopy中心點作為k個初始聚類中心點。

（6）由于k個Canopy子集之間是可能存在交集的，一個數(shù)據(jù)點可能同時屬于多個Canopy，所以應(yīng)該將這樣的數(shù)據(jù)點劃分到離它最近的Canopy子集中。即需要計算每個Canopy中全部數(shù)據(jù)點和Canopy的中心點之間的距離。

（7）更新每個Canopy的聚類中心點（每個Canopy中所有數(shù)據(jù)對象的平均值）。

（8）計算新的類簇中心點和最初的Canopy中心點之間的距離，若此距離小于等于T1，則將這個新類簇中心歸入到對應(yīng)的Canopy子集中。

（9）當(dāng)聚類標(biāo)準(zhǔn)函數(shù)收斂（新中心和舊中心的距離小于某個預(yù)先給定的閾值）時，退出迭代，否則重復(fù)執(zhí)行步驟（6）-（8）。

將Canopy中心點集合記為：CanopyCenterList=C（C1、C2、...、Ck）,聚類中心點的集合記為：P（P1、P2、...、Pk），下面給出Canopy-Kmeans算法的偽代碼，如下：

3 實例分析

為了測試傳統(tǒng)的K-means算法和優(yōu)化后的Cano?py-Kmeans算法的準(zhǔn)確率以及計算效率，我們采用機(jī)器學(xué)習(xí)標(biāo)準(zhǔn)測試數(shù)據(jù)庫UCI[6]（UCI Machine Learning Repository）中的兩個數(shù)據(jù)集Seeds和Car Evolution來做實驗，這些機(jī)器學(xué)習(xí)數(shù)據(jù)集是完全公開的，可以根據(jù)需要在網(wǎng)站上下載。它們的數(shù)據(jù)特征如表1所示。

表1 實驗數(shù)據(jù)集特征表

Seeds數(shù)據(jù)集是含有210個實驗樣本的小麥種子樣例，每個樣本有7個屬性，并根據(jù)種子的特征分為三個不同類別：卡瑪、羅薩以及加拿大；Car Evolution數(shù)據(jù)集是包含1728個實驗樣本的汽車樣例，每個樣本有6個屬性，并分為四個類別：unacc、acc、good以及 vgood。兩個數(shù)據(jù)集都是標(biāo)準(zhǔn)數(shù)據(jù)集，所以我們暫不對其進(jìn)行預(yù)處理，直接用原始數(shù)據(jù)進(jìn)行實驗。

由于本次試驗的主要目的在于比較傳統(tǒng)K-means算法和優(yōu)化后的Canopy-Kmeans算法的準(zhǔn)確性以及運算效率，所以實驗選擇在Spark平臺上采用單機(jī)模式進(jìn)行，在seeds數(shù)據(jù)集上，將傳統(tǒng)的K-means并行算法的迭代次數(shù)設(shè)為10次，將類別k設(shè)為3，將優(yōu)化后的Canopy-Kmeans算法的閾值T1和T2分別設(shè)為9和6；在Car Evolution數(shù)據(jù)集上，將傳統(tǒng)的K-means并行算法的迭代次數(shù)設(shè)為10次，將類別k設(shè)為4，將優(yōu)化后的Canopy-Kmeans算法的閾值T1和T2分別設(shè)為8和6。

另外，本實驗選取聚類結(jié)果的準(zhǔn)確率以及最小誤差平方和作為評價這兩種算法的準(zhǔn)確性標(biāo)準(zhǔn)，其中，準(zhǔn)確率是將實驗得到的聚類結(jié)果和UCI標(biāo)準(zhǔn)測試集中的類別標(biāo)簽做對比計算出來的（我們采用的Seeds和Car Evolution數(shù)據(jù)集都是帶有類別標(biāo)簽的），其定義如下：

其中mi是最后的聚類結(jié)果中被正確分到第i類的數(shù)據(jù)對象的個數(shù)，k是最終類別個數(shù)，n是所有的數(shù)據(jù)對象個數(shù)。最小誤差平方和Jmin則表示聚類多次迭代結(jié)束后的誤差平方和Js中的最小的一個，誤差平方和公式定義如下：

其中，s表示聚類的類別數(shù)目，nk表示第k個類別中的對象數(shù)目，表示第k個類中的第j個數(shù)據(jù)對象，mk則表示第k個類別的聚類中心點，另外，算法的運算效率則直接采用兩種算法聚類結(jié)果完成時分別耗用的時間t。最終的實驗結(jié)果如表2所示。

表2 傳統(tǒng)K-means算法和優(yōu)化后的算法的結(jié)果對比表

通過表2中的實驗結(jié)果，我們可以得到：一方面，由于Canopy-Kmeans算法先用Canopy方法粗聚類得到若干個Canopies，然后只在每個Canopies區(qū)域內(nèi)部計算每個數(shù)據(jù)點與Canopy中心點間的距離，而不用像傳統(tǒng)K-means算法那樣，必須迭代計算全部的數(shù)據(jù)點和每一個中心點的距離，因此優(yōu)化后的算法所用時間更少、效率更高；另一方面，優(yōu)化后的算法使用Canopy方法進(jìn)行預(yù)處理，將Canopy中心點直接作為聚類的初始中心點，這在一定程度上解決了K-means算法K值以及初始點的選取問題，因此準(zhǔn)確率也會相對有所提升。這就證明了我們優(yōu)化的模型Canopy-Kmeans的可用性。

4 數(shù)據(jù)整理與特征構(gòu)造

通過航空公司的數(shù)據(jù)接口直接讀取數(shù)據(jù)集市中的數(shù)據(jù)，對原始基礎(chǔ)表進(jìn)行清洗、合并，作為聚類模型的初始訓(xùn)練集，部分實驗數(shù)據(jù)字段如表3所示。

表3 部分實驗數(shù)據(jù)的字段描述

在對合并匯總后的基本數(shù)據(jù)進(jìn)行分析后發(fā)現(xiàn)，原始表中的數(shù)據(jù)雖然詳細(xì)充足，但是涉及到的變量太多，難免會有一些不重要的因素影響聚類的結(jié)果，因此，在建模之前我們需要分析原始數(shù)據(jù)變量，構(gòu)造并提取出對業(yè)務(wù)有用的衍生變量。通過對業(yè)務(wù)的充分理解與分析，并由航空業(yè)務(wù)領(lǐng)域的專家一起作出決策，決定從客戶的訂票行為、支付行為和乘機(jī)行為三個方面對用戶進(jìn)行細(xì)分，具體選取的建模變量如表4所示。

表4 衍生變量表格

5 細(xì)分結(jié)果及其分析

根據(jù)建立的模型，我們將處理后的數(shù)據(jù)在優(yōu)化后的Canopy-Kmeans模型上進(jìn)行客戶細(xì)分，其中Cano?py-Kmeans算法中的閾值T1和T2分別設(shè)為0.9和0.4，模型最終將所有的客戶一共分為8個群組，聚類結(jié)果如表5所示，其中，年齡、卡齡、現(xiàn)金支付比率、銀行卡支付比率、其他方式支付比率、B2C訂票比率、電話訂票比率、平均折扣率以及兩艙比率等21個字段對應(yīng)的數(shù)據(jù)均為簇內(nèi)所有數(shù)據(jù)對象的平均值。

根據(jù)聚類的結(jié)果，我們還可以得到各個分組中客戶的分布情況，最少的占5%，最大的占24%，相對較均勻，具體如圖1所示。

另外，由于我們利用Canopy-Kmeans算法模型對選取的18個業(yè)務(wù)指標(biāo)變量進(jìn)行聚類，是按客戶的訂票行為、支付行為和乘機(jī)行為來進(jìn)行分群的，為了同時判斷各組內(nèi)客戶的價值情況，我們需要分析每個組的RFM情況，具體情況如圖2所示。

通過表5的客戶細(xì)分結(jié)果、圖1的客戶群體分布以及圖2每個組的RFM情況，總結(jié)出各群體優(yōu)勢特征和弱勢特征，如表6所示。

表5 客戶細(xì)分結(jié)果表

圖1 客戶行為細(xì)分分布

圖2 客戶細(xì)分的RFM分布

表6 各組優(yōu)勢特征和弱勢特征

6 結(jié)語

本文采用優(yōu)化后的Canopy-Kmeans算法結(jié)合選取的航空客戶指標(biāo)數(shù)據(jù)進(jìn)行了客戶分群，并且對客戶細(xì)分的實驗結(jié)果進(jìn)行詳細(xì)分析，結(jié)合各分群的RFM分布，對八個客戶群進(jìn)行業(yè)務(wù)上的解釋并且通過以上相關(guān)分析，業(yè)務(wù)人員可根據(jù)分群結(jié)果以及客戶細(xì)分的RFM分布作出合適的營銷措施。

[1]楊鵬.基于數(shù)據(jù)挖掘的乘客出行行為研究[D].華南理工大學(xué),2016.

[2]Verma M,Srivastava M,Chack N,et al.A Comparative Study of Various Clustering Algorithms in Data Mining[J].International Journal of Engineering Research and Applications（IJERA）Vol,2012,2:1379-1384.

[3]李飛,薛彬,黃亞樓.初始中心優(yōu)化的K-Means聚類算法[J].計算機(jī)科學(xué),2002,29（27）:94-96.

[4]McCallum A,Nigam K,Ungar L H.Efficient Clustering of High-Dimensional Data Sets with Application to Rfference Matching[C].ACM,2000:169-178.

[5]袁方,周志勇,宋鑫.初始聚類中心優(yōu)化的K-means算法[J].計算機(jī)工程,2007,33（03）:65-66.

[6]UCI.Machine Learning Repository[EB/OL].http://archive.ics.uci.edu/ml/datasets.html.