异常检测的数据挖掘方法

我们正淹没在从世界范围内收集的海量的数据里，同时我们也渴求知识

异常事件发生相对较少

然而，一旦发生，它们的影响将会很戏剧性，并且通常具有负面影响

"在草堆中找针，草是如些多，时间如此少"

什么是异常？

异常是数据中不满足期望行为的模式

也指离群点，异常值，特异性，惊奇性等

异常与现实生活中的实体对应

--网络入侵

--信用卡欺诈

--机械系统中的缺陷

真实世界中的异常

信用卡欺诈

-信用卡上的费用异常高的定单

网络入侵

-与FTP流量相关的WEB服务器

简单例子

N1和N2是正常行为范

点o1和o2是异常点

在区域O3中的点也是异常点

相关的问题

稀有类挖掘

发现机会

新奇事物检测

异常挖掘

消除噪声

黑天鹅

关键的挑战

定义一个具有代表性的正常区域很有挑战性

正常行为与边远行为的界限通常是不精确的

标记数据对于训练验证的有效性

异常的精确定义在不同的应用领域是不一样的

恶意的敌人

数据可能包含噪声

正常行为不断在演变

相关特征的适当选择

Aspects of Anomaly Detection Problem（异常检测问题的方面）

输入数据的性质

略。

指导的有效性

略。

异常类型

点异常

单独的数据实例是异常的

上下文异常

在一个上下文中单独的数据实例是异常的

需要一个上下文的概念

也被称为条件异常

集体异常

相关数据实例的集体是异常的

在数据实例间需要一个关系

-有序数据

-空间数据

-图数据

在一个集体异常中单独的实例，从它们自己看来并不是异常的

异常检测的输出

标记

-每一个测试实例给一个正常或异常的标记

-对基于分类的方法特别适用

得分

-每一个测试实例分配一个异常得分

允许排序输出

需要一个附加的阀值参数

异常检测技术的评估-F值

准确率对于评估来讲并不是充分的度量

-举例：网络流量数据集，具有99.9%的正常数据和0.1%的入侵数据

-简单的分类器（使用正常类型标记）可以达到99.9%的准确率

Applications（应用）

网络入侵检测

保险/信用卡欺诈检测

医疗信息/医学诊断

工业损伤检测

图像处理/视频监控

文本挖掘中的小说主题检测

Different Types of Anomaly Detection Techniques（异常检测技术的不同类型）

基于分类的技术

有指导的分类技术

半指导的分类技术

优势：

（1）有指导分类技术

模型好理解

在检测已经多类型的异常时，具有较高的精度

（2）半指导分类技术

模型好理解

正常行为能够精确地学习

劣势：

（1）有指导分类技术

需要正常与异常类型的两种标签数据

不能检测未知新出现的异常

（2）半指导分类技术

需要正常类型的标签数据

对未使用的正常数据，也可能以高的概率识别为异常

有指导的分类技术

操作数据记录（过抽样/欠抽样/人工产生异常【SMOTE】）

基于规则的技术【PN-rule, CREDOS】

基于模型的技术

基于神经网络的方法

基于支持向量机的方法

基于贝叶斯网络的方法

代价敏感的分类技术

基于总体的算法（SMOTEBoost，RareBoost，MetaCost）

半指导的分类技术

基于神经网络的方法

基于支持向量机的方法

基于马尔可夫模型的方法

基于规则的方法

基于最近邻技术

重要假设：正常点有近邻，而异常点离其它点很远

通常两步方法

1、计算每个数据记录的邻居

2、分析邻居决定数据记录是否异常

分类：

基于距离的方法：异常点是那些离其它点最远的点

基于密度的方法：异常点是处于低密度区域的点

优势：

可用于无指导或半指导的情形中（对数据的分布无任何假设）

劣势：

如果正常点没有充足的邻居数量，该技术可能会失败

运算量

在高维空间中，数据是稀疏的，相似性的概念也许不再有意义了。由于稀疏性，两个数据记录之间的距离也许变得很相似，这样每个数据记录也许会作为潜在的异常点被考虑

基于密度的方法

局部异常因子（LOF,Local Outlier Factor）

