基于自编码器和密度的融合离群点检测算法

林昕玥，于 炯，，杜旭升，理姗姗，杨少智，高 杰

(1.新疆大学软件学院，新疆 乌鲁木齐 830091；2.新疆大学信息科学与工程学院，新疆 乌鲁木齐 830046)

0 引言

随着数据量的大规模增长，探求数据内潜在的有益知识或信息的需求日益增长，由此产生了数据挖掘[1]技术.离群点检测[2-3]是一种重要的数据挖掘技术.离群点又叫异常点、孤立点，是指与其他样本点具有明显不同特征的样本点.这些样本点与其他样本点差距巨大，可能是由完全不同的、还未引起注意的机制或因素产生的[4].

离群点检测的应用在多个领域都有所涉猎.例如：在金融领域，分析异常的金融交易数据，可以识别出金融欺诈，保护人们财产安全；在医疗领域，分析异常的影像数据，可以判断病症，给出医疗诊断，辅助医生进行诊疗[5]；在娱乐、购物领域，用户的异常点击可能代表该用户新的兴趣点，分析异常点击，有助于产品的营销和广告的精准投放.

在离群点检测研究的早期阶段，人们认为离群点数据本身没有价值，研究离群点的检测只是为了找出异常事件，减少异常事件对正常数据分析的影响.但近些年人们逐渐意识到，异常事件本身也有研究价值，它往往蕴含着人们还没有发现或者容易被忽略掉的有用信息[6].研究异常事件背后的有用信息，可以通过研究数据规律给生活带来便利提供另一种可能.

随着离群点检测技术的不断成熟和深入，多种检测算法相继被国内外研究人员提出.传统的检测算法基本是依靠数学公式对离群点进行计算和预测，主要包括基于分布的、基于深度的、基于聚类的、基于距离的和基于密度的算法[7-11].它们的可解释性都很强，但是各有缺点.例如，基于密度的离群点检测算法对密度的参数选择很困难[12]，在实际检测中很容易出现精度不高的现象.近年来，伴随着神经网络的普及，基于深度学习的离群点检测算法越来越多，最著名的有基于栈式自编码器的算法[13-14]和基于生成对抗网络(GAN)的算法[15].这些算法拟合效果相较于传统方法具有优秀的表现，适用于大规模的数据集.

针对很多离群点检测算法精度不够高的问题，本文提出了将近些年的基于栈式自编码器的离群点(SAE)检测算法与传统的基于密度的离群点(LOF)检测算法相结合的SAE-LOF算法.SAE-LOF算法将SAE的重构误差和LOF的局部离群因子作为新的特征输入到神经网络，对神经网络做有监督的训练，进而对离群点做出预测，以此提高离群点检测的精度.实验表明，该算法相比SAE算法、LOF算法、KNN算法、孤立森林算法，其检测精度有明显提升，算法性能有显著提高.

1 SAE检测算法

自编码器(Autoencoder，AE)是一种特殊的神经网络，其包含输入层、隐藏层和输出层.自编码神经网络的训练包括编码阶段与解码阶段[16].编码阶段将输入数据映射到隐藏层，解码阶段通过隐藏层数据重构输出.与普通神经网络不同的是自编码器的主要目标是构建输出与输入尽可能相近的神经网络.自编码器检测离群点的主要流程如下：

(1) 将正常数据输入自编码器进行训练，使其输出与输入的重构误差达到最小.编码、解码阶段描述如下：

h=f(Wx+b)；

(1)

y=g(W′h+b′)；

(2)

(3)

公式(1)(2)分别为编码、解码阶段；公式(3)为代价函数，其第1项为均方误差重构项，第2项为L2正则项.公式(1)—(3)中：W，b为编码阶段权重参数；W′，b′为解码阶段权重参数；f，g分别为编码阶段和解码阶段的激活函数.

(2) 将测试数据输入训练完成后的自编码器进行重构.

(3)计算测试数据集中各对象的重构误差，重构误差越大，其越有可能是离群点.重构误差越小，其越不可能是离群点.

