﻿ 基于MapReduce的并行异常检测算法
«上一篇
 文章快速检索 高级检索

 智能系统学报  2019, Vol. 14 Issue (2): 224-230  DOI: 10.11992/tis.201809007 0

### 引用本文

QI Xiaogang, HU Qiuqiu, LIU Lifang. Parallel anomaly algorithm based on MapReduce[J]. CAAI Transactions on Intelligent Systems, 2019, 14(2): 224-230. DOI: 10.11992/tis.201809007.

### 文章历史

1. 西安电子科技大学 数学与统计学院，陕西 西安 710071;
2. 西安电子科技大学 计算机学院，陕西 西安 710071

Parallel anomaly algorithm based on MapReduce
QI Xiaogang 1, HU Qiuqiu 1, LIU Lifang 2
1. School of Mathematics and Statistics, Xidian University, Xi’an 710071, China;
2. School of Computer Science and Technology, Xidian University, Xi’an 710071, China
Abstract: To improve the accuracy, sensitivity, and efficiency of anomaly detection algorithm in data mining when the amount of data increases, a parallel anomaly detection algorithm (MR-LOF) based on the MapReduce framework and the local outlier factor (LOF) algorithm is proposed in this paper. First, the dataset, stored in the Hadoop distributed file system (HDFS), is logically divided into multiple data blocks. Then, the MapReduce principle is used to process the data in each data block in parallel, so that the k-distance and LOF value of each data point is calculated only in a single block. It greatly improves the efficiency of the algorithm. Simultaneously, the concept of k-distance is redefined. It avoids the situation where the local density is infinite because more than k repeated points exist in the dataset. Finally, the data points whose LOF value is larger than threshold are merged, and the LOF values of combined data are recalculated. This process can effectively improve the accuracy and sensitivity. Experiments with real-world datasets demonstrate the validity, high efficiency, and extendibility of the MR-DLOF algorithm.
Key words: data mining    anomaly detection    local outlier factor    Hadoop    MapReduce    Distributed File System    parallel computing    local density

Hadoop Distributed File System (HDFS) 采用Master/Slave结构，其作为一个高度容错且易扩展的分布式文件系统，主要包含NameNode、Secondary NameNode和DataNode三类节点[21]图2详细地描述了HDFS结构。

NameNode为主节点且只有一个，负责接收用户的操作请求，记录每个文件数据块在各个DataNode上的位置和副本信息。Secondary NameNode为可选节点，与NameNode进行通信，定期保存HDFS元数据快照。DataNode为从节点且可以有多个，主要负责存储数据。同时为了保证数据安全，文件会有多个副本(默认为3个)。DataNode定期向NameNode上报心跳，NameNode通过心跳响应来控制DataNode。

2 算法设计 2.1 LOF算法

LOF是基于密度的经典算法，其核心部分是关于数据点密度的刻画。由数据点的k-邻近距离，计算各个数据点的局部可达密度和局部异常因子，根据局部异常因子大小判断数据点的异常程度从而得到异常点。算法的基本概念如下：

1) k-邻近距离 (k-distance): 对于任意正整数 $k$ ，点 $p$ k-邻近距离定义为 $k{\rm{ - }}{\rm distance}{\rm{ }}(p) = d(p,o)$ ，如果满足以下条件：

① 在样本空间中，至少存在 $k$ 个点 $q$ ，使得 $d(p,q) \leqslant d(p,o)$

② 在样本空间中，至多存在 $k - 1$ 个点 $q$ ，使得 $d(p,q) < d(p,o)$

2) k-距离邻域(k-neighbor): 点 $p$ k-距离邻域 ${N_k}(p)$ 即与点 $p$ 的之间距离小于 $k{\rm{ - }}{\rm distance}{\rm{ }}(p)$ 的对象的集合。

