cs / machine-learning

K-means

无监督学习(Unsupervised Learning)是机器学习的一种类型,它的核心特点是:训练数据没有标签。也就是说,算法在学习时,并不知道哪些是“对”或者“错”的答案,它只能从数据中自己“找规律”

Clustering 问题是一类 unsupervised learning 问题.

example: customer segmentation. 将客户分组,以便在决策(如信用卡审批)或营销(如产品推广)中提供帮助。

我们将介绍两种 clustering 的算法: K-means 以及 GMM

K-means 其实算是 GMM 的一种特殊情况.

k-means Algorithm 的 idea 即:

  • 给定 无标签 数据
    {x(n)}(n=1,…,N)\{ \mathbf{x}^{(n)} \} \quad (n = 1, \ldots, N)
  • 假设这些数据属于 KK 个 clusters(ex: K=2K = 2)
  • 找到这些簇

使用指示变量 rnk∈{0,1},1≤n≤N,1≤k≤Kr_{nk} \in \{0, 1\}, 1\leq n \leq N,1\leq k \leq K 作为待学习的 parameter:

  • rnk=1r_{nk} = 1 当 x(n)\mathbf{x}^{(n)} 属于第 kk 个簇时

  • rnk=0r_{nk} = 0 otherwise

寻找 cluster center μk\mu_k 和分配变量 rnkr_{nk},以 minimize distortion measure JJ: $J=∑k=1K∑n=1Nrnk∥x(n)−μk∥2 J = \sum_{k=1}^K \sum_{n=1}^N r_{nk} \left\| \mathbf{x}^{(n)} - \mu_k \right\|^2 $

其中 cluster center 的计算公式为: $μk=1Nk∑n:x(n)∈cluster kx(n)=∑n=1Nrnkx(n)∑n=1Nrnk \mu_k = \frac{1}{N_k} \sum_{n : \mathbf{x}^{(n)} \in \text{cluster } k} \mathbf{x}^{(n)} = \frac{\sum_{n=1}^N r_{nk} \mathbf{x}^{(n)}}{\sum_{n=1}^N r_{nk}} $ (当然这是 trivial 的, 就是 mean point)

distortion measure JJ 就是: squared distance of points from the center of its own cluster, 简称为 intra-cluster variation.

