近似图引导的演化贝叶斯网络结构学习算法

贝叶斯网络结构学习是贝叶斯网络推理及应用的基础.搜索高质量的节点序是贝叶斯网络结构学习的一类重要方法.针对在节点序空间中,搜索高质量节点序存在的难以高效、准确评估解的问题,本文提出了一种近似图引导的演化贝叶斯网络结构学习算法.首先,该算法利用互信息构建无向近似图;其次,该算法通过结合节点序和无向近似图构造有向图结构,将其贝叶斯信息准则评分作为节点序的适应度来高效评估节点序,并在演化优化的框架下,使用提出的基于Kendall Tau Distance的交叉算子和基于逆度的变异算子搜索最优节点序;最后,将搜索到的最优节点序输入K2算法得到其对应的贝叶斯网络结构.在4种不同规模网络上的实验结果表明,该算法在收敛时间和准确度之间取得了较好的平衡,其评分相较于对比算法中的次优解分别提升了10.91%、12.28%、53.96%、10.87%.

近似图包含搜索和索引技术的研究

在对图形数据库中的几种有代表性的传统相似性搜索及索引构造方法进行总结分析的基础上,探讨了近似图包含搜索区别于传统相似性搜索的特征,并且提出了一种针对近似图包含搜索的基于覆盖率和支持度对频繁子模式进行筛选的索引构造算法。实验结果验证了该方法的有效性。

支持近似图查询的Why-Not问题解释方法

why-not问题是为查询结果中的缺失元组找到合理的解释。解决数据库查询中的why-not问题不仅能够帮助用户更好地理解查询,而且能够提高数据库的质量和可用性。为了提高图数据库的可用性,提出了支持近似图查询的why-not问题解释方法。该解释方法不仅阐明了为什么why-not问题没有出现在查询结果中,而且给出了一些修改初始查询图的建议,使得why-not问题能够出现在修改后的查询图的查询结果中。该算法分两部分完成:第一部分为候选修改操作生成阶段,首先利用边频率信息提出候选操作集生成基本算法,接着利用图分解操作提出候选操作集生成改进算法,得到修改初始查询图的候选操作集;第二部分基于对查询图修改操作数最少的代价模型,分别采用贪心算法和回溯法选取候选操作,贪心算法设计了合理的贪心函数,回溯法构建了回溯剪枝树,并提出三种剪枝策略执行剪枝操作,最终选取的候选操作集即为支持近似图查询的why-not问题的合理解释。实验表明,该方法可以快速有效地为近似图查询中的why-not问题提供合理解释。

基于近似子图的规则空间压缩算法

规则空间模型是一种高效的知识结构诊断模型,但较高的规则空间构造代价阻碍了在小规模、实时认知诊断中的应用.为了提高规则空间模型的可扩展性,提出使用近似子图生成理想属性模式集进而压缩规则空间的方法.近似子图能够通过忽略和测试项目无关的属性降低子图规模量级,从而有效缩减理想属性模式集规模,达到压缩规则空间的目的;同时通过构建顶点间的虚拟边模拟领域知识图上的传递依赖关系,使近似子图在不引入额外属性的前提下保持领域知识图上的依赖关系,实现对不合理属性模式的有效过滤.在此基础上,给出了构造规则空间所需的近似子图构造算法以及由近似子图生成理想属性模式集的方法.最后在标准测试集上开展了近似子图与依赖保持子图和顶点导出子图两种方法的性能对比实验,并将近似子图应用于实际教学认知诊断中验证其诊断准确率,实验结果表明近似子图能够在不损失诊断结果准确率的前提下显著压缩规则空间,降低规则空间模型应用于小规模、实时诊断的门槛.

基于卡方统计的近似子图匹配

