面向长序列数据分类的变长子序列最优传输模型

Variable-Length Subsequence Optimal Transport Model for Long Sequence Data Classification

摘要: 序列数据分类是数据挖掘领域的重要任务，其性能高度依赖于序列间相似性度量的有效性。动态时间规整及其变体作为当前广泛采用的相似性度量方法，在长序列数据分类中存在计算复杂度高、病态对齐、忽略局部结构特征以及过度最大化相似性等问题。为此，本文提出一种面向长序列数据分类的变长子序列最优传输模型。首先，首次将感知重要点与最优传输理论结合，构造变长子序列，以子序列匹配替代传统逐点匹配，显著降低计算复杂度并缓解病态对齐。其次，为加强序列局部结构特征，引入复杂度修正因子构建代价矩阵。再次，设计位置惩罚正则项，以抑制位置过远子序列的不合理匹配，并缓解了过度最大化相似性问题。最后，采用熵正则化最优传输框架，通过Sinkhorn-Knopp快速迭代算法实现高效求解。在20个UCR数据集上的实验结果表明，所提模型在分类准确率和计算效率方面均显著优于主流对比方法，验证了其在长序列数据分类任务中的有效性与可行性。

Abstract: Sequence data classification is a fundamental task in data mining, and its performance heavily depends on the effectiveness of similarity measures between sequences. Dynamic Time Warping (DTW) and its variants, as widely adopted similarity measures, suffer from high computational complexity, pathological alignments, neglect of local structural characteristics, and excessive similarity amplification when applied to long sequence classification. To address these issues, this paper proposes a variable-length subsequence optimal transport model for long sequence data classification. First, by integrating Perceptually Important Points (PIPs) with optimal transport theory, we construct variable-length subsequences to replace traditional point-wise matching with subsequence-level matching, significantly reducing computational complexity while mitigating pathological alignments. Second, a complexity correction factor is introduced to construct a cost matrix that captures both numerical differences and local structural characteristics between subsequences. Third, a position penalty regularization term is designed to suppress unreasonable matches between subsequences that are far apart in temporal position, effectively alleviating excessive similarity amplification. Finally, the model is formulated within an entropy-regularized optimal transport framework and efficiently solved using the Sinkhorn-Knopp iterative algorithm. Experimental results on 20 UCR datasets demonstrate that the proposed model significantly outperforms mainstream methods in both classification accuracy and computational efficiency, validating its effectiveness and feasibility for long sequence data classification tasks.