第10章异常检测

10.1 为什么要进行异常检测？

面试官：在处理数据时为什么要做异常检测？

程序员大树：
异常检测，目标是发现与大部分其他对象不同的对象，这种异常点也称作离群点。有时这些点会影响分类的准确性，给分类造成误差；而有时，这些异常点却又非常重要，甚至需要专门挖掘这些异常点。比如网络攻击的异常检测，通过监视网络异常行为来识别网络攻击。

面试官：那么，异常有哪些成因呢？

程序员大树：
（1）数据来源于不同的类。异常数据对象，往往来自于一个与大多数数据对象源不同的其他数据对象。比如信用卡欺诈的人，就不属于合法持卡的那类人。
（2）自然变异。很多数据集都可以用统计分布来建模，比如用高斯分布，大部分数据对象显著地靠近中心，不同于平均对象的可能性很小。一些极端情况下的自然变异，会显著远离中心点，造成异常。
（3）数据测量或者收集误差。在生产实践中，有可能人测量失误、测量设备存在噪声等。我们应尽可能剔除这类噪声，因为它们会降低数据质量。

10.2 如何进行异常统计？

面试官：如何用统计学的方法，对异常数据做统计？

程序员大树：
（1）检测一元正态分布中的离群点。
        正态分布可以用记号N(μ,σ)表示，它的两个参数分别是均值和标准差。
        对于一个属性值x的对象，如果是离群点，有 $\frac{|\mathrm{X}-\mu|}{\sigma} \geq c$ ，c是选定的常量。
我们可以根据需要的a大小，反推出c的取值，利用公式： $\mathrm{p}\left(\frac{|\mathrm{X}-\mu|}{\sigma} \geq c\right)=a$
        其中a是稀有程度，表示错误将来自给定分布的值分类成离群点的概率。
（2）检测多元正态分布的离群点。
        对多元正态分布，可以类比一元的做法，只不过需将距离换成马氏距离。马氏距离可以看成是欧式距离的一种修正，解决欧式距离在各个维度尺度不一致的问题。
    马氏距离 $\mathrm{D}(\mathrm{x}, \bar{x})=(x-\bar{x}) S^{-1}(x-\bar{x})^{T}$ ，其中S为数据的协方差矩阵。

（3）检测混合模型离群点。

我们可以假设，数据集D包含两种概率分布的对象，M是大多数对象分布，A是异常对象的分布，对于一个数据对象x，总概率分布是：

$D(x)=(1-\lambda) M(x)+\lambda A(x)$
其中λ是离群点的比例。

因为正常对象数量比异常的大很多，因此当对象从正常移动到异常时，正常对象变化不大，而异常点的概率却会变化很大。通过不断调整λ，可以确定其分布。

（4）基于似然的离群点检测。

设 $M_{t}$ 和 $A_{t}$ 分别为时刻t正常和异常对象的集合。初始 t=0, $M_{0}=D$ , 而 $A_{0}$ 为空。在任意时刻 t，整个数据集的似然和对数似然分别以下两式给出:

$L_{t}(D)=\prod_{\mathbf{x}_{i} \in D} P_{D}\left(\mathbf{x}_{i}\right)=\left((1-\lambda)^{\left|M_{t}\right|} \prod_{\mathbf{x}_{i} \in M_{t}} P_{M_{t}}\left(\mathbf{x}_{i}\right)\right)\left(\lambda^{\left|A_{t}\right|} \prod_{\mathbf{x}_{i} \in A_{i}} P_{A_{t}}\left(\mathbf{x}_{i}\right)\right)$

$L L_{i}(D)=\left|M_{t}\right| \log (1-\lambda)+\sum_{\mathbf{x}_{i} \in M_{t}} \log P_{M_{1}}\left(\mathbf{x}_{i}\right)+\left|A_{1}\right| \log \lambda+\sum_{\mathbf{x}_{i} \in A_{i}} \log P_{A_{r}}\left(\mathbf{x}_{i}\right)$

其中 $P_{D}$ 、 $P_{M_{t}}$ 和 $P_{A_{t}}$ 分别是 D 、 $M_{t}$ 和 $A_{t}$ 的概率分布函数。

基于似然的离群点检测算法：
1: 初始化: 在时刻 t=0，令 $M_{t}$ 包含所有对象, 而 $A_{t}$ 为空。令 $L L_{t}(D)=L L\left(M_{t}\right)+L L\left(A_{t}\right)$ 为所有数据的对数似然。
2: for 属于 $M_{t}$ 的每个点x do
3:     将 x从 $M_{t}$ 移动到 $A_{t}$ ，产生新的数据集合 $A_{t+1}$ 和 $M_{t+1}$ 。
4:     计算D的新的对数似然 $L L_{t+1}(D)=L L\left(M_{t+1}\right)+L L\left(A_{t+1}\right)$
5:     计算差 $\Delta=L L_{r}(D)-L L_{t+1}(D)$
6:     if $\Delta$ >c，其中c是某个阈值 then
7:            将 x分类为异常。即 $M_{t+1}$ 和 $A_{t+1}$ 保持不变，并成为当前的正常和尼常集。
8:     end if
9: end for

10.3 如何进行基于邻近度的离群点检测

面试官：如何用邻近度，对离群点检测？

程序员大树：
        异常点检测的基本原则是，如果它远离大部分点，那么它是异常的。用邻近性度量，比统计分布更容易些。
        度量是否远离的最简单方法是k-近邻的距离。对同一个簇的相近对象，要找出选定对象与其k个相近对象的距离。
        离群点对K的取值敏感。如果K太小了，则少量临近点可能导致较低离群点得分。如果k太大了，则点数少于k的簇中所有对象可能都成了离群点。所以为了鲁棒性，可以将k-近邻距离定义成，前k个最近邻的平均距离。

10.4 如何进行基于密度的离群点检测？

面试官：如何利用密度，对离群点检测？

程序员大树：
        从密度的角度看，离群点是低密度区域中的对象。所以可以看成，离群点得分是该对象周围密度的逆。
        对于密度的定义为：到k个最近邻的平均距离的倒数。如果该距离小，则密度高。
可以将密度写成：
$\operatorname{density}(\mathrm{x}, \mathrm{k})=\left(\frac{\sum_{y \in N(x, k)} \operatorname{distance}(x, y)}{|N(x, k)|}\right)^{-1}$
        其中，N(x,k)是含对象x的k-最近邻集合，|N(x,k)|是集合大小，y是最近邻。
        当然也可以用相对密度表示。相对密度是用点x的密度与它最近邻y的平均密度之比，作为相对密度。
$\text { Relative density }(\mathrm{x}, \mathrm{k})=\frac{\operatorname{density}(x, k)}{\sum_{y \in N(x, k)} \operatorname{distance}(x, y) /|N(x, k)|}$

相对密度的离群点检测，给出了离群程度的定量度量，即使数据有不同密度也能很好处理。