图查询的应用越来越广泛,其中近似子图匹配是核心技术之一.但是大规模图数据中噪音的存在对近似子图匹配精确度影响较大,为进一步提高近似子图匹配算法的鲁棒性和实时性,提出一种基于卡方统计的近似子图匹配改进算法.在算法预处理阶段,利用统一邻居随机游走距离和高斯影响函数将目标图划分,使得划分后的子图在拓扑结构和标签属性之间达到最佳平衡.在算法匹配阶段,使用卡方统计量捕获的统计显著性来表征近似子图匹配结构相似度,再结合权重系数a调整结构相似度和标签相似度所占比重,其中统计显著性模型能够充分考虑背景结构和顶点邻域中的标签分布,有效处理部分标签和结构失配,从而得到最佳匹配子图.真实数据集中的实验结果表明,该算法效果较好,运算效率较高,可以应用于Toprk近似子图匹配.

一种基于图结构分解的图近似查询方法研究

图近似查询能够得到与查询图近似的结果集,相比较精确查询具有更广泛的应用范围。为提高近似查询的查准率和查全率,提出一种基于图结构分解的查询算法。该算法通过对查询图和目标图进行图结构分解,对其建立图分解索引,利用查询图的最小生成树集得到满足阈值的生成树集,通过图标准编码在索引中快速定位,查找出所有可能的近似结果。实验结果表明,该算法能有效得到近似结果,提高查询速度。

基于近似Voronoi图的移动机器人实时路径规划

运用Voronoi图理论及人工势场理论,研究了一种基于近似Voronoi图的移动机器人实时路径规划的方法,用来实现未知室内环境中移动机器人的自主导航。该方法朝向预先定义的目标点位置来探测室内环境,生成近似Voronoi图,同时利用人工势场法进行避障,生成一条能达到目标点的安全、光滑路径。仿真结果表明,该方法简单且易于实现,同时能够减少规划时间。

关于近似二部图边覆盖染色的一个充分条件

设G是一个简单图,其顶点集为V(G)而边集为E(G).S E(G)称为G的一个边覆盖,如果由S导出的子图是G的一个生成子图.G的边覆盖色数χc′(G)是E(G)所能划分成的最大边覆盖数.已知δ-1χc′(G)δ,由此将χc′(G)=δ的图称为CⅠ类图,否则称为CⅡ类图.显然,图的边覆盖染色分类问题是NP-完全的.给出了近似二部图是CⅠ类图的一个充分条件,而且该条件中的下界是最好的.

用AutoCAD绘制齿轮啮合近似轴测图的一种方法

介绍了一种利用AutoCAD绘图软件绘制齿轮啮合关系近似轴测图的方法,实现了简便快捷作图,具有一定的实际意义。

流模式下有向近似覆盖图算法研究

随着社交网络、交通网络、生物信息网等领域的分析需求快速增长,大规模图数据的处理逐渐成为信息技术领域新的挑战.近似覆盖图技术可以通过选取原图的子图,同时保证子图中任意节点间距离的增加在覆盖因子的约束范围内,从而降低大规模图存储与计算开销.当前相关工作主要研究无向图的近似覆盖图技术,针对于此,提出一种有向近似覆盖图算法,重新定义了簇集以及簇边、桥边、自由边3类关建边,并理论分析基于3类关键边的(3,2)近似覆盖图构建正确性.在此基础上,给出图数据以流模式到达时的近似覆盖图计算算法.算法通过判断边端点的类型进行边的积累聚簇及更新,进而得到全图近似覆盖结果,算法空间复杂度为O(■).最后以基于幂率模型的人工数据集为实验对象,验证算法满足覆盖因子(3,2)的有向近似覆盖图定义,且空间与时间开销较小.

图近似查询算法研究

从数据管理中的近似查询方向,对图数据的近似查询算法进行了研究。依据近似查询的类别,分别介绍了近似查询中的经典算法,并对这些算法进行了详细的分析和讨论,从索引单元以及索引机制比较了各种算法适用的范围以及应用领域。重点阐述和比较了各算法的特点及查询性能,分析了各个算法存在的优势和不足。对近似查询中现有算法的不足及未来的研究方向进行了讨论。

基于邻居向量的近似子图匹配

