基于消除噪声的聚类算法的手机用户行为分析

【摘要】针对数据量大、含有噪声、属性变量较多的数据集群，提出了一种基于消除噪声的聚类算法。该算法对数据进行分析及预处理，接着进行消除噪声处理，之后采用改进聚类算法对数据集进行聚类分析。在实验中，采用10 000条移动用户的手机数据，对通常的聚类方法和消除噪声后的改进聚类算法进行分析比较，发现改进后的算法效率更高、准确度也更好。根据聚类后的数据总结分析移动用户对新业务的使用情况，将有助于指导业务的开展。

【关键词】聚类算法消除噪声手机用户行为

中图分类号：TP392文献标识码：A文章编号：1006-1010(2014)-07-0036-04

1 概述

根据用户的行为数据对客户群体进行细分，从而采取不同的营销策略，是目前各通信运营商常用的业务推广方式[1-2]。对行为数据筛选聚类质量的高低，往往对细分人群特征提取起到决定性作用。一些常用的聚类算法，需结合通信行业服务特点，进行专门的优化和改进，借此提高客户识别率和命中率，从而帮助企业更好地制定相关营销策略，差异化服务相应客户。

本文提出了一种消除噪声的聚类算法来分析手机用户的行为，该方法针对手机用户的数据特点进行除噪再聚类，使得分析后的结果更准确，效率也更高。

2 除噪模块的提出

由于采集到的实际数据比较零散，不适合直接进行分析[3-4]；为此，本文首先对收集到的数据进行一系列处理，合成ARFF格式的文件，然后使用K-Means算法进行数据挖掘的处理操作。

然而，在对手机用户行为进行分析时，K-Means算法有几个不适宜之处：

第一，K-Means算法要求先定义簇的平均值再进行使用[5-6]，而这对于有分类属性的数据是不太适宜的。因为，如果用户事先给出k（要生成的簇的数目），那么对于不同的初始值，就会得出不同的聚类结果，这样就使得对初始值的选取十分敏感。

第二，K-Means算法对于凸面形状的簇，以及属性大小差别很大的簇识别能力有限；那么在手机用户群体属性差异较大时，会产生较大的误差。

第三，K-Means算法对于“噪声”和孤立点数据十分敏感，少量的该类数据会对平均值产生极大影响。

因此，本文加入“除噪模块”对数据进行处理，这样可以提高效率和准确率。

3 消除噪声的改进聚类算法的实现

3.1除噪聚类算法描述

为了能快速方便地处理大量数据，又要尽量减弱数据库中噪声点对聚类分析带来的不利影响，本文将两种算法相结合，即结合处理噪声数据源效果较好的DBSCAN算法与操作快速简便的K-Means算法，先利用前者对数据源文件进行除噪处理，再利用后者进行聚类分析。

（1）算法1：除噪聚类算法

输入：簇的数目k，包含n个对象的数据库，邻域半径ε，最小数目MinPts；

输出：k个簇，使平方误差准则最小。

过程：

Step1 调用DBSCAN算法对数据中的噪声事件进行判断和挖掘；

Step2对Step1产生的噪声进行处理；

Step3 对处理噪声后的数据，采用K-Means进行聚类分析；

Step4 K-Means采用不同的k值得到平方误差准则最小的分类。

（2）算法2：DBSCAN算法

Algorithm DBSCAN(D, ε, MinPts)//初始时所有对象没有进行分类

输入：包含n个数据对象的数据库D，邻域半径ε，最小数目MinPts；

输出：所有生成的簇，达到密度要求。

过程：

REPEAT

从数据库中找出一个未处理过的点；

IF 抽出的事核心点

THEN 找出所有从该点密度可达的对象，形成一个簇；

ELSE 抽出的点是边缘点（非核心对象），跳出本次循环，寻找下一点；

UNTIL 所有的点都被处理。

3.2除噪算法分析

本算法是一个嵌套算法，是两种不同聚类算法的结合。以下对算法的性能进行分析：

（1）空间复杂度分析

假设数据集D包含n个数据对象。若没有索引，在查询数据集中的某个点时，都要遍历整个数据集，因此时间复杂度是O(n2)；若使用索引，那么遍历操作的时间复杂度可降为O(nlgn)。

解释：

∵R*树的高度是O(lgn)，而ε邻域相对于整个数据空间很小，当查询树的有限分支时，对此“小”区域查询的平均耗时即为O(lgn)；

