基于Hadoop的局部异常检测算法*

李永政，郝新兵

(1.华北计算机系统工程研究所，北京 100083; 2.中国信息安全研究院有限公司，北京 100000)

0 引言

异常检测作为数据挖掘领域里的一个重要研究方向，是从大量数据中检测出少量与多数数据产生机制不同的数据点[1]。异常检测技术可以应用于很多领域，如网络入侵检测、电信和信用卡欺诈、气象预报等[2]。异常检测方法有基于统计学的方法、基于深度的方法、基于距离的方法、基于聚类的方法、基于密度的方法。基于统计的方法[3]是假设数据符合某种统计规律，将那些严重偏离数据分布曲线的数据点定义为异常点，但这种方法需先得知数据分布规律并且只适用于只有一个维度属性的数据，事实上这两种条件都难以满足。基于深度的方法是为每一个对象分配一个深度值，根据不同的深度值，将数据对象映射到二维空间相应的层上，处在浅层的数据对象更可能是异常点[4]。但是这种方法对高维数据的检测效率较低。基于距离的方法最早由KNORR E M等人[5]提出，其将与绝大部分数据点的距离都大于某一个阈值的数据点定义为异常点。RAMASWAMY S等人[6]在此基础上提出了K最近邻异常点检测方法，该方法首先计算每个数据对象的第k邻居距离，然后将所有数据对象第k邻居距离排序，距离最大的top(n)的数据对象作为异常点。但这种方法对于参数的选择十分敏感，并且时间复杂度偏高。基于聚类的方法[7]是在聚类的基础上，将距离所属簇中心比较远的点以及数据规模较小、分布比较稀疏的簇归为异常点，但这种方法高度依赖所选择的聚类算法。基于密度的方法，将密度明显小于其邻域密度的数据点定义为异常点，最具代表性的就是由BREUNIG M M等人[8]于2000年提出的Local Outlier Factor(LOF)离群因子异常检测算法。该算法通过计算数据集中每个数据点的离群因子的值来判断该点是否为异常点。在LOF算法基础上，众多学者提出了改进算法。Jin Wen等人[9]在LOF算法基础上提出了INFLuenced Outlierness(INFLO)算法，该算法基于对称邻居关系，引入了新的离群因子计算方法，在计算数据点的离群程度时，同时考虑近邻与逆向近邻。当不同密度数据区域离得很近时，可以防止边缘点被误判[10]。Tang Jian等人[11]提出了Connectivity-based Outlier Factor(COF)算法，它采用链距离的方法解决了异常点的密度与正常点的密度相差不大，属于模式偏离的情况。虽然以上方法提高了LOF算法检测准确度，但当数据规模较大、数据复杂度较高时，检测效率较低。

为了提高局部异常检测算法的检测效率和检测准确度，本文提出一种基于Hadoop的分布式局部异常检测算法MR-DINFLO。该方法在INFLO算法的基础上，引入信息熵来确定数据的离群属性，在计算各个数据对象之间距离时采用加权距离，给离群属性以较大的权重，提高了检测准确度。该算法还通过引入Hadoop的MapReduce计算模型，实现了检测算法的并行化，提高了检测效率。

1 研究基础

1.1 INFLO算法

INFLO算法是在LOF算法的基础上提出的，该算法重新定义了离群因子的计算方法，避免了不同密度区域的点离得很近时，边缘点有可能被误判的情况[12]。相关定义如下。

1.1.1 对象p的第k距离

对于任意一个正整数k，对象p的第k距离记作k-dis(p)，在数据集D中存在一个对象o，该对象与对象p之间的距离记作d(p,o)。

(1)

满足以下条件，则取k-dis(p)等于d(p,o)：

(1)至少存在k个对象o′∈D满足d(p,o′)≤d(p,o)；

(2)至多存在k-1个对象o′∈D满足d(p,o′)

1.1.2 对象p的k距离邻域

已知对象p的第k距离，那么数据集D中到对象p的距离不大于p的第k距离的对象的集合定义为p的k距离邻域。即:

Nk(p)={q∈D{p}|d(p,q)≤k-dis(p)}

(2)

1.1.3 对象p的反向k近邻

p的反向k近邻定义如下：

RNNk(p)={q|q∈D,p∈NNk(q)}

(3)

其中，NNk(p)与Nk(p)一样，都表示对象p的k距离邻域。

1.1.4 对象p的局部密度

对象p的局部密度表示如下：

(4)

1.1.5 对象p的局部离群因子

对象p的局部离群因子定义如下：

(5)

其中：

(6)

ISk(p)=NNk(p)∪ RNNk(p)

