不等长子时间序列的相似性度量方法

为了有效计算同一时间序列中具有不同长度的子序列数据的相似度,深入研究了时间序列中有关相似度计算的内容,提出了不等长子时间序列的相似性度量方法。该方法在分段计算每一相对独立子序列斜率的基础之上,能够有效地获得每一段的变化趋势,进而可以不受时间序列长度的影响而完成相似度计算。该方法在不同的数据集上进行实验,都获得了良好的效果,验证了该方法具有快速、准确、不受时间序列长度影响的特点。     

采用分段特征表示的异常序列检测算法

时间序列的有监督异常检测方法通常依赖于数据的标签，不仅会消耗大量时间进行数据标注，而且难以适用于无法给定标签的数据集。为解决异常序列检测中的标注问题，提出一种采用分段特征表示的异常序列检测方法。该方法采用分段聚合思想对时间序列进行标准化计算，并得到时序数据的特征表示，可提高无标签时间序列异常检测的可靠性。将表示后的特征划分为异常序列相关特征和无关特征，剪枝异常序列无关特征，可减少这些特征对检测结果的不利影响。为有效量化不同序列之间的差异性，提出一种面向时间权重分析的时间序列相似性度量方法，并构建时间序列的相似度矩阵，用于计算序列之间的相似度，可适用于无标签的时间序列中。在此基础上，根据相似度矩阵来计算每个子序列的异常分数，将其用于异常子序列的判定。通过合成数据集和真实数据集的实验对比表明：该方法节省了计算开销，提高了算法运行的时间效率和异常序列检测的准确率。     

基于形态模式的时间序列相似性度量算法

时间序列的特征表示与相似性度量是时间序列数据挖掘的重要基础。针对现有的序列表示方法难以具体反映序列的形态变化趋势,导致相似度量结果不精确的问题,提出一种新的基于形态模式的相似性度量算法。该算法在分段线性表示的基础上,根据序列在不同时段的斜率变化情况,划分序列的分段形态模式并用特殊的字符进行表示,把时间序列转换成字符串序列,利用最长公共子序列方法计算字符串序列的距离作为时间序列之间的距离。最后通过实验验证该方法的有效性。理论分析和实验证明该方法对数据点的值不敏感,能够减少噪声的干扰,而且具有较高的准确性。     

基于线性形态的时间序列异常模式挖掘

对于子序列长度相等的时间序列数据，文章提出了一种基于序列偏离度的异常模式发现方法。与传统的基于某一特定模型的方法不同，该方法首先对子序列进行线性分段，对每一分段计算其斜率，并将斜率进行离散化，离散化后的符号构成的特征序列就代表了原时间子序列的变化趋势，在此基础上，序列偏离度被定义和计算。这种方法不需预先定义模型，同时避免了通过序列间的两两比较来查找异常所带来的时间消耗。     

事件预测的时间序列数据挖掘方法

研究了应用数据挖掘技术预测时间序列数据中事件的方法。针对时间序列数据提出了显著特征提取算法，给出了特征间的相似度量标准，并应用特征聚类算法，将时间序列数据转换成相应的特征序列表示。应用频繁模式发现算法和预测模式生成算法在预测时段内发现与目标事件相关的时序特征模式，预测事件的发生。实验结果表明，该文所提出的方法能够有效地预测时间序列数据中的事件。     

一种新的基于相似度过滤的大数据保序匹配与检索算法

