共计 4180 个字符，预计需要花费 11 分钟才能阅读完成。
原文链接：http://tecdat.cn/?p=22945
最近咱们被客户要求撰写对于动静工夫规整算法的钻研报告，包含一些图形和统计输入
动静工夫扭曲算法何时、如何以及为什么能够无力地取代常见的欧几里得间隔，以更好地对工夫序列数据进行分类
工夫序列分类的动静工夫扭曲
应用机器学习算法对工夫序列进行分类须要肯定的相熟水平。
工夫序列分类（TSC）工作通常由 监督算法 解决，它旨在创立分类器，将输出工夫序列映射到形容工夫序列自身的一个或多个特色的离散变量（类）中。
能够在语音辨认或手势和静止辨认中找到时序分类工作的乏味示例。
图 — 挪动辨认示例
用于其余类型的数据（例如表格数据）的规范分类算法不能间接利用，因为它们将每个样本与其余样本离开解决。
对于工夫序列，不能疏忽数据的工夫程序，因而，不能思考工夫序列的每个样本而思考其余样本，但必须保留工夫程序。
出于这个起因，在文献中，有几种类型的工夫序列分类技术，将在下一段中简要解释。
工夫序列分类办法
作为 TSC 不同类型办法的简要概述。
- 基于区间的办法：从不同的区间中提取工夫序列的特色和信息，并将规范分类器利用于特色自身。算法的一个示例是 时序森林分类器。
- 基于字典 的办法：将工夫序列的特色转换为代表类的单词。规范分类器利用于提取单词的散布。算法的一个例子是 模式袋。
- 基于频率的办法：在频谱程度上提取工夫序列的特色，通过频率剖析和间断的规范分类器。算法的一个示例是 随机距离频谱集成。
- 基于形态的办法：形态是代表类的工夫序列的子序列。提取工夫序列 中 k 个 最具特色的形态，而后应用规范分类器。算法的一个示例是 Shapelet 变换分类器。
- 集成办法：对于个别问题十分有竞争力，它们联合了几个预计器，例如 HIVE-COTE 算法。
基于间隔的办法
在本文中，咱们将重点介绍基于间隔的办法。
它是一种将 间隔度量 与分类器 混合以确定类成员的非参数办法。分类器通常是 k 最近邻（KNN） 算法，用于理解要标记的工夫序列是否与训练数据集中的某些工夫序列类似。依据邻域，最近的类或最近类的聚合与所剖析的工夫序列相关联。动静工夫扭曲（DTW）是基于间隔的办法的一个示例。
图 — 基于间隔的办法
间隔指标
在工夫序列分类中，咱们须要计算两个序列之间的间隔，同时牢记每个序列内样本之间的工夫关系和依赖性。抉择正确的指标是这种办法的根底。
欧几里得间隔
让咱们开始思考常见的欧几里得间隔。
鉴于工夫序列分类，欧几里得间隔是不适合的，因为即便它保留了工夫程序，它也以逐点的形式测量间隔。实际上，与两个工夫序列的欧几里得间隔的相似性是通过思考它们的振幅来计算的，而与相移、时移和失真无关。
以图中的示例为例。咱们有树工夫序列：ts1、ts2 和 ts3。咱们心愿检测两条正弦曲线彼此类似，因为它们具备雷同的形态和高低趋势，即便它们的相位和频率略有不同。然而，如果咱们计算欧几里得指标，直线 ts3 的后果更靠近 ts1。
图 — 要比拟的工夫序列示例
之所以呈现这种景象，是因为欧几里得间隔正在比拟曲线的振幅，而不容许任何工夫拉伸。
图 — 欧几里得匹配
动静工夫扭曲
引入了动静工夫扭曲以防止欧几里得间隔的问题。
从历史上看，它是为语音辨认而引入的。如图所示，以不同的速度反复雷同的句子，有必要将工夫序列与雷同的单词相关联，从而治理不同的速度。
图 — DTW 的语音辨认利用
DTW 容许您通过确定工夫序列之间的最佳对齐形式并最大水平地缩小工夫失真和偏移的影响来掂量工夫序列之间的相似性。
不同相的类似形态，及时匹配弹性翘曲。
图 — 动静工夫扭曲匹配
算法
让咱们思考两个工夫序列 X =（x₁，x₂，…，xn） 和 Y =（y₁，y₂，…，ym）， 在等距工夫点采样，长度相等或不同。
咱们的指标是找到对齐工夫序列的最小间隔。
图 — 要对齐的工夫序列示例
定义部分老本矩阵，该矩阵将被最小化以找到最佳对齐形式。老本矩阵 C 定义为所有工夫序列点的成对间隔：
图 — 当地老本矩阵 C
目标是通过遵循老本最低的路线，在部分老本矩阵上找到对齐工夫序列的 翘曲门路。
翘曲门路 p 是部分老本矩阵上的点序列，因而是两个工夫序列上的几个点序列：
必须满足一些条件：
- 边界条件：
翘曲门路的终点和起点必须是序列的第一个和最初一个点。
- 枯燥性条件：
以保留工夫程序。
- 步长条件：
以限度跳跃和工夫偏移，同时对齐序列。
每个翘曲门路都有相干的老本：
- 与翘曲门路 p 相干的老本函数
图 — 翘曲门路示例（非最佳）
目标是找到最佳的翘曲门路：
DTW 通过递归实现解决，为此能够找到老本最低的翘曲门路：
图 — 最佳翘曲门路
找到最佳翘曲门路后，将计算出相干的最优老本，并将其用作 DTW 间隔。
递归实现达到最优，但计算成本为 O（NM）， 其中 N 和 M 是两个工夫序列的长度。
k- 最近邻
回到对感兴趣的工夫序列进行分类的原始问题，间隔度量能够与 k - 最近邻（k-nn）算法耦合。这意味着您能够计算工夫序列到训练数据集中所有其余工夫序列的 DTW 间隔。而后，如果您正在思考应用 1-nn 办法，则能够将最近邻的类与工夫序列相关联，或者，同样，您能够将 k 最近类中最罕用的类与 k-nn 办法相关联。
通过这种形式，您曾经达到了为工夫序列调配类的指标，该办法思考了工夫序列的时移。
传统 DTW 的代替办法可加快速度
疾速 DTW
提出了一种多级办法来放慢 FastDTW 算法中的算法速度。
它须要不同的步骤：
- 粗化：将工夫序列放大为较粗的工夫序列。这通过对相邻点对求平均值来减小工夫序列的大小。
- 投影：找到最小间隔的翘曲门路，用作更高分辨率翘曲门路的初始猜想。
- 优雅：通过部分调整将翘曲门路从较低分辨率细化到较高分辨率。此步骤在投影门路的邻域中查找最佳翘曲门路，半径 r 参数管制邻域的大小。
图 — 疾速 DTW
FastDTW 容许疾速分辨率，复杂度 为 O（Nr）， 具备良好的次优解决方案。
R 语言实现
在这篇文章中，咱们将学习如何找到两个数字序列数据的排列。
创立序列数据
首先，咱们生成序列数据，并在一个图中将其可视化。
plot(a, type = "l")
lines(b, col = "blue")点击题目查阅往期内容
Python 用 KShape 对工夫序列进行聚类和肘办法确定最优聚类数 k 可视化
左右滑动查看更多
01
02
03
04
计算规整形式
dtw()函数计算出一个最佳规整形式。
align(a, b)返回以下我的项目。你能够参考 str()函数来理解更多信息。
当初，咱们能够绘制组合。
用双向的办法作图
动静工夫规整后果的绘图：点比拟
显示查问和参考工夫序列以及它们的排列形式，进行可视化查看。
Plot(align)用密度作图
显示叠加了规整门路的累积老本密度。
该图是基于累积老本矩阵的。它将最优门路显示为全局老本密度图中的 “ 山脊 ”。
PlotDensity(align)小结
总而言之, DTW 是一种十分有用的计算序列最小间隔的办法, 不论是在语音序列匹配, 股市交易曲线匹配, 还是 DNA 碱基序列匹配等等场景, 都有其大展身手的中央. 它的最大特点是在匹配时容许工夫上的伸缩, 因而能够更好的在一堆序列汇合中找到最佳匹配的序列.
- Eamonn Keogh, Chotirat Ann Ratanamahatana, Exact indexing of dynamic time warping, Knowledge and Information Systems, 2005.
点击文末 “浏览原文”
获取全文残缺材料。
本文选自《R 语言 DTW(Dynamic Time Warping) 动静工夫规整算法剖析序列数据和可视化》。
点击题目查阅往期内容
ARMA-GARCH-COPULA 模型和金融工夫序列案例
工夫序列剖析：ARIMA GARCH 模型剖析股票价格数据
GJR-GARCH 和 GARCH 稳定率预测普尔指数工夫序列和 Mincer Zarnowitz 回归、DM 测验、JB 测验
【视频】工夫序列剖析：ARIMA-ARCH / GARCH 模型剖析股票价格
工夫序列 GARCH 模型剖析股市稳定率
PYTHON 用 GARCH、离散随机稳定率模型 DSV 模仿预计股票收益工夫序列与蒙特卡洛可视化
极值实践 EVT、POT 超阈值、GARCH 模型剖析股票指数 VaR、条件 CVaR：多元化投资组合预测危险测度剖析
Garch 稳定率预测的区制转移交易策略
金融工夫序列模型 ARIMA 和 GARCH 在股票市场预测利用
工夫序列分析模型：ARIMA-ARCH / GARCH 模型剖析股票价格
R 语言危险价值：ARIMA，GARCH，Delta-normal 法滚动预计 VaR（Value at Risk）和回测剖析股票数据
R 语言 GARCH 建模罕用软件包比拟、拟合规范普尔 SP 500 指数稳定率工夫序列和预测可视化
Python 金融工夫序列模型 ARIMA 和 GARCH 在股票市场预测利用
MATLAB 用 GARCH 模型对股票市场收益率工夫序列稳定的拟合与预测 R 语言 GARCH-DCC 模型和 DCC（MVT）建模预计
Python 用 ARIMA、GARCH 模型预测剖析股票市场收益率工夫序列
R 语言中的工夫序列分析模型：ARIMA-ARCH / GARCH 模型剖析股票价格
R 语言 ARIMA-GARCH 稳定率模型预测股票市场苹果公司日收益率工夫序列
Python 应用 GARCH，EGARCH，GJR-GARCH 模型和蒙特卡洛模仿进行股价预测
R 语言工夫序列 GARCH 模型剖析股市稳定率
R 语言 ARMA-EGARCH 模型、集成预测算法对 SPX 理论稳定率进行预测
matlab 实现 MCMC 的马尔可夫转换 ARMA – GARCH 模型预计
Python 应用 GARCH，EGARCH，GJR-GARCH 模型和蒙特卡洛模仿进行股价预测
应用 R 语言对 S&P500 股票指数进行 ARIMA + GARCH 交易策略
R 语言用多元 ARMA,GARCH ,EWMA, ETS, 随机稳定率 SV 模型对金融工夫序列数据建模
R 语言股票市场指数：ARMA-GARCH 模型和对数收益率数据探索性剖析
R 语言多元 Copula GARCH 模型工夫序列预测
R 语言应用多元 AR-GARCH 模型掂量市场危险
R 语言中的工夫序列分析模型：ARIMA-ARCH / GARCH 模型剖析股票价格
R 语言用 Garch 模型和回归模型对股票价格剖析
GARCH（1,1），MA 以及历史模拟法的 VaR 比拟
matlab 预计 arma garch 条件均值和方差模型 R 语言 POT 超阈值模型和极值实践 EVT 剖析
