基于變異系數的雙聚類算法及其在電信客戶細分的應用研究

林　勤　薛　云　楊柏高

1(廣東醫學院信息工程學院　廣東 東莞 523808)

2(華南師范大學物理與電信工程學院　廣東 廣州 510006)

?

基于變異系數的雙聚類算法及其在電信客戶細分的應用研究

林勤1薛云2楊柏高2

1(廣東醫學院信息工程學院廣東 東莞 523808)

2(華南師范大學物理與電信工程學院廣東 廣州 510006)

摘要針對傳統客戶價值細分方法不夠精細化的問題，提出一種基于變異系數的雙聚類算法。該算法選用了變異系數作為相似性度量，運用啟發式貪心策略，通過迭代增刪行列的方式挖掘出客戶消費記錄中局部消費行為相似的客戶群體。以某電信公司的電信客戶細分為實例，將所提算法與K均值(K-means)算法進行性能比較，實驗結果表明，所提算法具有更優的客戶細分能力和更強的客戶行為可解釋能力。因此，它更有助于指導企業制定差異化營銷策略。

關鍵詞變異系數客戶細分差異化營銷雙聚類K均值

ON VARIATION COEFFICIENT-BASED BICLUSTERING ALGORITHM AND ITS APPLICATION IN TELECOMMUNICATION CUSTOMER SEGMENTATION

Lin Qin1Xue Yun2Yang Baigao2

1(School of Information Engineering,Guangdong Medical College,Dongguan 523808,Guangdong,China)2(School of Physics and Telecommunication Engineering,South China Normal University,Guangzhou 510006,Guangdong,China)

AbstractTo improve the refinement degree of traditional customer value segmentation method, we proposed the variation coefficient-based biclustering algorithm. The algorithm selects the variation coefficient as the similarity measurement, applies the heuristic greedy strategy, and by the way of iterating the rows’ or columns’ insertion and deletion, the algorithm mines the customer groups with similar local consuming behaviours from their consumption records. Taking the telecommunication customers segmentation in a certain Telecom as the example, we compared the performances of the proposed algorithm with k-means clustering algorithm. Experimental result indicated that the proposed algorithm has better ability of customer segmentation and stronger interpretable ability on customer behaviours. Therefore, it is more conducive to guiding the enterprises to develop differentiated marketing strategies.

KeywordsVariation coefficientCustomer segmentationDifferentiated marketingBiclusteringK-means

0引言

近年來，隨著電信運營商網絡基礎設施間差距日益縮小，所涵蓋業務日趨同質，電信企業的發展模式逐步從以產品為中心的模式向以客戶為中心的模式轉變。精確識別和細分客戶市場，有助于電信企業合理配置企業資源，提高資源利用效率，降低運營成本；同時也有助于發現不同類別的客戶對服務的不同需求，為其提供個性化的服務，從而使運營商和客戶價值發揮到最大，實現電信企業和客戶之間的雙贏。因此探究精細的數據挖掘方法對客戶進行細分是目前數據挖掘應用的一個非常熱門且具有重要應用價值的研究課題[1]。

文獻[2-5]相繼提出并完善了客戶生命周期價值CLV(Customer Lifetime Value)和客戶生命周期利潤CLP(Customer Lifetime Profit)的概念和計算模型，先篩選與客戶的當前和潛在價值或者利潤相關的屬性，然后計算每一個客戶整個生命周期的凈利潤，最后運用閾值或者客戶價值矩陣對客戶進行細分。文獻[6-9]先根據RFM(Recency,Frequency,Monetary)模型或者其它的業務目標對消費數據進行屬性篩選，再分別運用粒子群優化的模糊C均值聚類算法PSO-FCM(Particle Swarm Optimization- Fuzzy C-Means)、自組織映射聚類算法SOM(Self-Organization Mapping)、K均值(K-Means)聚類算法對客戶進行分群。文獻[10]指出了上述兩種方法的不足，并引入了一種專門從客戶的消費記錄中挖掘出高端消費客戶群體的大均值子矩陣LAS(Large Average Submatrices)雙聚類算法，該方法在很大程度解決了建模和傳統聚類方法存在的缺陷。然而，在現實應用中客戶分群的目的并不僅僅限制于識別高價值客戶群體，很多時候還需要識別出具有一般性相似消費行為的客戶群體。

