基于序列树的增量式序列模式更新算法

在序列数据库更新时,现有的增量式序列模式挖掘算法只提到序列的插入操作和序列的扩展操作两种情况,没有针对序列删除操作。提出了一种基于序列树的增量式序列模式更新算法(ISPST)。当数据库更新时,ISPST算法只需要对与删除序列有关的序列构造投影数据库,实现对序列树的更新操作,通过深度优先遍历序列树得到更新后数据库中的所有序列模式。实验结果表明,当支持度发生变化时,ISPST算法在时间性能上优于PrefixSpan算法和IncSpan算法。

基于频繁序列树的交互式序列模式挖掘算法

为了减少在序列模式挖掘过程中由于重复运行挖掘算法而产生的时空消耗,提出了一种基于频繁序列树的交互式序列模式挖掘算法(ISPM)。ISPM算法采用频繁序列树作为序列存储结构,频繁序列树中存储数据库中满足频繁序列树支持度阈值的所有序列模式及其支持度信息。当支持度发生变化时,通过减少本次挖掘所要构造投影数据库的频繁项的数量来缩减投影数据库的规模,从而减少时空消耗。实验结果表明,ISPM算法在时间性能上优于PrefixSpan算法和Inc-Span算法。

一种基于频繁序列树的增量式序列模式挖掘算法

针对目前现有的增量式序列模式挖掘算法没有充分利用先前的挖掘结果,当数据库更新时,需要对数据库进行重复挖掘的问题。本文提出一种基于频繁序列树的增量式序列模式挖掘算法(ISFST),ISFST采用频繁序列树作为序列存储结构,当数据库发生变化时,ISFST算法分两种情况对频繁序列树进行更新操作,通过遍历频繁序列树得到满足最小支持度的所有序列模式。实验结果表明,ISFST算法在时间性能上优于PrefixSpan算法和IncSpan算法。

基于FP序列树的法文词语提取方法研究

法语复杂的语法和词形变化规则导致N-gram等词语提取方法的效果无法保证,影响法语文本挖掘的准确性。该文提出一种高效的法文词语提取方法,从待分析的法语文本中自动获取包括单词和短语的词语集合,构建法语文本挖掘所需的词库。该方法把文本中的单词共现信息压缩为FP序列树结构,快速提取频繁词串并计算其成词度,得到法文词语集合。实验表明,该方法的准确率高达90%,且具有比现有法文词语提取方法更高的召回率,能有效支持法语文本挖掘应用。

基于序列公式树模型的电学问题解答方法

自适应理解和求解语义多变的问题文本是机器解答电学问题的关键挑战,现有方法多侧重于问题文本的语义分析和结构分析,无法将问题文本解析为类人解答的求解形式。为此,构建一种基于序列公式树模型的电学问题解答方法。首先通过问题文本预处理标准化文本元素、关系提取,生成预编码序列和直陈关系序列。其次使用双向门控循环编码器对预编码序列进行特征编码,生成隐藏状态序列。再通过构建电学定理图,使用图卷积神经网络(GCNN)编码器建立直陈关系序列和定理之间的关联关系,将定理图中的关系结点转化为向量表示,生成公式结点嵌入状态序列,并提取不同变量之间的隐含电学关系。最后构建树形结构的解码器对隐藏状态序列和公式节点嵌入状态序列进行解码,形成问题的序列-公式树结构的求解式,实现电学问题的可读解答。构建一个包含3027个电学问题的数据集TexPE-3K,并对其进行标准化和信息标注。在数据集TexPE-3K上的实验结果表明,关系提取的平均准确率达到了96.8%,可读解答的平均准确率达到了55.57%,验证了该方法的可行性和有效性。

基于一种树模型的装配序列优化生成的研究

分析了装配序列评价的特点,提出了一种用于表达装配序列的树模型及其生成算法。阐述了装配序列二级分层综合评价与优化的方法,提出了利用熵权法来确定各评价指标的权重,利用模糊综合评价方法对该装配序列树模型中每层关系节点A或节点AP下的各数据子节点进行装配顺序的优化,最终生成优化的装配序列。该方法缩小了装配序列解空间,提高了装配序列的评价效率,并以齿轮减速器为例进行了验证。

序列树的构造

图G的标号是指G的顶点集到一个整数集的映射g且由g(u)和g(v)诱导出边e=uv的标号g^1.定义了序列树的根积和根粘接的运算,并研究了序列树的根积和根粘接的序列性,得到了一类新的顶点数较多且非毛毛虫的树为序列图.

树积序列性及序列标号

图G的标号是指G的节点集到一个整数集的映射g,且由g(u)、g(v)诱导出边euv的标号.本文定义了序列树的根积运算,并研究了满足一定条件的序列树的根积的序列性,得到了一类新的节点数较多且非毛毛虫的树为序列图.

一种基于测试序列失败树的动态测试方法

针对传统的测试方法按照静态的顺序执行预先生成的固定测试集,而实际测试范围可能被缩小,同时测试结果受到测试序列间、测试序列内的影响等问题,提出了一种构造测试序列失败树(TSFT)并用其指导动态测试的方法.该方法考虑到了测试序列之间的相关性和已测结果对后续测试的影响,通过TSFT指导测试序列的动态执行,同时还考虑了引导序列和验证序列对测试结果的影响,在避开TSFT的前提下,可在引导序列和验证序列集合中进行搜索和替换,动态地生成新的有效测试序列.实验结果表明,所提方法避免了一些重复测试以及错误转换对正确转换的测试结果的影响,较明显地提高了实际的测试效率和测试覆盖率.

基于遍历序列的构造树的算法

