图谱和Kuhn-Munkres算法在图匹配中的应用研究

为了对图数据库中的结构化数据进行有效的匹配分析,提出了基于全局结构相似度以及节点位置相似度的Kuhn-Munkres算法。首先对图数据构建全局以及节点位置矩阵,全局相似度矩阵用邻接矩阵的拉普拉斯谱特征构造,位置相似度矩阵首先使用高斯核函数进行节点相对位置的归一化计算,再利用其谱特征构造。节点位置相似度主要描述图所有节点之间的相对位置,弥补了全局结构相似度只刻画图整体结构的不足。最后使用Kuhn-Munkres算法进行图匹配,得到二分图的最大权匹配。实验表明,改进的Kuhn-Munkres算法有效提高了节点之间的匹配正确率。     

一种潜在文档相似模型

提出一种潜在文档相似模型（LDSM）,把每对文档看作一个二分图,把文档的潜在主题看作二分图的顶点,用主题问的加权相似度为相应边赋权值,并用二分图的最佳匹配表示文档的相似度。实验结果表明,LDSM的平均查准率和平均查全率都优于用TextTiling和二分图最佳匹配方法构建的文档相似模型。     

基于案例表示及语义匹配的装备故障辅助诊断方法

为满足装备故障快速诊断需求,将案例推理技术与文本语义相似度算法相结合,构建了一种基于句向量的装备故障案例的语义相似度匹配算法。根据装备故障信息的特点,结合面向对象的案例表示方法,在优选装备故障现象文本相似度计算方法和装备故障信息的权重合理分配的基础上,提出了基于句向量的装备故障案例相似度综合计算方法（综合法）。针对1 000个故障案例,在有无增加干扰项的情况下开展实验分析,结果表明,提出的综合法在有无干扰项情况下都能取得最好的故障案例匹配效果,既能根据案例相似度给出推荐案例的正确排序,又有较好的区分度。     

基于案例推理的故障诊断算法

电力系统智能告警研究目前主要集中于规则推理领域,未能充分利用系统内历史故障的案例进行有效的分析与故障处理.本文初步研究了基于案例推理的故障诊断算法,在此基础上提出了一种基于向量计算的案例匹配算法.该算法通过对故障信息进行抽象,并与系统案例库中的案例进行相似度计算的方式,对故障信息与案例信息进行一一匹配.案例库的建立基于经过人工分析的各类历史故障信息.相似案例的故障性质、故障原因分析可对本次故障的分析、诊断和后续处理起到指导作用.     

基于词法规则的语义对象匹配算法

介绍了基于词法规则的语义对象匹配算法,通过有限状态自动机将文本与描述语义对象的规则匹配,分析连续匹配成功的片段,以计算文本与语义对象的综合相似度,确定二者的匹配程度。该算法的特点是通过引入相似度计算,有效地解决了规则的不完全匹配问题。     

基于子图同构与事例匹配的装配体局部结构相似性分析

基于事例推理是解决面向装配的设计和装配工艺规划问题的有效方法,装配体检索是应用此方法的关键步骤.为此提出一种基于子图同构与事例匹配的装配体局部结构相似性分析方法.该方法将装配体零件间的装配关系用属性邻接图来表示,通过对装配体中联结关系的定性分类及装配体属性邻接图预处理规则的定义,利用Ullmann算法匹配出相似的装配体图(子图)结构,并给出了装配体局部结构相似度计算公式.最后通过实例验证了文中方法的有效性.     

一种基于马尔科夫网的本体匹配算法

概率模型是解决不确定性推理和数据分析的有效工具。针对本体匹配的不确定性,提出一种基于马尔科夫网的本体匹配改进算法。采用多种传统匹配算法计算相似度矩阵,改进相似度传播规则,添加2种结构稳定性约束规则和1种Disjoint一致性约束规则,定义其对应团的势函数。根据相似度矩阵和上述规则,给出马尔科夫网的构造方法,使用循环置信度传播算法计算随机变量的后验概率,依据后验概率得到最后的本体匹配结果。在OAEI2010数据集上进行实验,结果表明,与iMatch本体匹配系统相比,该算法能有效降低概率模型的复杂度,提高本体匹配的准确率和召回率。     

基于二分图极大权值匹配的SOC故障定位算法研究*

