基于高斯混合模型的最大期望聚类算法研究

何庆， 易娜， 汪新勇， 江立斌

(中国移动通信集团广东公司，广州 510623)

0 引言

随着信息技术应用领域的不断拓展，人们掌握的数据日益增加，如何存储和分析海量数据，成为学术研究的关键课题。海量数据中隐患带有巨大价值的共识，但由于大数据冗余的问题，其价值密度比较低，很难准确发现其中有价值的信息[1、2]。聚类分析算法是一种在无人监督情况下，进行数据挖掘和机器学习的方法，是进行大数据处理的重要方式。然而，聚类算法需要制定聚类个数，以串行方式运行，不适合海量数据处理。因此，本文选择最大期望聚类算法，其通过高斯混合模型为用户选择合理的聚类个数， 无需凭借经验指定。

1 聚类算法

聚类算法影响因素较多，如，判别标准、算法实现。在大数据处理中，聚类算法要满足以下要求。1.可伸缩性；2.多样性；3.发现任意形式簇；4.聚类高维数据处理。其中，数据集包括大量属性，例如，文档聚类中的关键词。聚类算法适合于低维度数据分析，不适合2-3维数据分析[3、4]。最大期望聚类算法是基于模型的聚类算法[5、6]，假设样本数据分布符合高斯混合模型，算法目的就是确定高斯部件中的参数，对给定数据进行充分拟合，得出模糊聚类。每个样本以不同概率符合每个高斯分析，概率值由以上各个参数计算值求得。最大期望聚类算法的基础是混合高斯模型，该模型被定义为N个高斯密度函数的线性组合，如式(1)。

(1)

(2)

最大似然估计是参数估计的主要方法，其通过似然函数获得最大值的参数估计。高斯混合密度函数中所有参数标记为θ，那么似然函数为式(3)[7、8]：

(3)

其中θ为所参数集合，P(x|θ)为最大似然函数，N为自然数。

2 最大期望聚类算法的优化

为了让最大期望聚类算法的适用范围更广，需要对其进行优化。首先，对公式3取对数，求出其最大值，计算公式如式(4)。

(4)

由于有和的对数，求导结果比较复杂，所以不能采用一般的计算方法，即求偏导并令导数为零的计算方法。最大期望聚类算法可以优化为某混合高斯分布，其共有K个分布，而且对应每一个观察到的X。如果同时知道其属于K中哪个分布[9、10]，就可以求出其中的参数。然而，由于不知道每个X属于哪个分布，就是说Z是观察不到的数值，则Z是隐患变量，如式(5)。

(5)

由于Z是观察不到的数值，所以最大期望聚类算法需要对Z的分布进行假设。依据式(5)进行参数估计，求出式(5)的最大期望值，其计算式，如式(6)。

(6)

通过上述计算以后，式(6)进行拉格朗日乘法计算，可得到式(7)。

(7)

其中，P(k|xi,θ(i-1))可以由以下式求得式(8)。

(8)

期望最大算法的整体流程是重复执行以下2步骤，直至数据收敛：

(1)依据参数初始值，或上次迭代所得结果数值，进行似然函数计算，如式(9)。

(9)

其中的条件分布P(Z|X,θold)的期望为式(10)。

Q(θ，θold)=Ez[logP(X,Z|θ)|X,θold]

(10)

(2)对似然函数进行最大化处理，以此获得新的参数值，用θnew对θold进行更新，实现Q(θ，θold)最大化。

3 大数据处理平台下最大期望聚类算法实现分析

本文以Hadoop平台为实验平台进行分析，该平台属于高效的云计算基础平台，利用通用硬件构建功能强大，运行稳定，操作简单的分布式集群计算系统，完全满足大数据分析的需要。Hadoop平台自身的开源性，使其付出相对低廉的成本[11-12]，就可以轻松处理大规模的数据群。国内利用Hadoop构建底层大数据基础框架平台有百度、腾讯和阿里等互联网公司，也有电信、移动和联通等传统通讯企业。MapReduce是一种新的海量数据处理方式，通过抽象出高层次的数学模型，编写出能够在成千上百台计算机上运行的程序，将聚类分析变得更加简单和准确。MapReduce引擎的扩展性趋于线性，如果数据处理量增加，只需要增加相应的计算机数量即可，而其他参数和运行时间不变。另外，MapReduce稳定性非常高，虽然个别计算机出现故障，但是计算集群规模为数千Note，不影响整体运行效率。对应个别计算故障问题，MapReduce进行相应完善，利用高斯混乱模型，将整体数据分析任务，进行聚类分解，妥善解决数据任务分析失败的问题，保证其不对所属作用的正确执行产生影响。下面就利用MapReduce处理方式中的最大期望聚类算方法，在Hadoop平台中选择样本数据进行相应分析，以国家失业率(UR)和国内人均总产值(GDP)间的关系为案例，进行相应数据说明。其中，数据来源于Hadoop平台中2016年世界主要国家失业率数据(单位：%)和国内人均总产值数据(单位：美元)[13-14]。由于部分国家2016年数据丢失，所以选择131个国家和地区数据进行分析，如表1所示。

表1 2016年世界主要国家失业率数据和国内人均总产值数据

由于利用数学原理进行计算，其过程比较复杂，所以采用MapReduce数据分析方式中的R语言进行数分析。首先，选择最优的聚类数目和一组要选择的混合模型，对每一模型采用基于高斯混合模型的分层聚类，计算出似然函数的最大值，得出最优高斯分布。以初始聚类结果作为最初数值，对每一模型和从2到131的多个类数进行期望值最大化法进行参数估计，计算每一情况下的BIC(贝叶斯数值)，并选择BIC数值最大的模型，完成R语言计算中的模型选择和数据聚类[15、16]。

