Question

1. kmeans算法：给定样本集 $ MathJax-Element-2326 $ ， 针对聚类所得簇划分 $ MathJax-Element-2333 $ ， 最小化平方误差：

   $ \min_{\mathcal C} \sum_{k=1}^{K}\sum_{\mathbf{\vec x}_i \in \mathbb C_k}||\mathbf{\vec x}_i-\vec \mu_k||_2^{2} $

   其中 $ MathJax-Element-2339 $ 是簇 $ MathJax-Element-2344 $ 的均值向量。

2. 定义观测随机变量为 $ MathJax-Element-2367 $ ，观测数据为 $ MathJax-Element-2351 $ 。定义隐变量为 $ MathJax-Element-476 $ ，它表示 $ MathJax-Element-2367 $ 所属的簇的编号。设参数 $ MathJax-Element-268 $ ， 则考虑如下的生成模型：

   $ P(\mathbf {\vec x},z\mid\theta) \propto \begin{cases}\exp(-||\mathbf {\vec x}-\mathbf {\vec \mu}_z||_2^2)\quad &||\mathbf {\vec x}-\mathbf {\vec \mu}_z||_2^2=\min_{1\le k\le K}||\mathbf {\vec x}-\mathbf {\vec \mu}_k||_2^2\\ 0\quad &||\mathbf {\vec x}-\mathbf {\vec \mu}_z||_2^2\gt \min_{1\le k\le K}||\mathbf {\vec x}-\mathbf {\vec \mu}_k||_2^2 \end{cases} $

   其中 $ MathJax-Element-270 $ 表示距离 $ MathJax-Element-279 $ 最近的中心点所在的簇编号。即：

   • 若 $ MathJax-Element-279 $ 最近的簇就是 $ MathJax-Element-280 $ 代表的簇，则生成概率为 $ MathJax-Element-274 $ 。
   • 若 $ MathJax-Element-279 $ 最近的簇不是 $ MathJax-Element-280 $ 代表的簇，则生成概率等于 0 。

3. 计算后验概率：

   $ P(z\mid \mathbf{\vec x},\theta^{})\propto \begin{cases} 1\quad &||\mathbf {\vec x}_i-\mathbf {\vec \mu}_z||_2^2=\min_{1\le k\le K}||\mathbf {\vec x}-\mathbf {\vec \mu}_k^{}||_2^2\\ 0\quad &||\mathbf {\vec x}_i-\mathbf {\vec \mu}_z||_2^2\gt \min_{1\le k\le K}||\mathbf {\vec x}-\mathbf {\vec \mu}_k^{}||_2^2 \end{cases} $

   即：

   • 若 $ MathJax-Element-279 $ 最近的簇就是 $ MathJax-Element-280 $ 代表的簇，则后验概率为 1 。
   • 若 $ MathJax-Element-279 $ 最近的簇不是 $ MathJax-Element-280 $ 代表的簇，则后验概率为 0 。

4. 计算 $ MathJax-Element-358 $ 函数：

   $ Q(\theta,\theta^{})=\sum_{j=1}^N\left(\sum_z P(z\mid \mathbf{\vec x}=\mathbf{\vec x}_j;\theta^{})\log P(\mathbf{\vec x}=\mathbf{\vec x}_j,z;\theta) \right) $

   设距离 $ MathJax-Element-2418 $ 最近的聚类中心为 $ MathJax-Element-2485 $ ，即它属于簇 $ MathJax-Element-2431 $ ，则有：

   $ Q(\theta,\theta^{})=\text{const}-\sum_{j=1}^N ||\mathbf{\vec x}_j-\vec\mu_{t_j}||_2^2 $

   则有：

   $ \theta^{}=\arg\max_\theta Q(\theta,\theta^{})=\arg\min_\theta \sum_{j=1}^N ||\mathbf{\vec x}_j-\vec\mu_{t_j}||_2^2 $

   定义集合 $ MathJax-Element-2569 $ ，它表示属于簇 $ MathJax-Element-258 $ 的样本的下标集合。则有：

   $ \sum_{j=1}^N ||\mathbf{\vec x}_j-\vec\mu_{t_j}||_2^2=\sum_{k=1}^K\sum_{j\in \mathbb I_k} ||\mathbf{\vec x}_j-\vec\mu_k||_2^2 $

   则有：

   $ \theta^{}=\arg\min_\theta\sum_{k=1}^K\sum_{j\in \mathbb I_k} ||\mathbf{\vec x}_j-\vec\mu_k||_2^2 $

   这刚好就是 k-means 算法的目标：最小化平方误差。

5. 由于求和的每一项都是非负的，则当每一个内层求和 $ MathJax-Element-2722 $ 都最小时，总和最小。即：

   $ \vec\mu^{}_k=\arg\min_{\vec\mu_k}\sum_{j\in \mathbb I_k}||\mathbf{\vec x}_j-\mathbf{\vec\mu}_{k}||_2^2 $

   得到： $ MathJax-Element-2765 $ ，其中 $ MathJax-Element-2767 $ 表示集合 $ MathJax-Element-2767 $ 的大小。

   这就是求平均值来更新簇中心。