針對上述問題，本文提出了一種基于變異系數的雙聚類算法，該算法選用了一個用于衡量不同單位、平均值數據組之間離散程度的統計量——變異系數作為聚類的相似性度量，同時采用啟發式貪心策略，通過迭代增刪行列的方式在客戶消費記錄中挖掘出變異系數較小且規模較大的客戶群體。由于該算法所挖掘出來的客戶群體僅須在部分消費屬性的行為相似就可以聚集在一起。因此，類內客戶與消費屬性間具有更高的關聯性，這也使得聚類結果的可解釋性大大提高。此外，本文還將該算法與成熟應用于電信客戶細分的K-Means算法進行性能比較，結果表明該算法具有更高的聚類有效性和可解釋性。

1基本概念及定義

假設客戶的消費記錄可以看成一個m×n的實數矩陣A，矩陣的m行代表m個不同的客戶，n列代表n種不同的消費屬性。同時，定義實數陣A的行集X={x1,x2,…,xm}，列集Y={y1,y2,…,yn}。雙聚類是實數陣A的一個k×l子矩陣U，表示為：U=(I,J)，其中I={i1,i2,…,ik}是行集X的子集，J={j1,j2,…,jl}是列集Y的子集。

定義1變異系數假設實數矩陣U是實數陣A的一個k×l子矩陣，ui,j是矩陣U第i行第j列的元素。定義矩陣U的變異系數為矩陣U的方差除以均值，其數學表達式為：

(1)

變異系數是一個用來比較不同行子集、列子集以及尺寸的兩個或者多個子矩陣內元素值分布變異程度的重要指標。值越小代表該子矩陣的元素值比其他子矩陣的元素值的分布越集中，這也間接地說明了該矩陣內的客戶群體在各屬性上的消費行為更加地相似。

定義2容量閾值假設實數矩陣U是實數陣A的一個規模為k×l子矩陣，定義容量閾值α為子矩陣U的尺寸與實數矩陣A的尺寸的比值，其數學表達式為：

(2)

容量閾值是衡量雙聚類質量的另一個很重要的標準。由于容量閾值小會使得子矩陣的變異系數變得很小，但是這樣的雙聚類質量不高。所以在尋找雙聚類的過程中，除了考慮子矩陣的變異系數，還要考慮容量閾值的大小。

定義3Action(x,U)動作采用FLOC算法[11]在迭代優化雙聚類種子過程中把刪除或者增加一行或者一列操作都統一為動作Action(x,U)的定義。具體定義如下：在給定實數矩陣A的行(列)x與子矩陣U的情況下，如果行(列)x在子矩陣U中，那么動作Action(x,U)表示從子矩陣U中移除行(列) x；如果行(列)x不在子矩陣U中，那么動作Action(x,U)表示將行(列)x添加到子矩陣U中。

定義4動作序列operation在每次迭代優化每個雙聚類種子過程中必須對所有行或者列都執行Action(x,U)動作。采用FLOC算法[11]將所有Action(x,U)動作先后次序定義為動作序列。具體定義如下：對于任一給定的子矩陣U，其動作序列operation為一個大小為(m+n)的數組，數組里的每個元素代表著Action(x,U)動作所操作的某一行或者一列，動作序列operation主要用于存放動作執行的先后次序。

2基于變異系數的雙聚類算法描述

2.1雙聚類算法

雙聚類(Biclustering)術語最早于2000年見于Cheng等人[12]的基因表達數據分析之中。傳統聚類要求同類基因必須滿足在所有條件下的表達行為都要相似。但是，通常情況下，一些基因只在某些條件下有著非常相似的表達行為，而在另一些條件下它們的表達行為不相似甚至毫不相干。對比傳統聚類，雙聚類算法可以對數據矩陣的行和列同時進行聚類，把一些只在部分屬性下有著相似性質的對象聚在一起，在對對象進行聚類的同時也完成了對屬性的篩選，這使得它更容易處理數據中存在噪聲或缺失，以及確定屬性權重等問題。正因為這些優點，除了生物信息領域，雙聚類算法的思想也很快被應用于市場劃分[13]、文本挖掘[14]、協同過濾推薦系統[15]等領域。

