机器学习笔记（17）：聚类（2）

本文来自之前在Udacity上自学机器学习的系列笔记。这是第17篇，介绍了什么是聚类（2），介绍软聚类（高斯混合聚类模型）。

正态分布回顾
软聚类牵扯到一个非常有趣的概率学知识，即正态分布。正态分布有趣之处在于现实生活中的很多数据都可以用正态分布来进行解释。

举个例子，我们抛掷1枚硬币，有 $\frac{1}{2}$ 的机会会得到正面或者反面。如果同时抛掷10枚硬币，记录当中有几个是正面的。然后重复操作一百万次，统计每一次正面数的概率分布。最终可以得到如下图所示的函数图像：

image.png

也就是说，10枚硬币中有5个是正面（或反面）的概率是最高的，然后向两边方向对称地降低概率。

具体Python代码为：

%matplotlib inline
import numpy as np
import matplotlib.pyplot as plt

n = 10
p = 0.5
size = 1000000
x=np.random.binomial(n=n, p=p, size=size)
probs_100 = [np.equal(x , i).mean() for i in range(n)]
for j in probs_100:
    print("{:.2f}".format(j))

plt.xticks(range(n))
plt.plot(list(range(n)), probs_100, color='blue', marker='o')
plt.xlabel('Number of Heads',fontsize=14)
plt.ylabel('Probability',fontsize=14)
plt.show()

除了这个例子，现实中很多数据可以用这种正态分布的形式来解释。它背后的原理是中心极限定理，即在适当的条件下，大量相互独立随机变量的均值经适当标准化后依分布收敛于正态分布。简单来说，就是一个事物不管受到什么因素，以及这些因素是如何影响的，将这些因素加起来的结果的平均呈正态分布。

在数学上，正态分布的定义如下：

若随机变量 $X$ 服从一个位置参数为 $\mu$ ，尺度参数为 $\sigma$ 的正态分布，记为：
$X ~ N(\mu, \sigma^2)$
则其概率密度函数为 $G(x)=\frac{1}{\sigma \sqrt{2\pi}} e^{- \frac{(x-\mu)^2}{2\sigma^2}}$ 。正态分布的数学期望值 $\mu$ 等于位置参数，决定了分布的位置；其方差 $\sigma^2$ 的标准差 $\sigma$ 等于尺度参数，决定了分布的幅度。对于单变量的正态分布，我们可以通过极大似然法求解出 $\mu$ 和 $\sigma^2$ 。

对于多变量（假设为d个变量）的高斯分布，概率密度函数为：

$G(X | \mu, \Sigma)=\frac{1}{ \sqrt{2\pi |\Sigma|}} e^{-\frac{{(X-\mu)^T(X-\mu)}}{2 \Sigma}}$

其中 $X$ 和 $\mu$ 是 $d$ 维的向量， $\Sigma$ 是 $d \times d$ 的协方差矩阵。

软聚类：高斯混合模型

软聚类引入正态分布，也就是说数据点看成是由多个正态分布进行混合后从中抽样得到的数据。反过来，也就可以使用该这个模型来求解聚类问题。因为正态分布又称为高斯分布，所以这个模型一般叫做高斯混合模型。

假设数据 $X$ 是从K个已知方差为 $\Sigma_k$ 的正态分布中均匀地抽样得到的 $x_i$ ， $k=1,2, \ldots, K$ ， $i=1,2, \ldots, N$ ，一共重复了N次获得了N个数据点。

因为有K个分布，概率密度可以表示为K个正态分布的密度函数的线性函数，即：
$P(X|\mu, \Sigma, \pi)=\sum_{k=1}^{K} \pi_k G(X| \mu_k, \Sigma_k)$
其中， $\pi_k$ 是第k个分布的混合系数， $\pi_k \geq 0$ 且 $\sum \pi_k = 1$ ，表示每一个正态分布的权重。而 $G(X| \mu_k, \Sigma_k)$ 表示第k个正态分布的概率密度，其表达式为 $G(X|\mu_k, \Sigma_k)=\frac{1}{\Sigma_k \sqrt{2\pi}} e^{- \frac{(X-\mu_k)^2}{2\Sigma_k^2}}$ 。

高斯混合模型的学习过程就是估计K个正态分布的概率密度，以及每个分布的权重。

所以，原来的聚类问题就转化为：将某个数据点 $x_i$ 代入到K个正态分布中求出属于每个类别的概率，然后将概率最大的类别作为该数据点的类别，直至对所有数据点归为K类为止。

$\frac{\pi_k G(x_i| \mu_k, \Sigma_k)}{\sum_{k=1}^{K} \pi_k G(x_i| \mu_k, \Sigma_k)}$

EM算法
上面的问题可以进一步转化为参数估计的问题，并使用EM算法求解。

我们的模型为：
$P(X|\mu, \Sigma, \pi)=\sum_{k=1}^{K} \pi_k G(X| \mu_k, \Sigma_k)$
$G(X|\mu_k, \Sigma_k)=\frac{1}{\Sigma_k \sqrt{2\pi}} e^{- \frac{(X-\mu_k)^2}{2\Sigma_k^2}}$

使用极大对数似然法来估计其中的参数 $\theta=(\mu_k, \Sigma_k, \pi_k), \quad k=1, 2, \ldots, K$ ，也就是
$\theta=argmax \, ln \,P(X| \theta)$
$ln \,P(X| \theta) = ln \sum_{i=1}^{N} P(x_i | \theta) = \sum_{i=1}^{N} ln \sum_{k=1}^{K} \pi_k G(x_i | \mu_k, \Sigma_k)$

定义一个隐变量 $\gamma_{ik}$ ，和我们的数据点一起构成完全数据 $(x_i, \gamma_{i1}, \gamma_{i2}, \ldots, \gamma_{iK})$ ，其中 $\gamma_{ik}$ 中只有一个为1，即当 $x_i$ 属于第 $k$ 个正态分布产生的数据点时。

高斯混合模型的EM算法步骤为：

取参数的初始值开始迭代；
E步：依据当前模型参数，计算第k个正态分布对数据 $x_i$ 的响应度
$\hat {\gamma_{ik}} = \frac{\pi_k G(x_i|\theta_k)}{\sum_{k=1}^{K} \pi_k G(x_i|\theta_k)}, \quad i=1,2, \ldots, N; \quad k=1,2, \ldots, K$
M步：计算新一轮迭代的模型参数
$\hat{\mu_k}=\frac{\sum_{i=1}^{N} \hat{\gamma_{ik} x_i}}{\sum_{i=1}^{N} \hat{\gamma_{ik}}}, \quad k=1,2, \ldots, K$
$\hat{\Sigma_k}=\frac{\sum_{i=1}^{N} \hat{\gamma_{ik}} (x_i-\mu_k)^2}{\sum_{i=1}^{N} \hat{\gamma_{ik}}}, \quad k=1,2, \ldots K$
$\hat{\pi_k}=\frac{\sum_{i=1}^{N} \hat{\gamma_{ik}}}{N}, \quad k=1,2, \ldots K$
重复第2和第3步，直至收敛。

具体EM算法的推导可以参考李航编写的《统计学习方法》一书。

机器学习笔记（17）：聚类（2）

推荐阅读更多精彩内容