基于逻辑 shapelets 转换的时间序列分类算法

时间序列 shapelets 是序列之中最具有辨别性的子序列。解决时间序列分类问题的有效途径之一是通过shapelets 转换技术,将其发现与分类器的构建相分离,其主要优点是优化了 shapelets 的选择过程并能够灵活应用不同的分类策略。但此方法也存在不足,仅仅简单地应用这些 shapelets 而忽略它们之间的逻辑组合关系,有可能降低分类的效果;另外,离线式的发现 shapelets 的过程是相当耗时的。文中针对后一个问题,采用了一种基于智能缓存的计算重用技术,将发现 shapelets 的时间复杂度降低了一个数量级。在此基础上,作者提出了一种基于合取或析取的逻辑 shapelets 转换方法,并通过在多个经典的基准数据集上测试,表明了该方法能够在提升分类准确性的同时保持 shapelets 所具有的解释力。     

一种使用shapelets的增量式时间序列分类

根据时间序列数据维度高、实值有序、数据间存在自相关性等特点,对时间序列分类过程进行研究。研究了当前比较流行的时间序列分类方法;从图像处理的角度出发,提出了一种将图片信息转化为时间序列数据的ITTS方法。shapelets作为最能够表示一条时间序列的子序列,随着时间的推移,这个特征序列可能会动态地发生变化。基于这样的思想,提出了一种基于动态发现shapelets的增量式时间序列分类算法IPST。该算法能够较好地动态发现当前最优的k个shapelets,从而提高时间序列分类的准确度。 得到 的shapelets集合还可以与多个传统的分类器结合,从而获得更佳的分类效果。     

基于LSH的shapelets转换方法

针对基于shapelets转换的时间序列分类算法因shapelets候选集中存在大量相似序列而造成耗时过长的问题,提出了一种基于LSH的shapelets转换方法（Locality Sensitive Hashing Shapelets Transform,LSHST）,提出一种局部敏感哈希函数（LSH）的改进算法,对原始子序列候选集进行逐级过滤筛选,快速挑选出形态上具有代表性的shapelets集合,计算集合中shapelets的质量,采用覆盖的方法确定将要进行转换的shapelets,进一步减小shapelets的数量,进行shapelets转换。实验表明,与Shapelet Transform（ST）、ClusterShapelets（CST）和Fast Shapelet Selection（FSS）算法相比,LSHST在分类精度上最高提升了20.05、19.9和16.52个百分点,在时间节省程度上最高达8 000倍、16 000倍和8.5倍。     

基于多样化top-k shapelets转换的时间序列分类方法

针对基于shapelets转换的时间序列分类方法中候选shapelets存在较大相似性的问题，提出一种基于多样化top-k shapelets转换的分类方法DivTopKShapelet。该方法采用多样化top-k查询技术，去除相似shapelets，并筛选出最具代表性的k个shapelets集合，最后以最优shapelets集合为特征对数据集进行转换，达到提高分类准确率及时间效率的目的。实验结果表明，DivTopKShapelet分类方法不仅比传统分类方法具有更高的准确率，而且与使用聚类筛选的方法（ClusterShapelet）和shapelets覆盖的方法（ShapeletSelection）相比，分类准确率最多提高了48.43%和32.61%；同时在所有15个数据集上均有计算效率的提升，最少加速了1.09倍，最高可达到287.8倍。     

基于shapelets学习的多元时间序列分类

多元时间序列广泛存在于日常生活中的各个领域,多元时间序列分类是从时间序列数据中获取信息的基本方法。目前,时间序列分类研究面临着相似性度量方法特殊、原始数据维度高等问题,现有的多元时间序列分类方法的分类性能仍有待提高。文中提出一种基于shapelets学习的多元时间序列分类方法。首先,提出了新的正则化最小二乘损失学习框架下的shapelets学习方法,在此基础上采用基于shapelets的一元时间序列分类方法对多元时间序列的每维一元数据进行分类,随后由各维上的分类结果投票决定多元时间序列的最终分类结果。实验证明,所提方法在多元时间序列分类问题中能够取得较高的分类精度。     

基于优化和两阶段筛选的时间序列Shapelets提取研究

