非监督学习算法:异常检测

什么是异常(outlier)?Hawkins(1980)给出了异常的本质性的定义:异常是在数据集中与众不同的数据,使人怀疑这些数据并非随机偏差,而是产生于完全不同的机制。聚类算法对异常的定义:异常是聚类嵌于其中的背景噪声。异常检测算法对异常的定义:异常是既不属于聚类也不属于背景噪声的点。它的行为与正常的行为有显著的不同。在某个季节里,某一天的气温很高或很低,这个温度数据就是一个异常。异常检测和分析是数据挖掘中一个重要方面,也是一个非常有趣的挖掘课题。它用来发现“小的模式”(相对于聚类),即数据集中间显著不同于其它数据的对象。异常检测具有广泛的应用,如电信和信用卡欺骗、贷款审批、药物研究、医疗分析、消费者行为分析、气象预报、金融领域客户分类、网络入侵检测等 。

一、异常检测方法的分类

  异常数据挖掘是一个非常有趣的研究课题,国内外关于这方面的已提出的算法文献非常多,这些方法大致分为四类:基于统计(statistical-based)的方法、基于距离(distance-based)的方法、基于偏差(deviation-based)的方法、基于密度(density-based)的方法。

  (一)基于统计的方法

  假设给定的数据集服从一个随机分布(如正态分布等),用不一致性测试(discordancy test)识别异常。存在问题是,在许多情况下,用户并不知道这个数据分布;而且现实数据也往往不符合任何一种理想状态的数学分布;即使在低维(一维或二维)时的数据分布已知,在高维情况下,估计数据点的分布是极其困难的。

 (二)基于距离的方法

  Knorr和Ng(VLDB’1998)提出一种基于距离的异常检测方法,基于距离的异常定义:数据集S中一个对象O称为DB(p,D)-outlier,如果它满足下列性质:数据集S中至少p*100%的对象与O的距离大于距离D。简单的说,基于距离的异常点就是那些没有“足够多”的邻居的对象。采取不同的参数p和D , DB(p,D)-outlier可以表示所有的基于统计的异常。基于距离的异常检测的算法又分为三个基本类型:基于索引(index-based)的算法、嵌套循环(nested-loop)算法、基于单元(cell-based)的方法。

 1.基于索引的算法

  寻找所有的DB(p,D)-outlier可以通过对最近邻查询或以O为中心的范围查询的回答来实现。基于多维索引结构R-Tree或kd-Tree算法复杂度是O(kN2 ),其中k为维数,N为数据点数。缺点:需要建立多维索引结构,时间复杂度大。

  2.嵌套循环算法NL

  将内存缓冲区空间划分成相等的两部分,数据集分成几个大小和每部分缓冲区相等的逻辑块,通过认真选择调入每一部分缓冲区的次序,使I/O次数最小算法复杂度是O(kN2)其中k为维数,N为数据点数。 特点:不需要建立多维索引结构,时间复杂度较大。

  3.基于单元的方法

  数据空间被划分为边长为D/(2k1/2)的单元;每个单元有两个包围层第一层为1倍的单元厚,第二层为int(2k1/2 -1)+1倍的单元厚确定异常,

  若cell_+_1_layer_count>M,单元中的对象都不是异常;

  若cell_+_2_layer_count<=M,单元中的所有对象都是异常;

  否则,单元中的一些对象可能为异常,逐个对象进行处理。算法复杂度是O(ck+N)。

  由于索引建立的开销很大,简单索引算法没有竞争性当k<=4时,基于单元的算法在N越大时优越性越明显当k>=5之后,嵌套循环算法开始显现出优势。

  4.基于距离的算法的改进

  Knorr和Ng(VLDB’1998)基于距离的异常检测方法的缺陷输入参数p与D很难确定,并且对于不同参数,结果有很大不稳定性。这就需要用户反复输入p与D进行测试,以确定一个满意解;不能给定异常的程度;算法的复杂度较高。Rastogi和Ramaswamy(SIGMOD’2000)提出了一个新的基于距离异常定义

  :Dnk 异常,用Dk(p)表示点p和它的第k个最近邻的距离,给定d维空间中包含N个点的数据集,参数n和k(自然数),如果满足Dk(p’)>Dk(p)的点p’不超过n-1个,那么称p为Dnk 异常。如果对数据点根据它们的Dk(p)距离进行排序,那么前n个点就被看作异常。循环嵌套算法(Nested-loop Algorithm),对每个点p,计算它的第k个最近邻的距离Dk(p),把具有极大Dk值前n个点作为异常。上面的算法每次处理一个点p,那么需要扫描一遍数据库,总共需要扫描N遍(N为数据点数)。 基于索引的算法(Index-based Algo?鄄rithm),用如R*-树的空间索引结构存储。基于划分的算法(partition-based Algorithm) ,如果某个点的Dk(p)较小的话,那么不可能是Dnk 异常,可以先对数据集进行划分,然后估计每个划分的Dk(p)的上、下界,如果能判定某个划分不可能包含异常的话,那么就可以直接把它删除掉;然后再从剩下的划分(侯选划分)来计算异常。现有的许多聚类算法可以用来划分数据集,如BIRCH。

  (三)基于偏差的方法

  Argrawal和Ragaran(KDD’1995)提出一种“序列异常”(sequential exception)的概念。算法介绍给定n个对象的集合S,建立一个子集序列{S1,S2,…,Sm},这里2≤m≤n,满足Sj-1

  (四)基于密度的方法

  距离异常的缺陷,基于密度的方法的有关概念对象p的k-距离(k-distance) 对任意的自然数k,定义p的k-距离(k-distance(p)),为p和某个对象o之间的距离,这里的o满足:

  至少存在k个对象o’∈D\{p},使得d(p, o’) d(p, o),并且至多存在k-1个对象o’ ∈D\{p},使得d(p, o’) < d(p, o)。 基于密度的方法的有关概念,

  1.对象p的k-距离邻域(Nk-distance), 给定p的k-距离k-distance(p),p的k-距离邻域包含所有与p的距离不超过k-distance(p)的对象。

  2.对象p相对于对象o的可达距离,给定自然数k,对象p相对于对象o的可达距离为:

  3. 对象p的局部可达密度(Local Reachable Dis?鄄tance),对象p的局部可达密度为对象p与它的MinPts-邻域的平均可达距离的倒数。

  4.对象p的局部异常因子(Local Outlier Factor), 局部异常的性质对象p的局部异常因子表示p的异常程度,局部异常因子愈大,就认为它更可能异常;反之则可能性小。簇内靠近核心点的对象的LOF接近于1,那么不应该被认为是局部异常。而处于簇的边缘或是簇的外面的对象的LOF相对较大。

  局部异常因子计算:第一步先产生所有点的MinPts-邻域(同时得到MinPts-距离),并计算到其中每个点的距离; 对低维数据,可以利用网格(Grid)来作k-NN查询,整个计算时间为 O(n );对中维或中高维数据,必须采用索引结构如X-树等,使得作k-NN查询的时间为O(logn) ,整个计算时间为 O(n logn);对特高维数据,索引结构不再有效,时间复杂度提高到O(n2)。第二步计算每个点的局部异常因子。

  二、算法小结

  基于统计的异常检测应用主要局限于科研计算,这主要是因为必须事先知道数据的分布特征这就限制了它的应用范围。 序列异常检测算法提出的序列异常的概念并没有得到普遍的认同。这是因为序列异常在概念上仍然有一定缺陷,遗漏了不少的异常数据。基于距离的算法跟基于统计的算法相比,不需要用户拥有任何领域知识。与“序列异常”相比,在概念上更加直观。更重要的是,距离异常更接近Hawkins的异常本质定义。基于密度的异常观点比基于距离的异常观点更贴近Hawkins的异常定义,因此能够检测出基于距离异常算法所不能识别的一类异常数据———局部异常。局部异常观点摈弃了以前所有的异常定义中非此即彼的绝对异常观念,更加符合现实生活中的应用。

  上述的异常检测算法是以静态数据集为研究对象,需要对数据集进行多次扫描,才能得到输出结果。在现实生活中,对动态的数据集,即流数据的在线处理的需求更为迫切,因此,只需进行一次扫描便得到结果的数据流异常检测算法,成为当前的研究热点。

