离群点：概念、检测和处理方法

离群点是在一组数据中，显著不同于其他数据的数据。大部分的数据挖掘方法都将离群点视为噪声或异常丢弃，然而，有一些应用场景天然适合离群点检测，如：欺诈、疾病、网络攻击、局部离群点分析（在局部属于离群点，但是全局来看是正常的）等等。比如，在下图中，大部分的数据粗略地服从高斯分布，在区域 R 内的两个点显著不同为离群点。
![IMAGE](pic/250BF26562A16510A0851D301115A38E.jpg =194x138)

简介

离群点和噪声的区别：
- 噪声：变量的随机误差、方差。噪声不应被视为离群点。比如：使用信用卡刷卡的用户中，某位用户买了一份比较丰盛的午餐，这可以看做是一笔“噪声交易”。而这种交易的数据不会被看做是离群点，否则信用卡公司需要验证大量的此类交易。
- 在检测离群点之前，应该删除噪声。通常，有如下定义：
  观测量(Measurement) = 真实数据(True Data) + 噪声 (Noise)。
  离群点(Outlier)属于观测量，既有可能是真实数据产生的，也有可能是噪声带来的，但是总的来说是和大部分观测量之间有明显不同的观测值。
离群点检测的重点：
离群点是如何产生的：可以演变为新颖性监测，比如在社交网站是识别新的主题、趋势。
离群点检测的挑战：
- 正常对象和离群点的有效建模
- 针对应用的离群点检测：比如在诊所数据中，小偏离是重要的，足以证实离群点，但是在市场分析中，需要检测对象有很大的波动和显著的偏差
- 处理噪声
- 可理解性。

离群点的类型

全局（global）离群点：全局的数据集，大部分离群点检测方法目的都在找全局离群点。
情景（条件）离群点：eg：温度为28度，是离群点吗？28 度是否为离群点要看时间地点。判定离群点的依赖分为情景属性（时间、地点）和行为属性（温度、湿度、气压）。情景离群点是局部离群点的推广
集体离群点：在下图中，黑色对象作为整体形成一个集体离群点，因为这些对象的密度比数据集中其他的对象高得多，然而每个黑色对象个体对于整体来说并非离群点。集体离群点可以检测计算机入侵（eg：多台计算机不断相互发送拒绝服务包、股票在一小群人当中的大量交易【操纵股市】）
![IMAGE](pic/83CC94538F0BBD0F05EC3677E8FB50AD.jpg =171x132)

检测方法概述

监督、半监督、无监督方法

监督方法：比如分类：
数据：标记正常和非正常样本，缺点是容易导致样本不均衡，可以对离群样本进行过抽样（复制）
- 比起召回率这些数值，更关心捕获到尽量多的离群点
无监督：
数据：没有标记。
假定正常对象在某种程度是聚类的。中心思想：1：找出簇，2：不属于任何簇的点为离群点。
- 问题 1: 不属于任何簇的点可能是噪声
- 问题 2: 先找簇，再找离群点的开销太大
- 问题 3: 如果数据对象是均匀分布的，但是这其中包含集体离群点，这种情况很难被检验出来。
半监督方法：只有少量正常和离群点对象被标记，大部分数据无标记。

统计、近邻性、聚类方法

使用统计模型（eg：高斯分布）
对于一组数据集中的每个对象以及一个给定的高斯分布，计算拟合高斯分布的概率密度 f(x)。如果 f(x)太低，则证明该数据对象不太可能由该高斯模型产生，因此为离群点。
基于近邻性：
一个对象与最近邻的近邻性，显著低于其他的对象与他们的最近邻的近邻性。比如第一个图里面 R 区域的两个点，假设选择 3 近邻，每个点除了自己圈圈里面的近邻以外，其他的两个最近邻的距离，都要显著地高于其他点与他们最近邻的距离。这样的点就是离群点。
缺点：高度依赖距离的度量方法。另外，如果离群点相互之间靠的近，很难检测集体离群点。
基于聚类的方法：
基于这样的假设：正常数据都属于大而密的簇，离群点属于小或稀疏的簇，或者不属于任何簇。缺点：开销太大。

统计方法

思想：学习一个拟合给定的生成模型，用模型去预测，将低概率预测的样本作为离群点。包括参数方法和非参数方法。

参数方法：假定正常的数据对象能够被一个以 $\Theta$ $Θ$ 为参数的分布产生，概率密度函数 f(x)给出生成对象的概率。值越小，越可能是离群点。
- 方法：一元、多元、混合高斯
非参数方法：不假设统计模型，试图输入数据确定模型。
- 方法：直方图、KDE。

