离群点检测方法_《Outlier Analysis》离群点分析 阅读笔记（1）

最近关注 VANETs（车载自组网络）/ ITS（智能交通系统）中的网络安全问题。

一、简单扯两句

由于网络规模的不断扩大、接入设备的日益增长，自动驾驶技术持续发展，各种传感器的配备提升了车辆感知能力，数据信息的交互为未来交通智能化发展创造了可能。

与此同时，交通领域中的安全问题也发生了新的变化。安全隐患从传统的车辆设备、仪器故障、人员操作不当，延伸到了整个车载网络的数字空间，如：虚假信息注入、消息篡改、拒绝服务攻击等等。这些新问题都是开放的网络环境带来的。

如何解决？

现有的解决方案包括两种[1]：

1. 以节点为中心；
2. 以数据为中心。

第一种“以节点为中心”属于比较传统的思路，找出有问题的节点并剔除出去，在以往的网络模式下已经使用非常广泛了。比如，“看门狗”、“泛洪检测”这种对节点行为的分析，还有一类是基于信任的方法，通过对节点的信誉进行评估，判断节点可信程度。

第二种“以数据为中心”相对来说，属于新一些的方法。主要利用统计学、机器学习等技术，对数据直接进行分析。

相比之下，由于车联网中网络拓扑频繁、动态变化，再加上为了保护用户隐私，引入了匿名及其更新机制，对单个节点的受信程度难以有效捕捉，对于虚假或错误信息的散播难以及时控制。从这个角度看来，第二种方法更适用于车联网的场景，以数据为对象，直接对其进行判别。

顺着这个思路想，怎么就能做到对数据真实性、有效性、完整性等方面进行判别呢？学习的过程中看到了一本《Outlier Analysis》[2]。接下来，便是一系列的阅读笔记啦。

---

二、谈谈作者

首先，介绍一下作者——Charu Aggarwal（这是他的个人主页：http://www.charuaggarwal.net）。他是 IBM 的托马斯沃森研究中心的一位高级研究员。在数据挖掘领域从事多年研究，尤其对数据流、隐私、不确定数据和社交网络分析颇有兴趣，出版了15本著作，发表了300多篇论文，获得了80多项专利，还有IBM和各类会议颁布的奖项。《Outlier Analysis》便是他的代表作之一。

---

三、Chapter 1 《An Introduction to Outlier Analysis》笔记

步入正题，以下是第一章的阅读笔记。

1. Outlier是什么？

Outlier可以翻译成离群点（离群值），或异常值。

1980年Hawkins给了一个早期的定义：

离群点指的是，一个观测值与其他观测值偏离太多，而引起猜疑，觉得它由一个不同的机制产生。

统计学中，常常也会出abnormalities、discordants、deviants、anomalies这类词来代替。

对于大部分应用而言，其过程中会产生一些数据。当应用过程出现异常状况时，对应到数据上，离群值也会随之产生。因此，离群值往往包含着系统和对象发生异常时的特征。识别出这些特征可以为应用带来不少好处。

实例包括：入侵检测系统；信用卡欺诈；传感监测；医学诊断；执法；地球科学等等。

在所有这些应用中，数据都有一个“正常”的模型，当数据偏离这个在正常模型时，我们则认为它是异常。与outlier相对，正常的数据点通常也称之为 inliers。

值得一提的是，在一些场景下（如入侵或欺诈检测），我们认定异常，并非根据某个体的数据点，而是根据多个数据点的序列推理得到。比如，欺诈行为很多情况下要通过观测一个个体在特定序列下的行为判断出。此外，还存在一些群体异常的情况。因此，异常不一定仅根据个体数据点来推断，这就需要根据问题特点，设计合理的离群点检测算法。

离群点检测算法的输出有两类