原文发布于微信公众号 - 大数据挖掘DT数据分析(datadw)

原文发表时间:2015-09-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏深度学习计算机视觉

数据挖掘之认识数据学习笔记相关术语熟悉

相关术语熟悉 首先认识数据的属性 属性是一个数据字段,表示数据对象的一个特征 标称属性 标称属性的值是一些符号或事物的名称,这一些值可以看做是枚举的 比如,职...

2776
来自专栏Coding迪斯尼

使用自动编解码器网络实现图片噪音去除

在前面章节中,我们一再看到,训练或使用神经网络进行预测时,我们需要把数据转换成张量。例如要把图片输入卷积网络,我们需要把图片转换成二维张量,如果要把句子输入LS...

722
来自专栏人工智能LeadAI

机器学习实战 | 数据探索

数据的输入质量决定了输出的最后结果,数据的探索、预处理、特征选择、降维等特征工程占了项目的70%的时间。那么如果我们确定了商业目的,该如何一步一步渐进式进行特征...

3585
来自专栏IT派

教程 | 如何使用TensorFlow和自编码器模型生成手写数字

本文详细介绍了如何使用 TensorFlow 实现变分自编码器(VAE)模型,并通过简单的手写数字生成案例一步步引导读者实现这一强大的生成模型。 全部 VAE ...

35911
来自专栏kangvcar

[face_recognition中文文档] 第4节 Face Recognition API

1602
来自专栏磐创AI技术团队的专栏

TensorFlow系列专题(十一):RNN的应用及注意力模型

目前循环神经网络已经被应用在了很多领域,诸如语音识别(ASR)、语音合成(TTS)、聊天机器人、机器翻译等,近两年在自然语言处理的分词、词性标注等工作的研究中,...

701
来自专栏程序生活

机器学习(六)Sigmoid函数和Softmax函数1 Sigmoid函数2 Softmax函数

1 Sigmoid函数 1.1 定义 Sigmoid函数是一个在生物学中常见的S型的函数,也称为S型生长曲线。Sigmoid函数常被用作神经网络的阈值函数,将变...

2.7K5
来自专栏C语言及其他语言

【优秀题解】1175:台球碰撞

题号1174,原题见下图: ? 解题思路: 解题思路: 把台球看做质点(台球坐标不变,球桌坐标各个边界向里收缩R,得到新的球桌); 假设没边界,求出小球沿着直...

2776
来自专栏Brian

熵的理解

---- 熵 熵在信息论中代表随机变量不确定度的度量。一个离散型随机变量X的熵H(X)定义为: image.png 明确定义的科学名词且与内容无关,而且不随信息...

2956
来自专栏企鹅号快讯

K近邻算法的Python实现

作者:黄耀鹏人工智能爱好者,一名数据科学研究者及科普写作者 知乎专栏:https://zhuanlan.zhihu.com/data-science-medit...

3799

扫码关注云+社区