依据R语言计算结果，得出BIC数值为-901.458 41，最优类别数为3类，并对各类分别含有184,210,3个样本，高斯混合概率密度分别为：0.412 142 17,0.521 352 82,0.098 451 24，可以在R语言中作出二维和三维的聚类概率密度图，如图1、图2所示。

图1 基于高斯混合模型的最大期望聚类二维概率密度图

通过图1可以大致看出各类别的主要分布区域，以及概率密度最为集中区域分别是人均国内生产总值处于45 000美元和失业率处于6%以下，以及国内人均生产总值处于15 000美元，失业率处于6%-7%之间的国家或者区域。由此可知，国内人均生产总值越高，失业率就会相对较低，但是这一特征并不明显，也会存在国内人均生产总值较高，失业率随之增加的现象[17]。

图2 基于高斯混合模型的最大期望聚类三维概率密度图

从图2中的三维概率密度图可知，失业率与国内人均生产总值之间并无必然关系，所以图2中显示的结果：国内人均生产总值越高，失业率就会相对较低，这一特征并不成立。

4 总结

大数据的出现给教育、医疗和工业等行业带来深入影响，其中的潜在价值非常巨大。大数据具有海量性、分散性[8]，实时性和低价值密度性的特征，需要利用数学分析方法进行数据挖掘，特征聚类，发现其中隐藏的价值。数据分析受到高斯混合模型的影响，可以对某一数据任务进行分类表示，并成功地应用到图像处理、语音识别领域。然而，高斯混

合模型在大数据特征分析方面仍然存在很多科学问题，所以本文围绕大数据的本质，深入研究针对大数据分析的最大期望聚类算法。

本文首先介绍基于高斯混合模型的最大期望聚类算法的原理，对高斯混合模型进行操作简化，然后选择Hadoop平台中的经济类数据作为研究对象，并利用MapReduce处理技术中的R语言进行相应分析。在R语言中利用高斯混合模型得出最大期望聚类算法的概率密度，并用二维、三维可视化化图进行表示，通过概率密度形象的表示，可以清楚地发现失业率与国内人均生产总值的集中区域。在二维可视化图中发现的“国内人均生产总值越高，失业率就会相对较低”假设，经过三维可视化图证明为不成立，说明基于高斯混合模型的最大期望聚类算法可以在大数据中发现有价值信息。本文将高斯混合模型应用于大数据分析，具有一定的创新价值，而且MapReduce中的R语言在处理高斯混合模型的数据聚类分析中，具有非常好的作用。

参考文献

[1] 鲁伟明，杜晨阳，魏宝刚，等.基于Map Reduce的分布式近邻传播聚类算法[J].计算机研究与发展.2012,49(8)：1762-1772.

[2] Bi-Ru Dai; I-Chang Lin. Efficient Map/Reduce-Based DBSCAN Algorithm with Optimized Data Partition [J].Cloud Computing, 2012,5(4)：59-66

[3] 翟周伟.Hadoop核心技术[M]北京：机械工业出版社，2015,9(1):2-3.

[4] 黄宜华.深入理解大数据：大数据处理与编程实践[M]北京：机械工业出版社，2014，4(8):9-10.

[5] 孟小峰，慈样.大数据管理:概念、技术与挑战[J].计算机研究与发展，2013,2(1):7.

[6] 陈丽敏，杨静，张健沛.一种加速迭代的大数据集谱聚类方法[J].计算机科学，2012,39(5)：172-176.

[7] 陈思慧.基于M1P和改进模糊K-Means算法的大数据聚类设计[J].计算机测量与控制，2014,22(4)：1270-1275.

[8] 高霞,李瑞俊.EM算法在不完全数据参数估计中的应用[J].集宁师范学院学报,2015,2(3):8-11.

[9] 毛海斌,张潇笑.一种解决不平衡情感分类的EM改进算法[J].电子测试,2015,3(5):90.

[10] 浦慧忠.基于数据挖掘的一种聚类分析方法在PDM系统中的应用研究[J].计算机与数字工程，2016，4(11):7-10.

[11] 陈岩.电信运营商基于移动互联网门户的精细化营销系统研究[J].电信工程技术与标准化，2017，4(2):8-11.

[12] 殷小红,王君.流量精细化运营的网络架构方案[J].通信管理与技术，2014，5(2):9-10

[13] 张卓筠,高功应,王磊.WLAN与LEPACN与EPC网络融合架构研究[J].移动通信，2012,11(10):9-11.

[14] DHARMESTID,NUGROHOSS,et al. The antecedents of online customers at insfaction and customer loyalty. DELAROSAM，2012,8(9):8-11.

[15] 林济铿,刘露,张闻博,等.基于随机模糊聚类的负荷建模与参数辨识[J].电力系统自动化，2013,9(14):9-12.

[16] 张粒子,王茜,舒隽.基于聚类最优乘子向量的发输电系统可靠性评估[J].电力系统自动化，2011,3(6):7-11.

[17] 王德青,刘晓葳,朱建平.基于自适应迭代更新的函数型数据聚类方法研究[J]. 统计研究，2015,4(4):7-9.

[18] MengXiaofeng.Big data management:concepts,techniques andchallenges[J].Journal of Computer Research and Development,2013,50(1)：146-169.