微软亚研院的AIOps底层算法: KPI快速聚类

标签: 运维干货 AIOps KPI 微软 数据 | 发表时间:2017-09-14 15:02 | 作者:小码哥
出处:http://www.yunweipai.com

导读

智能运维中存在海量时序数据(KPI)需要监控、检测异常、关联, 而AIOps的一个底层算法就是把大规模时序数据快速准确地聚类成有限的若干类别,从而大大降低后续数据分析与挖掘工作的开销。 其应用场景包括自动适配异常检测算法、辅助标注、辅助构建故障传播链等。 本文介绍的案例是由微软亚洲研究院发表在数据库领域顶级会议VLDB 2015的文章《 Yading: Fast Clustering of Large-Scale Time Series Data》。

简介

在大数据时代,快速、大规模的分析技术的重要性日益凸显,人们利用这些技术完成实时和交互性任务中的数据分析工作。运维中常见的KPI数据是一种时间序列数据,它具有数据实例多、维度高的特点。为了降低数据分析工作的开销,提高分析效率,人们希望将海量的时序数据曲线分为若干类别,从而减少需要考察的曲线数目。因此,如何对大规模的时间序列数据进行快速、准确的聚类是一个关键性问题。

本文中,作者设计了一套端到端的时序数据聚类算法Yading,实现了对大规模时间序列数据的高效、准确、自动化聚类。为验证算法效果,作者在公开数据集上将Yading与若干传统时序数据聚类算法进行对比,并在微软的实际工业数据上对算法进行了测试,证明了Yading的高效性和分类准确性。

时序数据聚类的挑战

  • 时序数据数量大、维度高。运维中的时序数据集通常具有大量实例(如数百万个),每个实例具有较高维度(如数千维),难以使用传统的聚类方法进行快速聚类。
  • 时序数据实例间的相似性难以准确刻画。不同于简单的数值型、类别型数据,时间序列数据上通常存在着相位扰动和随机噪声,使得对时序数据实例之间的相似性刻画较为困难。不恰当的相似性度量会大大降低聚类的准确性。
  • 聚类算法参数难以确定。许多聚类算法的效果和参数的选取有密切关系。面对大规模的时序数据,难以人工选取合适的参数。需要设计更智能的参数选择方法。

设计思想

为应对上述挑战,本文设计了一套端到端的时序数据聚类算法Yading,分以下三步实现大规模时序数据的快速、准确聚类,算法框架如下图所示。

  1. 输入数据集采样。对大量的时序数据进行随机采样,并使用逐段聚集平均(PAA)算法缩减每条时序数据实例的维度。用采样后的数据集作为聚类算法的输入。

  2. 在采样后的数据集上进行时序数据聚类。使用L1距离作为时序数据曲线间的相似性度量。在基于密度的聚类算法DBSCAN的基础上,设计出多密度的聚类算法Multi-DBSCAN,并使算法能够自动决定参数。

  3. 对大量数据采用分派(assignment)策略进行分类。对于采样中未被选择的大量时序数据曲线,采用分派策略将其分到与其L1距离最近的已聚类曲线所属的聚类簇中。同时建立了有序邻居图(Sorted Neighbor Graph, SNG)辅助计算时序数据实例之间的距离,提高分派算法的计算效率。

数据

1、输入数据集采样

大规模的时序数据集中通常含有数以万计的时序数据实例,每个实例上含有大量的数据点,直接对整个数据集进行聚类将带来巨大的计算开销。因此,本文通过随机采样和维度缩减的手段降低需要考察的实例数目和维度,将采样后的数据集作为聚类模块的输入,降低计算开销。

由于不需要对输入数据的分布作任何假设, 随机采样(random sampling)是一种减少数据实例个数的有效手段。采样过程中需要遵循两个原则:(1)每个类别的数据均在采样集中出现至少m次。(2)采样集中各类别数据所占比例与原数据集中的比例偏差不超过给定阈值ε。基于上述原则,作者采用数学方法推导出采样数据集大小的上界和下界,对原始数据集进行随机采样。

对于每个时序数据实例,使用 逐段聚集平均(Piecewise Aggregate Approximation,PAA)进行维度缩减。具体的,对于一条长度为D的时序数据,PAA将其划分为d个帧(d<D),将每个帧用一个值(例如该帧上数据点的均值)表示,从而将时序数据的长度从D减小为d,达到降维的目的。

