奖励-收集Steiner树问题的精确算法

奖励-收集Steiner树问题是图的Steiner最小树问题的衍生,同时也是组合优化中的NP-hard问题。首先,提出该问题的数学性质并给出证明,利用数学性质能降低该问题的规模;其次,基于该问题的数学性质设计出上下界子算法、降阶子算法和回溯子算法,通过上下界子算法和降阶子算法可以降低该问题解空间的规模,从而缩短回溯子算法的搜索时间,进而降低求解该问题最优解的时间;最后,应用案例分析、算例分析以及算法分析与对比表明,所设计的算法不仅可以求出该问题的最优解,而且比没有考虑该问题数学性质的一般回溯算法的时间复杂度更低。

基于二叉树及不定长子树的集合子集求解回溯算法

回溯算法按深度优先在搜索树中进行搜索,搜索过程中不满足问题的约束条件则进行剪枝,适用于求解组合数较大的问题。提出基于二叉树及不定长子树的集合子集求解回溯算法,算法设计采用相容性技术,在搜索过程中不需要剪枝,可求解出所有的集合子集,算法时间复杂度较理想,算法运行效率高。基于不定长子树的集合子集求解回溯算法复杂度为O(2^(n)),问题求解规模增大时,算法效率更高。

基于并行子树构建的XML解析方法

XML解析的高耗时特点制约着XML应用系统整体性能的提高,并行化是一种重要的优化手段。现有的并行XML解析算法存在的问题是需要通过预处理进行数据划分,才能实现分片并行完全解析处理。预处理往往很耗时,若进行优化处理,则实现复杂。提出的方法可实现对XML数据任意分片直接进行解析,并行构建各个片断中的子树,再通过子树合并获得全局的文档树。实验结果表明该方法能有效利用多核计算环境,并行实现XML解析。

中文作者共被引分析系统可视化实现研究

作者共被引分析可视化可以直观地表现一个学科的结构，国外已有一些相关的英文实验系统。本文主要叙述了中文作者共被引分析系统可视化研究的实现方法，给出了实现原理与总体结构所包括的三个模块。通过合理划定子树布局区域、限定可分配角度，排列子节点，建立了完整的实验系统，实现了共被引次数居于前lO位的作者的关联图视；系统还实现了人机交互，支持在人工监督下进行连续分析，具有作者研究简历面查询等功能。更换为其他文种的数据库，本文方法也可以用来表示相应的作者共被引分析可视化结果。

面向IPv6物联子网的轻量级树型转发模型

在IPv6物联网中,RPL路由模型已得到广泛的认可.然而对于规模较大的多跳网络结构,RPL面临着部分转发节点路由容量较大的问题.而且物联子网中扁平化的地址结构使得这一问题更为突出.设计了支持IPv6地址自动分配的轻量级树型转发模型TFAD(tree forwarding model with address automatically distributed),将物联子网中的节点构造成一棵层次转发树,树节点的IPv6地址在子树范围内高度聚合.各节点只需存储与其子节点数相当的转发项,即可完成TFAD模型的数据转发.此外,设计了TFAD模型的备份父节点机制,当网络出现故障时能够以子树为单位进行网络拓扑重构,实现物联子网的快速路由恢复.实验验证了TFAD模型的高效路由存储性能以及快速的路由学习能力和故障后路由恢复能力.

分布式全局频繁项目集的快速挖掘方法

针对传统的分布式全局频繁项目集挖掘算法存在大量的候选项目集,且求全局频繁项目集的网络通信代价过高等问题,提出了一种分布式数据库的全局频繁项目集快速挖掘算法(FDMA).该算法改进了频繁模式树(FP-树)的结构,将双向FP-树改为单向,每个节点只保留指向父结点的指针,减少了指针数,由此可节省1/3的树空间;同时通过传送用3个很小的数组表示的被约束子树,在此挖掘全局频繁项目集的过程中不再生成大量候选项目集或条件FP-树,从而减小了网络通信量,提高了挖掘效率.实验表明,所提算法的挖掘速度比传统的分布式数据库数据挖掘算法至少提高了1倍之多,随着数据库规模的增大,它的扩展性将更好.

基于加权频繁子树相似度的网页评论信息抽取

针对现有网页信息抽取方法普遍存在人工耗时大、抽取准确率低等问题,提出了一种基于加权频繁子树相似度的网页评论信息抽取方法 WTS。首先通过视觉特征对网页进行剪枝处理;然后,通过深度加权的相似度度量方法抽取最佳频繁子树;最后,通过子树对齐方法抽取评论路径并解析评论内容。通过对京东、苏宁等网站的评论内容抽取实验,验证了WTS方法比D-EEM、POL等方法在抽取产品评论信息上具有一定的优势。

