EGADS学习资料

EGADS (Extendible Generic Anomaly Detection System)是Yahoo一个开源的大规模时间序列异常检测项目，主要由两个模块构成，一个是时间序列构造模块，另一个是异常检测模块。
给定一段时间的离散值（构成一个序列），时间序列模块会学习这段序列的特征，并试图重新构建一个和原序列尽量接近的序列。结果和原序列一同送入异常检测模块，基于不同的算法（原则，阈值），异常点会被标记出来。


时间序列构造模块提供了多种算法(Time-series Modeling Module):
1.Olympic Model（Seasonal Naive）一个简单的窗口模型，对点Px的预测为点Px前n个值的Smoothed Average.
2.Exponential Smoothing Model 一个平滑模型，由简单的数列获得。ETS模型可以自动选择Single、Double、Triple里面匹配最好的输出。
3.Moving Average Model 也是平滑模型，点Px的预测值取邻近点的平均值。
4.Regression Models 一般是线性回归，特殊例子或者异常偏差特别大的时候有用。


异常检测模块(Anomaly Detection Module)
1.ExtremeLowDensityModel 超低密度模型，很简单有效的密度模型。
2.AdaptiveKernelDensityChangePointDetector 拐点检测模型
3.KSigmaModel 经典K-sigma模型
4.DBScanModel（Density-Based Spatial Clustering of Applications with Noise）又是一个基于密度的模型，在空间中作聚类，如果目标序列可以比较好的分类的话会有不错的效果。


序列构造自动选优
不同类型的数据可能适合不同的模型，选择AutoForecastModel，程序会自动把所有TMM都跑一遍，并推选偏差值最小的模型送入异常检测模块。
值得注意的是，这里自动选取的标准只关注了还原度，但还原度高并不直接代表能更好的查找异常，在使用本方法的时候要留意在心。


多数投票算法
不同的异常检测算法从不同的角度定义了异常。实践过程发现，单一异常算法并不能找出所有异常点，还会出现一系列的假阳性异常。使用Majority Voting，规定半数以上算法识别为异常的点才输出为结果，在实际数据中提供了远高于单一算法的准确度。


Robust PCA解决以下特征定义的问题：
1.高纬度。数据集纬度高，数据间相互交织，人工检测基本不可能。
2.最低加阳性。作为异常检测问题，我们不希望有过多的假阳性报警来干扰监控人员。
3.周期性。每小时/每天/每周/每月这样的周期性数据如果不妥善处理，某些周期性的行为可能误报为异常。实际数据中，每天固定时段的峰值数据相对于大部分采样点都可能被判定为异常，但实际为周期性正常现象。
4.数据并不是均匀分布的。像Netflix在两年中实现了高增长，算法需要足够健壮来处理非均匀分布的数据集(增长性数据是一个普遍现象，如长期来看的股市指数等)。
Robust PCA是一个非常常见的主要成分提取算法。RPCA本质其实是一个矩阵分解算法，目标是将输入X分解为X=L+S+E，L代表了X的low rank approximation（低秩估计）。而低秩估计本质就是将矩阵中相关性强的行投影到更低维的线性空间，实现了一个降维平滑的功能，同时剔除冗余信息，提取矩阵特征。提取完主要成分L后，获得了剩下的稀疏矩阵S，和噪点E。
做异常检测的时简单认为低秩矩阵L就能大部分还原输入序列，异常点的特征应该就表现在S或者E中。实际应用中可以把RPCA作为一个时间序列构造模型添加入EGADS中，用后者的异常检测模块提取异常。