The K-Means Algorithm

  • 初始化簇中心

  • 重复以下步骤直到收敛:

    • cluster assignment:(E step)

      将每个点分配给最近的簇中心: $rnk={1若 k=arg⁡min⁡j∥x(n)−μj∥20否则 r_{nk} = \begin{cases} 1 & \text{若 } k = \arg\min_j \left\| \mathbf{x}^{(n)} - \mu_j \right\|^2 \\ 0 & \text{否则} \end{cases} $

    • 参数更新:更新簇中心(M step)

    μk=∑nrnkx(n)∑nrnk\mu_k = \frac{\sum_n r_{nk} \mathbf{x}^{(n)}}{\sum_n r_{nk}}
python
import numpy as np

def euclidean_distance(x: np.ndarray, y: np.ndarray) -> np.ndarray:
    assert x.shape == y.shape
    error = np.sqrt(np.sum(np.power(x - y, 2), axis=-1))
    return error

def train_kmeans(train_data: np.ndarray, initial_centroids, *, num_iterations: int = 50):
    N, d = train_data.shape
    K, d2 = initial_centroids.shape
    if d != d2:
        raise ValueError(f"Invalid dimension: {d} != {d2}")
    assert train_data.dtype.kind == 'f'

    centroids = initial_centroids.copy()
    
    for i in range(num_iterations):
        # E-step: Assign each point to the nearest centroid
        # Expand dims for broadcasting: train_data (N, 1, d), centroids (1, K, d)
        distances = np.linalg.norm(train_data[:, np.newaxis, :] - centroids[np.newaxis, :, :], axis=2)  # shape (N, K)
        labels = np.argmin(distances, axis=1)  # shape (N,)

        # M-step: Update centroids
        new_centroids = np.zeros_like(centroids)
        for k in range(K):
            points_in_cluster = train_data[labels == k]
            if len(points_in_cluster) > 0:
                new_centroids[k] = np.mean(points_in_cluster, axis=0)
            else:
                new_centroids[k] = centroids[k]  # If a cluster has no points, keep old centroid

        centroids = new_centroids
        
        # monitor convergence
        assigned_centroids = centroids[labels]
        mean_error = np.mean(euclidean_distance(train_data, assigned_centroids))
        print(f'Iteration {i:2d}: mean error = {mean_error:2.2f}')
        
    assert centroids.shape == (K, d)
    return centroids

Applying K-means to image compression

python
import numpy as np

def compress_image(image: np.ndarray, centroids: np.ndarray) -> np.ndarray:
    """Compress image by mapping each pixel to the closest centroid."""

    H, W, C = image.shape
    K, C2 = centroids.shape
    assert C == C2 == 3, "Invalid number of channels."
    assert image.dtype == np.uint8

    # Step 1: reshape image to (N, 3) where N = H * W
    flat_image = image.reshape(-1, 3).astype(np.float32)  # shape (N, 3)

    # Step 2: compute distances to all centroids
    distances = np.linalg.norm(flat_image[:, np.newaxis, :] - centroids[np.newaxis, :, :], axis=2)  # shape (N, K)

    # Step 3: find closest centroid index for each pixel
    labels = np.argmin(distances, axis=1)  # shape (N,)

    # Step 4: map each pixel to its centroid
    compressed_flat = centroids[labels]  # shape (N, 3)

    # Step 5: reshape back to image shape
    compressed_image = np.round(compressed_flat).astype(np.uint8).reshape(H, W, C)

    assert compressed_image.dtype == np.uint8
    assert compressed_image.shape == (H, W, C)
    return compressed_image

Note: 这个 image,我们在处理的时候都是变成 (N = HM, 3) 来处理

如果我们把图像 reshape 成 (N, 3),是不是就丢掉了像素之间的空间结构(space topology)?比如谁是邻居,哪个区域属于同一物体?

答案是:是的,标准的 K-means 是忽略空间拓扑结构的!

📦 为什么我们还能用它来压缩图像?

虽然 K-means 忽略空间关系,它仍然能在 颜色分布 上做聚类 —— 也就是说,它试图把所有像素的颜色压缩成 K 种代表色。

它的效果好不好,取决于图像是“色彩分布主导”还是“空间结构主导”:

图像类型 K-means 压缩效果
渐变、纯色块、多彩卡通图 很好
纹理复杂、结构强烈、边缘清晰的图 容易出现 artifacts(马赛克感)

🤔 那如果我想要用空间结构呢?

这就引出了更高级的模型,比如:

1. Spatial-aware K-means / Bilateral K-means

  • 你可以把每个像素除了 (R, G, B) 之外,再加上 (x, y) 空间坐标!
  • 变成 (R, G, B, x, y),也就是 d = 5 的数据点。
  • 然后做 K-means,就能同时考虑颜色 + 空间邻近性。

示意代码:

python
H, W, _ = image.shape
pixels = image.reshape(-1, 3).astype(np.float32)

# 加入空间位置(归一化)
x_coords, y_coords = np.meshgrid(np.linspace(0, 1, W), np.linspace(0, 1, H))
position = np.stack([x_coords, y_coords], axis=2).reshape(-1, 2)

# 拼接颜色和位置
features = np.concatenate([pixels, position], axis=1)  # shape (N, 5)

# 训练 K-means
centroids = train_kmeans(features, initial_centroids=... , num_iterations=...)

当然这样压缩出来的颜色可能要再从 centroids[:, :3] 拿回来变成图像。


2. Graph-based clustering

如果你真的很关心“谁跟谁是邻居”,可以用:

  • Mean shift
  • DBSCAN
  • 或者构图然后用 spectral clustering

这些都更尊重空间拓扑,但计算代价也更高。


✅ 小结

方法 是否考虑空间结构 说明
原始 K-means ❌ 只考虑颜色,速度快,结果像色彩量化
K-means + 坐标 ✅(部分) 折中方法,考虑颜色 + 空间
图像分割(如 SLIC, GraphCut) ✅✅ 更复杂,更保拓扑,但更慢

你对 “space topology” 感兴趣是很棒的方向——这是计算机视觉里图像分割、语义分割的重要话题。如果你愿意深入,我可以给你推荐一些入门例子或论文。

要不要我给你加上空间感知的 K-means 版本?

Gaussian Mixture

K-Means 使用 hard clustering assignment

  • 每个点只能属于一个簇。

高斯混合模型(Mixture of Gaussians)使用 soft clustering

  • 一个点可以被多个簇共同解释。
  • 不同的簇会承担不同程度的“责任”(responsibility),即该点属于每个簇的后验概率。
  • (实际上,该点只由某一个簇生成,但我们不知道具体是哪个,于是我们为每个簇分配一个概率)

**图示:**如 (0.97,0.03)(0.97, 0.03) 表示该点以 97% 概率属于 簇2,以 3% 概率属于簇2

![Screenshot 2025-03-31 at 15.37.07](09(2)-Clustering(Kmeans&GMM).assets/Screenshot 2025-03-31 at 15.37.07.png)

不同的 clusters take different levels of responsibility for a point. 一个点上, responsibility 即 posterior probability.

Modeling

GMM Algorithm

  • Initialize parameters randomly θ={πk,μk,Σk}k=1K\theta=\left\{\pi_k, \mu_k, \Sigma_k\right\}_{k=1}^K

  • Repeat until convergence (alternating optimization)

  • E Step: Given fixed parameters θ\theta, set q(n)(z)=p(z∣x(n),θ)q^{(n)}(\mathbf{z})=p\left(\mathbf{z} \mid \mathbf{x}^{(n)}, \theta\right) $γ(znk)=πkN(x(n)∣μk,Σk)∑j=1KπjN(x(n)∣μj,Σj)=P(zk=1∣x(n)) \gamma\left(z_{n k}\right)=\frac{\pi_k \mathcal{N}\left(\mathbf{x}^{(n)} \mid \mu_k, \Sigma_k\right)}{\sum_{j=1}^K \pi_j \mathcal{N}\left(\mathbf{x}^{(n)} \mid \mu_j, \Sigma_j\right)}=P\left(z_k=1 \mid \mathbf{x}^{(n)}\right) $

  • M Step: Given fixed q(z(n))′q\left(\mathbf{z}^{(n)}\right)^{\prime} 's for x(n)\mathbf{x}^{(n)} 's (or γ(znk))\left.\gamma\left(z_{n k}\right)\right), update θ\theta :

    in order to get $θnew:=arg⁡max⁡θ∑n∑zq(n)(z)log⁡p(z,x(n)∣θ) \theta^{new} : = \arg \max _\theta \sum_n \sum_{\mathbf{z}} q^{(n)}(\mathbf{z}) \log p\left(\mathbf{z}, \mathbf{x}^{(n)} \mid \theta\right) Weupdate: We update: πknew =NkN=∑nγ(znk)Nμknew =1Nk∑n=1Nγ(znk)x(n)Σknew =1Nk∑n=1Nγ(znk)(x(n)−μknew )(x(n)−μknew )⊤ \begin{aligned} & \pi_k^{\text {new }}=\frac{N_k}{N}=\frac{\sum_n \gamma\left(z_{n k}\right)}{N} \\ & \mu_k^{\text {new }}=\frac{1}{N_k} \sum_{n=1}^N \gamma\left(z_{n k}\right) \mathbf{x}^{(n)} \\ & \Sigma_k^{\text {new }}=\frac{1}{N_k} \sum_{n=1}^N \gamma\left(z_{n k}\right)\left(\mathbf{x}^{(n)}-\mu_k^{\text {new }}\right)\left(\mathbf{x}^{(n)}-\mu_k^{\text {new }}\right)^{\top} \end{aligned} $

