基于大数据挖掘的离群点检测方法

1.统计学方法

离群点检测的统计学方法对数据的正常性做假定，假定数据集中的正常对象由一个随机过程（生成模型）产生。因此，正常对象出现在该随机模型的高概率区域中，而低概率区域中的对象是离群点。

离群点检测的统计学方法的一般思想是：学习一个拟合给定数据集的生成模型，然后识别该模型低概率区域中的对象，把它们作为离群点。有许多不同方法来学习生成模型，一般而言，根据如何指定和如何学习模型，离群点检测的统计学方法可以划分成两个主要类型：参数方法和非参数方法。

参数方法假定正常的数据对象由一个参数分布产生。该参数分布的概率密度函数给出对象被该分布产生的概率。该值越小，越可能是离群点。

非参数方法并不假定先验统计模型，而是试图从输入数据中确定模型。非参数方法的例子包括直方图和核密度估计。

（1）参数方法

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

假定数据集由一个正态分布产生，然后，可以由输入数据学习正态分布的参数，并把低概率的点识别为离群点。视具体情况而定，将其不同大小区域外的数据视为离群点。这种直截了当的统计学离群点检测方法也可以用于可视化。

②多元离群点检测

可以使用马哈拉诺比斯距离、统计量、混合参数分布检测多元离群点。

（2）非参数方法。使用直方图检测离群点包括如下两步：

第一步：构造直方图。尽管非参数方法并不假定任何先验统计模型，但是通常要求用户提供参数，以便用数据学习。如指定直方图的类型（等宽或等深的）和其他参数（如直方图中的箱数或每个箱的大小）。与参数方法不同，这些参数并不指定数据分布的类型（如高斯分布）。

第二步：检测离群点。为了确定一个对象是否是离群点，可以对照直方图检验它。在最简单的方法中，如果该对象落入直方图的一个箱中，则该对象被看作是正常的，否则被认为是离群点。

对于更复杂的方法，可以使用直方图赋予每个对象一个离群点得分。一般可以令对象的离群点得分为该对象落入的箱的容积的倒数。得分越高，表明是离群点的概率越大。

使用直方图作为离群点检测的非参数模型的一个缺点是：很难选择一个合适的箱尺寸。一方面，如箱尺寸太小，则有很多正常对象都会落入空的或稀疏箱，因而被误识别为离群点，这将导致很高的假正例率或低精度。相反，如果箱尺寸太大，则离群点对象可能渗入某些频繁的箱中，这将导致很高的假负例率或召回率。为了解决这些问题，使用核密度估计来估计数据的概率密度分布。

2.基于邻近性的方法

给定特征空间中的对象集，可以使用距离度量来量化对象间的相似性。基于邻近性的方法假定：离群点对象与它最近邻的邻近性显著偏离数据集中其他对象与它们近邻之间的邻近性。有两种类型的基于邻近性的离群点检测方法：基于距离的和基于密度的方法。基于距离的离群点检测方法考虑对象给定半径的邻域。一个对象被认为是离群点，如果它的邻域内没有足够多的其他点。基于密度的离群点检测方法考察对象和它近邻的密度。这里，一个对象被识别为离群点，因为它的密度相对于它的近邻低得多。

（1）基于距离的离群点检测。对于待分析的数据对象集D，用户可以指定一个距离阈值r来定义对象的合理邻域。对于每个对象o，可以考察o的r-邻域中的其他对象的个数。如果D中大多数对象都远离o，即都不在o的r-邻域中，则o可以被视为一个离群点。

（2）基于密度的离群点检测。现实世界的许多数据集都呈现更复杂的结构，那里对象可能关于其局部邻域，而不是关于整个数据分布而被视为离群点。因此，很难用距离来检测离群点。基于密度的离群点检测方法的基本假定是：非离群点对象周围的密度与其邻域周围的密度类似，而离群点对象周围的密度显著不同于其邻域周围的密度。

3.基于聚类的方法

基于聚类的方法通过考察对象与簇之间的关系检测离群点。直观地，离群点是一个对象，它属于小的偏远簇，或不属于任何簇。下面是三种基于聚类的离群点检测的一般方法；

（1）该对象属于某个簇吗？如果不，则它被识别为离群点；

（2）该对象与最近的簇之间的距离很远吗？如果是，则它是离群点；

（3）该对象是小簇或稀疏簇的一部分吗？如果是，则该簇中的所有对象都是离群点。

基于聚类的离群点检测方法具有如下优点：首先，它们可以检测离群点，而不要求数据是有标号的，即它们以无监督方式检测。其次，它们对许多类型的数据都有效。再次，簇可以看成是数据的概括，一旦得到簇，基于聚类的方法只需要把对象与簇进行比较，以确定该对象是否是离群点，这一过程通常很快，因为与对象总数相比，簇的个数通常很小。基于聚类的方法的缺点是：它的有效性高度依赖于所使用的聚类方法。这些方法对于离群点检测而言可能不是最优的。对于大型数据集，聚类方法通常开销很大，这可能成为一个瓶颈。