又∵对于数据集中的每个点，算法至多只需执行一次“小”区域查询；

∴使用R*树索引使得算法的时间复杂度降为O(lgn)。

（2）算法特点分析

①优点：DBSCAN算法能够把具有足够高密度的区域划分为簇，同时可在有“噪声”的空间数据库中发现满足指定条件的聚类。

②缺点：对内存要求高，输入参数敏感，数据要求分布均匀。

3.3除噪算法改进

考虑到除噪算法有上述缺点，笔者提出改进后的除噪算法如下：

（1）使用R*树索引。构造R*树，使用索引，从而将数据处理的时间复杂度降为O(nlgn)，降低该算法对内存的要求；

（2）试探性确定合理的参数ε和MinPts。

在一般情况下，为减少运算量，可以固定ε和MinPts中任意一个参数的值[7-9]，而根据需要确定另一个参数的值。若固定MinPts值，根据较密的那些类来选取较小的ε值，那么就可以使得位于相对较稀的那些类中的对象，减少邻域中的数据对象的数目，当该数目小于MinPts时，将这些对象定义为噪声点，这样就避免了分布较稀的类中的对象被分成多个性质相似的类。反之，根据较稀的那些类的性质确定一个较大的ε值，这样离得近且密度大的那些类之间的差异也就会被忽略，它们即可合并为同一个类。

4 实验和结果分析

4.1消除噪声的改进聚类算法

在中国移动某分公司提供的数据中，共针对153个属性进行筛选，选择其中的30个属性作为重点进行研究。在原始数据经过处理后，得到本文研究所需的weka数据文件，该文件中包含了30个属性值的10 000条记录。

（1）消除噪声的改进聚类算法的实现过程

①发现噪声实例

由于在数据库实例的采集过程中，可能会有一些数据采集误差和数据预处理的错误操作，数据中存在着可以称得上“噪声”的实例。为了进行更准确的数据挖掘，需要先对这些噪声进行处理，然后在消除噪声的基础上进行数据挖掘，提高数据挖掘效率。

测试条件：利用DBSCAN算法发现数据中潜在的噪声实例，选取参数ε=0.8，MinPts=4。

结果分析：观察运行结果可知，实例数目为10 000，属性个数为30，生成2个聚类，运行时间为549.8s；同时，该算法运行结果中，被判断为噪声的实例数目为8。

②消除噪声实例

对源文件中的实例进行筛选，找出运行结果为噪声的实例并删除，在删除被判断为噪声的8个实例后，保存为文件finally.arff，即为删除噪声后的数据文件。该文件中含有实例9 992个，属性数为30。

③除噪后聚类分析

针对文件finally.arff，再次利用K-Means算法进行聚类分析。

（2）两种模块对比

对两种模块分别用K-Means算法进行聚类分析，其中设置“numClusters”为6，即k=6。从两种不同模块的运行结果中不难看出，噪声是影响数据挖掘质量的一个重要因素，在消除噪声后，迭代次数从29次减到5次，簇内的误差平方和也有一定程度的降低，从而验证了消除噪声后再进行数据挖掘的必要性，见表1：

endprint

表1噪声消除前后K-Means算法性能参数对比表

类型 迭代次数 簇内的误差平方和

未消除噪声 29 1 722.186 132 049 162 3

消除噪声 5 1 484.293 250 367 957 9

4.2手机用户群体行为分析

根据上述改进的聚类算法，本文对10 000份移动用户消费数据进行分析，由4.1节的分析得知删除噪声后的数据文件中含有实例样本9 992个。本文按照年龄段进行划分，针对移动新近推出的几类新业务进行聚类分析，得到如图1所示的结果。

聚类依据：

◆上网本用户：流量使用达到每月10M以上；

◆电子渠道用户：访问网上营业厅1次以上；

◆手机报用户：每月定制3种以上手机报业务；

◆彩铃用户：自行下载3条以上彩铃；

◆短信用户：点对点短信每月250条以上。

由聚类结果可知，根据用户年龄层次划分，每类用户间的消费状况基本相似，因此营销策划首先应根据年龄段进行规划。图2总结了根据图1的聚类结果进行分析的手机用户群体行为以及提升方案：

从上述分析可以看出，移动业务的使用带有一定的群体行为；那么在制定和推广业务时，运营商应考虑到群体的特点，推出相应的特色业务，以吸引更多的客户。