Proof of M step update rule

我们上面已经给出 parameter 的更新算法,现在我们证明为什么这些 Parameters 是 argmax 的.

首先,我们先简化表达式: $J(π,μ,Σ)=∑n=1N∑k=1Kq(n)(zk)log⁡p(zk,x(n)∣πk,μk,Σk)=∑n=1N∑k=1Kγ(znk)(log⁡πk+log⁡1(2π)m/2(det⁡Σk)1/2−12(x(n)−μk)⊤Σk−1(x(n)−μk))=∑n=1N∑k=1Kγ(znk)log⁡πk−∑n=1N∑k=1Kγ(znk)log⁡((2π)m/2(det⁡Σk)1/2)=∑n=1N∑k=1Kγ(znk)log⁡πk−12∑n=1N∑k=1Kγ(znk)(x(n)−μk)⊤Σk−1(x(n)−μk)−12∑n=1N∑k=1Kγ(znk)(x(n)−μk)⊤Σk−1(x(n)−μk)+const \begin{aligned} J(\boldsymbol{\pi}, \boldsymbol{\mu}, \boldsymbol{\Sigma})= & \sum_{n=1}^N \sum_{k=1}^K q^{(n)}\left(\mathbf{z}_k\right) \log p\left(\mathbf{z}_k, \mathbf{x}^{(n)} \mid \pi_k, \boldsymbol{\mu}_k, \boldsymbol{\Sigma}_k\right) \\ = & \sum_{n=1}^N \sum_{k=1}^K \gamma\left(\mathbf{z}_{n k}\right)\left(\log \pi_k+\log \frac{1}{(2 \pi)^{m / 2}\left(\operatorname{det} \boldsymbol{\Sigma}_k\right)^{1 / 2}}-\frac{1}{2}\left(\mathbf{x}^{(n)}-\boldsymbol{\mu}_k\right)^{\top} \boldsymbol{\Sigma}_k^{-1}\left(\mathbf{x}^{(n)}-\boldsymbol{\mu}_k\right)\right. \bigg)\\ = & \sum_{n=1}^N \sum_{k=1}^K \gamma\left(\mathbf{z}_{n k}\right) \log \pi_k-\sum_{n=1}^N \sum_{k=1}^K \gamma\left(\mathbf{z}_{n k}\right) \log \left((2 \pi)^{m / 2}\left(\operatorname{det} \boldsymbol{\Sigma}_k\right)^{1 / 2}\right) \\ = & \sum_{n=1}^N \sum_{k=1}^K \gamma\left(\mathbf{z}_{n k}\right) \log \pi_k-\frac{1}{2} \sum_{n=1}^N \sum_{k=1}^K \gamma\left(\mathbf{z}_{n k}\right)\left(\mathbf{x}^{(n)}-\boldsymbol{\mu}_k\right)^{\top} \boldsymbol{\Sigma}_k^{-1}\left(\mathbf{x}^{(n)}-\boldsymbol{\mu}_k\right) \\ & -\frac{1}{2} \sum_{n=1}^N \sum_{k=1}^K \gamma\left(\mathbf{z}_{n k}\right)\left(\mathbf{x}^{(n)}-\boldsymbol{\mu}_k\right)^{\top} \boldsymbol{\Sigma}_k^{-1}\left(\mathbf{x}^{(n)}-\boldsymbol{\mu}_k\right)+\mathrm{const} \end{aligned} $ 因而我们 differentiate:

