基于混沌PSO和K均值算法的移动用户分类

摘 要：为了克服经典K-Means算法随机选择初始数据中心而易陷入局部最优解和聚类结果的不确定性问题，提出了一种基于粒子群和K-Means算法的改进聚类算法以实现移动用户分类。首先，定义了数据对象密度并采用改进的普里姆算法初始化聚类中心，然后，将此聚类中心用于初始化粒子位置，采用混沌粒子群算法寻优获得最优解作为最终的聚类中心，最后，采用经典K-Means算法根据最终聚类中心进行聚类。仿真实验表明文中方法能正确地实现移动用户分类，并具有较强的全局寻优能力和较快的收敛速度，弥补了经典K-Means方法的不足，具有较强的现实意义。

关键词：粒子群 K均值 分类 聚类

中图分类号：TP391 文献标识码：A

1.引言

移动用户分类是指根据用户的属性、偏好、需求以及价值等因素，采用相关技术对用户进行分类，并根据分类结果为用户进行量身定做相应的产品和服务[]。

传统的对移动用户进行分类的方法主要有经验细分法和数理统计法，经验细分法具有主观性强的缺点，而数理统计法的分类优劣很大程度上取决于分类标准，所以两种方法均具有片面性。

K-Means算法[2]是由MacQueen提出的一种经典的聚类算法，具有简单、快速和有效的数据分类能力，但聚类结果的优劣常依赖于初始值，且其采用基于梯度下降的算法使其易于得到局部最优解。

为了克服K-Means聚类方法的不足，不少文献开始对K-Means算法进行改进，文献[3]将遗传算法[4]的编码、适应度、选择、交叉和变异等用于K-Means聚类问题，提高了算法效率。文献[5]通过在粒子群[6]中引入小概率随机变异操作以增强种群的多样性，并通过群体适应度方差以确定K均值的操作时机，以提高算法的收敛性和全局寻优能力。文献[7]首先通过K-Means算法[8]获得聚类中心初始值，在此基础上采用蚁群算法和模拟退火算法对聚类中心进一步寻优。文献[9]首先采用决策树对移动通信客户进行分类，然后再采用相异度原理对客户进行再次分类，通过对移动客户的属性进行分析，来评价不同客户的消费行为，从而寻找出高价值客户。文献[10]设计了基于粗糙神经网络的客户消费分类模型，采用粗糙集进行属性简约和提取规则，从而构造分类神经网络拓扑结构，最后对网络进行训练和分类。文献[11]提出了一种基于改进DBSCAN算法的电信客户分类方法，通过为聚类分析生成增广簇排序，而簇排序对应了各样本点基于密度的簇结构，最终实现了电信客户的聚类。

上述工作均对实现了对用户的分类，具有重要的意义，本文在上述工作的基础上，提出了一种使用混沌PSO和K-Means算法并根据用户的消费行为对移动用户进行分类的方法，首先采用改进的普里姆算法获得初始聚类中心，然后采用混沌PSO对聚类中心进行优化，最后，采用K-Means算法聚类实现移动用户分类，较好地解决了移动用户分类问题。

2 K-Means算法

K-Means算法是一种基于距离的聚类算法，采用距离作为相似度评价指标，即如果两个数据对象之间的距离越近，它们之间的相似度越大。

从图1中可以看出文中方法较传统的K-Means算法收敛速度快，并能逼近全局最优解，而在迭代同样次数时，传统的K-Means算法由于随机选择聚类中心，所以收敛速度快，但最终陷入了局部最优。

5 总结

针对移动用户分类需求，提出了一种基于粒子群和K-Means算法的聚类方法。首先采用改进的普里姆算法进行聚类中心初始化，为了避免陷入局部最优解，采用混沌粒子群算法对聚类中心进一步进行寻优，以获得全局最优的聚类中心，最后，再采用经典K-Means算法进行聚类。实验表明文中方法克服了K-Means算法对于初始数据中心敏感以及易收敛于局部最优解的问题，能有效地对移动用户进行分类以协助移动公司针对不同用户指定相应政策。

参考文献

[1]范英， 张忠能， 凌君逸. 聚类方法在通信行业客户细分中的应用[J].计算机工程， 2004， 30（12）：440-441.

[2] Li M J and Ng M K， et al.. Agglomerative fuzzy K-means clustering algorithm with selection of number of clusters[J]. IEEE Transactions on Knowledge and Data Engineering， 2008， 20（11）： 1519-1534.

[3]唐朝霞.一种改进的基于遗传算法的K均值聚类算法[J].成都大学学报， 2011， 30（2）：162-164.

[4]刘全， 王晓燕， 傅启明， 张永刚， 章晓芳. 双精英协同进化遗传算法[J].软件学报，2012，23（4）：765-775.

[5]陶新民， 徐晶， 杨立标， 刘玉. 一种改进的粒子群和K均值混合聚类算法[J].电子与信息学报， 2010， 32（1）：92-97.

[6]纪震， 周家锐， 廖慧连， 吴青华.智能单粒子优化算法[J].计算机学报， 2010， 33（3）：556-561.

[7]陶红， 史小伍，李莎，高尚.基于蚁群和模拟退火算法的聚类新方法[J].微电子学与计算机，2011，28（12）：96-98.

[8]王会青， 陈俊杰， 郭凯. 启发式初始化独立的K-均值算法研究[J].2012， 48（11）：129-132.

[9]陈峰. 基于决策树和相异度算法的移动通信客户分类方法[J]， 计算机应用， 2009， 29（8）：2250-2256.

[10]万映红， 胡万平， 曹小鹏. 基于粗糙神经网络的客户消费模型研究[J]. 管理工程学报， 2011，25（2）：142-148.

[11]左国才， 周荣华， 符开耀. 基于DBSCAN算法的电信客户分类的应用研究[J].2012，26（3）：52-55.

[12]王会青， 陈俊杰， 郭凯. 启发式初始化独立的K-均值算法研究[J].计算机工程与应用， 2012，48（11）：129-132.

[13]单良，强浩，李军. 基于Tent 影射的混沌优化算法[J]. 控制与决策， 2005，20（ 2） ： 179-182.