论文研究-基于鲁棒高斯混合模型的加速EM算法研究.pdf

所需积分/C币:12 2019-07-22 22:34:04 1.13MB .PDF
222
收藏 收藏
举报

针对传统鲁棒高斯混合模型EM算法存在模型成分参数难以精确获取最优解以及收敛速度随样本数量的增加而快速降低等问题,提出了一种基于鲁棒高斯混合模型的加速EM算法。该算法采用隐含参量信息熵原理对高斯模型分量个数进行挑选,以及使用Aitken加速方法减少算法的迭代次数,当接近最优解时,EM步长的变化极为缓慢,这时使用Broyden对称秩1校正公式进行校正,使算法快速收敛,从而能够在很少的迭代次数内精确获取高斯混合模型的模型成分数。该算法通过与传统鲁棒EM算法和无监督的EM算法的聚类结果进行比较,实验证明该算法对初始值的设定并不敏感(成分数c无须预先设定),并且能够降低算法运算时间,提高聚类模型成分数(类簇)的正确率。
1044 计算机应用研究 第34卷 当z=0或z=1时,lnz=0;当z=c-时,样本x;是称秩1校正公式 否属于第k个高斯模型分量就会出现不确定性,并且缺失参数2.4改进算法的基本步骤 信息熵-zlnz取最大值e-。 a)初始化工作。设定分量个数k=n,混合系数丌=1/h 因此,当z=0或z=1时,-∑ ai In zik=0,第i个样本隐混合参数惩罚系数β=1。在参数空间中为每个模型分量参 含参数信息熵最小,那么总样木隐含参数信息熵-∑∑z1m数随意没置初始值。 b)以作为i+1步迭代初值,得到佔计值0,代入 an也就最小。当总样本隐含参数信息熵-2Em最小+{-DM(9*)-1(6-),从而修正得到+。 时,所对应的k值为分量个数最优解。 c)上-step。通过式(5)(6)获取辅劻函数Q(0,021)和隐 2.2提高聚类模型成分数的精度 含参量z 在传统鲁棒EⅥ算法屮,虽然每次迭代都能够将混合系数 d)M-step。通过式(13)代替式(6)计算H混合系数 σ≤的模型分量进行删减,但是当迭代稳定时,所得估计参 数k值木必是分量个数最优解。当高斯分量个数小于当前估 e)当混合系数丌≤时,则删除分量k,同时令k=k-1 计参数k值时,每次迭代的混合系数依然满足所有模型系数 「) Juslilicalional-step。执行式(14)(15)和(11),求出 丌4>的条件,此时模型成分数k值也可能成为分量个数最k、2和的迭代值。 g)对动使用 Broyden对称秩1校正公式,置 优解。 (4,-x16)(4,-z6) 解保存该分量个数相对应的隐含参数z值,令分量个数估计.,(4,-48),其中△,=g(")-g(”),80 在文献[1]算法的基础上,迭代求解分量个数k的最优 参数k=k-1,冉一次进行上述算法来求解下一个最优解,同 h)如果max‖μ2+1-k‘‖<g,收敛结束;否则,继续执行 吋保存相对应的隐含参数κ值,直至左≥2,循环终止。将保存 的隐含参数z值根据隐含参数信息熵原理进行比较,求得总 i)设立一个三维数组W,将x→W。当k=2时,循坯结 样木隐含参数z信息熵最小值所对应估计参数k值即为分量束;否则,在当前的h个高斯分量中找出权重最小的高斯分量 个数的最优解。 将其强行删除。令k=k-1,继续执行步骤a)。 2.3加怏算法的收敛速度 j利用隐含参量信息熵原理,比较三维数组W数据的总 EM算法最大的缺点就是收敛速度缓慢,只是次线性的收样本信息熵最小值,则最小值所对应的k值就是最佳分量个数 敛速度,这个缺点严重妨碍了EM算法在实际屮的发展与应最优解。 用。在保证具备原有EM算法单调收敛的前提下,本文提出 从以上步骤可以看出,改进的算法在每次迭代过程中有 种加速EM算法。 次成分的消狳过程(如步骤e))和两次提高算法收敛速度的步 在迭代初期,使用 Aitken加速方法减少算法的迭代次数,骤(如c)和g)。当迭代过程趋于稳定时,用 Broyden对称秩l 加速暹近最优解。当接近最优解吋,FⅥ步长的变化极为缓校正,拥有一组最佳k值判定的过程(如i)j))。这将使算法 慢,这时使用 Broyden对称秩Ⅰ校正公式进行校正。于是在整的迭代次数大大减少,运算时间加速,聚类模型成分精度得以 个迭代周期使EM算法的迭代次数明显减少,从而达到加速收提升。 敛的日的。 定理1在EM算法收敛的条件下,加速EM算法收敛 3实验结果分析 证明此问题可分以下情况讨论 本文实验的程序是在个人PC机上进行实验结果的验证。 a)若在加速EM算法中,每次迭代都取EM步长△“计该PC机为mc1 CORETM32310MCPU@2.10GHz,4CB 算△0+1),则加速EM算法即为EM算法 RAM,500GB硬盘和 Windows7旗舰版64hit操作系统,同时 b)若在加速下M算法中,每次迭代都按公式△0+1) 使用 MATLAB7.0作为实验平台。本文实验针对三种不同算 A0k)-Z吕 0(6)计算△01),则由g((4)≤,(+1)<a1)可法在高斯分量模型成分数正确率、运行时间以及算法收敛速度 得1)<m<a-1)…(4+)r0),因a<1,k→a时,记等方面进行比较。这三种算法分别为算法1是一种传统鲁棒 02→6“,则‖g(6=0,所以加速EM算法收敛 的EM聚类算法(即文L」中的REM-GMM算法)、算法2即 c)一般情形时,若设加速EM算法局部收敛,即存在某个本文提出的基于鲁棒高斯混合模型的加速EM聚类算法(AR 列|r()}的构造可知,存在子列/6。而由非负单调递减数M-GMM、算法3是一种传统的无监督EM算法(即文献[9 1,n→0,所以存在k2,当中的 NSEM-GMM算法)。 k>mxh1,k2时,r<公,于是‖g()<a!r)<(t≥1) 本文实验分成两组进行,一组是运用上述三种不同算法对 矛盾,因此加谏EM算法收敛。 标准的臃机样本数据(高斯分布随机数据)对象进行实验分 从数值实验结果来看,加速EM算法能显著减少迭代次析;另一组是同样运用上述三种不同算法对从UCI数据集屮 数,并且参数估计精度更高。但考虑到什么时候运用对称秩下载的 Irish数据集进行实验对比。这两组实验的结果主要是 1,所以在加速EM算法中加进一个延迟计算‖+-14‖<以聚类结果成分数正确率以及平均迭代次数和运行时间等方 ω,目的是将恔正尽量靠后,当接近最优解时,再用Broνden对面进行比较和分析。数据集的基本信息如表1所示。 第4期 邢长征,等:基于鲁棒高斯泥合模型的加逴玊M算法研究 1045 表1模拟数据集的信息 隐含参数信息熵的原理对隐含参数信息熵进行比较,当模型成 数据集名称 数据集数目类数 数 分数所对应的隐含参数信息熵取最小值时,该模型成分数即为 高斯分布随机数据 最优解,有效地提高了聚类模型成分效的精度,仅有两次收敛 150 4 成分数为2。NSEⅥ-GMM算法收敛的成分数正确率更低,有 3.1第一组实验 10次是收敛错误的。RFM-GⅥM与本文算法的正确率都在 95%以上,其中,本文算法( AREM-GMM)效果最好,成分数正 第一组实验所用数据集的样本总数为80,数据维数为2确率已达到了98% 样本数据对象由三个不同参数的高斯分布随机产生,其中 表2第一组数据聚类的比较结果 样本1由300个随机数据对象组成,样本2出200个随机数据 对象组成,样木3由300个随机数据对象组成。各个高斯分布 算法 齿代次数平均耗时模型成分数数据分类 正确率/%正确率/ REM-GMM 107.63 的期準值与协方差分别为1=(0,0),2 0|;/2=(20 AREM-GMM 81.37 98.5 0,9/43=(O,20),E1=(10.0 9,0 NSEM-GMM 135.24 2 0),∑,= 0.10 样木数据对象是 冋时可知,当在三种算法的聚类模型成分数都正确时,数 相互独立存在的,其中第一个分布数据对象比较分散。数据点据分类的正确率基本相同(基本都到达了97%)。这就说明了 分布图如图2所示 当聚类分量个数为最优解时,三种算法的数据聚类效果基不相 同,但本文算法的迭代次数最少,运行速度最快,模型成分数正 确率最高 国-0.2 3.2第二组实验 木组实验所用的数据集是由UCI机器学习库中下载的 =10 lis数据集,该数据集包含150个样本数据集对象。其中 0020406081-900010x301i数据集样本向量为4维,可以分为 setosa, versicolo和vi 图1函数fa=ain的线性图 图2数据集分布图 sinica三类。 利用本文改进的算法来进行数据集的高斯混合模型聚类。 Iris数据集在通过本文改进算法的某一次聚类过程中,迭 模型成分数初始化为c=800,根据迭代条什n≤-逐次删除代稳定后模型成分数为7,通过步骤h)i),计算出模型成分数 (步骤b)~h)所有的隐含参数值,通过隐含参数信息熵原理 混合系数较小的高斯模型,直到找出一组稳定的高斯馍型成分 对模型分量对应的总样本隐含参数信息熵进行比较,结果如图 数所对应的隐含参量值,通过隐含参量信息熵原理来最终求解4所小 出高斯混合模型的最终聚类结果,其中c=3时,总样本隐含参4所小 量信息熵最小,所对应的模型分量个数c=3为最优解。迭代 过程如图3所示。 模型分量个数k 图4分量个数所对应的隐含参数信息熵 a初始成分数c=800 (b)迭代成分数c=5 由图4可知,当分量个数k=3时,总样厶隐含参数信息熵 值最低,即分量个数3就是所求聚类分量个数最优解 lris数据集对三种不同算法都执行了250次后,对每种算 法成分数正确率进行比较,结果如表3所示。 表3竻二绀数据聚类的比较结果 20 算法 选代次数耗时模型成分数数据分类 i)代成分数c=3 迭代成分数c=2 正确率/%正确率/% 图3改进EM算法估计CMM过程 REM-GMM 107.4 表2是数据集通过三种不同算法随机执行了100次的比 AREM-GMM 175 较结果。在迭代次数与平均耗时方面笔者发现:本文算法 NSEM-GMM 357 260.1 85.4 ( AREM-GMM)采用 Aitken加速方法减少算法的迭代次数,当 由表3可以看出,本文改进的算法(ARFM-GMM)比原始 接近最优解时,EM步长的变化极为缓慢,这时使用 Broyden对鲁棒EM算法(HM-GⅥM算法)模型成分数正确率要高出8.4 称秩1校正公式进行校正,使算法快速收敛。所以本文算法的个百分点,同时也比般的无监督EⅥ算法( NSEM-GMM算 平均迭代次数和运行时间均优于其他两种算法,运行时间仅有法)的成分数正确率要高出10.9个百分点。同时,文算法 81.37s。同时,在模型成分数正确率方面, REM-GMM算法有( AREM-GMM)所花费的时间也是最少的。由此,本文算法具 四次收敛成分数为5,两次收敛成分数为4。而本文算法根据有更高的成分数正确率、更快的执行速度。 1046 计算机应用研究 第34卷 Conference Proceedings. 2013: 824-826 4结束语 [6 Peng Shanguo, Wang Xiwu, Zhong Qigen. The study of EM algorithm 本文在传统的EM算法基础上采用隐含参量信息熵原理 based on forward sampling C//Proc of International Conference on Electronics ComMunications and Control. [SL.]: IFFF. Press, 201 1 对高斯模犁分量个数进行挑诜以及使用 Aitken加速方法减少 4597-4600 算法的迭代次数,当接近最优解时,EM步长的变化极为缓慢 [7]朱林,雷景生,毕志勤,等,一种基于数据流旳软子空间聚类算法 这时使用 Broyden对称秩1饺正公式进行校正。本文算法解 LJ」.软件学报,2013,24(11):2610-2627 决了传统EM算法存在模型分量个数易陷于局部最优解,以及 [8 Figueiredo M A T, Jain A K. Unsupervised learning of finite mixture 在参数估计中需要人工参与等问题。实验证明该算法在没有 models[J. IEEE Trans on Pattem Analysis and Machine Intelli 预先指定模型分量参数和不改变数据聚类效果的前提下,模型 gence,2002,24(3):381-396 成分数准确率更高,迭代次数更少,收斂比率较快,并且由十本[9]宋磊,郑宝忠,张莹,等.一种基于高斯混合模型的改进EM算法 算法对初始条件不敏感.所以其鲁棒性更优。但乜存在局限 研究[J].应用光学,2013,34(6):985-989 性,本文算法没有探究在有噪声的数据集屮进行聚类的效果,「0姜元凯,郑洪源.基于粗糙模糊集的不确定数据流聚类算法「J 考虑在加人噪声的数据集中提高聚类精度有待进一步研究。 计算机科学与探索,2014,8(12):1494-1501 参考文献 L1Il」何剪,刘青宝.基于动态网格的数橘流聚类分析LJ」.计算机应用 1 Yang M S, Lai CY, Lin C Y. A robust EM clustering algorithm for 研究,2008,25(11):3281-3284 Gaussian mixture models[ J. Patter Recognition, 2012, 45(11) [12]赵桂儒,李卫东,刘典婷,等.EM算法的改进及其在行为识别中 3950-3961. 的应用[冂].视频应用与工程,2014,39(13):196-199 12」乔少杰,金混,韩楠,等.一种基于高斯混合模型的轨迹预测算法13赵晨阳,翟少丹,侣,基于最大后验估计的无监督聚类算法 [冂].软件学报,2015,26(5):1048-1063. [J].计算机工程与应用,2013,49(19):131-134 3」张欢鑫,冉鑫,基于在线分裂合并EM算法的高斯混合模型分类[14】 Aggarwal C, Han jiawei, wang jianyong,“a. A frame-work for 方法[J].计算机应用研究,2010,27(8):2906-2908 clustering evolving data streams[ C//Proe of the 29th International L 4 Sheikholeslani G, Chatterjees C, Zhang Aidong. Wave Cluster: a Conference on Very Large Data Bases. Washington DC: IEEE Pless multi-resolution clustering approach forvery large spatial databases 2003;81-92 Cl//Proc of the 24th Conference on VLDB. New York: ACM Press, 15] Nasereddins HH O. Stream data mining[ J]. Computer and Infor- mation Science,2009,1(8):183-190 [5] Zhang(hao, Feng fen, Zhang Qijun. EM optimization using coarse[I6]肖字鹏,何云斌,万静,等·基于模糊C均值的空间不确定数据聚 and fine mesh space mapping C]//Proc of Asia-Pacific Microwave 类[J].计算机二程,2015,41(10):47-52 (上接第1035页)用户偏好模型。山于群组推荐的特殊性,在构 group recommender systems for tourism[ J. Expert Systems with 建群组偏好模型时,本文考虑成员间的相互作用.从用户项目 Applications2011,38(6):7683-7692 特征属性均值相似性权重和特征频度权重两个方面来得到群[7] Jameson A, Smyth B. Recommendation to groups[ M]/ The Adap 伓用户偏好模型。相似度计算是保证推桲准确度关键的步骤 tive Web. Berlin: Springer, 2007: 596-627 本文计算群休在项目特征和评分上的综合相似度,并在Mo「8 oren-bar,Cmny, recommending TV programs to family Iems数据集上进行实验。通过结果的比较,表明本文提出 members[ J. Computers Graphics, 2004, 28(2): 149-156 的方法优于CHLM、 CF-AVG、ARBG三种方法。下一步的工作 [9 Amer-Yahia S, Roy S B, Chawlat A, et al. Group recommendation 有:a)考虑用户在项目领域中各特征偏好的杖重;b)考虑群组 semantics and efficiency[J. Proceedings of the VLDB Endow ment,2009,2(1):754-765 内成员的社会化关系和互动度对推荐结果的影响。 [10]郭均鹏,赵梦楠.面向在线杜区用户的群休推荐算法研究[冂].计 参考文献 算机应用研究,2014,31(3):6%6-699 [I]孟祥武,纪威宇,张玉洁,大环境下的推荐系统J.北京邮电大学] Song yang, Hu Zheng, Liu haifeng,etal. A novel group recommen 学报,2015,38(2):1-5 dation algorithm with collaborative filtering[ C //Proe of International [2 Chen Y L, Cheng Lichen, Chuang C N.A group recommendation Conferenee on Social Computing. Washington DC IEEE Computer system with consideration of interactions among group members[J] cociety,2013:901-904 Expert Systems with Applications, 2008, 34(3): 2082-2090 [12 Kim J K, Kim H K, Oh H Y. A group recommendation system for [3]梁天一,梁永全,类健聪,等,基于用户兴趣模型的协同过滤推荐 online communities[ J. International Journal of Information Ma 算法J」.计算机应用与软件,2014,31(11):260-263 nagement,2010,30(3):212-219 [4]o' connor M, Cosley d, Konstan J A,elal. PolyLens; a recommen-[13]裴颂文,吴百锋动态自适应特征权重的多类文本分类算法研究 der system for gIoups of users[ C//Proc of the 7th European Confe LJ」.计算机应月研究,2011,28(11):4092-4096 rence on Computer- Supported Cooperative Work. 2001: 199-218 14 Anand D, Bharadwaj KK. Utilizing various sparsity measures for en [5 Balirunas L, Makeinsk as T, Ricri F. Group recommendations with hanciny accurAcy of collaborative rec ommender syslems base! on loeal rank aggregation and collaborative filtering[ C]//Proc of the 4th ACM and global similarities[ J. Expert Systems With Applications Conference on recommender systerms. New york. acm Press 2010 011,38(5):5101-5109 119-1 [15]朱郁筱,苫琳媛.推荐系统评价指标综述[J.电子科技大学学 [6 Garcia I, Sebastia L, Onaindia E. On the design of individual and 报,2012,41(2):163-167

...展开详情
试读 5P 论文研究-基于鲁棒高斯混合模型的加速EM算法研究.pdf
立即下载 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
  • 至尊王者

关注 私信
上传资源赚钱or赚积分
最新推荐
论文研究-基于鲁棒高斯混合模型的加速EM算法研究.pdf 12积分/C币 立即下载
1/5
论文研究-基于鲁棒高斯混合模型的加速EM算法研究.pdf第1页

试读结束, 可继续读1页

12积分/C币 立即下载