斯坦福机器学习课程 第九周 (1)密度估计

动机:异常检测

视频地址

在接下来的一系列课程中,我将向大家介绍异常检测(Anomaly detection)问题。这是机器学习算法的一个常见应用。这种算法的一个有趣之处在于它虽然主要用于非监督学习问题,但从某些角度看,它又类似于一些监督学习问题。

首先,我们举一个例子来解释什么是异常检测。

假想你是一个飞机引擎制造商,当你生产的飞机引擎从生产线上流出时,你需要进行QA(质量控制测试)。而作为这个测试的一部分,你测量了飞机引擎的一些特征变量,比如你可能测量了引擎运转时产生的热量,或者引擎的振动等等(我有一些朋友很早之前就开始进行这类工作,在实际工作中他们确实会从真实的飞机引擎采集这些特征变量):

$$
x_1 = 产生的热量 \\
x_2 = 振动的强度 \\

$$

这样一来,如果你生产了m个引擎的话,你就有了一个从$x^{(1)}$到$x^{(m)}$的数据集:

$$
{x^{(1)},x^{(2)},…,x^{(m)}}
$$

也许你会将这些数据绘制成图表,看起来就是这个样子:

图中每个叉都是你的无标签数据。

假设有一天,你有一个新的飞机引擎从生产线上流出,这个引擎的数据为$x_{test}$。那么所谓的异常检测问题就是检查这个新的飞机引擎是否存在某种异常。

比如说,如果你的新引擎对应的点落在这里:

从数据上来看,它看起来像我们之前见过的引擎,因此我们可以直接认为它是正常的。然而如果你的新飞机引擎的$x_{test}$对应的点在这外面:

那么我们可以认为这是一个异常的引擎。

异常检测问题更正式的定义

异常检测问题更正式一些的定义如下:

假设我们有$m$个正常的样本数据${x^{(1)},x^{(2)},…,x^{(m)}}$,我们需要一个算法来告诉我们一个新的样本数据$x_{test}$是否异常。

我们要采取的方法是:给定无标签的训练集,对数据集$x$建立一个概率分布模型$p(x)$。当我们建立了$x$的概率模型之后,我们就会说,对于新的飞机引擎$x_{test}$,如果概率$p$低于阈值$ε$:

$$
p(x_{test}) \lt ε
$$

那么就将其标记为异常。

因此当我们看到一个新的引擎在我们根据训练数据得到的$p(x_{test})$模型中概率非常低时,我们就将其标记为异常;反之如果$p(x_{test})$大于给定的阈值$ε$,我们就认为它是正常的。


因此在上面的飞机引擎的例子中,对于给定的训练集,对于图中的中心区域的$p(x)$会很大;而稍微远离中心区域的点概率会小一些;更远的地方的点,它们的概率将更小;在外面的点将成为异常点:

中心区域$p(x)$很大 $p(x)$略小 $p(x)$很小 异常点

异常检测的应用场景

欺诈检测

异常检测最常见的应用就是欺诈检测了。

假设你有很多用户,你的每个用户都在从事不同的活动。你可以对不同的用户活动计算特征变量,然后建立一个用来表示用户行为对应的特征向量出现的概率的模型(用来表示用户表现出各种行为的可能性的模型)。

因此假设你看到某个用户在网站上行为的特征变量是这样的:

$$
\begin{align*}
x_1&:是用户登录的频率 \\
x_2&:是用户访问某个页面的次数 \\
x_3&:是用户在论坛上发帖的次数 \\
x_4&:是用户的打字速度(有些网站是可以记录的)
\end{align*}
$$

因此你可以根据这些数据建一个模型$p(x)$,然后你可以通过这个模型来发现你网站上的行为奇怪的用户。你只需要看哪些用户的$p(x)\ltε$即可,接下来你就可以对这些用户的档案做进一步筛选,或者要求这些用户 验证他们的身份,从而让你的网站防御异常行为或者欺诈行为。

这种技术将会找到行为不正常的用户,而不仅仅是有欺诈行为的用户。然而这就是许多许多在线购物网站常常用来识别异常用户的技术。

工业领域查找异常产品

异常检测的另一个例子是在工业生产领域,事实上我们上面已经谈到过飞机引擎的问题,你可以通过异常检测找到异常的飞机引擎,然后要求进一步细查这些引擎的质量。

计算机监控

第三个应用是数据中心的计算机监控。实际上我有些朋友正在从事这类工作。

如果你正在管理一个计算机集群或者一个数据中心,其中有许多计算机。那么我们可以为每台计算机计算特征变量,例如计算机的内存消耗、硬盘访问量、CPU负载或者一些更加复杂的特征(例如一台计算机的CPU负载与网络流量的比值)。

那么给定正常情况下数据中心中计算机的特征变量,你可以建立$p(x)$模型,通过它来找到运行不正常的计算机。

目前这种技术正在被各大数据中心使用,用来监测大量计算机可能发生的异常。

高斯分布(正态分布)

视频地址

在本节我将介绍高斯分布(也称为正态分布)。

