时间序列子序列搜索库 TSQLite

（y：=：=软件X 18（2022）101049原始软件出版物时间序列子序列搜索库Duarte Folgadoa，b，Pados，1，Marília Barandasa，b，1，Margarida Antunesa，Maria Lua Nunesa，Hui Liuc，Yale Hartmannc，Tanja Schultzc，Hugo Gamboaa，baAssociação Fraunhofer Portugal Research，Rua Alfredo Allen 455/461，波尔图，葡萄牙bLIBPhys（仪器、生物医学工程和辐射物理实验室），NOVA科学技术学院（Campus de Caparica），2829-516 Caparica，葡萄牙c德国不来梅大学认知系统实验室ar t i cl e i nf o文章历史记录：2021年10月30日收到收到修订版，2022年3月11日接受，2022年保留字：时间序列后续搜索距离基于查询的搜索分割Python包a b st ra ct子序列搜索和距离测度是时间序列数据挖掘中的重要工具。本文介绍了我们的Python包名为TSQLite，它提供了一套全面的方法，时间序列中的子序列搜索和相似性度量。这些方法是用户可定制的，以获得更大的灵活性和更有效的集成到实际部署场景中。TSVT2000能够快速探索时间序列数据分析，并在人类活动识别和室内定位的背景下进行了验证。版权所有©2022作者。由爱思唯尔公司出版这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）中找到。代码元数据当前代码版本v0.1.1指向此代码版本所用代码/存储库的永久链接https://github.com/ElsevierSoftwareX/SOFTX-D-21-00210Code Ocean compute capsule n/a法律代码许可证BSD 3条款许可证使用Git的代码版本控制系统使用Python的软件代码语言、工具和服务编译要求、操作环境依赖性NumPy、Scipy、Matplotlib和Numba（如果可用）开发人员文档/手册https://tssearch.readthedocs.io问题支持电子邮件info@fraunhofer.pt软件元数据1. 动机和意义时间序列数据挖掘算法使用子序列搜索作为子程序。子序列搜索是一种有用的探索性工具，已用于许多领域，如音乐信息检索[1]，步态分析[2]和室内定位[3]，以找到数据中的常见模式和行为。定义两个时间序列Q（q1，q2，. . .，q N）和Y1，y2，. . . ，y M）的长度分别为N和M。该子序列通讯作者：Associação Fraunhofer Portugal Research，Rua Alfredo Allen455/461，Porto，Portugal.电子邮件地址：duarte. fraunhofer.pt（Duarte Folgado）.1作者贡献相等https://doi.org/10.1016/j.softx.2022.101049时间序列上的搜索问题可以形式上定义为给定查询Q和较长的目标时间序列Y，找到Y的最佳连续性，从Yi开始，最小化与Q的相似性测量，其中i是每个子序列的初始时刻[4]。在本文中，我们介绍了一个名为TSQLite的Python包，它提供了基于查询的子序列搜索时间序列，以及常用的距离测量的实现。TSQLite支持单变量和多变量时间序列，并编写为易于由社区通过附加时间序列距离或后续搜索方法进行扩展。在文献中，有相关的软件包可用于时间序列的基距离测量，例如TSDist[5]2352-7110/©2022作者。 由Elsevier B.V.出版。这是一篇开放获取的文章，使用CC BY许可证（http://creativecommons.org/licenses/by/4.0/）。可在ScienceDirect上获得目录列表SoftwareX期刊主页：www.elsevier.com/locate/softxDuarte Folgado，Marília Barandas，Margarida Antunes等人软件X 18（2022）1010492和dtaidistance[6]。其他补充包，如pyts[7]和sktime[8]，专注于与搜索问题不同的监督学习另一个例子是tslearn[9]，一个通用机器学习库，支持完整开发管道的工具。但是没有一 上面列出的软件包集中于解决子序列搜索的问题。这个问题在UCR套件[10]中得到了解决，它可以在广泛的数据集上进行优化的子序列搜索。然而，它的软件实现并不容易扩展.与这些软件包相比，TSSoft主要关注子序列搜索问题，并执行具有附加功能的高度可定制的基于查询的搜索。TSAND目前被用于在人类活动识别的背景下分割重复运动[11]，并在室内定位中找到类似的位置模式[3]。在本文的其余部分，我们提出了一个概述的实现架构和功能，说明性的例子，基本的用法，以及影响和贡献，激发未来的研究主题。2. 软件描述2.1. 软件构架TSVs是Python 3的跨平台包 它依赖于Numpy [12]和SciPy[13]，它们为多维数据提供了有效的数值例程。它还依赖于Numba [14]进行有效的计算和Matplotlib [15]进行可视化。为了在时间序列之间执行相似性搜索，需要测量距离。将一个时间序列的第i个点与另一个时间序列的第i个点进行比较的距离度量被表示为锁步度量（例如，Euclideandistance和其他Lp范数）。允许一对多点比较的距离DTW和最长公共子序列（LCSS））表示为弹性测度[16]。多年来，已经提出了许多形式的时间序列查询。对于非重复性数据，查询搜索查找在较长信号上出现的查询.对于重复数据，我们将把轻微的变化称为分割，其目标是识别连续重复之间的图1、总结了TSVO处理流水线。数据由通过形状（T， D）的Numpy数组表示的时间序列组成，其中T是它们的长度，D是它们的维度。 对于多变量时间序列，查询和序列必须相同。通常，长度 查询的长度比序列小得多。用户可以选择所需的搜索方法或距离，通过单独选择或基于距离类型的过滤。此搜索配置使用JSON格式的文件指定。清单1展示了一个包含部分配置文件的示例。语法包括距离名称、简短描述、方法名称、关联参数以及是否支持多变量输入。使用键定义用于搜索的距离。如果用户选择多个距离，则例程将针对每个距离单独运行输出包括一个de-搜索的跟踪报告。它通过呈现它们所处的时刻、最佳对齐路径（对于弹性度量的情况）以及到查询的该软件包分为三个主要的子模块：tssearch。距离包含相似性度量的实现; Tssearch。搜索包含用于查询搜索和分段的高级例程的实现;以及TSSearch。utils，其中包含一些实用程序以及支持输出报告的可视化方法。123456789101112131415161718192021222324清单1：实现了两个弹性距离的JSON配置文件示例。表1自版本v0.1.1起实现的距离概述锁步Lp距离Pearson相关距离短时间序列距离（STS）[17]弹性动态时间扭曲（DTW）最长公共子序列（LCSS）时间扭曲编辑距离（TWED）[18]时间时间校准测量（TAM）[19]2.2. 软件功能2.2.1. 时间序列距离表1中总结了TSSTOSv0.1.1中包含的实施时间序列距离。这些距离用于搜索例程。然而，如果用户只对使用任何这些距离测量时间序列之间的距离感兴趣，则可以使用time_series_distance方法来实现，该方法接收两个时间序列和声明将计算哪些距离的配置文件2.2.2. 搜索方法TSVN 用 两 种 方 法 解 决 时 间 序 列 搜 索 问 题tssearch.time_series_search方法基于距离测量在较长序列上定位给定查询的k默认情况下，k被设置为检索最大匹配数。用户还可 以 显 式 地 定 义 k 的 值 来 检 索 k 个 最 佳 出 现 。tssearch.time_series_segmentation用于定位时间点在较长的重复序列上的连续查询重复之间2.2.3. 查询样品重量在某些情况下，为查询的每个点分配权重以度量它们对总距离的相对贡献是很有帮助的这种功能的用例的一个例子是找到一个查询，其中我们对某些区间的形状更不确定，因此分配了较低的权重。{“elastic“：{“DynamicTimeWarping“：{“多个“：“是“，“描述“：“”，“function“：“dtw“，“parameters“：{“dtw_type“：“dtw“，“alpha“：1}的情况下，“use“：“yes“}的情况下，“LongestCommonSubsequencence“：{“multivariate“：“是“，“description“：“”，“function“：“lcss“，“parameters“：{“eps“：1，“报告“：“距离“}的情况下，“use“：“yes“}}}Duarte Folgado，Marília Barandas，Margarida Antunes等人软件X 18（2022）1010493Fig. 1. 软件搜索在S1和S2序列中出现的查询Q。用户可以通过定义将使用哪些弹性或锁定步长距离来自定义搜索。输出包括呈现查询被发现的时刻、最优对齐路径（对于弹性度量的情况）、以及到查询的距离。在分割的情况下，假设进行搜索的时间序列是重复的，因此，目标是识别连续性之间的过渡时刻2.2.4. 可视化TSCOM实现了可视化方法来呈现分割和查询搜索的结果。可视化突出显示了匹配所处的时刻以及表示其到查询的距离值的颜色编码。2.2.5. 用户定制TSCDMA为用户提供了添加自定义距离的灵活性。用户可以编写自定义的距离方法，并提供文档，包括声明距离域，锁步或弹性。3. 说明性实例我们现在提供软件交互和功能的两个说明性示例。这些示例可以在Google Colab上找到，可以从包的GitHub存储库访问3.1. 分割心电图数据在本例中，我们使用了ECG记录中的10秒片段。录音中有几个心跳。为了简化示例，我们将查询定义为10 s记录期间存在的心跳之一。清单2给出了执行分段的示例代码。在第4行中，用户将DTW定义为分割的距离。在第6行中，计算分割并将输出分配给变量。该方法接收配置文件、查询和序列作为输入。在这种情况下，用户还指定了权重向量，该权重向量为第二局部最大值（T波）分配较少的贡献。123456清单2：基于查询的ECG分割的示例代码。输出可视化如图所示。2，并使用库中可用的可视化方法对于用户可能对进一步表征每个子序列感兴趣的场景，这可以使用为每个片段计算的距离值和/或使用TSFEL[20]或MVTS[21]来提取时间，统计和光谱特征作为分类算法的数据表示来完成。3.2. 基于步行数据的我们现在将描述来自基于可穿戴传感器的人类活动数据集的附加示例，以利用多维数据的示例来进一步说明TSSK在运动机能学内容上的适用性。CSL-SHARE数据集涵盖20名受试者的22项日常生活和运动活动，总时间为691分钟。它包含从各种类型的传感器记录的同步多通道生物信号，具有用于多维子序列搜索的相关上下文[11]。在该示例中，在受试者正在行走的试验中完成步幅分割对于该多变量查询搜索示例，考虑了两个时间序列-来自加速度计的加速度数据和来自附接到受试者膝盖的测角器的角度数据清单3给出了执行分段的示例代码在第7行和第8行中，用户使用附加参数α定义DTW，该参数α对幅度中的成本与其一阶导数之间的贡献进行加权。在第10行中，计算查询搜索，并将输出赋给一个变量。该方法接收配置文件、查询和序列作为输入。由于用户没有显式定义匹配数，因此它检索最大匹配数12345678910清单3：应用于步幅分割的查询搜索的说明性代码示例。importtssearchdata=tssearch. load_ecg_example（）cfg=tssearch。get_distance_dict（[“DynamicTimeWarping“]）outt=tssearch. 时间_序列_数据段时间（cfg，data[“query“]，data[“sequence“]，weight=data[“weight“]）importssearchimportnumpyasnpquery= np. loadtxt（“query.txt“）sequence= np。loadtxt（“sequence.txt“）cfg=tssearch。get_distance_dict（[“DynamicTimeWarping“]）cfg[“elastic“][“DynamicTimeWarping“][“parameters“][“alpha“]=0。5outt=tssearch. 时间_series_search（cfg，查询，Duarte Folgado，Marília Barandas，Margarida Antunes等人软件X 18（2022）1010494图二. 基于查询的ECG分割示例的结果。查询如左侧所示。查询由用户自定义，用户为分割分配了一个重要性相对较低的区域（蓝色）。右侧描绘了序列，垂直虚线表示计算的分割时刻。（关于此图例中颜色的参考解释，请读者参考本文的网络版本图三. 应用于步幅分割的多元查询搜索的结果。查询和序列由两个时间序列组成。查询描述在左边序列如右图所示距离度量查询和每个匹配之间的相似性使用的距离是DTW。输出可视化如图所示。3，并使用库中可用的可视化方法4. 影响子序列搜索是时间序列模式挖掘中最重要的子过程之一。后续搜索用于机器学习堆栈的不同阶段在初始阶段，子序列搜索可以分割感兴趣的窗口，使用特征提取方法进一步表征下游此外，测量查询和分段间隔之间的距离提供了定量数据，以执行下游数据挖掘任务，例如聚类或监督分类。具体的应用包括：金融、市场营销或股票价格时间序列，其中典型的查询是：哪些公司在给定的时间间隔内的股价与我们公司相似？我们过去是否有类似的情况，类似于我们产品上个月对由时间序列组成的科学数据集的典型查询是：过去哪些日子的地震活动与今天的模式相似给定查询定义的心跳不规则，患者在检查期间有多少次类似的心跳不规则？在步行运动中，健康受试者和神经系统疾病患者的步幅变化有多大TSTOM通过提供一组用于子序列搜索和相似性度量的方法来帮助时间序列数据科学家。这些方法之前在人类活动识别[11]和室内定位[3]的背景下进行了验证。TSSK也很容易扩展，使高级用户可以创建额外的搜索或距离测量方法，customized他们的需要。后续搜索实验的参数也记录在配置文件中，促进了研究人员之间的科学方法的开放性和可重复性。对于用户在子序列搜索后有兴趣进一步表征每个异常的场景，编写TSFEL与TSFEL[20]一起工作，TSFEL是一个专用于时间序列特征提取的Python软件包。对于这个用例，输出是一个标准化的文件格式，可以被Orange[22]、Weka[23]或scikit-learn[24].5. 结论我们已经开发了一个名为TSQLite的Python包，它提供了一套全面的方法，用于时间序列中的子序列搜索和相似性度量。TSSTOM包括单元测试和适当的代码文档。除了这些强烈导向的编码指南，这个项目还有三个主要的·····Duarte Folgado，Marília Barandas，Margarida Antunes等人软件X 18（2022）1010495贡献：（1）创建一个专用的Python包来解决单变量和多变量时间序列中的子序列搜索问题;（2）结合权重以定制给定查询间隔的重要性，以及（3）易于扩展的API以允许定制距离测量和搜索方法。TSCOM开放供投稿，并邀请用户使用新的子序列搜索方法和跨不同科学学科的相似性测量来扩展图书馆。TSTOS是开源的，可在GitHub上在线获得，有良好的文档记录，并不断维护。给出的实例表明，该方法是解决时间序列子序列搜索问题竞合利益作者声明，他们没有已知的竞争性财务利益或个人关系，可能会影响本文报告的工作致谢本文是ConnectedHealth（n. 葡萄牙竞争力和国际化行动计划（POCI）和里斯本区域行动计划（LISBOA 2020）的支持下，根据葡萄牙2020伙伴关系协议，通过欧洲区域发展基金（ERDF）。引用[1] 穆勒 河音乐处 理的基本 原理Cham ：Springer International Publishing;2015，http://dx.doi.org/10.1007/978-3-319-21945-5.[2] Barth J，Oberndorfer C，Pasluosta C，Schülein S，Gassner H，ReinfelderS，在自由行走运动期间使用惯性传感器数据上的多维子序列动态时间弯曲的步幅分割。传感器2015;15（3）：6419-40.http://dx.doi.org/10.3390/s150306419网站。[3] Santos R，Leonardo R，Barandas M，Moreira D，Rocha T，Alves P等，多层 建筑 室 内位 置 的基 于 众包 的 指纹 识 别。 IEEE Access 2021;9 ： 31143-60.http://dx.doi.org/10.1109/ACCESS的网站。2021.3060123。[4] [10]杨文，杨文，杨文.大规模时间序列数据库中快速相似性搜索的简化算法。KnowlInformSyst2001;3（3）：263-86.http://dx.doi.org/10.1007/PL00011669网站。[5] 放大图片作者：Mori U，Mendiburu A，Lozano J.R中时间序列的距离度量：tsdist包。R J 2016;8（2）：451.http://dx.doi.org/10.32614/RJ-2016-058网站。[6] Meert W，Hendrickx K，Craenendonck TV. Wannesm/dtaidistance v2.0.0。2020年，http://dx.doi.org/10.5281/ZENODO.3981067。[7] Faouzi J，Janati H. Pyts：一个用于时间序列分类的Python包。J Mach LearnRes 2020;21：1https://www.jmlr.org/papers/v21/19-[8]Löning M ， Bagnall A ， Ganesh S ， Kazakov V ， Lines J ， Király FJ.Sktime：用于时间序列机器学习的统一接口。2019，arXiv：1909.07872[Cs，Stat].[9]Tavenard R，Faouzi J，Vandewiele G，Divo F，Androz G，Holtz C，et al.Tslearn，a machine learning toolkit for time series data. J Mach Learn Res2020;21（118）：1https://jmlr.org/papers/v21/20-091.html[10]Rakthanmanon T，Campana B，Mueen A，Batista G，Westover B，ZhuQ ， et al. Searching and mining trillions of time series concurrences underdynamic time warping.第18届ACM SIGKDD知识发现和数据挖掘国际会议论文 集 。 北 京 ， 中 国 ： ACM 出 版 社 ;2012 年 ， 第 262 页 。http://dx.doi.org/10.1145/2339530.2339576网站。[11]刘H，Hartmann Y，Schultz T. CSL-SHARE：一个基于多模式可穿戴传感器的 人 类 活 动 数 据 集 。 前 计 算 科 学 2021;3 ： 90 。 http://dx.doi 的 网 站 。org/10.3389/fcomp.2021.759136。[12]Harris CR ， Millman KJ ， Van Der Walt SJ ， Gommers R ， Virtanen P ，Cournapeau D ， et al. Array programming with NumPy. Nature 2020;585（7825）：357-62. http://dx.doi.org/10.1038/s41586-020-2649-2网站。[13][10] Raghannan P，Raghannan R，Raghannan T，et al.SciPy 1.0：Python中科 学 计 算 的 基 本 算 法 。 Nat Methods 2020;17 （ 3 ） ： 261-72.http://dx.doi.org/10.1038/s41592-019-0686-2网站。[14]放大图片作者：Lam SK，Pitrou A，Seibert S. Numba：基于LLVM的pythonJIT编译器。在：在HPC中的LLVM编译器基础设施的第二次研讨会的会议记录。2015年，第1-6页。http://dx.doi.org/10.1145/2833157.2833162网站。[15]亨特JD。Matplotlib：2D图形环境。计算机科学与工程2007;9（03）：90-5.http://dx.doi.org/10.1109/MCSE.2007.55网站。[16]王X，Mueen A，Ding H，Trajcevski G，Scheuermann P，Keogh E.时间序列 数 据 表 示 方 法 与 距 离 测 度 的 实 验 比 较 Data Min Knowl Discov 2013;26（2）：275网址：//dx.doi.org/10.1007/s10618-012-0250-5网站。[17] [10] Möller-Levet CS，Klawonn F，Cho K-H，Wolkenhauer O.短时间序列非均匀采样点的模糊聚类在：智能数据分析国际研讨会。Springer;2003，p. 330-40. http://dx.doi.org/10.1007/978-3-540-45231-7_31网站。[18]马托·P-F时间扭曲编辑距离与刚度调整时间序列匹配。IEEE TransPatternAnalMachIntell2008;31（2）：306-18.http://dx.doi.org/10.1109/TPAMI.2008.76网站。[19][10]张文辉，张文辉.时间序列的时间对齐测量。Pattern Bronze 2018;81：268-79. http://dx.doi.org/10.1016/j.patcog.2018.04.003网站。[20]Barandas M，Folgado D，Fernandes L，Santos S，Abreu M，Bota P，et al.TSFEL：Time series feature extraction library. SoftwareX 2020;11 ：100456.http://dx.doi.org/10.1016/j.softx.2020.100456网站。[21]Ahmadzadeh A，Sinha K，Aydin B，Angryk RA. MVTS-data toolkit：用于预 处 理 多 变 量 时 间 序 列 数 据 的 Python 包 。 SoftwareX 2020;12 ： 100518.http://dx.doi.org/10.1016/j.softx.2020.100518网站。[22]Demšar J，Curk T，Erjavec A，Črt Gorup， Hočevar T，MilutinoviM ，Možina M ， et al. Orange ： Data mining toolbox in python.J Mach LearnRes 2013;14：2349http://jmlr.org/papers/v14/demsar13a.html[23]Frank E，Hall M，Holmes G，Kirkby R，Pfahringer B，Witten IH，et al.Weka-A machine learning workbench for data mining. 数据挖掘和知识发现手册。Springer; 2009，p.1269-77. 网址：//dx.doi.org/10.1007/978-0-387-09823-4_66网站。[24]Pedregosa F ， Varoquaux G， Gramfort A， Michel V， Thirion B， GriselO ， et al. Scikit-learn ： Machine learning in Python. J Mach Learn Res2011;12：2825https://www.jmlr.org/papers/v12/pedregosa11a.html