如何为时间序列数据优化K-均值聚类速度？

Tech Neo技巧沙龙 | 11月25号，九州云/ZStack与您一路商量云时代收集界线治理实践

时光序列数据(Time Series Data)是按时光排序的数据，利率、汇率和股价等都是时光序列数据。时光序列数据的时光距离可所以分和秒(如高频金融数据)，也可所以日、周、月、季度、年以及甚至更大年夜的时光单位。数据分析解决筹划供给商 New Relic 在其博客上介绍了为时光序列数据优化 K-均值聚类速度的办法。笔者对本文进行了编译介绍。

在 New Relic，我们每分钟都邑收集到 13.7 亿个数据点。我们为我们的客户收集、分析和展示的很大年夜一部分数据都是时光序列数据。为了创建应用与其它实体(比如办事器和容器)之间的关系，以便打造 New Relic Radar 如许的新型智能产品，我们正在赓续摸索更快更有效的对时光序列数据分组的办法。鉴于我们所收集的数据的量是如斯巨大年夜，更快的聚类时光至关重要。

在接下来的测试中，我们起首生成 10000 个随机时光序列数据，每个数据的样本长度为 500。然后我们向随机长度的┞俘弦波添加噪声。尽管这一类数据对 k-均值聚类办法而言并不睬想，但它足以完成未竽暌古化的实现。

加快 k-均值聚类

k-均值聚类是一种风行的分组数据的办法。k-均值办法的基来源基本理涉及到肯定每个数据点之间的距离并将它们分构成有意义的聚类。我们平日应用平面上的二维数据来演示这个过程。以跨越二维的方法聚类当然是可行的，但可视化这种数据的过程会变得更为复杂。比如，下图给出了 k-均值聚类在两个随便率性维度上经由几回迭代的收敛情况：

若何为时光序列数据优化K-均值聚类速度？

不幸的是，这种办法并不克不及很好地用于时光序列数据，因为它们平日是随时光变更的一维数据。然则，我们仍然可以应用一些不合的函数来计算两个时光序列数据之间的距离因子(distance factor)。在这些案例中，我们可以应用均方误差(MSE)来摸索不合的 k-均值实现。在测试这些实现的过程中，我们留意到很多实现的表示程度都有严重的问题，但我们仍然可以演示加快 k-均值聚类的可能办法，在某些案例中甚至能实现一个数量级的速度晋升。

聚类这些数据用去了接近 20 分钟。这不是很糟糕，但肯定算不上好。为了鄙人一?实现中达到更快的速度，我们决定去掉落尽可能多的 for 轮回。

这里我们将应用 Python 的 NumPy 软件包。如不雅你决定上手跟着演习，你可以直接将这些代码复制和粘贴到 Jupyter Notebook 中。让我们大年夜导入软件包开端吧，这是我们一向要用到的器械：

import time 
import numpy as np 
import matplotlib.pyplot as plt 
%matplotlib inline

n = 10000 
ts_len = 500 
phases = np.array(np.random.randint(0, 50, [n, 2])) 
pure = np.sin([np.linspace(-np.pi * x[0], -np.pi * x[1], ts_len) for x in phases]) 
noise = np.array([np.random.normal(0, 1, ts_len) for x in range(n)]) 
signals = pure * noise 
# Normalize everything between 0 and 1 
signals += np.abs(np.min(signals)) 
signals /= np.max(signals) 
plt.plot(signals[0])

第一个实现

让我们大年夜最根本和最直接的实现开端吧。euclid_dist 可认为距离函数实现一个简单的 MSE 估计器，k_means 可以实现根本的 k-均值算法。我们大年夜我们的初始数据集中选择了 num_clust 随机时光序列数据作为质心(代表每个聚类的中间)。在 num_iter 次迭代的过程中，我们会持续赓续地移动质心，同时最小化这些质心与其它时光序列数据之间的距离。

def euclid_dist(t1, t2): 
        return np.sqrt(((t1-t2)**2).sum()) 
def k_means(data, num_clust, num_iter): 
   centroids = signals[np.random.randint(0, signals.shape[0], num_clust)] 	
			 1/6    1 2 3 4 5 6 下一页 尾页	
			

　　推荐阅读
　　Git的4个阶段的撤销更改命令分析
            Tech Neo技巧沙龙 | 11月25号，九州云/ZStack与您一路商量云时代收集界线治理实践
            固然 git 出生距今已有 12 年之久，网上各类关于 git  的介绍文┞仿数不堪数，然则依然有很多人(包含我本>>>详细阅读


本文标题：如何为时间序列数据优化K-均值聚类速度？
地址：http://www.17bianji.com/lsqh/38787.html
 1/2    1