如果你已经对高斯分布非常熟悉了,那么也许你可以直接跳过这一节。但是如果你不确定或者你已经有段时间没有接触高斯分布了,那么请从头到尾看完这一节。在下一节中,我们将应用高斯分布来推导一套异常检测算法。

高斯分布的定义

假设$x$是一个实数随机变量(即:$x \in R$),如果x的概率分布服从高斯分布:其中均值为$μ$,方差为$σ^2$,那么将它记作:

$$
x \sim N(μ,σ^2)
$$

这里的$\sim$符号读作:”服从…分布”。大写字母$N$表示Normal (正态),有两个参数,其中$μ$表示均值,$σ^2$表示方差。

如果我们将高斯分布的概率密度函数绘制出来,它看起来将是这样一个钟形的曲线:

这个钟形曲线有两个参数,分别是$μ$和$σ$。其中$μ$控制这个钟形曲线的中心位置,$σ$控制这个钟形曲线的宽度。

从图中可以看出来,$x$取中心区域的值的概率相当大,因为高斯分布的概率密度在这里很大;而$x$取远处和更远处数值的概率将逐渐降低,直至消失。

高斯分布的数学公式如下:

$$
p(x;μ,σ^2)=
\frac{1}{\sqrt{2π}σ}exp(-\frac{(x-μ)^2}{2σ^2})
$$

其实我们并不需要记住这个公式,当我们真的需要用到它时,我们总可以查资料找到它。

高斯分布中,$μ$和$σ$的关系

我们举例来说明一下高斯分布中$μ$和$σ$这两个参数之间的关系:

$μ=0$,$σ=1$ $μ=0$,$σ=0.5$ $μ=0$,$σ=2$ $μ=3$,$σ=0.5$

值得提醒的是,在高斯分布的图像中,不管曲线的形状如何,曲线围城的总面积都是1。所以如果$σ$很大,就意味着数据的离散化程度越大,中间区域就会变宽,但由于总概率为1,所以高度会降低;反之如果$σ$很小,就意味着数据的离散化程度越小,中间区域就会变窄,但由于总概率为1,所以高度会升高。

参数估计问题

接下来让我们来看参数估计问题。

假设我们有以下数据集:

$$
{x^{(1)},x^{(2)},…,x^{(m)}} \ \ \ \ \ \ \ x^{(i)} \in R
$$

其对应的数据在图像中如下:

如果这些数据是服从正态分布的:

$$
x \sim N(μ,σ^2)
$$

但我们只有数据,并不知道参数$μ$和$σ$的具体值。那么参数估计问题,就是在寻找这些参数具体值的问题。

高斯分布的参数估计公式

具体来说,高斯分布中的参数估计公式如下:

$$
μ=\frac{1}{m}\sum_{i=1}^mx^{(i)}
$$

$$
σ^2=\frac{1}{m}\sum_{i=1}^m(x^{(i)}-μ)^2
$$

可以看出来,$μ$是在对所有m个样本求均值,$σ^2$实际上是对所有样本与均值做差再取平方后得到的平均大小。

再提一下,如果你精通统计学,你可能听过极大似然估计,那么这里的估计实际就是对$μ$和$σ^2$的极大似然估计。如果你不知道,也无所谓。

还有一点,如果你在学习统计学时,可能会见到这个式子:$σ^2=\frac{1}{m-1}\sum_{i=1}^m(x^{(i)}-μ)^2$,但在机器学习领域,大家习惯使用$σ^2=\frac{1}{m}\sum_{i=1}^m(x^{(i)}-μ)^2$,其实在实际情况中,具体使用$\frac{1}{m}$还是$\frac{1}{m-1}$其实区别很小,只要你有一个稍大的数据集。这两个版本的公式在理论特性和数学特性上稍有不同,但在实际应用中,他们的区别甚小,几乎可以忽略不计。

异常检测的具体算法

视频地址

在上节课中,我们谈到了高斯分布。在本节我将应用高斯分布开发异常检测算法。

假如说我们有一个无标签的训练集,其中共有$m$个训练样本,并且这里的训练集里的每一个样本都是$n$维的特征,因此你的训练集应该是$m$个$n$维的特征构成的样本矩阵:

$$
{x^{(1)},…,x^{(m)}} \\
x \in R^n
$$

对于我们的异常检测算法,我们要从数据中建立一个$p(x)$概率模型。由于$x$是一个向量,因此:

$$
p(x)=p(x_1)p(x_2)p(x_3)…p(x_n)
$$

我们假定特征$x_1$服从高斯正态分布:

$$
x_1 \sim N(μ_1,σ^2_1)
$$

根据上节学到的知识,你可以得出对应的$μ_1$和$σ_1$:

$$
μ_1=\frac{1}{m}\sum_{i=1}^mx^{(i)}_1
$$

$$
σ^2_1=\frac{1}{m}\sum_{i=1}^m(x^{(i)}_1-μ_1)^2
$$

这样$p(x_1)$就可以写成这样一个高斯分布:

