首页> 中国专利> 基于混合公共因子分析器的分布式高维数据分类方法

基于混合公共因子分析器的分布式高维数据分类方法

摘要

本发明公开了基于混合公共因子分析器的分布式高维数据分类方法,该方法通过网络中不同节点之间的协作,以分布式方式实现高维数据的分类。各个节点处用混合公共因子分析器来建模其高维数据的分布,整个分类分成训练和识别两个部分。在训练过程中,首先进行模型参数的初始化和局部计算,然后将计算好的三组中间变量进行广播扩散,当节点收到其邻居节点广播来的中间变量时,计算联合统计量并完成参数的估计,该过程不断迭代直至收敛。在识别阶段,待分类的数据输入任一节点,计算其关于训练出的每一类数据所对应的模型的对数似然值,将最大对数似然值对应的类别作为识别结果。采用本方法可以实现高维数据的分布式降维,网络中的每个节点都获得较高并且一致的分类性能,此外节点间只传输交互中间变量可以有效地保护数据的隐私。

著录项

  • 公开/公告号CN105550704A

    专利类型发明专利

  • 公开/公告日2016-05-04

    原文格式PDF

  • 申请/专利权人 南京邮电大学;

    申请/专利号CN201510916426.6

  • 发明设计人 魏昕;丁平船;张胜男;周亮;

    申请日2015-12-10

  • 分类号G06K9/62(20060101);

  • 代理机构32207 南京知识律师事务所;

  • 代理人汪旭东

  • 地址 210023 江苏省南京市栖霞区文苑路9号

  • 入库时间 2023-12-18 15:54:55

法律信息

  • 法律状态公告日

    法律状态信息

    法律状态

  • 2019-01-01

    授权

    授权

  • 2018-11-30

    著录事项变更 IPC(主分类):G06K9/62 变更前: 变更后: 申请日:20151210

    著录事项变更

  • 2016-06-01

    实质审查的生效 IPC(主分类):G06K9/62 申请日:20151210

    实质审查的生效

  • 2016-05-04

    公开

    公开

说明书

技术领域

本发明涉及一种基于混合公共因子分析器的分布式高维数据分类方法,属于数据处理与应用的技术领域。

背景技术

随着采集和存储技术的不断发展,数据的维度和数量不断增大,高维大数据不断涌现。例如,基于内容的大规模图像检索和文档检索中屡见不鲜的人脸图像、视频和网页文本、语音与音频信号处理中不可避免出现的高维特征矢量、生物信息学中对生物组织进行聚类分析中的基因数据等。很显然,维度越高,数据量越大,可以更加全面地刻画所描述的对象以及更好地分辨对象。然而,过高的维度、过大的数据量带来了极高的处理和传输负担,特别是在传感器网络中,单个节点的存储、处理和传输通信能力都十分有限,因此,对数据的分析与处理方法的设计提出了新的更高的要求和挑战。具体而言,一方面,对于高维度数据或特征而言,传统的模型和及其估计算法容易出现“维数灾难”问题,使得相关问题难以理解和表示,更不可能实现可视化。因此,如何实现对高维数据准确、高效地分析与处理,已经成为一个极具挑战性的基础研究问题;另一方面,当数据量很大的时候,单个传感器节点往往无法完成数据的分析和处理任务,此时可以将大数据分成不同的部分,分别存储在多个传感器节点上,通过合理的通信和协作,共同完成指定的任务。如何针对大数据设计协作处理策略,也是亟待解决的问题。

分类是指通过一定的方法将数据分成多个类的过程,在机器学习领域,对数据的分类是一个有监督学习的过程。在现有的文献和专利中,已经出现了大量分类的方法,但是当数据量很大或者单个节点处理能力有限的情况下,需要将数据分布在多个节点上,此时如何完成分布式处理,十分关键。因此,本专利所提出的方法正是为了解决这一问题,设计一种基于混合公共因子分析器的分布式高维数据分类方法(1)混合因子分析模型可以有效的处理高维数据;(2)通过设计节点间协作方式,只传输中间结果就可以获得满意的聚类结果,与传输原始数据方式相比,既减小了通信的开销,又保护了数据上的隐私信息,确保了网络中的数据安全。