通过上述两项操作,能够从规模为N*D的原始数据集中获得规模为s*d的采样数据集(s≤N, d≤D),且采样集保持原数据集的分布(underlying distribution)不变。用采样集作为聚类模块的输入,大大降低了计算开销。

2、时序数据聚类 以采样后的数据集作为输入,文中使用L1距离作为时序数据实例间的相似性度量,采用多密度的DBSCAN(Multi-DBSCAN)算法进行聚类。

点(x1,y1)与点(x2,y2)的L1距离可表示为:L = |x1-x2|+|y1-y2|。L1 距离计算复杂度低,且对于脉冲噪声具有一定的鲁棒性,适合作为处理大规模时序数据的相似性度量。

时序数据集中的数据曲线模式多种多样,每个类别中含有的曲线数量也有较大差异。面对这种情况,基于密度的聚类方法是一种很好的选择。一般地,如果时序曲线a和b相似,b和c相似,则a、b、c很可能属于同一类别。基于密度的聚类算法正是根据这一思想将相似曲线逐步加入同一聚类簇中,从而能够找出任意形状的聚类簇。特别地,真实的时序数据模式较为复杂,在一个数据集中可能存在多种密度的聚类簇(如下图所示)。因此本文中将基于密度的DBSCAN算法改进为多密度的Multi-DBSCAN,提升聚类准确性。

此外, 密度估计(density estimation)是基于密度的聚类算法的核心,已有工作中通常通过人工选择或使用一些计算开销较大的算法得到合适的密度阈值。本文中,作者设计了一种高效算法对密度进行自动估计,并使用数学方法证明了其合理性。具体的,该算法计算输入数据集中的每个数据对象到其k邻近对象之间的距离k-dis,将k-dis值按照降序排列得到k-dis曲线,曲线上的最平坦点即为候选密度值(如下图所示)。对于输入的时序数据集,该算法能够自动检测出不同聚类簇的密度,分别以每个候选密度值作为参数使用DBSCAN算法进行聚类,即可将数据集划分为若干聚类簇,同时识别出与大多数时序曲线均不属于同一类别的异常曲线(outliers)。 3、分派策略

在对采样集进行聚类后,使用 分派(assignment)策略对大量未分类时序数据曲线进行快速分类。具体的,对于一个未分类实例,找出与它相似性距离最近的已分类实例A。若二者的距离小于A所在聚类簇的密度半径,则将该实例划分至与A相同的类别中。否则,认为该实例是一个异常(outlier)。为提高计算效率,本文中还建立了有序邻居图,利用剪枝的方法加速寻找最邻近实例的过程,实现对大量时序数据的快速分类。

文中使用标准化互信息(Normalized Mutual Information, NMI)作为指标对聚类算法的准确性进行评价。作者分别在15个时序数据集上将本文提出的算法YADING与三种常用的聚类算法DECLUE2.0、DBSCAN、CLARANS进行对比,在不同规模数据集上的计算时间及所有数据集上的平均NMI如下图所示。可以看出,YADING在计算效率和聚类准确性方面均领先于几种常用算法。

YADING算法已被微软用于与实际业务相关的时序数据分析中。对于46000多条服务器CPU利用率及内存利用率时序数据,YADING算法仅用时4.5秒就完成了聚类工作(几种主要类别如下图所示),表现出极高的实际应用价值。

总结

本文介绍了一套快速、准确的时序数据聚类算法,用于对大规模时序数据进行快速分类,是时序数据挖掘与分析工作的重要手段。通过随机采样和维度缩减获得规模较小的采样集,从而大大减小聚类算法需要考察的数据量,降低计算开销。之后设计了一套基于L1 距离和Multi-DBSCAN算法的时序数据聚类方案,并能够自动进行密度估计,具有较高的鲁棒性。对于大量的未分类时序数据,根据聚类结果采用分派策略进行快速分类。最后,文中分别采用理论推导与真实数据验证的方式证明了该算法在解决大规模时序数据聚类问题上的高效性和准确性,具有很好的实用价值。

此外,在NetMan实验室今年十月份推出的智能运维挑战赛中,将提供来自互联网公司的公开脱敏数据集,供大家尝试自己的KPI聚类算法。欢迎感兴趣的朋友踊跃参与。

由于长度限制,本文没有介绍细节,特此附上原文链接,点击 阅读原文获取。

相关 [微软 aiops 算法] 推荐:

微软亚研院的AIOps底层算法: KPI快速聚类