1. 离群得分（大多数离群点检测算法输出一个分数，以量化每个数据点的离群程度。这个分数可以用于数据离群程度的排序。这是一种比较通用的输出形式，虽然没有明确给出哪些是离群点，但其保留了详尽的数据信）
2. 二进制标签（第二类的输出直接决定了一个数据点是否为离群点。在设定了阈值的情况下，离群得分实际上也可以转换成二进制的标签。这个阈值一般是基于分数的统计分布而设定的。相比之下，二进制标签包含的信息会少些，但最终结果对于具体应用的决策是刚需。）

到底多少算是离群，这个偏差其实很具有主观倾向。

2. Noise VS anomaly （噪声与异常）

在实际的应用中，数据可能会包含噪声，噪声带来了数据的偏差，但噪声并不是数据分析师关心的，只有显著且感兴趣的偏差才是数据分析师所关心的（即异常）。有时候由于噪声存在，数据也会偏离正常。这本书中，用“outlier”指代异常或噪声；而“anomaly”（异常）才是outlier中分析师们感兴趣的那一类。

在无监督的环境下，噪声，是正常数据和异常的边界，可以视为一种弱的离群点，未必能达到数据点被判定为感兴趣或异常的严格标准。如，聚类边界上的数据点就可以视为噪声。大多数离群点检测算法采用量化的方法来度量数据点的离群程度。一般来说，异常的离群程度是大于噪声的。但有时候噪声大了，由于偏离程度大，数据可能也会被误认为是异常。因此噪声和异常之间的界限很难划分，这也是很多学者热衷于研究的一个方向。

有些人利用弱离群点和强离群点来区分噪声和异常，毕竟都属于偏离正常的情况，只是偏离的强弱有些差别。不过，什么算强，什么算弱，怎么划分呢？这是个问题。

3. 数据模型非常重要 Data Model is Everything

离群点检测算法往往通过定义一种正常的数据模型，然后衡量给定数据点的偏差，得到一个离群得分。这个模型可能一些生成的数据模型，它们对正常模式进行不同的假设。这些模型有：高斯混合模型、基于回归的模型、基于邻近的模型。通过计算数据点与模型的匹配程度，计算离群得分。

举个例子，基于最近邻的离群点检测方法，从数据点的k近邻距离来衡量其离群情况。也就是说，这种方法假设：离群点是那些在距离分布上远离其他数据的点。

由此可见，数据模型的选择非常关键。当假设不合理时，生成的数据模型也无法奏效。一旦初始阶段的数学模型出错，将影响后续对数据的理解和分析。

因此，必须对正常模式的数据分布非常了解，同时理解自己要分析什么，建立合适的数据模型！这是最关键的一环。

在很大程度上，离群点检测是一个无监督的问题，无法利用已有的一些样本自主地学习到最佳的数据模型。这相比打了标签的有监督学习更具挑战性。因此，在实际应用中，数据分析师应当对各种偏差充分理解。

4. 离群点检测模型的可解释性

选择什么样的离群点模型，受到很多因素的影响。比如，数据类型、数据大小、相关离群样本的可得性、模型是否需要较强的可解释性。从分析师的角度来说，模型的可解释性非常重要。对应于具体的应用场景，当一个点被视为离群点，其实际意义是什么？

不同的模型具有的可解释性也不一样。利用数据原始属性，进行较少的数据变换，将会使模型的可解释性更强。

接下来，将介绍几种经典的离群点检测方法。

5. 基本的离群点检测模型

（1）离群点检测中的特征提取

由于离群点检测问题是无监督的，因此特征的挑选也富有挑战。不同于可以利用标签的分类方法，在无监督的离群点检测中很难找到息息相关的特征。

• Kurtosis measure

Kurtosis measure（峰度）有一种用来衡量总体数据（一组单变量点）离群度的特征量。第一步是计算均值μ和标准差σ，并将数据标准化为0均值和单位1的方差。如下：

如此定义的Zi，使得其方差为1。然后计算Zi四次幂的平均值，得到峰度如下：

当一组数据的特征分布很不均匀时，会表现出较高的峰度值。比如，当数据中包含一些极值点，由于峰度以四次方的形式定义，其值就会增加。峰度常常用于子空间离群点（孤立点）检测方法中，在数据的低维投影中找离群值。

