挖掘不确定频繁子图的改进算法的研究

鉴于图结构能简单方便地描绘复杂的数据以及实际应用中图数据的获得具有不确定性,不确定频繁子图挖掘算法得到广泛的研究。目前一个典型的图挖掘算法是MUSE,但MUSE算法存在期望支持度计算消耗大、时间效率不够高等问题。针对此问题提出了一种基于划分思想混合搜索策略的不确定子图挖掘算法EDFS,它用改进过的GSpan算法进行不确定的子图数据预处理,用裁剪子图模式的搜索空间裁剪不确定子图数据,用基于划分思想的混合策略进行频繁子图的挖掘。子图同构与边存在概率的实验结果证明了EDFS算法能更高效地挖掘出不确定数据频繁子图。     

基于Prim算法的最小生成树优化研究

在图的最小生成树算法中,Prim和Kruskal算法分别适用于稠密图和稀疏图,但两种算法都不能根据图的顶点数、顶点的度数以及边的分布情况自适应地改变自身.由此,对Prim算法进行改进,从图中每个顶点的度数入手,采取删除某些无用边的思想方法,给出了一个寻找最小生成树的算法,使其能动态调整自身的性能,既适合于稠密图,又适合于稀疏图,经实例验证,利用改进的Prim最小生成树算法,根据无向图的顶点数和顶点的度数动态确定求解最小生成树的时间,并将求解的时间复杂度最小化.     

复杂背景下遥感图像密集目标检测

遥感图像中的目标排列密集,常见的检测算法难以较好地区分密集目标,同时目标所处背景复杂,导致在模型生成的特征图中,存在高响应的背景噪声,容易带来错误的检测结果。针对上述问题,在CenterNet算法基础上,提出一种改进权重分配的目标检测算法。在计算热力图损失的过程中,设计一种改进权重分配策略,加大目标边缘区域回传的损失,促进网络对密集目标边缘的学习,减少算法将密集目标认定为单个目标的概率;在CenterNet网络结构中,添加语义分割模块,让网络模型学习每一个目标的分割图,通过分割图抑制特征图中高响应的背景噪声。在DOTA数据集上进行实验,改进算法均值平均精度（mAP）达到68.56%,优于其他方法,和原CenterNet算法相比,mAP提升了6.53个百分点。实验结果表明,改进的CenterNet算法能更好地适应复杂背景下的密集目标检测。     

基于图像显著性识别的自动抠图系统

RC算法引入区域级别的对比度,对颜色模型进行重新量化,能大幅提高处理速度、突出显著目标,然而其基于图的分割算法易出现分割区域不能较好地贴合物体边缘的问题。引入优化的SLIC算法代替基于图的分割算法,对RC算法进行改进,并实现一个基于图像显著性识别的自动抠图系统,克服传统抠图系统必须人工标记的缺点。实验结果表明,相比IT、MZ、GB、RC等经典算法,改进的RC算法抠取的显著目标更精确,其查准率、查全率、F值分别为0.82、0.85和0.83,系统能自动抠取显著目标并提供图片合成应用。     

深度优先遍历图的非递归算法的改进

针对深度优先遍历图的非递归算法与递归算法得到的顶点访问序列不一致的问题,提出改进算法。实验结果表明,改进算法在算法时间和空间性能保持不变的情况下克服了原算法的不足。     

改进图割的显著性区域检测算法

为快速准确地提取图像中的显著性区域,提出一种改进图割的显著性区域检测算法。采用改进的图割算法对图像进行预分割,将图像分成若干子区域,在此基础上利用区域间对比度计算各区域的显著性值,得到图像的显著图,利用迭代阈值分割算法对图像显著图进行分割处理,通过图像去噪完整有效地提取出显著性区域。实验结果表明,该算法能够准确地提取出图像中的显著性区域,与传统方法相比,使用该算法提取出的显著性区域更完整、准确,提高了效率。     

BMGSJoin：一种基于MapReduce的图相似度连接算法

