随着大数据时代到来，3G网络建设和商用不断深入，电信业正从服务经济向体验经济转型，移动网络运营商之间的竞争也已从市场竞争转向服务竞争.保障网络通信质量、提升网络服务质量是运营商掌握竞争先机所必须考虑的问题.

Reicheld的调查报告显示，每增加5%的客户保持率，行业就会增加25%~95%的平均利润率^[1].因此，如何为客户群体提供优质服务，保持客户，避免客户流失，是各大企业的核心工作任务.为了准确地了解客户、分析客户、服务客户，企业首先要正确地划分客户群体.通过客户细分, 运营商能更好地识别客户群体, 对不同的客户, 采取不一样的客户保持策略, 达到最优化配置与利用资源，最大化获取利润的目的.

1 相关工作

张巍等^[2]从电信业务出发，按用户行为、用户类型、用户投诉等多个角度细分用户，探讨了移动网络语音业务用户体验的建模问题，给出了建模方案.徐猛^[3]探讨了面向用户体验的多QoS约束多流程调度算法，目的是满足尽可能多的用户QoS需求，但未涉及基于用户体验的协同建模问题.周天圆^[4]将决策树、模糊神经网络等算法用来分析电信业务的用户体验，研究结果用现网数据进行了验证，但未对具体建模过程进行描述.郑茜茜^[5]将客户数据根据某个给定的阈值划分群体，阈值直接决定了划分效果的好坏.通常阈值的确定需要经过专家仔细研究和分析.但是，在不同地区和不同人文地理环境下，客户群体的划分往往不同，传统的通过某种阈值的统计分析法很难做到准确地细分客户群体.

在运用数据挖掘方法细分客户群体中，常用的是基于划分的K-means聚类^[6].K-means聚类简单、易行，时间复杂度是O(tKmn)^[7]，其中t为迭代次数，K为类别数，m为样本维数，n为样本数，K-means聚类的时间复杂度和样本数成线性关系，因此可用于大数据的客户细分.王扶东等^[8]从客户生命周期价值方面考虑，提出了基于加权的K-means客户细分方法.但是，K-means聚类算法对初始聚类中心的选取依赖性极大，较差的初始聚类中心常导致算法陷入局部最优解^[6].

国内外许多研究集中于降低初始聚类簇中心的选择对算法结果的影响，杜巍等^[9]研究初始聚类中心的选取方法，提出了一个改进的K-means聚类方法，并应用于客户细分，获得了一些有益的结果.Md.SohrabMahmud等^[10]基于平均权重，提出了一个初始化聚类中心的方法.王令剑等^[11]将聚类方法和时间序列分析结合，并用于入侵检测中，通过实验验证了该方法的有效性.曹永春^[12]将改进的人工蜂群算法和K-means迭代相结合，降低了初始聚类中心的依赖性和陷入局部最优解的可能性.胡伟^[13]提出了一个层次聚类的思路，通过从上往下地构造一棵K均值聚类树，最终在叶子节点达到聚类结果.高灵渲等^[14]在K-means算法的欧氏距离及中心点判定阶段改进, 提升了K-means算法的效率.易倩等^[15]将马氏距离与K-means算法相结合, 并在目标函数中增加变量权重因子和协方差矩阵调节因子，提高了聚类精度.杜红乐等^[16]针对数据之间距离不均匀的问题，研究了模糊C均值聚类问题及其应用.

上述研究在一定程度上对初始聚类中心的确定有所帮助，但尚未有效解决K-means算法依赖于初始聚类中心的问题.

除了初始聚类中心的影响外，K-means算法对噪声点和离群点很敏感.廖松有等^[17]通过引入模糊熵约束，使用了模糊C均值聚类算法，在一定程度上能抑制噪声数据对聚类的影响.卢鹏丽等^[18]以密度敏感距离作为相似性测度，结合近邻传播聚类算法和谱聚类算法，提出了一种密度敏感的层次化聚类算法.潘章明^[19]基于分治策略，提出了一种改进的共享近邻聚类算法.这些算法都是从密度的角度研究噪声点和离群点.

国内外学者针对K-means聚类方法及其应用，开展了一系列研究，取得了许多成果，但下列问题尚未得到有效解决.

