最大生成树算法和决策式算法相结合的中文依存关系解析

基于最大生成树解析算法和决策式解析算法的互补关系,提出了最大生成树解析算法和决策式解析算法相结合的中文依存关系解析方法。结合方法利用Nivre模型的依存关系解析结果和依存度修正最大生成树模型有向边的权重,再搜索最大生成树作为依存树。使用宾州中文树库中的4 500句语料作十折交叉测试,结合模型的依存关系正确率达到了86.49%。结果表明该文提出的结合方法有效地提高了的中文依存关系解析性能。

最大生成树聚类算法研究

在生物学研究中,需要对基因进行分类,以获得对种群固有结构的认识,有效鉴别基因表示数据的模式是研究DNA序列的重要基础。在已有最大树聚类理论基础上,引入模糊聚类思想,提出了最大树基因聚类算法,同时将该方法用于基因的聚类分析,实验结果表明它们是有效可行的。

基于最大生成树的社团划分算法

针对层次聚类算法存在复杂度高、准确度低等问题,提出了一种基于最大生成树的社团划分算法。该算法重新定义了节点间相似度,并利用最大生成树进行初始聚类,然后根据社团相似度合并局部社团得到最终划分结果。算法不仅降低了时间复杂度,而且在划分社团的准确度方面有所提高。将该方法在真实网络与人工网络上进行验证和比对,实验结果表明基于最大生成树的社团划分算法能够快速、准确地划分出网络中的社团结构。

基于最大生成树的重叠社区发现算法

挖掘复杂网络的重叠社区结构对研究复杂系统具有重要的理论和实践意义。针对局部扩展算法(local fitness method,LFM)随机选取种子节点造成的社区结果鲁棒性较低等问题,提出了一种基于最大生成树的重叠社区发现算法:提出一种新颖的边权重定义,将无权的网络转换为带权重的网络,而且该权重真实反映了网络真实结构;提出一种节点影响力计算方法,反映节点在整个网络结构中的重要程度;提出了一种新的生成候选种子集的方法,并借助最大生成树使得到的候选种子节点在网络中更具有代表性;对初始社区划分结果进行优化,避免社区之间重叠度过多。经仿真实验发现,该算法与经典的重叠社区发现算法相比,无论在真实网络还是LFR人工网络上,均有良好的表现。

求最大生成树的改进的矩阵算法

生成树问题是图论、运筹学、资源优化、物流等中常见的基本问题,本文在生成树常见算法避圈法、破圈法、普里姆算法的基础上研究了最大生成树改进的权矩阵算法,并研究了算法的实际应用.

基于最大生成树的传感器任务分配方法研究

根据集合论中偏序关系集和集合论中的特殊图中生成树的概念,提出了一种传感器任务分配和选择方法.建立了传感器任务分配模型,得到其最大生成树,根据任务的重要程度和传感器在任务中的重要程度来决定传感器的使用.算例分析表明:该方法适合于均匀分布以及指定任务优先级两种情况下的传感器任务分配,计算简单、方法具有规律性,可用计算机程序实现.

最大生成树法在生产中的应用

在工业生产中,对加工零件品种多、设备多、工艺流向不一致的生产车间,加工设备的单行布置一般采用“从至表试验法“。即首先绘制各种加工工艺路线图零件在生产线设备上加工综合图(称为连通图),用破圈法求最大树,由最大树按给定的设备顺序编制从至表;再次通过有限次试验调整改进从至表,求得较优化的单行布置设备方案。这种方法虽然简单,但是对于加工零件品种多、设备多的大车间。

基于生成树的回路核

针对图的相似性问题,提出了基于生成树的回路核,其中包括基于最小生成树的回路核、基于最大生成树的回路核、基于最小生成树或最大生成树的回路核、基于最小生成树与最大生成树的回路核、基于混合生成树的回路核、基于赋权混合生成树的回路核.结果表明,所定义的基于生成树的回路核是可计算的、正定的;在实验中,回路核的识别率高于通路核的识别率,最高可达100%.