5 总结

对于数据量大、含有噪声、属性变量较多数据分析的问题，往往采用数据挖掘的方法，但需要根据数据自身的特点选择合适的方法。本文主要讨论手机用户的群体行为，根据其特点提出了去除噪声后的聚类算法，该方法避免了一些噪声点对整体数据分析的影响，从而能更好地指导对手机用户行为的分析。

参考文献：

[1] 唐晓兰,刘中临,刘嘉勇. 一种基于知识库的行为特征检测模型[J]. 信息安全与通信保密, 2012(2): 78-82.

[2] 孙燕花,李杰,李建. 基于CURE算法的网络用户行为分析[J]. 计算机技术与发展, 2011,21(9): 35-38.

[3] 牛红惠,徐甜. 基于聚类粒子群算法网络异常检测模型研究[J]. 微电子学与计算机, 2012,29(3): 102-105.

[4] 许琼来,唐守廉. 3G时代移动用户市场细分研究[J]. 移动通信, 2008(1): 71-74.

[5] 李丹,刘雁. 从用户消费偏好出发浅析移动增值业务营销策略[J]. 移动通信, 2007(7): 89-92.

[6] 朱旭东,刘志镜. 基于主题隐马尔科夫模型的人体异常行为识别[J]. 计算机科学, 2012,39(3): 251-257.

[7] 吴斌,郑毅,傅伟鹏,等. 一种基于群体智能的客户行为分析算法[J]. 计算机学报, 2003,26(8): 913-918.

[8] Eduardo Ares M, Parapar Javier, Barreiro Alvaro. An experimental study of constrained clustering effectiveness in presence of erroneous constraints[J]. Information Processing & Management, 2011,48(3): 537-551.

[9] Guerra L, Robles V, Bielza C. A comparison of clustering quality indices using outliers and noise[J]. Intelligent Data Analysis, 2012,16(4): 703-715.★

作者简介

顾强：硕士毕业于南京邮电大学，现就职于中国移动通信集团江苏有限公司，研究方向为数据仓库、经营分析、数据挖掘等。

endprint

表1噪声消除前后K-Means算法性能参数对比表

类型 迭代次数 簇内的误差平方和

未消除噪声 29 1 722.186 132 049 162 3

消除噪声 5 1 484.293 250 367 957 9

4.2手机用户群体行为分析

根据上述改进的聚类算法，本文对10 000份移动用户消费数据进行分析，由4.1节的分析得知删除噪声后的数据文件中含有实例样本9 992个。本文按照年龄段进行划分，针对移动新近推出的几类新业务进行聚类分析，得到如图1所示的结果。

聚类依据：

◆上网本用户：流量使用达到每月10M以上；

◆电子渠道用户：访问网上营业厅1次以上；

◆手机报用户：每月定制3种以上手机报业务；

◆彩铃用户：自行下载3条以上彩铃；

◆短信用户：点对点短信每月250条以上。

由聚类结果可知，根据用户年龄层次划分，每类用户间的消费状况基本相似，因此营销策划首先应根据年龄段进行规划。图2总结了根据图1的聚类结果进行分析的手机用户群体行为以及提升方案：

从上述分析可以看出，移动业务的使用带有一定的群体行为；那么在制定和推广业务时，运营商应考虑到群体的特点，推出相应的特色业务，以吸引更多的客户。

5 总结

对于数据量大、含有噪声、属性变量较多数据分析的问题，往往采用数据挖掘的方法，但需要根据数据自身的特点选择合适的方法。本文主要讨论手机用户的群体行为，根据其特点提出了去除噪声后的聚类算法，该方法避免了一些噪声点对整体数据分析的影响，从而能更好地指导对手机用户行为的分析。

参考文献：

[1] 唐晓兰,刘中临,刘嘉勇. 一种基于知识库的行为特征检测模型[J]. 信息安全与通信保密, 2012(2): 78-82.

[2] 孙燕花,李杰,李建. 基于CURE算法的网络用户行为分析[J]. 计算机技术与发展, 2011,21(9): 35-38.

[3] 牛红惠,徐甜. 基于聚类粒子群算法网络异常检测模型研究[J]. 微电子学与计算机, 2012,29(3): 102-105.

[4] 许琼来,唐守廉. 3G时代移动用户市场细分研究[J]. 移动通信, 2008(1): 71-74.