(1) 初始聚类中心选取：初始聚类中心选取不合适，会导致局部最优解；

(2) 聚类个数K：有时用户需要聚类成不同个数的簇.同一个数据集，从不同的角度分析将需要不同的聚类个数，产生不同的聚类效果，比如评价可分为好、中、及格、差，也可分为很好、好、中、及格、差、极差等；

(3) 聚类效果：由于聚类受初始簇中心选取和K值影响，聚类结果往往难以保证.

为此，本文提出可调多趟聚类方法，第1趟通过引入一个较大的K值，采用K-means聚类算法，获得K个簇，为第2趟聚类的簇数及簇中心初始值选择提供参考.由此，用户可以根据实际情况，选择合适的簇数及初始簇中心，通过第2趟聚类获取较好的挖掘结果.

2 K-means聚类

K-means聚类算法是1967年由MacQueen首次提出的一种经典划分聚类方法.K-means算法以K为参数，把n个数据对象的集合分为K个簇，使得簇内对象的相似度高，簇间对象的相似度低.簇的相似度是关于簇中对象的均值度量，如质心、重心、距离等.本文采用欧氏距离计算.

K-means算法流程如下：首先，随机地选择K个对象，每个对象代表一个簇的初始簇中心.对剩余的每个对象，根据其与各个簇中心的距离，将它指派到最相似的簇.然后计算每个簇的新均值.这个过程不断重复，直到准则函数收敛.

定义1^[6] 平方误差准则函数.设x是多维空间中的点，表示给定对象：m_i是簇C_i的簇中心，d()表示两个对象之间的距离(通常采用欧氏距离)，平方误差和SSE定义为：

$ {\rm{SSE = }}\sum\limits_{i = 1}^k {\sum\limits_{x \in {C_i}} {d{{\left( {{m_i}, x} \right)}^2}} } . $

(1)

基于距离的K-means聚类算法存在以下不足：算法需要预先给定簇个数K；算法对初始簇中心值选取依赖性极大，常陷入局部最优；在数据量小的情况下，算法对离群点和噪声很敏感；算法不能用于发现非凸形状的簇；算法只能用于数值数据.

K-means聚类算法需要预先给定簇个数，这一特点限制了对基于客户细分的用户业务分析.有时，用户希望从多个角度对数据进行分析，希望将客户细分为不同的级别，以便进行不同级别上的决策.例如某企业决策层希望把客户细分为潜在流失客户、一般客户和VIP客户3个类别；而具体业务人员希望把客户细分为潜在流失客户、可挽留客户、一般客户、可升级客户和VIP客户5个类别.这时，K-means聚类方法需要开展两次完全无关的挖掘，并且在大数据下，难以保证挖掘的效果.针对K-means存在的不足，并兼顾不同用户的需求，本文在进行大量数据挖掘实践的基础上，提出了一个可调的多趟K-means聚类方法.

3 可调的多趟K-means聚类

本文的多趟K-means聚类分为两趟，第1趟确定初始簇，为用户选择K值和初始簇中心提供依据与参考.第2趟为可定制的聚类.其体系结构如图 1所示.

3.1 初始聚类

层次聚类分为自顶向下和自底向上两种.本文提出的聚类算法采用自底向上的方式，初始聚类从用户期望分类的簇数出发.聚类过程如下：

(1) 获取电信业务数据集D，对数据进行预处理；

(2) 根据用户实际需要，获取聚类簇数K₀(K₀为整数)；

(3) 依据专家知识、背景和用户需求将簇数K₀放大到聚类簇数K₁(${K_1} \gg {K_0}$，K₁为大于K₀的整数)；

(4) 从D中任选K₁个数据对象作为初始聚类中心；

(5) 对数据集D做K₁-means聚类；

(6) 生成大约K₁个聚类簇.

初始聚类时，由于选取了多个聚类中心，随机性强，覆盖面广，能够在一定程度上避免选取不合适的聚类中心，导致聚类效果进入局部最优.

初始聚类后，可以用误差平方和、抱团性和分离性等评价指标分析是否有离群簇.

3.2 可定制的K-means聚类

