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

李向榮 范福海 孟向海

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

1 引言

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

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

2 K-Means聚類算法

2.1 K-Means算法原理

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

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

通過K-Means 聚類算法實(shí)現(xiàn)數(shù)據(jù)分類的目標(biāo)就是使各類的距離平方和J( )wi最小。K-Means聚類算法其實(shí)是一個(gè)反復(fù)迭代的過程，最終實(shí)現(xiàn)所有數(shù)據(jù)樣本到各聚類中心距離的平方和J(W )最小。整個(gè)算法執(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)則，多年來(lái)學(xué)者們先后提出啟發(fā)式和貪婪準(zhǔn)則來(lái)確定類別數(shù)k ，較具有代表性的是根據(jù)經(jīng)驗(yàn)準(zhǔn)則2 ≤ kmax≤來(lái)選擇不同的聚類類別，多次運(yùn)行K-Means算法，從而選出理想效果情況下的最優(yōu)聚類數(shù)［4～8］。因此，該算法明顯的缺點(diǎn)是必須事先給定聚類數(shù)k 或多次迭代尋優(yōu)，如果選擇了不準(zhǔn)確的k 值往往會(huì)使聚類質(zhì)量下降，就失去聚類的意義。

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

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

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

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

其中:

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

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

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

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

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

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

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

根據(jù)實(shí)際分析需求，提取江蘇省常熟市停車項(xiàng)目以2017 年11 月30 日為截止時(shí)間，選取寬度為十個(gè)月的時(shí)間段作為觀測(cè)窗口，并將該時(shí)間段內(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 模型中:以車輛號(hào)牌作為唯一的ID 標(biāo)識(shí)，F(xiàn)（Frequency）表示車輛累計(jì)停車次數(shù)；L（Length）表示車輛的平均停車時(shí)長(zhǎng)；C（Cost）表示車輛停車后系統(tǒng)的平均計(jì)費(fèi)；P（Pay）表示車主平均支付的費(fèi)用；A（Arrears）表示車輛的累計(jì)欠費(fèi)額度。

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語(yǔ)

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