图1 SAE结构

SAE是由多个自编码器堆叠而成的，后一个自编码器的输入来自于其前一个自编码器的隐藏层数据，依此堆叠.SAE采用逐层贪婪的方式训练，通过最小化重构误差，得到每一层的最优参数.

SAE是一种深度模型，将普通自编码器堆叠起来，使得模型具有更强的拟合能力和特征学习能力，提升了普通自编码器分辨异常样本的能力.

2 LOF检测算法

基于密度的离群点检测算法，以LOF[17-18]为代表.LOF算法相关定义如下：

设数据集为P={p1，p2，…，pi，…，pj，…，pN}，N为数据集P的大小，pi，pj∈P是数据集P的任意2个数据对象，dist(pi，pj)为数据对象pi与pj之间的欧氏距离.

定义1对象pi的r邻域N(pi，r).

对于正整数r，对象pi(pi∈P)的r邻域N(pi，r)定义为

N(pi，r)={pj∈P|dist(pi，pj)≤r，pj≠pi}.

(4)

定义2对象pi的第k距离k-dist(pi).

对于正整数k(k≤N)，对象pi(pi∈P)的第k距离k-dist(pi)=r′，满足：

对于任意r≤r′，都有|N(pi，r)|≥k；

对于任意r

|N(pi，r)|表示对象pi的r邻域内点的个数(不包括pi).

定义3对象pi的第k距离邻域Nk(pi).

对于正整数k(k≤N)，对象pi(pi∈P)的第k距离邻域Nk(pi)=N(pi，r)，其中r=k-dist(pi).

定义4对象pj到pi的第k可达距离reach-distk(pi，pj).

对于正整数k(k≤N)，对象pj(pj∈P)到pi(pi∈P)的第k可达距离定义为

reach-distk(pi，pj)=max{k-dist(pj)，dist(pi，pj)}.

(5)

定义5对象pi的局部可达密度lrdk(pi).

对象pi(pi∈P)的局部可达密度定义为

(6)

定义6对象pi的局部离群因子LOFk(pi).

对于正整数k(k≤N)，对象pi(pi∈P)的局部离群因子定义为

(7)

通过以上步骤最终得到每个点的局部离群因子.比较每个点的LOFk值，将LOFk值较大的样本点标记为离群点.

3 SAE-LOF检测算法

基于SAE的离群点检测算法构建输出尽可能接近输入的神经网络，认为输出与输入的差异越大，越有可能是离群点.基于LOF的离群点检测算法针对样本点的个数和样本之间的距离综合判定离群点.这2种方法是从2种不同的角度表示离群特性，其划分正常点和离群点的依据也有所不同，所以实际检测出来的离群点也不同.为了更全面地表示离群特性、衡量离群程度，本文提出将SAE与LOF结合的算法即SAE-LOF算法.

当同一样本点用多种检测方法进行离群判定时，使用传统的“投票”制度，异常票数较高的样本点被认定为离群点，正常票数较高的样本点被认定为正常点.这种结合方式与单一检测方法相比，能降低检测错误率，提高检测精度.但是“投票”制度将不同检测方法看作同等重要，与实际不符，因而影响了检测精度.

神经网络的实质是对多个特征进行“加权”，让不同特征以不同的重要性对输出结果产生影响.使用神经网络将多种检测方法进行结合，既能让不同检测方法“加权投票”，又能通过自我学习更新权重，使得最终检测结果更接近实际情况.另外，用动量梯度下降法对神经网络进行优化，可以减少震荡，提高迭代收敛速度.

综合以上几点，本文采用神经网络将SAE与LOF结合，把SAE的重构误差和LOF的局部离群因子作为新的特征输入到神经网络中，通过神经网络的拟合，将输出结果逼近实际的正常和异常的标签.算法步骤为：

输入：预处理后的数据集.

输出：离群点预测结果.

(1) SAE训练及测试

(a) 训练SAE，采用逐层贪心的策略，反复进行正向传播和反向传播，最小化重构误差，得到每层最优参数.