可定制的K-means聚类，可通过用户需求、反复实验及历史经验，用多个K值调整目标聚类个数.例如可设置聚类个数为K-2、K-1、K、K+1、K+2，然后比较哪组聚类的效果较优，根据实际需要作出合适的选择.

第2趟聚类在第1趟聚类基础上，选取K个值作为第2趟初始簇中心，它们是距离最远的K个第1趟的簇中心，以避免聚类中心在迭代过程中重合，导致局部最优解.第2趟聚类过程如下：

(1) 获取第1趟聚类中心C₁、C₂、…、C_K1；

(2) 计算任意两个簇中心C_i与C_j之间的距离DIST_ij；

(3) 取K个不同的C_i值(i=1, 2, …, K)，计算

$ \max \sum\limits_{i = 1}^K {\sum\limits_{j = 1}^{K_1} {\left[{\left. {{\rm{DIST}}\left( {{C_i}, {C_j}} \right)} \right)} \right]} } ; $

(2)

(4) 将满足式(2)的K个C_i作为第2趟的初始聚类中心；

(5) 对数据集D做K-means聚类；

(6) 最后根据聚类结果合并簇，得到目标划分.

在聚类过程中，满足式(2)的K个不同的C_i值，确保了K个初始簇中心两两之间的距离较大，避免聚类中心在迭代过程中重合.

3.3 可调的多趟聚类效果

可调的多趟聚类效果如图 2所示.第1趟产生K₁个簇，第2趟用户可定制K个簇.在图 2中，S_i(i= 1, 2, …, n)为第1趟聚类的簇；C_i与T_i分别为用户根据不同需求定制的簇.

3.4 可调多趟聚类算法

本文的可调多趟聚类算法如下.设用户需要划分K₀个簇，数据集为X={x₁，x₂，x₃，…，x_i，…，x_n}，其中x_i是一条数据记录，算法的步骤如下：

(1) 设定K₁个初始聚类中心，K₁远大于K₀，可以取K₁ =5×K₀.

(2) 根据K₁个聚类中心，对X做K₁-means聚类，得到K₁个簇.

(3) 分析K₁个簇，判断是否有离群簇.如果有离群簇，在X中分离对应的离群簇数据.

(4) 假设除离群簇外有K₂个簇中心C={c₁，c₂，c₃，…，c_K2}.计算两两簇中心之间的距离.

(5) 计算$\max \sum\limits_{i = 1}^K {\sum\limits_{j = 1}^{K_2} {\left[{\left. {{\rm{DIST}}\left( {{C_i}, {C_j}} \right)} \right)} \right]} } $.

(6) 选择前K₀个不同的C_i，满足式(2)的要求，将C_i作为第2趟聚类的初始簇中心.

(7) 对数据集用K₀个C_i做K₀-means聚类.得到K₀个簇G={g₁，g₂，g₃，…，g_K0}.

(8) 将步骤7的聚类结果输出.

(9) 根据需要修改K₀值，即改变目标聚类个数，重复步骤6~8.

步骤8对得到的多组聚类结果进行对比和评估，根据实际情况选择合适的聚类结果.

算法流程如图 3所示.

使用可调的多趟K-means聚类能够排除离群簇，减少了初始聚类中心对聚类结果的影响，并能发现非凸形状的簇，最后还能够根据实际需要调整聚类个数.本文的方法适合于用户对聚类数及聚类结果都比较模糊，可为用户提供多种聚类效果的选择.

3.5 算法评估

聚类算法能够使簇内具有较高的相似度，而簇与簇之间的相似度较低.为了分析聚类的效果，需要从簇中对象的“相似性”和不同簇之间对象的“相异性”两方面考虑，可按定义1的评价方法来衡量算法的有效性.

平方误差和，用于评价簇的集中程度.小的平方误差和说明簇中的对象集中度高.平方误差和的计算参见定义1.

分离性，即任意两个簇中心的距离中的最小值^[13].分离性值越大，簇与簇之间相差越大.分离性的定义如下：

定义2^[13] 分离性.设C_i为簇i(i=1, 2, …, k)的簇中心，分离性定义为

