多维智能下钻分析--Adtributor算法研究

近年来，AIOPs智能运维是运维领域的一大研究热点。2014年，微软研究院提出了一种基于Adtributor算法的多维时间序列异常根因分析方法。同时，在AIOps 技术研讨交流会暨2019国际 AIOps 挑战赛中，获奖的前五支团队无一例外地引用了该算法。本文详细介绍Adtributor算法核心思想和哈勃多维分析的工作流程，相信有助于大家熟悉AIOps的机器学习算法。

目录

一、背景相关

1. 背景介绍
2. 数据/输入
3. 输出/难点

二、Adtributor算法研究

1. Adtributor整体设计思路
2. Adtributor算法细节阐述
3. Adtributor结果评估
4. Adtributor算法改进

三、哈勃多维分析

1. Adtributor在哈勃多维分析中的应用
2. 哈勃多维分析特色
3. 哈勃多维分析率值KPI转换策略
4. 哈勃多维分析时间点说明
5. 哈勃多维分析结果展示

四、总结

一、背景相关

1. 背景介绍

在互联网Web服务的智能运维(AIOps)过程中，首要需求通常是对监控的各种关键性能指标(KPI)进行实时异常检测，然后需要对检测出的异常指标进行异常定位和根因分析(RCA, root cause analysis)，以便尽快做进一步的修复止损等操作。