人们提出了一些由一棵二叉树或严格二叉树的某两种遍历序列以及某种遍历序列和结点的某种信息构造该二叉树或严格二叉树的算法.根据基于遍历序列的唯一确定树的方法,提出一些新的由一棵树的某两种遍历序列以及某种遍历序列和结点的某种信息构造该树的算法,为构造树提供更多的途经.

图的广义树序列

设P(G)=λ(λ-1)r1…(λ-m)rm,则称(1,r1,…,rm)是一个指数序列.本文证明了,当m=n-1,若1≤i<i+c≤n-1,则当ri=ri+c=2,rk=1,(k≠i,i+c),并且1≤i≤c+2时,该序列是一个广义树序列.

基于同步树序列替换文法的统计机器翻译模型

基于短语的模型是目前发展相对成熟的一种统计机器翻译(Statistical machine translation,SMT)模型.但基于短语的模型不包含任何结构信息,因而缺乏有效的全局调序能力,同时不能对非连续短语进行建模.基于句法的模型因具有结构信息而具有解决以上问题的潜力,因而越来越受到研究者们的重视.然而现有的大多数基于句法的模型都因严格的句法限制而制约了模型的描述能力.为突破这种限制并将基于短语的模型的优点融入到句法模型中,本文提出一种基于同步树序列替换文法(Synchronous tree sequence substitution grammar,STSSG)的统计机器翻译模型.在此模型中,树序列被用作为基本的翻译单元.在这种框架下,不满足句法限制的翻译等价对和满足句法限制的翻译等价对都可以融入句法信息并被翻译模型所使用.从而,两种模型的优点均得到充分利用.在2005年度美国国家标准与技术研究所(NIST)举办的机器翻译评比的中文翻译任务语料上的实验表明,本文提出的模型显著地超过了两个基准系统:基于短语的翻译系统Moses和一个基于严格树结构的句法翻译模型.

分布式环境下全局序列模式挖掘技术研究

由于分布式环境下挖掘全局序列模式常常产生过多候选序列,加大了网络通信代价。为此提出一种基于分布式环境下的全局序列模式快速挖掘算法。该算法将各站点得到的局部序列模式压缩到一种语法序列树上,避免了重复的序列前缀传输;基于合并树中节点序列规则和简单的特点,提出一种项扩展和序列扩展剪枝策略,有效地约减了候选序列,减少了网络传输量,从而快速生成全局序列模式。理论和实验表明,在大数据集环境下该算法性能优越,能够有效地挖掘全局序列模式。

DMGSP:一种快速分布式全局序列模式挖掘算法

为了解决分布式环境下挖掘全局序列模式常产生过多候选序列,加大网络通信代价问题,提出了一种基于分布式环境下的快速挖掘全局序列模式算法——DMGSP.该算法将分布式环境下的各站点得到的局部序列模式压缩到一种语法序列树上,避免了重复的序列前缀传输.采用合并树中结点序列规则和项序扩展策略,对非频繁序列进行剪枝,有效地约简了候选序列,减少了网络传输量,从而快速生成全局序列模式.算法分析和实验结果表明,在大数据集环境下的DMGSP算法性能优越,能够有效地挖掘全局序列模式.

缩减投影数据库规模的增量式序列模式算法

在增量式序列模式挖掘算法中,数据库更新只有插入和扩展2种操作,未考虑序列删除的情况。为此,提出一种基于频繁序列树的增量式序列模式更新算法(IUFST)。在数据库和支持度发生变化时,IUFST算法分不同情况对频繁序列树进行更新操作,缩减投影数据库的规模,提高算法效率。实验结果表明,该算法在时间性能上优于PrefixSpan算法和IncSpan算法。

大数据环境下基于前缀树的频繁项集挖掘

针对大数据环境下频繁项查找效率低和可扩展性问题,提出了一种基于MapReduce框架运行的新分布式FIM算法。首先,使用前缀序列树来构建候选序列子集,避免了昂贵的扫描过程。接着,使用宽幅支持度的方法产生频繁项集,每个MapReduce迭代将修剪掉非频繁项集,显著地压缩内存消耗,以及每一个MapReduce作业的迭代时间。最后,在不同事务规模和支持度下,与不同算法进行实验对比。实验结果表明,提出的序列增长算法获得了良好的效率和可扩展性,特别是在处理大数据集和长项集方面。

一种高效的增量式序列模式挖掘算法

现有的增量式挖掘算法在支持度发生变化时,需要对序列数据库进行重复挖掘,为减少由此产生的时空消耗,提出一种高效的增量式序列模式挖掘算法。算法采用频繁序列树作为序列存储结构,当序列数据库和最小支持度发生变化时,通过执行更新操作,实现频繁序列树的更新,利用深度优先遍历频繁序列树找到序列数据库中所有的序列模式。实验结果表明,与IncSpan算法和PrefixSpan算法相比,该算法的挖掘效率较高。

一类广义树的色性

本文证明了图G是树序列为的广义树的充要条件是G的色多项式为 P(G;λ)=λ(λ一1)p(λ-2)…(λ-q+2)2(λ-q+1)2(λ-q),这里q=4,5.

K_n的某类树分解

本文对直径较小的树序列证明了Gyarras猜想

基于页面布局相似性的钓鱼网页发现方法

针对钓鱼网页与真实网页布局结构相似的特点,提出了基于页面布局相似性的钓鱼网页发现方法,该方法首先抽取出网页中带链接属性的标签作为特征,然后基于该特征提取网页标签序列分支来标识网页;接着通过网页标签序列树对齐算法将网页标签序列树的对齐转换成网页标签序列分支的对齐,使二维的树结构转换成一维的字符串结构,最后通过生物信息学BLOSUM62编码的替换矩阵快速计算对齐分值,从而提高钓鱼网页的检测效果,仿真实验表明该方法可行,并具有较高的准确率和召回率。