$ F = \mathop {\min }\limits_{\begin{array}{*{20}{c}} {i = 1,2, \cdots ,k}\\ {j = 1,2, \cdots ,k} \end{array}} \left( {{c_i} - {c_j}} \right) $

(3)

4 结果与讨论 4.1 实验数据

为了验证可调多趟K-means聚类方法在客户细分中的可行性和有效性，本文用某电信企业的移动用户数据进行了实验，并对实验结果做了分析和总结.

本实验数据采用电信客户的通话数据，根据客户的通话质量情况细分客户.实验中把客户分为5个等级，通信质量好、通信质量较好、通信质量中、通信质量较差、通信质量差，分别代表 5个等级的服务情况.对于通信质量较差与差的客户，移动运营商应该着重改善该客户群体的服务质量，防止客户流失；对于通信质量好及较好的客户，移动运营商可以有针对性地为他们提供额外的服务，引导该客户群体提升消费水平.

客户的通话数据来源于测量报告，如表 1所示.数据中包括客户标识、上下行接收电平、接收质量、时间提前量等反映网络质量水平的数据.在GSM网络^[20-21]中误码率(RxQual)和上、下行电平(Rxlev)是影响通话质量的重要因素.误码率决定了通话时的语音质量.误码率也称作质量，其值越小，语音质量越好.上、下行电平反应手机的信号好坏.当上、下行电平太低时，可能会导致手机信号弱，无法进行电话的正常拨打和接听.当上、下行电平不平衡时，也可能会导致频繁的掉话.

实验环境采用数学软件Matlab，实验选取了测量报告中与网络质量相关的11条属性做分析，构成了8组数据集，数据集的数据量从11322条到82665条.

以最后一组数据为例，实验使用可调多趟K-means聚类方法，对82665条数据进行聚类.由于需要把客户分为5个等级，所以设定第1次聚类个数为20倍，即100个.聚类后分析，得到1个离群簇，离群簇中包含数据609条.排除这609条离群数据后进行第2次聚类，对99个簇中心施行可定制的聚类.经过实验对比和用户实际需求，决定第2次聚类个数为5个.这样定制后聚类簇数为5个簇，这5个簇分别对应通信质量好、通信质量较好、通信质量中、通信质量较差和通信质量差，合并后每个簇的数据量分别是40 869、26 300、8 879、2 930、3 078.

实验中分别记录了11组可调多趟K-means聚类算法和基于密度的DBSCAN ^[4]算法的运算时间，如图 4所示.

从图 4可以看出，由于初始值的选取有一定随机性，本文提出的可调多趟K-means聚类算法达到收敛时的迭代次数存在一定的不确定性，算法的执行时间有一定的波动.当数据量达到一定规模时，多趟K-means聚类算法的效率远远高于传统的DBSCAN算法.

由实验结果可知，通信质量好的客户数有40 869个，通信质量差的客户数有3 078个，说明当前环境下，通信质量总体情况令人满意.但是移动运营商仍需要分析通信质量差的3 078位客户与通信质量较差的2 930位客户，找出通信质量差的原因并及时进行处理，以尽量降低客户流失.

4.2 聚类效果的对比

实验将传统K-means算法和本文提出的可调多趟K-means的聚类效果进行比较，从误差平方和与分离性两个评价指标进行对比，结果如图 5和图 6所示.

从图 5中可以看出，本文提出的可调多趟K-means聚类算法效果在“相似性”方面略优于传统的K-means算法.由图 6可知，在“相异性”方面，可调多趟K-means聚类算法远远优于传统K-means算法.

从以上实验结果可知，本文提出的可调多趟K-means聚类算法能够有效地处理海量数据的挖掘问题，该聚类算法应用于电信领域的客户细分有效、可行.本文为电信运营商有效地细分客户提供了参考.

5 结束语

K-means是目前数据挖掘中常用的聚类方法，本文针对传统K-means方法的缺点，提出了一个可调的多趟K-means聚类方法，该方法能够在保留传统K-means聚类方法优点的基础上有效地改进K-means存在的不足，并能根据实际需要分析并调整聚类结果的个数.实验表明，该算法应用于电信数据分析及其客户细分有效、可行，下一步工作将探讨本文的方法在大数据挖掘中的应用.