$$
p(x_1)=p(x_1;μ_1,σ^2_1)
$$

同样地,我假设$x_2$也服从高斯分布,可以得出:

$$
p(x_2)=p(x_2;μ_2,σ^2_2)
$$

与此类似$x_3$服从另外一个高斯分布:

$$
p(x_3)=p(x_3;μ_3,σ^2_3)
$$

直到$x_n$:

$$
p(x_n)=p(x_n;μ_n,σ^2_n)
$$

因此可以得出:

$$
\begin{align*}
p(x)
&= p(x_1;μ_1,σ^2_1)p(x_2;μ_2,σ^2_2)p(x_3;μ_3,σ^2_3)…p(x_n;μ_n,σ^2_n) \\
&= Π_{j=1}^np(x_j;μ_j,σ^2_j)
\end{align*}
$$

其中$Π$(读作pai,是$π$的大写形式)类似$∑$符号,只不过这里将连加换成了连乘。顺便要说的是,估计$p(x)$的分布问题,通常被称为密度估计问题。

注意:对于熟悉统计学的同学来说,上面的式子实际上就对应于一个从$x_1$到$x_n$的独立的假设。但实际应用中,无论这些特征是否相互独立,这些算法的效果都还不错。

异常检测算法步骤总结

让我们来总结一下异常检测算法的具体步骤:

  • 1.从样本中选择一些能体现出异常行为的特征$x_i$。

我们可以尝试找出一些特征,比如在你的系统里,那些能看出用户异常行为或者欺诈行为的特征。

  • 2.分别计算出每个特征的参数$μ_1,…,μ_n,σ^2_1,…,σ^2_n$。

$$
μ=
\begin{equation}
\left[
\begin{matrix}
μ_1 \\
μ_2 \\
┋ \\
μ_n
\end{matrix}
\right]
\end{equation}
=
\frac{1}{m}\sum_{i=1}^mx^{(i)}
$$

$$
σ^2=
\begin{equation}
\left[
\begin{matrix}
σ^2_1 \\
σ^2_2 \\
┋ \\
σ^2_n
\end{matrix}
\right]
\end{equation}
=
\frac{1}{m}\sum_{i=1}^m(x^{(i)}-μ)^2
$$

其中:

$$
μ_j=\frac{1}{m}\sum_{i=1}^mx^{(i)}_j
$$

$$
σ^2_j=\frac{1}{m}\sum_{i=1}^m(x^{(i)}_j-μ_j)^2
$$

对$m$个无标签数据分别计算出他们每个特征的期望$μ$和方差$σ^2$。注意,这里$μ$和$σ$都是m维度的向量,而$μ_j$和$σ_j$都是其中对应的第$j$个元素。

  • 3.给定一个新的样本$x$,计算出它对应的$p(x)$:

$$
p(x)=Π_{j=1}^np(x_j;μ_j,σ^2_j)=Π_{j=1}^n\frac{1}{\sqrt{2π}σ_j}exp(-\frac{(x_j-μ_j)^2}{2σ^2_j})
$$

通过判断$p(x)<ε$,来判断是否有异常发生。

给定一个用户行为的样本,如何知道用户行为是否异常呢?我们将用户行为数据带入到$p(x)$的计算中来,如果这个结果非常小,那么我们就将这个行为标注为异常行为。

异常分析例子

假如说我们有下面这样的数据集:

从图中我们可以看出,数据集有两个特征$x_1$和$x_2$。

其中特征$x_1$对应的是水平方向的数据,它的均值是5,标准差是2;$x_2$对应的是竖直方向上的数据,它的均值是3,标准差是1:

$$
μ_1=5,σ_1=2
$$

$$
μ_2=3,σ_2=1
$$

这两个特征对应的分布如下:

$p(x_1;μ_1,σ^2_1)$ $p(x_2;μ_2,σ^2_2)$

如果绘制出$p(x)$的图像,那么这个图像如下:

通过图像,我们可以得出具体的某一点对应的高度值。

假如$x_1=2$,$x_2=2$那么就是这个点:

在3-D表面图上的高度就代表$p(x)$的值。而这个$p(x)$完整的写出来就是下面的形式:

$$
p(x)=p(x_1;μ_1,σ^2_1)p(x_2;μ_2,σ^2_2)
$$

那么有了这个表达式,我们如何鉴定新的样本是否异常呢?

要回答这个问题,我们可以先给计算机设某个无穷小的数值$ε$,假如我设置$ε=0.02$(我会在后面讲到如何选取$ε$的值)。

现在我们有两个样本,分别为$x_{test}^{(1)}$和$x_{test}^{(2)}$:

我们用上面的式子来计算出$p(x_{test}^{(1)})$,可以发现这是一个比较大的数,具体大小是大于等于$ε$的,所以对于$x_{test}^{(1)}$的检测结果是不属于异常。同样对于$p(x_{test}^{(2)})$,我们发现这是一个很小的数,具体值是小于$ε$的,所以我们说$x_{test}^{(2)}$属于异常数据。

坚持原创技术分享,您的支持将鼓励我继续创作!