4.基于分类的方法

如果训练数据具有类标号，则离群点检测可以看作分类问题。基于分类的离群点检测方法的一般思想是：训练一个可以区分“正常”数据和离群点的分类模型。基于分类的离群点检测方法通常使用一类模型（单分类模型SVDD），即构造一个仅描述正常类的分类器，不属于正常类的任何样本都被视为离群点。基于分类的方法和基于聚类的方法可以联合使用，以半监督的方式检测离群点。

5.挖掘情境离群点和集体离群点

与一般的离群点检测相比，识别情境离群点需要分析对应的情境信息。情境离群点检测方法可以根据情境是否可以清楚地识别而分成两类。

（1）把情境离群点检测转换成传统的离群点检测。这类方法适用于情境可以被清楚识别的情况，其基本思想是把情境离群点检测问题转换成典型的离群点检测问题。具体地说，对于给定的数据对象，用两步来评估该对象是否是离群点。第一步，使用对象的情境属性识别对象的情境。第二步，使用一种传统的离群点检测方法，估计该对象的离群点得分。

（2）关于情境对正常行为建模。在某些应用中，清楚地把数据划分成情境是不方便的或不可行的。这时，可以关于情境对正常行为建模；使用一个训练数据集，这种方法训练一个模型，关于情境属性的值，预测期望的行为属性值。然后，为了确定一个数据对象是否是情境离群点，可以在该对象的情境属性上使用该模型。如果该对象的行为属性值显著地偏离该模型的预测值，则该对象被宣布为情境离群点。通过使用连接情境和行为的预测模型，这些方法可避免直接识别具体情境。许多分类和预测技术都可以用来构建这种模型，如回归、马尔科夫模型和有穷状态自动机，等等。

与情境离群点检测一样，集体离群点检测方法也可以划分为两类。

（1）第一类方法把问题归结为传统的离群点检测。其策略是识别结构单元，把每个结构单元（例如，子序列、时间序列片段、局部区域或子图）看作是一个数据对象，并提取特征。这样，集体离群点检测问题就转换成在使用提取的特征构造的“结构化对象”集上的离群点检测。一个结构单元代表原数据集中的一组对象，如果该结构单元显著地偏离提取的特征空间中的期望趋势，则它是一个集体离群点。

（2）为集体离群点检测预先定义结构单元可能是困难的，或者是不可能的。因此，第二类方法直接对结构单元的期望行为建模。例如，为了在时间序列中检测离群点，一种方法是从序列中学习马尔科夫模型。因此，一个子序列被宣布为集体离群点，如果它显著地偏离该模型。

6.高维数据中的离群点检测

一般地，高维数据的离群点检测方法应该应对以下挑战：

（1）离群点的解释：不仅应该能够识别检测离群点，而且能够提供离群点的解释。离群点的解释可能是，例如，揭示离群点的特定子空间，或者关于对象的“离群点性”的评估。这种解释可以帮助用户理解离群点的含义和意义。

（2）数据的稀疏性：这些方法应该能处理高维空间的稀疏性。随着维度的增加，对象之间的距离严重地被噪声所左右。因此，高维空间中的数据通常是稀疏的。

（3）数据子空间：它们应该以合适的方式对离群点建模，例如，自适应现实离群点的子空间和捕获数据的局部变化。在所有的子空间上使用固定的距离阈值来检测离群点不是一种好想法，因为两个对象之间的距离随着维度增加而单调增加。(www.xing528.com)

（4）关于维度的可伸缩性：随着维度的增加，子空间的数量是指数增加。包含所有可能的子空间的穷举组合探索不是可伸缩的选择。

高维数据的离群点检测方法可以划分成三种主要方法，包括扩充的传统离群点检测、发现子空间中的离群点和对高维离群点建模。

（1）扩充的传统离群点检测。一种高维数据离群点检测方法是扩充的传统离群点检测方法。它使用传统的基于邻近性的离群点模型。然而，为了克服高维空间中邻近性度量恶化问题，它使用其他度量或构造子空间并在其中检测离群点。另一种方法则是通过维规约，把高维离群点检测问题归结为较低维上的离群点检测。其基本思想是：把高维空间规约到低维空间，那里标准的距离度量仍然能够区分离群点。如果能够找到这样的较低维空间，则可以用传统的离群点检测方法。为了降低维度，可以对离群点检测使用或扩充一般的特征选择和提取方法。例如，可以用主成分分析（PCA）来提取一个低维空间。

（2）发现子空间中的离群点。高维数据中离群点检测的另一种方法是搜索各种子空间中的离群点。其唯一的优点是，如果发现一个对象是很低维度的子空间的离群点，则该子空间提供了重要信息，解释该对象为什么和在何种程度上是离群点。

