,1,*, 李易1FINFLO: A New Fast Local Outliers Detection Algorithm
YANG Xiaolin1,2, LI Jingjing,1,*, LI Yi1通讯作者: 李菁菁（E-mail:jjli@cnic.cn）
收稿日期:2020-08-8网络出版日期:2020-12-20
Received:2020-08-8Online:2020-12-20
作者简介 About authors
杨校林,中国科学院计算机网络信息中心,在读硕士研究生,主要研究领域为聚类与异常点检测,智能网络运管分析技术等。本文中承担的任务是算法设计、实验设计与文献撰写。
YANG Xiaolin is a graduate student in Computer Network Information Center of Chinese Academy of Sciences. His main research areas are clustering and anomaly detection, and intelligent network operation and management analysis technology. In this paper, he is responsible for the algorithm design, experiments design and paper writing. Email:
李菁菁,中国科学院计算机网络信息中心,高级工程师,硕士生导师。主要研究领域为未来网络体系结构,大规模云基础设施智能监测感知,智能网络运管分析技术等。主要负责中国科技网全网及超大型信息系统的设计、建设和长期运管等工作。主持和参与了多项发改委、科技部、国家自然科学基金委的重点课题和中国科学院信息化专项工程建设项目。本文中负责思路解析和总体统稿。
LI Jingjing is senior engineer and master tutor of Computer Network Information Center of Chinese Academy of Sciences. His main research areas are future network architecture, large-scale cloud infrastructure intelligent monitoring and perception, and intelligent network operation and management analysis technology. In this paper, he is responsible for the idea analysis and overall draft.
李易,中国科学院计算机网络信息中心,工程师,长期从事科技网核心网运维工作,对核心网运维和优化有丰富的经验。现在主要负责科技网核心网网络优化和监控系统方面的设计、建设和DNS运维及负载均衡建设工作。参与了科技部和中国科学院信息化专线工程建设项目。本文中负责数据整理。
LI Yi is an engineer of Computer Network Information Center of Chinese Academy of Sciences. He has long been engaged in the operation and maintenance of the core network of the science and technology network, and has extensive experience in the operation, maintenance and optimization of the core network. In this paper, he is responsible for data preparation.E-mail: liyi@cstnet.cn
摘要
【目的】基于局部密度的LOF算法时间复杂度高,且容易将处于簇边缘的正常对象误判成异常对象,INFLO算法引进反向k-近邻解决LOF算法这一缺陷,但是计算每个对象的局部异常因子时都会使用反向k-近邻没有必要且耗费时间。【方法】通过对两个算法的分析,本文改进了INFLO算法,提出了一种快速异常点检测算法FINFLO( faster Influenced outlierness),该算法的主要思想是：计算对象的局部因子时尽量避免考虑反向k-近邻对象,尽可能地只利用k-近邻对象。首先,计算出所有对象的反向k-近邻对象个数的均值,然后在计算对象的局部异常因子时,如果对象的反向k-近邻对象个数不小于所有对象的反向k-近邻对象个数均值,则只需要考虑对象的k-近邻对象,否则需要同时考虑k-近邻对象和反向k-近邻对象。【结论】实验结果显示,该算法能够提高离群点检测的精度,降低时间复杂度,实现有效的局部离群点的检测。
关键词：
Abstract
[Objective] Local density based LOF algorithm has high time complexity, and it tends to misjudge the normal objects at the edge of the cluster as exceptions. The inverse k-nearest-neighbor algorithm is introduced to solve the problem of LOF algorithm in INFLO algorithm. However, it is unnecessary and time-consuming to use the inverse k-nearest-neighbor when calculating the local outlier factor of each object. [Methods] Through the analysis of the two algorithms, this paper proposes a new fast anomaly detection algorithm, named Faster Influenced Outlierness, FINFLO. When calculating the local factors of objects, FINFLO tries to avoid considering reverse k-nearest neighbor objects, and use only k-nearest neighbor objects as much as possible. If the number of reverse k-nearest neighbor objects is not less than the mean of all reverse k-nearest neighbor objects, only k-nearest neighbor objects need to be considered, otherwise reverse k-nearest neighbor objects need to be considered. [Conclusions] Experimental results show that the algorithm can improve the accuracy of outlier detection, reduce the time complexity, and achieve effective local outlier detection.
Keywords：
PDF (5882KB)元数据多维度评价相关文章导出EndNote|Ris|Bibtex收藏本文
本文引用格式
杨校林, 李菁菁, 李易. FINFLO：快速局部异常点检测算法[J]. 数据与计算发展前沿, 2020, 2(6): 82-89 doi:10.11871/jfdc.issn.2096-742X.2020.06.009
YANG Xiaolin, LI Jingjing, LI Yi.
引 言
Hawkins对离群点的本质做如下定义：离群点是数据集中偏离大部分数据的数据,由于偏离其它数据太多,使人怀疑这些数据的偏离并非由随机因素产生,而是产生于完全不同的机制[1]。离群点检测是数据挖掘领域中的一项重要技术,目的是在大量且复杂的数据集中剔除噪音并保留有意义的数据点。离群点检测被广泛应用在网络监控、金融欺诈、数据清洗、电子商务、故障检测、天气预报、医药研究、信用贷款等众多领域。迄今为止,众多科研人员已经提出很多的离群点检测相关算法,大致分为如下四类：基于统计模型、基于距离模型、基于密度模型和基于偏离模型[2]。随着人工智能和模式识别的兴起,越来越多新颖的算法被提出,越来越多的应用被落实[3],例如,基于模糊粗糙集的离群点检测算法[4]和利用自组织映射离群点检测技术[5],文献[6]提出了一种基于深度信念网络的多类支持向量机入侵检测方法,该方法可以有效缩短分类器的训练时间,同时提高入侵异常点的分类准确率,文献[7]将迁移学习应用在时序数据离群点检测并取得了良好的结果,Rivero等人[8]应用决策树获取元数据,然后将新网络攻击类别映射为高斯流型中的数据对象,计算新类别与已知类别之间的距离,该方法可以很好的检测出新的网络攻击类别。基于统计模型的算法要求知道关于数据集合参数的知识,比如数据分布,但是在大多数情况下数据分布是未知的。为了改进基于统计模型算法的缺陷,科研人员引进了基于距离的异常检测算法,这种算法可以不需要预先知道数据的分布模式,也可以很好的适应高维度数据集,但是基于距离的异常点检测算法只能发现全局的异常对象,无法发现局部的异常对象,同时有科研人员引进分布式计算方式加速异常点检测的计算[9]。Breunig 等人在 2000 年提出了基于局部密度的离群点检测算法 LOF[10],LOF算法基于每个对象和它的k-近邻对象的局部可达密度计算局部异常因子,并将局部异常因子与自然数1比较,大于1可能是异常数据点,小于1则是正常点。Jin W.等人提出了INFLO算法[11],该算法在计算对象的局部异常因子时同时考虑了对象的k-近邻对象和反向k-近邻对象,从而避免了算法对分布在簇边缘的对象的误判。但是INFLO算法的时间复杂度很高,需要频繁查找对象的反向k-近邻对象。除此之外,还出现了很多借鉴LOF算法思想计算局部异常度的度量方法,比较典型的有计算基于连接的异常系数的COF算法[12],局部空间异常测度SLOM算法[13]和基于局部信息熵的加权子空间离群点检测算法[14]。基于偏离模型的算法也借鉴了基于局部密度的LOF算法,有多粒度偏差系数MDEF算法[15]等。这些算法的时间复杂度高,算法的精确度依赖用户指定的参数。岳峰等于2007年提出基于反向k-近邻的孤立点检测算法ODRKNN[16],该算法认为数据点的反向K近邻个数越少,说明它的偏离程度越大,数据点越有可能是一个异常点,但是该算法在数据量大且维度高的情况下,算法就会出现误差。
本文改进了INFLO算法,提出了一种基于局部密度的快速异常点算法FINFLO,因为数据对象的k-近邻对象和反向k-近邻对象不是对称的,频繁计算数据对象的反向k-近邻对象是非常耗时的。所以本文算法计算对象的局部异常因子时在符合给定条件时不会同时考虑对象的k-近邻对象和反向k-近邻对象,由此计算出来的数据对象的局部异常因子仍然可以高效地定位局部异常对象,且效率大大提升。并且在多簇环境下,该算法的精确度并没有降低,仍然可以适应于多簇环境中。
1 预备知识
1.1 LOF算法
Breunig等人在 2000 年提出了基于局部密度的离群点检测算法 LOF,该算法会计算出对象的局部异常因子表征对象的离群程度,不是二值性表示,而是一种趋向性表示。LOF算法通过比较每个对象p和其k-邻域对象的密度来判断该对象是否为异常,这样允许出现对象分布不均匀、密度不同的情况。对象p的局部密度越低,越有可能是异常点。即若对象p距离其他对象偏离较远,其k-邻域内邻居大多数对象的局部可达密度相对较大,对象p的局部可达密度相对较小,计算得出对象的局部异常因子较大。算法中的基本定义如下：
定义1（k-邻近距离 k-distance）：在距离对象p最近的几个对象中,第 k个最近的对象o与对象p之间的距离称为对象p的k-邻近距离,记为 k-distance (p),其中对象o满足以下条件：
（1）至少存在k个对象o'$\epsilon$ D\{p},使得d(p,o')≤d(p,o);
（2）至少存在k-1个对象o'$\epsilon$ D\{p},使得d(p,o')<d(p,o);
定义2（可达距离 reachability distance）：可达距离的定义和k-邻近距离是相关的,给定参数k时,对象p相对于对象o的可达距离 reach-distance（p, o）为对象o 的k-邻近距离和对象p与对象o之间的直接距离的最大值。即：
reach-distancek(p,o)=max(k-distance(o),d(p,o))
定义3（局部可达密度 local reachability density）：对象p 的局部可达密度为它与邻近的对象的平均可达距离之和的倒数,即：
$lrd_{k}=\frac{\sum{O \epsilon N(p,k)}{}reach-distance_{k}(p,o)}{|N(p,k)|} -1$
定义4（局部异常因子 local outlier factor）：局部异常因子是用局部相对密度来定义的。对象p 的局部相对密度（局部异常因子）为对象p的k-近邻的平均局部可达密度跟数据点p的局部可达密度的比值,即：
$lof_{k}(p)=\frac{\sum{O \epsilon N(p,k)}{}\frac{lrd_{k}(o)}{lrd_{k}(p)}}{}}{|N(p,k)|}$
1.2 INFLO算法
LOF算法仅仅适用于单簇数据分布环境,对多簇数据判定时极易出现误判。Jin W.等人针对LOF算法的缺陷,提出了INFLO算法, INFO算法计算对象的局部异常因子时不仅仅考虑了对象的k-近邻对象,还考虑了对象的反向k-近邻对象。同时,INFLO算法计算得出的局部异常因子也是一种趋向性表示。INFLO算法计算对象局部因子的方法同LOF算法一致,但是在对象分布存在两簇甚至多簇时,INFLO算法的性能明显优于LOF算法。FINFLO算法计算对象的局部异常因子时同时考虑其k-近邻对象和反向k-近邻对象。如果对象是处于簇边缘的正常对象,它必然处于其他对象的k-近邻对象域中,因此其局部异常因子也会置于正常范围之内,也即小于1或接近于1。该算法的基本定义如下：
定义1（局部密度 local outlier density）：对象p的局部密度为其k-邻近距离的倒数,即：
$den(p)=\frac{1}{k-distance(p)}$
其中k-邻近距离同2.1 LOF算法中的定义1。
定义2（反向k-近邻 reverse KNN）：若对象q的k-近邻中包含对象p,则对象p的反向k-近邻中包含对象q,即：
$RNN_{k}(p)={q|q \epsilon N N_{k}(q)}$
定义3（影响域离群因子influenced outlierness）：对象p的影响域由其k-近邻和反向k-近邻组成,对象p的影响域异常因子为其影响域内对象的平均密度和它的局部密度的比值,即：
$INFLO_{k}(p)=\frac{den_{avg}(IS_{k}(p))}{den(p)}$
其中：
$den_{avg}(IS_{k}(p))=\frac{\sum_{o \epsilon IS_{k}(p)}{}den(o)}{|IS_{k}(p)|}$
2 FINFLO算法
2.1 算法思想
LOF算法计算对象的局部异常因子时只考虑了k-近邻对象,当对象分布存在两个及以上簇时,LOF算法容易将处于簇边缘的正常对象误判成异常。INFLO算法引进了对象的反向k-近邻对象来解决LOF算法的缺陷,但是此时算法在检索对象的反向k-近邻和计算局部异常因子时变得非常耗时。在现实生活中,数据对象分布中只有少量对象是分布异常,大多数的对象都是正常分布,且大多数对象都处于簇的内部,所以在计算对象的局部异常因子时,只有少量的对象才需要同时考虑k-近邻对象和反向k-近邻对象,这类对象一般分布在簇的边缘。FINFLO算法在不影响算法准确率的情况下,重新设计数据对象异常判定策略,尽量减少考虑数据对象的k-近邻的对象。2.2 基本概念
FINFLO算法在计算对象的局部异常因子时,如果对象的反向k-近邻对象个数不小于所有对象的反向k-近邻对象个数的均值,则仅需要考虑k-近邻对象,否则需要同时考虑反向k-近邻对象。FINFLO算法的基本定义如下：定义1（局部密度 local outlier density）：对象p的局部密度由两部分组成,一部分是其k-邻近距离的倒数,第二部分是底数为e,指数为负的k-邻近距离的指数：
$den(p)=\frac{1}{k-dist(p)}+e^{-k-dist(p)}$
定义2 （局部质心因子 local centroid factor）：对象p的局部质心因子表征该对象的局部正常程度：
$lcf=\frac{\sum{o \epsilon NN_{k}(p)}{}k-dist(o)}{k-dist(p)*NN_{k}(p)}$
定义3（局部异常因子 local outlier factor）：对象p的局部异常因子采用如下公式：
$lof= \begin{equation} \begin{cases} \frac{den_{avg}(IS_{k}(p))}{den(p)},RNN_{k}(p) < ave \\ \frac{den_{avg}(NN_{k}(p))}{den(p)}, else \end{cases} \end{equation}$
其中：
$ave=\sum{q \epsilon N(p,k)} \frac{RNN_{k}(p)}{|N(p,k)|}$
2.3 离群点判定策略
首先根据定义2判定数据对象的局部质心因子,如果该数据对象的局部质心因子大于等于1,说明它是其k-邻域的局部质心,其k-邻域的所有数据对象可以以它为中心点形成一个点簇,它位于该簇数据点最密集的地方,所以它一定不是局部异常点。同时,根据定义3计算局部异常值的计算方式,该点的局部异常值也一定会小于1。通过定义2可以找出所有的局部质心点,局部质心点一定是局部正常点,可以避免后续判定。如果数据对象的局部质心因子小于1,则不能认定该数据对象是局部正常点,需要进一步判定。根据反向k-近邻的定义,反向k-近邻与k-近邻并不是对称的,如果数据对象的反向k-近邻对象个数大于等于全局反向k近邻对象个数的均值,在计算局部异常因子时,不需要考虑数据对象的反向k-近邻,这是因为在多簇数据分布的环境下,大部分数据分布在簇内部,只有少量的数据分布在簇的边缘,计算簇内部数据对象的局部异常因子时不需要考虑其反向k-近邻,而簇边缘数据对象的反向k-近邻一定比簇内部的反向k-近邻对象数量少,所以,本算法取全局反向k-近邻对象数目均值作为阈值边界,避免外部经验值输入。
如果数据对象的反向k-近邻个数小于全局对象反向k-近邻数目均值,则必须同时考虑该数据对象的k-近邻对象和反向k-近邻对象。
具体的伪代码描述如下：
| Algorithm FINFLO: |
|---|
| Input: k, D, a threshold T |
| Output: label of p in D |
| Method: |
| 1. FOR each p in D DO |
| 2. Get its lcf based definition 2 on ; |
| 3. IF lcf > 1 THEN |
| 4. Label as a normal point; |
| 5. ELSE |
| 6. N = getRKNN(p); |
| 7. IF N > avg(RKNN) THEN |
| 8. Get its lof based on definition 3; // not consider its RNN; |
| 10. IF lof > = T THEN |
| 11. label p as an outlier; |
| 12. ELSE label p as a normal point; |
| 13. ELSE |
| 14. Get its lof based on defintion 3; 15. // must consider its RNN; |
| 16. IF lof > = T THEN |
| 17. label p as an outlier; |
| 18. ELSE label p as a normal point; 19. ENDFOR |
新窗口打开|下载CSV
3 实验分析
本节设计实验对LOF算法,INFLO算法以及FINFLO算法的执行效率和检测精准度进行分析。测试的硬件环境是CPU 1.8GHZ,主存8G,软件环境为：操作系统Microsoft Windows 10,编程语言为Python 3。测试所使用的数据集为KDD CUP 1999数据集,KDD CUP 1999 数据集使用的是DARPA 1998的原始数据,在DARPA 1998数据集的基础上进行了预处理,提取出了以“连接”为单位的每条记录。KDD CUP 1999数据集中的数据有40个属性,取其中的20个属性,具体为取9种TCP连接基本特征,9种基于时间的网络流量统计特征和2种TCP连接的内容特征,对其中的非数值性属性进行了数值化处理,对连续型属性进行离散化处理。其中每一条数据记录都是一条网络连接,每条网络连接被标记为正常连接或者异常连接,异常类型被分为4大类,共39种攻击类型。在所有数据集中,异常数据占全部数据的2%~3%。3.1 FINFLO算法的精确度和执行效率
为了对比LOF算法,INFLO算法和FINFLO算法的精确度和执行效率设计对比试验, 将KDD CUP 1999数据集作为实验数据集,评价算法性能的指标为真正的异常点占算法结果中返回的异常点的比值,比值越大,则算法的性能越好;同时算法的执行时间作为执行效率的指标,时间越短,算法的执行效率越高。算法的精确度公式为：$precision=\frac{Number of vorrect outliers}{|outliers|}$
KDD CUP-500数据中含有数据记录500条,维度为20,KDD CUP-1000数据集中含有数据记录1,000条,维度为20, KDD CUP-2000数据集中含有数据记录2,000条,维度为20。三组实验的结果如图1和图2所示,可以看出在每一组实验中,LOF的算法执行时间最长,FINFLO算法的执行时间最短,同时 INFLO算法结果的准确率和FINFLO算法的准确率是一样的,也是最高的。这是因为在LOF算法中计算数据对象的k-可达距离计算复杂,进而导致了数据对象局部密度计算耗时,同比之下INFLO算法和FINFLO算法在没有折损精度的情况下改进了数据对象局部密度的计算方式;同时可以看出,相比于INFLO算法,FINFLO算法在没有牺牲准确率的情况下,运行时间大大缩减,这是因为FINFLO算法计算数据点的局部异常因子时首先进行了剪枝操作,质心因子大于1的数据对象必然不是异常对象,同时符合条件的数据对象在计算局部异常因子时不会考虑反向k-近邻,这是因为KNN和反向KNN是不对称,如果一个数据对象处于高密集区域,该数据对象的反向KNN集合则非常大,计算时非常耗时且无用。
图1
新窗口打开|下载原图ZIP|生成PPT图1三种算法的准确率对比图
Fig.1Comparison of precision of three algorithms
图2
新窗口打开|下载原图ZIP|生成PPT图2三种算法的运行时间对比图
Fig.2Comparison of runtime of three algorithms
3.2 FINFLO算法的优化测试
在不同规模的数据集上设计实验,设置不同的K值测试FINFLO算法的性能。如图3所示,随着K值的增大,FINFLO算法在所有规模的数据集上的准确率也会增大,但是同时需要注意的是算法的执行时间也会随着K值的增大相应地延长。这是所有KNN相关算法都会遇到的问题,根据FINFLO算法的定义我们可以知道,随着K值的增大,数据对象的k-邻近距离会变大,在数据对象的k-近邻中包含的数据对象数量也会增大,相应的数据对象的反向k-近邻数量也会增大且k-近邻和反向k-近邻不是对称的,那么对象的邻居查找和局部异常因子计算的时间就会延长。因此在设置K值的时候,需要综合考虑机器的性能和数据规模以及对结果精确度的要求以获得最适合的结果。图3
新窗口打开|下载原图ZIP|生成PPT图3FINFLO算法在不同K值下的准确率
Fig.3Accuracy of FINFLO algorithm under different K values
同时我们还针对三种算法设计实验,在固定K值为5,数据维度为20的情况下测试不同数量的数据集运行时间,通过图4我们可以看出,随着数据量的增加,三种算法的运行时间都会增长。
图4
新窗口打开|下载原图ZIP|生成PPT图4三种算法在不同数目数据点下的运行时间对比图
Fig.4Comparison of runtime of three algorithms under different data points
4 结论与展望
离群点检测是知识发现中的一个活跃领域,相关技术被广泛应用在各种领域,在这些应用领域中研究离群点的异常行为能发现隐藏在数据集中有价值的知识。本文提出的一种基于局部密度的异常点检测算法——FINFLO算法,该算法在计算对象的局部异常因子之前会首先计算它的反向k-近邻对象数量和所有对象反向k-近邻均值之间的关系,然后确定是否要引入反向k-近邻,这大大缩短了算法的运行时间。通过实验证明,该算法能够提高离群点检测的精度,降低时间复杂度,实现有效的局部离群点的检测。科技网后台网管系统正在迈向自动化运维,该算法结合滑动窗口可以应用于流式数据异常点的检测与判断,有较大的应用前景。利益冲突声明
所有作者声明不存在利益冲突关系。参考文献 原文顺序
文献年度倒序
文中引用次数倒序
被引期刊影响因子
[M].
[本文引用: 1]
[J].
[本文引用: 1]
[J].
[本文引用: 1]
[J].
DOI:10.1016/j.fss.2006.08.004URL [本文引用: 1]
[J].
DOI:10.1109/69.991726URL [本文引用: 1]
[J].
[本文引用: 1]
[J].
[本文引用: 1]
[本文引用: 1]
[J].
[本文引用: 1]
[本文引用: 1]
[C].
[本文引用: 1]
[C].
[本文引用: 1]
[J].
[本文引用: 1]
[J].
[本文引用: 1]
[C].
[本文引用: 1]
[J].
[本文引用: 1]