2.2基于變異系數的雙聚類算法

算法的目的是在實數矩陣中挖掘出k個尺寸較大、變異系數較小的雙聚類。基本思想是首先隨機生成k個平均尺寸大于容量閾值的雙聚類種子；然后固定這些種子的行數和列數，以行列交替抽樣的方式粗略優化各個雙聚類種子；接著，順序執行動作序列里對k個種子進行每個增或刪一行或一列的動作，每次動作只賦予使得變異系數下降得最快的雙聚類種子，不斷循環迭代直至k個雙聚類種子的平均尺寸小于容量閾值為止。最后，為了避免雙聚類的尺寸小有利于變異系數下降而造成以上迭代偏向于刪動作的情況，重復以上順序執行動作序列中的增操作，每次操作只賦予使得變異系數下降得最快的雙聚類種子，不斷循環迭代直至k個雙聚類種子的平均變異系數值不再變化為止。

定理1動作序列operation里的某一動作Action(x,U)對所有的種子執行操作后，該動作只賦予執行后變異系數下降得最快的雙聚類種子，其他雙聚類種子不執行該動作。假如該動作執行后，所有雙聚類種子的變異系數都沒有下降，則所有雙聚類都不執行該動作。

算法1基于變異系數的雙聚類算法

輸入：矩陣A， 聚類個數k，平均容量閾值threshold1，threshold2

輸出：k個滿足條件的聚類

初始化：隨機產生k個種子的行數和列數，且k個種子的平均容量閾值不小于threshold1

方法：LCVS_SearchForBCs()

1) Bcseed = RoughOptimize( ) ；

//初略優化種子，使得k個種子的變異系數不會太大，加速收斂

2) while(avg(Bcseed.size)/(m*n))> threshold2)//重復順序執

//行動作序列里的動作，直到k個種子的平均容量閾值小于threshold2

3) 隨機產生一個大小為(m+n)的動作序列operation，用于存放行列操作順序；

4) for i = 1 to (m+n)

//順序執行動作序列

5) for num = 1 to k//找出該動作執行后變異系數下降最大的種

//子，將動作賦予該種子，其他保持不變

6) decv(num) = Action(operation(i, Bcseed(num));

//對第num個種子執行動作，返回該種子執行動作后變異系數下降量

7) decv(max) = max(decv)；

//找出下降量最大的種子

8) 把該動作賦予序號為max的種子，修改其相應的信息，其余種子保持不變

9) end for；

10) end for；

11) end while；

12) while(avg(currBcseed.cv) ~= avg(preBcseed.cv))

//重復順序執行動作序列里的增一行或一列的動作，直到k個種子的平

//均變異系數不再變化為止

13) 重復3)到9)過程中增加一行或者一列過程，刪除的過程忽略。

總的來說，算法包括了三個階段。第一階段是步驟1)，對k個種子進行了粗略地優化，加快后面迭代的收斂速度；第二個階段是步驟2)到11)，運用定理1對k個種子進行了自適應地增或刪行列操作，同時控制平均的尺寸，使得k個種子的變異系數比較小，尺寸也不會太小；第三個階段是12)到13)，由于變異系數值下降往往會傾向于刪除操作，為了避免第二階段過于側重刪操作，這個階段只執行動作序列中的增操作。算法的全過程和第一階段的流程如圖1、圖2所示。

圖1　LCVS雙聚類算法總流程圖　圖2　粗略優化種子的流程圖

3基于變異系數的雙聚類算法的應用

3.1數據描述和預處理

本文實驗數據來源于第十屆亞太知識發現與數據挖掘國際會議提供的電信客戶數據。數據內容包括月平均消費額、月平均通話時長、國際通話分鐘數等225個屬性。經統計，該數據缺失數據多，數據取值范圍廣，數據取值類型多樣，本文通過數據清洗，選用了其中2 000條記錄，74個與消費相關的屬性。

由于算法是對子矩陣內所有的消費屬性進行變異系數的計算，而各個消費屬性可能在單位或者平均數上存在差異。為了避免這些差異對算法性能的影響，本文將原始的消費記錄按照式(3)進行標準化處理：

(3)