图相似度连接在数据挖掘领域应用广泛,尤其是在数据预处理阶段,可用于数据清理、近复本检测等,其研究具有十分重要的意义。针对基于编辑距离约束的图相似度连接问题进行研究,返回两个图集合中所有编辑距离不超过给定阈值的图对。基于分布式编程框架MapReduce,设计采用“过滤-验证”框架的MGSJoin算法,利用基于路径的q-gram签名实现非解候选对的过滤,计数过滤。鉴于该算法键值对数量庞大的潜在问题,引入Bloom Filter技术对算法进行改进并设计BMGSJoin算法。实验结果表明,提出的两种图相似度连接算法能较大地改善现有算法的效率和可扩展性,并能较好地应对当前大数据挖掘分析的需求。     

贪心线性推移负载平衡算法

针对环与线性阵列的负载平衡速度较慢与迁移量较大的问题,提出一种贪心线性推移平衡算法。该算法适用于任何具有哈密尔顿通路的图结构网络。其平衡过程的负载迁移量一般不大,平衡负载速度较快。对二维网状网等网络结构的贪心线性推移平衡算法进行改进,得到分二阶段的贪心线性推移平衡算法。实验结果表明,此类改进在平衡条件减弱时能较大地提高算法的时间性能。     

一种基于逐点插入Delaunay三角剖分生成Voronoi图的算法

采用改进的逐点插入算法生成Voronoi图。该算法在逐点插入的过程中生成凸壳,进而生成Delaunay三角剖分。在生成Voronoi图的实现过程中,通过遍历三角形的边顶点快速识别相关的三角形组,进而生成Voronoi图。试验结果表明,该算法能实现,成功生成Voronoi图。     

基于图的关联规则改进算法

关联规则挖掘是数据挖掘研究的最重要课题之一。基于图的关联规则挖掘DLG算法通过一次扫描数据库构建关联图,然后遍历该关联图产生频繁项集,有效地提高了关联规则挖掘的性能。在分析该算法基本原理基础上,提出了一种改进的算法—DLG#。改进算法在关联图构造同时构造项集关联矩阵,在候选项集生成时结合关联图和Apriori性质对冗余项集进行剪枝,减少了候选项集数,简化了候选项集的验证。比较实验结果表明,在不同数据集和不同支持度阈值下,改进算法都能更快速的发现频繁项集,当频繁项集平均长度较大时性能提高明显。     

构建贝叶斯网络本质图的新方法

等价类学习是贝叶斯网络结构学习的一个重要分支,而本质图是贝叶斯网络等价类的图形表示,是进行等价类学习的有力工具。针对求解贝叶斯网络结构本质图存在的繁琐问题,提出了一种构建贝叶斯网络本质图的组合算法。该算法从初始非循环有向图开始,对所有有向边进行排序,保持V-结构中的边不变,将不参与V-结构的有向边转化为无向边,依次根据三条规则判定各条无向边在本质图中的方向。给出了算法的理论证明,通过具体案例分析验证了算法的有效性。     

一种改进的Dijkstra算法的分析及程序实现

Dijkstra算法是求有向图中从某一源点到其余各点最短路径的算法。本文通过对传统的Dijkstra算法进行分析,提出一种改进算法,经理论分析,对于顶点数较多而边数较少的有向稀疏图来说,在求最短路径时能够大大提高算法的运行效率。     

基于改进遗传算法的不规则图形排样

针对大规模零件和布料优化排样问题,研究遗传算法在智能排样中的应用及其在智能优化排样中的优缺点。以传统遗传算法优化排样为基础,提出一种改进的基于遗传算法的优化排样算法,利用图形间的相似度对图形群体进行分类,降低遗传算法的时间复杂度。实验结果证明,该方法在时间复杂度上优于传统的遗传算法优化排样,适用于大规模的图形排样系统。     

面向图相似性搜索的高效图编辑距离算法

在图相似性搜索问题中,图编辑距离是较为普遍的度量方法,其计算性能很大程度上决定了图相似性搜索算法的性能。针对传统图编辑距离算法中存在的因大量冗余映射和较大搜索空间导致的性能低下问题,提出了一种改进的图编辑距离算法。该算法首先对图中顶点进行等价划分,以此计算映射编码来判断等价映射;然后定义映射完整性更新等价映射优先级,选出主映射参与扩展;其次,设计高效的启发式函数,提出基于映射编码的下界计算方法,快速得到最优映射。最后,将改进的图编辑距离算法扩展应用于图相似性搜索。在不同数据集上的实验结果表明,该算法具有更好的搜索性能,在搜索空间上最大可降低49%,速度提升了约29%。     

