基于混合聚類算法的客戶細(xì)分策略研究

王　虹,孫　紅

(1.上海理工大學(xué) 光電信息與計算機(jī)工程學(xué)院,上?！?00093;2.上海理工大學(xué) 上?，F(xiàn)代光學(xué)系統(tǒng)重點(diǎn)實(shí)驗(yàn)室,上海　200093)

基于混合聚類算法的客戶細(xì)分策略研究

王虹1,2,孫紅1,2

(1.上海理工大學(xué) 光電信息與計算機(jī)工程學(xué)院,上海200093;2.上海理工大學(xué) 上?，F(xiàn)代光學(xué)系統(tǒng)重點(diǎn)實(shí)驗(yàn)室,上海200093)

摘要針對層次聚類法和 K-means 聚類法的缺陷和不足,提出將二者相結(jié)合的改進(jìn)算法,既解決了層次聚類法伸縮性差的問題,又解決了 K-means聚類法對初始聚類中心敏感的問題。通過對改進(jìn)算法的計算復(fù)雜度分析并利用 UCI 數(shù)據(jù)庫的測試數(shù)據(jù)對改進(jìn)算法進(jìn)行測試。結(jié)果表明,混合聚類算法使樣本聚類的準(zhǔn)確率提高到94%,并有更高的執(zhí)行效率和更好地實(shí)用性。此外,將此算法應(yīng)用到汽車銷售公司的客戶細(xì)分管理中,得出了差別化明顯的客戶細(xì)分類別,表明此改進(jìn)算法具有更強(qiáng)的客戶細(xì)分能力以及客戶行為特征的解釋能力。

關(guān)鍵詞層次聚類法;K-means算法;混合聚類算法;客戶細(xì)分;汽車銷售

Customer Segmentation Strategy Based on Hybrid Clustering Algorithm

WANG Hong1,2,SUN Hong1,2

(1.School of Optical-Electrical and Computer Engineering,University of Shanghai for Science and Technology,

Shanghai 200093,China;2.Shanghai Key Lab of Modern Optical System,University of Shanghai for

Science and Technology,Shanghai 200093,China)

AbstractAn improved algorithm is put forward to fuse the hierarchical clustering method and the K- means clustering method to solve both the poor scalability of the former and the sensitivity to the initial clustering center of the latter.The computing complexity analysis of the improved algorithm and the test data of UCI database testing results show that the hybrid clustering algorithm increases the sample clustering accuracy to 94% with a higher efficiency and better practicability.In addition,this algorithm is applied to the car sales company in the management of customer segmentation,where the differential is obtained obviously of customer segmentation categories,showing that the improved algorithm has higher detection rate and stronger interpretation ability on customer behaviors.

Keywordshierarchical clustering;K-means algorithm;hybrid clustering algorithm;customer segmentation;auto sale

聚類算法中劃分聚類和層次聚類法是常見的兩種聚類技術(shù)。劃分聚類方法具有較高的執(zhí)行效率,但存在初始中心選擇的隨機(jī)性問題,聚類精度較低。層次聚類法在算法上比較符合數(shù)據(jù)的特性[1],但在該算法中,一旦一個分裂或合并被執(zhí)行就不能修正,使其聚類質(zhì)量受到影響,且時間復(fù)雜度較高[2]。鑒于劃分和層次聚類法各自在處理數(shù)據(jù)上的優(yōu)勢和缺陷,本文充分結(jié)合兩種算法的特點(diǎn),提出將二者結(jié)合的混合聚類算法,在凝聚層次聚類的基礎(chǔ)上進(jìn)行K-means[3]算法繼而完成聚類分析,最后將混合聚類算法應(yīng)用于汽車銷售[4]公司的客戶細(xì)分管理系統(tǒng)中使其得到有效的細(xì)分客戶類別,提高客戶細(xì)分能力和客戶行為特征[5]解釋能力。

1K-means 和 凝聚層次聚類