伴随大数据时代的到来,数据快速保序匹配与检索成为众多大数据应用急需解决的关键问题,通过抽象与归约等措施,数据对象可抽象为具有若干属性的点集或序列,从而将数据匹配问题转化为字符或数字序列匹配问题。提出一种基于相似度过滤的数据保序匹配与检索算法,算法分三步:(1)数据转换,基于幅值变化趋势将原始序列转换为二进制,对序列中任何一个字符,通过判断包括其前后邻居在内的三个点的关系定义二进制序列,准确反映相邻三点之间的凸增长(降低)或凹增长(降低)关系;(2)数据归约,为方便候选序列与模式序列之间的相似度计算,运用基于幅度变化比例的数据归约方法,将候选序列与模式序列均归约到固定区间;(3)相似度计算,为区分不同趋势的凸增长(降低)或凹增长(降低)幅度,通过计算候选序列与模式序列对应点之间的差值绝对值之和作为相似度判断依据,提出基于相似度过滤的快速匹配方法,寻找与模式序列变化趋势一致的子序列集合,并按照相似度大小排序。理论分析与实验结果表明:(1)该算法具有亚线性时间复杂度;(2)该算法能有效解决Chhabra等人算法对数据震荡幅度失控的问题,同时解决数据序列与模式序列分段规律但整体不相似的问题;(3)解决了Chhabra等人算法中对匹配序列排序造成的匹配结果疏漏问题。该方法不仅能更准确、更多地匹配出变化趋势一致的子字符串,同时将多个候选子串根据与模式之间的相似度进行排序,为进一步的数据精确检索提供判断依据。     

基于连续密度隐马尔可夫的时间序列分类算法

针对数据挖掘过程中对异常数据检测的准确率较低、分类速度较慢,导致数据分类准确率较低、效率较差的问题,提出基于连续密度隐马尔可夫的时间序列分类算法。构建时间序列变化趋势分割点目标函数,利用贪婪搜索法求解时间序列分段值,提取序列变化趋势特征得到数据主要信息,提升数据分类的准确性;改进帧内特征表达准确性,使用因子分析矩阵高斯分布建立连续密度隐马尔可夫模型,提高时间序列分类速度;采用平稳子空间分析法把数据划分为平稳子空间和非平稳子空间,运用相对熵权衡平稳子空间分布相似度,实现时间序列精准分类。仿真结果表明,所提方法分类正确率较高、计算速度快且鲁棒性好,可以满足真实场景下数据分析需求。     

基于J2EE平台应用时序挖掘算法对纺织品出口风险预测的研究

贸易数据是按时间记录下的、不断更新中的海量数据。首先引入时间序列模式的概念,分析了时间序列的本质问题;其次改进了AprioriAll算法挖掘贸易序列数据库的有用序列模式;然后使用离散傅里叶变换子序列相似性查找的方法,将现有序列与挖掘到的感兴趣的序列模式进行子序列匹配,得到有用的知识;最后结合实际情况,合理搭建系统平台,将改进的算法应用在该平台之下得到满意的效果。     

多维序列模式挖掘算法

提出一种基于最大频繁模式、模式相似与属性描述相结合的多维序列模式挖掘算法MSP,该算法包括3个步骤:挖掘数据集中的最大频繁模式,每个频繁模式成为一个模式类;比较数据中各序列项序列与各模式类的包含与相似关系;按照一定的规则抽取与各模式类相关的属性,给出以属性为前件、模式类为后件的多维序列规则为形式的多维序列模式挖掘结果....     

基于深度表示模型的移动模式挖掘

针对时空轨迹中位置顺序和时间对于理解用户移动模式的重要性,提出了一种新的用户轨迹深度表示模型。该模型考虑到时空轨迹的特点:1)不同的位置顺序表示不同的移动模式;2)轨迹有周期性并且在不同的时间段有变化。首先,将两个连续的位置点组合成位置序列;然后,将位置序列和对应的时间块组合成时间位置序列,作为描述轨迹特征的基本单位;最后,利用深度表示模型为每个序列训练特征向量。为了验证深度表示模型的有效性,设计实验将时间位置序列向量应用到用户移动模式发现中,并利用Gowalla签到数据集进行了实验评测。实验结果显示提出的模型能够发现"上班""购物"等明确的模式,而Word2Vec很难发现有意义的移动模式。     

基于形态特征的时间序列相似性搜索算法