发明内容

本发明目的在于解决了上述现有技术的缺陷,提出了一种基于混合公共因子分析器的分布式高维数据分类方法,该方法包括如下步骤:

步骤1:数据的采集;

设有M个节点组成一个网络,每个节点采集到的数据来自V个类,数据维度为p。其中,节点m采集到的所有数据中,来自第v个类的数据集为其中表示节点m处,来自第v个类的第n个数据,为数字第v个类的训练数据个数;此外,节点m的邻居节点集合表示为Rm

步骤2,训练:对于所有节点中来自于第v个类的数据用混合公共因子分析器(MCFA)来描述其分布,并且采用分布式方式完成模型的训练,估计出参数>Θ(v)={{wg(v),ξg(v),Ωg(v)}g=1G,L(v),E(v)}(v=1,...,V);>以同样的方式,估计出每一类数据所对应的MCFA的参数集Θ(v)(v=1,...,V),训练过程完成;

步骤3,识别:当网络中的任一节点采集到新的用于识别的数据x'时,计算x'关于Θ(v)(v=1,...,V)的对数似然值logp(x'|Θ(v))(v=1,...,V):

>log>p(x|Θ(v))=Σn=1Nmlog(Σg=1Gwg(v)×N(x|L(v)ξg(v),L(v)Ωg(v)(LT)(v)+E(v)));>

将最大对数似然值对应的序号作为x'的识别结果v':

>v=arg>maxv=1Vlog>p(x|Θ(v)).>

本发明步骤2所述针对第v个类的数据的训练的过程包括如下:

为了表示简洁,并且不会影响理解和实施,省略中的上标“(v)”)。

步骤2-1,初始化:设定MCFA中的参数初始值其中,各节点处的(w1,...,wg,...,wG)=(1/G,...,1/G,...,1/G);L和E矩阵中的每一个元素都从标准正态分布N(0,1)中生成;{ξ1,...,ξg,...,ξG}中的每个元素都从标准正态分布N(0,1)中生成;Ω1=...=Ωg=...=ΩG=Iq,其中Iq为(q×q)的单位矩阵。

步骤2-2,广播数据个数:每个节点l(l=1,2,...,M)将其采集到的数据个数Nl广播给其邻居节点。当某个节点m收到它的所有邻居节点广播来的数据个数之后,该节点计算权重系数clm

>clm=NlΣlRmNl,>

此外,迭代计数器iter=1,开始迭代过程;

步骤2-3,局部计算:在传感器网络中的每个节点l处,根据当前的节点处的数据Xl和上一次迭代之后估计出的参数值Θold,即(当iter=1时,Θold为初始化之后的参数值),计算出al,n,g,bg,hg其公式为:

>al,n,g=rl,n,gΣg=1Grl,n,g>

其中,>rl,n,g=wgoldN(xl,n|Loldξgold,LoidΩgold(Lold)T+Eold),>

>hg=[LoldΩgold(Lold)T+Eold]-1·Lold·Ωgold>

>bg=ξgold-hgTLoldξgold>

>Λg*=(Ig-hgTLold)Ωgold>

步骤2-4,广播扩散:传感器网络中的每个节点l把计算出三组中间变量,即:

>Σn=1Nlal,n,g,Σn=1N1al,n,gxl,n,Σn=1Nlal,n,gxl,nxl,nT(g=1,...,G),>放在一个数据包内,然后向其他节点广播扩散该数据包。

步骤2-5,联合计算:当节点m(m=1,...,M)收到来自其所有邻居节点l(l∈Rm)发来的含有中间变量的数据包之后,计算联合统计量即:

>Sm,g(1)=ΣlRmclm·Σn=1Nlal,n,g,Sm,g(2)=ΣlRmclm·Σn=1N1al,n,gxl,n>

