2. 西安电子科技大学 计算机学院,陕西 西安 710071
2. School of Computer Science and Technology, Xidian University, Xi’an 710071, China
随着当前数据量的增多,在数据处理和数据分析过程中,应用有效的数据挖掘技术能够大大提升数据处理和分析的速度,同时也能够提升数据处理的准确性。其中,数据挖掘就是从大量的、不完全的、有噪声的、模糊的及随机的数据集中提取隐含在其中的、事先不知道的但又潜在的有用的信息和知识的过程[1]。异常检测是数据挖掘中的重要任务之一,目的是从给定的数据集中发现异常的数据对象[2]。异常检测又称为离群点检测、偏差检测、孤立点检测等,用于反作弊、故障诊断、金融诈骗等领域。随着移动通信、云计算等技术的快速发展,数据量的日渐增多[3],传统基于单机内存设计的异常检测算法面临着很大的挑战。因此研究适用于大规模数据的异常检测算法具有重要的应用价值。
近年来,已经出现许多异常检测算法,主要包括两类[4]:有监督性的[5-6]和无监督性的[7-13]。有监督性的异常检测算法在监测异常数据前需要大量的样本进行模型检测,但实际应用中往往无法事先获取大量的训练样本。因此无监督的异常检测算法具有更高的实用价值。
在无监督异常检测算法中,Breunig等[10]提出的Local Outlier Factor(LOF)算法,通过计算每个点的局部异常因子(LOF值)从而判断一个数据对象的异常程度。该算法与其他算法相比,理论简单、适应性较高,并且能有效地检测全局异常和局部异常。然而LOF算法是基于局部密度设计的,算法复杂度较高且假设不存在大于或等于
本文主要针对算法的计算量和算法中重复点对局部异常因子的影响这两个方面对LOF异常检测算法进行了深入分析,并根据Hadoop作业调度机制和MapReduce计算框架,设计了一种基于MapReduce和LOF思想的并行异常检测算法(MR-DLOF)。在MR-DLOF算法中,为了避免数据集中存在大于或等于
Hadoop是Apache软件基金会开发的分布式系统基础架构。其理论基础是Google在国际上发表的关于MapReduce[14]、GFS[15]和BigTable[16]的三篇论文。Hadoop由HDFS、MapReduce、HBase、Hive和Zookeeper等成员组成,其中HDFS和MapReduce是两个最重要的成员。HDFS可以实现不同节点、不同类型计算机的数据整合,MapReduce通过Map函数和Reduce函数建模来实现可靠的分布式计算。实践证明,大量基于MapReduce的并行算法的实现有效地提高了算法的计算能力[17-20]。
1.1 Hadoop MapReduceHadoop MapReduce 的实现采用了Master/Slave 结构。MapReduce分布式计算框架主要包含两个处理过程:Map阶段和Reduce阶段。Map阶段的Map函数和Reduce阶段的Reduce函数都由用户根据需求进行自定义。Map函数主要处理输入数据集并产生中间输出,然后通过某种方式将这些中间输出通过Reduce函数组合在一起导出最终结果。此过程均以键值对(key/value)形式成对地输入和输出数据,保证了数据的安全性和可靠性。当Reducer函数输出最后一个键值对时,MapReduce任务完成。图1为MapReduce详细流程。HDFS首先根据数据大小和块大小对数据进行物理分割,用户可根据需求对数据进行逻辑分割,经过Map阶段,对每一块数据执行Map任务后,对数据进行排序后进入Reduce阶段合并结果,最后将结果写入HDFS中。
![]() |
Download:
|
图 1 MapReduce framework处理过程 Fig. 1 MapReduce framework process |
Hadoop Distributed File System (HDFS) 采用Master/Slave结构,其作为一个高度容错且易扩展的分布式文件系统,主要包含NameNode、Secondary NameNode和DataNode三类节点[21]。图2详细地描述了HDFS结构。
![]() |
Download:
|
图 2 HDFS结构 Fig. 2 HDFS structure |
NameNode为主节点且只有一个,负责接收用户的操作请求,记录每个文件数据块在各个DataNode上的位置和副本信息。Secondary NameNode为可选节点,与NameNode进行通信,定期保存HDFS元数据快照。DataNode为从节点且可以有多个,主要负责存储数据。同时为了保证数据安全,文件会有多个副本(默认为3个)。DataNode定期向NameNode上报心跳,NameNode通过心跳响应来控制DataNode。
2 算法设计 2.1 LOF算法LOF是基于密度的经典算法,其核心部分是关于数据点密度的刻画。由数据点的k-邻近距离,计算各个数据点的局部可达密度和局部异常因子,根据局部异常因子大小判断数据点的异常程度从而得到异常点。算法的基本概念如下:
1) k-邻近距离 (k-distance): 对于任意正整数
① 在样本空间中,至少存在
② 在样本空间中,至多存在
其中,
2) k-距离邻域(k-neighbor): 点
3) 可达距离 (reachability distance): 给定参数
${\rm reach}{\rm{ - }}{{\rm dis}_k}(p,o) = \max \{ k{\rm{ - }}{\rm distance}(o),d(p,o)\} $ |
4) 局部可达密度 (local reachability density): 数据点
$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): 数据
${\rm{LOF}}{_k}(p) = \frac{{\sum\nolimits_{o \in {N_k}(p)} {\displaystyle\frac{{{\rm lrd}(o)}}{{{\rm lrd}(p)}}} }}{{|{N_k}(P)|}}$ | (2) |
根据局部异常因子的定义,如果数据点
LOF算法是基于密度的异常检测算法,计算量大,且在LOF算法中关于局部可达密度的定义存在假设:不存在大于或等于
算法1 MR-DLOF algorith
输入
输出 Abnormal data and LOF values
Get data set which
Calculate
return Abnormal data and LOF
由于LOF算法不足,本文重新定义了k-邻近距离的概念,并结合MapReduce框架提出并行异常检测算法。重新定义的k-邻近距离概念如下。
k-邻近距离(k-distinct-distance): 对于任意正整数
1) 在样本空间中,至少存在
2) 在样本空间中,至多存在
其中,
算法2 Compute
输入 data set
输出 data set which
Initialize a Hadoop Job
Set TaskMapReduce class
Logically divide X into multiple data blocks:
In the j-th TaskMapReduce
FirstMapper
输入
输出
for each data
Calculate
Sort
for each
if
add
end
Calculate k-distinct-distance record
end
FirstReducer
输入
输出
SecondMapper
输入
输出
for
if
else
end
SecondReducer
输入
输出
for value do
end
ThirdMapper
输入
输出
for
end
if
output
ThirdReduce
输入
输出
for value do
Sort
end
本部分主要介绍了MR-DLOF算法基本思想和步骤。首先,将数据集存放在HDFS上并将原始数据集逻辑地切分为多个数据块;然后,根据MapReduce原理并行处理各个数据块中的数据,使得每个数据点的k-邻近距离和LOF值的计算仅在单个块中执行;最后将每个数据块中局部异常因子小于设定阈值的点剔除,并将大于设定阈值的数据点合并成一个新的数据集,更新其k-邻近距离和LOF值,从而提高算法的准确度和灵敏度。Algorihm1和Algorihm2为算法伪代码。
3 实验与分析实验平台配置:3台PC机(通过局域网连接),节点配置为VMware Workstation Pro 12.0.0 for Windows下的CentOS-7,JDK为1.8版本,Hadoop为2.7.4版本。本文所有算法均采用JAVA语言实现,eclipse编译环境。实验环境为基于云平台的Hadoop集群,共有3个节点:1个控制节点和2个计算节点,控制节点内存为32 GB,计算节点内存为8 GB。节点信息如下表1。
![]() |
表 1 节点信息 Tab.1 Node information |
实验数据集:为了验证MR-DLOF算法的有效性和高效性,本文选用网络入侵数据集KDD-CUP1999[22],KDD-CUP1999数据集中每个连接用41个特征和1个标签来表述:其中3个特征以CSV格式写成。这41个特征包含7个离散变量,34个连续变量,并且第20个变量数据全为0。
LOF和MR-DLOF算法中采取距离的方法进行计算,由于每个特征属性的度量方法不同,为了避免出现“大数吃小数”的现象,消除属性度量差异对计算结果的影响,需要对数据集进行预处理。本文对除去全为0变量和CSV格式变量后的37个变量进行标准化处理。
3.1 算法的有效性验证性能衡量标准:异常检测算法对正常数据与异常数据的检测结果如表2所示。
![]() |
表 2 数据检测结果 Tab.2 Data test result |
准确度:
${\rm{Accuracy = }}\frac{{{\rm{TP + TN}}}}{{{\rm{TP + TN + FP + FN}}}}$ | (3) |
灵敏度:即真正辨识率,是正确检测出异常数据的个数与实际异常数据个数之比。
${\rm{Sensitivit = }}\frac{{{\rm{TN}}}}{{{\rm{TN + FN}}}}$ | (4) |
本文主要对比LOF算法和MR-DLOF算法处理相同规模数据集的准确度和灵敏度,来验证MR-DLOF算法的有效性。针对每种规模的数据集,分别从KDD-CUP1999标准化处理后的数据库中随机选取10组不同的数据集,并使所选取的每种规模数据集中攻击数据(即异常点)在该数据集中占比为1%~2%。使用LOF算法和MR-DLOF算法分别计算其准确度和灵敏度,并取其平均值作为评价指标,其中设定阈值
由图3~4可知,LOF和MR-DLOF在处理相同数据集时,MR-DLOF算法在保证其灵敏性的基础上,大大提高了其准确率。
![]() |
Download:
|
图 3 算法准确度比较 Fig. 3 Accuracy comparison of algorithm |
![]() |
Download:
|
图 4 算法灵敏度比较 Fig. 4 Sensitivity comparison of algorithm |
本文主要对比LOF算法和MR-DLOF算法处理相同规模数据集的执行时间,来验证MR-DLOF 算法的执行效率。如图5所示,可以看出当数据量比较大时,MR-DLOF的执行效率明显优于LOF算法。数据量少时LOF算法执行效率优于MR-LOF算法的原因是Hadoop调度Map任务和Reduce任务时需要一定的时间;但当数据量比较大时,将数据分块后,Hadoop会调度多个MapReduce并行执行任务,效率明显增加。
![]() |
Download:
|
图 5 算法效率比较 Fig. 5 Efficiency comparison of algorithm |
为了验证MR-DLOF算法的可扩展性,本文通过扩大数据规模来比较MR-DLOF在不同计算节点下的执行效率,由图6可以看出,在相同数据集规模下,当集群计算节点增加时,算法的执行效率提高。因此当数据集增大时,MR-DLOF算法具有可扩展性,可通过扩充Hadoop集群中计算节点的方法来提高算法的执行效率。
![]() |
Download:
|
图 6 不同计算节点数量下的执行效率 Fig. 6 Execution efficiency under different calculating node numbers |
本文通过分析LOF算法的不足,设计了一种基于MapReduce和LOF算法的并行异常检测算法。该算法修正了k-邻近距离的概念,从而避免某些点的可达距离为零、局部可达密度为无穷大的情况,以提高算法的有效性,同时,为了减少计算量,将分块、利用MapReduce框架思想并行化处理各个数据块中的数据点,大大提高了算法的执行效率。最后,通过真实数据集验证算法的有效性、高效性和可扩展性。
[1] |
HAN Jiawei, KAMBER M. Data mining: concepts and techniques[M]. San Francisco: Morgan Kaufmann Publishers Inc., 2006: 1–18.
(![]() |
[2] |
AGGARWAL C C. Outlier analysis[M]. New York: Springer, 2013: 75–99.
(![]() |
[3] |
CHEN Feng, DENG Pan, WAN Jiafu, et al. Data mining for the internet of things: literature review and challenges[J]. International journal of distributed sensor networks, 2015, 2015: 431047. (![]() |
[4] |
吴镜锋, 金炜东, 唐鹏. 数据异常的监测技术综述[J]. 计算机科学, 2017, 44(S2): 24-28. WU Jingfeng, JIN Weidong, TANG Peng. Survey on monitoring techniques for data abnormalities[J]. Computer science, 2017, 44(S2): 24-28. ( ![]() |
[5] |
STEINWART I, HUSH D, SCOVEL C. A classification framework for anomaly detection[J]. The journal of machine learning research, 2005, 6(1): 211-232. (![]() |
[6] |
邓红莉, 杨韬. 一种基于深度学习的异常检测方法[J]. 信息通信, 2015(3): 3-4. DENG Hongli, YANG Tao. An anomaly detection method based on deep learning[J]. Information and communications, 2015(3): 3-4. DOI:10.3969/j.issn.1673-1131.2015.03.002 ( ![]() |
[7] |
ZHAO Xuanqiang, WANG Guoying, LI Zhixing. Unsupervised network anomaly detection based on abnormality weights and subspace clustering[C]//Proceedings of the 6th International Conference on Information Science and Technology. Dalian, China, 2016: 482–486.
(![]() |
[8] |
左进, 陈泽茂. 基于改进K均值聚类的异常检测算法[J]. 计算机科学, 2016, 43(8): 258-261. ZUO Jin, CHEN Zemao. Anomaly detection algorithm based on improved K-means clustering[J]. Computer science, 2016, 43(8): 258-261. ( ![]() |
[9] |
邹云峰, 张昕, 宋世渊, 等. 基于局部密度的快速离群点检测算法[J]. 计算机应用, 2017, 37(10): 2932-2937. ZOU Yunfeng, ZHANG Xin, SONG Shiyuan, et al. Fast outlier detection algorithm based on local density[J]. Journal of computer applications, 2017, 37(10): 2932-2937. DOI:10.11772/j.issn.1001-9081.2017.10.2932 ( ![]() |
[10] |
BREUNIG M M, KRIEGEL H P, NG R T, et al. LOF: identifying density-based local outliers[C]//Proceedings of 2000 ACM SIGMOD International Conference on Management of Data. Dallas, Texas, USA, 2000: 93–104.
(![]() |
[11] |
BHATT V, SHARMA K G, RAM A. An enhanced approach for LOF in data mining[C]//Proceedings of 2013 International Conference on Green High Performance Computing. Nagercoil, India, 2013: 1–3.
(![]() |
[12] |
MIAO Dandan, QIN Xiaowei, WANG Weidong. Anomalous cell detection with kernel density-based local outlier factor[J]. China communications, 2015, 12(9): 64-75. DOI:10.1109/CC.2015.7275260 (![]() |
[13] |
TANG Bo, HE Haibo. A local density-based approach for outlier detection[J]. Neurocomputing, 2017, 241: 171-180. DOI:10.1016/j.neucom.2017.02.039 (![]() |
[14] |
DEAN J, GHEMAWAT S. MapReduce: simplified data processing on large clusters[J]. Communications of the ACM, 2008, 51(1): 107-113. DOI:10.1145/1327452 (![]() |
[15] |
GHEMAWAT S, GOBIOFF H, LEUNG S T. The google file system[C]//Proceedings of the 19th ACM Symposium on Operating Systems Principles. Bolton Landing, NY, USA, 2003: 29–43.
(![]() |
[16] |
CHANG F, DEAN J, GHEMAWAT S, et al. Bigtable: a distributed storage system for structured data[C]//Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation. Seattle, WA, 2006: 15.
(![]() |
[17] |
MU Yashuang, LIU Xiaodong, YANG Zhihao, et al. A parallel C4.5 decision tree algorithm based on MapReduce[J]. Concurrency and computation practice and experience, 2017, 29(8): e4015. DOI:10.1002/cpe.4015 (![]() |
[18] |
侯泳旭, 段磊, 秦江龙, 等. 基于Isolation Forest的并行化异常探测设计[J]. 计算机工程与科学, 2017, 39(2): 236-244. HOU Yongxu, DUAN Lei, QIN Jianglong, et al. Parallel anomaly detection based on isolation forest[J]. Computer engineering & science, 2017, 39(2): 236-244. DOI:10.3969/j.issn.1007-130X.2017.02.003 ( ![]() |
[19] |
叶海琴, 孟彩霞, 王意锋, 等. 一种基于MapReduce的频繁模式挖掘算法[J]. 南京理工大学学报, 2018, 42(1): 62-67. YE Haiqin, MENG Caixia, WANG Yifeng, et al. Frequent pattern mining algorithm based on MapReduce[J]. Journal of Nanjing University of Science and Technology, 2018, 42(1): 62-67. ( ![]() |
[20] |
刘义, 景宁, 陈荦, 等. MapReduce框架下基于R-树的k-近邻连接算法[J]. 软件学报, 2013, 24(8): 1836-1851. LIU Yi, JING Ning, CHEN Luo, et al. Algorithm for processing k-nearest join based on R-tree in MapReduce[J]. Journal of software, 2013, 24(8): 1836-1851. ( ![]() |
[21] |
WHITE T. Hadoop: the definitive guide[M]. 4th ed. Gravenstein Highway North: O’reilly Media Inc., 2015: 1–4.
(![]() |
[22] |
http://archive.ics.uci.edu/ml/machine-learning-databases/kddcup99-mld/.
(![]() |