参数方法

一元检测：正态分布、分箱、zscore

正态分布和 3 $\sigma$ 原则

当数据服从正态分布：在该原则下，异常值如超过 3 倍标准差，那么可以将其视为异常值。正负 3 $\sigma$ 的概率是 99.7%，那么距离平均值 3 $\sigma$ 之外的值出现的概率为 P(|x-u| > 3 $\sigma$ ) <= 0.003，属于极个别的小概率事件。
数据服不服从正态分布：可以用远离平均值的多少倍标准差来描述。下图中红色箭头所指就是异常值。
![IMAGE](pic/3CA916A87AB0393ACBB4506174B7E06E.jpg =304x236)
例子：
![IMAGE](pic/FF23F8EF547E96D878F710886AED7FE7.jpg =502x500)

箱型图和散点图

箱型图检测方法：利用箱型图中的四分位距（IQR）对异常值进行检测，也叫 Tukey‘s test。箱型图的定义：四分位距(IQR)就是上四分位与下四分位的差值。具体可参考数据的概括性度量。通过 IQR 的 1.5 倍为标准，规定：超过上四分位+1.5 倍 IQR 距离，或者下四分位-1.5 倍 IQR 距离的点为异常值。如果 max 和 min 值在 Q1-1.5IQR、Q3+1.5IQR 范围之内，则更新 max 和 min 的值。
![IMAGE](pic/56BEF981FACFF83528206725E9F11C87.jpg =113x151)
散点图是一种观察离群点的方法，比较直观但是不能量化。
![IMAGE](pic/69B970C9C737B28CD3CA25BB7480E50F.jpg =618x308)

z-score

$z=\frac{x-\bar{x}}{s}$ ，其中，\bar{x}为总体均值， $s$ 为样本标准差。
对于正态分布，z 值在[-3,3]内已经覆盖了大概 99%的数据，所以在该范围之外的数据可被认为是离群点。

Grubbs（格拉布斯）检验

通过假设检验的方法进行一元离群点检测：
定义原假设 H0 为：数据集中没有离群点
则备择假设 H1 为：数据集中有离群点
$G={\frac {\displaystyle \max _{{i=1,\ldots ,N}}\left\vert Y_{i}-{\bar {Y}}\right\vert }{s}}$
其中， $\overline{Y}$ 为样本均值和 ${s}$ 为标准差。上式定义为双侧检验，Grubbs 检验还可用于单侧检验。检测最小值是否是离群点，需计算：
$G={\frac {{\bar {Y}}-Y_{\min }}{s}}$
其中， $Y_{min}$ 是最小值，检测最大值是否是离群点，需计算：
$G=\frac{Y*{\max}-{\bar{Y}}}{s}$
其中， $Y*{max}$ 是最大值

置信度: $\alpha$

根据置信度，计算 tv 值：
$tv = t^2_{\alpha/(2N),N-2}$

双侧检验阈值： $\frac{N-1}{\sqrt{N}}\sqrt{\frac{tv}{N-2+tv}}$

如果统计值 G 落在拒绝域内（阈值的两侧），则拒绝原假设，接受备择假设。

其中，N 为数据的数量。对于单侧检测，用 $\alpha/N$ 代替 $\alpha/(2N)$ .

多元检测：马哈拉诺比斯距离、卡方校验（越大越可能是离群点）

马氏距离检测方法

$MDist(x, \bar{X}) = (x - \bar{X})^{T}S^{-1}(x - \bar{X})$

其中，S 是协方差矩阵。马氏距离的结果是一元变量，可以使用检验一元离群点的方法进行检验。如果 $MDist(x, \bar{X})$ 是离群点，说明 x 是离群点。
关于马氏距离的详细内容，可参考距离的度量方法

卡方统计量 $X^2$

$X^2=\sum_{i=1}^{n}\frac{(O_i - E_i)^2}{E_i}$
其中 $O_i$ 是数据对象 O 在第 i 维度上的值。 $E_i$ 是所有对象在第 i 维上的均值，n 是维度。
如果一个数据对象的卡方值很大，则很有可能是离群点。（假定数据符合正态分布）

使用混合参数分布和多个簇检测多元离群点

假定：数据是由混合参数分布产生的。

例如下图中，有两个大的簇 C1 和 C2，假如我们在这里假设，用一个正态分布不能产生这两组数据。因此，均值会落在两个簇之间，会导致位于均值附近的数据不会被判定为离群点。