>Sm,g(3)=ΣlRmclm·Σn=1Nlal,n,gxl,nxl,nT>

步骤2-6,参数估计:节点m(m=1,...,M)根据步骤2-5计算出的联合统计量和步骤2-3计算出的估计出>Θ={{wg,ξg,Ωg}g=1G,L,E},>即:

>wg=Sm,g(1)Σg=1GSm,g(1)>

>ξg=bgSm,g(1)+hgTSm,g(2)Sm,g(1)>

>Ωg=2hgTSm,g(2)(bg-ξg)T+hgSm,g(3)hgTSm,g(1)+Λg*+ξgξgT+bgbgT-2bgξgT>

>L=Σg=1G(Sm,g(2)bgT+Sm,g(3)hg)Σg=1GSm,g(1)(Λg*+bgbgT)+2hgTSm,g(2)bgT+hgTSm,g(3)hg>

>E=diag{1Σg=1GSm,g(1)×Σg=1G[Sm,g(1)L(Λg*+bgbgT)LT+(2LhgT-2Ip)Sm,g(2)bgTL+(LhgT-2Ip)×Sm,g(3)hgLT+Sm,g(3)]}}>

步骤2-7,判别收敛:节点m(m=1,...,M)计算当前迭代下的对数似然值,即:

>log>p(Xm|Θnew)=Σn=1Nmlog(Σg=1Gwg×N(xm,n|g,gLT+E))>

其中Θnew表示当前迭代估计出的参数值,Θold表示上一次迭代中的估计参数值。如果logp(Xmnew)-logp(Xmold)<ε,其中ε=10-5,节点m进入终止状态。否则,转向步骤

2-3开始下一次迭代。

经过上述步骤2-1~步骤2-7之后,估计出Θ(v)

本发明方法应用于数据的并行分布式处理。

有益效果:

1.本发明采用的混合公共因子分析器能够对高维数据进行降维,从而在降维的同时顺利完成数据的建模,获得更好的分类性能,并且降低了运算复杂度。此外,本发明只传输中间计算结果而非原始数据,极大地保护了传输数据的隐私。

2.本发明采用的基于混合公共因子分析器的训练与识别过程,使得网络中的各个节点可以充分利用其它节点的数据中所包含的信息,使得分类性能极大地优于集中式方法。

附图说明

图1为本发明涉及的基于混合公共因子分析器的分布式高维数据分类方法的流程图。

图2为本发明所涉及的方法和其他方法的分类性能的定性比较结果示意图。

图3为本发明所涉及的方法和其他方法的分类性能的定量比较结果示意图。

具体实施方式

下面结合说明书附图对本发明创造作进一步的详细说明。

如图1-3所示,本发明提供了一种基于混合公共因子分析器的分布式高维数据分类方法,该方法包括如下步骤:

步骤1:数据的采集;

设有M台计算机/计算节点(即:节点),组成一个网络,每个节点采集到的数据来自V个类,数据维度为p。其中,节点m采集到的所有数据中,来自第v个类的数据集为其中表示节点m处,来自第v个类的第n个数据,为数字第v个类的训练数据个数。

此外,每个节点的数据传输范围设为Dis,对于当前节点m,所有与其距离小于Dis的节点为其邻居节点,节点m的邻居节点集合表示为Rm。在本发明中,节点之间的连接关系(网络拓扑)事先确定好,只需要保证任意两个节点之间至少存在一条直接或经多跳可以到达的路径即可。

步骤2:训练;

对于所有节点中来自于第v个类的数据集用混合公共因子分析器(mixtureofcommonfactoranalyzers,简称MCFA)来描述其分布。与第v个类相关的MCFA模型其参数集为其中为混合权值,满足(q维矢量)和((q×q)矩阵)分别为与p维数据对应的q维因子所服从的高斯分布的均值和协方差矩阵,q取p/2~p/8之间的任意整数。采用如下的分布式方式完成训练,具体训练过程如下(这里以第v类数据的训练过程为例,为了表示简洁,并且不会影响理解和实施,下面的步骤中略去中的上标“(v)”):

