基于K-means算法的優化及在航空業客戶細分的應用

趙倩蕓，李擁軍

（1.華南理工大學數學學院，廣州 510006；2.華南理工大學計算機科學與工程學院，廣州 510006）

0 引言

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

1 K-means算法聚類

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

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

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

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

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

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

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

2 改進算法：Canopy-Kmeans算法聚類

2.1 Canopy算法

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

算法步驟如下：

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

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

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

（4）反復迭代此過程，重復執行（2）-（3），直到集合D為空時，迭代過程結束。

2.2 Canopy-Kmeans算法

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

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

Canopy-Kmeans算法步驟

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

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

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

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

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

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

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

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

（9）當聚類標準函數收斂（新中心和舊中心的距離小于某個預先給定的閾值）時，退出迭代，否則重復執行步驟（6）-（8）。

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

3 實例分析

為了測試傳統的K-means算法和優化后的Cano?py-Kmeans算法的準確率以及計算效率，我們采用機器學習標準測試數據庫UCI[6]（UCI Machine Learning Repository）中的兩個數據集Seeds和Car Evolution來做實驗，這些機器學習數據集是完全公開的，可以根據需要在網站上下載。它們的數據特征如表1所示。

表1 實驗數據集特征表

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

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

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

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

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

表2 傳統K-means算法和優化后的算法的結果對比表

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

4 數據整理與特征構造

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

表3 部分實驗數據的字段描述

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

表4 衍生變量表格

5 細分結果及其分析

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

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

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

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

表5 客戶細分結果表

圖1 客戶行為細分分布

圖2 客戶細分的RFM分布

表6 各組優勢特征和弱勢特征

6 結語

本文采用優化后的Canopy-Kmeans算法結合選取的航空客戶指標數據進行了客戶分群，并且對客戶細分的實驗結果進行詳細分析，結合各分群的RFM分布，對八個客戶群進行業務上的解釋并且通過以上相關分析，業務人員可根據分群結果以及客戶細分的RFM分布作出合適的營銷措施。

[1]楊鵬.基于數據挖掘的乘客出行行為研究[D].華南理工大學,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]李飛,薛彬,黃亞樓.初始中心優化的K-Means聚類算法[J].計算機科學,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]袁方,周志勇,宋鑫.初始聚類中心優化的K-means算法[J].計算機工程,2007,33（03）:65-66.

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