聚类

我们的问题为：

$$

\min _{C_{1}, \ldots, C_{K}} \sum_{k=1}^{K} W\left(C_{k}\right)

$$

$$

W\left(C_{k}\right)=\frac{1}{\left|C_{k}\right|} \sum_{i, j \in C_{k}}\Vert x_{i}-x_{j}\Vert _{2}^{2}

$$

最优化问题为：

$$

\min _{C_{1}, \ldots, C_{K}} \sum_{k=1}^{K} \frac{1}{\left|C_{k}\right|} \sum_{i, j \in C_{k}}\Vert x_{i}-x_{j}\Vert _{2}^{2}

$$

Centroid

让 \(\mu_{k}=\frac{1}{\left|C_{k}\right|} \sum_{i \in C_{k}} x_{i}\) 为 \( C_{k}\) 的 mean/centroid。

$$

\frac{1}{\left|C_{k}\right|} \sum_{i, j \in \mathcal{C}_{k}}\Vert x_{i}-x_{j}\Vert _{2}^{2}=2 \sum_{i \in C_{k}}\Vert x_{i}-\mu_{k}\Vert _{2}^{2}

$$

那么优化问题可以变为：

$$

\min _{C_{1}, \ldots, C_{K}} \sum_{k=1}^{K}\left\{\sum_{i \in C_{k}}\Vert x_{i}-\mu_{k}\Vert _{2}^{2}\right\}

$$

迭代法

$$

\text { binary matrix } R=\left[r_{n k}\right] \in R^{N \times K}

$$

$$

\text { if } x_{n} \text { is assigned to cluster } k, \text { then }r_{n k}=1 \text { and } r_{n j}=0, j \neq k

$$

目标：

找到 \(\left\{\mu_{k}\right\}\)，并把每一个数据点分配到一类，使 objective function 最小化。

$$

J\left(R,\left\{\mu_{k}\right\}\right)=\sum_{n=1}^{N}\left[\sum_{k=1}^{K} r_{n k}\Vert x_{n}-\mu_{k}\Vert ^{2}\right]

$$

• \(\mu_{k}=\frac{1}{\left|C_{k}\right|} \sum_{i \in C_{k}} x_{i}\) 为 \( C_{k}\) 的 mean/centroid。
• \(R=\left[r_{n k}\right] \in R^{N \times K}\)

重复以下两步：

1. step 1：固定 \(\{\mu_{k}\}\)，最优化 \(R\)
2. step 2：固定 \(R\)，最优化 \(\{\mu_{k}\}\)

具体如下：

step 1

对于某一个具体的 n，我们选择 \(r_{nj}\) 最小化

$$\sum_{k=1}^{K} r_{n k}\Vert x_{n}-\mu_{k}\Vert ^{2}$$

也就是说，将 \(x_n\) 分配给最接近的 centroid。

step 2

对于固定的 \(R\), \(J\left(R,\left\{\mu_{k}\right\}\right)\) 是 convex，quadratic 的，因此，将关于 \(u_{k}\) 的梯度设为 0：

$$

2 \sum_{n=1}^{N} r_{n k}\left(\mu_{k}-x_{n}\right)=0 \Rightarrow \mu_{k}=\frac{\sum_{n=1}^{N} r_{n k} x_{n}}{\sum_{n=1}^{N} r_{n k}}

$$

让 \(u_{k}\) 等于属于 cluster k 的所有数据点 \(x_n\) 的均值

k-means 算法对于异常值十分敏感，因为具有极大值的对象可能会产生严重扭曲的数据分布