步骤2-1,初始化:设定MCFA中的参数初始值其中,各节点处的(w1,...,wg,...,wG)=(1/G,...,1/G,...,1/G);L和E矩阵中的每一个元素都从标准正态分布N(0,1)中生成;{ξ1,...,ξg,...,ξG}中的每个元素都从标准正态分布N(0,1)中生成;Ω1=...=Ωg=...=ΩG=Iq,其中Iq为(q×q)的单位矩阵。

步骤2-2,广播数据个数:每个节点l(l=1,2,...,M)将其采集到的数据个数Nl广播给其邻居节点。当某个节点m收到它的所有邻居节点广播来的数据个数之后,该节点计算权重系数clm

>clm=NlΣlRmNl>

该权重的含义为用于衡量节点m的各邻居节点l(l∈Rm)每次传输的信息在节点m处的重要性。此外,迭代计数器iter=1,开始迭代过程。

步骤2-3,局部计算:在传感器网络中的每个节点l处,根据当前的节点处的数据Xl和上一次迭代之后估计出的参数值Θold(当iter=1时,Θold为初始化之后的参数值),计算出al,n,g,bg,hg

>al,n,g=rl,n,gΣg=1Grl,n,g>

其中,>rl,n,g=wgoldN(xl,n|Loldξgold,LoidΩgold(Lold)T+Eold),>即:

>hg=[LoldΩgold(Lold)T+Eold]-1·Lold·Ωgold>

>bg=ξgold-hgTLoldξgold>

>Λg*=(Ig-hgTLold)Ωgold>

步骤2-4,广播扩散:传感器网络中的每个节点l把计算出三个中间变量,即:

>Σn=1Nlal,n,g,Σn=1N1al,n,gxl,n,Σn=1Nlal,n,gxl,nxl,nT(g=1,...,G)>放在一个数据包内,然后向其他节点广播扩散该数据包。

步骤2-5,联合计算:当节点m(m=1,...,M)收到来自其所有邻居节点l(l∈Rm)发来的含有中间变量的数据包之后,计算联合统计量即:

>Sm,g(1)=ΣlRmclm·Σn=1Nlal,n,g,Sm,g(2)=ΣlRmclm·Σn=1N1al,n,gxl,n>

>Sm,g(3)=ΣlRmclm·Σn=1Nlal,n,gxl,nxl,nT>

步骤2-6,参数估计:节点m(m=1,...,M)根据步骤(5)计算出的联合统计量和步骤(3)计算出的估计出>Θ={{wg,ξg,Ωg}g=1G,L,E}>

>wg=Sm,g(1)Σg=1GSm,g(1)>

>ξg=bgSm,g(1)+hgTSm,g(2)Sm,g(1)>

>Ωg=2hgTSm,g(2)(bg-ξg)T+hgSm,g(3)hgTSm,g(1)+Λg*+ξgξgT+bgbgT-2bgξgT>

>L=Σg=1G(Sm,g(2)bgT+Sm,g(3)hg)Σg=1GSm,g(1)(Λg*+bgbgT)+2hgTSm,g(2)bgT+hgTSm,g(3)hg>

>E=diag{1Σg=1GSm,g(1)×Σg=1G[Sm,g(1)L(Λg*+bgbgT)LT+(2LhgT-2Ip)Sm,g(2)bgTL+(LhgT-2Ip)×Sm,g(3)hgLT+Sm,g(3)]}}>

步骤2-7,判别收敛:节点m(m=1,...,M)计算当前迭代下的对数似然值,即:

>log>p(Xm|Θnew)=Σn=1Nmlog(Σg=1Gwg×N(xm,n|g,gLT+E))>