基于任务-资源图的AGVS循环死锁搜索算法的改进研究

针对AGVS中循环死锁搜索算法研究中存在的不能搜索全部的循环死锁的问题,利用任务-资源图提出一个改进算法.改进算法如下:首先,根据AGV的相对位置关系和执行任务的情况,利用任务-资源图(Task-Resource graph,T-R图)对AGVS进行建模,然后根据循环死锁的T-R图特征,在每一个状态时刻下的T-R图使用图的强连通分支理论搜索循环死锁.当访问完所有状态时刻下的T-R图,也就找到了AGVS中的所有循环死锁.算例验证与理论分析均说明改进算法可以搜索到全部类型的循环死锁,解决了原算法存在的不足.根据改进算法开发的控制规则,可以有效避免新循环死锁的产生.同时指出,对改进算法稍加修改,可以找到AGVS中所有的循环死锁和非循环死锁.     

图的几何关系直方图及在匹配中的应用

针对图结构在一些非刚性变换下谱特征不稳定等问题,提出一种基于几何关系直方图的图结构信息的描述方法,并在此基础上实现图的顶点匹配。首先通过夹角和距离等一些几何量来描述图的顶点与其他各边的位置关系,然后结合直方图给出一种图顶点的特征描述,最后采用改进的匈牙利算法实现图的匹配。不同于传统的描述方法,该方法是利用图的顶点与边的几何关系的统计特征来描述图的结构信息。其结构简单,信息描述充分。实验结果表明,方法对于一些扰动前后的图的匹配具有较高的匹配准确度。     

高校学分制环境下排考问题的改进图算法

本文利用图论模型的转化,改进传统贪心算法,设计了一种新的求解高校排考问题的图算法.改进后的算法可以更好应对在现实学分制环境下,跨年级、跨专业、主辅修等复杂的选课因素.为了解决传统算法中仅靠人工优化来实现的软约束目标,改进后的图算法首先将排考图着色模型,转化为无向赋权图的分团覆盖模型,通过深度优先策略和赋权机制,求解同时满足排考硬约束条件和软约束条件的排考方案.经过数据验证,改进算法的排考效果,在排考效果上优于传统贪心算法,在时间效率上优于人工排考方式.改进后的新算法在近年我校的期末考务工作中发挥了一定作用.     

基于粗糙数据推理的TextRank关键词提取算法

基于图模型的TextRank算法是一种有效的关键词提取算法,在提取关键词时可取得较高准确度。但该算法在构造图的关联边时,所采用的共现窗口规则仅考虑了局部词汇间的关联,并具有较大随意性与不确定性。针对这一问题,该文提出了一种基于粗糙数据推理理论的改进TextRank关键词提取算法,粗糙数据推理可扩大关联范围,增加关联数据,得到的结果更加全面。结合粗糙数据推理理论中的关联规则,该文提出的算法做了以下改进: 依据词义对候选关键词进行划分;再通过粗糙数据推理对不同分类中候选词间的关联关系进行推理。实验结果表明,与传统的TextRank算法相比,改进后算法的提取精度有了明显的提高,证明了利用粗糙数据推理的思想能有效地改善算法提取关键词的性能。     

基于图论Isoperimetric算法的岩心图像分割

基于图论的图像分割算法是当前图像分割领域研究的热点,其中归一化分割（Ncut）是一种典型的图论分割算法。但Ncut分割的速度慢,分割结果容易受图像的噪声和虚假边缘的影响,难以应用到实际。为此,提出一种基于图论的等周（Isoperimetric）改进分割算法。该算法使用解线性方程的方法代替解特征向量的方法、用4-邻接的方法代替全连接,避免了复杂的空间滤波。该算法运用到岩心图像分割中,提高了分割的效率,取得了较好的分割效果。     

赋权有向图的最小生成树算法

针对赋权有向图最小生成树问题存在可行解的情况,根据树节点入度最大值为1的性质,提出赋权有向图最小生成树性质。采用反证法,调整生成树根节点到弧头的路径来证明赋权有向图MST性质的正确性。基于赋权有向图MST性质,给出改进的Prim和Kruskal算法及其时间复杂度分析。实验给出构造某赋权有向图实例最小生成树的具体步骤,表明这2种算法能正确有效地构造赋权有向图最小生成树。