Kurtosis measure有一个缺点，它在分析单个特征时，忽略了各种属性间的相互作用。

当然，也有办法考虑各个属性的相互作用，也可以在低维距离分布情况下采用Kurtosis measure。例如，先将数据映射到低维空间S，然后计算 N 个数据点到数据中心的马氏距离集合的峰度。这样的计算，提供了子空间S的多维峰度，同时考虑到了 S 空间多个维度间的相互作用。我们可以通过再引入贪婪算法，迭代地添加候选子集 S 中的特征，以构建一个最高维峰度的判别子集。

• 数据相关性分析

第二种特征挑选的方法是找到离群点检测问题与监督学习之间的联系。基本的思想是：我们认为，当一个特征与其他特征不相关时，即视其为无关特征。因为往往离群点是那些违反了正常数据依赖关系下模型的点。无关的特征是不能用来独立建模数据的。因此，当有人用了回归模型来从其他特征预测某一个特征，且平均的平方误差很大时，此时，这个特征应该被剔除。

将所有的特征标准化为单位方差，然后利用其他的特征来预测第k个特征，得到均方误差RMSE_k。如果RMSE_k 大于1，则预测误差大于特征的方差，此时这个第k特征应当剔除。我们也可以用这种方法来衡量特征的重要性。通常，第 k 特征的权重为max{ 0,1-RMSE_k }。

（2）极值分析

离群点检测最基本的形式是：对一维数据的极值分析。

这是一类特殊的离群点，它们的值或太大或太小。这类离群点在很多应用场景中都很有意义。

极值统计与传统的离群点定义有所不同。前面提到，霍金斯Hawkins对离群点的定义是针对数据点产生的概率，而非数值的极限情况。

例如，在数据集{1,2,2,50,98,98,99}的一维数值中，1和99的值可以被视为极值，而50位于数据集数值大小的平均水平，因此不太可能被当做极值。然而，我们将这个数据集划分成两个{1,2,2}和{98,98,99}。因此，大部分概率和基于密度的模型都会将50视为数据的离群点，这与霍金斯的定义也是相符的。

因此，离群点和极值点的冲突常常存在，尤其是在多元数据的上下文中。许多极值模型也会利用概率模型来量化数据点是极值点的可能性。

极值模型虽然和离群点的衡量角度不同，但在大部分异常检测算法中都能派上用场，作为最后一步。为什么这么说呢？大部分离群点建模方法量化了数据点与正常模式的偏离程度，并以数据分值的形式表征。极值分析通常作为这些偏差衡量的最后一步，因此这时候偏离程度已经被表征为单变量的形式（离群得分）。此时的极值就对应于离群点。

在许多多标准的离群点检测算法中，离群得分可能就是一个向量（如气象中的温度、压力等），而非单个值。在这种情况下，可利用多元极值方法把这些离群点的分数统一为单个值，也可以生成二进制标签的输出。因此，即使原始的数据点无法直接利用极值建模的方法来分析，也可以在后续让其发挥价值。极值分析为离群点提供了可靠的支持。

通过利用基于距离或深度的方法，极值分析也可以推广至多变量数据。然而，这些方法仅仅在我们确定离群点处于数据边界的情况下适用。

（3）概率和统计模型

在概率和统计模型中，数据被建模为一个闭合的概率分布，模型的参数通过学习得到。这类方法最关键的是，选择合适的数据分布，合理建模。

例如，高斯混合模型假设数据是一个生成过程的输出，每个数据点都属于一个 k 高斯聚类。利用最大期望 (expectation-maximization, EM) 算法来学习所观测数据高斯分布的参数，从而尽可能提高数据生成过程的概率（可能性）。

该方法的一个关键输出是：数据点到不同聚类的从属概率。数据点如果拟合值很低，那么很可能被视为是离群点。