（3）高维离群点建模。另一种方法是试图直接为高维离群点建立一个新模型。这种方法通常避免邻近性度量，而是采用新的启发式方法来检测离群点。

【注释】

[1]黄晨：“近年10起重大越狱案件一览”，http：//www.caing.com/2011-09-15/100302744.htm l，最后访问日期：2018年4月26日。

[2]中商情报网：“黑龙江嫌犯杀警越狱盘点：近年国内越狱大案件”，http：//mil.askci.com/military/2014/09/04/93322wofp.shtm l，最后访问日期：2018年4月26日。

[3]王婷婷、张莹：“媒体盘点近7年12起越狱案28名越狱犯全被抓回”，http：//news.china.com/domestic/945/20141103/18922977_all.htm l，最后访问日期：2018年4月26日。

[4]环球军事网：“中国最严重的监狱越狱案件分析”，http：//www.huanqiumil.com/a/40936_2.htm l，最后访问日期：2018年4月26日。

[5]百度百科：“关联规则”，http：//baike.baidu.com/item/%E5%85%B3%E8%A7%84%E5%88%99/6319603？fr＝aladdin，最后访问日期：2018年4月29日。

[6]参见欧高炎等：《数据科学导引》，高等教育出版社2017年版。

[7]频繁模式是指频繁地出现在数据集中的模式（如项集、子序列或者子结构）、而长频繁模式是指频繁模式中的项数较长的频繁模式。

[8]杨云、罗艳霞：“FP-Growth算法的改进”，载《计算机工程与设计》2010年第7期。

[9]参见[美]韩家炜等：《数据挖掘概念与技术》，范明等译，机械工业出版社2015年版。

[10]参见欧高炎等：《数据科学导引》，高等教育出版社2017年版。

[11]参见周英、卓金武、卞月青：《大数据挖掘系统方法与实例分析》，机械工业出版社2016年版。

[12]单彩虹等：“可逆矩阵的判定及其逆矩阵的求法”，载《信息系统工程》2015年第9期。

[13]刘明：“线性回归模型的统计检验关系辨析”，载《统计与信息论坛》2011年第4期。

[14]参见[美]韩家炜等：《数据挖掘概念与技术》，范明等译，机械工业出版社2015年版。

[15]参见王振武：《大数据挖掘与应用》，清华大学出版社2017年版。

[16]参见欧高炎等：《数据科学导引》，高等教育出版社2017年版。

[17]参见李春葆等：《数据仓库与数据挖掘实践》，电子工业出版社2014年版。

[18]参见李航：《统计学习方法》，清华大学出版社2015年版。

[19]Jack Cui：“机器学习实战教程（八）：支持向量机原理篇之手撕线性SVM”，http：//cuijiahua.com/blog/2017/11/ml_8_svm_1.htm l，最后访问日期：2018年7月7日。

[20]参见李航：《统计学习方法》，清华大学出版社2015年版。

[21]参见欧高炎等：《数据科学导引》，高等教育出版社2017年版。

[22]王磊：“人工神经网络原理、分类及应用”，载《科技资讯》2014年第3期。

[23]参见鲍军鹏、张选平：《人工智能导论》，机械工业出版社2015年版。

[24]参见[美]韩家炜等：《数据挖掘概念与技术》，范明等译，机械工业出版社2015年版。

[25]邓茗春、李刚：“几种典型神经网络结构的比较与分析”，载《信息技术与信息化》2008年第6期。

[26]Zhou ZH，et al，“Combining Regression Estimators：GA-Based Selective Neural Network Ensemble”，International Journal ofComputational Intelligence＆Applications，pp.341～356.

[27]参见[爱尔兰]Igor Milovanovic：《Python数据可视化编程实战》，人民邮电出版社2015年版。

[28]王丽丽：“集成学习算法研究”，广西大学2006年硕士学位论文。

[29]Breiman L，“Bagging predictors”，Machine Learning，pp.123～140.

[30]Bootstrap方法最初由美国斯坦福大学统计学教授Efron在1977年提出。作为一种崭新的增广样本统计方法，Bootstrap方法为解决小规模子样试验评估问题提供了很好的思路。英语Bootstrap的意思是靴带，这里“bootstrap”法是指用原样本自身的数据抽样得出新的样本及统计量，根据其意现在普遍将其译为“自助法”。就是从我们的训练集里面采集固定个数的样本，但是每采集一个样本后，都将样本放回。也就是说，Bootstrap的一般的抽样方式都是“有放回地全抽”（其实样本量也要视情况而定，不一定非要与原样本量相等），意思就是抽取的Bootstrap样本量与原样本相同，只是在抽样方式上采取有放回地抽，之前采集到的样本在放回后有可能继续被采集到。

[31]注意，在计算每一个基分类器的误差时，需要考虑该基分类器对应的训练数据中样本的权重。

[32]参见[美]韩家炜等：《数据挖掘概念与技术》，范明等译，机械工业出版社2015年版。