- - 运维派
智能运维中存在海量时序数据(KPI)需要监控、检测异常、关联, 而AIOps的一个底层算法就是把大规模时序数据快速准确地聚类成有限的若干类别,从而大大降低后续数据分析与挖掘工作的开销.  其应用场景包括自动适配异常检测算法、辅助标注、辅助构建故障传播链等.  本文介绍的案例是由微软亚洲研究院发表在数据库领域顶级会议VLDB 2015的文章《 Yading: Fast Clustering of Large-Scale Time Series Data》.

缓存算法

- lostsnow - 小彰
没有人能说清哪种缓存算法由于其他的缓存算法. (以下的几种缓存算法,有的我也理解不好,如果感兴趣,你可以Google一下  ). 大家好,我是 LFU,我会计算为每个缓存对象计算他们被使用的频率. 我是LRU缓存算法,我把最近最少使用的缓存对象给踢走. 我总是需要去了解在什么时候,用了哪个缓存对象.

BFPRT算法

- zii - 小彰
BFPRT算法的作者是5位真正的大牛(Blum 、 Floyd 、 Pratt 、 Rivest 、 Tarjan),该算法入选了在StackExchange上进行的当今世界十大经典算法,而算法的简单和巧妙颇有我们需要借鉴学习之处. BFPRT解决的问题十分经典,即从某n个元素的序列中选出第k大(第k小)的元素,通过巧妙的分析,BFPRT可以保证在最坏情况下仍为线性时间复杂度.

贪心算法

- Shan - 博客园-首页原创精华区
顾名思义,贪心算法总是作出在当前看来最好的选择. 也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择. 当然,希望贪心算法得到的最终结果也是整体最优的. 虽然贪心算法不能对所有问题都得到整体最优解,但对许多问题它能产生整体最优解. 如单源最短路经问题,最小生成树问题等.

缓存算法

- 成 - FeedzShare
来自: 小彰 - FeedzShare  . 发布时间:2011年09月25日,  已有 2 人推荐. 没有人能说清哪种缓存算法由于其他的缓存算法. (以下的几种缓存算法,有的我也理解不好,如果感兴趣,你可以Google一下  ). 大家好,我是 LFU,我会计算为每个缓存对象计算他们被使用的频率.

K-Means 算法

- - 酷壳 - CoolShell.cn
最近在学习一些数据挖掘的算法,看到了这个算法,也许这个算法对你来说很简单,但对我来说,我是一个初学者,我在网上翻看了很多资料,发现中文社区没有把这个问题讲得很全面很清楚的文章,所以,把我的学习笔记记录下来,分享给大家. k-Means 算法是一种  cluster analysis 的算法,其主要是来计算数据聚集的算法,主要通过不断地取离种子点最近均值的算法.

查找算法:

- - CSDN博客推荐文章
从数组的第一个元素开始查找,并将其与查找值比较,如果相等则停止,否则继续下一个元素查找,直到找到匹配值. 注意:要求被查找的数组中的元素是无序的、随机的. 比如,对一个整型数组的线性查找代码:. // 遍历整个数组,并分别将每个遍历元素与查找值对比. 要查找的值在数组的第一个位置. 也就是说只需比较一次就可达到目的,因此最佳情况的大O表达式为:O(1).

排序算法

- - 互联网 - ITeye博客
排序算法有很多,所以在特定情景中使用哪一种算法很重要. 为了选择合适的算法,可以按照建议的顺序考虑以下标准: .     对于数据量较小的情形,(1)(2)差别不大,主要考虑(3);而对于数据量大的,(1)为首要.  一、冒泡(Bubble)排序——相邻交换 .  二、选择排序——每次最小/大排在相应的位置 .

联接算法

- - CSDN博客数据库推荐文章
本文摘自《锋利的SQL》: http://item.jd.com/10380652.html. 在Microsoft SQLServer Management Studio中执行查询时,如果选定工具栏中的 按钮,可以看到为查询生成的执行计划. 执行计划以图形方式显示了SQL Server查询优化器选择的数据检索方法,如表扫描、排序、哈希匹配等.

微软迷踪

- 晋安渔夫 - cnBeta.COM
上周一,即微软CEO史蒂夫・鲍尔默来华访问前一天,微软(Microsoft)市值15年来首次被IBM超越. 这是继去年被苹果公司挤下IT市值王座之后,微软排名再度滑落. 但这并未影响鲍尔默来华展示微软对于移动互联网的野心,他在演讲中透露,Windows Phone未来几个月内将进入中国.