3.2實驗結果分析

在實驗中，設置雙聚類算法的參數為：聚類個數k=6，平均容量閾值threshold1=0.05，threshold2=0.05。編程和運行的平臺是Matlab2010。算法運行的結果如表1所示。

表1　6個聚類的分群結果

首先，從整體分析。據表1可發現算法所挖掘出來的這6個類的變異系數都比較小，這說明各個客戶群體在各自類內消費業務上的消費行為都很相似。同時，從各類分群的列數可以看出，對比于傳統的聚類算法，算法挖掘出來的客戶群體的消費屬性和客戶之間的關聯性、可解釋性更高。

其次，本文還細致地分析每個分群的典型特征，對各個分群進行描述，并根據各個分群的特點給出了相應的服務方式和營銷策略的建議，具體如表2所示。由于篇幅關系，本文只對其中第5分群展開詳細地解析。

客戶分群5：客戶的人數是284，約占整體客戶的1/10，消費屬性是16個，類內的客戶在各消費屬性的平均消費額與全體客戶在對應屬性的平均消費額相比較高，倍數的范圍是2.3968~3.0833，其中比較核心的消費業務是近6個月平均移動通話分鐘數、近6個月國外平均忙時通話分鐘數、近6個月平均外部網通話次數、近6個月平均移動通話次數、近6個月平均主叫不同號碼數、近6個月平均國外通話次數。鑒于該類用戶的核心消費業務比較集中于外網、國外通話等商旅業務、消費額高、相對于其他5個客戶群體對企業整體的利潤貢獻最大，故可以將其定義于商旅型高價值客戶群體。可以采用重點維系的服務方式提高客戶的忠誠度和信任度。同時可以采取積極為其定制一些與商旅相關的個性化優惠套餐、創新服務產品的營銷策略來達到提高服務質量，提升企業的利潤。例如漫游優惠套餐，國際通話優惠套餐，飛機、酒店預訂優惠等商旅創新產品等。

表2　6個雙聚類結果的分析和營銷方案

續表2

4聚類有效性驗證

為了進一步驗證基于變異系數的雙聚類算法的統計意義，本文將該算法與已經成熟應用于電信客戶細分的K-Means算法進行聚類有效性的比較。其中基于變異系數的雙聚類算法沿用以上的參數設置和實驗結果，K-Means算法的參數設置是聚類個數k為6個，迭代次數為100次，相似性度量選用歐氏距離，開始預分類選用隨機種子，編程和運行的平臺也選用Matlab2010。

采用文獻[10]提出的分離度，緊密度，PA指標來對兩個算法的有效性進行分析，具體公式如下所示：

定義5分離度V[10]定義各類中心與數據集中心點的距離平方(只挑選該雙聚類所涉及到的屬性來計算距離)，再除以屬性數目之后的加權和為類間分離度，其數學表達式為：

(4)

其中，Ci指各類中心，C為數據中心，pi表示第i個聚類中屬性的個數，NC表示類的數目。

V的值越大，說明聚類的結果類與類之間的差距越大，類與類之間的區分度越高。 反之，則說明聚類的結果類與類之間的差距越小，類與類之間的區分度越低。

定義6緊密度D[10]定義類中各點與類中心的最大距離平方和為類內緊密度，其數學表達式為：

(5)

其中，x指各類內的每個對象，Ci指各類中心。

D的值越大，說明聚類的結果各類類內的對象越相似，反之則說明聚類的結果各類類內的對象越相異。

定義7PA指標[10]定義分離度除以緊密度,再除以聚類數目為PA指標，其數學表達式為：

(6)

其中，Ci指各類中心，C為數據中心，pi表示第i個聚類中屬性的個數，x指各類內的每個對象，NC表示類的數目。

PA指標的值越大，說明聚類的結果類間的分離度越大，類內的緊密度越小，聚類的綜合效果越好。反之則說明聚類的結果類間的分離度越小，類內的緊密度越大，聚類的綜合效果越差。

所得的結果如表3所示。從表3可以看出基于變異系數的雙聚類算法所得結果的分離度V的值比K-Means算法大，緊密度D的值僅為K-Means算法的四分之一，PA指標接近K-Means算法的兩倍。這說明對比K-Means算法，該算法所得的結果類與類之間的區分度比較高，類內的對象更加相似，聚類的綜合效果更好。

