基于变异系数的双聚类算法及其在电信客户细分的应用研究

林　勤　薛　云　杨柏高

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)。林勤，助理实验师，主研领域：数据挖掘，并行计算。薛云，副教授。杨柏高，本科。