连接异常因子（COF,Connectivity Outlier Factor）

多粒度偏差因子（MDEF,Multi-Granularity Deviation Factor）LOCI

基于聚类的技术

主要假设：

正常数据属于大的稠密的聚类，而异常数据不属性于任何有效的聚类

常用方法：

将数据聚成有限数量的聚类

至于它的最近的聚类，分析每一个数据实例

异常实例：

不符合任何聚类的数据实例

小聚类数据实例

低密度数据实例

在同一个聚类中，离其它点很远的数据实例

优势：

无指导算法

存在的聚类算法可以被接入

劣势：

如果数据没有自然的聚类或聚类算法不能检测自然的聚类，该技术将失效

运算量大：使用索引结构也许会减轻该问题

在高维空间中，数据是稀疏的，两个数据记录间的距离也许会变得也很似

FindOut算法作为小波聚类(WaveCluster)的副产品

使用小波变换将数据转换成多维信号

高频信息符合聚类的分布边界快速改变的区域

低频部分符合数据集中的区域

移除这些高频和低频部分，所有剩下的点就是异常点

使用聚类进行异常检测

固定宽度的聚类首先被应用

第一个点是第一个聚类的中心

如果d(x1,x2)<=w，那么x1和x2是靠近的，其中w是用户定义的参数

如果每个随后的点是靠近的，增加到一个类，否则创建一个新的类

那些在小聚类中的点就是异常点

基于聚类的局部异常因子CBLOF

使用挤压聚类算法执行聚类

为每一个数据实例确定CBLOF

如果数据记录位于小聚类中，CBLOF=聚类的大小*该数据实例与最近的更大一点聚类的距离

如果数据记录位于大数据中，CBLOF=聚类的大小*该数据实例与该数据实例所属聚类的距离

基于统计的技术

主要假设：正常数据实例发生在统计分布的高概率区域，然而异常发生在统计分布的低密度区别

常用方法：使用给定的数据估计一个统计分布，然后应用一个统计推断检测来确定该检验的实例是否属性该分布

如果一个观测离样本的平均值超过3倍标准差，那么它就是异常的

优势：

利用现有统计建模技术对不同的分布类型建模

提供一种统计上合理的解决方案来检测异常值

劣势：

由于具有高维度，进行参数估计同时构建假设检验是很难的

假设的参数对真实数据未必有效

统计技术的类型

参数技术

假设正常数据（也有可能异常）产生自一个潜在的参数分布

从训练样本中学习参数

非参数技术

不会假设参数的任何知识

使用非参技术估计分布的密度

SmartSifter(SS)

具有连续与分类属性数据的统计建模

直方图密度用于表示分类属性的概率密度

有限混合模型用于表示连续属性的概率密度

对于一个测试实例，SS估计了由学习统计模型产生的测试实例的概率p(t-1)

接着，测试实例被加入样本，然后该模型将重新估计

由新模型产生的测试实例的概率为p(t)

对于测试实例的异常得分是|p(t)-p(t-1)|

对正常与异常数据建模

如下给出数据D的分布：

D=(1-x)*M+x*A

M代表主体分布；A代表异常分布

M，A分别代表正常与异常元素的集合

第1步：将所有的实例赋值给M，A初始化为空

第2步：对每个M中的实例xi

(1)估计M和A的参数

(2)计算分布D的log似然函数L

(3)从M中移走x，并且插入A

(4)重新估计M和A的参数

(5)计算分布D的log似然函数L'

(6)如果L'-L>a，那么x是异常值，否则从M中移除x

第3步：回到第2步

基于信息理论的技术

重要假设：异常值显著地改变了数据集的信息内容

常用方法：检测能够显著改变信息内容的数据实例

--需要一个信息理论度量

优势：

可以在一个无指导的模式下操作

劣势：

需要一个足够敏感的信息理论度量来检测由少数异常引起的不规则性

使用熵

找一个k大小的数据子集，该子集的移出，将导致整个数据集熵的最大减少

使用一个近似的线性查找算法以直线性的方式搜索k大小的子集

其它的信息理论度量已经被研究了，比如条件熵、相对条件熵、信息增益，等等