其中Θnew表示当前迭代估计出的参数值,Θold表示上一次迭代中的估计参数值。如果logp(Xmnew)-logp(Xmold)<ε,其中ε=10-5,节点m进入终止状态。否则,转向步骤2-3开始下一次迭代。

本发明经过步骤2-1~步骤2-7之后,估计出Θ(v)。以同样的方式,估计出每一类数据所对应的MCFA的参数集Θ(v)(v=1,...,V),训练过程完成。

步骤3:识别;当网络中的任一节点(假设为节点m)采集到新的用于识别的数据x'时,计算x'关于Θ(v)(v=1,...,V)的对数似然值logp(x'|Θ(v))(v=1,...,V),即:

>log>p(x|Θ(v))=Σn=1Nmlog(Σg=1Gwg(v)×N(x|L(v)ξg(v),L(v)Ωg(v)(LT)(v)+E(v)));>

将最大对数似然值对应的序号作为x'的识别结果v':

>v=arg>maxv=1Vlog>p(x|Θ(v)).>

本发明的性能评价包括如下:

设有15个节点,组成一个网络,保证网络中任意两个节点之间可以直接或间接进行通信。将UCI数据集中采集到的3844个0~9手写数字训练数据随机分配到20个节点上,训练数据的特征为该数字手写轨迹上等间隔地取8个点的二维坐标组成,共16维。那么,M=15,p=16,q取6,采用本发明所述的训练方法,得到Θ(0)(1),...,Θ(9)。训练完成后,为了测试所有节点的总体识别率,将每个测试数据x'(总共3500个)分别在所有节点上,采用本发明所述的识别过程进行识别。由于待识别的数字真实值已知,将采用本发明所涉及的识别方法和其真值进行比较,得到识别正确率(即:识别正确率=所有节点正确识别的手写数字的数量/(15*3500)),从而可以评价和衡量出本发明所涉及的方法的有效性和准确性。

为了比较本发明提出的基于MCFA的分布式分类方法(简称D-MCFA)和其他方法的性能,这里和基于MCFA的集中式手写数字识别方法(简称C-MCFA),基于MCFA的各节点间无协作的手写数字识别方法(简称N-MCFA),基于分布式高斯混合模型的手写数字识别方法(简称D-GMM)进行比较。需要说明的是,在C-MCFA中,所有节点需要将原始数据传输给某个中心节点,由中心节点采用传统的MCFA来完成训练和识别,而后再把结果回传给各节点,这种方式在实际中用的很少,一是传输原始数据通信开销很大,一旦出现丢包或数据包损坏,对最后的识别性能影响很大,二是不利于数据中的隐私保护,网络安全堪忧。识别结果分别用定性和定量两种方式来表示。在结果的定性表示中,采用混淆矩阵的hinton图,如图2所示。在该图中,各列表示数字0~9的识别结果而各行表示数字0~9的真值。主对角线上的小方块表示正确识别的情况,小方块的尺寸越大表明正确该识别的数字越多,而其他位置上出现小方块表明存在错误识别的情况。由该图可以看出,C-MCFA和本发明的D-MCFA(这里只给出其中的一个节点,其他节点结果相同)性能较好,而D-GMM性能较差,最差的是N-MCFA。在结果的定量表示中,采用识别率的均值和方差两个指标,如图3所示。在该图中,本发明设计的D-MCFA的识别正确率和方差与C-MCFA基本相同,并且各个节点识别正确率的方差较低,而N-MCFA和D-GMM识别正确率和方差性能都较差。此外,将采用分布式本发明所采用的D-MCFA和现有的基于t混合因子分析的分布式手写数字识别方法进行比较,结果表明本发明方法的识别率与基于t混合因子分析的分布式手写数字识别方法识别性能相当,但是D-MCFA完成训练所需的时间为180秒,而基于t混合因子分析的分布式手写数字识别方法完成训练所需时间为420秒,因此,D-MCFA提高了运算速度。

去获取专利,查看全文>

相似文献

  • 专利
  • 中文文献
  • 外文文献
获取专利

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号