![IMAGE](pic/69990670EAB5AF7BFBE763C1D4660ADE.jpg =202x197)

为了解决这个问题，假设这些数据由两组正态分布 $\Phi_1(\mu1,\sigma1)$ 和 $\Phi_2(\mu2,\sigma2)$ 组成。对于数据集中任意的一个样本 x，x 被这两个分布产生的概率为 $P(x|\Phi_1,\Phi2)=f_1(x)+f_2(x)$
其中，f_1(x)是分布 1 的概率密度函数，f_2(x)同理。

根据 EM 算法，求解参数：均值和标准差，

![IMAGE](pic/C362795E4E6FBE8B896A48167835AF08.jpg =545x441)
![IMAGE](pic/29722318F267F3DEECB6485A13DF7AC3.jpg =558x121)

非参数方法

对照直方图

如果数据落在直方图中的一个箱内，则认为是正常数据，否则是离群点。

![IMAGE](pic/5CDE024B304CE19291C758BC138DBDDE.jpg =684x324)

更复杂地，使用直方图给对象赋一个离群点得分。比如用箱容积的倒数。比如购买 7500 美元，离群点得分 wei 为ParseError: KaTeX parse error: Unexpected end of input in a macro argument, expected '}' at end of input: \frac{1}{2%}，购买 385 美元的离群点得分为ParseError: KaTeX parse error: Unexpected end of input in a macro argument, expected '}' at end of input: \frac{1}{60%}。
缺点：直方图的箱尺寸，如果过小，会导致很多正常对象落入空或稀疏箱，被误识别为离群点。如果箱尺寸太大，离群点很可能被分入箱中。

核密度估计

通过核密度函数估计近似数据集的概率密度函数，如果 f(x)太大，则对象可能是正常对象，否则可能是离群点。

关于核密度估计，可参考核密度估计

基于近邻性

###基于距离的离群点

对于一个待分析的数据集 D，用户指定阈值 r $(r\ge 0)$ 定义对象的合理邻域。对每个对象 x，考察和 r 近邻中的对象个数。如果数据集 D 中大多数对象都远离对象 o，则 o 被视为 $DB(r,\pi)$ 离群点。

公式：
$\frac{||\quad\{x'|dist(x, x') \leq r\} \quad ||}{||D||} \leq {\pi}$
其中， $\pi\in(0,1]$

伪代码：

![IMAGE](pic/77A36C6D014289F10A25CBA74B49D408.jpg =767x491)

基于网格的方法

CELL 方法：将数据划分到格子中，然后根据距离计算，算法如下：

![IMAGE](pic/9D5E1682615EDE7BE53EA5191F6EEC79.jpg =198x196)

C 是一个存储了一组数据的格子，内含有 a 个数据，上图中，标记为 1 的为 1 层单元，含有 b1 个数据，标记为 2 的为 2 层单元，含有 b2 个数据。

一层单元：C 中的任意一个数据 x，和 1 层单元中的任意一个数据 y，距离 $dist(x,y)\leq r$
二层单元：C 中的任意一个数据 x，和 2 层单元中的任意一个数据 y，距离 $dist(x,y)\ge r$

剪枝策略：
- 如果 $a + b1 > \pi n$ ，则 C 中没有 $DB(r,\pi)$ 离群点。
- 如果 $a+b1+b2 < \pi n + 1$ ，则 C 中数据均为 $DB(r,\pi)$ 离群点。

聚类方法

按距离判断离群点算法：

计算各个簇内均值
初始化阈值
计算测试数据对每个簇内均值点的距离
为每个数据寻找最近的簇，如果距离大于阈值，判定为离群点

聚类方法判定离群点，大体分三种：

按距离：按点与质心距离、点与质心相对距离（每个样本点到质心比样本点平均向量或中位数向量到质心）、百分比（距离的前多少个）
按簇，不是簇里的为离群点
按大小簇，小簇为离群点

基于密度

基于密度的离群点检测方法的关键步骤在于给每个数据点都分配一个离散度，其主要思想是：针对给定的数据集，对其中的任意一个数据点，如果在其局部邻域内的点都很密集，那么认为此数据点为正常数据点，而离群点则是距离正常数据点最近邻的点都比较远的数据点。通常有阈值进行界定距离的远近。在基于密度的离群点检测方法中，最具有代表性的方法是局部离群因子检测方法 (Local Outlier Factor, LOF)。

