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

标签: 运维干货 AIOps KPI 微软 数据 | 发表时间:2017-09-14 23: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》.

AIOps 核心技术和算法要点

- - IT瘾-dev
AIOps已经逐渐兴起,AI算法已较为成熟,使之与运维结合到了一起,下面列出AIOps相关技术和算法要点,有空了再展开写,懂大数据和机器学习的基本都知道各个组件及算法的作用. elasticsearch(支持时序). clickhouse(支持时序). -------------推荐阅读------------.

AIOps 中的四大金刚

- - IT瘾-dev
在传统的自动化运维体系中,重复性运维工作的人力成本和效率问题得到了有效解决. 但在 复杂场景下的故障处理、变更管理、容量管理、服务资源过程中,仍需要人来掌控决策的过程,这阻碍了运维效率的进一步提升. 而AI方法的引入,使得机器能够代替人来做出决策,从而让真正意义上的实现完全自动化成为了可能. 在AIOps的落地实施过程中,最关键的因素还是 人,即AIOps的建设者们.

AIOps 需要翻越的「三座大山」

- - OneAPM 博客
最近 AIOps 火热的就像8月里的盛夏,运维圈子里的每一个人都在讨论着 AIOps,仿佛不聊点AIOps的东西,就透着那么out. 原来做运维产品的一众厂商也像打了鸡血似的,纷纷推出花样繁多的AIOps产品,仿佛AIOps是什么传说中的灵丹妙药,一试就灵、包治百病一样. Gartner 更是推波助澜,颇为大胆的预测到2022年,将有超过40%的企业会采用 AIOps 平台技术.

AIOps在美团的探索与实践——故障发现篇

- - DockOne.io
【编者的话】AIOps,最初的定义是Algorithm IT Operations,是利用运维算法来实现运维的自动化,最终走向无人化运维. 随着技术成熟,逐步确定为Artificial Intelligence for IT Operations——智能运维,将人工智能应用于运维领域,基于已有的运维数据(日志、监控信息、应用信息等),通过机器学习的方式来进一步解决自动化运维无法解决的问题.

在数字化转型中挖掘AIOps的应用潜力

- - 机器之心
「AIOps」是IT的AI增强版,利用AI优化IT运营. 基于IT团队管理开发环境中的数据和信息训练AI,由此重构运营模式. AIOps可以为宕机和IT故障提供敏捷解决方案,从而缓解IT部门面临的问题,并降低解决问题的成本. AIOps平台利用大数据,机器学习和数据分析功能,使用多种数据源和数据收集方法,通过AI信息流监控和自动化服务平台,为决策者提供可行性建议,主动增强IT运营,AIOps的应用优势也正在加速这种技术落地企业.

Elasticsearch对垒8大竞品技术,孰优孰劣? - 运维 - dbaplus社群:围绕Data、Blockchain、AiOps的企业级专业社群。技术大咖、原创干货,每天精品原创文章推送,每周线上技术分享,每月线下技术沙龙。

- -
Elasticsearch当前热度排名很高. 入行Elastic-Stack技术栈很久很久,为了免于知识匮乏眼光局限,有必要到外面的世界看看,丰富自己的世界观. 本篇内容从Elastic的竞争产品角度分析探讨. 哪些应用场景下使用Elasticsearch最佳. 哪些应用场景下不使用Elasticsearch最好.

Redis高可用详解:持久化技术及方案选择 - Redis - dbaplus社群:围绕Data、Blockchain、AiOps的企业级专业社群。技术大咖、原创干货,每天精品原创文章推送,每周线上技术分享,每月线下技术沙龙。

- -
本文将先说明上述几种技术分别解决了Redis高可用的什么问题,然后详细介绍Redis的持久化技术,主要是RDB和AOF两种持久化方案. 在介绍RDB和AOF方案时,不仅介绍其作用及操作方法,同时还会介绍持久化实现的一些原理细节及需要注意的问题. 最后,介绍在实际使用中持久化方案的选择以及经常遇到的问题等内容.

ES既是搜索引擎又是数据库?真的有那么全能吗? - 更多 - dbaplus社群:围绕Data、Blockchain、AiOps的企业级专业社群。技术大咖、原创干货,每天精品原创文章推送,每周线上技术分享,每月线下技术沙龙。

- -
经常遇到很多朋友询问,如何学好Elasticsearch. 这个问题本质上很不好回答,但我一直又很想好好回答,所以本文就以我个人的经验视角,跟大家探讨一下如何正确的拥抱Elasticsearch. Elasticsearch是什么,不同的人有不同的理解定位,之前写过Elasticsearch对比其它数据产品的文章.

超3亿活跃用户的多活架构,数据同步与流量调度怎么做? - 架构 - dbaplus社群:围绕Data、Blockchain、AiOps的企业级专业社群。技术大咖、原创干货,每天精品原创文章推送,每周线上技术分享,每月线下技术沙龙。

- -
1、OPPO多活架构原则   . 多活成本比较高的,双活是两倍,三活可能成本会低一些,但三活的难度更大. 因此没有办法对所有业务进行多活,只能对主线做多活. 举个例子,系统有个充值的功能,充值功能本身是强一致的,完全不能允许任何的延迟或者是副本的读. 但是多活切换之后,只有少数用户在切换的前几分钟有充值的,这部分用户余额可能没有通过过去,只需要对这部分用户进行服务降级,其他绝大多数用户是可以使用完整的服务的.