公司笔试题目分享

作者: 水之心 | 来源:发表于2018-11-16 21:59 被阅读0次

1 K-means 与 EM 的联系

给定 $n$ 维空间中一个包含 $m$ 个点的数据集 $D = (x_1, x_2, \cdots, x_m)^T$ , 以及期望其聚成 $k$ 簇： $\mathcal{C} = \{C_1, C_2, \cdots, C_k\}$ , 我们可以定义每个簇的中心点为

$\mu_i = \frac{1}{m_i} \displaystyle \sum_{x_j \in C_i} x_j$

其中 $m_i=|C_i|$ 表示簇 $C_i$ 的点的个数。这样，K-means 算法的目标函数 (平方差和) 为：

$\text{SSE}(\mathcal{C}) = \displaystyle \sum_{i=1}^k \sum_{x_j \in C_i} ||x_j - \mu_i||^2$

1.1 EM 算法的基本原理和步骤

假设每一个簇 $C_i$ 都由一个多元正态分布刻画，即

$f_i(x) = f(x|C_i;\mu_i,\Sigma_i) = \frac{1}{(2\pi)^{\frac{n}{2}}|\Sigma_i|^{\frac{1}{2}}} \exp\{- \frac{(x-\mu_i)^T\Sigma_i^{-1}(x-\mu_i)}{2}\}$

其中，簇均值 $\mu_i \in \mathbb{R}^n$ 及协方差矩阵 $\Sigma_i \in \mathbb{R}^{n\times n}$ 均是未知参数。 $f_i(x)$ 是 $x$ 属性属于簇 $C_i$ 的概率密度。令 $X_j$ 表示对应 $x_i$ 的第 $j$ 维度的随机变量，记 $X = (X_1, X_2, \cdots, X_d)^T$ 代表对应于 $d$ 个维度的随机向量。假设 $X$ 的概率密度函数是在所有 $k$ 个簇之上的高斯混合模型，定义为

$f(x) = \displaystyle \sum_{i=1}^k f_i(x)P(C_i) = \sum_{i=1}^k f_i(x|C_i;\mu_i,\Sigma_i)P(C_i)$

其中先验概率 $P(C_i)$ , 满足

$\displaystyle \sum_{i=1}^k P(C_i) = 1$

我们将簇 $C_i$ 的参数简记作

$\theta_i = \{\mu_i, \Sigma_i, P(C_i)\}$

则 $\theta =\{\theta_1, \ldots, \theta_k\}$ 的似然为

$P(D|\theta) = \prod_{j=1}^m f(x_j)$

则 MLE (极大似然估计) 为

$\theta^* = \arg\max_{\theta} \ln (P(D|\theta))$

由贝叶斯公式可知

$P(C_i|x_j) = \frac{P(x_j|C_i)P(C_i)}{\sum_{t}^kP(x_j| C_t)P(C_t)}$

由于每个簇都建模为一个多元正态分布，故而

$P(x_j|C_i) \approx 2\epsilon \cdot f_i(x_j)$

因而， $P(C_i|x_j)$ 可以看作是点 $x_j$ 在簇 $C_i$ 中的权值或贡献。

$i=1,\ldots,k$

初始化： $t\leftarrow0$ , 对于每一个簇 $C_i$ , 均值 $\mu_i^t$ 使用均匀分布随机地初始化且 $\Sigma_i^t \leftarrow I$ , $P^t(C_i) \leftarrow \frac{1}{k}$ .
E 步：计算 $w_{ij} \leftarrow P^t(C_i|x_j)$ , 且记 $w_i \leftarrow (w_{1i}, \ldots, w_{mi})^T$ 表示簇 $C_i$ 在所有 $m$ 个点上的权向量。
M 步：重新估计 $\Sigma_i^t, \mu_i^t, P^t(C_i)$ , 即

$\begin{aligned} &\mu_i^t \leftarrow \frac{D^Tw_i}{w_i^T\mathbf{1}}\\ &\Sigma_i^t \leftarrow \frac{\sum_{j=1}^m w_{ij}(x_j - \mu_i)(x_j - \mu_i)^T}{w_i^T\mathbf{1}}\\ &P^t(C_i) \leftarrow \frac{w_i^T\mathbf{1}}{m} \end{aligned}$

不断地依次重复操作 $E$ 步和 $M$ 步，直到

$\sum_{i=1}^k ||\mu_i^t - \mu_i^{t-1}||^2 \leq \epsilon$ .

公司笔试题目分享

1 K-means 与 EM 的联系

1.1 EM 算法的基本原理和步骤

其他

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

机器学习中的数学