重构肿瘤克隆单体型的改进生成树算法

目的基于三代测序数据重构肿瘤克隆单体型,有效识别肿瘤异质性。方法该算法提取混合肿瘤数据中的变异位点数据,通过概率函数求解各体细胞突变位点的连接权值;设计了一种基于最大生成树的单体型重构算法,遵循肿瘤克隆间继承原则逐级扩展最大生成树,以确定克隆中各变异位点的连接模式;采用厚度剥离方法估计求得子克隆个数、配比及演化关系。结果在仿真实验中,分别对测序覆盖度、读段长度、亚克隆数目及体细胞变异率四个指标进行了准确率分析,充分说明了该算法具有良好的鲁棒性;该算法对肿瘤克隆单体型重构精度均值可达到97%以上,与其它工具进行性能比较具有显著优势。结论所提方法可以较为精确的重构肿瘤亚克隆单体型,明晰肿瘤克隆演化过程,为肿瘤异质性研究和临床决策提供理论依据。

基于中文宾州树库的依存句法分析器的比较

依存句法分析作为句法分析的一种,是当前自然语言处理领域的热点问题。文章利用目前应用最广的四类依存句法分析器(斯坦福依存句法分析器、复旦大学依存句法分析器、哈尔滨工业大学依存句法分析器和最大生成树依存句法分析器)对汉语进行了依存句法分析研究。主要对四类依存句法分析器进行了详细介绍,重点对各分析器所采用的模型和算法进行了分析和对比。通过实验,总结了目前依存句法分析研究存在的问题,并对未来的研究发展趋势进行了展望。

多视影像相对方位关系误判检测的置信传播算法

场景模糊或者不同场景中的重复纹理会导致影像匹配时产生大量的误匹配点,从而得到误判的相对方位关系。本文引入概率推论方法,提出了一种改进的误判相对方位关系检测算法,利用回路闭合约束构建了基于影像间相对方位关系的贝叶斯网络,推导了贝叶斯网络中的先验概率模型,并利用置信传播算法解算了贝叶斯网络中最大后验概率的求解问题。试验结果表明,利用本文提出的全局一致性约束方法可以有效检测影像间误判的相对方位关系,改善场景重建的结果,并且具有很高的计算效率。

基于最大熵的依存句法分析

该文提出并比较了三种基于最大熵模型的依存句法分析算法,其中最大生成树(MST)算法取得了最好的效果。MST算法的目标是在一个带有权重的有向图中寻找一棵最大的生成树。有向图的每条边都对应于一个句法依存关系,边的权重通过最大熵模型获得。训练和测试数据来源于CoNLL2008 Share Task的公用语料。预测的F1值在WSJ和Brown两个测试集上分别达到87.42%和80.8%,在参加评测单位中排名第6。

基于时延—带宽约束的新型层次拓扑聚集算法

针对时延—带宽约束的层次路由问题,提出了楼梯法这一全新的拓扑聚集算法。使用一个规则的楼梯来模拟2个边界节点之间的所有通路支持的QoS属性,将原始拓扑压缩为一个六元组标识的全相连图。然后,根据六元组各参数特性对全相连图分别采用了最大生成树和改进的星型压缩算法进行线性压缩。仿真的结果表明,在聚集后信息空间复杂度同为O(|B|)的情况下,楼梯法较其他拓扑聚集算法具有更小的信息失真率。

基于医学影像的血管快速提取与可视化

在计算机辅助诊断系统中,血管的提取与可视化是血管研究的重要组成部分。本研究利用八叉树实现了血管的双阈值快速分割和边界距离场的快速计算;然后建立基于边界距离场的血管组织最大生成树,并提取感兴趣血管分支的树的主干,即该分支的中心路径,最后用基于图形处理器的三维纹理体绘制方法沿着路径显示血管虚拟内窥镜,用曲面重建方法显示该血管分支的相关信息。实验结果表明八叉树能有效的提高血管分割速度,并减少边界距离场的计算时间,体绘制算法和曲面重建方法能快速的显示血管组织的详细信息,为疾病诊断提供技术支持。