实际中，常常利用拟合值的对数形式作为离群得分，因为采用对数形式，可以让离群点的极值倾向更明显（前面有提到，利用极值方法来反映拟合值的离群情况）。

概率模型的一大优势在于，可以应用于现实生活中几乎任何的数据类型，只要找到合适的生成模型。

概率模型的一大缺点在于，它尽可能地将数据拟合至一个特定的分布，有时候可能是不合适的。当模型参数增加，过拟合的现象也会严重。很多参数模型也很难解释，不够直观。毕竟数据的分析是为了更好地理解异常数据的产生，如果可解释性不强，那么价值也不够。

（4）线性模型

利用线性相关性将数据降维，将问题转化为对低维子空间数据的分析。采用最小二乘拟合的方法确定最优的低维超平面（例如，在二维中，则意味着通过回归分析，找到一条穿过原始点的最优曲线）。然后，利用原始数据点到超平面的距离来衡量它们的离群程度（量化形式：离群得分 outlier score）。这时候，就可以用极值分析来确定利群点是哪些。

下面举个二维空间的例子。我们利用线性模型来建模数据点{(x_i,y_i), ∀ i ∈ {1, ... , Ｎ}}，如下：

其中a和b为系数，最后一个分量为残差，表征建模的误差。为了最小化如下的最小二乘误差

需要通过对数据的学习来调整系数a和b。这是一个凸非线性规划问题，存在闭式解。这里的平方残差就给出了利群得分。利用极值分析可以得到异常的离群情况，将其视为离群点。

• 降维和主成分分析PCA

降维和PCA这两个概念非常类似，区别在于主成分分析在来建模数据相关性采用的是一种无参数技术，没有主观参数的介入。通过多元回归分析可以得到PCA，即确定最小化最小二乘误差的超平面，得到最小重构误差的低维子空间。而离群点会存在较大的重构误差，因为它们不符合数据的聚合子空间模式。因此，可以将重构误差视为利群得分。

另外，主成分分析可用于噪声校正，修改数据点的属性以降低噪声。离群点会比一般正常的数据点更明显地修正。降维的方法是矩阵分解的一种特例，矩阵分解的一般方法可以用于不完整的数据集。

降维和回归建模的方法大部分都很难从数据的原始属性给予解释。这是由于子空间被定义为属性的线性组合（带有正负系数），从数据属性的特点方面很难解释清楚。然而，有些降维的形式，例如非负矩阵分解，是高度可解释的。

（5）基于近邻度的模型

基于近邻度的模型（proximity-based models），其核心观念是：基于相似度和距离函数，离群点是那些与其他节点孤立的数据点。近邻模式是离群值分析这一领域中最流行的一类方法。其中包括聚类方法（clustering）、基于密度的方法（density-baed）和最近邻方法（nearest-neighbor）。

• 聚类和基于密度的方法

在聚类和基于密度的方法中，数据的密集区域可以直观地发现，而离群点就是那些不处于密集区域的点。也就是说，离群点是那些距离密集区域很远的数据点。

聚类和基于密度的方法主要区别在于：聚类方法分割数据点，而基于密度的方法(如直方图)对数据空间进行分割。因为后者的目的是估计所测试的点在数据空间中的密集情况，而空间分割便是最有效的方法。

对于聚类的方法，第一步是采用一种聚类算法来确定数据集的密集区域。第二步是，度量数据点到不同聚类的拟合情况，以计算出利群得分。例如，对于k-means聚类算法，数据点到最近质心的距离即可用来度量该点的离群倾向。对于聚类算法的选择应该慎重，因为不同的聚类方法可能会导致千差万别的数据分割。因此，我们可以对同一个数据集进行多次聚类，得到不同运行轮次下这些点的离群得分平均值，这样结果会更具有鲁棒性。

而对于基于密度的方法（例如，直方图），通过划分数据区域为若干个小区域，每个区域中数据点的个数即可用来计离群得分。基于密度的方法相对来说，可解释性较强。数据当中的系数区域可以联合多个原始属性来表示。例如，考虑一个基于以下属性子集的系数区域：Age≤20，Salary≥100,000。显然，这样的数据空间划分从语义的角度就具有高度可解释性。我们可以理解，为什么这样的数据是离群点。