与基于全局特征的时间序列分类方法相比,基于shapelets的分类方法在可解释性和分类速度方面更具优势。针对现有的优化模型学习到的shapelets判别力不足以及shapelets候选数量太多等问题,提出了基于优化和两阶段筛选的时间序列shapelets提取算法。首先对时间序列取样,结合极值点和序列趋势对取样的时间序列进行分组,根据分组结果对稀疏组Lasso正则器的每项赋予权重,并在加权稀疏组Lasso的每一组中都使用融合罚正则项来保证解的相邻位置平坦变化,将多项稀疏正则项作为正则器与局部线性判别分析相结合来构建目标函数。然后,建立一个两阶段的筛选框架来度量组的稀疏性,从而快速地找到对分类起决定性作用的关键组。最后仅使用一组关键组来提取shapelets用于时间序列的分类,缩小了shapelets的规模。在28个时间序列数据集上进行了大量实验,实验结果表明,与现有的基于shapelets的提取方法相比,所提方法不仅能显著提高分类精度,具有较高的时间效率,而且能够在一定程度上缩小shapelets的规模。     

基于趋势特征表示的shapelet分类方法

Shapelet是一种具有辨识性的时间序列子序列，通过识别局部特征达到对时间序列准确分类的目的。原始shapelet发现算法效率较低，大量工作关注于提高shapelet发现的效率。然而，对于带有趋势变化的时间序列，采用典型的时间序列表示方法进行shapelet发现，容易造成序列中趋势信息的丢失。为了解决时间序列趋势信息丢失的问题，提出一种基于趋势特征的多样化top-k shapelet分类方法：首先采用趋势特征符号化方法对时间序列的趋势信息进行表示；然后针对序列的趋势特征符号获取shapelet候选集合；最后通过引入多样化top-k查询算法从候选集中选取k个最具代表性的shapelets。在时间序列的分类实验中，与传统分类算法相比，所提方法在11个数据集上的分类准确率均有提升；与FastShapelet算法相比，提升了运行效率，缩短了算法的运行时间，并在趋势信息明显的数据上效果显著。结果表明，所提方法能有效提高时间序列的分类准确率，提升算法运行效率。     

基于非相似原理快速查找多个shapelets

shapelets是描述时间序列局部特征的子序列,它能最大程度对不同类别进行区分。从它的发明至今一直吸引着研究者的关注,但是由于过高的时间复杂度阻碍了它被广泛应用。一种快速查找多个shapelets的方法（Non-Similar Discover of Shapelet,NSDS）被提出：基于shapelets非相似的特性,根据子序列间距离分布设置一个距离阈值,以此过滤掉候选集中的相似子序列。再使用类可分离性作为过滤后的候选子序列的评价标准,最终选择出性能最好的多个shapelets。通过在单变量时间序列数据集上的实验表明了该方法可以极大缩短查找shapelets时间,而且能保持较高的分类准确性。将该方法扩展到多变量时间序列,对多个变量采用组合分类器的方法来提高整体分类的准确率。     

Multi-shapelet:一种基于shapelet的多变量时间序列分类方法

shapelet是时间序列中最具有辨识性的子序列,其一经提出就被来自各个领域的研究人员广泛研究,并在此过程中提出了许多有效的shapelet发现技术用于进行时间序列分类。然而,多变量时间序列的候选shapelet可能长度不同且变量来源不同,故很难直接对其进行比较,这对基于shapelet多变量时间序列分类方法提出了独特的挑战。为了应对这一挑战,提出了一种基于无监督表示学习和shapelet的多变量时间序列分类方法Multi-shapelet。Multi-shapelet首先使用混合模型DC-GNN（Dilated convolution neural network and graph neural network, DC-GNN）作为编码器,将不同长度的候选shapelet嵌入统一的shapelet选择空间,以进行shapelet之间的比较;其次,提出了一种新的损失函数以无监督学习方式训练该编码器,使得DC-GNN对shapelet编码得到相应的嵌入（Embedding）后,属于同类shapelet对应的嵌入之间的相对位置形成的拓扑与原空间中shapelet之间相对位置形成的拓扑之间的关系更接近于一种等比例的缩小,这对后续基于相似性的剪枝过程十分重要;最后,使用K-means聚类和模拟退火算法进行shapelet剪枝和选择操作。在UEA的18个多变量时间序列数据集上的实验结果表明,Multi-shapelet的整体精度相比于其他方法得到了显著提升。     

基于RELM的时间序列数据加权集成分类方法

时间序列数据通常是指一系列带有时间间隔的实值型数据,广泛存在于煤矿、金融和医疗等领域。为解决现有时间序列数据分类问题中存在的含有大量噪声、预测精度低和泛化性能差的问题,提出了一种基于正则化极限学习机(RELM)的时间序列数据加权集成分类方法。首先,针对时间序列数据中所含有的噪声,利用小波包变换方法对时间序列数据进行去噪处理。其次,针对时间序列数据分类方法预测精度低、泛化性能较差的问题,提出了一种基于RELM的加权集成分类方法。该方法通过训练正则化极限学习机(RELM)隐藏层节点数量的方法,有效选取RELM基分类器;通过粒子群优化(PSO)算法,对RELM基分类器的权值进行优化;实现对时间序列数据的加权集成分类。实验结果表明,该分类方法能够对时间序列数据进行有效分类,并提升了分类精度。     