针对故障传播给故障定位带来的影响,考虑SOC功能测试系统中的故障源和故障事件之间的不确定性,提出一种基于二分图的故障定位算法。首先从SOC中抽象出特定的硬件模块,由这些模块构成故障源。然后故障源结合相应的故障事件组合成二分图,在二分图的基础上生成一种适用于SOC故障定位的故障传播模型(Fault Propagation Model,FPM)。最后将SOC故障定位的问题转化成二分图极大权值匹配的求解问题,从概率上保证结果的正确性。实验结果表明,故障定位准确率提高了0~21%,误报率下降了0~15%,更加适用于小型系统的故障定位。     

基于灰色理论的故障案例检索算法

案例检索是基于案例推理系统的关键问题。为了在信息不完全的条件下提高故障案例匹配的准确度,将灰色关联分析应用到故障案例相似度的计算中,对灰色关联度公式进行改进,提出一种基于二次搜索策略的故障案例检索算法。对多种案例检索算法进行比较分析,结果表明该方法克服了传统方法确定相似度系数的主观性缺点,具有较好的分辨能力。     

非均匀有理B样条曲线优化匹配组合

目的 为了解决从曲线库(轮廓线集合)中筛选出与期望曲线相匹配的相似曲线段问题,研究基于Kabsch算法的NURBS(非均匀有理B样条)曲线优化匹配组合方法。方法 首先提出一种基于Kabsch算法的曲线相似性判断方法,针对两条NURBS曲线上相同个数点阵,经最优旋转和平移变换得到其最小均方根偏差,进而依据基于最小均方根偏差和相似度指标判断曲线相似性;在此基础上,提出一种类似二分查找法的曲线优化匹配组合方法,对于给定相似度和最小搜索步长,通过曲线分割和相似性判断得到期望曲线分割段数最少的相似组合曲线。结果 给定一条期望的3D曲线,在相似度为0.025和最小搜索步长为0.05情况下,采用所提方法从包含4条3D曲线的曲线库中依次筛选出10段基元构建相似组合曲线。结论 提出了一种新的NURBS曲线优化匹配组合方法,实验结果表明,对不同期望曲线能高效稳定构建相对应的相似组合曲线,适用于类似碎片拼接重构问题。     

基于加权二部图匹配的中文段落相似度计算

为了改进传统以向量空间模型（VSM）为代表的基于词频统计的方法在中文段落相似度计算时存在的精度不高问题,在基于加权二部图匹配的思想上提出了一种计算中文段落之间相似度的方法。该方法将相似度计算分为段落和句子两个层次,将句子作为简单段落看待,也使用二部图匹配进行相似度计算。首先利用句子主干词汇提取算法来提取句子的主干词汇,将主干词汇作为二部图的顶点,把主干词汇之间的相似度作为二部图顶点之间的权值系数,进行句子相似度的计算。其次,将句子作为加权二部图的顶点,把句子之间的相似度作为二部图顶点之间的权值系数,进行段落之间的相似度计算。实验结果表明,该方法与VSM相比,由于它能准确识别同义词,自动匹配两个在段落中不同位置的相似词语,因而在准确度上有了很大的提高。     

OM-based video shot retrieval by one-to-one matching

This paper proposes a new approach for shot-based retrieval by optimal matching (OM), which provides an effective mechanism for the similarity measure and ranking of shots by one-to-one matching. In the proposed approach, a weighted bipartite graph is constructed to model the color similarity between two shots. Then OM based on Kuhn–Munkres algorithm is employed to compute the maximum weight of a constructed bipartite graph as the shot similarity value by one-to-one matching among frames. To improve the speed efficiency of OM, two improved algorithms are also proposed: bipartite graph construction based on subshots and bipartite graph construction based on the same number of keyframes. Besides color similarity, motion feature is also employed for shot similarity measure. A motion histogram is constructed for each shot, the motion similarity between two shots is then measured by the intersection of their motion histograms. Finally, the shot similarity is based on the linear combination of color and motion similarity. Experimental results indicate that the proposed approach achieves better performance than other methods in terms of ranking and retrieval capability.

一种求解二部图最大匹配问题新算法及其应用

提出了解决二部图最大匹配问题的分层网络优化算法,并应用新算法对排课问题进行求解。定义了分层网络的概念及匹配的规则,结合广度优先搜索策略生成分层网络体系,然后按网络逆序找出最大匹配。实验表明,算法在解决大规模二部图最大匹配的理论问题和实际应用问题时均能获得准确的结果,具备良好的性能。     

面向性能仿真的非连续微分代数模型的指标分析

针对物理系统性能仿真形成的非连续高指标微分代数模型,提出一种基于加权二部图的指标转换方法．该方法将微分代数系统表示为加权二部图,基于二部图匹配算法可以判定微分代数系统是否为高指标系统．对于高指标系统,采用文中方法可以找出需要求导的最小结构奇异方程子集,以便将高指标系统转换为低指标形式．最后,针对定结构与变结构的非连续微分代数模型给出了相应的指标分析策略．文中策略与相关算法已在基于Modelica语言的建模仿真平台MWorks上实现．     

