智能运维 — 质量保障 — 异常检测 — 指标异常检测 — 框架

B. 智能运维 — 质量保障 — 异常检测 — 指标异常检测 — 框架
雅虎遗作：异常检测框架（EGADS）
业务场景
系统指标：系统指标可以反映硬件的健康情况。比如CPU利用率，硬盘空间，网络端口状态，内存使用情况等等。
商业指标：这些指标可以帮助公司快速的发现服务问题。比如页面访问率，访问延迟等等。
EGADS的整体框架
时间序列建模模块 (TMM) — 给出期望值
各种时序异常检测算法
异常检测模块 (ADM) — 异常概率
异常类型
Outliers：对于一段时间序列而言， Xt是t时刻的观察值，E(Xt)是在t时刻的期望值，如果 Xt和E(Xt)存在着较大的差异，那么可以认为Xt是一个Outliers。
Change points：对于一个给定的时刻t，如果数据点在t之前以及之后的行为和t时刻的行为有较大的差异，那么该时刻t被称为Change point。Change point和Outliers最大的不同之处是前者往往意味着长时间的变化和异常，而后者往往是反复无常，不稳定的。
Anomalous time-series：Anomalous time-series是定义在时间片段上的，如果某个时间片段的特征和其他的时间片段有明显的不同，那么该时间片段被定义为Anomalous time-series。
报警模块 (AM) — 对于不重要的异常，AM会自动过滤掉，而对于重要的异常，AM会给出预警
具体实现细节
基于分解的方法
实际上，在时间序列分解领域中，一种很普遍的做法是把时间序列分解成 趋势，季节性，噪音 3个部分。通过观测噪音的部分，我们可以判断是否为异常。
除上面提到的以外，时间序列分解还可以作用到频域上。频域上的分解算法大致可以分为2类，分别是参数化的方法和非参数化的方法，前者的代表算法有傅里叶变换以及小波变换，后者则是完全由数据本身决定。
报警模块：为了达到这个目的，该模块包含了两个阶段，分别是 阈值选取 以及 过滤 。先通过阈值选取产生一系列的备选异常，然后再过滤掉不相干、不重要的异常，从而完成报警。
阈值选取：我们提到可以通过TMM模块和ADM模块得到预测值和实际值的偏差，那么多大的偏差才能被定义为异常呢？实际上，这也正是阈值选取的作用。选定阈值后，过大的偏差会进入下一阶段，反之则被忽略。
Kσ偏差：该方法是一种参数化的方法。我们假定数据是正态分布，并且事先得到了的均值和方差。那么根据统计学中的“three sigma rule”，99.73%的样本都会分布在均值附近的3倍标准差以内。这个概率可以被认为是正常点置信度，这种方法比较适合数据已经被精确的建模，并且误差是高斯分布的情况。如果数据服从于混合高斯或者其他的分布，那么这种方法是非常不精确的。
密度分布：第二种方法主要用于处理非正态分布的数据。它的基本想法是寻找偏差分布中的低密度区域。一个最常用的算法是LOF(Local Outlier Factor)算法。对于某个点来说，它的密度可以由它的邻居的密度经过估计得到，这被称为局部密度估计。如果目标点的局部密度比其邻居的密度要低。那么该点就会被认为是异常。
过滤
过滤是整个算法过程中的最后一步。目前为止，我们得到的异常仅仅是数学统计意义上的异常，并不是实际中用户所关心的异常。比如，有些用户关心时序数据的峰值，有些用户关心数据的波动，有些则着眼于大段时间的异常。EGADS提供了一个简单的接口，可以允许用户自己标注异常的时序数据区域。那么在最初训练分类器的时候，EGADS就会使用这些人为标注的数据来判断统计上的异常是否和用户所标记的异常相近。真正做到了让数据说话，同时又满足用户的具体需求。
基于机器学习的KPI自动化异常检测系统（Opprentice）
主要思想：Opprentice (Operator’s Apprentice)的主要思想就是跟着运维人员从历史数据中学习，运维人员就像是一个“师傅”，将自己的领域知识“教“给Opprentice，然后Opprentice根据“学”到的知识来自动选择合适的异常检测器和算法参数。
步骤
运维人员首先在历史的KPI曲线上标记出异常
接着Opprentice 使用十几种不同类型的检测器提取出上百个异常特征
我们就可以将异常检测问题转化成机器学习中监督式的分类问题，将提取出的特征作为机器学习算法的输入，通过分类算法将KPI曲线上的点分为正常和异常，从而实现了异常检测。
微信亿级用户异常检测框架的设计与实践
设计目标
主要用于检测恶意帐号可能存在的环境聚集和属性聚集；
方案需要易于融合现有画像信息等其他辅助信息；
方案需要具有较强的可扩展性，可直接用于亿级别用户基数下的异常检测。
复杂度分析
基于聚类算法，若要对亿级别用户两两间计算相似度，其时间复杂度和空间消耗基本上是不可接受的。
核心思路
对用户划分子空间：基于这一想法，同时考虑到恶意用户自然形成的环境聚集和属性聚集，我们可以根据环境以及用户属性对整个用户空间进行划分，只在这些子空间上计算节点之间的相似度，并基于得到的用户相似度图挖掘恶意用户群体。此外，直观上来分析，如果两个用户聚集的维度越“可疑”，则该维度对恶意聚集的贡献度应该越高，
依据上述思路，需要在属性划分后的子空间计算两两用户之间的相似度，然而实际数据中特定属性值下的子空间会非常大，出于计算时间和空间开销的考虑，实际实现上我们会将特别大的 group 按照一定大小 (如 5000) 进行拆分，在拆分后的子空间计算节点相似度。(实际实验结果表明这种近似并不会对结果造成较大影响)
详细设计方案
核心问题
如何根据用户特征 / 使用怎样的特征将整个用户空间划分为若干子空间？
如何衡量用户特征是否“可疑”？
如何根据构建得到的用户相似度关系图找出异常用户群体?
用户空间划分
用户特征
核心特征：核心特征指黑产帐号若要避免聚集，需要付出较大的成本的特征，主要包括一些环境特征；
支撑特征：支撑特征指黑产帐号若要避免聚集，改变所需成本较小的特征。
何为“可疑”
可疑属性提取
多粒度的可疑属性识别
恶意用户识别
工程优化
Spark 性能优化 — 数据倾斜
两阶段聚合
局部聚合
全局聚合
三阶段自适应聚合
随机局部聚合：设定一个较大的数（如 100），参照两阶段聚合第一阶段操作给每个 key 打上一个随机数，对打上随机数后的 key 进行聚合操作；
自适应局部聚合：经过随机局部聚合后，可获取每个随机 key 下的记录条数，通过单个随机 key 下的记录条数，我们可以对原 key 下的数据条数进行估算，并自适应地调整第二次局部聚合时每个原始 key 使用的随机数值；
第二轮随机局部聚合；根据自适应计算得到的随机数继续给每个 key 打上随机数，注意此时不同 key 使用的随机数值可能是不同的，并对打上随机数后的 key 进行第二轮局部聚合；
全局聚合：经过第二轮随机局部聚合后，若特定 key 下记录数超过设定阈值 (如 5000)，则保留该结果，不再进行该阶段全局聚合；否则，则将随机 key 还原为原始 key 值，进行最后一阶段的全局聚合。
答案是肯定的。通过对整个异常用户检测流程进行细致的分析，我们发现我们并不需要对子空间内所有用户对进行相似度计算，通过前期实验我们发现当用户可疑度超过 0.7 时，基本就可以判定该用户是恶意用户。根据用户可疑度计算公式反推，当节点关联边的权重超过 18.2 时，其在最后结果中的权值就会超过 0.7，基于这一想法，我们引入了动态 Dropping 策略。
通过相似度计算得到的用户相似度关系图节点分布是极不均匀的，大部分节点度数较小，少部分节点度数较大，对于这种分布存在严重倾斜的网络图，图划分策略的选择对图算法性能具有极大影响。为了解决这一问题，我们使用 EuroSys 2015 Best Paper 提出的图划分算法 HybridCut 对用户相似度关系图进行划分。
百度时序数据标签工具：Curve
传统标注工具的问题
准确性：标注人员通常对异常认识不清晰，随着标注进度的推进，判断标准很容易发生漂移
标注效率：异常数据占比很小，标注时大量的时间耗费在检查正常数据上，效率较低。
现有解决方案的优点
基于自动异常检测的辅助标注方法：在标注开始前，自动分析疑似异常区间，高亮提醒标注人员关注，减少检查正常数据耗费的精力；在标注过程中，提供异常区间对比功能，协助标注人员认识异常，避免判断标准的漂移，减少标注数据前后矛盾的情况。
功能
可视化和标注功能
Y轴区间自动计算 — 基于离群点自动判断
大尺度数据采样 — 均值，最大值，最小值
辅助标注功能 — 参考线生成（自定义插件）
初始异常识别
异常区间对比
异常判断
按照所有数据最小的千分之三和最大的千分之三作为异常数据
时间序列异常检测学件：Metis
代码结构
数据层（DB）：存储检测异常信息、样本信息、任务信息等。
服务层(server)： 服务层划分为四大模块，分别是：数据驱动模块DAO、特征计算模块feature、算法模块feature以及业务模块business。
接口层(API)： 提供API能力，时间序列异常检测接口和WEB管理的操作接口。
WEB层(web)： 系统提供的WEB服务，通过服务界面，用户可以进行异常查询、打标标注、样本库管理、模型训练等操作。
关键技术点
样本组成
以当前时间点为基准，获取一周前的这个时间点的前后各180分钟的分钟级数据；
以当前时间点为基准，获取前一天的这个时间点的前后各180分钟的分钟级数据；
获取当前时间点前180分钟的分钟级数据；
特征提取
规范化：转换成 0 ~1
通过各种统计算法（均值、方差、分位数等）获取统计特征
通过xgboosting分类
其他
Facebook 时间序列预测算法 Prophet 的研究
aiops学术网站
测试数据集