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

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

数据流上快速子序列匹配

数据流技术目前已广泛应用于金融分析、网络监控及传感器网络等诸多领域,而已有的相似性匹配技术主要针对时间序列数据库,难于直接应用于高速、连续、实时、海量的流数据,因此在数据流上渐进、实时地进行子序列匹配成为一个极具价值和挑战性的问题。在动态时间规整技术的基础上,设计了一种新颖的界限机制,充分利用相似性阈值,尽量减少冗余计算,算法完全符合数据流"单遍扫描"的性能要求,并通过大量的模拟和真实数据实验表明:与现有的SPRING算法相比,在不损失任何算法精度的前提下,仅增加几个字节的空间开销,速度至少提高3倍。

一种基于图的近重复视频子序列匹配算法

为了解决近重复视频检测中的效果和效率问题,提出了一种基于图的近重复视频子序列匹配算法。将基于关键帧特征的相似性查询结果构建成匹配结果图,进而将近重复视频检测转换成一个在匹配结果图中查找最长路径的问题。该算法有三个主要优势:a)它能在众多杂乱的匹配结果中找到最佳的匹配序列,有效剔除了某些假"高相似度"匹配带来的噪声,因而能在一定程度上弥补底层特征描述力的不足;b)由于它充分考虑和利用了视频序列的时序特性,具有很高的近重复视频定位准确度;c)它能自动检测出匹配结果图中存在的多条离散路径,从而能一次性检测出两段视频中可能存在多段近重复视频的情形。提出的算法不仅提高了检测的准确度,而且提高了检测效率,取得了良好的实践效果。

海量数据流上快速Top-K子序列匹配算法研究

数据流技术在金融分析、网络监控等诸多领域得到了广泛应用,而已有的子序列匹配算法主要针对静态序列,难于直接应用到海量、高速和连续的流数据。本文在动态时间规整技术的基础上,提出了一种新颖的TopKSM算法,能渐进、实时地获取Top-K相似子序列。算法完全符合数据流"单遍扫描"的性能要求。大量的实验表明,与现有的SPRING算法相比,该算法具有更高的性能。

数字趋势序列的子序列匹配算法

针对时序数据挖掘中传统趋势序列分析的缺点,提出了数字趋势序列、趋势序列展开等概念.根据数字趋势序列的特点,使用片段斜率所对应的弧度值来度量片段的趋势.针对数字趋势序列的子序列匹配问题,设计了DTW(Dynamic Time Warping)快速搜索算法.算法分为3个部分:DTW顺序搜索、约束机制、冗余消除机制.并使用实际的股票数据对算法进行了验证.

一种基于动态时间弯曲的数据流子序列匹配系统

随着工业生产中数据源的不断增加,人们对数据流的处理需求日益增大.其中,一个基本需求是基于距离度量方法的子序列匹配.由于动态时间弯曲距离(dynamic time warping,DTW)具有较高的度量精度,将其应用于子序列匹配问题是非常有价值的.但是,DTW具有较高的计算复杂度,这极大地限制了它在数据流上的应用.针对该问题,设计了一种高效的基于DTW的数据流子序列匹配系统.首先对数据流进行高效的适应性分段,然后对每一子段进行切比雪夫因式分解.不同于在原始数据空间的DTW计算,系统将在低维的切比雪夫特征空间计算DTW距离,因此,系统具有较高的计算效率.另外,提出了一种高效的在线匹配算法,可实现DTW在数据流上的增量式计算,进一步提高了系统的执行效率.

基于分段距离和子序列匹配的飞机故障检测

针对飞机故障检测数据中重复率高数据量大,监测算法效率和准确率低的问题,本文在PAA压缩数据的基础上使用分段概率提取细分QAR数据,调整FP-Growth算法创建独具特色FP-Tree降低数据的重复度,提高数据的查询速度,提出了基于分段距离和子序列匹配算法,本文采用真实的飞机飞行QAR数据验证该算法的有效性和准确度。

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

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

用基于移动均值的索引实现时间序列相似查询