(b) 测试SAE，用得到的参数编码、解码，计算测试集的重构误差.

(2) LOF

用LOF算法计算每个样本的LOFk值.

(3) 神经网络的训练及测试

(a) 将(1)得到的重构误差和(2)得到的LOFk值组成新的二维特征数据集，由于特征维度过少，神经网络难以拟合，故需生成多项式特征.设重构误差特征为a，LOFk特征为b，则神经网络数据集为{a，b，a2，ab，b2，…}.

(b) 将神经网络数据集标准化，公式为

(8)

其中：mean(xj)表示第j维特征所有样本的均值，std(xj)表示第j维所有样本的标准差.

(c) 采用改进的BP神经网络训练，通过动态梯度下降法最小化代价函数，确定网络参数.

图2 神经网络结构

(d) 测试神经网络.

先分别测试SAE和LOF，将得到的SAE的重构误差和LOF的LOFk构成神经网络的测试集，并通过生成多项式特征增加特征维度，将其标准化后输入到神经网络中.经过神经网络计算，每个样本得到一个预测值.神经网络结构如图2所示.

(4) 离群点预测

将全部样本的预测值降序排列，取预测值最高的n个样本预测为离群点，其中n=0.03|C|，|C|表示神经网络测试集的样本数.

算法流程如图3所示.神经网络训练和测试部分细化，如图4所示.

图3 SAE-LOF算法流程

4 实验部分

4.1 数据集

本文使用了2个公开数据集进行实验：KDD-CUP99数据集和Shuttle数据集.KDD-CUP99是一个比较权威的用于检测网络入侵的数据集.本文选取10%的KDD-CUP99数据集，包含normal一种正常类型和back、buffer_overflow、ftp_write、guess_passwd等22种异常攻击类型.该数据集包含41个特征，其中9个特征为符号型，其余为数值型；Shuttle是一个有关航天飞机的数据集，由澳大利亚悉尼大学计算机科学系Jason Catlett采集并捐赠，包含9个数值型特征.

4.2 数据集预处理

(1) 数据集拆分：将数据集拆分为符号型特征、数值型特征标签.

(2) 符号型特征数值化：采用one-hot编码将符号型特征数值化.如：协议类型中icmp编码为[1，0，0]，tcp编码为[0，1，0]，udp编码为[0，0，1].one-hot编码让特征之间的距离计算更加合理.

(3) 特征降维：使用MDS算法对数值化的符号型特征降维.由于one-hot编码扩充了特征维度，特征空间显著增大，因此选用MDS(多维缩放)算法做降维处理.

(4) 特征合并：将降维后的特征与原本的数值型特征合并.

(5) 归一化处理：为了将数据缩放到一定范围内，使得不同量级的数据能进行比较和加权，还需对特征进行归一化.

(9)

其中：max(xj)表示第j维特征所有样本的最大值，min(xj)表示第j维特征所有样本的最小值.

Shuttle数据集由于没有符号型特征，故只需执行步骤(5)即可.

4.3 数据集划分

预处理后的数据集全部归一化到0至1的范围内.由于后续步骤需要对SAE和LOF分别处理，并用神经网络将其结合，故需对数据集进行划分(见表1).数据集划分情况如下：

数据集A：随机抽取50%的正常样本数据；

数据集B：33.3%的正常样本数据和少量异常样本数据；

数据集C：剩余正常样本数据和少量异常样本数据.

数据集B和C中异常样本占比3%.数据集A用于训练SAE；数据集B用于测试SAE、LOF，进而训练神经网络；数据集C用于测试神经网络，并根据测试结果预测离群点.

表1 数据集划分

4.4 实验性能评估指标

常见的性能评估指标有精度(Accuracy，acc)、错误率(Error rate，er)、受试者工作特征(Receiver Operating Characteristic，ROC)、AUC(Area Under ROC Curve)[19-20].

精度是预测正确的样本数占总体样本数的比例，错误率是预测错误的样本数占总体的比例.公式为：

(10)

(11)