[5] 李丹,刘雁. 从用户消费偏好出发浅析移动增值业务营销策略[J]. 移动通信, 2007(7): 89-92.

[6] 朱旭东,刘志镜. 基于主题隐马尔科夫模型的人体异常行为识别[J]. 计算机科学, 2012,39(3): 251-257.

[7] 吴斌,郑毅,傅伟鹏,等. 一种基于群体智能的客户行为分析算法[J]. 计算机学报, 2003,26(8): 913-918.

[8] Eduardo Ares M, Parapar Javier, Barreiro Alvaro. An experimental study of constrained clustering effectiveness in presence of erroneous constraints[J]. Information Processing & Management, 2011,48(3): 537-551.

[9] Guerra L, Robles V, Bielza C. A comparison of clustering quality indices using outliers and noise[J]. Intelligent Data Analysis, 2012,16(4): 703-715.★

作者简介

顾强：硕士毕业于南京邮电大学，现就职于中国移动通信集团江苏有限公司，研究方向为数据仓库、经营分析、数据挖掘等。

endprint

表1噪声消除前后K-Means算法性能参数对比表

类型 迭代次数 簇内的误差平方和

未消除噪声 29 1 722.186 132 049 162 3

消除噪声 5 1 484.293 250 367 957 9

4.2手机用户群体行为分析

根据上述改进的聚类算法，本文对10 000份移动用户消费数据进行分析，由4.1节的分析得知删除噪声后的数据文件中含有实例样本9 992个。本文按照年龄段进行划分，针对移动新近推出的几类新业务进行聚类分析，得到如图1所示的结果。

聚类依据：

◆上网本用户：流量使用达到每月10M以上；

◆电子渠道用户：访问网上营业厅1次以上；

◆手机报用户：每月定制3种以上手机报业务；

◆彩铃用户：自行下载3条以上彩铃；

◆短信用户：点对点短信每月250条以上。

由聚类结果可知，根据用户年龄层次划分，每类用户间的消费状况基本相似，因此营销策划首先应根据年龄段进行规划。图2总结了根据图1的聚类结果进行分析的手机用户群体行为以及提升方案：

从上述分析可以看出，移动业务的使用带有一定的群体行为；那么在制定和推广业务时，运营商应考虑到群体的特点，推出相应的特色业务，以吸引更多的客户。

5 总结

对于数据量大、含有噪声、属性变量较多数据分析的问题，往往采用数据挖掘的方法，但需要根据数据自身的特点选择合适的方法。本文主要讨论手机用户的群体行为，根据其特点提出了去除噪声后的聚类算法，该方法避免了一些噪声点对整体数据分析的影响，从而能更好地指导对手机用户行为的分析。

参考文献：

[1] 唐晓兰,刘中临,刘嘉勇. 一种基于知识库的行为特征检测模型[J]. 信息安全与通信保密, 2012(2): 78-82.

[2] 孙燕花,李杰,李建. 基于CURE算法的网络用户行为分析[J]. 计算机技术与发展, 2011,21(9): 35-38.

[3] 牛红惠,徐甜. 基于聚类粒子群算法网络异常检测模型研究[J]. 微电子学与计算机, 2012,29(3): 102-105.

[4] 许琼来,唐守廉. 3G时代移动用户市场细分研究[J]. 移动通信, 2008(1): 71-74.

[5] 李丹,刘雁. 从用户消费偏好出发浅析移动增值业务营销策略[J]. 移动通信, 2007(7): 89-92.

[6] 朱旭东,刘志镜. 基于主题隐马尔科夫模型的人体异常行为识别[J]. 计算机科学, 2012,39(3): 251-257.

[7] 吴斌,郑毅,傅伟鹏,等. 一种基于群体智能的客户行为分析算法[J]. 计算机学报, 2003,26(8): 913-918.

[8] Eduardo Ares M, Parapar Javier, Barreiro Alvaro. An experimental study of constrained clustering effectiveness in presence of erroneous constraints[J]. Information Processing & Management, 2011,48(3): 537-551.

[9] Guerra L, Robles V, Bielza C. A comparison of clustering quality indices using outliers and noise[J]. Intelligent Data Analysis, 2012,16(4): 703-715.★

作者简介

顾强：硕士毕业于南京邮电大学，现就职于中国移动通信集团江苏有限公司，研究方向为数据仓库、经营分析、数据挖掘等。

endprint