{A4E22888-7017-4186-8D9C-B712353A6389}

2. [20 分] EM for GDA with missing labels

在本题中,我们将使用 EM 算法来处理标签不完整时的高斯判别分析 (GDA) 问题

假设你有一个数据集,其中一部分数据 is labeled,另一部分 unlabeled.

我们希望在这个partially labelled dataset上学习一个generative model.

注:这种学习设定被称为半监督学习(semi-supervised learning),是机器学习中的一个重要研究方向。

In particular, 我们假设我们有 ll 个带标签的样本和 uu 个未标记的样本,即: $D={(x(1),y(1)),⋯ ,(x(l),y(l)),x(l+1),⋯ ,x(l+u)} D = \{(x^{(1)}, y^{(1)}), \cdots, (x^{(l)}, y^{(l)}), x^{(l+1)}, \cdots, x^{(l+u)}\} \notag $

We also make the following assumptions

  • The data is real-valued MM 维向量,即 x∈RMx \in \mathbb{R}^M
  • 标签 y∈{0,1}y \in \{0, 1\}(即一个二分类问题)
  • We model the data following the same assumption as in GDA:
P(x,y)=P(y)P(x∣y)(1)P(x, y) = P(y) P(x \mid y) \tag{1}P(y=j)={ϕif j=11−ϕif j=0(2)P(y = j) = \begin{cases} \phi & \text{if } j = 1 \\ 1 - \phi & \text{if } j = 0 \end{cases} \tag{2}P(x∣y=j)=N(x;μj,Σj),j=0 or 1(3)P(x \mid y = j) = \mathcal{N}(x; \mu_j, \Sigma_j), \quad j = 0 \text{ or } 1 \tag{3}

where ϕ\phi 是伯努利分布的参数(即 0≤ϕ≤10 \leq \phi \leq 1),μj\mu_j 和 Σj\Sigma_j 分别是第 jj 类的 class-specific mean 和 covariance matrix. (因为只有两类, 为了简化记号,也可以写成 ϕ1=ϕ\phi_1 = \phi,ϕ0=1−ϕ\phi_0 = 1 - \phi)

Multivariate Gaussian distribution N(x;μj,Σj)\mathcal{N}(x; \mu_j, \Sigma_j) 定义如下:

p(x∣y=j;μj,Σj)=N(x;μj,Σj)=1(2π)M/2∣Σj∣1/2exp⁡(−12(x−μj)⊤Σj−1(x−μj))(4)p(x \mid y = j; \mu_j, \Sigma_j) = \mathcal{N}(x; \mu_j, \Sigma_j) = \frac{1}{(2\pi)^{M/2} |\Sigma_j|^{1/2}} \exp\left(-\frac{1}{2}(x - \mu_j)^\top \Sigma_j^{-1}(x - \mu_j)\right) \tag{4}

由于存在未标记数据,我们的目标是最大化以下混合目标函数:

J=∑i=1llog⁡p(x(i),y(i))+λ∑i=l+1l+ulog⁡p(x(i))(5)J = \sum_{i=1}^l \log p(x^{(i)}, y^{(i)}) + \lambda \sum_{i = l+1}^{l+u} \log p(x^{(i)}) \tag{5}

其中,λ\lambda 是超参数,用于控制 labeled and unlabeled data 的 weight.

由于我们没有 explicitly model p(x)p(x) 的形式,我们使用全概率公式将目标函数重写为:

J=∑i=1llog⁡p(x(i),y(i))+λ∑i=l+1l+ulog⁡∑j∈{0,1}p(x(i),y(i)=j)(6)J = \sum_{i=1}^l \log p(x^{(i)}, y^{(i)}) + \lambda \sum_{i = l+1}^{l+u} \log \sum_{j \in \{0,1\}} p(x^{(i)}, y^{(i)} = j) \tag{6}

通过这种方式,unlabeled training examples 使用了与 labeled samples 相同的模型. 我们将使用 EM 算法来优化上述目标函数.


在推导解法时,请给出所有必要的推导步骤,并尽量解释推导的过程,使之易于理解。

提示: 你可以使用如下等式:

p(x(i),y(i))=∏j∈{0,1}[ϕj(2π)M/2∣Σj∣1/2exp⁡(−12(x(i)−μj)⊤Σj−1(x(i)−μj))]I[y(i)=j](7)p(x^{(i)}, y^{(i)}) = \prod_{j \in \{0,1\}} \left[ \frac{\phi_j}{(2\pi)^{M/2} |\Sigma_j|^{1/2}} \exp\left( -\frac{1}{2}(x^{(i)} - \mu_j)^\top \Sigma_j^{-1}(x^{(i)} - \mu_j) \right) \right]^{\mathbb{I}[y^{(i)} = j]} \tag{7}

(a) lower bound derivation [3 points]

(a) 推导 objective JJ 的 variational lower bound . Specifically, 证明对于任意的概率分布 qi(y(i)=j)q_i(y^{(i)} = j),objective 的 lower bound 可以写为: $ L(\mu, \Sigma, \phi) = \sum_{i=1}^l \log p(x^{(i)}, y^{(i)}) + \lambda \sum_{i=l+1}^{l+u} \sum_{j \in \{0,1\}} Q_{ij} \log \frac{p(x^{(i)}, y^{(i)} = j)}{Q_{ij}} \tag{8} $

其中,Qij≜qi(y(i)=j)Q_{ij} \triangleq q_i(y^{(i)} = j) 是记号简化。

提示: 可以考虑使用 Jensen 不等式来推导。

(b) E-step [2 points]

Write down the E-step. Specifically, define the distribution Qij=qi(y(i)=j)Q_{ij} = q_i(y^{(i)} = j)

(c) M-step for μk\mu_k [6 points]

推导当 k=0k = 0 或 11 时,μk\mu_k 的 M-step update rule, while holding QiQ_i's fixed.

并文字解释:从直觉上看,what μk\mu_k looks like ? in terms of x(i)x^{(i)}'s (labeled and unlabeled) 以及 pseudo-counts.

(d) M-step for ϕ\phi

[6 points] 推导 ϕ∈R\phi \in \mathbb{R} 的 M-step update rule, while holding QiQ_i's fixed.

并文字解释:从直觉上看,what ϕ\phi looks like ? in terms of x(i)x^{(i)}'s (labeled and unlabeled) 以及 pseudo-counts.

(e) M-step for Σk\Sigma_k

[3 points] 最后,based on analogy, 写出 Σk\Sigma_k (k=0k = 0 或 11)的 M-step update rule。

由于我们知道推导过程与 GDA(高斯判别分析)或 GMM 的 M 步类似,因此你不需要重复完整推导步骤(你已经在之前任务中练习过)。

并文字解释:从直觉上看,what Σk\Sigma_k looks like ? in terms of x(i)x^{(i)}'s (labeled and unlabeled) 以及 pseudo-counts.