改進的K-means算法及其在鐵路客戶細分中的應(yīng)用

鄧 程 ，楊壯英，古軍杰，蔡 志，李 粵

（廣州鐵路（集團）公司 株洲北站，株洲 412001）

改進的K-means算法及其在鐵路客戶細分中的應(yīng)用

鄧 程 ，楊壯英，古軍杰，蔡 志，李 粵

（廣州鐵路（集團）公司 株洲北站，株洲 412001）

提出使用距離均和識別孤立點，并引入方差對孤立點進行判斷處理，對傳統(tǒng)的K-means算法進行改進并將改進后的K-means算法應(yīng)用到鐵路客戶細分領(lǐng)域，實驗結(jié)果表明，改進后的K-means算法能更為準確地對鐵路貨運客戶進行聚類分析，從多維的角度較為全面、深入地細分客戶消費行為特征，從而輔助鐵路貨運營銷部門制定有針對性的營銷策略，進行高效的客戶關(guān)系管理，提高市場競爭力。

數(shù)據(jù)挖掘；鐵路貨運；K-means算法

隨著當(dāng)今物流的高速發(fā)展，市場競爭日趨激烈，鐵路客戶營銷策略缺少對客戶消費行為的深入挖掘，無法對不同類型的客戶開展有針對性的營銷策略，導(dǎo)致客戶流失率緩慢增長以及鐵路貨運營業(yè)額的逐年下降。因此，確定新的分類指標，建立定量分析模型，對鐵路客戶進行更為精準的分類，是當(dāng)前鐵路貨運營銷部門所面臨的重要問題。

1 K-means算法

1.1 聚類分析的概念

聚類分析簡而言之是“物以類聚”，是指將抽象或具體集合分為由類似的對象組成的多個類的過程。由聚類所生成的簇是一組數(shù)據(jù)對象的集合，這些對象與同一個簇中的對象彼此相似，與其他簇中的對象相異。在商務(wù)上，聚類分析能幫助市場分析人員從客戶基本庫中發(fā)現(xiàn)不同的客戶群，并用購買模式來刻畫不同客戶群的特征。K-means算法是當(dāng)前應(yīng)用最為普遍的聚類算法。

1.2 K-means算法的基本思想

K-means算法的基本思想是：將數(shù)據(jù)集分為K個空間，以K個空間的中心點按照物以類聚的原則進行聚類，將其屬性值最接近的歸為一類。然后進行迭代，不斷移動簇集中的對象，更新各簇類中心的值，直至總體平方誤差Sum of squared errors（SSE）達到預(yù)先規(guī)定的閾值，使得相同簇中對象高相似度，不同簇中對象之間高相異度。

1.3 孤立點對K-means聚類結(jié)果的影響

在數(shù)據(jù)挖掘范疇內(nèi)，孤立點是指數(shù)據(jù)集中不符合一般模型的那些對象，即和其它的數(shù)據(jù)有著不同的性質(zhì)，它可能是度量或執(zhí)行錯誤所導(dǎo)致的，也可能是固有數(shù)據(jù)變異性的結(jié)果。即使是少量孤立點的存在也會對聚類結(jié)果產(chǎn)生很大的影響，因為孤立點的存在會使平均值得到很大的偏離，影響聚類準確度，嚴重影響了K-means算法的實際使用效果。

1.4 傳統(tǒng)K-means算法中的不足

目前在K-means算法中普遍采用Euclidean Distance公式，即歐式距離作為檢測數(shù)據(jù)集之間的相關(guān)性，如公式（1）所示：

歐式距離是指兩點在歐式空間的直線距離，其優(yōu)點是幾何意義簡單直觀，如圖1所示，Euclidean Distance是以圓形方式逼近中心點。

圖1 Euclidean Distance公式逼近中心點效果圖

從圖1中可以看出距離公式法的不足之處在于：歐式距離將數(shù)據(jù)集中的不同屬性之間的差別同等看待，即各屬性對歐式距離的貢獻是相同的。相異度很小的屬性之間對歐式距離的貢獻很小。因此歐式距離往往不能滿足實際情況的需要。本文從對孤立點的識別和處理作為切入點，對傳統(tǒng)的K-means算法進行改進。

2 K-means優(yōu)化算法的改進

2.1 算法的改進思想

（1）對孤立點的識別

定義1：距離和Hi