其中：m为样本容量，f(xi)为第i个样本的输出，yi为第i个样本的标签，∏(x)为指示函数，当x取真、假时分别为1和0.

另外，根据真实标签与预测结果，可计算出真正例(TP)、假反例(FN)、假正例(FP)、真反例(TN).分类结果的混淆矩阵如表2所示.

表2 分类结果的混淆矩阵

根据表2可以计算出真正例率(TPR)，假正例率(FPR)：

(12)

(13)

为了寻找TPR与FPR的关系，进而衡量模型性能，本文先根据预测结果对样本倒序排列，把分类阈值设到最大，将所有样本预测为反例，然后依次将每个样本预测为正例.第一轮描点(FPR，TPR).此后每一轮按公式计算：假设上一轮描点(x，y)，如果当前点为真正例，则描点(x，y+1/m+)，否则描点(x+1/m-，y).其中m+为真实正例个数，m-为真实负例个数.公式为：

(14)

(15)

以x_fpr和y_tpr分别为横、纵坐标，即可描绘出ROC曲线图.ROC曲线与x轴之间的面积为AUC，可以估计为

(16)

一般认为，AUC越接近1，模型的性能越好.

4.5 实验结果及分析

为了验证SAE-LOF算法的有效性，本文将其与SAE算法、LOF算法、KNN算法、孤立森林(iForest)算法进行对比，比较各自的acc、er、AUC指标，并绘出ROC曲线图.

表3展示的是不同模型在KDD-CUP99和Shuttle 2个数据集下的精度acc、错误率er以及运行时间.由表3可知，对于KDD-CUP99数据集，SAE与LOF的结合与SAE、LOF、KNN、iForest相比，样本分类的精度分别提升了3.66%，0.91%，3.05%，4.88%；对于Shuttle数据集，样本分类的精度分别提升了2.57%，0.27%，2.41%，1.03%.分类错误的概率降低了同等的百分比.

相比于SAE算法、LOF算法和iForest算法，SAE-LOF算法的运行时间有所增加，但比KNN算法的时间大幅度降低.这是因为SAE-LOF算法对SAE算法和LOF算法进行了融合，训练时间有所延长.虽然运行时间较长，但是检测精度有明显提升，所以仍有一定的研究价值.

表3 不同模型acc、er对比

图5和6是不同模型的ROC曲线图.其中图5是KDD-CUP99数据集，计算ROC曲线与x轴围成的面积可得SAE、LOF、KNN、iForest、SAE_LOF模型的AUC值，分别为0.963 7，0.948 4，0.956 5，0.878 2，0.996 5.图6是Shuttle数据集，SAE、LOF、KNN、iForest、SAE_LOF模型的AUC值分别为0.907 3，0.980 0，0.762 2，0.932 1，0.987 2.由此可见，SAE-LOF算法的AUC值高于其余4种算法，该算法在性能上超越了其余4种算法，从而验证了该算法的有效性.

图5 KDD-CUP99 ROC曲线

5 结束语

本文首先介绍了基于自编码器的离群点检测算法SAE和基于密度的离群点检测算法LOF.其次，针对SAE和LOF检测精度不高的问题，提出了将SAE和LOF相结合的SAE-LOF算法.SAE-LOF算法将SAE的重构误差与LOF的局部离群因子作为新的特征输入到神经网络，进行有监督的训练，进而预测离群点.该算法在2个公开数据集上进行实验，实验结果与SAE算法、LOF算法、KNN算法、孤立森林算法进行比较.结果表明，SAE-LOF算法的预测结果具有更高的精度、更低的错误率以及更高的AUC值.这表明该算法显著提高了分类器的性能.

但该算法还有很多提升空间.在数据量爆炸式增长的今天，如何分析海量数据内部规律，进而检测出离群点，成了一个亟待解决的难题.而对于大规模数据集，该算法只能随机抽取部分样本做成新的数据集，再进行训练和预测，因此需要进行研究和改进.另外，本文使用了算法融合的方法，虽然提高检测精度，但也延长了训练时间.所以怎样在保证精度的情况下缩短训练时间，也是今后要改进的问题，