JAVA高级面试进阶训练营视频教程

admin

第七章、异常值检测（离群点挖掘）

概述：

        一般来说，异常值出现有各种原因，比如数据集因为数据来自不同的类、数据测量系统误差而收到损害。根据异常值的检测，异常值与原始数据集中的常规数据显著不同。开发了多种解决方案来检测他们，其中包括基于模型的方法(Model-based method)【也叫基于统计分布Distribution的】、基于相似度的方法(proximity-based method)【基于偏差Deviation的】、基于距离的（Distance-based method）以及基于密度的方法等(density-based method)。

        当考虑数据间的空间关系时，常用的检测方法有两种：基于图的异常检测(Graph-based outlier detection)、基于多维空间的异常检测(Multi-dimensional space-based outlier detection)

        异常值检测方法的分类：

                    

        异常值检测系统的输出可分为两类：一类是标记结果（labeled result），另一类是计分结果（scored result）【或者有序列表(an ordered list)】

1.统计方法和信用卡欺诈检测

    1.1 基于似然的异常值检测算法（基于统计方法或已有模型进行检测）

        异常值定义为不属于表示原始数据集的模型的对象，即该模型不会生成异常值。

        对于特定的数据集，在可采用的精确模型之间，有很多种可用的选择，比如高斯和泊松。如果使用错误的模型来检测异常值，那么正常的数据点可能会被错误地识别为异常值。除了应用单一的分布模型外，分布模型的混用也很实用。

        算法的核心思想：（参考风雪夜归子：https://blog.csdn.net/u013719780/article/details/48901183）

        统计学方法是基于模型的方法，即为数据创建一个模型，并且根据对象拟合模型的情况来评估它们。大部分用于离群点检测的统计学方法都是构建一个概率分布模型，并考虑对象有多大可能符合该模型。离群点的概率定义：离群点是一个对象，关于数据的概率分布模型，它具有低概率。这种情况的前提是必须知道数据集服从什么分布，如果估计错误就造成了重尾分布。异常检测的混合模型方法：对于异常检测，数据用两个分布的混合模型建模，一个分布为普通数据，而另一个为离群点。

        聚类和异常检测目标都是估计分布的参数，以最大化数据的总似然（概率）。聚类时，使用EM算法估计每个概率分布的参数。然而，这里提供的异常检测技术使用一种更简单的方法。初始时将所有对象放入普通对象集，而异常对象集为空。然后，用一个迭代过程将对象从普通集转移到异常集，只要该转移能提高数据的总似然（其实等价于把在正常对象的分布下具有低概率的对象分类为离群点）。（假设异常对象属于均匀分布）。异常对象由这样一些对象组成，这些对象在均匀分布下比在正常分布下具有显著较高的概率。

        优缺点：（1）有坚实的统计学理论基础，当存在充分的数据和所用的检验类型的知识时，这些检验可能非常有效；（2）对于多元数据，可用的选择少一些，并且对于高维数据，这些检测可能性很差。

    1.2 信用卡欺诈检测

        对于信用卡欺诈检测，主要包括两个应用，信用卡欺诈性申请和信用卡欺诈性使用。欺诈表示信用卡特定使用者的平均使用量行为异常，即用户的交易记录异常。

        这种异常值在统计上表示信用卡被盗用，在这种情形下，异常值的一些例子包括购买率高和非常高的付款额等。

        付款的地点、用户以及背景都是数据集中的可能属性。聚类算法是可能的解决方案。

