法律状态公告日
法律状态信息
法律状态
2022-07-22
公开
发明专利申请公布
技术领域
本发明涉及计算机技术领域,尤其涉及一种基于图优化的多视图谱聚类方法及系统。
背景技术
随着信息提取技术的快速发展,多视图数据已广泛应用于许多领域。例如,一个句子可以用不同的声音说话;一篇文章可以翻译成几种语言;一个对象可以从不同的角度观察,等等。多视图数据的异构性给其聚类带来了挑战。在针对多视图的聚类方法中,基于图论的方法颇受关注。这种方法的目的是通过最小化簇间的相似性和最大化簇内的相似性来切割构建的相似图。相似图可以从不同的视图中学习,而切割方法通常通过对相似图执行谱聚类(通常包括两个独立的过程,即谱嵌入和离散化)来完成。
现有技术中,有研究通过使用局部流形融合学习加权图,集成了所有视图的信息,但事实证明,加权项中的参数对最终性能非常关键。为了学习每个视图的最佳权重,有研究重新制定了标准谱学习模型,并设计了计算谱嵌入的无参数自动加权方法。还有研究通过交叉视图图扩散从多视图数据中学习了统一的图,一旦获得了统一图,就可以通过对谱嵌入进行k-均值算法来生成聚类标签。
尽管多视图聚类中的图学习取得了很大的进展,但它在多阶段过程中的性能仍然显示出明显的局限性:在这样的框架下,对每个阶段目标函数的优化都是独立的,从而降低了最终的聚类性能。就特定目标而言,每个视图的图都是在线性空间中独立学习的;要从多个视图中融合图,通常需要额外的参数,而参数选择会影响聚类性能,从而难以同时对所有特定任务有效。
发明内容
为了解决这些问题,本发明的目的是提出了一种基于图优化的多视图谱聚类(MSCGO)框架来同时学习和划分一个统一的图,通过保留了核空间中数据的局部结构,并自动集成了来自多个视图的信息,有效地提高了聚类性能。
为了实现上述技术目的,本发明提供了一种基于图优化的多视图谱聚类方法,包括以下步骤:
通过交替迭代优化方法对多视图数据集进行聚类,生成融合图;
基于数据集,构建数据相似矩阵,数据相似矩阵用于获取特征点之间在每个视图的相似性;
基于数据相似矩阵,设计用于聚类的目标函数和约束条件;
基于交替迭代优化方法,对目标函数进行迭代处理,直至目标函数收敛或达到最大迭代次数;
获取迭代处理后针对数据相似矩阵生成的数据类别指示向量和融合图。
优选地,在构建数据相似矩阵的过程中,相似矩阵包含数据在各个视图内的相似性;
优选地,在设计用于聚类的目标函数和约束条件的过程中,目标函数表示为:
其中,K表示邻居数、K
优选地,在设计用于聚类的目标函数和约束条件的过程中,约束条件为:
优选地,在对目标函数进行迭代处理的过程前,对目标函数进行初始化,其中,用于初始化的参数包括权重参数λ
优选地,在对目标函数进行迭代处理的过程中,固定其他参数,分别对待优化变量进行优化,直至目标函数收敛或达到最大迭代次数,生成优化后的类别指示矩阵Y和融合图。
优选地,在分别对待优化变量进行优化的过程中,优化Z
优化R的过程包括:
s.t.R
其中,
优化F的过程包括:
s.t.F
其中,
优化α
优化Y的过程包括:
s.t.Y∈Ind,其中,G=FR。
优选地,在优化F的过程中,通过迭代法对F进行优化,具体包括以下步骤:
步骤a.计算L的最大特征值σ,定义临时矩阵L
步骤b.计算临时矩阵
步骤c.计算临时矩阵M=2L
步骤d.对临时矩阵M进行奇异值分解,使得M=USV
步骤e.更新F=UV
优选地,在优化Y的过程中,Y的更新方式为逐行更新,更新方式表示为:
本发明还公开了一种基于图优化的多视图谱聚类系统,包括:
数据收集模块,用于收集若干视图;
第一数据处理模块,用于根据多视图数据集生成数据相似矩阵,数据相似矩阵用于获取特征点之间在每个视图的相似性;
第二数据处理模块,用于基于数据相似矩阵,设计用于聚类的目标函数和约束条件;基于交替迭代优化方法,对目标函数进行迭代处理,直至目标函数收敛或达到最大迭代次数;
聚类模块,用于通过获取迭代处理后针对数据相似矩阵生成的数据类别指示向量和多视图数据集的融合图。
本发明公开了以下技术效果:
相对于现有技术而言,本发明提出了一个联合框架,即MSCGO,来学习保留核空间中数据局部结构的图,并通过集成多个视图的信息来直接划分图;由于在优化过程中算法可以生成临时的数据类别划分,因此一个主要益处是,数据的团簇结构可反馈到图的学习过程中,同时,端到端的设计避免了一些多视图聚类方法中存在的多阶段优化的缺陷;此外,MSCGO采用交替迭代方法以生成稳定的聚类,避免了随机性;本发明提到的方法,相对于数据划分的传统技术而言,准确度提高至少10%。
附图说明
为了更清楚地说明本发明实施例或现有技术中的技术方案,下面将对实施例中所需要使用的附图作简单地介绍,显而易见地,下面描述中的附图仅仅是本发明的一些实施例,对于本领域普通技术人员来讲,在不付出创造性劳动性的前提下,还可以根据这些附图获得其他的附图。
图1为本发明所述的步骤流程图。
图2为本发明所述的聚合效果图。
具体实施方式
下为使本申请实施例的目的、技术方案和优点更加清楚,下面将结合本申请实施例中附图,对本申请实施例中的技术方案进行清楚、完整地描述,显然,所描述的实施例仅仅是本申请一部分实施例,而不是全部的实施例。通常在此处附图中描述和示出的本申请实施例的组件可以以各种不同的配置来布置和设计。因此,以下对在附图中提供的本申请的实施例的详细描述并非旨在限制要求保护的本申请的范围,而是仅仅表示本申请的选定实施例。基于本申请的实施例,本领域技术人员在没有做出创造性劳动的前提下所获得的所有其他实施例,都属于本申请保护的范围。
如图1-2所示,本发明提供了一种基于图优化的多视图谱聚类方法,包括以下步骤:
通过交替迭代优化方法对多视图数据集进行聚类,生成融合图;
基于数据集,构建数据相似矩阵,数据相似矩阵用于获取特征点之间在每个视图的相似性;
基于数据相似矩阵,设计用于聚类的目标函数和约束条件;
基于交替迭代优化方法,对目标函数进行迭代处理,直至目标函数收敛或达到最大迭代次数;
获取迭代处理后针对数据相似矩阵生成的数据类别指示向量和融合图。
进一步优选地,在构建数据相似矩阵的过程中,数据相似矩阵包含数据在各个视图内的相似性
进一步优选地,在设计用于聚类的目标函数和约束条件的过程中,目标函数表示为:
其中,k表示邻居数、K
进一步优选地,在设计用于聚类的目标函数和约束条件的过程中,约束条件为:
进一步优选地,在对目标函数进行迭代处理的过程前,对目标函数进行初始化,其中,用于初始化的参数包括权重参数λ
进一步优选地,在对目标函数进行迭代处理的过程中,固定其他参数,分别对待优化变量进行优化,直至目标函数收敛或达到最大迭代次数,生成优化后的类别指示矩阵Y和融合图。
进一步优选地,在分别对待优化变量进行优化的过程中,
优化Z
优化R的过程包括:
s.t.R
其中,
优化F的过程包括:
s.t.F
其中,
优化α
优化Y的过程包括:
s.t.Y∈Ind,
其中,G=FR。
进一步优选地,在优化F的过程中,通过迭代法对F进行优化,具体包括以下步骤:
步骤a.计算L的最大特征值σ,定义临时矩阵L
步骤b.计算临时矩阵
步骤c.计算临时矩阵M=2L
步骤d.对临时矩阵M进行奇异值分解,使得M=USV
步骤e.更新F=UV
进一步优选地,在优化Y的过程中,Y的更新方式为逐行更新,更新方式表示为:
本发明还公开了一种基于图优化的多视图谱聚类系统,包括:
数据收集模块,用于收集若干视图;
第一数据处理模块,用于根据多视图数据集生成数据相似矩阵,数据相似矩阵用于获取特征点之间在每个视图的相似性;
第二数据处理模块,用于基于数据相似矩阵,设计用于聚类的目标函数和约束条件;基于交替迭代优化方法,对目标函数进行迭代处理,直至目标函数收敛或达到最大迭代次数;
聚类模块,用于通过获取迭代处理后针对数据相似矩阵生成的数据类别指示向量和多视图数据集的融合图。
图2表示在两个合成数据集上的实验,第一(第二)行显示不同视图上的双月(三环)数据集。第一(第二)列显示视图1(2)上的数据集。不同的标记代表我们的方法划分的不同团簇。
本发明提出的聚类过程包括以下几个步骤:
步骤1、输入原始数据矩阵和聚类类别数,初始化所有参数和待优化变量;
设数据集X有V个视图,
需初始化的参数包括权重参数λ
需初始化的待优化变量包括各个视图的图Z
步骤2、设计基于图优化的多视图谱聚类优化问题,写出目标函数和约束条件;
目标函数和约束条件为:
其中,
步骤3、通过交替迭代优化方法对得到的目标函数进行求解;通过交替优化方法解决上述优化问题,如下所示:
1)固定其他参数优化Z
令
其中,
(·)
2)固定其他参数优化R,此时问题转化为以下等价问题:
s.t.R
其中,
R=VU
此处矩阵U,V通过对M进行奇异值分解得到,即M=USV
3)固定其他参数优化F,此时问题转化为以下等价问题:
s.t.F
其中,
a.计算L的最大特征值σ,定义临时矩阵L
b.计算临时矩阵
c.计算临时矩阵M=2L
d.对临时矩阵M进行奇异值分解,使得M=USV
e.更新F=UV
重复步骤c-e直至收敛或达到最大迭代次数。
4)固定其他参数优化α
α
5)固定其他参数优化Y,此时问题转化为以下等价问题:
s.t.Y∈Ind,
其中G=FR。Y的更新方式为逐行更新。对于第i行,更新后仅有一个元素
步骤4、按照步骤3更新待优化变量直至目标函数收敛或达到最大迭代次数;
步骤5、从优化生成的类别指示矩阵Y得到聚类结果。
本实施例在两个人工数据集上的聚类效果在图1中予以体现。以上所述仅为本发明的较佳实施例,凡依本发明申请专利范围所做的均等变化与修饰,皆应属本发明的涵盖范围。
本发明的效果可以通过以下仿真实验做进一步的说明。
1.仿真条件:
本发明是在中央处理器为Intel Core i7-9700K CPU、内存16G、Windows10操作系统上,运用MATLAB软件进行的仿真。
2.仿真内容:
仿真中使用的数据为来自都柏林大学研究者整理的BBC新闻文本数据集和哥伦比亚大学图像库的COIL-20数据集。两个数据集均已知类别的真实划分,可以作为算法生成划分的评判标准。
本专利选择了近年来的AASC、SMSC、MVGL、MCGC、GMC、SwMC和CGD作为对比算法。MSCGO为本专利得到的结果,本专利以ARI作为聚类质量的评判指标(ARI越大说明聚类效果越好),对比结果如表1所示(最优结果粗体显示):
表1
从表1可见,在两种不同类型的数据集上,本专利的数据划分质量要明显优于其它算法。相比于现有方法,本发明的方法对数据划分的准确度提高可超过10%。
应注意到:相似的标号和字母在下面的附图中表示类似项,因此,一旦某一项在一个附图中被定义,则在随后的附图中不需要对其进行进一步定义和解释,此外,术语“第一”、“第二”、“第三”等仅用于区分描述,而不能理解为指示或暗示相对重要性。
最后应说明的是:以上所述实施例,仅为本发明的具体实施方式,用以说明本发明的技术方案,而非对其限制,本发明的保护范围并不局限于此,尽管参照前述实施例对本发明进行了详细的说明,本领域的普通技术人员应当理解:任何熟悉本技术领域的技术人员在本发明揭露的技术范围内,其依然可以对前述实施例所记载的技术方案进行修改或可轻易想到变化,或者对其中部分技术特征进行等同替换;而这些修改、变化或者替换,并不使相应技术方案的本质脱离本发明实施例技术方案的精神和范围。都应涵盖在本发明的保护范围之内。因此,本发明的保护范围应所述以权利要求的保护范围为准。
机译: 一种计算机实现的方法,用于通过生成对象的粗略几何图形,计算优化(其中该优化包括视差图优化和表面优化)以及基于优化来优化粗略几何图形来生成对象的三维模型。
机译: 基于谱聚类提供局部建议的系统和方法
机译: 基于用于视点切换的预测结构的多视图视频编码的方法和设备,以及用于基于视点切换的预测结构的多视图视频解码的方法和设备