存在XML强多值依赖的XML Schema规范化研究

为了解决不完全信息环境下XML模式设计中XML文档的数据冗余和操作异常,研究了不完全信息环境下存在XML强多值依赖的XML Schema规范化问题;提出了XML Schema、符合XML Schema的不完全XML文档树等概念;基于子树信息等价和子树信息相容的概念给出了XML强多值依赖的定义;提出了弱键路径和XML强多值依赖弱范式的定义;通过实例分析了在XML Schema中XML强多值依赖引起数据冗余的原因,提出了转换规则,给出了规范化算法。研究成果可较好地处理XML文档中出现大量不完全信息时的数据冗余问题,实现不完全信息环境下更好的XML Schema设计。

在单向FP-tree上挖掘频繁闭项集

频繁闭项集提供了频繁项集的一种完整的、最小表示。针对稠密数据集,提出一种基于单向FP-tree的频繁闭项集挖掘算法Unid_FP-FCI。该算法在挖掘过程中只生成被约束子树,而它是一种虚拟的树结构,在原有的单向FP-tree基础上用三个很小的数组来表示,因而避免了以往算法需递归构造条件FP-tree来计算频繁闭项集的弊端,极大地降低了内存空间和时间开销,提高了挖掘效率。

Web信息抽取技术在统一检索系统中的应用研究

结合统一检索系统的信息抽取特点,应用基于HTML结构的信息抽取方法,介绍人工找到切割关键信息块的标记和位置的方法,最后提出基于子树广度的Web信息抽取方法,并给出了抽取规则的实现方案及实例。实验证明,该方法在基于Web过程模拟的统一检索系统中能保证很高的数据抽取回召率和查准率,并且成功应用于四家省级科技文献共享平台。

基于共享子树的组播状态聚合新方法

网络层组播存在的可扩展性问题导致路由节点需要记录的组播路由状态数量非常庞大,严重影响了组播技术的推广应用。创建了一种基于共享子树的网络组播状态聚合方法SSMM,首次提出将不同组播树之间互相重叠的子树聚合为单一的共享子树,且完全基于MPLS组播技术设计,大量减少了组播状态数量。SSMM不需要服务器集中计算组播路径,易于实际应用。性能分析和仿真试验证明其优于以往相关工作,较好解决了网络组播的可扩展性问题。

基于图文有效信息量的网页正文定位

在现有的网页抽取技术中,正文定位方法仅考虑网页文本信息,当正文图片信息较多、文本信息偏少时,容易出现偏差,且定位准确率较低。针对该问题,从信息论角度出发,结合网页中的文本信息图片信息,设计一种对网页中图片信息量和有效信息量的估算方法,在此基础上,提出一种基于图文信息量的网页正文定位算法。实验结果表明,该算法在不同正文文本量的情况下,均具有较高的定位准确率。

基于子树广度的Web信息抽取

提出一种新的网页信息抽取方法,基于子树的广度可不加区分地对不同科技文献网站的页面信息进行自动抽取。对大量科技文献网站进行信息抽取实验,已应用到甘肃省科技文献共享平台。实验结果证明,该方法能不依赖科技文献网页的来源而自动地抽取相关信息,并能保证较高的数据抽取回召率和查准率。

基于最小相关实体子树的XML关键字查询算法

针对目前XML关键字查询结果中包含了许多无意义的节点的问题,提出了一种语义相关的查询算法。由于XML文档具有半结构化和自描述的特点,通过充分利用节点间的语义相关性,提出了最小最低实体子树(SLEST)的概念,在这个概念中,关键字之间仅存在物理连接关系;为了捕获关键字之间的IDREF引用关系,提出基于最小相关实体子树(SIEST)的算法,并利用最小最低实体子树和最小相关实体子树代替最小最低公共祖先(SLCA)作为查询结果。实验结果表明,提出的算法能有效提高XML关键字查询结果的查准率。

基于亚像元估测的城市硬化地表景观格局分析

