最长公共子序列¶
最长公共子序列（LCSS）[1] 是时间序列之间的一种相似性度量。
让我们考虑两个时间序列 \(x = (x_0, \dots, x_{n-1})\) 和
\(y = (y_0, \dots, y_{m-1})\)，它们的长度分别为 \(n\) 和
\(m\)。
这里，假设所有元素 \(x_i\) 和 \(y_j\) 都位于相同的
\(d\) 维空间中。
在 tslearn 中，这样的时间序列将表示为形状分别为
(n, d) 和 (m, d) 的数组，并且可以使用以下代码计算 LCSS：
from tslearn.metrics import lcss, lcss_path
lcss_score = lcss(x, y)
# Or, if the path is also an important information:
path, lcss_score = lcss_path(x, y)
这是在调用
tslearn.clustering.TimeSeriesKMeans 时使用的算法，其中
metric="lcss"。
问题¶
给定整数 :math epsilon 和实数 :math delta，\(x\) 和 \(y\) 之间的相似度 S 公式如下：
常数 \(\delta\) 控制我们可以在时间上走多远，以便将一个时间序列中的给定点与另一个时间序列中的点匹配。常数 \(\epsilon\) 是匹配阈值。
在这里，路径可以被视为时间序列中欧几里得距离不超过给定阈值的部分，即它们是接近/相似的。
算法解决方案¶
存在一个\(O(n^2)\)算法来计算这个问题的解决方案（为了简化，提供了从1开始索引的时间序列的伪代码）：
def lcss(x, y):
# Initialization
for i = 0..n
C[i, 0] = 0
for j = 0..m
C[0, j] = 0
# Main loop
for i = 1..n
for j = 1..m
if dist(x_i, x_j) <= epsilon and abs(j - i) <= delta:
C[i, j] = C[i-1, j-1] + 1
else:
C[i, j] = max(C[i, j-1], C[i-1, j])
return C[n, m]
使用不同的地面度量¶
默认情况下，tslearn 使用平方欧几里得距离作为基础度量
（即上述问题中的 \(dist()\) 是
欧几里得距离）。如果想使用其他基础度量，代码
将会是：
from tslearn.metrics import lcss_path_from_metric
path, cost = lcss_path_from_metric(x, y, metric=compatible_metric)
属性¶
最长公共子序列具有以下属性：
\(\forall x, y, LCSS(x, y) \geq 0\)
\(\forall x, y, LCSS(x, y) = LCSS(y, x)\)
\(\forall x, LCSS(x, x) = 0\)
然而，从数学上讲，LCSS 不是一个有效的度量，因为它不满足三角不等式。
附加约束¶
可以为可接受路径的集合设置额外的约束。 这些约束通常包括强制路径靠近对角线。
首先，Sakoe-Chiba带由一个半径\(r\)（要考虑的对角线元素数量，有时也称为扭曲窗口大小）参数化，如下图所示：
\(n = m = 10, r = 3\). 对角线用灰色标记以提高可读性。¶
相应的代码如下：
from tslearn.metrics import lcss
cost = lcss(x, y, global_constraint="sakoe_chiba", sakoe_chiba_radius=3)
其次，Itakura平行四边形为对齐路径设置了最大斜率\(s\)，这导致了一个平行四边形形状的约束：
\(n = m = 10, s = 2\). 对角线用灰色标记以提高可读性。¶
相应的代码如下：
from tslearn.metrics import lcss
cost = lcss(x, y, global_constraint="itakura", itakura_max_slope=2.)