将近似子图匹配分成节点匹配和边匹配两个阶段。将数据图中所有节点的h-邻居节点表示成向量形式,采用一种启发式推理算法进行节点匹配得到节点对应关系,使用查询节点权重提高匹配相似度,使用节点过滤、索引技术和孤立候选节点提高运算效率;利用邻居向量索引得到匹配节点集合的扩展图,进行边匹配,得到匹配图。在真实数据上进行实验,实验结果表明,该算法效果较好,运算效率较高,可以应用于节点标签稀疏的情况和top-k近似匹配。

基于回溯模式总结的鲁棒近似子图查询算法

为提高近似子图查询(匹配)的精度性和效率,提出一种模式总结重新匹配的近似子图查询算法。当部分嵌入被发现不能成为同构嵌入时,所提算法会生成失败模式。在回溯过程中,与失败模式进行匹配,对无用的部分嵌入进行剪枝,对所有的同构嵌入完成精确枚举。实验在酵母数据集和DBLP数据集上进行,比较无噪声和有结构噪声两种情形下的精确度,与卡方统计法和启发式算法相比,所提算法具有更高的精确度和鲁棒性。对于不同查询数,递归调用次数在10^(7)级,明显低于其它算法。

鲍林近似能级图的新认识

鲍林近似能级图对于理论化学的研究具有很重要的意义。但是,由于它的规律性不是那么明显,因而使用不是太方便。本人通过重新的排列,将复杂的鲍林近似能级图简便化,规律化,实用化。在将方便其与元素周期律联系起来的同时,也大大方便了元素对应其电子、价电子排布式的书写。运用这张能级图,还可以快速地将某个原子的原子序数与其所对应的元素周期表的位置相互联系对应起来,方便计算。

基于近似子图的实时教学认知诊断模型设计与应用

开展个性化教学是实现素质教育至关重要的措施和手段。实现个性化教学的主要手段是使用计算机辅助测验对学生知识结构进行诊断,然后根据诊断结果开展有针对性的资源推送和路径规划等补救教学活动,其核心问题是教学认知诊断模型的构建。当前常用的基于RSM和AHM的教学认知诊断模型虽然能够对学生的知识状态进行高效、准确的诊断,但其生成规则空间的代价较高,在小规模实时诊断应用中效率较低。近似子图是领域知识图在测试项目下的相关子图,其顶点集只包含测试项目中涉及到的认知属性,其边集包括顶点集在领域知识图中直接依赖关系的投影,以及顶点集在领域知识图中间接依赖关系的模拟。近似子图可以降低规则空间规模的量级,满足其构造的实时性要求。基于近似子图的教学认知诊断模型在"Java语言程序设计"课程中的教学实验证明:该模型可以降低构建RSM规则空间的时间代价,在保证诊断准确率的前提下达到课堂实时认知诊断的目的,及时帮助学生发现自身知识缺陷并开展有针对性的补救学习,最终有效改善学生学习效果。针对学生的调查问卷结果也显示,该教学模式较传统课堂更为轻松和高效。

基于近似个体协同的进化子结构发现

SUBDUE是一个主流的图数据挖掘算法。为克服其贪婪式查找易陷入局部极值的问题,将进化算法与爬山算法相结合并引入图数据挖掘,较好地权衡了算法的探查和利用能力。另外,针对图数据挖掘中普遍存在的实例易丢失的问题,采用了个体协同的查找方法,该方法与常见的种群间协同进化算法不同,可以使同一种群中的个体进行协同查找,重新找回丢失的实例。同时,还给出了一种具有多项式时间复杂度的近似图匹配算法以改善个体间协同的性能。实验结果表明,以上措施增强了算法的执行效率及寻优能力,能够获得更优的解。

正则图同构判定的一个充要条件

给出了正则图同构判定的一个新充要条件,该条件对近似正则图同构判定也是有效的。

能级交错、能级图及电子填充顺序

目前教科书中普遍进行的有关能级交错现象的阐述、鲍林能级图的引用价值以及电子进入轨道顺序等问题有所争议,本文根据有关数据进行讨论,并提出了不同看法.