基于R-vine-copula-CoVaR模型的金融市场风险溢出效应研究

为了挖掘国际金融市场与中国金融市场的风险溢出效应,本文首先通过ARJI-GARCH模型捕捉单个市场收益率的跳跃等典型事实特征,然后采用最大生成树(Maximum Spanning Tree,MST)算法优化的R-vine来刻画多维金融资产的复杂相依结构;最后构建R-vine-copula-Co VaR模型,测度了国际原油市场、国际黄金市场、美国股票市场与中国股票市场、外汇市场之间的风险溢出效应。实证结果表明:各市场之间均存在双向风险溢出效应,但溢出程度差别很大,国际黄金市场是风险溢出的最大爆发源,仅有中国外汇市场与中国股票市场、国际黄金市场间存在负向风险溢出;市场之间的双向风险溢出效应呈非对称性,国际原油市场与黄金市场的风险溢出效应远大于中国股票市场与外汇市场风险溢出效应;Rosenb-Latt检验表明基于R藤的Co VaR风险溢出测度更具有灵活性和有效性;后验测试结果表明R-vine-copula-Co VaR模型能有效地测度国际金融市场对中国金融市场风险溢出效应,而对中国金融市场风险溢出效应的Co VaR测度存在被高估的可能。

半直觉模糊图与应用

将对象作顶点集,用直觉模糊数刻画对象间的相关性和不相关性表示成直觉模糊边;建立了半直觉模糊图模型。定义了半直觉模糊图的生成子图、度、路径、相关截图、序关系、最大生成树等概念。给出基于半直觉模糊图的聚类分析算法,分析了算法的复杂度。结合经典实例作了基于半直觉模糊图的聚类分析,结果显示基于半直觉模糊图的聚类分析算法复杂度低于一般直觉模糊聚类算法。高效实用且自动化程度高。

三角网格模型的基本群分割

提出一种有效的三角网格模型分割方法。用Dijkstra算法求出三角网格模型上任意给定一个基点到其余顶点的最短路径树;求出该模型对偶图的最大生成树,且对偶图的边与该最短路径树的边不相交;找出该模型上所有既不属于最短路径树也不和最大生成树相交的边,这些边分别与最短路径树组成的最短环集合就是给定基点处的基本群,沿着这些最短环就可以把网格分割成一个拓扑同胚于圆盘的区域。实验结果表明,该分割方法可以快速、有效地实现网格的分割。

基于动态规划的简单语义单元词义消歧

为了更为高效、准确的使用语义信息来进行自然语言处理,提出了一种基于动态规划的简单语义单元词义消歧方法。阐述了语义相关度计算模型,提出简单语义单元的概念,分析了简单语义单元的特点;使用动态规划的方法,依次求出每个多义词所有义项的最大生成树变量;求出语义修饰关系完全图的最大生成树,可将最大生成树转化为最佳语法分析方案,实现词义消歧。实验结果表明,该方法具有一定的可行性。

基于模糊聚类的城市经济发展水平分类

科学定位城市经济的发展水平对于制定城市发展战略规划以及相关政策具有重要的现实意义。将模糊聚类分析应用于城市经济发展水平的分类研究,选取具有代表性的经济指标建立模糊相似矩阵,应用模糊聚类法实现聚类,从而对城市经济发展水平进行分类。

一种基于水下机器人的构筑物场景复原优化方法

为了克服水下构筑物场景复原过程中的累积误差,有效还原水下构筑物的表面结构信息,本文提出了一种基于水下机器人的构筑物场景复原优化方法。通过构建最大生成树,采用基本的图算法寻找基准坐标系以及完成坐标系的转换,并建立了误差方程,选取L-M迭代算法实现变换矩阵的最优化,采用对比实验实现了对该方法的可靠性检测。实验结果表明,采用该优化方法后可有效反映整个探测过程的图像信息,为后续的机器视觉处理建立了有效基础。