城市硬化地表不仅是影响城市生态环境质量重要因子,也是定量描述城市地表物理特征,进行城市景观分类的基础。基于多种分辨率遥感影像亚象元分类提取硬化地表成为近年来的研究热点。利用TM/ETM+和Quickbird不同分辨率遥感数据,以北京市中心城区为研究区域,对比分析回归树法和多元回归法的估测精度,选出预测硬化地表指数(Impervious surface index,简称为ISI)最优估测模型,并进行景观分类与城市景观格局分析。结果表明:(1)回归树亚象元估测法是提取硬化地表信息的一种有效的方法(最大相关系数=0.94),不同季节遥感影像可以挖掘地物在不同时期光谱差异,提高分类精度。(2)根据硬化地表指数划分城市用地类型,提供了量化分类的依据;(3)北京城市硬化地表景观格局表现出极强的空间梯度性,从北京市中心到郊区,ISI逐渐降低:城市二环以内,ISI平均值为67.32%,集中分布在高于60%范围;二环-四环分布比较相似,平均值分别为65.91%、66.13%;四环-五环区域ISI下降迅速(ISI=46.42%),存在两个高峰,分别是低于<20%和>70%;六环以外区域,非硬化地表成为主要类型(ISI=9.32%);(4)北京市景观格局在不同区域差异巨大:从市中心到市郊,景观破碎化程度加强,平均斑块面积逐渐增加,高密度城市用地比例逐步下降,自然地表平均面积呈现U形分布;中等密度城市用地斑块密度最高,破碎度最高;城市用地形状比自然地表复杂,低密度城市用地形状最为复杂。(5)运用回归树亚象元估测法提取出北京中心城区硬化地表信息,为城市地表景观特征提取与高精度量化分类提供了新的研究方法与研究思路,在此基础上进行了景观分类及景观格局分析,进一步推广并论证了硬化地表在景观生态学研究中的应用价值。

面向序列规划的装配工艺APS树模型生成的研究

分析了现有装配序列规划方法和装配序列表达模型的缺陷,提出了一种合理的装配工艺APS树模型,并用这种模型表达非线性的装配序列。利用产品功能结构树和零部件的信息,采用基于装配关系图分割的几何推理和基于规则的知识推理的方法来简化工艺子装配体的识别,以此生成装配结构树。然后,利用装配知识判定子装配体的装配优先约束关系,提高由装配结构树生成装配工艺APS树的效率。最后,基于装配结构树,通过不断添加数据节点和关系节点,自上而下分层规划,从而生成产品的装配工艺APS树。

基于XML Schema的XML强多值依赖的推理规则集

XML强多值依赖的推理规则集问题是解决不完全信息环境下XML数据依赖蕴涵问题的基础,是不完全信息环境下XML模式设计理论的关键问题之一。提出了XML Schema、符合XML Schema的不完全XML文档树等概念;基于子树信息等价和子树信息相容的概念提出了XML强多值依赖的定义及性质;给出了相应的推理规则集,并对其正确性和完备性进行了证明。研究成果为不完全信息环境下存在XSMVD的XML Schema设计奠定了基础。

基于决策树的亚健康状态判定及其与中医体质分类相关性研究

目的:基于决策树模型,进行亚健康状态判定,并研究与中医体质分类的相关性。方法:对中国中医科学院广安门医院体检人员进行健康状态辨识与影响因素的调查,并经两名具有副主任医师以上职称的中医师判断:515例体检人群中,剔除疾病状态人群后,剩余健康9例(1.74%),可疑亚健康87例(9.07%),亚健康状态419(80.89%);采用SPSS 17.0决策树CART算法,对筛选后的影响因素进行决策树分析,归纳出模型的诊断规则,并采用10层交叉验证模型的识别正确率和体质归类。结果:经单因素分析提取有统计学意义的影响因素共66个,将其放入决策树模型,从中挑选出18个相关因素,25条诊断规则。10层交叉验证模型识别正确率为89.02%。结论:决策树模型能够较好的反应和识别亚健康状态,且决策树模型中医体质分型与亚健康状态偏颇体质人群符合率为59.46%,平和质人群则只有40.54%,因此偏颇体质可能是影响亚健康状态的基础因素,从而为疾病的体质预防提供一定的依据,也为临床研究亚健康及辅助诊断亚健康提供思路。

一种基于TFP树的频繁项集改进挖掘算法

FP-growth算法是一种被证明有效的频繁模式挖掘算法。但是由于在挖掘频繁模式时需要递归地生成大量的条件FP-树,其时空效率较低,本文针对这一问题,首先构造一种改进的TFP-树结构,然后在构造的TFP-tree基础上引入被约束子树提出一种基于TFP树的频繁项集的改进挖掘算法,并对该算法进行性能分析,结果证明该算法在运行速度得到很大提高。

基于全条件独立的贝叶斯网络MPD-JT构造算法

针对求解贝叶斯网络最大主子图存在的NP(non-deterministic polynomialtine)难问题,提出了一种基于全条件独立结构的最大主子图连接树(maximal prime sub-graph decomposition junction tree,MPD-JT)构造算法。该算法通过道义图上的全条件独立结构得到贝叶斯网络最大主子图,并利用构成这些最大主子图的节点作为簇节点构造连接树,避免了三角化过程,而且在求解过程中通过删除一些符合条件的点,大大降低了算法复杂度。给出了算法的理论证明,通过具体案例分析验证了算法的有效性。