基于图常量条件函数依赖的图修复规则发现

数据一致性是数据质量管理的一个重要内容。为了提升图数据一致性,大量关系型数据库中的数据依赖理论被引入到图数据库,包括图函数依赖、图关联规则等。图修复规则是最新提出的一种针对图数据的数据依赖规则,具有强大的修复能力,但目前尚无有效的挖掘算法。为了自动生成图修复规则并提高图数据修复的可靠性,提出一种将图常量条件函数依赖转化为图修复规则的方法(GenGRR)。通过图模式在图中匹配同构子图并映射成节点-属性二维表,从表中相应属性域中抽取错误模式把图常量条件函数依赖转化成图属性值修复规则;删去图模式中常量条件函数依赖RHS对应的节点与相连边生成图属性补充规则。基于最大公共同构子图筛选并验证生成图修复规则的一致性。在多个真实数据集上进行测试,验证相比图常量条件函数直接修复图数据,通过转化生成的图修复规则具有更好的修复效果。

基于UMCS树的UML类图的混合相似性度量

软件重用是基于给定条件从存储库中检索以前开发的软件产品,检索基于相似性度量。UML(Unified Modeling Language)类图被广泛应用于软件设计,UML类图重用作为软件设计重用的核心而备受关注。因此,对UML类图的相似性开展研究。类图包含语义和结构信息。目前,UML类图的相似性研究主要集中在语义,也有个别讨论结构相似性,但没有考虑将语义和结构相结合。因此,提出一种结合语义和结构的混合相似性度量。鉴于UML类图的非形式化特征,将UML类图转换成图模型,搜索最大公共子图列表,构建了最大公共子图树,提出一个基于最大公共子图序列的混合相似性度量方法。针对概念公共子图和结构公共子图分别定义了语义匹配和结构匹配,并开展了相似性对比和基于相似性的分类质量比较实验,实验结果验证了所提出方法的优势。

基于蚁群算法的三维CAD模型检索

为了更好地实现CAD模型的重用,提出一种利用蚁群算法的三维CAD模型检索算法.通过提取CAD模型的B-rep信息,将模型用属性邻接图来表示;根据如果2个CAD模型存在相似的特征或局部结构,那么CAD模型对应的属性邻接图就应存在公共子图这一原理,利用蚁群算法来检测属性邻接图中的公共子图,从而得到2个CAD模型相似的局部细节特征;然后通过比较相似局部细节特征对CAD模型进行相似性评价.实验结果表明,该算法能较好地实现三维CAD模型检索,检索性能高于通用领域的检索算法,可以实现CAD模型设计和制造知识的重用.

JTangWFR:一个高效可靠的流程推荐系统

传统的流程推荐技术无法支持包含循环结构的流程,其实用性受到极大限制,为此提出一种支持循环结构的流程推荐方法。该方法基于最大公共子图和最小公共超图的图匹配策略,对参考流程和流程模式的距离进行计算,根据计算结果选取候选节点集作为推荐结果。基于该方法,结合传统流程推荐技术,实现了JTangWFR原型系统。基于合成与真实数据集的系列试验结果表明,该系统不仅能够有效支持循环结构,还在推荐效率和准确度方面比以往方法有较大提升。

一种三维CAD模型局部匹配算法

针对现有的三维计算机辅助设计模型检索算法难以实现局部结构匹配的问题,提出一种利用蚁群算法来实现三维计算机辅助设计模型局部匹配的方法。提取模型的B-Rep信息,将局部结构和计算机辅助设计模型分别用属性邻接图来表示;利用蚁群算法实现局部结构和计算机辅助设计模型属性邻接图中的公共子图检测,并根据公共子图得到计算机辅助设计模型中包含的局部结构;通过比较欲检索的局部结构和计算机辅助设计模型所包含的局部结构,实现模型局部相似性评价。实验结果表明,该算法可以实现三维计算机辅助设计模型局部匹配,检索效率满足工程检索的要求。

面向重用的三维CAD模型检索算法