3D Model Retrieval Using Bipartite Graph Matching Based on Attention

In this paper, we propose an attention-based bipartite graph 3D model retrieval algorithm, where many-to-many matching method, the weighted bipartite graph matching, is employed for comparison between two 3D models. Considering the panoramic views can donate the spatial and structural information, in this work, we use panoramic views to represent each 3D model. Attention mechanism is used to generate the weight of all views of each model. And then, we construct a weighted bipartite graph with the views of those models and the weight of each view. According to the bipartite graph, the matching result is used to measure the similarity between two 3D models. We experiment our method on ModelNet, NTU and ETH datasets, and the experimental results and comparison with other methods show the effectiveness of our method.

     

基于二分图卷积表示的推荐算法

随着数据驱动智能技术的快速发展,个性化推荐算法及相关应用成为了研究热点。推荐可视为将用户与物品进行匹配的问题,但用户与物品之间存在的语义差距不便于两者之间的直接匹配。现有的许多基于深度学习的推荐算法采用的思路都是将不同空间中的实体映射到统一潜在语义空间,利用其嵌入表示来进行匹配度计算。随着网络表示学习方法的出现,由于用户和物品的交互可构成二分图,用户和物品的嵌入表示可被视作二分图节点表示,许多基于二分图节点表示的推荐算法被提出,但现有算法仍难以对高阶交互信息进行有效提取。针对这一问题,文中提出了一种基于二分图卷积表示学习的推荐算法BGCRRA(Bipartite Graph Convolution Representation-based Recommendation Algorithm)。该算法首先将用户和物品交互视作二分图,然后通过实现自适应融合多阶、多层次的图卷积模型来对节点进行嵌入表示,最后计算用户和物品的匹配度,并实现推荐。文中在3个公开的数据集上进行对比实验,通过将该算法与当前表现优异的算法进行HR和NDCG(Normalized Discounted Cumulative Gain)指标的比较分析,验证了所提推荐算法的有效性。     

基于图的直方图及路径相似性的图匹配方法

针对图结构在一些非刚性变换下谱特征不稳定等问题,提出一种基于几何关系直方图及路径相似性的图结构信息的描述方法,并在此基础上利用谱分析方法实现图的顶点匹配.首先通过图的直方图给出了一种图顶点的特征描述并初始化候选匹配关系,再基于最短路相似性给出一种匹配关系之间的亲和性的度量,最后采用谱方法求解2个特征点集之间对应关系,实现图的顶点的匹配.与传统的描述方法不同,该方法是利用图的直方图及路径相似性来描述图的结构信息,结构简单,信息描述充分.实验结果表明,文中方法对于一些扰动前后的图的匹配具有较高的匹配准确度.     

基于条件型游走二部图协同过滤算法

针对拥有少量评分的新用户采用传统方法很难找到目标用户的最近邻居集的问题,本文提出了一种条件型游走二部图协同过滤算法。该算法根据复杂网络理论的二部图网络,将用户-项目评分矩阵转换为用户-项目二部图,采用了条件型游走计算目标用户与其他用户之间的相似性。研究结果表明在同样的数据稀疏性情况下,本文提出的条件型游走二部图协同过滤算法在MAE和准确率都要优于其他两种传统的协同过滤算法,从而提高了算法的推荐精度;而且当训练值的比例很低时,即数据稀疏程度越大时,本文提出的推荐算法的对推荐质量的提高程度越大。     

基于模块度和标签传递的推荐算法

针对基于网络信息的商品推荐的问题,提出了在二部网络上基于社区挖掘和标签传递的推荐算法。首先,用带权的二部图来表达用户-项目的评分矩阵,利用标签传递技术对二部网络进行社区挖掘;然后,基于二部网络中的社区结构信息,充分利用用户所在的社区之间的相似性以及项目之间、用户之间的相似性来挖掘用户可能感兴趣的项目;最后,向用户进行项目的推荐。在实际网络上的实验结果表明,与基于双向关联规则项目评分预测的推荐算法（BAR-CF）、基于项目评分预测的推荐算法（IR-CF）、基于网络链接预测的用户偏好预测方法（PLP）和改进的基于用户的协同过滤的方法（MU-CF）相比,该算法的平均绝对差（MAE）低0.1~0.3,准确率高0.2。因此,所提算法可以取得比其他类似方法更高质量的推荐结果。