改進(jìn)K-Means聚類算法在停車用戶價值分群中的應(yīng)用?

李向榮 范福海 孟向海

（青島科技大學(xué) 青島 266061）

1 引言

伴隨著互聯(lián)網(wǎng)時代引發(fā)出激烈的市場競爭，現(xiàn)在很多企業(yè)將營銷的焦點，從傳統(tǒng)的以產(chǎn)品為中心轉(zhuǎn)變?yōu)橐杂脩魹橹行?，而用戶關(guān)系管理系統(tǒng)的關(guān)鍵問題就是用戶的價值分類，企業(yè)通過將用戶進(jìn)行分類，可以針對不同價值的用戶為用戶制定個性化的服務(wù)方案，最大限度挖掘用戶的潛藏價值，充分發(fā)揮營銷策略，實現(xiàn)企業(yè)利潤最大化、服務(wù)用戶最優(yōu)化的目標(biāo)。K-Means 算法作為典型的基于距離的快速聚類算法，在企業(yè)進(jìn)行用戶價值分類中得到較廣泛的應(yīng)用。該算法最初是由Steinhaus、Lloyd、BallHall、McQueen 分別于 1955 年、1957 年、1965 年和1967 年在各自不同的科學(xué)領(lǐng)域獨立提出來的，后來被廣泛研究和應(yīng)用，并在后續(xù)發(fā)展中不斷的改進(jìn)和優(yōu)化［1～2］。

本文以現(xiàn)有停車業(yè)務(wù)后臺數(shù)據(jù)為支撐，結(jié)合傳統(tǒng)K-Means聚類算法，提出了一種確定樣本數(shù)據(jù)最優(yōu)聚類數(shù)的方法，用來評估該算法的聚類結(jié)果，并確定樣本數(shù)據(jù)的最優(yōu)聚類數(shù)，有效地解決了重復(fù)選擇聚類數(shù)目導(dǎo)致的聚類效率低、迭代繁瑣［3～5］。根據(jù)停車數(shù)據(jù)的內(nèi)在需求，借鑒經(jīng)典的客戶關(guān)系管理RFM 模型，結(jié)合實際停車業(yè)務(wù)場景，通過建立合理的用戶價值評估模型，對用戶聚類分群，分析比較不同用戶群的用戶價值，給企業(yè)后續(xù)制定差異化的營銷策略，針對不同的用戶群提供個性化的用戶服務(wù)提供了良好的參照。

2 K-Means聚類算法

2.1 K-Means算法原理

K-Means 算法是以距離作為相似性的評價指標(biāo)，并在最小化誤差函數(shù)的基礎(chǔ)上將數(shù)據(jù)劃分為預(yù)定的類別數(shù)據(jù)k 的一種典型的聚類算法。即認(rèn)為兩個對象的距離越近，其相似度就越大［6］。

設(shè)X={x1,x2…,xi,…,xn} 是一給定的包含n個m 維數(shù)據(jù)點的數(shù)據(jù)集合，其中 xi?Rm，采用K-Means 聚類算法是將數(shù)據(jù)對象劃分為k 個劃分W={wi,k=1,2,…k }，每一個劃分稱為一個類wk，每一個類均有一個類別中心μi，選取歐式距離作為類別間相似性和距離判斷準(zhǔn)則，計算各點到聚類中心的距離平方和:

通過K-Means 聚類算法實現(xiàn)數(shù)據(jù)分類的目標(biāo)就是使各類的距離平方和J( )wi最小。K-Means聚類算法其實是一個反復(fù)迭代的過程，最終實現(xiàn)所有數(shù)據(jù)樣本到各聚類中心距離的平方和J(W )最小。整個算法執(zhí)行一次的流程包括圖1 中4步。

圖1 傳統(tǒng)K-Means聚類算法流程

由圖1 得知，傳統(tǒng)K-Means 聚類算法是在假設(shè)聚類數(shù)k 已知的前提下進(jìn)行的，由于缺少嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)準(zhǔn)則，多年來學(xué)者們先后提出啟發(fā)式和貪婪準(zhǔn)則來確定類別數(shù)k ，較具有代表性的是根據(jù)經(jīng)驗準(zhǔn)則2 ≤ kmax≤來選擇不同的聚類類別，多次運(yùn)行K-Means算法，從而選出理想效果情況下的最優(yōu)聚類數(shù)［4～8］。因此，該算法明顯的缺點是必須事先給定聚類數(shù)k 或多次迭代尋優(yōu)，如果選擇了不準(zhǔn)確的k 值往往會使聚類質(zhì)量下降，就失去聚類的意義。

2.2 改進(jìn)K-Means聚類算法

鑒于此，為了更加有效地反映聚類結(jié)構(gòu)類別間的分離性和類別內(nèi)的緊密型［5］，提出BWP 指標(biāo)，來確定算法的最優(yōu)聚類類別數(shù)k 。

假設(shè) K=(X ,Y )為聚類空間，其中 X={x1,x2,…xn} ，n 個數(shù)據(jù)對象被聚成m 類，定義第i類的第 j 個樣本的最小類別間的距離為a( i,j )，其最小類內(nèi)距離為b( i,j )，定義BWP 指標(biāo)為第 i 類的第 j 個樣本的聚類距離與其聚類離差聚類的比值，其計算公式為