针对现有CAD领域的检索算法对模型的局部细节特征描述不足的现状,提出了一种基于最大公共子图的三维CAD模型检索算法,通过提取CAD模型的B-Rep信息,将模型用属性邻接图来表示.根据如果2个CAD模型存在相似的特征或局部结构,CAD模型所对应的属性邻接图应存在公共子图的原理,通过检测属性邻接图中的公共子图,得到了2个与CAD相似的局部细节特征,并利用这2个相似的局部细节特征对CAD模型进行了相似性评价.实验表明,该方法能够实现三维CAD模型检索,且检索的效率能够满足工程检索的要求,因此可以实现CAD模型设计和制造知识的重用.

基于图结构的中文文本表示方法研究

为解决基于统计的文本表示模型的信息缺失问题,本文提出了一种考虑词间语义和语序信息的基于图结构的中文文本表示方法,其思想是将文本的特征项表示成图结构中的节点,特征项间的关系表示成节点间的有向边,据此可将文本表示成由节点和有向边组成的图结构,并且将边赋予权重信息,该模型较大程度地保留了原文本的结构信息及语义信息。中文语料测试结果表明,基于图结构的文本表示方法对复杂文本语料的分类问题十分有效。对于简短文本语料,本文提出扩展特征项共现单元的修正方法,提高了图结构中文文本表示方法的普遍适用性。

基于最大公共子图的文本相似度算法研究

用图结构表示文本,能更好地反映文本内部的结构特征,体现文本内的语义关系及词语在上下文中的语序关系,在此基础上,本文提出了一种基于最大公共子图的文本相似度计算方法,应用最大公共子图提取文本的公共部分,并利用最大公共子图的性质度量文本间的相似程度。最后针对分类试验结果中存在的问题,提出图模型修正方法以改进文本的表示效果,并对修正前后不同β取值下的F-Score值进行比较。修正后的试验结果表明,基于最大公共子图的文本相似度算法有着较好的分类性能。

图的最大公共连通子图问题研究

图像识别、恶意代码族群特征提取、人工智能中许多应用问题都可以规约为一类图的最大公共连通子图问题。提出了求解简单最大连通子图问题的矩阵方法,定义了图特征相关度和图度序列相关系数的概念,最后结合算例给出了一种求解一般最大公共连通子图问题的贪婪算法,能够快速有效地找到一个尽可能大的公共连通子图。

两棵树的公共子树查找算法综述

本文通过对基于两棵树中的公共子树查找问题在有根、带标记、有序树中的主要算法及相关历史的回顾,结合算法思想将公共子树查找问题分为主要3类。本文深入探讨了每类算法中的代表算法,其中根据数据挖掘中枚举树相关技术提出了一种可能的公共子树查找算法的思想。最后比较了文中主要算法的效率,同时较为深入地分析和讨论了公共子树的相关研究及未来可能的研究发展方向。

基于属性相似性的三维装配体通用设计单元发掘方法

为了从已有CAD模型中获取具有共性的可重用信息、缩短产品开发周期,以产品三维装配体模型为对象,提出了一种基于属性相似性的装配体通用设计单元发掘方法。针对装配体模型的多源输入信息,建立了模型信息的属性邻接图表示方法;采用三类属性相似度分析方法将装配体模型进一步转化为聚类属性邻接图,实现了所有零件和连接关系的分组和统一表示;以聚类属性邻接图为基础,给出了基于快速频繁子图挖掘的装配体通用设计单元发掘算法和步骤。以一组制动器类产品的装配体模型为对象,验证了所提方法的有效性。

一种面向加密算法共性子图的指令定制方法

为提高处理器对加密算法的处理效率和扩展性能,本文提出一种基于共性子图的指令定制方法.该方法通过挖掘常用加密算法中的共性计算模式,用一条模式指令替换多条被共性模式覆盖的指令,并使用查找表(LUT)对S-盒间址访问进行处理,达到减少算法指令数的目的.我们针对MD5,SHA256,RC5和AES等4种常用加密算法进行了实验,结果表明该方法可以有效的减少4种算法的核心循环体指令,使这些算法得到15.4%～60.6%的指令减少率.

不一致数据库中基于用户语义模板的评论可信度计算