时间序列相似性搜索是数据挖掘的一个重要基础性研究内容,它的相似性定义主要是基于欧氏距离,这类算法的缺点:如果时间序列产生偏移,会产生错误的结果.基于形态特征的时间序列相似性快速搜索算法,以界标为分界点,利用界标提取了时间序列的特征,将时序分为若干子序列,并对每个子序列进行线性化,将线性化后的子序列进行预处理;同样将查询序列进行基于界标的分段算法,然后利用一种改进的快速相似性搜索算法,可以快速地搜索到与查询序列相似的序列.?＃ 箅例表明了算法的有效性.     

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

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

基于YOLOv3和EPnP算法的多药盒姿态估计

针对机械臂药盒抓取操作中对药盒定位和姿态估计的要求,提出一种基于YOLOv3深度学习算法和EPnP算法相结合的多药盒姿态估计方法,此方法主要分为多药盒定位和姿态估计两部分;首先通过YOLOv3算法实现药盒的快速精确定位,并通过定位框分割出单个药盒;然后进行特征提取和特征匹配并估计单应矩阵;通过单应矩阵的透视矩阵变换求得药盒平面4个角点的像素坐标并作为EPnP求解所需的2D点,结合药盒先验尺寸信息在相机坐标系下构建药盒对应的3D点坐标以实现药盒姿态求解;通过结合OptiTrack系统设计了药盒姿态精度对比实验,结果表明,该算法充分发挥了YOLOv3算法兼具快速性和准确性的优势,并且具有良好的姿态估计精度,总体算法速度达到15 FPS,药盒姿态估计平均误差小于0.5°。     

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

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

改进的非极大值抑制算法的目标检测

目的 作为目标检测的后置处理算法,非极大值抑制（NMS）算法被用于移除多余的检测框。然而,NMS算法在每轮迭代中抑制所有与预选取检测框Intersection-over-Union（IoU）值大于给定阈值的检测框,容易造成目标的漏检和误检。此外,阈值的选取对整个算法的效果有着至关重要的影响。针对这个问题,本文提出了改进的NMS算法,分别为分段比例惩罚因子NMS算法和连续比例惩罚因子NMS算法。在连续比例惩罚因子NMS算法中,阈值对算法的运行效果仅有轻微的影响。方法 改进的NMS算法首先根据检测框与预选取检测框的IoU值大小计算出检测框对应的比例惩罚因子;然后将检测框置信度分数乘以比例惩罚因子,通过比例惩罚因子逐轮降低检测框的分数;最后经过多轮迭代后移除分数低于阈值的检测框。结果 基于分段比例惩罚因子NMS算法和连续比例惩罚因子NMS算法的Faster RCNN目标检测模型在PASCAL VOC 2007数据集下,Faster RCNN的检测平均精度均值（mAP）相较于传统的NMS算法分别提高了1.5%和1.6%。其中,以火车类为例,当准确率和召回率均为80%时,火车类检测的漏检率和误检率分别降低了1.8%和1.2%。与传统的NMS算法相比,本文所提出改进的NMS算法可以有效地保留目标检测框和移除目标的假正例检测框,从而降低NMS算法的漏检率和误检率。结论 在时间复杂度相同和运行效率一致的情况下,与传统的NMS算法相比,本文所提出的改进NMS算法mAP值得到了显著的提升,同时本文算法为其他目标检测模型提供了一个通用的解决方法。     

Partitioning a sequence into few monotone subsequences

In this paper we consider the problem of finding sets of long disjoint monotone subsequences of a sequence of numbers. We give an algorithm that, after preprocessing time, finds and deletes an increasing subsequence of size (if it exists) in time . Using this algorithm, it is possible to partition a sequence of numbers into monotone subsequences in time . Our algorithm yields improvements for two applications: The first is constructing good splitters for a set of lines in the plane. Good splitters are useful for two dimensional simplex range searching. The second application is in VLSI, where we seek a partitioning of a given graph into subsets, commonly refered to as the pages of a book, where all the vertices can be placed on the spine of the book, and each subgraph is planar. Received: 23 July 1990 / 19 June 1997     

HierarchyScan: A Hierarchical Algorithm for Similarity Search in Databases Consisting of Long Sequences

