技术领域
本发明涉及信号处理、数据分析技术领域,尤其涉及基于高阶关联保持的缺失多视图子空间聚类方法及系统。
背景技术
随着信息获取技术的发展,多媒体数据,如:文本,音频,图像,视频等,通常能从现实应用场景中的多种来源获取。例如:在多媒体图像检索任务中,颜色、纹理和边缘可以被用来描述图像;在视频场景分析任务中,不同拍摄角度的摄像机可以为同一个场景的场景分析提供更多信息。此类型的数据被称之为多视图数据,随之产生了一系列的多视图学习算法,如:跨视图领域自适应、多视图聚类、多视图异常点检测等。数据语义信息的获取是多媒体数据挖掘中的一个重要研究课题。多视图聚类以无监督的方式分析数据的多视图特征,以捕获数据的内在类簇信息,在近些年来得到越来越多的关注。
在许多现实应用中,多视图数据可能会存在某些视图中的数据样本由于某些原因而造成缺失。例如,当我们处理跨语言文档聚类任务时,往往不是所有文档都被翻译成不同的语言。在疾病诊断中,每一种疾病测试方式都可以被视为一个视图,但有些人可能因为一些不可控的因素而不会进行所有的测试。由于视图的不完全性,使得从缺失的多视图数据中挖掘互补信息变得更加困难。此外,由于不同的视图可能会缺失不同数量的实例,它们将会为聚类任务贡献不平衡的信息。因此,直接利用传统的多视图聚类方法很难捕捉不完整多视图数据的聚类结构。为了有效地对缺失多视图数据进行聚类,在过去的十几年里,大量缺失多视图聚类算法被提出并取得了不错的聚类效果。然而,现有的缺失多视图聚类算法仅利用成对样本关联和成对视图关联来提高聚类性能,而忽略了样本、视图的高阶关联。在此种策略下,缺失多视图数据中的信息丢失是不可避免的,因此,此前方法的聚类性能受到了限制。
在发明中,我们关注的高阶关联一般可以分为如下两部分:1)一方面,高阶样本关联用来描述一个缺失多视图数据的全局类簇结构,另一方面,它揭示了类似类簇的结构信息。2)高阶视图关联描述了多个视图之间的全局语义一致性。捕获高阶相关性有以下两个利处:1)它可以更好地联合利用不同视图之间的信息,获得数据底层的内在聚类结构。2)利用样本隶属于同一超边上其它数据点的信息,而不仅仅是一阶连通的样本信息,可以更有效地恢复每个视图中缺失的样本。因此,对于缺失多视角聚类任务,挖掘数据的高阶关联是必要且有效的。基于此,本发明提出了基于高阶关联保持的缺失多视图子空间聚类(HCP-IMSC)方法及系统,利用数据的高阶关联,有效地恢复缺失多视图数据的不同视图的缺失样本和数据的子空间结构。
发明内容
本发明的目的是针对现有技术的缺陷,提供了基于高阶关联保持的缺失多视图子空间聚类方法及系统。
为了实现以上目的,本发明采用以下技术方案:
基于高阶关联保持的缺失多视图子空间聚类方法,包括:
S1.输入原始数据矩阵,并将输入的原始数据转化为已观测部分和缺失部分;
S2.根据原始数据的自表征特性,得到多个与缺失多视图数据相对应的亲和矩阵;
S3.使用张量分解挖掘多个亲和矩阵之间的高阶关联;
S4.从多个亲和矩阵中学习统一的亲和矩阵,得到全局亲和矩阵;
S5.基于全局亲和矩阵构建超图,并利用超图诱导拉普拉斯矩阵约束缺失多视图数据的缺失部分;
S6.将全局亲和矩阵、张量分解和超图诱导的拉普拉斯矩阵约束整合至统一的学习框架,得到目标函数;
S7.通过交替迭代优化策略对得到的目标函数进行求解,得到求解结果;
S8.根据得到的求解结果,对全局亲和矩阵使用谱聚类,得到聚类结果。
进一步的,所述步骤S1中将输入的原始数据转化为已观测部分和缺失部分,表示为:
其中,
其中,
进一步的,所述步骤S2中得到多个与缺失多视图数据相对应的亲和矩阵,表示为:
s.t.diag(Z
其中,约束diag(Z
进一步的,所述步骤S3中使用张量分解挖掘多个亲和矩阵之间的高阶关联,表示为:
s.t.Z=Φ(Z
其中,
进一步的,所述步骤S4中从多个亲和矩阵中学习统一的亲和矩阵,得到全局亲和矩阵,表示为:
其中,ω
进一步的,所述步骤S5中超图诱导拉普拉斯矩阵约束,表示为:
其中,L
进一步的,所述步骤S6中得到目标函数,表示为:
s.t.Z=Φ(Z
其中,α表示惩罚参数。
进一步的,所述步骤S7具体为:
S71.当变量A、
s.t.diag(Z
其中,B
计算目标函数的导数并置为0,变量Z
Z
其中,Q
对下述公式进行优化,表示为:
其中,
其中,
S72.当变量
计算目标函数的导数并置为0,变量A的解为:
S73.当变量
计算目标函数的导数并置为0,变量
其中,M
S74.当变量
令
计算目标函数的导数并置为0,变量
其中,
S75.当变量
计算目标函数的导数并置为0,则变量
进一步的,所述步骤S71中得到目标函数的最优解具体为:获取目标函数无约束时的最优解,将获取的无约束时的最优解映射到有约束项张成的空间中,得到目标函数的最终解。
相应的,还提供基于高阶关联保持的缺失多视图子空间聚类系统,包括:
输入模块,用于输入原始数据矩阵,并将输入的原始数据转化为已观测部分和缺失部分;
获取模块,用于根据原始数据的自表征特性,得到多个与缺失多视图数据相对应的亲和矩阵;
挖掘模块,用于使用张量分解挖掘多个亲和矩阵之间的高阶关联;
统一模块,用于从多个亲和矩阵中学习统一的亲和矩阵,得到全局亲和矩阵;
约束模块,用于基于全局亲和矩阵构建超图,并利用超图诱导拉普拉斯矩阵约束缺失多视图数据的缺失部分;
整合模块,用于将全局亲和矩阵、张量分解和超图诱导的拉普拉斯矩阵约束整合至统一的学习框架,得到目标函数;
求解模块,用于通过交替迭代优化策略对得到的目标函数进行求解,得到求解结果;
聚类模块,用于根据得到的求解结果,对全局亲和矩阵使用谱聚类,得到聚类结果。
与现有技术相比,本发明提出了提一种基于高阶关联保持的缺失多视图子空间聚类方法及系统,使用张量分解和超图引导的拉普拉斯正则保持视图之间和样本之间的高阶关联,从而充分挖掘视图之间的互补信息,达到更好恢复缺失样本和提高聚类效果的目的。
附图说明
图1是实施例一提供的基于高阶关联保持的缺失多视图子空间聚类方法流程图;
图2是实施例一提供的HCPIMSC框图;
图3是实施例二提供的不同算法在三个自然缺失多视图数据集上的聚类结果;
图4是实施例二提供的随着成对率变化下不同算法在六个数据集上的ACC结果示意图;
图5是实施例二提供的随着成对率变化下不同算法在六个数据集上的Fscore结果示意图;
图6是实施例二提供的随着成对率变化下不同算法在六个数据集上的Precision结果示意图;
图7是实施例二提供的随着成对率变化不同算法在六个合成缺失多视图数据集上补全的特征的聚类ACC结果示意图;
图8是实施例二提供的HCPIMSC算法在三个自然缺失多视图数据集上的消融实验结果示意图;
图9是实施例二提供的不同参数组合下三个自然缺失多视图数据集上的ACC结果示意图;
图10是实施例二提供的不同参数组合下三个自然缺失多视图数据集上的NMI结果示意图;
图11是实施例二提供的不同参数组合下三个自然缺失多视图数据集上的Purity结果示意图;
图12是实施例二提供的HCPIMSC方法在三个自然缺失多视图数据集上的目标函数收敛曲线图。
具体实施方式
以下通过特定的具体实例说明本发明的实施方式,本领域技术人员可由本说明书所揭露的内容轻易地了解本发明的其他优点与功效。本发明还可以通过另外不同的具体实施方式加以实施或应用,本说明书中的各项细节也可以基于不同观点与应用,在没有背离本发明的精神下进行各种修饰或改变。需说明的是,在不冲突的情况下,以下实施例及实施例中的特征可以相互组合。
本发明针对现有缺陷,提供了基于高阶关联保持的缺失多视图子空间聚类方法及系统。
实施例一
本实施例提供的基于高阶关联保持的缺失多视图子空间聚类方法,如图1所示,包括:
S11.输入原始数据矩阵,并将输入的原始数据转化为已观测部分和缺失部分;
S12.根据原始数据的自表征特性,得到多个与缺失多视图数据相对应的亲和矩阵;
S13.使用张量分解挖掘多个亲和矩阵之间的高阶关联;
S14.从多个亲和矩阵中学习统一的亲和矩阵,得到全局亲和矩阵;
S15.基于全局亲和矩阵构建超图,并利用超图诱导拉普拉斯矩阵约束缺失多视图数据的缺失部分;
S16.将全局亲和矩阵、张量分解和超图诱导的拉普拉斯矩阵约束整合至统一的学习框架,得到目标函数;
S17.通过交替迭代优化策略对得到的目标函数进行求解,得到求解结果;
S18.根据得到的求解结果,对全局亲和矩阵使用谱聚类,得到聚类结果。
本实施例提出了一种基于高阶关联保持的缺失多视图子空间聚类(HCPIMSC)方法有效地恢复缺失的样本和多视图数据底层的子空间结构。具体地,从多视图数据中学习的多个亲和矩阵可以看做一个低秩三阶张量,本实施例使用一个张量分解约束捕获视图之间和样本之间的高阶关联。然后,本实施例使用一种自加权策略从视图特有的亲和矩阵中学习一个统一的亲和矩阵,它可以有效描述多视图数据底层的子空间结构。为了捕获带有缺失样本视图内部的高阶几何结果,本实施例从统一的亲和矩阵得到一个超图,并使用一个超图引导的拉普拉斯正则化约束缺失样本位于它们的邻近样本附近。最终,本实施例将亲和矩阵学习、张量分解和超图引导的拉普拉斯正则整合进一个统一的学习框架。基于得到的全局亲和矩阵,可以到聚类结果。如图2所示为HCPIMSC方法的算法框图。
在步骤S11中,输入原始数据矩阵,并将输入的原始数据转化为已观测部分和缺失部分。
由于视图中的样本缺失,挖掘视图之间的互补信息变得更加困难。为了减少处理缺失多视图数据和完整的多视图数据之间的差距。本实施例引入映射函数,将输入的原始数据分为已观测部分和缺失部分,具体表示为:
其中,
其中,
在步骤S12中,根据原始数据的自表征特性,得到多个与缺失多视图数据相对应的亲和矩阵。
基于张量tubal秩,本实施例将与缺失多视图数据相对应的亲和矩阵表示为,
s.t.diag(Z
其中,约束diag(Z
由于每个视图的亲和矩阵描述了子空间结构,在理想情况下应该具有块对角结果。此外,由于多视图数据具有潜在的语义一致性,张量Z的每一个切片都应该具有类似的块对角结构。随之,Z在理想情况下应该为一个块对角张量,同时Z具有低秩特征。因此,本实施例约束Z为一个低秩张量来捕获其中的块对角结果。
在步骤S13中,使用张量分解挖掘多个亲和矩阵之间的高阶关联。
张量核范数是用来代替张量tubal秩约束张量低阶结构的可计算约束。然而,计算大小为n×n×V张量的张量奇异值分解需要花费O(n
s.t.Z=Φ(Z
其中,
在步骤S14中,从多个亲和矩阵中学习统一的亲和矩阵,得到全局亲和矩阵。
不同视图可能缺失不同数量的样本,因此,不同视图对聚类任务的贡献的信息会不同。为了为缺失多视图数据学习一个统一类簇结构,本实施例使用一种自加权策略从视图特征的亲和矩阵
其中,ω
在步骤S15中,基于全局亲和矩阵构建超图,并利用超图诱导拉普拉斯矩阵约束缺失多视图数据的缺失部分。
每个视图中缺失的样本基于视图特有的亲和矩阵使用其它的线性组合进行重构。然而,由于视图缺失和视图聚类能力差异,视图特有的亲和矩阵并不能很好地描述数据底层的类簇结构。基于统一的亲和矩阵,本实施例使用一个超图引导的拉普拉斯正则约束缺失样本在它们邻近样本附近进行重构。该正则化约束可以表示如下:
其中,w(e)和d(e)分别表示超边e的边权重和度。
其中,L
在步骤S16中,将全局亲和矩阵、张量分解和超图诱导的拉普拉斯矩阵约束整合至统一的学习框架,得到目标函数。
本实施例提出的基于高阶关联保持的缺失多视图子空间聚类方法的目标函数可以表示如下:
s.t.Z=Φ(Z
其中,α表示惩罚参数。第一项学习视图特有的亲和矩阵,第二项将它们融合为一个统一的亲和矩阵。HCPIMSC算法使用张量分解和超图引导的拉普拉斯正则保持视图之间和样本之间的高阶关联,从而充分挖掘视图之间的互补信息,达到更好恢复缺失样本和提高聚类效果的目的。
在步骤S17中,通过交替迭代优化策略对得到的目标函数进行求解,得到求解结果。
具体步骤为:
S171.当变量A、
s.t.diag(Z
其中,B
求取目标函数的导数并置为0,变量Z
Z
其中,Q
然后,本实施例通过优化如下问题得到Z
其中,
目标函数的最优解如下:
其中,
S172.当变量
求取目标函数的导数并置为0,A有如下解:
S173.当变量
求取目标函数的导数并置为0,
其中,M
S174.当变量
令
求取目标函数的导数并置为0,变量
其中,
S175.当变量
求取目标函数的导数并置为0,变量
本实施例提供了一种基于高阶关联保持的缺失多视图子空间聚类方法(HCPIMSC),与其它缺失多视图聚类算法,如:LT-MSC、MLAN、GMC和SM2SC等进行比较,HCPIMSC方法使用张量分解和超图引导的拉普拉斯正则保持视图之间和样本之间的高阶关联,从而充分挖掘视图之间的互补信息,达到更好恢复缺失样本和提高聚类效果的目的。图2给出了HCPIMSC算法的算法框图。
相应的,本实施例还提供基于高阶关联保持的缺失多视图子空间聚类系统,包括:
输入模块,用于输入原始数据矩阵,并将输入的原始数据转化为已观测部分和缺失部分;
获取模块,用于根据原始数据的自表征特性,得到多个与缺失多视图数据相对应的亲和矩阵;
挖掘模块,用于使用张量分解挖掘多个亲和矩阵之间的高阶关联;
统一模块,用于从多个亲和矩阵中学习统一的亲和矩阵,得到全局亲和矩阵;
约束模块,用于基于全局亲和矩阵构建超图,并利用超图诱导拉普拉斯矩阵约束缺失多视图数据的缺失部分;
整合模块,用于将全局亲和矩阵、张量分解和超图诱导的拉普拉斯矩阵约束整合至统一的学习框架,得到目标函数;
求解模块,用于通过交替迭代优化策略对得到的目标函数进行求解,得到求解结果;
聚类模块,用于根据得到的求解结果,对全局亲和矩阵使用谱聚类,得到聚类结果。
实施例二
本实施例提供的基于高阶关联保持的缺失多视图子空间聚类方法与实施例一的不同之处在于:
为了充分验证本发明HCPIMSC方法的有效性,首先在三个自然缺失的多视图数据库(3sources、bbcsport、bbc)和六个常用的合成的缺失多视图数据库上(MSRCV1、ORL、Yale、100leaves、COIL20、handwritten)测试HCPIMSC方法的性能,同时与以下一种单视图聚类算法和六种目前比较流行缺失多视图聚类算法进行比较:
(1)BSV:该方法首先使用每个视图的特征均值对每个视图进行补全,然后对每个视图使用谱聚类,并给出最好的聚类结果。
(2)MIC:该方法使用一种基于加权非负矩阵分解的算法从缺失多视图数据中学习一个潜在的特征矩阵进行聚类。
(3)MKKM-IK:该方法联合进行核k均值聚类和核矩阵补全,并学习一个共有的嵌入表征进行聚类。
(4)MKKM-IK-MKC:该方法联合进行核k均值聚类和视图交互核矩阵补全,并学习一个共有的嵌入表征进行聚类。
(5)UEAF:该方法使用嵌入对齐和局部结构保持联合学习潜在表征和缺失视图补全,并使用一个自适应加权策略挖掘视图的差异性。
(6)FLSD:该方法使用一个图约束的矩阵分解模型和语义一致性约束分别学习视图特有的潜在表征和视图共享的聚类表征。
(7)EE-R-IMVC:该方法从多视图低维度特征矩阵中学习一致聚类表征的同时对每个缺失视图进行补全。
实验中,在三个自然缺失的多视图数据库上对HCPIMSC方法与其他七种聚类方法进行对比试验。三个自然缺失的多视图数据库具体信息如下:
3sources:它包含六类总共416条新闻报道。每一套新闻报道从BBC、Reuters和Guardian三个广播电台获取。每个电台采集的数据视为一个视图。三个视图分别包含352、302和294被报道的新闻。
bbcsport:它包含五类总共737条不同的体育新闻。每个视图分别包含519、531和513被报道的新闻。
bbc:它包含五类总共2225条不同的体育新闻。每个视图分别包含1828、1832和1845条被报道的新闻。
实验中,在六个合成缺失的多视图数据库上对HCPIMSC方法与其他七种聚类方法进行对比试验。六个合成缺失的多视图数据库具体信息如下:
MSRCV1:它包含七类共210张场景识别图片。每张图片使用六类不同的特征进行描述,如,256维LBP特征,100维HOG特征,512维GIST特征,48维Color Moment特征,1302维CENTRIST特征,和210维SIFT特征。
ORL:它包含在不同光照、时间、以及面部细节下40位人的共400张人脸图片。在本实验中,三类不同的特征,如4096维intensity特征,3304维LBP特征,和6750维Gabor特征用于描述每张人脸图片。
Yale:它包含15个体总共165张灰度人脸图片。本实验中,我们分别提取了4096维intensity、3304维LBP和4096维Gabor特征。
100leaves:该数据集包含100类共1600张植物图片。在本实验中,本实施例从每张图片中提取了形状、材质、边缘三种不同的特征。
COIL20:它包含20种共1400张物体图片。对于每张图片,本实施例提取了1024维intensity特征,3304维LBP特征和6750维Gabor特征。
handwritten:它包含从0到9共2000张手写数字图片。对于每张图片,本实施例提取了76维FOU特征,216维FAC特征,64维KAR特征,240维Pix特征,47维ZER特征,以及6维MOR特征。
在本实验中,从六个标准多视图数据集中生成具有不同成对率的缺失多视图数据。首先随机选择n
结果分析:
图3给出了不同方法在三个自然缺失多视图数据集上的七个聚类指标结果。本实施例有如下结论。
(1)HCPIMSC算法的聚类结果明显优于其它对比算法。例如,在3sources数据集上,HCPIMSC算法比第二优的FLSD算法在ACC、NMI和Purity指标上分别高2.65、4.99和2.65百分点。因此,它表明了挖掘缺失多视图数据的高阶关联能够促进聚类性能。
(2)FLSD算法在3source和bbcsport数据集上相比于其它对比算法取得更好的聚类效果。这表明了保持缺失多视图数据的局部结构能够很好地促进聚类效果。HCPIMSC算法对FLSD算法取得更好的结果,表明了使用高阶样本关联的超图比基于成对样本关联的相似图更能恢复缺失视图样本的底层信息。
(3)BSV和MIC算法通常取得比较差的聚类结果。这表明了使用特征均值或者零值对缺失视图样本进行补全会破坏数据的原始结构,从而降低算法聚类性能。
(4)HCPIMSC算法比MKKM-IK、MKKM-IK-MKC、EE-R-IMVC和UEAF算法取得更好的聚类结果。这表明了缺失多视图数据中的高阶关联对于聚类任务具有促进作用。
图4、5、6给出了不同算法在合成缺失多视图数据集上的ACC、Fscore和Precision指标下的聚类结果。本实施例有如下结论。
(1)在所有的成对率设置下,HCPIMSC算法能比其它对比算法取得更好的聚类效果。一个原因是,HCPIMSC算法自适应使用超图诱导的拉普拉斯矩阵对缺失视图样本进行补全,而不是使用特定值补全。第二个原因是,HCPIMSC算法使用张量分解恢复缺失多视图数据的子空间结构。超图诱导的拉普拉斯约束和张量分解能够很好地挖掘数据的高阶关联,从而促进聚类效果。
(2)在所有的成对率设置下,EE-R-IMVC、MKKM-IK-MKC和UEAF算法在六个数据集上能得不错的结果。这表明了对联合进行缺失补全和聚类任务能够促进聚类性能。HCPIMSC算法的聚类结果优于比这三种算法的结果。这表明了高阶关联对成对关联更好地恢复类簇结构。
(3)对于ORL数据集,HCPIMSC算法在0.5成对率下的结果比0.9成对率聚类结果好。可能原因为数据中噪声信息会随着成对率增加而增加。在这种情况下,HCPIMSC算法会恢复出带有噪声的子空间结构,因此,聚类效果下降了。
(4)大多数据下,所有算法在0.9成对率下的聚类结果比0.1成对率下的结果好。这表明了视图之间的互补信息会随着样本成对率降低而下降。
除了比较上述方法的聚类性能外,还希望对补全特征的质量有更多的了解。为此,将补全的特征拼接在一起构成一个矩阵,并使用这个特征矩阵进行谱聚类。对比了零值补全(ZF)、均值补全(MF)和UEAF算法中补全的特征。图7给出了不同样本成对率下得到的补全特征进行谱聚类的聚类ACC指标结果。从图7中结果可知,HCPIMSC算法补全的特征能取得更好的聚类结果。这表明了使用高阶关联约束样本在它的邻近样本附近重构的有效性。
在HCPIMSC算法中,超图诱导的拉普拉斯正则(HR)和张量分解(TF)为两项约束挖掘缺失多视图数据中的高阶关联。为了更好地探究它们的有效性,开展了一个消融实验并在表中给出了在三个自然缺失多视图数据集上七个聚类指标下的结果。从图8中结果可知,当HCPIMSC算法缺失超图诱导的拉普拉斯正则(HR)或者张量分解(TF)约束,聚类效果会急剧下降。这表明了挖掘数据的高阶关联可以促进缺失多视图聚类的效果。
参数灵敏度
本发明包含两个超参数,即α和β。为了研究HCPIMSC算法对两个参数的敏感性,在图9、10、11给出了HCPIMSC算法在三个自然缺失多视图数据集上不同参数组合下的ACC、NMI和Purity的结果。从结果可知,HCPIMSC算法随着参数α变化效果波动很小,对于参数β比较敏感。总的来看,HCPIMSC算法能在很大参数范围内取得令人满意的聚类结果。
计算复杂度分析
优化算法求解目标函数过程中,计算复杂度主要位于更新变量
经验收敛性:
为了验证HCPIMSC算法的收敛性,本实施例记录了算法在三个自然缺失的多视图数据集上的目标函数收敛曲线。图12给出了HCPIMSC算法在三个自然缺失多视图数据集上的目标函数收敛曲线。从曲线可知,HCPIMSC算法的目标函数值单调下降并在迭代次数20次内收敛,因此,具有很强的收敛性。
注意,上述仅为本发明的较佳实施例及所运用技术原理。本领域技术人员会理解,本发明不限于这里所述的特定实施例,对本领域技术人员来说能够进行各种明显的变化、重新调整和替代而不会脱离本发明的保护范围。因此,虽然通过以上实施例对本发明进行了较为详细的说明,但是本发明不仅仅限于以上实施例,在不脱离本发明构思的情况下,还可以包括更多其他等效实施例,而本发明的范围由所附的权利要求范围决定。
机译: 记录了一种基于数据库的数据关联方法和一种基于数据库的数据关联系统以及基于数据库的数据关联方法,并且计算机可读记录介质包括计算机可读记录介质。
机译: 多对象多视图关联的图像处理方法和系统
机译: 与基于分组的多媒体通信标准关联的数据的隧道方法,用于通过单个HTTP端口通信端口业务的方法,具有程序指令的计算机可读介质,用于与基于分组的多媒体通信协议,与数据包的多媒体通信相关联的数据的隧道指令通过单个HTTP端口与端口通信,以及用于通过单个端口向多个端口传送隧道通信的系统