支持均匀缩放的不等长时间子序列查询方法

作为时序数据分析中的基础技术之一,时间序列的子序列查询旨在寻找与目标序列相似的子序列。现有的子序列查询方法大多仅支持查询与目标序列长度相同的子序列,因而均匀缩放技术常被用于解决子序列查询中的不等长问题。但现有支持均匀缩放的子序列查询技术大多未考虑子序列的Z-标准化,且对查询效率仍有改善的空间。针对该问题,提出一种基于索引技术且支持均匀缩放的子序列查询方法。结合现有索引方法 ULISSE提供的树状数据结构,设计可保证非漏报的下界距离,为索引结构的剪枝提供理论保证,并利用索引中存储的元数据,提出精确K-近邻查询算法。所提方法适用于非归一化和归一化两种场景。实验结果表明,较UCR-US和ULISSE基线方法,该基于索引的不等长子序列查询方法在CAP、GAP两个真实数据集以及随机游走人工合成数据集上均实现了查询效率的显著提升,针对在非归一化和归一化两种场景下的不等长子序列查询,该方法的平均效率提升分别为2.33和2.51倍。

一种带匹配路径约束的最长公共子序列长度算法

在带约束的最长公共子序列问题中提出一种特殊的新问题:假设有两序列Q和C,Q中指定的匹配位置序列I,计算两序列Q和C的最长公共子序列,且这个最长公共子序列的匹配路径必须经过位置序列I。针对此问题,该文提出一种带匹配路径约束的最长公共子序列算法。首先定义带匹配路径约束的最长公共子序列模型,其次推出该序列的性质,最后求出带匹配路径约束的最长公共子序列长度的基础算法和快速算法。基础算法和快速算法时间复杂度分别为O(mnt)和O(mn),m,n,t分别为序列Q,C,I的长度。

基于状态压缩的最长公共上升子序列快速算法

探讨了最长公共上升子序列(LCIS)问题,在前人算法的基础上提出一种高效求解LCIS的动态规划算法。对于LCIS问题,分别使用最长公共子序列(LCS)和最长上升子序列(LIS)相结合的算法、动态规划算法、经过状态压缩的改进动态规划算法进行设计,并对后两种算法进行了实现。设计的状态压缩的动态规划算法,实现了LCIS的快速求解。通过分析这三种算法的时间和空间复杂度,最终提出了时间复杂度为O(mn)、空间复杂度为O(m)或O(n)的基于状态压缩的快速LCIS算法。

关于子序列数量下界的一个改进

序列删除t个数后会产生不同的子序列,由于序列的结构未知,给计算这些子序列的数量带来了一个难题。为了研究子序列的数量,本文在前人的基础上,采用放缩法,研究了当序列前3个块互不相同时子序列的数量,改进了子序列数量的下界。

最长公共子序列算法在程序代码相似度度量中的应用

阐述了最长公共子序列算法在程序代码结构相似度度量中的应用,列举了两种计算最优值和一种获取最长公共标识符子序列的算法.根据最优值得到结构相似度值,进而可以查找出结构相似程序对.最后探讨了程序代码相似度的实际应用.

基于子序列全连接和最大团的时间序列模体发现算法

针对时间序列模体发现算法计算复杂,并且无法发现多实例模体的问题,提出基于子序列全连接和最大团的时间序列模体发现(TSSJMC)算法。首先,使用快速时间序列子序列全连接算法求得所有子序列之间的距离,生成距离矩阵;然后,设置相似性阈值,将距离矩阵转化为邻接矩阵,构造子序列相似图;最后采用最大团搜索算法从相似图中搜索最大团,最大团的顶点对应的时间序列为包含最多实例的模体。在公开的时间序列数据集上进行实验,选用已有的能够发现多实例模体的Brute Force和Random Projection算法作为对比对象,分别从准确性、效率、可扩展性和鲁棒性对TSSJMC算法进行分析并获得了客观的评判结果。实验结果表明,与Random Projection算法相比,TSSJMC算法在效率、可扩展性和鲁棒性法方面均有明显优势;与Brute Force算法相比,TSSJMC算法发现的模体实例数量虽略低,但其效率和可扩展性都优于Brute Force算法。因此,TSSJMC是质量和效率相平衡的算法。

Kernel-Shapelets:基于卷积网络的特征子序列学习方法