在 LOF 方法中，通过给每个数据点都分配一个依赖于邻域密度的离群因子 LOF，进而判断该数据点是否为离群点。若 LOF $\gg$ 1，则该数据点为离群点；若 LOF 接近于 1，则该数据点为正常数据点。

K-邻近距离（k-distance）：在距离数据点 p 最近的几个点中，第 k 个最近的点跟点 p 之间的距离称为点 p 的 K-邻近距离，记为 k-distance (p) 。
可达距离（reachability distance）：可达距离的定义跟 K-邻近距离是相关的，给定参数 k 时，数据点 p 到数据点 o 的可达距离 reach-dist（p, o）为数据点 o 的 K-邻近距离 和 数据点 p 与点 o 之间的直接距离的最大值。即：
$reach_dist_{k}(p,o)=\max\{k\text{-}distance(o),d(p,o)\}$
局部可达密度（local reachability density）：局部可达密度的定义是基于可达距离的，对于数据点 p，那些跟点 p 的距离小于等于 k-distance（p）的数据点称为它的 k-nearest-neighbor，记为 $N_k(p)$ （同距离可能有多个点，所以不是 k），数据点 p 的局部可达密度为它与邻近的数据点 o 们的平均可达距离的倒数，即：

$lrd_{k}(p)=\frac{|N_k(p)|}{\sum_{o\in{N_{k}(p)}}reach_dist_k(p,o)}$

局部异常因子（local outlier factor）：根据局部可达密度的定义，如果一个数据点跟其他点比较疏远的话，那么显然它的局部可达密度就小。但 LOF 算法衡量一个数据点的异常程度，并不是看它的绝对局部密度，而是看它跟周围邻近的数据点的相对密度。这样做的好处是可以允许数据分布不均匀、密度不同的情况。局部异常因子即是用局部相对密度来定义的。数据点 p 的局部相对密度（局部异常因子）为：点 p 的邻居 o 们的平均局部可达密度跟数据点 p 的局部可达密度的比值，即：

$LOF_{k}(p)=\frac{\sum_{o\in{N_k(p)}}\frac{lrd(o)}{lrd(p)}}{|N_{k}(p)|}=\frac{\sum_{o\in{N_{k}(p)}}lrd(o)}{|N_{k}(p)|}/lrd(p)$

根据局部异常因子的定义，如果数据点 p 的 LOF 得分在 1 附近，表明数据点 p 的局部密度跟它的邻居们差不多；如果数据点 p 的 LOF 得分小于 1，表明数据点 p 处在一个相对密集的区域，不像是一个异常点；如果数据点 p 的 LOF 得分远大于 1，表明数据点 p 跟其他点比较疏远，很有可能是一个异常点。

了解了 LOF 的定义，整个算法也就显而易见了：

对于每个数据点，计算它与其它所有点的距离，并按从近到远排序；
对于每个数据点，找到它的 k-nearest-neighbor，计算 LOF 得分。

算法应用

LOF 算法中关于局部可达密度的定义其实暗含了一个假设，即：不存在大于等于 k 个重复的点。当重复点存在的时候，重复点的平均可达距离为零，局部可达密度就变为无穷大，会给计算带来一些麻烦。在实际应用时，为了避免这样的情况出现，可以把 k-distance 改为 k-distinct-distance，不考虑重复的情况。或者，还可以考虑给可达距离都加一个很小的值，避免可达距离等于零。

LOF 算法需要计算数据点两两之间的距离，造成整个算法时间复杂度为 $O(n^2)$ 。为了提高算法效率，后续有算法尝试改进。FastLOF （Goldstein，2012）先将整个数据随机的分成多个子集，然后在每个子集里计算 LOF 值。对于那些 LOF 异常得分小于等于 1 的，从数据集里剔除，剩下的在下一轮寻找更合适的 nearest-neighbor，并更新 LOF 值。这种先将数据粗略分成多个部分，然后根据局部计算结果将数据过滤来减少计算量的想法，并不罕见。比如，为了改进 K-means 的计算效率， Canopy Clustering 算法也采用过比较相似的做法。

哪些算法对离群点敏感？

线性回归。因为用到了最小二乘法

离群点的处理方法

检测离群点以后需要对其进行处理。处理方法大致分为以下几种：

删除含有异常值的记录：直接将含有异常值的记录删除；
视为缺失值：将异常值视为缺失值，利用缺失值处理的方法进行处理，比如均值、中位数、常数等；
平滑修正：用前后两个观测值的平均值、或者 z-score 方法计算的上下限，修正离群点；
不处理：直接在具有异常值的数据集上进行数据挖掘；

ref