融合FastDTW与SBD的稀有时间序列分类方法.pdf

http:/DOI:10.13700/j.bh.1001-5965.2021.0471融合 FastDTW 与 SBD 的稀有时间序列分类方法李显，牛保宁*，柳浩楠，张旭康(太原理工大学信息与计算机学院，晋中030600)摘要：稀有时间序列分类（RTSC）在天文观测等领域有广泛应用。针对目前稀有时间序列方法处理大规模数据集存在准确率低和时间成本高的问题，以天文观测中的短时标稀有天体光变事件耀发现象为研究对象，提出改进的稀有时间序列分类方法 RTSC-FS。该方法融合动态时间弯曲（DTW）的改进 FastDTW 和 SBD 度量序列距离，同时具有 FastDTW 计算复杂度低、衡量精度高和 SBD 计算速度快的特点，采用滑动窗口过滤、重采样、窗函数平滑、标准化数据等数据预处理技术进一步降低时间成本。在由地基广角相机阵（GWAC）记录到的星等变化的时间序列数据集上，所提方法从约 791 万天次的光变数据中发现具有耀发特征的曲线 44 条，召回率 60.27%，查准率达 34.65%，相比 Baseline 发现数量更多，召回率、查准率有所提升。关键词：稀有时间序列分类；FastDTW 算法；SBD 方法；地基广角相机阵；星等中图分类号：TP311文献标志码：A文章编号：1001-5965（2023）06-1523-10稀有时间序列分类（ratetimeseriesclassification,RTSC）是从大规模的时间序列数据集中寻找极少的、具有固定特征的样本，其在科学研究领域有着广泛的应用。时间序列数据是一类具有先后顺序的数据点构成的序列，具有数据量大、价值密度低的特点。在天文观测领域，随着现代时域天文观测技术的发展和高性能观测设备的使用，在大规模数据中发现稀有时间序列数据成为天文事件发现的重要手段1。地基广角相机阵（ground-basedwide-anglecamera，GWAC）是为中法天文卫星项目 SVOM2建设的时域天文巡天设备，每 15s 采集观测数据一次3，目标是发现与监测伽马射线暴的光学瞬时辐射和其他剧烈变换的天体4。GWAC 采集的天体点源图像数据经过处理后生成光变曲线，反映天体在某一时间区间内的亮度变化，属于时间序列数据。在时间跨度达 6 个月的情况下，GWAC 在设定的 89个天区范围可观测到约 790 万天次的光变数据，从这些时间序列数据中发现符合特定模式的稀有时间序列数据是科研人员面临的一个主要问题。动态时间弯曲（dynamictimewrapping，DTW）及其改进算法5-8是时间序列挖掘的有效算法，其被用于发现稀有时间序列时，存在以下问题：目标时间序列稀少，如果不进行初步筛选，算法在全部的数据上发现目标序列的时间成本高。未经过预处理的时间序列数据由于噪点、天气、设备等因素对观测效果的影响，形成的曲线的特征不明显，导致查准率低。为解决以上问题，本文采用滑动窗口滤波进行初步筛选，以剔除大部分不相关曲线，大幅减少不必要的计算；使用重采样方法对数据降维，在保留曲线特征的基础上减小计算量；使用窗函数实现平滑处理，降低噪点对时间序列特征的破坏，提高目标时间序列识别的准确率；采用标准化手段使分布收稿日期：2021-08-19；录用日期：2022-01-02；网络出版时间：2022-01-1017：27网络出版地址： J.北京航空航天大学学报，2023，49（6）：1523-1532.LI X，NIU B N，LIU H N，et al.A hybrid method for rare time series classification with FastDTW and SBDJ.Journal of BeijingUniversity of Aeronautics and Astronautics，2023，49（6）：1523-1532（in Chinese）.2023年6月北京航空航天大学学报June2023第49卷第6期JournalofBeijingUniversityofAeronauticsandAstronauticsVol.49No.6在不同范围的时间序列统一尺度，提高识别率。本文的创新点如下：1）采用滑动窗口快速地对数据集进行初步的筛选，减小待处理的数据量；采用重采样对数据降维；采用窗函数对数据降噪；采用标准化提高数据的识别率。2）提出 RTSC-FS 方法，其是结合了 FastDTW算法与SBD9的稀有时间序列分类方法，利用FastDTW准确率高和 SBD 计算速度快的优势，保证了稀有时间序列数据分类的速度和精度。1相关工作时间序列分类是时间序列数据挖掘中最常见和最流行的技术，根据数据集的不同可以分为标准时间序列分类和稀有时间序列分类。数据预处理在标准时间序列分类和稀有时间序列分类中是必不可少的，常见的数据预处理的目的是对数据降维、降噪、方便计算。滑动窗口思想是一种能够有效的对时间序列中固定区间内采样并计算的手段，滑动窗口关心在一段时间内的数据流中数据的局部分布情况10，以更好地获取当前数据流的状态。常见的滑动窗口分为固定滑动窗口和可变滑动窗口。Schfer 和Leser11使用滑动窗口方法将时间序列转换为特征向量，结合机器学习分类器对时间序列进行分析。采用滑动窗口思想能够有效地捕获数据的局部特征并及时对序列数据进行筛选，避免不必要的计算。可变滑动窗口能够有效地自适应序列长度，将窗口大小调整到相对合理的大小，便于计算。时间序列数据的重采样方法主要分为升采样和降采样 2 种类型。升采样是将低频数据转为高频数据的过程，需要在原始数据的基础上采用插值算法实现。降采样是将高频数据转为低频数据的过程，方便数据的分析过程。由于真实的观测过程不可避免地会使部分数据含有不可去除的噪声，可能会对识别造成干扰，如光变曲线短暂的下降等。在对数据进行重采样后，对数据进行平滑处理能够有效地去除光变曲线中的噪点，提高时间序列的信噪比（signaltonoiseratio，SNR）。在时域信号的分析处理过程中，对数据进行分窗处理是一种常见的手段。时间序列数据也是一种时域信号，具有非周期性、离散化和有限长的特点，在对其进行计算分析时会产生频谱能量泄漏的现象。而窗函数就是一种对时域信号数据进行有效降噪处理的工具，原始的时间序列数据在窗口函数的作用下能够降低频谱能量泄漏12。窗函数会试图通过消除不连续性并在测量时间间隔的开始和结束处创建平滑的瞬变来减少频谱泄漏的影响13。标准化是一种能够将数据按照一定比例放缩、避免单位限制、方便进行比较的数据处理手段。常用的标准化方法包括 Z-Score 标准化、最大绝对值归一化、最小最大归一化、稳健标准化。归一化能够将数据规范到 0,1 区间，更加方便计算，而标准化并无此限制，采用标准化或归一化需要根据实际情况而定。1.1标准时间序列分类标准时间序列分类方法可以分为基于距离的方法和基于特征的方法14。前者以 DTW 算法5及其改进算法6-8为代表，其关键是测量给定的 2 个时间序列之间的相似度；后者以 FS（fastshapelets）15、BSPCOVER16、LTS17为代表，其关键是寻找 shap-elets。Shapelets 是 Keogh 和 Ye18提出的一种时间序列数据挖掘原语，是时间序列的一个最大区分子序列。由于寻找 shapelets 时间复杂度很高，不适合大规模数据集的时间序列发现。现存适用广泛、性能好的时间序列分类方法是 DTW 及其改进算法。DTW 算法是动态规划算法在时间序列距离问题上的应用，从前往后求得2 个时间序列数据之间的点的距离，再从后往前选取最小值求得最短路径。相比 Euclidean 距离，DTW距离能够更好地衡量 2 个序列之间形状上的相似度，但是 DTW 的时间复杂度为 O(n2)，其中，n 为时间序列的长度，不能够在大规模数据集中直接应用。DTW 的改进主要从降低时间成本和提高分类准确率方面进行。在降低时间成本方面，Salvador 和 Chan6将DTW 改进为 FastDTW 算法，采用粗粒度化、投影、细粒度化 3 个方面的优化策略，减少算法的搜索空间，将原始算法的复杂度从 O(n2)降低到 O(n)，但是由于其得到的是较优解，仍然存在一定的误差。FastDTW 算法围绕着降低计算的时间复杂度进行改进，虽然取得了不错的效果，但是在面对长时间序列数据距离计算时仍然会消耗大量时间，由于其计算的是较优解，在精确度上有所欠缺。此外，现存研究方法大多需要遍历数据集计算相似度，在数据集规模较小的情况下（如 UCR 数据集），可以快速完成时间序列数据相似度的计算，但是，在数据规模很大的情况下，时间上的消耗往往是难以接受的。在提高分类准确率方面，加权 DTW（weightedDTW，WDTW）19将惩罚机制应用到序列之间距离1524北 京 航 空 航 天 大 学 学 报2023年的计算上，以降低噪点对距离失真的影响，该方法能够提高距离计算的准确率，但是时间复杂度为 O(n4)，在大规模时间序列分类上的时间消耗是令人难以接受的。时间序列数据分类复杂的原因在于要分类的时间序列数据不等长，这导致一般分类方法难以直接应用。Rebbapragada等20采用改进的 K 均值聚类算法对时间序列数据的特征进行提取，但是在序列长度较长且长短不一时数据处理过程十分耗时。Hyndman 等21提出的方法需要对数据进行主成分分析，这在大数据集的处理上往往是十分耗时的。Imani等22利用邻居序列的信息进行序列的聚类，可以有效减小包括相移在内的时间序列的子序列之间的变化带来的影响。实际情况中，时间序列数据的变化范围往往不统一，如相同模式的序列数值的变化范围可以相差几倍甚至几十倍，因此有必要对其进行标准化。现存的分类方法大多直接将时间序列的源数据参与计算，往往缺乏预处理步骤，对于离群点或数据在区间内进行波动导致序列之间产生误差的影响不能有效去除。K-Shape 算法是 Paparrizos 和 Gravano9提出的一种用于时间序列聚类的算法，SBD 是该算法中使用归一化互相关系数进行时间序列距离衡量的工具，也是该算法的核心，SBD 越小则代表 2 个时间序列的相似程度越高，此外，SBD 的计算可以通过快速傅里叶变换进行加速，因此可以用来进行时间序列数据分类。另外，现存的分类方法大多采用单一的距离判定标准，本文综合采用 DTW 距离和 SBD两种方法进行时间序列相似度的判定。1.2稀有时间序列分类标准时间序列分类默认训练数据中各个样本类别均衡，然而现实世界中的数据集存在着类别不平衡现象，本文所解决稀有时间序列分类问题的数据集尤甚。当前，针对稀有时间序列分类问题的解决大致从算法和数据 2 个角度进行改进。数据上的改进通常是针对数据集中的类别不平衡进行调整，根据一定的方法生成贴合真实的样本23，使各类别样本数趋于平衡，数据改进方面的方法可以分为过采样、欠采样和混合采样 3 种方法。在过采样方面，Douzas 等24结合 k-means 和合成少数类过采样技术(syntheticminorityoversamplingtechnique,SMOTE)方法，减少了噪声的产生，有效解决了类间不平衡问题。Ma 等25采用时间序列扭曲（timeserieswraping,TSW）方法对样本进行微调从而扩充数据集。在欠采样方面，Kang 等26通过在采样前使用噪声滤波处理改善噪声的影响，取得了显著改进。然而本文所面向的大规模数据集非正样本序列长、噪声多且形态复杂，以上方法并不适用。算法上的改进以代价敏感方法、集成学习、单分类学习为代表。Gnnemann27在逻辑回归中引入代价敏感模型用于解决汽车维修问题，节约了10%的成本。Bo28改进了随机森林的子空间选择和模型集成使得随机森林用于不平衡数据的分类。Lee 等29提出动态时间池（dynamictemporalpooling,DTP）并改善卷积神经网络（convolutionalneuralnetwork,CNN）的分类性能，在单