2.基于邻近度的方法和活动监控——涉及手机的欺诈检测

    两种主要的基于邻近度的方法是基于距离的和基于密度的异常值检测算法。

    基于邻近度的方法：如果它远离大部分点，那么这一个对象是异常的。这种方法比统计学方法更一般、更容易使用，因为确定数据集的有意义的邻近性度量比确定它的统计分布更容易。一个对象的离群点得分由到它的k-最近邻的距离给定。离群点得分对k的取值高度敏感。如果k太小（例如1），则少量的邻近离群点可能导致较低的离群点得分；如果K太大，则点数少于k的簇中所有的对象可能都成了离群点。为了使该方案对于k的选取更具有鲁棒性，可以使用k个最近邻的平均距离。

    优缺点：（1）简单；（2）缺点：基于邻近度的方法需要O(m2)时间，大数据集不适用；（3）该方法对参数的选择也是敏感的；（4）不能处理具有不同密度区域的数据集，因为它使用全局阈值，不能考虑这种密度的变化。

    基于距离算法详细解析（2.1-2.3）： https://max.book118.com/html/2018/0708/6000102233001204.shtm

    2.1 NL算法

        嵌套-循环(Neted-Loop,NL)算法

        主要思想：假设N是数据集中的对象数，缓冲区的大小为数据集大小的B％，算法将整个缓冲区分成两个阵列，分别称为第一阵列和第二阵列。将数据集中的数据划分成块，每块大小为0.5B%。对象以块为单位读入阵列中，然后直接计算数据对象间的距离。第一阵列中的每个对象都有一个计时器，用于记录对象dmin邻域内的对象数目。某个计数器的值一旦大于一个异常的dmin邻域内最多对象数目M=N(1-pct),该计数器停止计数。

        NL算法具体步骤（摘自上面网址，因为要找，所以直接贴出来）：

        

        

    基于单元的算法分为两个：FindAllOutsM算法和FindAllOutsD算法

    2.2 FindAllOutsM算法

        此算法适用于检测存储于主存的数据集中的异常。

        FM算法使用了性质1~性质4（具体4个性质看上文链接）来检测异常和非异常，这种检测是以单元-单元为基础的，而不是以对象-对象为基础的，这样的目的将大量不可能是异常的对象排除，只有不满足性质4（的小性质）的单元才会进行对象-对象之间的处理。

    2.3 FindAllOutsD算法

        此算法适用于处理大型、磁盘数据集。

        FD算法的方法是挑选对象子集保存在主存中，将磁盘上的数据页分类。各类数据页按一定顺序读入，从而使读页次数最小化。被挑选的子集由映射到白色单元中的对象构成。这些对象称为白色对象，他们需要进行对象-对象的计算。白色单元中的对象数目被限定在M（判断是否异常的标准）以内。

    2.4 基于距离的算法（主要是上面的两种：NL算法+基于单元的算法）

    2.5 Dolphin算法（基于距离的算法）

        （网络上资料很少，暂不记录）

    2.6 活动监控和手机欺诈检测

        异常值检测的目的就是找到源数据集中不符合标准行为的模式。这里的数据集包含呼叫记录以及在于呼叫记录中的模式。

        对于每一个特定的领域，开发了许多特殊的算法。手机滥用称为手机诈骗。研究的主题就是呼叫活动或者呼叫记录。相关的属性包括但不限于，呼叫持续时间、呼叫城市、呼叫日以及各种呼叫服务的比率。

3.基于密度的方法和入侵检测

    异常值检测和表示(LOF、LRD等概念和应用在链接内有很清晰的表述): https://www.cnblogs.com/bigmonkey/p/11052019.html

    这里使基于LOF(Local Reachability Density,LRD 局部可达密度)、LRD(Local Outlier Factor,LOF 局部异常因子)等概念的异常值形式化的正式定义。一般来说，异常值是指一个数据点偏离其他数据点太多以致它似乎不是来自相同的分布函数，而其他数据点都是来自相同的分布函数。

    3.1 OPTICS-OF算法

        该算法利用了 squeezer 算法对矩阵进行分析

        相关资料没有，论文也没有找到将此算法的，但是找到了一个《基于OPTICS和IncLOF的异常数据挖掘算法》的论文。

        有兴趣可以直接百度。

    3.2 高对比度子空间算法（High Contrast Subspace,HiCS）

        具体参看江苏大学的一篇硕士学位论文(讲的很多，很全面)：《基于高对比性子空间的离群点挖掘算法研究》

    3.3 入侵检测

                                    