BWP 指標(biāo)可以很好地正向反映單個樣本聚類的有效性，對于整體數(shù)據(jù)集，可以通過計算所有樣本數(shù)據(jù)聚成k 類時BWP 指標(biāo)的平均值avgbwp( k )，來分析總體聚類效果，其對應(yīng)的最大值就是所需的最優(yōu)聚類數(shù)kσ。

其中:

通過改進(jìn)K-Means 聚類算法直接定位樣本數(shù)據(jù)所要聚成的類別，省去了多次重復(fù)迭代的時間。該算法執(zhí)行過程如下:

1）輸入樣本數(shù)據(jù)集，初選聚類類別范圍2 ≤ k ≤ n ；

2）循環(huán)調(diào)用K-Means算法，并利用（2）式和（3）式分別計算出單個樣本的BWP 指標(biāo)值和數(shù)據(jù)集平均BWP指標(biāo)值；

3）將式（3）結(jié)果代入式（4）計算并輸出最優(yōu)聚類數(shù)kσ；

4）利用該聚類數(shù)分析得出聚類結(jié)果。

3 改進(jìn)K-Means 聚類算法在停車業(yè)務(wù)上的應(yīng)用

3.1 數(shù)據(jù)準(zhǔn)備與預(yù)處理

根據(jù)實際分析需求，提取江蘇省常熟市停車項目以2017 年11 月30 日為截止時間，選取寬度為十個月的時間段作為觀測窗口，并將該時間段內(nèi)的所有停車訂單記錄數(shù)據(jù)進(jìn)行探索、預(yù)處理后，重構(gòu)數(shù)據(jù)字段作為分析模型參數(shù)，在進(jìn)行變量標(biāo)準(zhǔn)化、歸一化處理后［8～12］，作為K-Means聚類分析的數(shù)據(jù)集。

圖2 FLCPA模型構(gòu)建流程

特別的，在FLCPA 模型中:以車輛號牌作為唯一的ID 標(biāo)識，F(xiàn)（Frequency）表示車輛累計停車次數(shù)；L（Length）表示車輛的平均停車時長；C（Cost）表示車輛停車后系統(tǒng)的平均計費(fèi)；P（Pay）表示車主平均支付的費(fèi)用；A（Arrears）表示車輛的累計欠費(fèi)額度。

3.2 BWP指標(biāo)確定與最優(yōu)聚類數(shù)

表1 幾種有效性指標(biāo)確定的停車數(shù)據(jù)集的最優(yōu)聚類數(shù)

為了更加有效地檢驗BWP 指標(biāo)確定最優(yōu)聚類數(shù) k 的性能，引入 DB 指標(biāo)、CH 指標(biāo)、Wint 指標(biāo)和IGP 指標(biāo)這四項指標(biāo)作為參照［5，13］。停車數(shù)據(jù)集的結(jié)構(gòu)分布和聚類結(jié)果如圖3所示。

圖3 k=4 時停車數(shù)據(jù)集的最優(yōu)聚類結(jié)果

3.3 用戶分群聚類結(jié)果

根據(jù)以上步驟最終確定，針對現(xiàn)有采集的停車訂單數(shù)據(jù)集，采用改進(jìn)K-Means聚類算法的最優(yōu)聚類數(shù)為4。表2 是得出的最終聚類結(jié)果，表3 展示了各分類用戶群的優(yōu)勢特征和劣勢特征。

表2 停車數(shù)據(jù)集的最終聚類結(jié)果

表3 用戶分類群特征描述表

通過綜合考慮實際停車業(yè)務(wù)，每個用戶群都有各自顯著的表現(xiàn)特征，基于該表現(xiàn)特征，可將以上類別定義成四個等級的用戶類別:重要保持用戶、重要發(fā)展用戶、一般價值用戶、一般挽留用戶［14～17］。各類用戶群的價值特征如下。

重要保持用戶（用戶群1）:這類車主的顯著特征是停車次數(shù)（F）多、單次停車時間（L）較長、且欠費(fèi)額度（A）少，這類用戶是停車業(yè)務(wù)鏈中最優(yōu)質(zhì)的會員，其貢獻(xiàn)最大，是項目營收的主要成分。

重要發(fā)展用戶（用戶群2）:這類用戶是停車業(yè)務(wù)中的潛在用戶，其平均停車時長（L）和平均支付金額（P）較好，且信用度最高，但由于這部分車主停車不固定，應(yīng)盡可能積極引導(dǎo)用戶。

一般價值用戶（用戶群3）:這類用戶存在明顯的欠費(fèi)行為，信用度較差，總體占比一般，可能大都在開展活動時選擇收費(fèi)停車泊位停車。

一般挽留用戶（用戶群4）:這類用戶停車頻率（F）最少，且只占總體的2.53%，整體價值較低，較少活動在城市中心等繁華路段。

4 結(jié)語

本文通過改進(jìn)傳統(tǒng)K-Means 聚類算法聚類數(shù)不確定問題，采用BWP 有效性指標(biāo)來確定最優(yōu)聚類數(shù)，減少了重復(fù)迭代的繁瑣，提高了算法運(yùn)行的效率，并在此基礎(chǔ)上將其應(yīng)用于實際停車業(yè)務(wù)后臺數(shù)據(jù)中，根據(jù)業(yè)務(wù)的需求，重新構(gòu)建FLCPA 參數(shù)模型，理論與實踐相結(jié)合，充分驗證了改進(jìn)K-Means聚類算法在用戶價值分群中的必要性和良好性能。