问时间序列海量数据集的聚类方法
EN

Stack Overflow用户

提问于 2017-04-16 21:49:14

回答 1查看 110关注 0票数 2

大多数聚类算法都需要一个距离矩阵。如果数据的维数较低，则很容易创建距离矩阵。但是，如果一个时间序列有大约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个时间序列要聚类，O(n^2)对于那些循环来说是非常高的。我需要通过一些索引或预处理技术在最短的时间内计算距离函数。请注意，距离函数将进行逐点比较。

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

发布于 2018-01-31 22:25:39

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

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/43437934

复制

相似问题

问时间序列海量数据集的聚类方法EN