K-means算法是基于劃分的聚類算法[6],該算法對于大數(shù)據(jù)集是相對可伸縮的和高效率的,時間復(fù)雜度是O(nkt),n是數(shù)據(jù)集大小,k是聚類數(shù),而t是迭代次數(shù)。但該算法的缺點(diǎn)明顯:(1)k的確定一般來說是困難的;(2)不適合發(fā)現(xiàn)非凸面形狀的簇;(3)對孤立點(diǎn)是較為敏感的。

凝聚層次聚類[7]算法雖具有較好的聚類質(zhì)量,沒有K-means算法的初始值選擇問題,能產(chǎn)生較高質(zhì)量的聚類,但昂貴的時間復(fù)雜度O(n2logn)和空間復(fù)雜度O(n2)使其難以應(yīng)用于大規(guī)模的數(shù)據(jù)集中。

2基于K-mean和凝聚層次的混合算法

2.1　輪廓系數(shù)

輪廓系數(shù)將簇的凝聚度和分離度有機(jī)結(jié)合形成一種有效的簇評估度量,其值可有效確定待測數(shù)據(jù)集中所包含簇的個數(shù)。輪廓系數(shù)將數(shù)據(jù)集中任一對象與本簇中其他對象的相似性以及該對象與其他簇中對象的相似性量化,且將量化后的兩種相似性按某種方式組合,獲得聚類的優(yōu)劣評價。對于某一對象i,其輪廓系數(shù)為[8]

(1)

其中,ai是對象i到本簇中其他對象的平均距離;bi是對象i到其他簇中對象平均距離的最小值。

2.2　基于K-mean和凝聚層次的混合算法

混合聚類算法引入輪廓系數(shù)的概念,通過計算不同K值下整個簇集的平均輪廓系數(shù)獲得簇的最優(yōu)數(shù)目Kopt。另外,由于首先進(jìn)行的層次聚類算法已將鄰近性較強(qiáng)的對象歸并為一簇,而隨后的K-means算法也旨在聚集相似的對象,因此K-means算法完全可信任層次聚類算法的結(jié)果,在層次聚類算法的基礎(chǔ)上完成K-means算法。

此外,混合聚類算法還能識別數(shù)據(jù)集中的離群點(diǎn),這將有助于形成正確的結(jié)果簇集。可為K-means算法設(shè)定一閾值,一旦某對象與所有簇中心的距離均超過了該閾值,則認(rèn)為該對象是離群點(diǎn);否則將此對象歸并到與其距離最接近的簇中,且動態(tài)漸進(jìn)地更新簇的中心。

混合聚類算法的流程表述如下:(1)引入silhouette,將含有n個原始數(shù)據(jù)的集合分類,分別計算不同K值下的silhouette,選取silhouette最大值對應(yīng)的K值作為最優(yōu)聚類數(shù)Kopt;(2)repeat;(3)選取兩個最接近的簇(或?qū)ο?且合并其生成一新簇;(4)計算合并前兩簇(或?qū)ο?的平均值作為所生成新簇的中心;(5)until整個數(shù)據(jù)集僅剩余(Kopt+REAR)個簇;(6)repeat;(7)計算出每個簇的整體相似度;(8)選取出當(dāng)前簇集內(nèi)整體相似度[9]最低的簇,將該簇內(nèi)的對象分別分配給與其最鄰近的簇同時更新該簇的中心;(9)until數(shù)據(jù)集中僅剩余Kopt個簇;(10)repeat;(11)依次選取數(shù)據(jù)集中所有對象;(12)if該對象已經(jīng)包含在第(9)步所生成的Kopt個簇中then繼續(xù)保持將該對象在此簇中;(13)else計算該對象與已存在的Kopt個簇中心之間的距離;(14)if該對象與所有簇的距離均超過了所設(shè)定的閾值eps then將此對象視為離群點(diǎn);(15)else將此對象歸并到與其最為接近的一個簇中,同時更新簇的中心;(16)until整個簇集中對象的分布不再變化?；旌暇垲愃惴ü采婕暗絻蓚€參數(shù)REAR 和Eps,REAR依據(jù)層次聚類算法的執(zhí)行程度來取值,閾值Eps的設(shè)定是為了更好地識別數(shù)據(jù)集中存在的少量離群點(diǎn)。所以,閾值Eps的設(shè)定要根據(jù)實(shí)際應(yīng)用來權(quán)衡。