3) 可达距离 (reachability distance): 给定参数 $k$ 时，数据点 $p$ 到数据点 $o$ 的可达距离 ${\rm reach}{\rm{ - }}{\rm dis}(p,o)$ 为数据点 $o$ $k{\rm{ - }}{\rm distance}{\rm{ }}(o)$ 和数据点 $p$ 与点 $o$ 之间距离的最大值，即

 ${\rm reach}{\rm{ - }}{{\rm dis}_k}(p,o) = \max \{ k{\rm{ - }}{\rm distance}(o),d(p,o)\}$

4) 局部可达密度 (local reachability density): 数据点 $p$ 的局部可达密度为它与k-距离邻域内数据点的平均可达距离的倒数，即

 $lr{d_k}(p) = \frac{{|{N_k}(p)|}}{{\sum\nolimits_{o \in {N_k}(p)} {{\rm reach}{\rm{ - }}{{\rm dis}_k}(p,o)} }}$ (1)

5) 局部异常因子 (local outlier factor): 数据 $p$ 的局部相对密度(局部异常因子)为点 $p$ 的邻域内点的局部可达密度和数据点 $p$ 的局部可达密度的比值的平均值，即

 ${\rm{LOF}}{_k}(p) = \frac{{\sum\nolimits_{o \in {N_k}(p)} {\displaystyle\frac{{{\rm lrd}(o)}}{{{\rm lrd}(p)}}} }}{{|{N_k}(P)|}}$ (2)

2.2 MR-DLOF算法

LOF算法是基于密度的异常检测算法，计算量大，且在LOF算法中关于局部可达密度的定义存在假设：不存在大于或等于 $k$ 个重复点。当这样的重复点存在的时候，这些点的平均可达距离为零，局部可达密度就变得无穷，从而影响了算法的有效性。

$k$ : number of nearest neighbor

$N$ : data block number

$\theta$ : threshold for LOF

Get data set which $lo{f_i} > \theta$ from 算法 2 add in $XX$

Calculate $lo{f_i} > \theta$ of ${x_j} \in XX$

return Abnormal data and LOF

k-邻近距离(k-distinct-distance): 对于任意正整数 $k$ ，点 $p$ k-邻近距离定义为 $k{\rm{ - }}{\rm distance}{\rm{ }}(p) =$ $d(p,o)$ ，如果满足以下条件：

1) 在样本空间中，至少存在 $k$ 个点 $q$ ，使得 $d(p,q) \leqslant d(p,o)$

2) 在样本空间中，至多存在 $k - 1$ 个点 $q$ ，使得 $0 < d(p,q) < d(p,o)$

$k$ : number of nearest neighbor

$\theta$ : threshold for LOF

$N$ : data block number

Logically divide X into multiple data blocks: ${D_1},{D_2}, \cdots ,{D_N}$ .

FirstMapper

输入　 $D = {d_1},{d_2}, \cdots ,{d_m}$

输出　 $< {\rm key,value} > =$ 　　　　 $< {d_i},\left[ {\left( {{\rm{ }}{o_k},{\rm dis}({d_i},{o_k})} \right),{\rm{ }}k{\rm{ - }}{\rm dis}({d_i})} \right] >$

for each data ${d_i},i = 1,2, \cdots ,m$ do

Calculate ${\rm di{s}_{ij}} = {\rm distance}({d_i},{d_j}),j = 1, \cdots ,m$

Sort ${\rm di{s}_{ij}}$ of ${d_i}$

for each ${\rm di{s}_{ij}}$ of ${d_i}$ do

if ${\rm di{s}_{ij}} \ne 0{\kern 1pt} \& {\kern 1pt} |k{\rm{ - }}{\rm neighbour}| < k$

add ${d_i}$ and ${\rm di{s}_{ij}}$ in k-distinct-neighbor record $\left( {{\rm{ }}{o_k},{\rm dis}({d_i},{o_k})} \right)$

end

Calculate k-distinct-distance record $k{\rm{ - }}{\rm dis}({d_i})$

end

FirstReducer