In this paper, a hierarchical algorithm, HierarchyScan, is proposed to efficiently locate one-dimensional subsequences within a collection of sequences with arbitrary length. The proposed algorithm performs correlation between the stored sequences and the template pattern in the transformed domain to identify subsequences in a scale- and phase-independent fashion. This is in contrast to those approaches based on the computation of Euclidean distance in the transformed domain. In the proposed hierarchical algorithm, the transformed domain representation of each original sequence is divided into multiple groups of coefficients. The matching is performed hierarchically from the group with the greatest filtering capability to the group with the lowest filtering capability. Only those subsequences whose maximum correlation value is higher than a predefined threshold will be selected for additional screening. This approach is compared to the sequential scanning and an order-of-magnitude speedup is observed.     

Exemplar learning for extremely efficient anomaly detection in real-valued time series

We investigate algorithms for efficiently detecting anomalies in real-valued one-dimensional time series. Past work has shown that a simple brute force algorithm that uses as an anomaly score the Euclidean distance between nearest neighbors of subsequences from a testing time series and a training time series is one of the most effective anomaly detectors. We investigate a very efficient implementation of this method and show that it is still too slow for most real world applications. Next, we present a new method based on summarizing the training time series with a small set of exemplars. The exemplars we use are feature vectors that capture both the high frequency and low frequency information in sets of similar subsequences of the time series. We show that this exemplar-based method is both much faster than the efficient brute force method as well as a prediction-based method and also handles a wider range of anomalies. We compare our algorithm across a large variety of publicly available time series and encourage others to do the same. Our exemplar-based algorithm is able to process time series in minutes that would take other methods days to process.     

时间序列对称模式挖掘

随着信息化和工业化的融合,物联网和工业互联网蓬勃发展,由此产生了以时间序列为代表的大量工业大数据.时间序列中蕴含着很多有价值的模式,其中,对称模式在各类时间序列中广泛存在.挖掘对称模式对于行为分析、轨迹跟踪、异常检测等领域具有重要的研究价值,但时间序列的数据量往往高达几十甚至上百GB.使用直接的嵌套查询算法挖掘对称模式可能花费数月乃至数年的时间,而索引、下界和三角不等式等典型加速技术最多只能产生一两个数量级的加速.因此,基于动态时间规整算法的启发,提出了一种能够在O(w×|T|)的时间复杂度内挖掘出时间序列所有对称模式的方法.具体来说,给定对称模式长度约束,基于区间动态规划算法计算出对称子序列,进而依据贪心策略选择数量最多且不重叠的对称模式.此外,还研究了在时间序列数据流挖掘对称模式的算法,并根据窗口内数据的特征动态调节窗口大小,保证了对称模式数据的完整性.采用1个人工数据集、3个真实数据集在不同数据量下对上述方法进行实验.由实验结果可知,与其他对称模式挖掘方法相比,该方法在模式挖掘结果及时间开销方面均有较好的表现.     

CONTOUR: an efficient algorithm for discovering discriminating subsequences

In recent years we have witnessed several applications of frequent sequence mining, such as feature selection for protein sequence classification and mining block correlations in storage systems. In typical applications such as clustering, it is not the complete set but only a subset of discriminating frequent subsequences which is of interest. One approach to discovering the subset of useful frequent subsequences is to apply any existing frequent sequence mining algorithm to find the complete set of frequent subsequences. Then, a subset of interesting subsequences can be further identified. Unfortunately, it is very time consuming to mine the complete set of frequent subsequences for large sequence databases. In this paper, we propose a new algorithm, CONTOUR, which efficiently mines a subset of high-quality subsequences directly in order to cluster the input sequences. We mainly focus on how to design some effective search space pruning methods to accelerate the mining process and discuss how to construct an accurate clustering algorithm based on the result of CONTOUR. We conducted an extensive performance study to evaluate the efficiency and scalability of CONTOUR, and the accuracy of the frequent subsequence-based clustering algorithm.