提出了基于移动均值的索引来解决子序列匹配中的“ε-查询”问题：提出并证明了基于移动均值的缩距定理和缩距比关系定理，后者具有很好的“裁减”能力，可以在相似查询时淘汰大部分不符合条件的候选时间序列，从而达到快速相似查找的目的引入了由Jagadish等人提出的BATON^＊-树，并在此基础上适当修改，建立了MABI索引，极大地加快了相似查询过程；最后，在一个股票交易数据集上进行了实验，证明了MABI索引的良好性能．

时间序列相似性度量的研究

数据流上渐进、实时地进行子序列匹配成为一个极具价值和挑战性的问题。文中对已有的主要度量函数Lp-norms、DTW、LCSS、EDR和ERP等进行了分析和对比,从理论上归纳出其特性,对ERP算法进行了改进,大量的模拟和真实数据实验表明:改进的ERP算法在解决此类问题上具有高效性。

基于导数序列的时间序列同构关系发现

时间序列子序列匹配作为时间序列检索、聚类、分类、异常监测等挖掘任务的基础被广泛研究。但传统的时间序列子序列匹配都是对精确相同或近似相同的模式进行匹配,为此定义了一种全新的具有相似发展趋势的序列模式——时间序列同构关系,经过数学推导给出了时间序列同构关系判定的法则,并基于此提出了同构关系时间序列片段发现的算法。该算法首先对原始时间序列进行预处理,然后分段拟合后对各时间序列分段进行同构关系判定。针对现实背景数据难以满足理论约束的问题,通过定义一个同构关系容忍度参数使实际时间序列数据的同构关系挖掘成为可能。实验结果表明,该算法能有效挖掘出满足同构关系的时间序列片段。

基于时间序列的音乐流行趋势预测研究

在大数据环境下,对音乐及听众的历史数据进行分析,可以实现对音乐流行趋势较为准确的预测。在STL、Holt-Winters分解模型的基础上,提出TSMP算法。该算法从长期趋势和周期两方面进行分析,对长期趋势编码和分类并基于类别最优值选择法对音乐流行趋势进行预测。基于TSMP算法,进而提出E-TSMP算法,该算法基于子序列模式匹配法及对近期发布新专辑的附加处理,实现更精准的预测。在清华大学和阿里云天池大数据竞赛平台承办的"2016中国高校计算机大赛——大数据挑战赛之阿里音乐流行趋势预测"比赛中,参赛团队凭借提出的E-TSMP算法对2016年9月~10月艺人的播放量实现了较好的预测,并在此次比赛中夺得亚军。

高维时序数据的相似搜索

作者提出了一种针对高维时序数据相似搜索,改进了以前时序数据中的相似搜索只适应于低维的算法。这种方法是基于二元匹配算法,可视为二元匹配算法在高维时序数据的扩展。

基于语句特征的音乐哼唱快速检索技术

哼唱检索作为音乐检索的重要方式,由于其有效性和方便性,引起了广泛的关注.本文提出了一种新的基于语句特征的音乐哼唱快速检索技术,可以实现哼唱音乐的快速检索.该技术将音乐数据库和用户提供的哼唱片段,按自然停顿方式划分音乐语句,使用BDTW算法对音乐语句片段进行音高相似性计算,并允许用户根据自己哼唱情况,对匹配条件进行个性化设置,限制数据库音乐片段和查询序列的局部最大差异长度.另外,对音乐库建立支持音乐语句查询的索引结构DIS,减少了检索时间.实验结果表明所提出的检索方法能够快速有效地返回查询结果.

基于最小首差循环链码的快速搜索算法

分析了常用的时间序列相似性搜索的一般方法，提出了基于最小首差循环链码的快速搜索算法。其基本思想是对股票数据进行合理的符号化，并对符号化后的数据求最小首差循环链码，有效的解决了因时间轴上的平移、伸缩、旋转等对相似性判断的影响，遇到相似序列后跳到该相似序列的下一个位置继续搜索，大大提高了相似性搜索的效率和准确率．并给出了理论分析和验证结果。