Hi代表點i和其它點距離的總和，如公式（2）所示。

公式（2）中，Xih，Xjh分別代表兩點的坐標值。

定義2：距離均和S

S代表點i和其它點距離的均和，如公式（3）所示。

其中n為樣本數(shù)據(jù)d位數(shù)據(jù)的維數(shù)。對每個數(shù)據(jù)點i，首先計算其距離和Hi，并計算距離均和S，公式（3）中α為距離調(diào)節(jié)因子，本文通過實驗對α值進行對比，確定為1.05。即當(dāng)某個點距離待聚類的種群數(shù)據(jù)的平均距離均和的1.05倍時，則認定為孤立點。將該孤立點從初始樣本中挑選出來，以此類推，找出初始樣本中所有的孤立點。

（2）引入方差對孤立點進行處理

由于相異度很小的屬性之間對歐式距離的貢獻很小。所以不能僅僅依靠距離來判斷孤立點屬于臟數(shù)據(jù)而給予拋棄。因此在對孤立點進行考核的時候，還要依據(jù)孤立點與簇內(nèi)的相似度。在此引入方差，因為相似度可以用方差來衡量。如果簇內(nèi)的方差越大，則說明簇內(nèi)的相似度越小。反之如果簇內(nèi)方差越小，則說明簇內(nèi)的相似度越大。

類K的方差Vk的定義：

公式（4）中Ak表示類k內(nèi)的數(shù)據(jù)集x所構(gòu)成的空間；x表示類k的數(shù)據(jù)集；Xj表示數(shù)據(jù)點在變量j上的取值；nsk表示類k內(nèi)的數(shù)據(jù)集數(shù)量；表示k的中心點在變量j上的取值；

相對距離的定義：

計算每個孤立點各簇內(nèi)中心的相對距離，將孤立點分配到與之最近的簇中，如果加入孤立點后的SSE大于加入孤立點之前的SSE，則拋棄該孤立點，反之則將將孤立點分配到該簇。

2.2 改進的K-means算法描述

3 基于改進的K-means算法的鐵路貨運客戶細分

3.1 鐵路客戶細分指標的確定和數(shù)據(jù)預(yù)處理

（1）分類指標的確定

通過與鐵路貨運營銷人員溝通，確定客戶細分分類指標包括：客戶關(guān)系建立時間、月平均運費、年度運輸配送次數(shù)、年度運輸配送次數(shù)、是否存在附加收益、年發(fā)送量、客戶影響力。

（2）數(shù)據(jù)預(yù)處理

在數(shù)據(jù)挖掘中，提取自2012年6月1日00： 00 ～ 2013年6月1日23：59，2年共129 196條記錄。數(shù)據(jù)來源于中鐵快運貨票中的歷史數(shù)據(jù)，這些原始的數(shù)據(jù)不可能不加處理的直接用于數(shù)據(jù)挖掘，存在的一些噪聲，缺失數(shù)據(jù)和不一致性數(shù)據(jù)會給數(shù)據(jù)挖掘的結(jié)果產(chǎn)生較大影響。因此，在進行數(shù)據(jù)挖掘之前，必須對這些數(shù)據(jù)進行預(yù)處理。所用的數(shù)據(jù)預(yù)處理包含數(shù)據(jù)集成、數(shù)據(jù)歸約、數(shù)據(jù)清理和數(shù)據(jù)變換幾種方法。由于年度運輸配送次數(shù)采用的是離散型的數(shù)值，而年度運輸配送次數(shù)是一個連續(xù)性數(shù)值屬性，需要把連續(xù)值屬性離散化，采用概念分層的方法，具體約定如表1所示。

表1 規(guī)范化約定表

3.2 聚類結(jié)果分析

經(jīng)過反復(fù)實驗，最終將鐵路客戶劃分為5個簇類，聚類分析如表2所示。

表2 聚類結(jié)果分析表

從表2可以看出，高端客戶占鐵路運輸收益的貢獻值最大，在今后的工作中要進一步加強這部分客戶關(guān)系的維護工作。戰(zhàn)略客戶群雖然不穩(wěn)定，但是達到了鐵路平均收益的1/4，是鐵路營銷部門開拓市場重點發(fā)展的對象，提供有針對性的個性化服務(wù)，爭取將這部分客戶發(fā)展在鐵路的高端客戶，這將極大提高鐵路的經(jīng)濟收益。

