提出新型曲线距离度量k-DTW，更鲁棒且学习效率更高。
Improved Learning via k-DTW: A Novel Dissimilarity Measure for Curves
- 基于第k大匹配距离的参数搜索，构造新距离度量。
- 样本量可比DTW减少，复杂度降低约√m倍。
- 适合曲线聚类、分类等需要抗噪的场景。
本文提出k-动态时间规整（k-DTW），一种针对多边形曲线的新距离度量。相比传统标准动态时间规整（DTW）和弗雷歇距离，k-DTW具有更强的度量性质且对异常值更鲁棒。我们给出了k-DTW的精确算法与(1+ε)近似算法，通过参数搜索求解第k大匹配距离。首次建立了适用于曲线的无维度学习界，并证明：在学习曲线中位数问题中，所需样本量小于DTW，其中依赖曲线复杂度m的因子被替换为k；且在相关的Rademacher与高斯复杂度上，k-DTW的界严格优于DTW，差距达˜Ω(√m)阶，当k≪m时尤为显著。实验验证了其在聚类与最近邻分类中的优势。
原文摘要 · Abstract (English)
This paper introduces $k$-Dynamic Time Warping ($k$-DTW), a novel dissimilarity measure for polygonal curves. $k$-DTW has stronger metric properties than Dynamic Time Warping (DTW) and is more robust to outliers than the Fréchet distance, which are the two gold standards of dissimilarity measures for polygonal curves. We show interesting properties of $k$-DTW and give an exact algorithm as well as a $(1+\varepsilon)$-approximation algorithm for $k$-DTW by a parametric search for the $k$-th largest matched distance. We prove the first dimension-free learning bounds for curves and further learning theoretic results. $k$-DTW not only admits smaller sample size than DTW for the problem of learning the median of curves, where some factors depending on the curves' complexity $m$ are replaced by $k$, but we also show a surprising separation on the associated Rademacher and Gaussian complexities: $k$-DTW admits strictly smaller bounds than DTW, by a factor $\tildeΩ(\sqrt{m})$ when $k\ll m$. We complement our theoretical findings with an experimental illustration of the benefits of using $k$-DTW for clustering and nearest neighbor classification.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。