在时序分类领域中,基于特征子序列的方法因能给出个体分类的局部依据,从而具有较强的可解释性,但计算十分耗时,且分类表现相较于深度学习方法并不占优。深度学习方法虽在分类表现上优于其他方法,但缺乏可解释性。为了提高基于特征子序列方法的分类表现,增强深度学习方法的可解释性,提出基于CNN网络提取特征子序列的方法Kernel-Shapelets。该方法通过提取CNN的卷积核对应权重并作进一步筛选,从而提取出特征子序列,利用全局最大池化层的输出找出CNN网络的判断依据,从而提高模型的可解释性。通过在UCR时序数据集上进行实验,Kernel-Shapelets方法的平均分类准确率为82%,相比基于特征子序列的最优基准模型提高了15.4%,证明了Kernel-Shapelets能够利用CNN网络的学习能力提取出更有效、更具有辨识性的特征子序列,提取出的特征子序列也提高了CNN网络的可解释性。

算法分析与设计课程中最长公共子序列问题的教学探讨

介绍算法分析与设计课程中最长公共子序列问题的动态规划算法,利用该算法解决最长递减子序列问题和回文词的构造问题,通过这两个问题的求解,有助于学生举一反三,启发学生思维,以学致用,提高问题求解能力。

结合Hausdorff距离和最长公共子序列的轨迹分类

为了提高运动目标轨迹分类的准确性,该文综合考虑了轨迹的位置信息和方向信息,提出了一种结合Hausdorff距离和最长公共子序列(Longest Common SubSequence,LCSS)的轨迹分类算法。该算法首先采用改进的Hausdorff距离对轨迹的位置信息进行相似性测量,然后采用改进的LCSS算法对轨迹的方向信息进行相似性测量。与其他轨迹聚类算法不同,该算法融合了Hausdorff距离和LCSS两种算法的优点,提高了轨迹分类的准确性。此外,为了进一步降低计算复杂度,该文还实现了一种基于插值的保距变换算法和一种LCSS快速算法。实验结果表明,该轨迹分类算法可以明显提高轨迹的聚类准确率,聚类准确率可达到96%;基于插值的保距变换算法和LCSS快速算法可以很大程度上降低算法的计算复杂度,下降幅度最大可达到80%。该方法可以同时满足轨迹分类对精确度、实时性和鲁棒性的要求。

第一类m子序列的构造

伪随机序列在流密码、信道编码、扩频通信等领域有着广泛的应用,m序列是优秀的伪随机序列.基于m序列,本文首次提出通过重构m序列移位寄存器状态图,构造一类称之为m子序列的移位寄存器状态图.根据重构的状态图,提出了第一类m子序列并予以证明.本文推导了第一类m子序列移位寄存器反馈函数式,分析了第一类m子序列具有良好的周期特性、游程特性、平衡特性以及较高的线性复杂度.仿真结果表明,m子序列自相关特性也具有很好的δ(t)函数特征.利用文中给出的构造方法,可以构造更多性能优良的m子序列.

基于复杂网络和最优子序列双射的形状描述与匹配

本文结合复杂网络理论分析形状特性,对形状建模成基于形状内部距离的小世界复杂网络,分析复杂网络节点的度特征和聚类系数特征,通过复杂网络的动态演化,构造多尺度的关于节点分布的直方图来描述形状;用轮廓点多尺度的度特征、聚类系数特征和内部距离形状上下文特征来描述轮廓点,结合改进的最优子序列双射算法实现形状匹配.实验中分析了复杂网络理论中各特征在形状分析中的描述能力,实验结果表明提出的形状匹配算法能实现一些非刚性变换下的物体形状匹配和较高精度的形状检索.

时态数据的趋势序列分析及其子序列匹配算法研究

针对时态数据挖掘中传统趋势序列分析的缺点,提出了数字趋势序列、趋势序列展开等概念.根据数字趋势序列的特点,使用片段斜率所对应的弧度值来度量片段的趋势.针对数字趋势序列的子序列匹配问题,设计了“DTW双约束快速搜索算法”.算法分为3个部分:DTW顺序搜索、双约束机制、冗余消除机制,其中DTW顺序搜索构成了算法的基本框架,双约束机制加快了DTW距离的计算过程,冗余消除机制消除了最终结果集中的冗余.

带约束最长公共子序列快速算法

带约束最长公共子序列(CLCS)问题有很深的生物学应用背景,常被用来表示同源基因序列相似性的度量,但计算CLCS时间代价很高,最早的CLCS算法的时间复杂度为O(rn4),目前,最快的CLCS算法的时间复杂性为O(rn2).运用对偶原理将带约束最长公共子序列问题转换为带约束最小覆盖集问题,并建立带权的ref树结构,构造包含约束序列的约束覆盖子集,约简带约束覆盖子集并从中搜索关键路径,再通过关键路径构造CLCS,该算法将算法时间复杂度提升到O(nlogn+(q+r)L),r是约束序列的长度,q是两序列序偶的个数,L是两序列的最长公共子序列(LCS)长度.