在清洗算法不能有效地纠正不一致数据的情况下,"知情"用户给出的关于其正确取值的评论,对数据库的其他用户意义重大,可以帮助他们甄别错误数据,并在不丢失信息的前提下,尽可能地从不一致数据库中获取有用信息,但只有正确可信的评论才能有如此意义。因此,评论的可信度估算是这类应用中的一个关键问题。和互联网评论不同,数据库一般向系统内用户开放,用户的特征更易于提取,其语义确定。由于数据是对现实世界的描述,能对同一评论对象,发出类似评论的用户往往具有相同的背景或语义特征。文章提出了一种基于用户的特征分析的评论可信度计算算法,有针对性地解决了上述问题。算法首先根据语义特征,对历史评论者进行用户社区挖掘,得到在某准确度下评论过某对象的用户公共特征,形成用户模板;其次,对于任意给定新评论,通过其评论者和用户公共特征模板的匹配程度,并综合该评论者可信度、评论者和评论对象的语义相关性等关键因素,计算出该评论的可信度。实验证明,该算法在时间和准确率两方面都是有效的。

一种基于最大公共子图的文本谱聚类算法

传统的基于空间向量的文本谱聚类方法容易忽略文本上下文之间的语义联系,通过图结构进行文本表示可以很好的解决这一问题,在此基础上,本文提出了基于最大公共子图的谱聚类算法——SC-MCS算法。该算法通过求解文本之间的最大公共子图来进行文本相似度的计算,最后进行文本聚类。实验结果表明,与传统的基于空间向量的文本谱聚类方法相比,该算法在准确率和召回率都取得了一定的提升。

SegGraph:室外场景三维点云闭环检测算法

提出适用于配有三维激光雷达的自主移动机器人在室外场景进行同时定位与地图创建(simul-taneous localization and mapping, SLAM)的一种闭环检测算法,命名为SegGraph.作为SLAM的关键模块,闭环检测的任务是判断机器人当前位置是否与已到过的某一位置邻近.SegGraph包含3步:1)对在不同时刻得到的2组点云分别移除大地平面后采用区域增长方法分割为若干个点云簇;2)以点云簇为顶点,以点云簇图心间距离为边权值,分别构建带权值的完全图;3)判定所得的2个完全图是否含有足够大的公共子图.SegGraph的主要创新点是在寻找公共子图时以边权值(即点云簇间距离)为主要匹配依据.这是因为点云数据中的噪声会导致在邻近地点获得的不同点云经分割后得出差别很大的点云簇集,不同点云中相应的点云簇也便无法匹配.然而相应点云簇间距离却受分割过程影响不大.主要贡献包括研发高效的判定2个点云簇图是否有足够大的公共子图的近似算法,实现完整的SegGraph算法,及以被广泛使用的公开数据集KITTI(Karlsruhe Institute of Technology and Toyota Technological Institute)评估SegGraph的准确度及运行效率.实验结果显示SegGraph具有良好的准确度及运行效率.

一种基于最大公共子图的社交网络对齐方法

随着Internet的普及,各类社交网络走进人们的视野,用户为满足不同的服务需求,往往不会局限于单一社交网络中,因此,跨社交网络环境下的用户识别问题成为研究者的热门话题。主要利用网络结构信息,针对社交网络对齐问题进行研究,主要包含以下研究点:首先,将网络对齐问题抽象为最大公共子图问题(α-MCS),并提出求解自适应参数的方法,相比于传统的基于启发式定义参数的方法,该方法可有效区分不同类型网络中匹配用户与非匹配用户;其次,为快速而准确地解决-MCS,提出了基于最大公共子图的迭代式网络对齐算法MCS_INA(α-MCS based iterative network alignment algorithm),该算法每次迭代过程主要包含两个阶段。第1个阶段,分别在两个社交网络中选取各自的候选匹配用户,第2个阶段,针对候选匹配用户进行识别。相比于其他算法,MCS_INA时间代价低,且依据不同网络特征,通过参数估计,可保证较高的识别精度;最后,在真实数据集和合成数据集中验证了算法MCS_INA的有效性。

基于拓扑子图与编辑距离的距离测量方法