融合选择提取与子类聚类的快速Shapelet发现算法

基于Shapelet的时间序列分类算法具有可解释性,且分类准确率高、分类速度快.在这些算法中,Shapelet学习算法不依赖于单一分类器,能够学习出不在原始时间序列中的Shapelet,可以取得较高的分类准确率,同时还可以保证Shapelet发现和分类器构建同时完成;但如果产生的Shapelet过多,会增加依赖参数,导致训练时间太长,分类速度低,动态更新困难,且相似重复的Shapelet会降低分类的可解释性.提出一种选择性提取方法,用于更精准地选择Shapelet候选集,并改变学习方法以加速Shapelet学习过程;方法中提出了两个优化策略,通过对原始训练集采用时间序列聚类,可以得到原始时间序列中没有的Shapelet,同时在选择性提取算法中加入投票机制,以解决产生Shapelet过多的问题.实验表明,该算法在保持较高准确率的同时,可以显著地提高训练速度.     

Classification of time series by shapelet transformation

Time-series classification (TSC) problems present a specific challenge for classification algorithms: how to measure similarity between series. A shapelet is a time-series subsequence that allows for TSC based on local, phase-independent similarity in shape. Shapelet-based classification uses the similarity between a shapelet and a series as a discriminatory feature. One benefit of the shapelet approach is that shapelets are comprehensible, and can offer insight into the problem domain. The original shapelet-based classifier embeds the shapelet-discovery algorithm in a decision tree, and uses information gain to assess the quality of candidates, finding a new shapelet at each node of the tree through an enumerative search. Subsequent research has focused mainly on techniques to speed up the search. We examine how best to use the shapelet primitive to construct classifiers. We propose a single-scan shapelet algorithm that finds the best $k$ shapelets, which are used to produce a transformed dataset, where each of the $k$ features represent the distance between a time series and a shapelet. The primary advantages over the embedded approach are that the transformed data can be used in conjunction with any classifier, and that there is no recursive search for shapelets. We demonstrate that the transformed data, in conjunction with more complex classifiers, gives greater accuracy than the embedded shapelet tree. We also evaluate three similarity measures that produce equivalent results to information gain in less time. Finally, we show that by conducting post-transform clustering of shapelets, we can enhance the interpretability of the transformed data. We conduct our experiments on 29 datasets: 17 from the UCR repository, and 12 we provide ourselves.     

Time series shapelets: a novel technique that allows accurate, interpretable and fast classification

Classification of time series has been attracting great interest over the past decade. While dozens of techniques have been introduced, recent empirical evidence has strongly suggested that the simple nearest neighbor algorithm is very difficult to beat for most time series problems, especially for large-scale datasets. While this may be considered good news, given the simplicity of implementing the nearest neighbor algorithm, there are some negative consequences of this. First, the nearest neighbor algorithm requires storing and searching the entire dataset, resulting in a high time and space complexity that limits its applicability, especially on resource-limited sensors. Second, beyond mere classification accuracy, we often wish to gain some insight into the data and to make the classification result more explainable, which global characteristics of the nearest neighbor cannot provide. In this work we introduce a new time series primitive, time series shapelets, which addresses these limitations. Informally, shapelets are time series subsequences which are in some sense maximally representative of a class. We can use the distance to the shapelet, rather than the distance to the nearest neighbor to classify objects. As we shall show with extensive empirical evaluations in diverse domains, classification algorithms based on the time series shapelet primitives can be interpretable, more accurate, and significantly faster than state-of-the-art classifiers.     

Generalized random shapelet forests

Shapelets are discriminative subsequences of time series, usually embedded in shapelet-based decision trees. The enumeration of time series shapelets is, however, computationally costly, which in addition to the inherent difficulty of the decision tree learning algorithm to effectively handle high-dimensional data, severely limits the applicability of shapelet-based decision tree learning from large (multivariate) time series databases. This paper introduces a novel tree-based ensemble method for univariate and multivariate time series classification using shapelets, called the generalized random shapelet forest algorithm. The algorithm generates a set of shapelet-based decision trees, where both the choice of instances used for building a tree and the choice of shapelets are randomized. For univariate time series, it is demonstrated through an extensive empirical investigation that the proposed algorithm yields predictive performance comparable to the current state-of-the-art and significantly outperforms several alternative algorithms, while being at least an order of magnitude faster. Similarly for multivariate time series, it is shown that the algorithm is significantly less computationally costly and more accurate than the current state-of-the-art.