数据的异常检测是一个难题, 面临许多挑战, 其中包括:
- 定义一个正常表现的范围是比较困难的, 异常值和正常值有时候边界并不是特别明显
- 某些恶意行为会伪装成正常值, 难以发现
- 大多数领域的正常行为只能在一段时间内有效, 对于未来的普适性并不是很高
- 对于异常的概念会由于应用的不同而不同
- 缺少带有标记的数据
- 数据的噪声可能有较大的影响
分析异常数据有多种方案, 包括:
- 基于分类的手段
- 基于最近邻算法
- 基于聚类
- 基于统计方法
- 基于信息理论
- 基于特征理论
我们这次着重介绍的是时序数据的异常检测, 我们来讨论讨论LOF方法, 并且给出相应的代码实现
1. LOF方法简介
该方法源自于论文Conformalized density- and distance-based anomaly detection in time-series data
LOF方法也就是Local Outlier Factor的缩写
首先我们需要引入一些符号:
k: 类似于KNN中的k, 代表第k个相邻的
dist(a,b): 表示a和b之间的距离, 可以是几何距离, 也可以是曼哈顿距离等
LOF方法使用对于第k个邻居的反向平均距离(Inverted average distance)来进行一个密度的测量, 我们记作loc_dens
密度的测量
同时我们给出其中的reach_dist
reach_dist
其中NN_k(x)是x的第k个近邻, 而reach_dist是为了当x和o彼此靠近的时候减少统计波动
我们计算出密度之后, 就要利用该密度和其他近邻的点进行比较, 进而我们就可以计算出异常程度的分数, 记为LOF, 按如下方法进行计算:
LOF
如果LOF越大则说明异常程度越高
2. LOF-ICAD方法
基于LOF方法, 论文给出了一种特征抽取的方法, 进一步提高了精度
这里直接给出算法的细节:
输入:
- 窗口长度L
- 合适的训练集合的大小T
- 修正集合的大小C
- 时间序列(x1, ... , x(T+C+L-1))
- 测试的值x(T+C+L)
- 密度测量NCM
输出(异常分数p, 从0到1):
步骤:
- 将时间序列(x1, ... , x(T+C+L-1))映射到矩阵X, 其中矩阵X是L x (T+C)的矩阵
举个例子, 比如对于时间序列(1, 2, 3, 4, 5, 6), T=2, C=2, L=3
则生成X矩阵为
1, 2, 3, 4
2, 3, 4, 5
3, 4, 5, 6 - 将矩阵X划分成训练矩阵X(T)(L x T大小)以及修正矩阵X(C)(L x C大小)
如上述例子, X(T)为:
1, 2
2, 3
3, 4 -
计算NCM值(α1, ..., αC)对于修正矩阵X(C)的每一行(应该会有L行)
NCM
具体的NCM值的计算也就是LOF的计算方式得到
-
对序列最后的x(T+C+L-1)计算NCM值
计算序列末尾的NCM -
计算异常程度分数p
p的计算
如果p的分数特别高, 则异常程度相应地越高
3. Java实现
首先给出LOF算法的实现
package LOF;
import java.util.ArrayList;
/**
* Local Outlier Factor
*
* @author mezereon E-mail:mezereon@gmail.com
* @since 18-4-12
*/
public class LOF {
private int k;
public LOF(int k) {
this.k = k;
}
/**
* 返回异常程度的分数， 越接近1则越异常
*
* @param knn 输入一个时序数据生成的旋转矩阵
* @param x 输入测试的序列
*/
public double getLOF(double[][] knn, double[] x) {
double sum = 0;
for (double[] o : knn) {
sum += getLocDens(knn, o) / getLocDens(knn, x);
}
return sum / k;
}
/**
* 获取local density
*
* @param knn 输入一个时序数据生成的旋转矩阵
* @param x 输入测试的序列
*/
public double getLocDens(double[][] knn, double[] x) {
double[] nnk = findKthPoint(knn, x);
double sum = 0;
for (double[] o : knn) {
sum += reachDist(o, x, nnk);
}
return sum / k;
}
/**
* 找到第k个相似的序列
*
* @param knn 输入一个时序数据生成的旋转矩阵
* @param x 输入测试的序列
*/
public double[] findKthPoint(double[][] knn, double[] x) {
ArrayList list = new ArrayList();
for (int i = 0; i < knn.length; i++) {
list.add(knn[i]);
}
int index = 0;
double minDist = dist(knn[0], x);
for (int i = 0; i < k; i++) {
index = 0;
minDist = dist((double[]) list.get(0), x);
for (int j = 0; j < list.size(); j++) {
if (minDist > dist((double[]) list.get(j), x)) {
minDist = dist((double[]) list.get(j), x);
index = j;
}
}
if (i != k - 1) {
list.remove(index);
}
}
return (double[]) list.get(index);
}
/**
* 返回与相似序列的距离比较之下的较大值
*
* @param o 输入序列
* @param x 测试序列
* @param nnk 第k相似的序列
*/
public double reachDist(double[] o, double[] x, double[] nnk) {
return Math.max(dist(o, x), dist(nnk, x));
}
/**
* 返回序列之间的欧几里德距离
*
* @param nnk 第k相似的序列
* @param x 测试序列
*/
private double dist(double[] nnk, double[] x) {
double sum = 0;
for (int i = 0; i < nnk.length; i++) {
sum += (nnk[i] - x[i]) * (nnk[i] - x[i]);
}
return Math.sqrt(sum);
}
public int getK() {
return k;
}
public void setK(int k) {
this.k = k;
}
}
给出LOF-ICAD的实现
package LOF;
import Tool.DetectTool;
import Util.MatrixUtil;
/**
* @author mezereon E-mail:mezereon@gmail.com
* @since 18-4-26
*/
public class LOFDetectTool implements DetectTool {
private int T;// 时间序列用来训练的长度
private int L;// 时间序列的所利用的窗口长度
private int K = 1;// LOF算法中的k值, 默认设置为1, 也就是取历史最相似的序列进行预测
/**
* LOF检测工具的构造方法
*
* @param T 时间序列用来训练的长度
* @param L 时间序列的所利用的窗口长度
*/
public LOFDetectTool(int T, int L) {
this.T = T;
this.L = L;
}
/**
* 利用LOF进行时间序列分析
* 打印最后一段窗口的异常分数, 越接近1则越异常
*/
public void timeSeriesAnalyse(double[] series) {
// 利用T和L, 以及时间序列生成测试矩阵
double[][] mat = MatrixUtil.getMat(series, T, series.length - T - L + 1, L);
//一个窗口大小的测试序列, 默认是原序列中最后窗口大小的序列
double[] test = MatrixUtil.getTestSeries(series, series.length - L - 1, L);;
double[][] matC = MatrixUtil.getMatC(mat, T, series.length - T - L + 1, L);
double[][] matT = MatrixUtil.getMatT(mat, T, series.length - T - L + 1, L);
LOF lof = new LOF(K);
double[] ncmForC = new double[matC.length];
for (int i = 0; i < matC.length; i++) {
ncmForC[i] = lof.getLOF(matT, matC[i]);
}
double ncmForTest = lof.getLOF(matT, test);
double count = 0;
for (double x : ncmForC) {
if (ncmForTest <= x) {
count++;
}
}
count /= matC.length;
System.out.println("Anomaly Score is "+count);
}
}
给出具体的Test类
public class LOFDetectToolTest {
public double[] testData;
@Before
public void setUp() throws Exception {
testData = FileTool.getData("data.json");
}
@Test
public void timeSeriesAnalyse() throws Exception {
LOFDetectTool lofDetectTool = new LOFDetectTool(200, 50);
lofDetectTool.timeSeriesAnalyse(testData);
}
}
4. 测试
测试序列1
对于上图序列计算得到的窗口异常分数为0.007092198
我们给它加一个峰值
测试序列2
得到的窗口异常分数为0.950354609
源码以及测试数据我已经放到github了
地址为https://github.com/MezereonXP/AnomalyDetectTool
其中包括自己编写的多种异常检测的工具类, 欢迎使用
希望大家多多Star, 有什么问题可以提issue给我, 或者发邮件到我的邮箱 mezereonxp@gmail.com
下一篇, 将会介绍利用指数平滑进行异常检测的方法
