特征点分段提取的时间序列模式匹配方法_李正欣.pdf
《特征点分段提取的时间序列模式匹配方法_李正欣.pdf》由会员分享,可在线阅读,更多相关《特征点分段提取的时间序列模式匹配方法_李正欣.pdf(7页珍藏版)》请在咨信网上搜索。
1、http:/DOI:10.13700/j.bh.1001-5965.2021.0546特征点分段提取的时间序列模式匹配方法李正欣*,刘畅,吴诗辉,郭建胜(空军工程大学装备管理与无人机工程学院,西安710051)摘要:常用的时间序列模式匹配方法难以平衡计算复杂度与匹配精度,针对该问题,提出了一种特征点分段提取的时间序列模式匹配方法。提取时间序列每个变量维度上的特征点,降低序列长度;将特征点序列转化为分位点矩阵,利用欧氏距离对分位点矩阵进行相似性度量;在几组时间序列数据集上对所提方法进行分类实验。结果表明:所提方法在降低计算复杂度的同时,获得了较高的匹配精度。关键词:时间序列;模式匹配;特征提取;
2、分位点矩阵;计算复杂度中图分类号:TP391文献标志码:A文章编号:1001-5965(2023)07-1593-07xt(j)t(t=1,2,m)tj(j=1,2,n)jxt(j)jtn=1xt(j)n 1xt(j)现实世界中,存在着大量时间序列类型数据1,如捕捉手语动作产生的信号2,电商平台中用户的浏览记录3,股票交易中的交易量、开盘价、收盘价4等形成的数据。时间序列是一组记录事物状态随时间发生变化的观测值5,可定义为,其中,表示 个时刻,表示第个变量,表示第 个变量在第 个时刻上的记录值6。当时,为一元时间序列;当时,为多元时间序列7。然而,随着云储存技术的快速发展,时间序列数据规模日益
3、庞大8。时间序列数据挖掘主要从规模庞大的时序数据中进行整理9,最终产生有效的信息10,其逐渐成为掌握当下现实事物规律的方法之一11。时间序列数据挖掘包括相似性查询12、关联分析13、分类14、聚类15、预测16、模式匹配17等内容。其中,模式匹配是描述时间序列之间相似性的方法。在开展时间序列数据挖掘其他工作时,需要先使用模式匹配方法。模式匹配又可细分为特征提取与相似性度量 2 个过程18。特征提取主要降低时间序列维数,相似性度量以降维后的特征序列为输入,由距离度量公式计算出 2 条时间序列的距离,距离越小说明 2 条时间序列相似程度越高19。目前,常用的模式匹配方法在提高计算效率或提高度量准确
4、率方面效果理想20,但能同时达到两者的方法不多。因此,研究既降低计算复杂度又保持较高匹配精度的模式匹配方法具有现实意义和理论价值21。为此,本文提出了一种特征点分段提取的时间序列模式匹配方法。首先,提出一种特征点分段提取方法,提取时间序列的特征点;然后,依据特征序列计算出分位点矩阵,利用欧氏距离对分位点矩阵进行相似性度量;最后,通过实验对本文方法进行有效性验证。1相关研究常用的时间序列模式匹配方法包括奇异值分解(singularvaluedecomposition,SVD)22、动态时间弯曲(dynamictimewarping,DTW)23、自适应代价动态时间弯曲的多元时间序列相似性度量方法
5、(adaptive cost multivariate dynamic time warping,ACM-DTW)24、趋势距离(trenddistance,TD)25、欧氏距离(Euclideandistance,ED)26和基于点分布特征(pointdistribution,PD)的方法27等。收稿日期:2021-09-13;录用日期:2021-12-10;网络出版时间:2022-02-1514:35网络出版地址: J.北京航空航天大学学报,2023,49(7):1593-1599.LI Z X,LIU C,WU S H,et al.Segmentation extraction of f
6、eature points for time series pattern matchingJ.Journal of Beijing Universityof Aeronautics and Astronautics,2023,49(7):1593-1599(in Chinese).2023年7月北京航空航天大学学报July2023第49卷第7期JournalofBeijingUniversityofAeronauticsandAstronauticsVol.49No.7SVD 方法将时间序列不同变量放在一起处理,在特征提取阶段,建立相关系数矩阵并以线性变换的结果为输入,使用距离公式计算匹配精
7、度。SVD的优点是能够体现不同变量的内在联系,但是会打乱时间序列的先后顺序,容易降低后续匹配精度的准确性。DTW 距离可以计算 2 条长度不相等的时间序列,具有较高准确性,在相似性度量中被广泛使用。但其计算代价较高,需要在众多弯曲路径中找出最短路径,在一些数据规模较大的时间序列上效果不理想。ACM-DTW 方法以 DTW 距离为基础,定义自适应代价函数赋给基础距离矩阵权重,在匹配过程中限制点列的使用来减少不合理匹配情况出现;ACM-DTW 优化了 DTW 距离的弯曲路径,一定程度地降低 DTW 距离计算复杂度,但需要设置额外空间记录点列使用次数且参数初始化较复杂。TD 方法同样是以 DTW 距
8、离为基础的方法,使用最小二乘法提取出时间序列的倾斜角与时间跨度,以此作为特征利用 DTW 距离完成相似性度量。TD 能够有效降低 DTW 距离的计算代价,但需要事先设置参数且参数优化复杂。ED 距离计算复杂度低,其计算不同时间序列之间对应时刻的平方和并累积求和。ED 距离要求序列等长,匹配精度也容易受到序列伸缩、弯曲等形变的影响。PD 方法以多元时间序列的局部重要点为基础,根据重要点的图像特征使用 ED 距离完成相似性度量。PD 方法能够度量时间长度不相等的时间序列,但将不同变量和时间的观测值放在一起进行局部重要点提取,没有考虑变量之间的量纲差异,在大规模多元时间序列数据集上效果不理想。针对以
9、上模式匹配方法无法平衡匹配精度与计算复杂度的问题,本文提出了一种特征点分段提取的时间序列模式匹配方法。2特征点分段提取方法x Rnmnm根据时间序列的趋势特性得到序列特征,本节提出一种特征点分段提取的方法。利用滑动窗口28提取出时间序列各变量维度的特征点,压缩时间序列长度。时间序列,为变量维数,为时间维数。通常这 2 个维数较高,为了降低计算复杂度,提取时间序列特征。由于时间序列不同变量代表着序列的不同属性,同时将变量和时间放在一起提取特征,则没有考虑变量之间的量纲差异,容易降低后续相似性度量结果。在确保变量维数不变的情况下,使用滑动窗口提取特征点,提出一种特征点分段提取的方法。x Rnm输入
10、:输入:时间序列,滑动窗口因子。seg输出:输出:特征序列。xjx(j)xi(j)j=1,2,n i=1,2,mxi(j),xi(j),xi+(j)步骤1对于 第 个变量,以第 i 观测值为滑动窗口中心,其中,滑动窗口为。xi(j)xi(j)xi(j)seg(j)步骤2如果观测值为当前所在滑动窗口内的最大或最小值,则观测值为特征点,并将特征点提取到序列中。x Rnmnseg步骤3针对时间序列所有变量,按照顺序执行步骤1、步骤2,得到一条 维的特征序列。3特征点分段提取的相似性度量x Rnm时间序列提取出的特征点如图 1 所示。可以看出,不同特征序列上的特征点个数一般不相同,如果直接使用特征序列
11、进行相似性度量,可能会因此增加后续度量的难度。25025jim221n特征点数值特征序列编号时间图1特征点提取示意图Fig.1Schematicdiagramoffeaturepointextractionj(j=1,2,n)seg(j)seg(j)为此,引入统计学常用的 9 个分位点29(最小值点、5%、10%、25%、50%、75%、90%、95%、最大值点),利用特征序列构建特征矩阵。于是,提出一种分位点矩阵提取方法。首先,对第个变量维度上的特征点序列从小到大排序;然后,对排序后的序列计算出 9 个分位点;最后,对其他特征点序列用同样方法提取 9 个分位点,形成分位点矩阵。seg输入:输
12、入:特征序列。Q输出:输出:分位点矩阵。segj(j=1,2,n)seg(j)步骤1针对的第条特征序列,对该序列上的特征点按照从小到大的方式排序。步骤2对排序后的特征序列,分别提取 9 个分 位 点:最 小 值 点、5%、10%、25%、50%、75%、1594北 京 航 空 航 天 大 学 学 报2023年Q(j)90%、95%、最大值点,构成分位点序列。Q步骤3对于其他变量维度上的特征序列,依次执行步骤 1、步骤 2,最终形成分位点矩阵。x RnmQ Rn9通过以上方法,将时间序列转换为分位点矩阵。需要注意的是,分位点矩阵不改变时间序列的变量维度,将时间维度压缩为 9。对于 2 条长度不同
13、的时间序列,其分位点矩阵结构相同。这样,可以直接用欧氏距离度量 2 条序列的分位点矩阵。为不失一般性,采用欧氏距离的平方刻画 2 条时间序列的距离,如下:DED(Qx,Qy)=ni=19j=1(qxijqyij)2(1)QxQyxyqxijqyijijO(n)式中:、分别为时间序列、的分位点矩阵;、分别为 2 个分位点矩阵第 行、第 列上的元素。显然,式(1)的计算复杂度为。为了后续实验的顺利进行,将特征点分段提取的时间序列模式匹配方法记为 SFP-ED。4实验与结果分析本节使用 6 组时间序列数据集,对其中所有样本逐一使用 5 种模式匹配方法进行实验,并进行匹配精度比较,同时,对 SFP-E
14、D 方法的参数进行敏感性分析。4.1实验方法与实验数据本 文 实 验 环 境 为 Intel(R)Core(TM)i5-9300HCPU,16GBRAM,Windows10,MATLABR2018a。参 与 实 验 对 比 的 模 式 匹 配 方 法 有 SVD、DTW、ACM-DTW、TD 和 PD。其中,DTW 方法直接使用原始时间序列进行距离度量,输出计算结果。实验方法采用 k 近邻法与留一法结合的形式进行,确定时间序列数据集的样本个数 n,任选其中一个样本 T 作为输入序列。首先,使用 6 种方法找到与 T 最近似的 k 个序列。然后,找出 k 个序列中与序列 T 标签相同的样本 N。
15、最后,将 N 与 k 的比值作为度量结果。将时间序列数据集中的其余样本,依次作为输入序列,重复以上实验,得到 n 个度量结果,匹配精度即为这 n 个度量结果的平均值30。实验采用类别标签已知的 6 组公开数据集,前 5 组为多元时间序列数据集,后 1 组为一元时间序列数据集,详情如表 1 所示。4.2实验结果比较4.2.1ASL 数据集实验结果=1在 ASL 数据集上,使用第 1 节中的模式匹配方法与SFP-ED 方法进行实验,其中,TD 方法(maxError=0.03、=0.8、=0.2)、PD 方 法(Xi1:i+1,j1:j+1)、SFP-ED()结果如表 2 所示。表1实验数据集Ta
16、ble1Detailofexperimentaldatasets数据集长度均长变量个数样本量类别ASL479559222168LP115156884JV72916126409EEG25625664222WR128191836862442Trace27527512004表2ASL 数据集上的匹配精度Table2MatchingaccuracyonASLdatasetkSVDDTWACM-DTWTDPDSFP-ED10.7180.9770.9260.9720.5790.98650.6390.9290.8700.9580.5700.947100.5700.9290.8560.9060.5570.94
17、4DTW、ACM-DTW、TD 和 SFP-ED 方法的匹配精度较高。其中,TD 方法提取序列的倾斜角、时间跨度作为特征,ACM-DTW 方法设置自适应损失函数提高 DTW 距离运算速率,SFP-ED 方法提取序列的特征点作为特征。DTW、ACM-DTW 和 TD 方法是以 DTW 距离为基础,而 SFP-ED 方法以欧氏距离为基础,使得 SFP-ED 的计算复杂度较低于 DTW和 TD 方法。SVD、PD 方法匹配精度较低。这是因为 SVD方法打乱了时序顺序,存在误判风险;PD 方法将相邻变量与时间放在一起提取局部重要点,没有考虑变量之间的量纲差异;SFP-ED 方法针对每一个变量维度提取特
18、征点,能够体现不同变量之间的差异。表 3 给出了 6 种方法在不同准确率 e 下的匹配次数。在准确率较低的情况下(e40%),DTW、ACM-DTW、TD 和 SFP-ED 方法对应的匹配次数比 SVD、PD 方法少;在准确率较大的情况下(e80%),DTW、ACM-DTW、TD 和 SFP-ED 方法所对应的匹配次数比 SVD、PD 方法多。进一步地,将ASL 数据集中第87 个序列(ASL_87)作为输入(见图 2),分别采用上述 6 种方法,找出最相似的序列,如图 3 所示。SVD、TD 与 SFP-ED 方法找出的序列与输入序列较为相似,且都属于同一类(boy)。而 DTW、ACM-D
19、TW 和 PD 方法形状差别较大。4.2.2其他数据集实验结果使用SVD、PD、TD、DTW、ACM-DTW、SFP-ED方法在 ASL、LP1、JV、EEG、WR 多元时间序列数据集上进行实验,计算匹配精度,因为 SVD、PD 是第7期李正欣,等:特征点分段提取的时间序列模式匹配方法1595基于多元时间序列的模式匹配方法,所以仅使用DTW、ACM-DTW、TD、SFP-ED 方法在 Trace 一元时间序列数据集上进行实验。实验结果为 k=1 时的匹配精度,如表 4 所示。其中,PD、TD、SFP-ED方法采取上述相同的参数设置30。DTW、ACM-DTW、TD 和 SFP-ED 方法在 6
20、 组数据集上匹配精度较高。SVD 和 PD 方法效果不理想。4.3SFP-ED 方法参数敏感性分析本节分析滑动窗口因子 对 SFP-ED 方法的压缩程度和匹配精度的影响,实验结果如图 4 所示。压缩程度近似表示为表36 种模式匹配方法在不同准确率下的匹配次数Table3Matchingtimesof6patternmatchingmethodsunderdifferentaccuracyratese/%SVDDTWACM-DTWTDPDSFP-EDN=1 N=5 N=10N=1N=5N=10N=1N=5N=10N=1N=5N=10N=1N=5N=10N=1N=5N=10061201250016
21、9060091331430010190301302027150040002517203019122283403419130105433618945025659261602926125101398341763707151571310802271411291715222361079073025301215100155846021117714820015412521018813512565522131891731.00.5002020406010变量变量值时间图2输入序列(ASL_87,boy)Fig.2Inputsequence(ASL_87,boy)1.00.50变量值1.00.50变量值1.0
22、0.50变量值1.00.50变量值1.00.50变量值1.00.50变量值0020202040602040602040601010变量变量02010变量02010变量02010变量02010变量时间204060时间204060时间204060时间时间时间(a)SVD方法(ASL_101,boy)(b)DTW方法(ASL_166,change-mind)(c)ACM-DTW方法(ASL_166,change-mind)(d)TD方法(ASL_92,boy)(e)PD方法(ASL_114,building)(f)SFP-ED方法(ASL_85,boy)图3不同方法在 ASL 数据集上寻找的最相似序
23、列Fig.3ThemostsimilarsequencefoundbydifferentmethodsonASLdataset1596北 京 航 空 航 天 大 学 学 报2023年=lm(2)lm式中:为特征序列的平均长度;为时间序列的时间维长度。l实验结果表明,随着参数 的增大,减少,也=1,5,10相应减小,匹配精度变化不大。这表明 在一定范围内变化,对 SFP-ED 方法的匹配精度影响较小。为了直观地展示 对匹配精度的影响,选取 ASL 数据集中第 204 号样本,以其第 1 个变量维度序列为分析对象,分别给出三种情况下特征点的提取情况,如图 5 所示。同时,计算出 3 种情况下对应的
24、 9 个分位点,如表 5 所示。变大,特征点数量减少,而提取的最大值点和最小值点保持不变,因此,9 个分位点的变化不大。4.4计算复杂度比较在整个实验过程中,TD、DTW 和 SFP-ED 方法性能较好。其中,TD、DTW 方法在相似性度量阶段都使用 DTW 距离进行计算,SFP-ED 方法则使用欧氏距离进行计算。TD 方法以每拟合段的斜率和表46 组数据集上的匹配精度Table4Accuracyon6datasets数据集SVDDTWACM-DTWTDPDSFP-EDASL0.7180.9770.9260.9720.5780.986LP10.4770.8860.9090.6360.8300.
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 特征 分段 提取 时间 序列 模式 匹配 方法 李正欣
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。