多维时序数据中的相似子序列搜索研究

由于动态时间弯曲距离较之欧氏距离有更好鲁棒性,因此被广泛用作时序数据相似子序列搜索研究领域中的相似性度量.在单一维度上的相似子序列搜索可能不能获得足够的匹配结果作为继续深入分析的依据,因此通过引入在多维数据分析中常用的数据立方体模型将相似子序列搜索问题扩展到了多维场景之下,从而在多个维度上得到搜索结果以获取更多有价值的知识.在此基础上利用数据立方体相邻层次单元间的相关性对基本的搜索算法进行了改进,在保证准确性的基础上提高了搜索效率.在真实网络安全数据集上的实验验证了所提方法的有效性.

基于LSH的时间子序列查询算法

子序列的相似性查询是时间序列数据集中的一种重要操作,包括范围查询和k近邻查询.现有的大多算法是基于欧几里德距离或者DTW距离的,缺点在于查询效率低下.文中提出了一种新的基于LSH的距离度量方法,可以在保证查询结果质量的前提下,极大提高相似性查询的效率;在此基础上,给出一种DS-Index索引结构,利用距离下界进行剪枝,进而还提出了两种优化的OLSH-Range和OLSH-kNN算法.实验是在真实的股票序列集上进行的,数据结果表明算法能快速精确地找出相似性查询结果.

一种变步长趋势子序列搜索算法

为了克服基于点距离的时间序列相似性搜索物理概念模糊和速度慢的缺点,提出时间序列的分段趋势序列(PTS)概念,并在此基础上提出一种变步长趋势子序列搜索算法.该算法基于时间序列分段线性表示理论,通过相似阈值和子序列间的趋势距离计算跳跃步长,从跳跃步长后开始的子序列进行下一次匹配,从而对全序列实现跳跃式搜索。理论分析和仿真结果表明,该算法对基于趋势表示的子序列搜索在时间和空间上都具有更优的性能,适用于时间序列的动态特征分析.

k-长DNA子序列计数算法研究

基因组的结构与功能存在密切联系,其功能主要通过DNA子序列来表达,因此研究DNA序列结构对于生物信息学来说具有重要的意义。该文研究了k-长DNA子序列在DNA全序列中出现频数的计数问题,设计并实现了k-长DNA子序列内部计数算法和外部计数算法。该算法通过一个哈希函数把k-长DNA子序列映射为整数关键字从而把k-长DNA子序列出现频数的计数问题转化为整数关键字的重复计数问题,使得能够利用经典B树算法来解决k-长DNA子序列的出现频数计数问题。针对所要解决的问题提出3种改进措施以进一步提高算法的性能。

基于闭合有间隔频繁子序列的点击流聚类

对网站日志文件中记录的点击流序列聚类可以发现用户使用模式,从而对用户归类。而传统聚类方法面临着难以提取点击流中有代表性的特征向量以及点击流及其特征向量存在数据稀疏性的问题。针对上述情况,提出一种基于闭合有间隔频繁子序列模式挖掘的点击流聚类方法。该方法从点击流中提取子序列模式的频繁支持度,构建特征向量,利用基于双向映射欧氏距离的模糊距离度量判断向量间相似度,增强BIRCH聚类算法对点击流数据的聚类效果。

基于LLM的时间序列异常子序列检测算法

为了提高时间序列中异常子序列检测算法的有效性,提出一种基于局部线性映射(LocalLinear Mapping,LLM)的异常子序列检测算法.该算法将时间序列子序列通过其相邻子序列线性重构,很好地保留了时间序列子序列与其相邻子序列的相关性.基于LLM的映射特性,使用两种异常指标(贡献因子,重构误差),并将其应用于ST东方(B)股票交易时间序列数据集的异常子序列检测中.实验结果表明,所提出的算法对异常子序列的异常检测具有很好的效果,有效提高了时间序列中异常子序列的检测效率.

求最长公共子序列长度的一个新方法

提出了一个求序列Ｘ最长单调子序列的方法，若Ｘ的长度为ｎ，则此方法所需时间为Ｏ（ｎｌｏｇｎ），空间占用为Ｏ（ｎ）．利用该方法可有效地求出Ｘ，Ｙ两序列最长公共子序列的长度．如果Ｘ的长度为ｍ，Ｙ的长度为ｎ，此时空间占用为Ｏ（ｍ＋ｎ）；若Ｙ中的各个元素在Ｘ中平均重复出现至多常数次，则所需时间为Ｏ（ｍ＋ｎｌｏｇｎ）．作为应用之一，该方法可以用于文本的比较、等级考试录入文本的评测等．