3算法的性能分析和優(yōu)勢驗(yàn)證

3.1　算法的計算復(fù)雜度分析

改進(jìn)后的混合聚類算法大致可分為3個階段:步驟(1)尋求最優(yōu)聚類數(shù)Kopt,步驟(2)~步驟(9)采用凝聚層次聚類算法進(jìn)行聚類分析,步驟(10)~步驟(16)用K-means 算法完成聚類分析。其中步驟(1)為獲取Kopt需多次求解輪廓系數(shù),故該步驟的計算復(fù)雜度是O(I×n),其中I是求解輪廓系數(shù)的次數(shù),由經(jīng)驗(yàn)規(guī)則可知I≤n。第二階段的層次聚類算法的計算復(fù)雜度主要集中于第步驟(2)~步驟(5),其中步驟(3)~步驟(4)涉及n-(Kopt+REAR)次迭代,對于第i次迭代,步驟(3)需時間O((n-i+1)2)來搜索相似度矩陣,步驟(4)需時間O(n-i+1)來更新相似度矩陣。而第3階段的K-means算法中的所有步驟的計算復(fù)雜度均不會超過O(n2)。所以,整個算法的計算復(fù)雜度應(yīng)為O((n-C)×n2),若將相似度矩陣中的值存放于有序表中,則步驟(3)查找兩個最近簇的開銷可降低為O(n-i+1),但出于維護(hù)有序表結(jié)構(gòu)的附加開銷,算法最終的計算復(fù)雜度可降為O((n-C)×nlogn),其中C=Kopt+REAR,是與簇數(shù)相關(guān)的常數(shù)。

顯然,改進(jìn)后的混合聚類算法的計算復(fù)雜度要優(yōu)于單獨(dú)分別使用的K-means和凝聚層次聚類算法,有更高的執(zhí)行效率和更好的實(shí)用性。

3.2　利用UCI數(shù)據(jù)庫對改進(jìn)算法的測試

3.2.1改進(jìn)算法測試原理

通過選取一組已知聚類數(shù)目和聚類成員的數(shù)據(jù),利用 K-means算法以及改進(jìn)算法分別對該組數(shù)據(jù)進(jìn)行聚類,比較各自聚類結(jié)果,并與實(shí)際聚類效果進(jìn)行比較,以評價改進(jìn)方法的優(yōu)劣。由于選擇的是固定聚類數(shù)目的數(shù)據(jù),因而主要的比較對象是每個分類中所含元組的數(shù)量。

3.2.2測試數(shù)據(jù)集的選取

驗(yàn)證算法的優(yōu)劣,通常選擇UCI數(shù)據(jù)集里的數(shù)據(jù),在這里選取一個用來做聚類分析測試的數(shù)據(jù)集Iris[10],此數(shù)據(jù)集共含有150個樣本,以下是Iris測試集數(shù)據(jù)分類。

表1　Iris測試集數(shù)據(jù)分類

3.2.3測試結(jié)果對比

(1)測試結(jié)果的評價方法。此數(shù)據(jù)集可分成 3 類,每類的元組數(shù)量是 50 個,對測試結(jié)果優(yōu)劣的評價主要的依據(jù)就是聚類得到的每一類中含有正確元組的比例,聚類的正確率越高,則模型效果越好。設(shè)n是數(shù)據(jù)集中所有樣本個數(shù),m表示用聚類得到的正確樣本個數(shù),正確率a=m/n×100%,現(xiàn)在分別利用傳統(tǒng)的K-means方法和改進(jìn)的混合聚類算法對該數(shù)據(jù)集進(jìn)行聚類,表2是數(shù)據(jù)集的部分?jǐn)?shù)據(jù)。

表2　Iris數(shù)據(jù)集部分?jǐn)?shù)據(jù)

(2)傳統(tǒng)K-means方法聚類測試。利用K-means方法將聚類數(shù)目設(shè)定為3,初始聚類中心由系統(tǒng)隨機(jī)生成如表3所示。

表3　K-means 聚類初始聚類中心