一些其他的方法（如核密度估计）不会划分数据区域，但仍然是对数据区域的密度进行估计，只不过将空间的划分换成了更平滑的内核函数。

• 最近邻方法

在最近邻方法中，计算每个数据点到其k个最近邻的距离，并将其视为离群得分。

选定k (k>1)，在该方法中，会将那些与大部队相去甚远的小节点群体视为离群点。这是情有可原的，因为在数据生成过程中，如若发生了异常，也可能会产生一系列比较少的相关节点，它们虽然相互之间离的很近，但也应视作异常点。

（个人觉得，这是最近邻方法区别于前面两种方法的一点优势）

然而，最近邻方法需要计算出单个数据点到其他所有数据点的距离，完成所有数据计算的复杂度为O(N^2)，在实际大规模数据场景下会导致计算时间过长，开销过大，难以适用。

当我们不需要得到所有点的离群得分，只要得到二进制的结果（离群点/非离群点）时，有一种简化计算的思路。在计算过程中，对于数据点“A”，如果在还未遍历完时，就发现已经算得其当前k最近邻距离小于已有的r个最大值（top-r），那么此时就可以断定数据点“A”非离群点，无需继续遍历剩下的点。

（5）信息论模型

前面提到的很多异常检测模型，利用各种数据分析形式，如生成概率模型参数、聚类、低维超平面，得到数据的偏离程度。信息理论的方法也是基于相同的原则，但不以直接的方式来实现离群点的检测。其核心思想是，离群点会增加对数据集描述的最小编码长度。例如如下两个字符串：

ABABABABABABABABABABABABABABABABAB

ABABACABABABABABABABABABABABABABAB

虽然这两个字符串长度相等，但他们的描述不同。可以看到第二个字符串比第一个相差一个“C”，第一个可以描述成“AB 17 times”，而第二个就不能如此简单描述了。这个字符“C”其实就对应着离群点，带来了最小编码长度的增加。信息理论模型与传统其他模型密切相关，因为它们都通过对数据集的简明表示，并将其作为基准进行对比。例如，在多维数据集的场景下，模型都用到了如下的简明描述：

（1）一个概率模型：利用生成模型参数来描述数据集，例如：混合高斯分布、混合指数幂分布。

（2）聚类或基于密度的模型：在做大五岔容忍范围内，通过聚类描述、直方图或者其他表示形式来描述数据集。

（3）PCA模型或谱模型：通过对多维数据的低维子空间或网络的浓缩表示，例如潜在表示，实现对数据的描述。

（4）频繁模式挖掘方法，通过频繁模式描述数据，这是利用信息论进行异常检测时最常用的方法。

6. 高维离群点检测

对于离群点检测而言，数据维度高是一大挑战。因为多个维度间存在噪声、相关性第等问题，导致成对的距离更有相似的倾向。这里的一个关键点在于：不相关的属性会降低距离计算的精度，从而得到的离群得分也不精确。

当我们采用基于距离的算法来给离群点打分时，我们需要观察弱/不相关属性带来的影响。在高维空间中，数据越来越稀疏，成对的数据点之间几乎等距。结果就导致，离群点很难从众多数据点中区别出来。

相比之下，在相关属性的局部低维子空间中可以更好地分析离群点。这类方法我们称之为子空间离群点检测，这是离群点分析中的一类重要的算法。通常，我们假设：

离群点隐藏于局部低维子空间，而在高维分析中难以发现。

基于这一假设，找到异常值最为凸显的子空间，在其中搜索，往往带来很好的效果。

这种子空间搜索的方法，是（全维度）聚类和（全数据）回归的一种推广。

它结合了局部数据模式分析和子空间分析，从而挖掘出重要的离群点。这是一个很大的挑战，因为要想在高维中同时找出相关数据点和子空间，这在计算上是很难的。

