基于Shapelet剪枝和覆盖的时间序列分类算法

时间序列shapelets是时间序列中能够最大限度地表示一个类别的子序列.解决时间序列分类问题的有效途径之一是通过shapelets转换技术,将shapelets的发现与分类器的构建相分离,其主要优点是优化了shapelets的选择过程,并能够灵活应用不同的分类策略.但该方法也存在不足:一是在shapelets转换时,用于产生最好分类结果的shapelets数量是很难确定的;二是被选择的shapelets之间往往存在着较大的相似性.针对这两个问题,首先提出了一种简单有效的shapelet剪枝技术,用于过滤掉相似的shapelets;其次,提出了一种基于shapelets覆盖的方法来确定用于数据转换的shapelets的数量.通过在多个数据集上的测试实验,表明了所提出的算法具有更高的分类准确率.     

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

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

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

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

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

与基于全局特征的时间序列分类方法相比,基于shapelets的分类方法在可解释性和分类速度方面更具优势。针对现有的优化模型学习到的shapelets判别力不足以及shapelets候选数量太多等问题,提出了基于优化和两阶段筛选的时间序列shapelets提取算法。首先对时间序列取样,结合极值点和序列趋势对取样的时间序列进行分组,根据分组结果对稀疏组Lasso正则器的每项赋予权重,并在加权稀疏组Lasso的每一组中都使用融合罚正则项来保证解的相邻位置平坦变化,将多项稀疏正则项作为正则器与局部线性判别分析相结合来构建目标函数。然后,建立一个两阶段的筛选框架来度量组的稀疏性,从而快速地找到对分类起决定性作用的关键组。最后仅使用一组关键组来提取shapelets用于时间序列的分类,缩小了shapelets的规模。在28个时间序列数据集上进行了大量实验,实验结果表明,与现有的基于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的方法（Non-Similar Discover of Shapelet,NSDS）被提出：基于shapelets非相似的特性,根据子序列间距离分布设置一个距离阈值,以此过滤掉候选集中的相似子序列。再使用类可分离性作为过滤后的候选子序列的评价标准,最终选择出性能最好的多个shapelets。通过在单变量时间序列数据集上的实验表明了该方法可以极大缩短查找shapelets时间,而且能保持较高的分类准确性。将该方法扩展到多变量时间序列,对多个变量采用组合分类器的方法来提高整体分类的准确率。     

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

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

一种基于DTW的新型故事时间序列相似性度量方法

现有时间序列相似性度量方法在进行股市序列相似性分析时,通常忽略成交量等其他重要因素对股价的影响,从而导致序列聚类、分类不精确。针对这一问题,本文提出了新的股市时间序列相似性度量方法。该方法在动态时间弯曲算法的基础上,通过引进时间衰竭因子,并结合成交量因素,给出了股市序列的最终度量公式。为了证明提出方法的可行性和有效性,本文实验部分通过选取家电等三个行业中的股票数据进行测试。实验结果表明,基于动态时间弯曲(Dynamic time warping,DTW)的新型股市时间序列相似性度量方法能够在保持股票序列形态特征的基础上,较好地解决股市技术分析中量价关系问题,从而更有效地应用于股市技术分析里关于模式发现等领域。     

管道流量泄漏时间序列分类的算法研究

时间序列分类比一般分类问题困难,主要在于要分类的时间序列数据不等长,因此不能直接应用一般的分类算法。首先提出基于聚类模型的数据转换,然后进行基于模型的聚类分析,用领域相关法对时间序列建模,用模型参数组成等长向量来表示每条序列,最后进行时间序列匹配算法分析,用分类算法进行训练和分类。结合管道流量泄漏点提出一种时间序列匹配的新方法,利用同类样本间的连续性规律,将时间序列排序,并在相邻的时间序列之间添加样本点,新方法优于基于动态时间弯折的传统方法;针对管道流量泄漏时间序列分类的算法研究观测到不同算法在不同因素影响下的性能表现,为今后发展新的算法提供有力依据。     

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.     

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.     

融合选择提取与子类聚类的快速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.