网站首页 公文大全 个人文档 实用范文 讲话致辞 实用工具 心得体会 哲学范文 总结范文 范文大全 报告 合同 文书 信函 实用
  • 汇报体会
  • 节日庆典
  • 礼仪
  • 毕业论文
  • 评语寄语
  • 导游词
  • 口号大全
  • 其他范文
    • 百花范文网 > 实用范文 > 其他范文 > 一种改进的期望最大化算法

    一种改进的期望最大化算法

    时间：2023-01-17 10:00:18来源：百花范文网本文已影响人

    刘 铭, 于子奇

    (长春工业大学 数学与统计学院, 长春 130012)

    期望最大化(expectation-maximum, EM)算法[1]是一种通过迭代进行极大似然估计的优化算法, 广泛应用于对含有隐变量的概率密度模型(如混合高斯模型)的参数估计中. EM算法作为一个基于梯度上升的优化算法, 在对模型参数进行迭代优化的过程中, 其似然函数值一般情况下是递增的. 但EM算法在优化过程中具有收敛速度较慢、 鲁棒性差、 易陷入局部最优等问题.

    对EM算法存在的上述问题, 目前已有许多改进方法. 官国宇等[2]提出了一种基于双截断混合高斯模型推导的EM算法, 并使用Bayes信息准则优化所拟合的混合高斯模型参数；

    Castillo-Barnes等[3]提出使用推广的混合α-stable模型泛化EM算法, 提高了算法的鲁棒性；

    Safarinejadian等[4]结合分布式平均方法改进EM算法, 使其能应用于模拟具有网状拓扑结构的任何网络中；

    Ho等[5]利用协方差修正EM算法中最大化步的偏移量加快了算法的收敛速度；

    Lin等[6]结合Krasnoselskii-Mann(KM)算法和EM算法加速算法的收敛, 并避免了图像重建时出现的模式崩溃问题；

    王卫东等[7]提出了使用密度峰值聚类方法初始化混合高斯模型的参数, 并使用相对熵作为EM算法在迭代过程中的终止条件, 其目的是优化混合高斯模型的最终参数, 并提高模型的鲁棒性；

    Chaudhari等[8]提出了使用k最大似然估计器替代传统EM算法对混合模型进行参数估计, 并实验验证了该方法能在分类精度与传统EM算法相差较小的基础上有效提高模型的收敛速度；

    Wang等[9]提出使用基于EM算法的Bayes推理方法解决了模型及其参数的不稳定性；

    He等[10]基于源自低通信号特性的低秩稀疏先验策略提出了一种新型EM算法, 并将其应用于多图推理与聚类问题中, 实验结果表明, 该算法能有效改善传统EM算法的模型稳定性.

    虽然目前对EM算法的研究成果较丰富, 但其改进算法大多数侧重于解决EM算法的鲁棒性差与收敛速度较慢的问题, 对于模型易陷入局部最优问题的解决方案仍较少. 针对该问题, 本文通过引入模糊C均值(fuzzyC-means, FCM)算法对EM算法进行改进, 先将FCM算法用于生成EM算法的初始参数, 再将初始参数作为先验知识导入到模型中辅助算法跳出局部最优陷阱. 最后通过实验证明改进EM算法在无监督聚类任务中相比于传统的聚类算法效果更优, 且因改进后的EM算法跳出了局部最优陷阱使其结果更可靠.

    1.1 EM算法和混合高斯模型

    期望极大算法是一种迭代优化算法, 用于对含有隐变量的概率参数模型进行极大似然估计, 以求出能拟合给定数据分布的概率模型的最优参数. 该算法需先根据给定的显性数据初步估计出能拟合该数据分布的模型参数, 再根据已估计出的模型参数预测隐性数据的值, 然后根据估计出的隐性数据及之前给出的显性数据再重新对参数进行估计, 反复迭代上述步骤直至收敛后结束迭代.

    对于一个含有隐变量Z的概率模型, 假设给定显性数据为Y, 则概率模型关于Y的概率分布为P(Y|θ), 其中θ为要估计的模型参数.则显性数据Y关于模型参数θ的对数似然函数为L(θ)=logP(Y|θ)；

    假设显性数据Y和隐变量Z之间的联合概率分布为P(Y,Z|θ), 则整体的对数似然函数为L′(θ)=logP(Y,Z|θ).EM算法通过迭代求解显性数据Y关于模型参数θ的对数似然函数L(θ)=logP(Y|θ)的极大近似, 从而得到参数θ的估计值, 即

    (1)

    混合高斯模型(Gaussian mixture model, GMM)是一种基于高斯分布的概率密度模型, 其通过将多个单高斯模型线性组合, 以克服传统单高斯模型对复杂数据样本拟合度较低的缺点. 理论上, 一个混合高斯模型可拟合任意复杂的数据分布, 只要该混合高斯模型拥有足够多且权重设计合理的单高斯模型. 显然, 将混合高斯模型应用到聚类任务中时, 需根据数据特征向量推算出混合高斯模型的权重, 其中混合高斯模型中的各单高斯模型(分量)可视为聚类任务的目标聚类类型. 特别地, 当已知目标的概率密度函数时, 求解混合高斯模型的任务即转化为对高斯概率模型的参数进行估计. 对于已知特征空间X={x1,x2,…,xn}, GMM的概率模型为

    (2)

    其中:x为自变量; 参数π,μ,ε分别为混合概率模型的混合系数、 期望和方差；
    N(x|μk,εk)表示混合概率模型中第k个分量, 参数μk为混合概率模型中第k个分量的期望, 参数εk为混合概率模型中第k个分量的方差；
    πk为混合系数, 即分量N(x|μk,εk)的权重, 其满足约束条件

    (3)

    由式(2)可见, GMM模型中需要进行估计的参数分别为μk,εk和πk, 本文使用EM算法估计混合高斯模型的参数, 其算法流程分为两步：
    首先估计函数参数的粗略值；

    其次根据已知的参数计算最大似然函数.假设参数已被初步估计, 即可视为参数已知, 则需根据其求解参数的最大似然函数.首先求解任意高斯模型k均值μk的最大似然函数, 先将式(2)中的所有样本连乘得到关于π,μ,ε的最大似然函数, 再对式(2)取对数得到关于π,μ,ε的对数似然函数, 最后对μk求导并令导数为0, 即可得到关于μk的最大似然函数：

    (4)

    令

    (5)

    解得

    (7)

    (8)

    由于模型权重πk存在约束条件式(3), 因此需加入Lagrange算子：

    (9)

    解得

    (10)

    由于使用EM算法对混合高斯模型进行参数估计时, 需要先验的高斯模型初始值拟合概率分布, 故需先指定π,μ,ε的初始值, 将其代入式(7)计算出γ(znk), 再将γ(znk)代入式(5),(8),(10)分别求出新的π,μ,ε, 然后用新的π,μ,ε代入式(7)计算出新的γ(znk), 如此循环迭代, 直到算法收敛.EM算法流程如下.

    算法1期望最大化算法.

    输入：K,π,μ,ε,e；

    输出：πnew,μnew,εnew；

    while max{‖lnp(x|π,μ,ε)new-lnp(x|π,μ,ε)old‖2}>edo formula (5) and

    1.2 模糊C均值算法

    模糊C均值(FCM)算法[11]是一种模糊无监督聚类算法, 其为基于划分的聚类算法, 基本思想是通过对目标函数的迭代, 使隶属于同一聚类中心的数据点之间相似度最大, 而隶属于不同聚类中心的数据点之间相似度最小. 作为K均值算法(K-means)的模糊化改进, FCM算法在其基础上引入了基于模糊理论的隶属度概念[12], 从而将K均值算法对数据的硬性划分转变为通过隶属度函数确定某一数据类型的柔性划分.

    作为一种基于目标函数的聚类算法, 根据其基本思想, 将一组含有n个向量的特征空间X={x1,x2,…,xn}分为l类, 其聚类中心用C={c1,c2,…,cl}表示, 求解每个聚类中心, 使距离指标的目标函数达到最小.其目标函数可定义为

    (11)

    其中：U=(uij)是隶属度矩阵, 其元素uij表示第i个向量相对于第j类的隶属度, 该隶属度的取值范围为uij∈[0,1]；

    元素dij=‖xi-cj‖表示第i个特征向量xi与第j个聚类中心cj之间的欧氏距离, 类似于隶属度, 该变量通常用于表示特征向量与聚类中心的相似性；
    m∈[1,+∞)是模糊常数, 表示聚类的模糊程度,m值越大, 表示模糊程度越大.该目标函数的约束条件为对于任意样本xi, 其对各聚类中心的隶属度之和为1, 可表示为

    (12)

    算法通过使用Lagrange乘子法构造新的函数求解给定约束条件下目标函数的最小值：

    (13)

    其中λ为Lagrange乘子.对函数F求极值得到最优化条件如下：

    由极值条件式(12)解得：

    (18)

    FCM算法流程如下.

    算法2模糊C均值算法.

    输入：X,c,m,ε;

    输出：U,C;

    1.3 改进的期望最大化算法

    已知EM算法的迭代策略属于局部最优策略, 且其在迭代过程中极度依赖初始参数值的选择, 故在初始值极端化的情况下易陷入局部收敛问题. 为解决上述问题, 本文将FCM算法用于EM算法的初始化过程, 即使用基于柔性划分的FCM算法. 将数据通过模糊聚类算法预先分配到混合高斯模型的各分量中, 再根据数据在模型中的概率分布, 用期望最大化算法求解混合高斯模型, 最后在聚类中对每个数据点选择概率较大的类作为最终聚类结果. 使用基于FCM的混合高斯模型可在保持原有算法收敛速度的同时, 较合理地搜索到最优的模型参数.

    FCM算法初始化EM算法参数的过程如下：
    首先, 为初始化聚类中心C, 需要随机从输入的数据集合X中选取K个特征向量作为初始聚类中心；

    然后, 根据该聚类中心集合对每个数据点使用目标函数计算隶属度矩阵U；

    再通过更新后的隶属度矩阵U重新计算新的聚类中心; 迭代计算该流程直到收敛, 最后将聚类中心C输出并作为EM算法中的初始μ输入.

    获得初始μ后根据初始μ={μ1,μ2,…,μn}和特征向量X={x1,x2,…,xn}计算

    即完成了EM算法的初始化.

    改进的期望最大化算法(IEM)流程如下.

    算法3改进的期望最大化算法.

    输入：X,c,m,e;

    输出：πnew,μnew,εnew;

    whileU,C=FCM(X,c,m,e) do formula (5),(10) and

    2.1 数据属性

    本文采用数据集UCI User Knowledge Modeling(http://archive.ics.uci.edu/ml/datasets/User+Knowledge+Modeling), 其通过数据集下5个相关属性(STG,SCG,STR,LPR,PEG)衡量直流电机学科学生的学习状况[13]. 该数据集相关属性列于表1. 将数据集中的5个属性作为特征向量X={x1,x2,…,x5}输入到FCM,K-means,EM和IEM模型中, 对用户知识水平进行聚类分析.

    表1 数据集UCI User Knowledge Modeling相关属性

    2.2 模型与数据的结合

    针对本文的研究目标, 即对用户知识水平的聚类分析, 本文在测试这些算法的聚类效果时, 将数据集的5个属性作为特征向量输入到模型中. 由于数据集中所有数据按标签列(UNS列)分为4类, 即所有数据共有4种类型, 故将算法的聚类中心数目设为4个.

    考虑EM算法参数, 由于π,μ,ε在初始状态下未知, 因此本文在测试原始EM算法时使用随机分配的π,μ,ε值初始化EM算法. 根据FCM算法的参数, 除固定的特征向量空间X、 聚类中心个数C外, 模糊常数m也会影响其最终的分类效果, 考虑到模糊常数m是一种与实际数据相关的经验变量, 虽然从聚类有效性角度得出m的取值范围为1.5≤m≤2.5, 但具体的最优值只能通过测试寻找.

    对于模型结果的评价, 考虑到本文所使用的数据集具有参考类别, 故可使用外部聚类指标进行评价, 选取JC,FMI,RI三个主流的外部指标作为本文结果的评价指标[14]. 其中：
    JC表示Jaccard系数, 其含义为参考集合与聚类集合的交集大小与并集大小的比值, 即所有属于同一参考类中的样本与在聚类结果中属于同类样本对所占比例, 其公式为

    (19)

    FMI表示聚类结果中和参考集合同类的样本比例与参考集合中和聚类结果同类的样本比例的几何平均数, 其公式为

    (20)

    RI表示聚类结果和参考集合中属于同类样本与不属于同类样本占所有样本的比例, 其公式为

    (21)

    这里a表示在聚类结果中与参考集合和真实集合中属于同类的数据样本数量,b表示在聚类结果中与参考集合不属于同类且聚类结果与真实集合同类的数据样本数量,c表示在聚类结果中与参考集合不属于同类且参考集合与真实集合同类的数据样本数量,d表示聚类结果中既不和参考集合同类又不和真实集合同类的数据样本数量,m(m-1)/2表示样本的总数量. 上述3个外部指标的取值范围均为[0,1], 且其值越大表示聚类的效果越贴近真实集合的类别分布.

    本文在以聚类中心数为4的前提下, 使用数据集UCI User Knowledge Modeling作为样本, 分别在m=1.5,2,2.5情形下重复测试100次, 评价指标JC,FMI,RI的平均值列于表2. 由表2可见, 在特征向量、 聚类中心数不变的情形下,m=1.5和m=2的JC,FMI,RI值相差较小, 且其JC,FMI值均明显低于m=2.5的JC,FMI值, 仅有RI值略高于m=2.5, 因此当m=2.5时FCM模型的性能达到最优, 故本文在实例仿真时模糊常数m取值为2.5.

    表2 不同模糊常数下的FCM模型平均指标

    2.3 实例仿真与结果分析

    将数据集UCI User Knowledge Modeling的数据样本输入FCM,K-means,EM,IEM 4种无监督聚类算法中进行实例仿真实验, 仿真结果列于表3. 由表3可见: 本文IEM算法在JC指标上， 高于FCM和EM算法约19%, 高于K-means算法约30%；

    在FMI指数上， IEM算法高于FCM和EM算法约13%, 高于K-means算法约23%；

    在RI指数上, IEM算法高于FCM和K-mean算法约9%, 高于EM算法约5%. 从而验证了本文IEM算法在用户知识建模的聚类任务中效果明显优于其他传统聚类算法, 其主要原因是本文算法结合了FCM算法柔性划分的特性, 能根据数据分布最优化混合高斯模型的初始参数, 使其在最大程度上避免陷入局部最优的陷阱.

    表3 不同算法对数据集UCI User Knowledge Modeling的仿真结果

    综上所述, 本文针对使用传统期望最大化算法进行参数估计的混合高斯模型的最终聚类效果过于依赖初始概率密度中心的问题, 使用模糊C均值初始化EM算法的模型参数改进EM算法, 并将改进后的EM算法应用于无监督聚类任务中, 最后通过无监督聚类的性能评价指标JC,FMI和RI验证该改进算法的性能. 通过数据集UCI的仿真实验结果表明, 本文算法的JC,FMI,RI指标均较原始FCM和EM算法有较大提高, 从而验证了IEM算法在无监督聚类任务中效果较传统聚类算法更优.

    猜你喜欢 高斯聚类混合 混合宅现代装饰(2022年5期)2022-10-13一种傅里叶域海量数据高速谱聚类方法北京航空航天大学学报(2022年8期)2022-08-31基于知识图谱的k-modes文本聚类研究南京理工大学学报(2022年1期)2022-03-17一种改进K-means聚类的近邻传播最大最小距离算法计算机应用与软件(2021年7期)2021-07-16基于模糊聚类和支持向量回归的成绩预测华东师范大学学报（自然科学版）(2019年5期)2019-11-11数学王子高斯小天使·二年级语数英综合(2019年4期)2019-10-06混合运算大篷车学苑创造·A版(2019年8期)2019-08-15从自卑到自信 瑞恩·高斯林电影故事(2015年16期)2015-07-14

    相关热词搜索：最大化 算法 期望

    • 范文大全
    • 说说大全
    • 学习资料
    • 语录
    • 生肖
    • 解梦
    • 十二星座
    最新文章

    推荐访问

    最大化 期望 算法 算法实践与创新论文 算法工程师主要工作 算法工程师具体工作做什么 算法工程师培训 算法工程师工作流程 算法工程师工作职责描述 算法工程师工作职责描述怎么写 算法工程师工作职责描述简短 算法工程师干啥的 算法工程师的工作 算法工程师的工作内容 算法工程师职位描述

    本文一种改进的期望最大化算法由百花范文网整理提供，版权归原作者、原出处所有。

    Copyright © 百花范文网 All Rights Reserved.