用原K-means算法對相同的預(yù)處理后數(shù)據(jù)集進行挖掘，其聚類結(jié)果相差較大。每個簇之間的界定，無法清晰地給出，因為某些客戶群的劃分是矛盾的。2次實驗結(jié)果差異的原因就是在于是否對數(shù)據(jù)集去除了孤立點。

例如“株洲火炬工業(yè)爐有限責(zé)任公司”這個客戶，在去除孤立點之后的K-means中聚類到簇1高端客戶群中。而在沒有去除孤立點之后的K-means聚類中，則被劃分到簇3戰(zhàn)略客戶群中，其原因就是“永利化工”這個客戶，按照優(yōu)化K-means是一個孤立點，“永利化工”在2012年5月～2012年9月，共產(chǎn)生運輸次數(shù)71次，超過任何一個客戶當(dāng)年運輸總次數(shù)。因此其特征更加靠近簇2中端客戶群，但是“永利化工”其它的屬性特征，例如客戶類型，客戶關(guān)系發(fā)生時間，運費金額，客戶忠誠度等屬性又符合簇1低端客戶群的特征，因此在做聚類分析的時候，造成質(zhì)心偏離，得出不一樣的聚類結(jié)果。經(jīng)過和鐵路貨運人員溝通確定，“株洲火炬工業(yè)爐有限責(zé)任公司”應(yīng)屬低端客戶群，從而也論證了去除孤立點算法對準確進行客戶的聚類劃分是有幫助。

4 結(jié)束語

本文針對傳統(tǒng)的基于距離識別孤立點的K-means算法中，無法處理密度不均勻的數(shù)據(jù)集局部特征的缺點進行了改進，提出了使用距離均和識別孤立點，并引入方差對孤立點進行判斷處理。通過實驗驗證，改進后的K-means算法有效避免了將孤立點全部拋棄的盲目性，有效降低了總體平方誤差，把相同特質(zhì)的數(shù)據(jù)劃為一個簇內(nèi)，提高了聚類的精確度。將改進后的K-means算法，應(yīng)用到鐵路客戶細分領(lǐng)域，使得聚類結(jié)果更為精確，從多維的角度較為全面、深入地細分客戶消費行為特征。在確定目標客戶后，鐵路貨運營銷部門可以實施有針對性的營銷和客服方案，進行高效的客戶關(guān)系管理。下一步工作的重點是全面分析鐵路營業(yè)額季節(jié)性周期變化規(guī)律與客戶特征之間的關(guān)聯(lián)規(guī)則，以提高鐵路貨運的競爭力和市場占有率。

[1]Johannes Grabneier,Andreas Rudolph. Techniques of Cluster Algorithms in Data Mining, Data Mining and Knowledge Discovery[J]. Kluwer Academic Publishers, 2002(6): 303-360.

[2]景 波，劉 瑩，黃 兵. 基于孤立點檢測的工作流研究 [J]. 計算機工程，2008，4（22）： 268-270.

[3]潘 瑩，梁京章，黎慧娟. 基于K-means算法的校園網(wǎng)用戶行為的聚類分析 [J]. 計算技術(shù)與自動化，2007，26（1）：66-68.

[4]陳 偉. Apriori算法的優(yōu)化方法[J]. 計算機技術(shù)與發(fā)展，2009，19（6）：80-83.

責(zé)任編輯 方 圓

Improved K-means Algorithm and its application in railway customer segmentation

DENG Cheng, YANG Zhuangying, GU Junjie, CAI Zhi, LI Yue
( Zhuzhou North Station, Guangzhou Railway Group Company, Zhuzhou 412001, China )

This paper put forward the idea of improving the traditional K-means Algorithm with identifying the isolated points by average distance sum, and judged and processed the isolated points by introducing variance. The improved K-means Algorithm was applied to the field of railway freight customer segmentation. The experimental result showed that the improved K-means Algorithm could carry out cluster analysis on railway freight customers more accurately, sectionalize the characteristics of customers’ consuming behaviors in a comprehensive and in-depth manner from multidimensional perspectives, thus assist railway freight marketing department to formulate targeted marketing strategies, carry out high eff i cient customer relation management and increase market competitiveness.

data mining; railway freight transportation; K-means Algorithm

U293∶TP39

：A

1005-8451（2014）06-0045-04

2013-12-19

鄧 程 ，技術(shù)員；楊壯英，工程師。