每個聚類中的案例數(shù)為39、50、61;通過輸出的結(jié)果分析K-means方法聚類得到每一類中樣本正確的個數(shù)為48、50、37,樣本正確分類的比例a1=135/150×100%=90%。

(3)改進(jìn)聚類算法聚類測試。

表4是改進(jìn)聚類算法得到的初始聚類中心,最終得到的每個分類中樣本數(shù),分別為為57、50、43。通過輸出的結(jié)果分析得到改進(jìn)聚類算法得到每一類中樣本正確的個數(shù)為49、50、42,樣本正確分類的比例a1=135/150×100%=94%。

表4　改進(jìn)算法初始聚類中心

3.2.4混合聚類算法測試結(jié)果評價

在 UCI數(shù)據(jù)集上的實(shí)驗(yàn)測試結(jié)果表明,實(shí)際每個分類中包含 50 個樣本,混合聚類算法在每個分類中包含的樣本數(shù)量更接近實(shí)際,且該算法使更多的個體樣本被正確地分配到應(yīng)有的類別中,即更高的樣本聚類準(zhǔn)確率。由此可得,改進(jìn)后的混合聚類算法能動態(tài)地自動停止聚類,并能獲得更好地聚類效果,對數(shù)據(jù)集有更好的適應(yīng)性。

4混合聚類算法應(yīng)用實(shí)證研究

4.1　數(shù)據(jù)的處理分析

為了對改進(jìn)的混合聚類算法在客戶細(xì)分管理中的應(yīng)用進(jìn)行說明,本文選取某汽車銷售公司的客戶信息數(shù)據(jù)作為數(shù)據(jù)源。數(shù)據(jù)集包含了2012年2月11日至2014年12月28日的共計540 753條記錄。

(1)客戶細(xì)分系統(tǒng)體系結(jié)構(gòu)。結(jié)合汽車行業(yè)[11]的特點(diǎn),本文將客戶細(xì)分系統(tǒng)分為數(shù)據(jù)獲取、數(shù)據(jù)存儲和數(shù)據(jù)應(yīng)用3層。系統(tǒng)體系結(jié)構(gòu)如圖1所示。

圖1　客戶細(xì)分系統(tǒng)的體系結(jié)構(gòu)圖

(2)數(shù)據(jù)處理及聚類過程實(shí)現(xiàn)。通過對數(shù)據(jù)進(jìn)行收取、清洗、轉(zhuǎn)換、加載等的數(shù)據(jù)獲取層實(shí)現(xiàn)之后,根據(jù)數(shù)據(jù)源的情況構(gòu)建事實(shí)表,然后以事實(shí)表為中心,構(gòu)建關(guān)聯(lián)的維表,實(shí)現(xiàn)數(shù)據(jù)存儲層的實(shí)現(xiàn),最后通過數(shù)據(jù)清理、數(shù)據(jù)集成和變換、數(shù)據(jù)規(guī)約的數(shù)據(jù)預(yù)處理過程對數(shù)據(jù)進(jìn)行增強(qiáng)處理,對客戶信息進(jìn)行初步整理。本文以聚類個數(shù)k=3為例對聚類結(jié)果進(jìn)行描述,采用本文所提改進(jìn)的混合聚類算法,可得到如表5和表6所示的結(jié)果。

表5　聚類中心

表6　聚類的結(jié)果

如表6所示,通過聚類對樣本集中的每條數(shù)據(jù)標(biāo)定了其所屬的類別,由此可得到表7的聚類細(xì)分結(jié)果。

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

4.2　細(xì)分結(jié)果策略

