基线估计(一)：Self-Organizing Maps在异常检测与定位中的应用
基线估计(一)：Self-Organizing Maps在异常检测与定位中的应用
1 背景
在前文中，我们提到了基线估计的背景，标准定义，以及目前常用的手段1。从本文开始，我们将针对前文提到的手段，详细论述具体的算法如何应用到生产环境中。
在诸多相关算法中，本文将首先介绍自组织映射（Self-Organizing Maps）在异常检测和定位中的应用。
2 什么是自组织映射(SOM)？
自组织映射的训练实例
自组织映射2 是一种使用非监督学习来产生训练样本输入空间的一个低维（通常是二维）离散化表示的神经网络。SOM本质上是一种只有输入层—隐藏层的神经网络，它可用于vector quantization、visualization、clustering以及dimensionality reduction等。以下图为例，蓝色斑点是训练数据的分布，小白斑点是当前的训练数据，起初SOM处于任意位置（训练之初参数随机设置），选择SOM神经元中离白点最近黄色高亮节点，它会往白点移动，同时SOM上的黄色高亮节点的邻居节点也会小幅度移动。直至多次迭代后，网格会趋于近似的数据分布。
SOM的定义如下：
，可用于表征输入样本空间
的具有拓扑结构的一组神经元，它通常包含如下几个成分
-
是一组具有拓扑结构的神经元
- 任意神经元
，都包含一个权重向量
-
是神经元的拓扑结构，通常是2维的矩形/六边形网格，如下图所表示SOM，其拓扑结构是一个矩形网格
-
是度量函数，用来度量输入向量
和权重向量
间的距离
- 输入向量
通过最佳匹配单元best matching unit, BMU映射到SOM上，如下图所示
的bmu是下图中的深黑色节点
bmu实例
在训练开始前，通常需要根据实际的场景来选择SOM的拓扑结构、神经元数量以及度量距离。然后通过训练数据训练SOM各神经元权重向量，具体流程如下：
- 随机设置各神经元权重，或者根据主成分向量采样（更快收敛）
- 从输入空间O中选取输入向量
- 遍历SOM的神经元 
- 通过度量函数计算神经元的权重向量与输入向量的距离
- 保留距离最小的节点（最佳匹配单元BMU）
- 更新BMU节点及其邻域内节点的权重
- 其中 
是神经元
的权重，
是迭代次数
- 
是邻近函数（neighborhood function），通常选取高斯函数作为其邻近函数
- 
是训练系数，随着迭代次数增加而平稳减小
- 
是神经元
与输入向量的度量，
是输入向量对应的BMU节点与输入向量的度量
- 直至最大迭代次数，或SOM整体达到收敛3 如何用SOM做异常检测？
由上述可知，针对任意N维样本，我们可以得到一个拓扑的SOM，使得原样本可映射到这个具有拓扑性质的SOM内。那么我们如何通过SOM来进行异常检测呢？首先我们定义一个量化误差（quantization error, qe），用来表示测试样本
和SOM之间的误差距离，我们通常使用
和
之间的距离作为其量化误差，即
有了量化样本
和自组织映射的度量距离，我们便可用这个距离来做异常检测，此时只需要设置一个合理的阈值，当
低于阈值时，我们认为是正常的，而当
高于阈值时，我们认为存在异常。此外我们通常可以通过生成qe分布并基于概率来推荐阈值，也可以基于实际样本和人工经验来制定相应阈值。
Alexander3等人的研究中，随硬件使用时长变化，整体qe随时间的变化曲线，当濒临硬件的使用寿命极限时，整体qe会显著上升，并且在濒临极限前可通过qe检测出硬件风险
4 如何用SOM做定位？
在使用SOM做定位时，首先我们需要明确什么是定位，以及什么是SOM能够解决的定位问题？定位是一个比较复杂的问题，它包含基于多维度的定位，基于多指标的定位，基于调用链的定位，基于事件因果的定位等等。
- 基于维度的定位：我们发现联通用户访问量下跌，想定位用户访问下跌主要来自于哪个城市，哪个数据中心等
- 基于指标的定位：我们发现某机房的单机到达瓶颈，我们想确定是CPU、线程、I/O还是网卡资源导致其到达了极限
- 基于调用链的定位：目前大型互联网公司的架构，基本都是通过微服务间的调用搭建起来的。那么如果我们发现用户交易付款存在大幅下跌时，支撑交易付款背后的微服务是一个调用链，我们该如何定位调用链的问题节点
- 基于事件因果的定位：如我们发现同一时间点发生了N个异常事件，我们想溯源到底是哪个事件导致了这N个异常事件的发生
- ...
Alexander等人通过SOM做异常检测和定位的逻辑
首先我们需要明确，SOM只能做基于维度的定位和基于指标的定位。SOM做异常定位与Adtributor5的思想类似，Alexander等人3的定位逻辑如上，主要使用各个单指标的quantization error来明确最异常的几个维度/指标。所以在训练SOM前，需要对训练数据的多维指标做归一化，最后在刻画
和
的距离时，才可比较每个维度/指标的异常程度。详细的逻辑可参照下图，样本共有四个维度，测试集共有20480个样本，第一张图是测试集的quantization error随时间的分布，第二张图的原理如下，每个样本都可以计算出一个最异常维度，如样本
的最异常维度是Bearing 1，样本
的最异常维度是Bearing 2，...。20480个样本都有其最异常维度，那么每个维度都有其样本数，这便是第二张图的绘制原理，通过这张图我们可以得知此次机器的寿命问题主要因为Bearing 3。
5 Self-Organizing Maps实战
以上便是SOM用来做异常检测和定位的方法，目前线下coding的代码尚未完成，过几天提交。代码：shendu-ht/self-organizing-maps。
参考资料
1(https://cloud.tencent.com/developer/article/1877457)
2 The self-organizing map. https://doi.org/10.1016/S0925-2312(98)00030-7
3 Self-Organizing Maps for Anomaly Localization and Predictive Maintenance in Cyber-Physical Production Systems
4 Anomaly Detection Using Self-Organizing Maps-Based K-Nearest Neighbor Algorithm
5 Adtributor: Revenue debugging in advertising systems