图结构数据搜索的核心是为图的匹配寻找一个好的相似性测量方法。图编辑距离法和最大公共子图法是现有的两种较成熟的测量方法。图编辑距离法善于描述细小的距离差距,但缺乏结构上的描述;最大公共子图法与之相反,在结构描述上很有优势,但是在细节的描述上很弱。鉴于这种情况,将最大拓扑公共子图法与编辑距离测量法相结合,提出了一种新的相似性测量方法。这种方法先用拓扑公共子图进行结构性描述,然后利用编辑距离的细节描述能力对最大拓扑公共子图内部的相似性距离进行调整,从而有效地发挥了最大公共子图法和编辑距离法各自的优点,使得图之间的相似性衡量更加有效、精确;同时在图的相似性搜索、图像检索、对象识别等领域也更有相容力和理解力。

基于顶点冲突学习的最大公共子图算法

针对最大公共子图(MCS)的传统分支策略依赖于图的静态属性,缺少学习历史搜索信息的问题,提出了基于顶点冲突学习的分支策略。首先,把上界的减少值作为分支点完成匹配动作的奖励;其次,由于当最优解被更新时,得到的最优解是分支点不断推理产生的结果,因此给予在完整的搜索路径上的分支点适当的奖励,从而强化这些顶点对搜索的积极作用;最后,设计了匹配动作的价值函数,并选择具有最大累计奖励的顶点作为新的分支点。在McSplit算法基础上,提出了糅合新分支策略的McSplitRLR算法。实验结果表明,除去均可以被所有对比算法在10 s之内解决的简单算例,在相同机器和求解限制时间条件下,相较当前先进的算法McSplit、McSplitSBS,McSplitRLR分别多解决了109、33个困难算例,求解率分别提高了5.6%、1.6%。

三维装配模型共性结构发掘方法

为了更好地利用三维装配模型可重用的共性结构信息,减少重复性的劳动,缩短产品的开发周期,提出一种三维装配模型共性结构发掘方法.首先,以三维装配模型各零件的属性邻接图为基础,保持装配特征属性信息,简化非装配特征属性信息,形成属性化装配特征邻接图;然后,基于三维装配模型各零件之间的装配关系,将零件的属性化装配特征邻接图组合形成三维装配模型属性邻接图;其次,通过频繁子图挖掘算法提取三维装配模型的共性结构.最后,以一组夹具模型为例进行实例验证,结果表明该三维装配模型共性结构发掘方法能够准确有效地发掘产品中的共性结构信息,具有良好的应用效果.

基于元结构匹配与有偏采样的图相似度计算方法

作为图分类、图相似搜索等诸多图数据分析任务的核心步骤,图相似度计算一直是备受研究者们所重视的一个热点问题.由于传统图相似度计算方法的复杂性,无法适用于实时计算节点较多的图相似度任务,针对此问题研究者们提出了新型的基于图神经网络的图相似度计算方法.然而这些算法虽有效加快了图相似度的计算,但是仍然存在两方面的不足,从而影响了他们的性能:(1)多数现有工作通过节点级或图级嵌入的比较来衡量图之间的相似度,忽略了大图中丰富的局部结构特征;(2)所有现有工作均随机采样生成图对数据,导致样本包含的结构不均匀,训练所得模型只对部分特定结构敏感因而误差较大.为此,本文提出了一种新颖的基于元结构匹配与有偏采样的图相似度计算方法MB-GSC(Meta-Structure Matching and Biased Sampling based Graph Similarity Computation).首先提出GSE(Graph Structure Extraction)算法提取图中元结构并构建图的结构分布向量,然后基于此向量提出有偏采样策略RSG(Representative Sample Generation)进行代表性样本的生成,用于后续模型训练.同时,提出算法MSA(Meta Structure Alignment)对提取到的元结构进行最优匹配对齐,从而获取公有结构形状差异与特有结构数量差异,进而构建蕴含有效的局部相似信息的子结构相似向量.最后,在模型中集成节点级成对比较相似向量、图级神经张量网络相似向量、子结构相似向量进行图对相似性计算.为验证算法的有效性,采用5个评估指标在4个真实数据集上与基准方法进行了大量对比实验,对模型性能进行全面评估.实验结果验证了本文所提算法MB-GSC能够更准确且高效地计算图之间的相似度,在GED预测、MCS预测任务上的准确度比现有模型分别提升11.16%、7.45%,且在保证相同准确率的同时使训练样本数平均减少54%.