從以上得出的3類客戶可看出,汽車銷售公司的的客戶群特征[12]存在明顯的差異,公司要想實(shí)施有效的營銷策略,最大限度地增加業(yè)務(wù)利潤,必須能夠準(zhǔn)確抓住不同特征客戶的行為特點(diǎn)[13],進(jìn)而制定針對性營銷策略。例如針對第一類客戶新建立家庭一族,可考慮對其實(shí)行交叉銷售,與醫(yī)院及超市或其他服務(wù)部門建立相應(yīng)的合作方案以促進(jìn)銷售。對第二類未婚大齡青年客戶一族,其對汽車的要求更多地體現(xiàn)在外形上,期望所購買的這輛車能向周圍人顯示自身的個性和情趣,所以外形時尚、色彩鮮艷的個性化小車將會受到這類客戶的青睞。對第三類家庭穩(wěn)定型一族,公司也可實(shí)行一定的交叉銷售,例如與學(xué)校合作推出的名?？?課程培訓(xùn)卡等套餐銷售策略。同時由于這類客戶擁有大量社會資源,穩(wěn)定性高,因此需要大力加強(qiáng)服務(wù)營銷,并著力培養(yǎng)此類客戶的忠誠度,實(shí)現(xiàn)客戶轉(zhuǎn)介紹,挖掘客戶背后的潛在客戶資源。

5結(jié)束語

聚類算法在客戶細(xì)分管理中有著廣泛的應(yīng)用。文章提出的基于K-means 和凝聚層次聚類的混合聚類算法能夠更快速,有效地實(shí)現(xiàn)客戶聚類,提高聚類準(zhǔn)確率和聚類精度,為公司提供科學(xué)有效的客戶細(xì)分解決方案,提高客戶細(xì)分的科學(xué)性和準(zhǔn)確性。

參考文獻(xiàn)

[1]Almeida J,Barbosa L,Ls A,et al.Improving hierarchical cluster analysis:a new method with outlier detection and automatic clustering[J].Chemometrics and Intelligent Laboratory Systems,2010,87(2):208-217.

[2]Hang Guoyan,Zhang Dongmei,Ren Jiadong,et al.A hierarchical clustering algorithm based on K-means with constraints[C].Taiwan:Proceding of the 4th International Conference on Innovative Computing,Information and Control (1C1C1C),IEEE Computer Society,2011.

[3]張建輝.K-means聚類算法研究及應(yīng)用[D].武漢:武漢理工大學(xué),2007.

[4]彭俊松.汽車行業(yè)銷售商業(yè)務(wù)管理系統(tǒng)[M].北京:電子工業(yè)出版社,2010.

[5]閆相斌,李一軍,葉強(qiáng).基于購買行為的客戶分類方法研究[J].計算機(jī)集成制造系統(tǒng),2005,11(12):1679-1774.

[6]周濤,陸惠玲.數(shù)據(jù)挖掘中聚類算法研究進(jìn)展[J].計算機(jī)工程與應(yīng)用,2012,48(12):100-111.

[7]Guha S,Rastogl R,Shim K.CURE:an efficient clustering algoritbm for large database[J].Information Systems,2010,26(1):35-58.

[8]Sid L,Mounira T.Divisive hierarchical K means[C].Hong Kong:International Conference on Computational Intelligence for Modeling Control and Automation,2012.

[9]Q1an W N,Zhou A Y.Analyzing popular clustering algorithms from different viewpoints[J].Journal of Software,2009,13(8):1382-1394.

[10]趙作為.基于SOM的4S店客戶細(xì)分及變化挖掘研究[D].大連:大連理工大學(xué),2013.

[11]曾小青.基于消費(fèi)數(shù)據(jù)挖掘的多指標(biāo)客戶細(xì)分新方法[J].計算機(jī)應(yīng)用研究,2013,30(10):2944-2947.

[12]李鑫鑫.聚類算法在電子商務(wù)客戶細(xì)分中的應(yīng)用研究[D].青島:中國海洋大學(xué),2012.

作者簡介:王虹(1990—),女,碩士研究生。研究方向:大數(shù)據(jù),數(shù)據(jù)挖掘與數(shù)據(jù)分析。孫紅(1964—),女,副教授。研究方向:計算機(jī)網(wǎng)絡(luò)通信與云計算等。

基金項目:國家自然科學(xué)基金資助項目(61170277;61472256);上海市教委科研創(chuàng)新重點(diǎn)基金資助項目(12zz137);滬江基金資助項目(C14002)。

收稿日期:2015- 04- 29

中圖分類號TP301.6

文獻(xiàn)標(biāo)識碼A

文章編號1007-7820(2016)01-029-04

doi:10.16180/j.cnki.issn1007-7820.2016.01.008