公司笔试题目分享

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

公司笔试题目分享
2021-04-16-竞技世界笔试回忆
笔试题目
某游戏彩票外企Java笔试题
C语言笔试题目整理
需求分析 - 你如何对需求原型进行理解和拆分
产品岗笔试题：字节跳动历年真题精选
纯 HTML+CSS+JavaScript 编写的计算器应用
神奇的卡特兰数
笔试题目记录

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 的联系给定维空间中一个包含个点的数据集 , 以及期望其聚成簇：, 我们...
2021-04-16-竞技世界笔试回忆
总体来说，竞技世界的笔试给了我不少好感，许多公司的笔试题目都是语法题，但竞技世界不是，竞技世界总体来说笔试题目更多...
笔试题目
1 深信服笔试题2 这道题不难，但是考试的时候思路很乱，写的也很乱，也没通过测试用例，还好拍下来（突然想起来还开了...
某游戏彩票外企Java笔试题
第一轮笔试笔试形式：paper test题目难易程度：中等笔试时间：1个小时笔试语言：题目和答题全部用英文 1 ...
C语言笔试题目整理
结束繁忙的毕业季，总结了一波面试笔试的经验，下面分享一些遇到过的笔试题目：整数分解题目描述：一个正整数有可能...
需求分析 - 你如何对需求原型进行理解和拆分
学习完整课程请移步互联网 Java 全栈工程师某公司的产品面试，面试前该公司让面试者做一道笔试题，笔试题目为：...
产品岗笔试题：字节跳动历年真题精选
以下题目来自字节跳动往年产品岗笔试题精选题目分享：（因为其他平台目前暂时只有题目没有相关答案参考，因此这里抛砖引...
纯 HTML+CSS+JavaScript 编写的计算器应用
一道笔试题之前偶然看到一个公司的笔试题，题目如下：用HTML5、CSS3、JavaScript，做一个网页，实...
神奇的卡特兰数
首先看一道笔试题： C语言应用：下面是一些大公司的笔试题先来一道阿里巴巴的笔试题目：16个人按顺序去买烧饼，其中...
笔试题目记录
32位机器上，以下结构的sizeof(P)为 /*考察结构体对齐和填充：结构体每个成员相对于结构体首地址的偏移量...

公司笔试题目分享

1 K-means 与 EM 的联系

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

其他

相关文章

公司笔试题目分享

2021-04-16-竞技世界笔试回忆

笔试题目

某游戏彩票外企Java笔试题

C语言笔试题目整理

需求分析 - 你如何对需求原型进行理解和拆分

产品岗笔试题：字节跳动历年真题精选

纯 HTML+CSS+JavaScript 编写的计算器应用

神奇的卡特兰数

笔试题目记录

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

机器学习中的数学