表3　K-means算法和基于變異系數的雙聚類算法的聚類有效性對比

5結語

目前電信行業正以前所未有的速度，成為發展最快的行業之一。但是同時，電信行業間的競爭也越趨加劇。精確地識別、細分客戶市場，有助于指導電信企業優化資源配置，制定和設計個性化，差異化的創新產品，提升企業在行業中的競爭力。這已成為電信行業內的一個共識。本文分析了傳統客戶細分方法存在的缺陷，并在此基礎上提出了一種基于變異系數的雙聚類方法，該方法在客戶樣本和消費屬性兩個維度上對消費記錄進行雙向聚類，可以挖掘出在部分消費屬性上行為比較相似的客戶群體。另外，結合某電信公司的客戶消費數據，本文將該算法與K-Means算法進行聚類有效性的比較，實驗結果表明，該算法的聚類結果具有更好的客戶細分能力和更強的客戶行為可解釋能力，更有利于企業進一步實施差異化營銷。然而，由于現在電信客戶消費記錄急劇增長，當面臨海量數據處理的時候，該算法還是會遇到單機內存和計算能力不足的瓶頸。因此如何對該算法進行并行優化設計，這將是后續亟待解決的問題。

參考文獻

[1] Hung S Y,Yen D C,Wang H Y.Applying datamining to tele-com churn management[J].Expert Systems with Applications,2006,31(3):515-524.

[2] Jackson B B.Build Customer Relationships That Last[J].Harvard Business Review,1985,63(10):120-128.

[3] Berger P D,Nasr N I.Customer lifetime value:marketing models and applications[J].Journal of interactive marketing,1998,12(1):17-30.

[4] 陳明亮.客戶保持與生命周期研究[D].西安:西安交通大學,2001.

[5] 齊佳音.企業客戶價值研究[D].西安:西安交通大學,2002.

[6] 張煥國,呂莎,李瑋.C均值算法的電信客戶細分研究[J].計算機仿真,2011,28(6):185-188.

[7] D Urso P,De Giovanni L.Temporal self-organizing maps for telecommunications market segmentation[J].Neurocomputing,2008,71(13):2880-2892.

[8] Ye L,Qiuru C,Haixu X,et al.Telecom customer segmentation with K-means clustering[C]//Computer Science & Education (ICCSE),2012 7th International Conference on IEEE.Melbourne.VIC:IEEE Computer Society,2012:648-651.

[9] 曾小青,徐秦,張丹,等.基于消費數據挖掘的多指標客戶細分新方法[J].計算機應用研究,2013,30(10):2944-2947.

[10] 林勤,薛云.一種雙聚類算法在電信高價值客戶細分的應用研究[J].計算機應用,2014,34(6):1807-1811.

[11] Jiong Yang,Wei Wang,Haixun Wang,et al.Enhanced Biclustering on Expression Data[C]//Proceedings of the 3rd IEEE Conference on Bioinformatics and Bioengineering.Maryland:IEEE Computer Society,2003:321-327.

[12] Cheng Yizong,George M Church.Biclustering of expression data[C]//Proceeding of the 8th International Conference on Intelligent Systems for Molecular Biology.New York:ACM press,2000:93-103.

[13] Dhillon L S.Co-Clustering Documents and Words Using Bipartite Spectral Graph Partitioning[C]//Proceeding of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.San Francisco:ACM press.2001:269-274.

[14] Banerjee A,Dhillon L,Ghosh J,et al.A Generalized Maximum Entropy Approach to Bregman Co-clustering and Matrix Approximation[J].Journal of Machine Learning Research,2007,8(12):509-514.

[15] Su X,Khoshgoftaar T M.A Survey of Collaborative Filtering Techniques[J].Advances in Artificial Intelligence,2009(4):1-19.

中圖分類號TP391

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.02.052

收稿日期：2014-06-23。國家自然科學基金項目(71102146)；廣東醫學院面上基金項目(XK1330)；廣東醫學院青年基金項目(XQ1224)。林勤，助理實驗師，主研領域：數據挖掘，并行計算。薛云，副教授。楊柏高，本科。