通常一个KPI的异常是多个维度异常共同导致的结果，反过来说KPI异常会反映在各个维度下面。例如对于网页访问量(Total_PV）涉及多个维度：用户位置、网络运营商、数据中心等；各维度对应一系列可能情况（或者元素），用户位置：北京，上海，广州等；网络运营商：移动，联通，电信等；数据中心：DC1，DC2等。当Total_PV发生异常时，最可能的异常原因可以表示为不同维度的元素集合，如｛北京、上海｝，或｛北京移动，广州电信，DC1｝等。

指标和维度的示意如下图所示，其中 A, B, C 代表不同维度，a1, b1, a1b1 表示对应维度下的元素指标。对于多维KPI，异常定位和根因分析的目的就是在检测到KPI异常之后，从所有维度中挖掘出最可能是异常发生根本原因的元素，因此根因分析也叫做智能下钻。

微软研究院于2014年发表论文《Adtributor: Revenue Debugging in Advertising Systems》，提出一种Adtributor方法用于对多维时间序列的异常根因分析，该方法可应用于监控系统运维、广告业务异常检测、网络流量监测与异常分析等多种场景。

2. 数据/输入：

多维时间序列数据，包含：时间戳TimeStamp、指标KPI、维度D、元素E。数据表结构如下：

从统计分析的角度来看， KPI可以分为两类：

• 量值KPI，具有可加性(additive)，如成功数、访问总量；
• 率值KPI，量值KPI推导得到，亦称为推导性(derived, ratio)KPI，如点击率、成功率；

举例说明：例如用户位置维度下，北京、上海和广州的访问成功量分别为70、90和10，访问总量均为100，成功率分别为70%、90%、100%；三者的访问成功量相加得到用户位置维度的访问成功量为260，但三者的成功率不能直接相加得到用户位置维度的成功率为260%。因此对于量值KPI和率值KPI需要采用不同的方法进行根因分析。

3. 输出/难点：

能够准确反映KPI发生异常根本原因的维度-元素集合即异常根因。异常根因需要尽可能满足多个条件，这也是根因分析的难点所在：

1. 对于每一个维度，元素集合能够尽可能地解释KPI异常波动；
2. 对于每一个维度，元素集合符合奥卡姆剃刀原则、形式上尽可能简洁；
3. 在所有维度中，找出最意外的、真实情况与期望值相差最大的维度和元素。

二、Adtributor算法研究

1. Adtributor整体设计思路

Adtributor多维根因分析流程如图所示，主要包括四个步骤：

步骤1数据收集。收集KPI的多维时间序列数据，对于缺失值、死值等进行初步预处理，提升数据质量。

步骤2异常检测。采用ARMA时间序列模型对KPI进行实时预测，将预测值F和真实值A对比，判断KPI是否发生异常；预测值F和真实值A将用于Adtributor根因分析。

步骤3根因分析。Adtributor对异常KPI的所有维度和元素计算EP值和S值，并与TEP、TEEP阈值比对分析，从而筛选和定位出异常根因。

算法主要思路如图所示

1. 对于异常KPI，计算所有维度下所有元素的真实值和预测值的差异，即S值(Surprise, 意外性)，将每一维度下的元素依据S值大小降序排列； S值的设定反映了难点3——找出最意外的元素。
2. 对于每一维度，从上到下依次对排序后的所有元素计算其变化在KPI变化总量中的占比，即元素对于KPI异常的解释能力EP值(Explanatory power)；当EP值大于TEEP阈值(1%)时，认为是可疑元素，加入该维度下的根因集合。

随着维度和元素越多，全局贪婪方式的根因分析时间成本呈指数型增加。TEEP阈值的设定反映了难点2的奥卡姆剃刀原则——不再考虑解释能力差/变化占比小的元素，使结果尽可能简洁。所以一般TEEP设置比较小，比如认为占比小于1%的元素影响太小可以不予考虑。

1. 对于每一维度，根因集合中的元素EP之和大于TEP阈值(90%)时，则认为根因集合已经能够很大程度上解释/反映KPI异常波动，不再考虑剩下解释能力小的元素了。 TEP阈值的设定反映了难点1——尽可能地解释KPI异常波动；TEP阈值一般设定在[0, 1]之间，越大表示希望根因集合能够越大程度上解释KPI异常原因。
2. 对于每一维度，计算所有元素S值总和作为维度的S值，并将根因集合根据维度S值降序排列。 S值的设定反映了难点3——找出最意外的维度。

核心思想：将多维根因分析问题分解为多个单维根因分析问题，采用EP值和S值定位出每个维度下的异常元素集合，最后根据每个维度总的S值大小汇总输出根因集合。

步骤4结果输出。当维度不多时，可以输出所有维度的分析情况；当维度数量较多时，可输出排名靠前的TOP N异常根因。维度和元素过多，对于影响较小的筛查和修复意义不大，反而会增加运维工程师负担；过少，则容易遗漏重要的异常根因。

2. Adtributor算法细节阐述

对于Adtributor算法中提出的关键名词EP值和S值，以下重点介绍。

2.1 EP值—量值KPI

思想：对于每一维度，如果元素的波动变化在异常KPI的波动变化中的占比越大，则认为元素越能解释KPI异常的发生。EP值(Explanatory power, 解释能力)用于衡量元素对异常的解释能力。EP值计算公式如下：

式中，A为故障真实值，F为ARMA时间序列模型正常预测值，下标i为维度、j为元素、m为异常指标。

EP值可以为正、为负、大于100%，但是每个维度下的所有元素EP之和必须为100%。EP为正表示可能是异常根因，为负表示不是异常根因，大于100%表示与KPI异常有非常明显的正相关关系。分析量值KPI时，根据公式可知某一元素的波动占比可能超过100%，此时TEP阈值可能设定大于1。

2.2 S值—量值KPI

思想：如果KPI在某一维度下的真实值和预测值相差越大，则越有可能是异常根因。

方法：KPI先验概率和后验概率的相似度可以采用相对熵(relative entropy)来衡量，进而判断维度是否具有意外性，相对熵也称KL散度(Kullback-Leibler divergence)。相比于KL散度，JSD散度(Jensen-Shannnon divergence)作为KL散度的一种变形，其对称性好、对于零值具有适应性、对相似度判别更加准确，因此采用JSD散度。基于JSD散度，论文提出S值(Surprise, 意外性)公式如下：

其中，预测概率或先验概率计算公式为

真实概率或后验概率计算公式为

维度的S值为维度下所有元素的S值之和，即

2.3 EP值—率值KPI

前面提到，率值KPI的计算方式不同于量值KPI，因为率值KPI不能像量值KPI一样在不同维度和元素上进行加减操作，率值KPI的波动变化也不能通过加减反映在各个维度和元素上。此时，偏导数和有限差分便派上用场了。衡量对于这种形式函数的波动变化情况，偏导数计算公式如下：

在离散问题中，根据有限差分理论其偏导数可等价简化为

因此，本文推导出的EP值计算公式如下：

2.4 S值—率值KPI

根据相对熵理论，对于需要首先计算f(.)和g(.)函数的联合概率分布，然后计算联合概率分布函数的相对熵，计算十分复杂。论文作出近似假设，认为f和g函数之间相互独立，则的联合概率分布相对熵就是f(.)和g(.)的概率分布函数相对熵之和。因此，率值KPI的S值等于组成率值KPI定义公式的分子KPI和分母KPI的S值之和。省略下标ij，S值计算公式如下

S = sum(Sf, Sg)

3. Adtributor结果评估

论文收集某著名国际企业2013年广告系统的数据，针对包含量值和率值等12个指标进行异常检测和根因分析，对于多维分析结果人工校验，分析Adtributor算法的有效性。

在根因分析的核心衡量标准——准确率accuracy上，实验证明Adtributor准确率可达95.3%，与具有丰富运维经验的领域专家水平接近，远高于Strawman算法的20%。在运行速度上，论文实验记录对于相同异常指标，人工排查根因平均用时在73分钟左右，而Adtributor算法根因分析平均为3分钟左右，因此Adtributor算法能够在指数级上提升多维根因分析的效率。

值得注意的是，指标之间不一定是彼此独立的，某一指标的异常可能与其他指标的变化相关联。构建指标之间的关系依赖图，当某一指标发生异常告警时，便可对其关联指标执行根因分析，帮助运维工程师更全面地定位故障根因。

输出结果说明：

1. 图形可视化展示不同指标之间的依赖关系
2. 对于给定的指标和维度，给出排名前三的元素即故障根因，
3. 右侧曲线展示指标的历史数据变化趋势，按照维度聚合并在右侧历史曲线上展示

4. Adtributor算法改进

实际部署中针对业务发现的问题，论文提出对算法的两点改进：

1. 不稳定维度：对于某些指标，其下某一维度本身不稳定波动变化频繁，尽管不是指标异常根因但可能被误认为异常根因。因此，对于这类指标的预测模型可以增加中异常发生前短时间内较大波动指标数据的权重。
2. 可视化加强：少量指标之间的关系依赖图容易构建，数以百计的指标之间的依赖关系可视化较难实现。一个可行的策略是M.Chickering提出的Bayesian structure learning algorithm.

三、哈勃多维分析

1. Adtributor在哈勃多维分析中的应用

多维分析作为哈勃监控系统的一大功能特色，在算法应用层借鉴了Adtributor算法对业务数据进行根因分析，实际效果较好。以下是哈勃多维分析结构体系图，精选层中实现了基于熵Adtributor算法，目前已经开源。

【重点】AIOps智能运维开源项目：本项目从运维领域的痛点出发，致力于智能运维（Artificial Intelligence for IT Operations，AIOps）算法库建设，打造运维领域的 AI 大脑。包括但不限于单维时间序列异常检测，多维时间序列异常检测，多维下钻根因分析，ROOT根源分析，趋势预测，日志模板提取，日志异常定位等方向。内网地址：https://git.code.oa.com/TencentAIOps/tencent-aiops-algorithms

精选层中brute_force实现了基于控制图理论的异常检测算法，将于后期持续开源。

2. 哈勃多维分析特色

相比于与论文，哈勃多维分析更深入地结合公司自研上云业务的业务背景和数据特点，在借鉴Adtributor算法的基础上做出如下改进：

1. 异常检测。论文采用ARMA时间序列模型判定KPI是否异常，并计算正常预测值；哈勃采用从异常发生前三小时的历史数据取平均作为正常预测值，运行效率高于ARMA模型，实际业务使用效果高效。具体请看后面“哈勃多维分析时间点说明”部分。
2. 根因分析。论文有针对性地对量值和率值KPI采用不同的计算方式进行根因分析；哈勃采用将率值KPI统一转换成量值KPI的方式来分析。具体请看后面“哈勃多维分析率值KPI转换策略”部分。
3. 结果输出。论文根据维度中元素的S值降序输出异常元素集合；哈勃在论文的基础上，针对不同业务可自定义选择根据元素影响范围面或者异常占比的大小输出，具有更好的选择自由度和业务针对性，比如影响面大的元素更加引起客户的注意。
4. 结果输出。论文计算每一维度的总S值，并依据S值大小降序排列输出各个维度的异常元素集合；哈勃统一维度输出顺序，将用户设定或者重点关注的维度放在前面，方便用户查看

3. 哈勃多维分析率值KPI转换策略

虽然论文分别给出了量值KPI和率值KPI的不同计算方式，但是率值KPI的计算方式明显要比量值KPI的复杂得多，在运行效率和内存上都更苛刻。因此哈勃多维分析将率值KPI转换成量值KPI的根因分析，经实际业务数据验证，该策略确实有效。

核心思想：将复杂的问题转换成简单的问题来解决。

以业务请求成功率为例说明，

成功率=成功数/请求总数 *100%

成功率=(1-失败数/请求总数)*100%

根据率值KPI的定义公式，我们可以提出这样一个前提假设：在异常时间内请求总数可认为是基本不变的；或者失败数相比于请求总数在量级上更小得多，导致失败数的异常波动变化被抹平。此时，成功率和成功数、失败数在时间序列趋势图上表现为

• 成功率-成功数：趋势基本一致

成功率-失败数：上下基本对称

因此将成功率指标的异常根因分析转换为成功数或失败数的异常根因分析就表现得可行。

实践证明，当上述趋势表现越明显，率值KPI和相应量值KPI的异常根因分析结果越接近。

同时，在根因分析的召回率和准确率保持较高的水平下，率值KPI转换策略在执行效率和实现方式上更加高效可行。

4. 哈勃多维分析时间点说明

前面提到，哈勃多维分析舍弃ARMA时间序列模型，采用正常时间取平均作为预测值F，关于正常时间和各时间点的设定说明如下：

经验上设置异常时间anomaly_time为3分钟，监控系统的目的是能及时检测到KPI异常的发生，并尽快定位异常根因便于运维工程师修复止损。

1. 正常时间由过渡时间和历史窗口确定，和异常时间满足如下关系：
2. 过渡时间内，对于缓变型的异常告警，KPI曲线从正常到异常有个缓慢过渡的阶段，该时间段内判定为正常和异常均不太合理，因此跳过过渡时间以设定正常时间；对于突变型异常告警，过渡时间的设定作用较小。过渡时间在业务经验上设定为20分钟。
3. 通过设定历史窗口可调节正常时间段的长短，确保正常时间内的KPI是正常的，因为异常与正常是相对而言的，正常时间的设定会导致KPI异常的判定不同，从而导致根因分析结果可能不同。历史窗口在业务经验上设定为3小时。

5. 哈勃多维分析结果展示

多维分析作为哈勃系统的一大功能特色，以下是哈勃官网和微信公众号“云监控助手”的界面。哈勃监控系统官网http://hubble.oa.com。

哈勃对于自研上云的业务提供多指标、多维的监控，可实时根据业务数据展示KPI时间序列趋势图，并允许用户手动选择不同时间、不同维度查看曲线分析KPI异常情况。

“云监控助手”提供三个功能模块：上方告警视图模块，对于检测出的异常告警给出异常时刻的和前一天的KPI曲线对比，高亮显示异常时间段；中间多维分析结果模块，经过哈勃多维分析（通常是秒级）列出业务上主要关注维度下的异常元素，并对比较重要的元素进行染色显示，同时异常分数表明每个维度下不同元素的异常相对大小；下方关注人模块，可实时查看订阅和关注了告警的人员，并提供了一键拉群等快捷功能。

四、总结

本文详细介绍了AIOps智能运维开源项目中开源的一种基于熵的多维根因分析算法——Adtributor算法，并介绍了算法在哈勃多维分析中的应用，希望在开源协同的大环境下，能够推动更多公司内部自研业务上云。我们后续会从时间序列异常检测、深度学习等多方面丰富算法应用层，并将算法持续开源。

附件1：论文原文《Adtributor: Revenue Debugging in Advertising Systems》

五、资料整理

1. 智能运维系统（一）：https://zhuanlan.zhihu.com/p/27528044
2. 根因分析的探索：https://zhuanlan.zhihu.com/p/31991166
3. FOCUS: SHEDDING LIGHT ON THE HIGH SEARCH RESPONSE TIME IN THE WILD：https://zr9558.com/2017/08/01/focus-shedding-light-on-the-high-search-response-time-in-the-wild-2/
4. 业务指标多维分析算法盘点：https://www.bizseer.com/index.php?m=content&c=index&a=show&catid=26&id=3
5. 典型的四篇论文：
6. Adtributor: Revenue Debugging in Advertising Systems
7. iDice: Problem Identification for Emerging Issues
8. HotSpot: Anomaly Localization for Additive KPIs with Multi-Dimensional Attributes
9. Squeeze：Generic and Robust Localization of Multi-Dimensional Root Causes