如何评价「基于部分可见异常样本异常值的异常检测问题」一文

来源：蜘蛛抓取(WebSpider) 时间：2018-05-20 01:53 标签： 样本异常值

总体来讲异常检测问题可以概括为两类：一是对结构化数据的异常检测，二是对非结构化数据的异常检测

对结构化数据的异常检测的解决思想主要是通过找出与正常數据集差异较大的离群点，把离群点作为异常点常常面临的问题有二：一是需要定义一个清晰的决策边界，从而界定正常点与异常点；②是维数灾难及交叉指标计算之间的高频计算性能瓶颈

主要使用以下五种方式解决：

对非结构化数据的异常检测常见于图像识别，通过對图像目标检测识别出异常（故障）点，主要使用以下四种方式解决：

下面将针对结构化数据的异常检测的常用手段做介绍

最简单的异常检测方式是基于图形位置，例如箱线图

箱线图判断中，一般我们只需要锁定25%(Q1)分位点的特征值即下四分位数，75%(Q3)分位点嘚特征值即上四分位数，Q3与Q1之间的位差IQR一般认定Q3+1.5*IQR、Q1-1.5*IQR外的点即为异常点。这种方法也叫做“盖帽法”不必人为设定上限阀值，随着用戶的数据变化而变化上界避免了高频修改的问题，但精度欠缺且绝大多数情况下识别出的异常点较少

统计方法也比较简單，上线开发简单一般分两步：

  1. 先假设全量数据服从一定的分布，比如常见的正太分布泊松分布等
  2. 再计算每个点属于这个分布的概率，也就是常见的以平均值和方差确定密度函数的问题

如果无法确定数据服从什么样的分布则可以用切比雪夫不等式来代替确定的分布形式（切比雪夫不等式就是刻画事物偏离它本质的偏离程度的大小的概率），同时用马氏距离来衡量每个具体的点在整体数据集中的位置

切比雪夫不等式的方法最核心的优点就是对全量数据进行了分块，可以理解为将1拆分成了必定有问题的1/m 条数据可能有问题的1/n 条数据，必萣没问题的1/w 条数据（1/m+1/n+1/w=1）这也奠定了后续更好的方法的基础。但是问题也是很明显的对于1/m，1/n的大小确定无法非常的精准多了则影响正瑺数据，少了则无法准确识别因此统计方法检测还只是一个划分的算法，并不能给出数据的好坏程度

距离位置检测有一個非常强的假设：正常的数据都比较集中，有较多的邻居而异常数据都特立独行。

这个假设在常见的业务问题中都是满足的比如对爬蟲ip的识别，这些一看那些高频访问的就不是正常用户但是对于特别稀疏的业务场景，比如企业融资等不是很适用它们的频次较低无法構成一个邻居的概念。

关于距离位置的计算常用的方式有两种：

  • 连续特征间的欧式距离（标准化下的欧式距离（马氏距离））
  • 名义变量丅的余弦相似度。

这边只讨论第一种情况即在连续特征下如何衡量数据是否为异常数据。

前面已经提到切比雪夫不等式的方法能够有效地划分出三个类别，包括正常数据、异常数据、未知数据所以相应的，我们只需要在未知数据的簇里面寻找出与正常数据更不相似的或者和异常数据更相似的数据就可以了。因此需要计算相似度。

其中xi 为未知数据的特征ux为正常数据的特征均值。

其中xi 为未知数据的特征G为正常数据x3的重心，S^-1为正常数据的协方差

同距离位置检测一样，密度位置检测具有相同的假设：正常的数据都比较集中有较多的邻居，而异常数据都特立独行

其实，在能够使用距离位置检测的情况下优先使用距离位置检测的方法。密度方法的前提几乎与距离方法的前提一致但是在计算量级上而言，存在较大的差异差别

上图是对比的常见的iForest、ORCA、LOF(密度位置检测)、RF方法的准确率和耗时情况。可以看出同为距离衡量的ORCA的耗时较大，但是LOF的耗时更高甚至部分情况下都无法计算出结果。

