algorithm - 时间序列大数据集的聚类方法

Question

大多数聚类算法都需要一个距离矩阵。如果数据的维度较低，则创建距离矩阵很容易。但是要考虑大约 8000 个点的时间序列呢？

for i in range(total_series):
    for j in range(total_series):
        dis[i][j] = distance(series[i],series[j])

很明显，创建此矩阵所需的最短时间为 O(n^2) 阶。现在，如果我们比较两个时间序列的所有 8000 个点，时间复杂度会非常高。我只是在谈论对齐距离(欧几里得)，而不是这里的一些编辑距离。

由于我们有大约 50,000 个时间序列要聚类，因此对于那些 for 循环，O(n^2) 会非常高。我需要通过一些索引或预处理技术在最短的时间内计算距离函数。注意距离函数是要逐点比较的。

有人可以建议一些技术，以便我们可以通过一些预处理在小于 O(时间序列长度)的情况下找到两个时间序列之间的距离吗？或者建议一些无需创建时间复杂度为 O(n^2) 的距离矩阵的聚类方法？

Answer 1

由于欧氏距离的对称性，您可以计算复杂度为 O(n^2/2) 的三角矩阵