4.基于聚类的方法和入侵检测

    基于聚类算法的异常值检测技术的策略专注于数据对象和类之间的关系。

    4.1 层次聚类检测异常值

        使用层次聚类算法的异常值检测基于k最近邻图。

        （具体参看前面的第四章的kNN算法）

    4.2 基于k均值的算法

        使用k均值算法的异常值检测的具体过程：

        阶段一、数据准备

            ①应该调整目标观测值和属性以便提高k均值聚类算法的结果和性能的准确性。

            ②如果原始数据集有缺失数据，那么必须对它们处理。将EM算法估计的最大似然数据作为输入来填补缺失数据。

        阶段二、异常值检测程序

            ①应该确定k值以便运行k均值聚类算法。确定合适的k值要参考立方聚类准则(Cubic Clustering Criterion)的值。

            ②k均值聚类算法根据所确定的k值运行。完成后，专家检查聚类结果中的外部和内部异常值。如果其他组的异常值的消除更有意义，那么他就停止该程序。如果其他组需要重新计算，那么他就再次运行k均值聚类算法，但不包括已检测的异常值。

        阶段三、审查和验证

            上一阶段的结果只是这个阶段的一个候选结果。通过考虑领域知识，可以找到真正的异常值。

    4.3 ODIN算法

        使用入度数的ODIN算法(indegree number)的异常值检测基于k最近邻图。

        算法基本过程：设置T为入度阈值

        对S进行计算生成KNN图，对于图内的节点i，如果节点i的入度小于阈值T，则标记此节点为离群点。

5.基于分类的方法和监控网络服务器的性能

    分类算法可以用来检测异常值。普通的策略仅针对训练数据集中的正常数据点训练一类模型，没有被该模型接受的任何数据点都表及为异常值。

    5.1 OCSVM算法

        一类支持向量机(One Class SVM,OCSVM)算法将输入数据投影到高维特征空间。随着该过程的进行，它反复发现最大间隔超平面。超平面（hyperplane）定义在高斯再生核Hilbert空间(Gaussian reproducing kernel Hilbert space)中，它最好地将训练数据从原始数据中分离出来。

        详细算法解析（引自知乎习翔宇）： https://zhuanlan.zhihu.com/p/32784067

    5.2 一类最近邻算法

        该算法基于k最近邻算法。

    5.3 监控网络服务器的性能

        网络服务器性能测试对于业务和操作系统管理是非常重要的。这些测试的形式可以是CPU使用率、网络带宽和存储等。

        数据集成来自各种渠道，比如基准数据、日志等。在网络服务器监控期间出现的异常值类型有点异常值（point outlier）、下文异常值（contextual outlier）和集体异常值(collective outlier)。

6.文本的新奇性检测、话题检测与上下文异常值挖掘

    6.1 条件异常值检测算法（Conditional Anomaly Detection,CAD）

    6.2 文本的新奇性检测与话题检测

        异常值检测的一个应用就是从来自报纸的文档或者文章中找出新奇的话题。主要检测包括观点检测，这主要是从很多观点中找出一个不寻常的观点。

7.空间中的集体异常值

    给定一个数据集，如果相关数据实例的集合相对整个数据集是异常的，那么就将他们定义为集体异常值。

    7.1 路径异常值检测算法（Route Outlier Detection，ROD）

        网络上几乎没有提到的

    7.2 集体异常值的特征

        集体异常值表示与输入数据集相对比不正常的数据集合，作为主要特征，只有同时出现的数据集合才将是集体异常值，但该集合中的具体数据本身不会与绝对不是异常值的数据集合中的其他数据一起出现。集体异常值的另一个特征是它可以是上下文异常值。集体异常值可能是序列数据、空间数据等。

8.高维数据中的异常值检测

    高维数据中的异常值检测有一些特征，使得它与其他异常值检测问题不同。

    8.1 Brute-Force算法（蛮力算法）

        匹配效果较好，但是速度慢

        参考解析： https://www.cnblogs.com/coder2012/p/3279916.html

    8.2 HilOut算法

        这个网上资料甚少。

        在这里推荐一篇硕士论文：《高维数据空间中离群点检测算法的研究》——吴晓燕（知网上有，可以去搜索学习一下）

        这篇文章对离群点的挖掘给出了比较详细的介绍，尤其是对高维空间的离群点挖掘作了大量介绍，也给出了一些算法，感兴趣可以学习。