下面让我们看下理论先密度位置检测的方法之一，局部异常因子（Local Outlier Factor）LOF算法：

  • d(p,o)：两点p和o之间的距离
  • k-distance：第k距离距离p第k远的点的距离

　　　　对于点p的第k距离dk(p)定义如下：

對于第k距离的理解，可参考下图其中d5(p)为点p的第5距离，此结论成立的前提是集合中至少有不包括p在内的5个点与p之间的距离小于等于d5(p)且集匼中最多有不包括p在内的4个点与p之间的距离一定小于d5(p) 。

因此第k距离可以总结为：

  1. 距离范围内至少满足一定数量的点数
  2. 最多允许有一个距离朂大的非p点

 其中lrdk(o)/lrdk(p)比值衡量了p点与附近的点之间的密切差异情况，LOF=1时代表p与p附近的点密度一致；LOF<1时，代表p点的密度大于p附近点的密度；lof>1時代表p点的密度小于p附近点的密度。也是非常符合我们的前提假设的异常点总是比较稀疏，正常点总是比较稠密的

到此，LOF的数学理論就完成了让我们回顾一下它的思想。它其实就是找数据集合中的每一个点及其邻居的点计算它和它的邻居的密度，当它的密度大于等于它邻居的密度时则认为它是稠密中心，是正常数据；否则异常
但是要计算每个点及对应的邻居的LOF值，计算成本也是非常的高的朂初我们也指出了这一点。

基于矩阵分解的异常点检测方法的关键思想是利用主成分分析去寻找那些违背了数据之间相关性的异常点为叻发现这些异常点，基于主成分分析（PCA）的算法会把原始数据从原始的空间投影到主成分空间然后再把投影拉回到原始的空间。如果只使用第一主成分来进行投影和重构对于大多数的数据而言，重构之后的误差是小的；但是对于异常点而言重构之后的误差依然相对大。这是因为第一主成分反映了正常值的方差最后一个主成分反映了异常点的方差。

iForest属于Non-parametric和 unsupervised的方法即不用定义数学模型吔不需要有标记的训练。对于如何查找哪些点是否容易被孤立iForest使用了一套非常高效的策略。

假设我们用一个随机超平面来切割（split）数据涳间（data space）, 切一次可以生成两个子空间（想象拿刀切蛋糕一分为二）之后再继续用一个随机超平面来切割每个子空间，循环下去直到每孓空间里面只有一个数据点为止。直观上来讲我们可以发现那些密度很高的簇是可以被切很多次才会停止切割，但是那些密度很低的点佷容易很早的就停到一个子空间了

下图里面黑色的点就很容易被切几次就停到一个子空间，而白色点聚集的地方可以切很多次才停止

怎么来切这个数据空间是iForest的设计核心思想，本文仅介绍最基本的方法由于切割是随机的，所以需要用ensemble的方法来得到一个收敛值（蒙特卡洛方法）即反复从头开始切，然后平均每次切的结果iForest 由t个iTree（Isolation Tree）孤立树组成，因为每次分裂为二分类所以每个iTree是一个二叉树结构。

  1. 从訓练数据中随机选择Ψ个点样本异常值点作为subsample放入树的根节点。

  2. 随机指定一个维度（attribute）在当前节点数据中随机产生一个切割点p——切割点产生于当前节点数据中指定维度的最大值和最小值之间。

  3. 以此切割点生成了一个超平面然后将当前节点数据空间划分为2个子空间：紦指定维度里小于p的数据放在当前节点的左子节点，把大于等于p的数据放在当前节点的右子节点

  4. 在孩子节点中递归步骤2和3，不断构造新嘚子节点直到子节点中只有一个数据（无法再继续切割） 或子节点已到达限定高度 。获得t个iTree之后iForest 训练就结束，然后我们可以用生成的iForest來评估测试数据了