在选择子空间上很容易出错，因此需要识别出相关的多个子空间，并对不同的子空间进行预测。这种方法与“outlier ensembles”的概念紧密相关，下面是对它的具体介绍。

• outlier ensembles

总的来说，这是一种集成的概念。

在诸如聚类、分类的很多数据挖掘问题中，大量的元算法被用来改进solution的鲁棒性。这些元算法结合了多个算法的输出，称之为“ensembles”。例如，分类中常用的集成方法包括bagging，subsampling，boosting和stacking。类似地，集成的方法也常常用于改进聚类的效果。

因此，很自然地，我们会思考，这种元算法问题是否也存在于离群点检测领域中。答案是肯定的，尽管离群点检测的元算法研究相对较新，但在分类和聚类其他问题中，这些研究已很成熟了。在离群点检测领域，主要分类两类：

（1）序列组合

（2）独立组合

（后续将更新如下7-9的内容）

7. 数据基本类型

前面的讨论都是针对多维数值型数据的分析与处理。我们假定数据记录相互之间是独立的。然而，在实际生活中，原始获得的数据往往在属性类型和数据点相关性方面更加复杂。一下是一些真实世界中的数据类型。

• 类别、文本、混合 属性

在真实的应用中，许多数据集可能包含类别属性，通常取值为离散的无序值。例如，人口统计学数据可能就包含这种族、性别、邮编等属性，这些属性值并非有序的，因此需要对其进行特别分析与处理。混合属性的数据包含着数值型和类别的属性。大部分现有的模型都可以归类为这一情况。许多场景的一大挑战就是构建一种距离（或相似性）函数，使其在分析离散数据时保留语义的意义。

当属性的可取值不多的情况下，基于回归的模型在离散属性值方面可以发挥一定作用。典型的方法就是通过对每个分类值构建一个属性，从而将离散值转化为二进制数值。再将诸如主成分分析的回归模型应用于这一二进制数据集上。这些方法可以很容易地扩展到文本数据上，因为在单词频率上存在固有的排序。这种情况下，可以利用单词之间的相关性建立回归模型。

实际上，一些最成功的文本去噪的模型是基于潜在语义分析（latent semantic analysis, LSA）的。LSA是线性回归分析的一种。其他用于文本和类别数据的常用方法包括聚类、基于临近的方法、概率模型、基于频繁模式挖掘的方法等等。

• 当数据值存在关联时

在实际生活中，不同的数据值在时间和空间上存在关联，或者数据项通过显示的网络关系链路相关联。这种依赖关系对于异常检测过程将有很大的影响，即时是在定义的层面。在这种场景下，数据项的期望值会受到其上下文依赖关系的影响，因此离群点需要基于这种上下文建模的偏差来定义。

当单个数据项由于关联其他数据项，而被宣布为异常点时，我们称之为上下文异常。因为该离群点只是在上下文关系中，才会被视为异常的，即将其判定为异常是有条件的，故又被称为条件异常。例如，时间序列中突然的尖峰就是一种上下文异常，因为这个尖峰的数据点在最近的时间帧里与其他数值差别很大，它偏离了期望的正常值范围。

当一群数据项被判定为异常时，我们称这群点为集体异常/离群点。例如，随着时间的推移，当股票价格出现异常且快速的波动时，可以波动中包含的所有数据项视为集体异常。事实上，所有存在依赖关系的数据中出现了异常

1) 时间序列数据和数据流

2) 离散序列

3) 空间数据

4) 网络和图数据

8. 有监督的离群点检测

9. 评估指标

[1] R. W. van der Heijden, S. Dietzel, T. Leinmüller and F. Kargl, "Survey on Misbehavior Detection in Cooperative Intelligent Transportation Systems," inIEEE Communications Surveys & Tutorials, vol. 21, no. 1, pp. 779-811, Firstquarter 2019.

[2]Charu C. Aggarwal, Outlier Analysis, 2nd Edition, Springer.