(7)

相比较LOF算法，INFLO既考虑了k近邻，又考虑了反向k近邻，可以很好地表征数据对象所在区域的密度特征。

1.2 距离加权策略

为了提高检测准确度，在计算两个数据对象之间距离时，胡采平等[13]采用加权距离,通过计算属性信息熵来确定属性的权重。

熵是信息论中用来描述信息和随机变量不确定性的重要工具，设X为随机变量，其取值集合为S(X)，P(x)表示X可能取值的概率，则X的熵定义为：

(8)

数据的混乱程度是由数据在各个属性上的混乱程度决定的，属性的信息熵反映了数据在各个属性上分布的混乱程度，属性的信息熵越大，数据在该属性上分布越不规律，进而可能导致整个数据分布越不规律。假设d维数据集D的属性集为A={A1,A2,…,Ad}，D中数据对象p在属性Ai上的值记为fAi(p)。

1.2.1 离群属性

对于p∈D,Ai∈A,若满足以下关系：

则称属性Ai为离群属性。

如果属性Ai的信息熵不小于其他属性信息熵的平均值，说明属性Ai的不确定性较大。因此称属性Ai为离群属性。

1.2.2 加权距离

设p,q∈D,其中fAi(p)和fAi(q)是第i(i=1,2,…,d)维属性的值，wi是第i维的权重，数据对象p和q的加权距离为:

(9)

其中：

(10)

离群属性对于数据对象之间距离计算有较大的贡献，因此给离群属性较大的权重。

1.3 Hadoop与MapReduce核心技术

Hadoop是由Apache基金会开源的一个分布式系统架构，它主要由分布式文件系统Hadoop Distributed File System(HDFS)和MapReduce分布式计算框架两大核心内容组成[14]。

1.3.1 HDFS

HDFS是Hadoop的分布式文件系统，为Hadoop的分布式系统提供海量数据存储支持。HDFS可以部署在商用硬件的集群上，并且具有容错机制。HDFS采用Master/Slave的体系架构，集群由Namenode和多个Datanode组成[15]。Namenode是管理节点，负责管理文件系统的元数据。Datanode是文件系统的工作节点，负责存储或检索实际的数据。

1.3.2 MapReduce

MapReduce是Hadoop的分布式计算框架，它可分为两个主要阶段，即Map阶段和Reduce阶段。输入数据被分割到多个数据块中，每个数据块内每行数据都要执行Map函数，Map阶段输入key/value对，key为文件中行偏移量，value为这行数据内容。用户自定义Map函数，输出中间key/value对，Reduce阶段合并所有具有相同key值的键值对，根据用户自定义Reduce函数，计算最终结果[16]。MapReduce模型计算方法如图1所示。

图1 MapReduce计算模型

2 MR-DINFLO算法

为了提高局部异常检测算法的检测效率和检测准确度，本文提出基于Hadoop的局部异常检测算法MR-DINFLO。该算法在INFLO算法的基础上，利用MapReduce框架实现了算法的并行化，提高了检测效率。同时，该算法在计算各数据点之间距离时采用加权距离，给离群属性以较大的权重，提高了检测准确度。MR-DINFLO算法的输入和输出描述如下：

输入：m维数据集D；参数k；异常点个数n。

输出：前n个异常点及所对应的离群因子。

该算法主要分为四个阶段。每个阶段都是按照MapReduce计算流程来进行。除了第一个阶段，每个阶段Map的输入来源于上一阶段Reduce的输出。Reduce的输出写入到HDFS中。

(1)第一阶段。此阶段包含两个相互依赖的MapReduce程序。输入是数据集D，输出是各个属性的信息熵。方法如下：

FirstMapper

输入：数据集D

输出：〈di_valuei,1〉，其中di表示数据的第i个属性，i=1,2,…,m；valuei是数据对象在第i个属性的取值;“1”表示数据对象在第i个属性取值为valuei的个数为1;di_valuei表示将di与valuei作为一个整体输出。下划线连接表示将下划线两边内容作为一个整体输出，以下同理。

FirstReducer

输入：〈di_valuei,1〉

输出：〈di_valuei,countvaluei〉，其中countvaluei表示数据对象在第i个属性取valuei的总个数。

SecondMapper

输入：〈di_valuei,countvaluei〉

输出：〈di,valuei_countvaluei〉

SecondReducer

输入：〈di,valuei_countvaluei〉

根据式(8)计算第i个属性的信息熵。

输出：〈di,E(i)〉，其中E(i)表示第i个属性的信息熵。

(2)第二阶段。输入是数据集D和第一阶段的输出，输出是数据集D中数据对象的局部密度和k近邻。方法描述如下：