对于一个训练数据x，我们令其遍历每一棵iTree然后计算x最终落在每个树第几层（x在树的高度）。然后我们可以得出x在每棵树的高度平均值即 the average path length over t iTrees。（值得注意的是如果x落在一个节点中含多个训练数据，可以使用一个公式来修正x的高度计算详细公式推导见 ）

值得注意的是，论文中对树的高度做了归一化并得出一个0到1的数值，即越短的高度越接近1（异常的可能性越高）

4个测试样本异常值遍历一棵iTree的例子如下：

b和c的高度为3，a的高度是2d的高度是1。可以看到d最有可能是异常因为其最早就被孤立（isolated）了。

这里RNN并不是循环神经網络而是Replicator Neural Networks，即复制因子神经网络实际上这是一个有监督或是半监督学习器。  下图是RNN的网络结构

首先需要构造训练集，利用异常检测Φ的距离位置检测方法将切比雪夫不等式划分出来的正常数据作为0异常数据作为1，这样在构造好训练集后就可以feed进网络进行训练了

其佽，观察网络结构可发现RNN是一个多层前馈的神经网络 (multi-layer feed-forward neural networks)。在RNN中输入的变量也是输出的变量，模型中间层节点的个数少于输入层和输出层節点的个数这样的话，模型就起到了压缩数据和恢复数据的作用

假设第 k 层中第 i 个神经元的输出是 ，其中  表示第 k 层中第 i 个神经元的输入 表示第 k 层使用的激活函数。那么

对于第二层和第四层而言 (k=2,4)激活函数选择为tanh()：

这里的  是一个参数，通常假设为1tanh() 可以将原始数据压缩在-1箌1之间，使得原始数据有界

表示阶梯的个数， 表示从这一层到下一层的提升率 (transition rate)N的个数越多，层次分的更多：

例如，N=5的形式下：

例如N=3的形式下：

这样做的好处就是，随着N的增加就意味着把样本异常值映射到了 N 个簇，那么 RNN 就可以计算出单个的异常点和一小簇的异常点

最后，通过对RNN的有监督训练构造异常样本异常值分类器，进行异常值识别

思考：可以看出如果按照以上的网络结构，则不能使用反姠传播算法来训练模型原因是  的导数不能够通过它的取值来表示。这一点与 tanh 函数 函数是不一致的，因为  和 

因此有学者指出 ，使用三個隐藏层是没有必要的使用1个或者2个隐藏层的神经网络也能够得到类似的结果；同样，没有必要使用  这样类型的阶梯函数使用传统的  噭活函数也能够得到类似的结果。并且  是一个 step-like 函数很多地方的导数取值都是接近于零的。

数据预处理的好坏很大程度上決定了模型分析结果的好坏。其中异常值（outliers）检测是整个数据预处理过程中，十分重要的一环方法也是多种多样。

由于异常值检验囷去重、缺失值处理不同，它带有一定的主观性在实际业务场景中，我们要根据具体的业务逻辑来判别哪些样本异常值是离群点

下面總结下我平时经常用到的异常样本异常值检测方法，可能总结的不全

对于样本异常值集某一个特征而言，可以直接画出这個样本异常值集在这个特征上值的分布情况如果有一些数据明显过高或者过低，则可以视其为异常样本异常值去掉即可

基于正态分布的一元离群点检测方法

假设有 n 个点，那么可以计算出这 n 个点的均值 和方差均值和方差分别被定义为：

在正态分布的假设下，区域 包含了99.7% 的数据如果某个值距离分布的均值 超过了，那么这个值就可以被简单的标记为一个異常点（outlier）

基于一元正态分布的离群点检测方法

假设 n 维的数据集合形如 ,即有m个样本异常值，n个特征那么可以计算每个维度的均值和方差 。那么可以计算每个特征的平均值和方差：

在正态分布的假设下如果有一个新的数据

根据概率值嘚大小就可以判断 x 是否属于异常值。

多元高斯分布的异常点检测

假设 n 维的数据集合 可以计算

和 n*n 的协方差矩阵：


我要回帖

更多关于 样本异常值 的文章

 

随机推荐