输入　 $< {\rm key,value} > =$ 　　　　 $< {d_i},\left[ {\left( {{\rm{ }}{o_k},{\rm dis}({d_i},{o_k})} \right),{\rm{ }}k{\rm{ - }}{\rm dis}({d_i})} \right] >$

输出　 $< {\rm key,value} > =$ 　　　　 $< {d_i},\left[ {\left( {{\rm{ }}{o_k},{\rm dis}({d_i},{o_k})} \right),{\rm{ }}k{\rm{ - }}{\rm dis}({d_i})} \right] >$

SecondMapper

输入　 $< {\rm key,value} > =$ 　　　　 $< {d_i},\left[ {\left( {{\rm{ }}{o_k},{\rm dis}({d_i},{o_k})} \right),{\rm{ }}k{\rm{ - }}{\rm dis}({d_i})} \right] >$

输出　 $< {\rm key,value} > =$ 　　　　 $< {d_i},\left( {{\rm{ }}{o_k},{\rm reach}{\rm{ - }}{\rm dis}({d_i},{o_k})} \right) >$

for ${o_k} \in k{\rm{ - }}{\rm distinct}{\rm{ - }}{\rm neighbour}$ do

if $k{\rm{ - }}{\rm dis}({o_k}) < {\rm dis}({d_i},{o_k})$

${\rm reach}{\rm{ - }}{\rm dis}({d_i},{o_k}) = {\rm dis}({d_i},{o_k})$

else ${\rm reach}{\rm{ - }}{\rm dis}({d_i},{o_k}) = k{\rm{ - }}{\rm dis}({d_i},{o_k})$

end

SecondReducer

输入　 $< {\rm key,value} > =$ 　　　　 $< {d_i},\left( {{\rm{ }}{o_k},{\rm reach}{\rm{ - }}{\rm dis}({d_i},{o_k})} \right) >$

输出　 $< {\rm key,value} > {\rm{ = }}$ 　　　　 $< {d_i},{\rm lrd}({d_i}) >$

for value do

${\rm lrd}({d_i}) = k/\sum {{\rm reach}{\rm{ - }}{\rm disk}({d_i},{o_k})}$ , 　　　　　 ${o_k} \in k{\rm{ - }}{\rm distinct}{\rm{ - }}$ neighbour

end

ThirdMapper

输入　 $< {\rm key,value} > = < {d_i},{\rm lrd}({d_i}) >$

输出　 $< {\rm key,value} > =$ 　　　　 $< {d_i}({\rm lof}({d_i}) > \theta ),{\rm lof}({d_i}) >$

for ${o_k} \in k{\rm{ - }}{\rm distinct}{\rm{ - }}{\rm neighbour}$ do

${\rm lof}({d_i}) = (\sum {{\rm lrd}({o_k})/k} )/{\rm lrd}({d_i})$ , 　　　　　 ${o_k} \in k{\rm{ - }}{\rm distinct}{\rm{ - }}$ neighbour

end

if ${\rm lof}({d_i}) > \theta$

output

ThirdReduce

输出　 $< {\rm key,value} > = < {d_i}*,{\rm lof}({d_i}*) >$

for value do

Sort ${\rm lof}({d_i})$ for ${d_i}$ and record ${d_i}*$

end

3 实验与分析

LOF和MR-DLOF算法中采取距离的方法进行计算，由于每个特征属性的度量方法不同，为了避免出现“大数吃小数”的现象，消除属性度量差异对计算结果的影响，需要对数据集进行预处理。本文对除去全为0变量和CSV格式变量后的37个变量进行标准化处理。

3.1 算法的有效性验证

 ${\rm{Accuracy = }}\frac{{{\rm{TP + TN}}}}{{{\rm{TP + TN + FP + FN}}}}$ (3)

 ${\rm{Sensitivit = }}\frac{{{\rm{TN}}}}{{{\rm{TN + FN}}}}$ (4)

3.2 算法的高效性验证