TS-CHIEF:一种用于时间序列分类的可扩展的、精确的森林算法

题目：

TS-CHIEF: A Scalable and Accurate Forest Algorithm for Time Series Classification

作者：

Ahmed Shifaz, Charlotte Pelletier, Francois Petitjean, Geoffrey I. Webb

来源：

Machine Learning (cs.LG)

Submitted on 25 Jun 2019

文档链接：

arXiv:1906.10329

代码链接：

摘要

时间序列分类(TSC)在过去的二十年中取得了巨大的进步。HIVE-COTE(基于转换的集成的分级投票集体)是当前分类精度方面的最新技术。HIVE-COTE认识到时间序列是一种特殊的数据类型，传统的属性值表示方法(主要用于机器学习)无法提供相关的表示。HIVE-COTE组合了多种类型的分类器:每种分类器都提取关于时间序列的特定方面的信息，无论是在时域、频域还是在序列中的区间摘要中。然而，HIVE-COTE(以及它的前身FLAT-COTE)通常无法在少量数据上运行。例如，在只有1,500个时间序列的数据集上训练HIVE-COTE可能需要8天的CPU时间。它有多项式的运行时w.r。t训练集的大小，所以随着数据量的增加，这个问题会变得复杂。我们提出了一种新的TSC算法TS-CHIEF，它在精度上与HIVE-COTE有很强的竞争，但只需要运行时的一小部分。TS-CHIEF构建了一个集成分类器，该分类器集成了过去十年研究中最有效的时间序列嵌入。它使用树形结构的分类器来有效地做到这一点。我们对UCR归档的85个数据集进行了TS-CHIEF评估，在这些数据集中，TS-CHIEF以可伸缩性和效率达到了最先进的准确性。我们证明TS-CHIEF可以在2天内完成130k时间序列的训练，这一数据量是任何TSC算法都无法达到的，且精度相当。

英文原文

Time Series Classification (TSC) has seen enormous progress over the last two decades. HIVE-COTE (Hierarchical Vote Collective of Transformation-based Ensembles) is the current state of the art in terms of classification accuracy. HIVE-COTE recognizes that time series are a specific data type for which the traditional attribute-value representation, used predominantly in machine learning, fails to provide a relevant representation. HIVE-COTE combines multiple types of classifiers: each extracting information about a specific aspect of a time series, be it in the time domain, frequency domain or summarization of intervals within the series. However, HIVE-COTE (and its predecessor, FLAT-COTE) is often infeasible to run on even modest amounts of data. For instance, training HIVE-COTE on a dataset with only 1,500 time series can require 8 days of CPU time. It has polynomial runtime w.r.t training set size, so this problem compounds as data quantity increases. We propose a novel TSC algorithm, TS-CHIEF, which is highly competitive to HIVE-COTE in accuracy, but requires only a fraction of the runtime. TS-CHIEF constructs an ensemble classifier that integrates the most effective embeddings of time series that research has developed in the last decade. It uses tree-structured classifiers to do so efficiently. We assess TS-CHIEF on 85 datasets of the UCR archive, where it achieves state-of-the-art accuracy with scalability and efficiency. We demonstrate that TS-CHIEF can be trained on 130k time series in 2 days, a data quantity that is beyond the reach of any TSC algorithm with comparable accuracy.

要点

图1:关键差分图，显示了基准UCR归档[9]的85个数据集中领先的TSC算法(在第2节中描述)的平均误差等级。排名越低(越靠右)，算法相对于其他算法的平均误差就越小。虽然我们的方法是可扩展的和有效的，但我们的方法TS-CHIEF在精度上比当前最先进的方法HIVE-COTE稍好一些。

图2:使用卫星图像时间序列数据集[45]，随着训练规模的增加，TS-CHIEF与HIVE-COTE的对数尺度训练时间。即使是1500个时间序列，TS-CHIEF也比当前最先进的HIVE-COTE要快900多倍。参数k表示TS-CHIEF林中使用的树的数量。参数的选择将在第4节中讨论。

图3:在85个UCR数据集上，TS-CHIEF与扁平cote(红色圆圈)和蜂巢cote(蓝色矩形)的准确性比较。

图4:sit数据集训练集大小的精度函数。

图5:一个UCR数据集的训练时间作为序列长度'的函数。

图6:删除一种或两种分裂函数与TS-CHIEF(使用所有三种分裂函数)的精度两两比较，以确定每种分裂函数对总体精度的贡献。

图7:临界差分图，显示了每种分裂函数的贡献。

本文介绍了TS-CHIEF算法，它是一种可扩展的、高精度的TSC算法。我们已经证明TS-CHIEF充分利用了树的准线性可伸缩性，以及过去十年来对精确表示时间序列的研究。我们对85个数据集进行的实验表明，我们的算法达到了与HIVE-COTE算法相媲美的最先进的精度，HIVE-COTE算法由于其计算复杂性，不能在许多应用中使用。我们证明，在土地覆盖制图的应用中，TS-CHIEF能够在2天内从13万个时间序列中学习一个模型，而HIVE-COTE只需要8天就能从1500个时间序列中学习大量数据，TS-CHIEF只需13分钟。TS-CHIEF提供了时间序列分类的一般框架。我们相信，研究人员将会发现，整合新的转换和相似性度量并将其大规模应用是很容易的。