光谱技术

基于数据特征分解的分析

关键思想：

找到能够捕捉大部分变化的属性组合

属性的缩减集能够将正常的数据解释得很好，对于异常数据却不是必要的

优势：

在非指导模式下可以操作

劣势：

它是基于这样的假设，即异常和正常的实例在缩减后的空间中是可区分的

使用稳健的主成份分析

计算数据集的主成分

对每个测试的点，计算它在这些主成份下的投影

如果yi表示第i个主成份，那么如下有一个卡方分布

sum(<i=1,q>,yi^2/ai)=y1^2/a1+y2^2/a2+y3^2/a3+...+yq^2/aq,q<=p

如果对于一个给定的显著水平，满足如下条件，那么这个观测是异常的：

sum(<i=1,q>,yi^2/ai)>kfq^2(b)

另外一个观察最后几个主成份的度量是

sum(<i=p-r+1,p>,yi^2/ai)

对于以上的度量，异常点具有较高的值

PCA用于异常检测

一些主要的主成份，捕获了普通数据的可变性

最小的主成份对普通数据来说，应该有的常量值

异常值在最小的主成份中有变异性

使用PCA进行网络入侵检测

-对每个时间t,计算主成份

-随时间，堆积所有的主成份，形成一个矩阵

-矩阵的左奇异向量捕获了正常行为

-对于任意的t,主成份与奇异向量间的角度给出了异常度

基于可视化的技术

使用可视化工具观察数据

为人工检查提供数据的替代视图

更形象地发现异常点

优势

-圈定一个人

劣势

-对低维数据表现较好

-对于高维数据，在聚合或部分视图中，异常值也许是不可区分的

-对于实时异常检测不合适

可视化数据挖掘

检测电信欺诈

用图展现电话呼叫模式

用颜色标记出欺骗性的电话呼叫（异常）

上下文异常检测

检测上下文异常

重要假设：在一个上下文内的所有正常实例是彼此相似的（在行为属性方面），然而在同一个上下文中，异常实例与其它实例不同

常用方法：

-围绕一个数据实例，确定一个上下文（使用上下文属性的集合）

-确定测试数据在上下文中是否是异常值（使用行为属性集合）

优势：

-当在全局视图下分析时，可以检测那些很难发现的异常值

劣势：

-确定一个好的上下文属性的集合

-使用上下文属性确定一个上下文

上下文属性

上下文属性为每个实例定义了一个邻居（上下文）

举例：

-空间上下文：经度、纬度

-图上下文：边、权重

-有序上下文：位置、时间

-轮廓上下文：用户的人口统计资料

上下文异常检测技术

减少异常点检测

-使用上下文属性的分段数据

-使用行为属性在每一个上下文中应用一个传统的离群点异常

-通常，上下文检测 不能轻易地分段

利用结构数据

-使用上下文属性，从数据中建立模型

-关于它们的上下文，模型自动地分析数据实例

条件异常检测

每个数据点表示为[x,y]，这里的x表示上下文属性，y表示行为属性

nU高斯模型的混合，U从上下文数据学习而来

nV高斯模型的混合，V从行为数据学习而来

p(Vj|Ui)表示，当上下文部分由Ui产生时，行为部分由Vj产生的概率

一个数据实例[x,y]的异常得分：

集体异常检测

检测集体的异常值

挖掘数据实例间的关系

序列异常检测

-检测异常序列

空间异常检测

-在一个空间数据集中检测异常子区域

图的异常检测

-在图数据中检测异常子图

序列异常检测

多个子规则

-在序列数据库中检测异常序列

-在一个序列中，检测异常子序列

提纲

问题陈述

技术

-- 基于核函数的技术

-- 基于窗口的技术

-- 马尔可夫链的技术

实验评价

-- 实验方法

-- 数据集

-- 人工数据生成器

-- 结果

结论

动机和问题陈述

用于符号序列的几个异常检测技术已经被提出来了

-每个被提出的技术用于一个单独的应用领域

-对于跨领域的技术没有比较的评估

-这种评估对于区别技术的相对优劣势是必要的