输入：阶段1中Reduce的输出

根据式(10)确定各个属性的权重，为下面计算数据对象之间加权距离做准备。

输出：〈di,wi〉，i=1,2,…,m

Mapper

输入：数据集D

根据式(9)计算一个数据对象p与其他所有数据对象之间的加权距离d(p,q)，接着根据式(2)计算数据对象p的k-dis(p)和Nk(p)。根据式(4)计算对象p的局部密度den(p)。

输出：〈p_den(p),Nk(p)〉

Reducer

不做任何处理

(3)第三阶段。输入是第二阶段Mapper的输出，输出是各个数据对象的离群因子。方法如下：

Mapper

输入：阶段2中Mapper输出结果[p_den(p),Nk(p)]

根据式(3)和式(7)先计算出数据对象p的k近邻和反向k近邻的并集ISk(p)，然后根据式(6)计算出数据对象p的ISk(p)内所有对象平均局部密度denavg(ISk(p))，最后根据式(5)计算出离群因子INFLOk(p)。

输出：〈p,INFLOk(p)〉

Reducer

不做任何处理

(4)第四阶段。输入是第三阶段Mapper的输出，输出是前n个离群数据对象及所对应的离群因子。方法如下：

Mapper

输入：阶段3中Mapper输出的结果〈p,INFLOk(p)〉

输出：〈str,Topn-INFLOk(D′)〉，其中str为任意字符串，D′表示在Map中的数据集，Topn-INFLOk(D′)表示Map中前n个最大离群因子所对应的数据对象的集合。

Reducer

输入：〈str,Topn-INFLOk(D′)〉

输出：〈p,INFLOk(p)〉，对象p表示整体数据集D的前n个异常数据对象之一。

3 实验与分析

实验平台配置：本文采用3节点的Hadoop集群，每个节点配置为CentOS-7系统，JDK1.8版本，Hadoop为2.7.6版本。其中一个节点为Master节点，即Namenode，另外两个为Slave节点，即Datanode。

实验数据集：对数据进行预处理，首先，调整攻击(离群点)占比，保证攻击(离群点)占数据集的2%；然后，对非数值型属性进行数值化处理。

3.1 算法准确度的比较

采用如下度量对算法准确度进行评价：

本文从KDD-CUP 99数据集中选取5种不同规模的子集，首先进行预处理操作，然后进行数据标准化处理，以排除数据属性不同量纲带来的影响。各算法在不同规模数据集上检测的准确度大小如表1所示。从表1数据可以看出，本文提出的MR-DINFLO算法的准确度从数据集为100万时的0.86增长到500万时的0.94。这也说明了随着数据量的逐渐增大，算法越趋稳定。算法准确度评价结果如图2所示，从图2可以看出，在处理相同规模的数据时，本文提出的MR-DINFLO算法的准确度比MR-DINFLO(无信息熵)高，因此可以看出引入信息熵提高了检测准确度。同时可以看出INFLO算法准确度比LOF算法高。

表1 各算法在不同规模数据集上的准确度

图2 算法准确度对比

3.2 算法时间效率的比较

时间效率一般由算法运行时间来衡量，指的是从程序启动到得到实验输出结果的时间。本文提出的MR-DINFLO算法运行在3节点Hadoop集群上，INFLO算法以及LOF算法运行在单机上。它们的输入都是相同规模的数据集。各算法在不同规模数据集上的运行时间如表2所示。算法时间效率评价结果如图3所示，从图3可以看出，在数据量较少时，MR-DINFLO算法的运行效率与LOF算法和INFLO算法相当，这是因为一个MapReduce程序开始执行时，各个节点启动、任务初始化会消耗一部分时间。然而随着数据量的增大，MR-DINFLO算法的运行效率远高于LOF算法和INFLO算法。当数据集大小为300万条时，MR-DINFLO算法的运行时间为1 538 s，LOF算法运行时间为3 013 s，INFLO算法运行时间为3 562 s。

表2 各算法在不同规模数据集上的运行时间 (s)

图3 算法时间效率对比

4 结论

异常检测是数据挖掘中非常重要的领域之一，具有很高的研究价值。为了提高局部异常检测算法的检测效率和检测准确度，本文提出基于Hadoop的局部异常检测算法MR-DINFLO。该算法在INFLO算法的基础上，利用MapReduce框架实现了算法的并行化，提高了检测效率。另外，该算法在计算各数据点之间距离时采用加权距离，给离群属性以较大的权重，提高了检测准确度。在真实数据下验证了MR-DINFLO算法具有高效可行性。