问题陈述：给定一个具有n个序列的集合S，和一个查询序列Sq，为Sq找到一个关于S的异常得分

-在S中的序列假设是（或者大部分）正常的

该定义在如下的多领域是适用的

--飞行安全

--系统调用入侵检测

--蛋白质组，蛋白质组学

基于核函数的技术

定义序列间的一个相似核函数

--曼哈顿距离-对不同长度的序列不适用

--规范化最长共同序列

应用任何基于传统距离的异常检测技术

-CLUSTER

将普通序列聚成一个固定个数的聚类

测试序列的异常得分是与离它最近聚类中心相似性的倒数

-KNN

测试序列的异常得分是在普通序列数据中离它第k个最近邻居的相似性的倒数

基于窗口的技术（tSTIDE)

从测试序列中抽取有限长度的滑动窗口

对每一个滑动窗口，找到它在训练数据集中的频率

-对于滑动窗口来说，频率代表异常得分的倒数

组合每个窗口异常得分的异常得分，为测试序列得到全局的异常得分

马尔可夫链的技术

基于之前观察事件的条件，估计测试序列的每个事件发概率

组合每个事件的概率获得全局异常的得分

FSA

--事件概率是基于前L-1事件条件下的概率

--如果前L-1事件没有训练数据集中发生，该事件将被忽略

FSA-z

和FSA一样，只是当前L-1事件未发生在训练数据中时，该事件的概率为0

PST

-如果前L-1事件在训练集中未发生足够的次数，它们将会被最大的suffix替代，这里的suffix发生的次数超过了需要的阀值

Ripper

如果前L-1事件在训练集中未发生足够的次数，它将会被最大的subset替代，这里的subset发生的次数超过了需要的阀值

HMM

事件的概率，等于从训练集的学习生成的HMM中的相应的转移概率

在线异常检测

通常数据以流式的方式传达

应用

--视频分析

--网络流量监控

--飞行安全

--信用卡欺诈交易

挑战

异常需实时检测

什么时候拒绝？

什么时候更新？

-周期性地更新-一段固定的时间周期之后，模型更新

-插入每条数据记录，增量更新

需要增量建模更新技术重要训练模型，会很昂贵

-被动更新-模型只有当被需要的时候才会更新

模型更新的动机

如果正在到达的数据点开始创建一个新的数据聚类，该方法将不能检测这些点为异常点

增量的LOF和COF

增量LOF算法

-增量的LOF算法为每条插入的数据记录计算LOF值，并且立即决定是否该数据实例是一个异常点

-如果有必要的话，根据已存在的数据记录更新LOF值

增量COF算法

-为每个插入的数据记录计算COF值

-需要的话，更新ac-dist

分布式异常检测的必要性

在诸多异常检测应用中的数据来源不同

-网络入侵检测

-信用卡欺诈

-航空安全

同时发生在多位置失败，也许仅分析单独一个位置的数据并不能检测出来

-在如此复杂的系统中检测异常也许需要来自于单个位置的检测异常的信息集成，以在一个复杂系统全局水平上检测异常

用于异常相关和集成的高性能和分布式算法是必要的

分布式异常检测技术

简单的数据交换方法

-将数据融合到一个位置

-在分布式的位置间交换数据

分布式的近邻方法

-每一次距离计算交换一条数据记录-计算效率低下

-基于跨站点距离计算的隐私保护异常检测算法

基于模型交换的方法

-探索合适的统计或数据挖掘模型的交换，以致能描述正常或异常的行为

---区别普通行为的模式

---使用统计或数据挖掘学习模型描述这些模式

---跨多位置交换模型，在每一个的位置进行组合，以检测出全局的异常点

集中式和分布式体系架构

分布式异常检测算法

参数

-基于分布

-基于图

-基于深度

非参

-基于密度

-基于聚类

半参

-基于模型(ANN,SVM)

Case Study（案例研究）

略。

Discussion and Conclusions（讨论和结论）

异常检测能够在数据中检测出危急信息（临界信息）

在多个应用领域非常适用

异常检测问题的本质依赖于某个应用领域

需要不同的方法来解决一个特定问题的制定