Lec4: K-means 与概率基础

K-means 的目标与 Lloyd 算法，以及条件概率、贝叶斯公式和基础发生率。

聚类目标#

聚类根据输入结构分组，簇号没有预先定义的类别语义。相似性依赖特征表示和距离，同一数据可以因任务不同得到不同分组。

设样本总数为 $N$ ，第 $i$ 个样本为 $x_i\in\mathbb R^d$ ， $i$ 是编号。簇数为 $K$ ，中心为 $c_k$ ，归属为 $z_i\in\{1,\ldots,K\}$ 。K-means 最小化：

J(z,c)=\sum_{i=1}^{N}\|x_i-c_{z_i}\|_2^2 =\sum_{k=1}^{K}\sum_{i\in\mathcal I_k}\|x_i-c_k\|_2^2.

$\mathcal I_k=\{i:z_i=k\}$ 是第 $k$ 个簇的样本索引集合。

$c_{z_i}$ 是样本 $i$ 所属簇的中心。在距离表达式中，下标 $2$ 表示 $L_2$ 范数，上标 $2$ 表示对范数值再平方：

\|v\|_2=\sqrt{\sum_{j=1}^{d}v_j^2},\qquad \|v\|_2^2=\sum_{j=1}^{d}v_j^2.

例如样本为 $(1,2)$ ，所属中心为 $(4,6)$ ，欧氏距离为 $5$ ，该样本对目标的贡献是距离平方：

\|x_i-c_{z_i}\|_2^2=(1-4)^2+(2-6)^2=25.

目标函数将所有样本到各自簇中心的距离平方相加。

固定中心，将每个样本分到最近中心：

z_i\in\arg\min_k\|x_i-c_k\|_2^2.

固定归属，对中心求导：

\nabla_{c_k}J=2N_kc_k-2\sum_{i\in\mathcal I_k}x_i=0.

得到均值更新：

c_k=\frac1{N_k}\sum_{i\in\mathcal I_k}x_i, \qquad N_k=|\mathcal I_k|>0.

初始化中心后反复进行分配和更新，直到稳定。分母是簇内样本数，空簇需要显式处理。更换距离后，均值未必仍是最优代表点。

两个子步骤均不增加目标，目标又有下界零，因此目标值收敛；这不保证全局最优。并列距离的处理、空簇策略和停止条件会影响具体实现。

每轮主要复杂度为 $O(NKd)$ ，迭代 $T$ 轮约为 $O(TNKd)$ 。

两个中心的等距边界满足：

2(c_b-c_a)^{\mathsf T}x=\|c_b\|_2^2-\|c_a\|_2^2.

边界是超平面，形成 Voronoi 划分。K-means 更适合紧凑、尺度相近的点群，对非凸、细长或尺度差异大的簇可能不合适。

最优训练目标随簇数增加不增：

J_{K+1}^*\leq J_K^*.

因此不能按训练目标最小直接选择 $K$ 。将 RGB 像素聚类并替换为中心颜色可实现颜色量化，但不等于语义分割。

欧氏距离是度量，平方欧氏距离不满足三角不等式。例如：

(0-2)^2=4>(0-1)^2+(1-2)^2=2.

下式为离散情形；连续变量边缘化时改用积分。

边缘分布：

p(x)=\sum_y p(x,y).

条件分布与乘法规则：

p(y\mid x)=\frac{p(x,y)}{p(x)},\qquad p(x)>0.

p(x,y)=p(y\mid x)p(x).

独立：

X\perp Y\quad\Longleftrightarrow\quad p(x,y)=p(x)p(y).

独立同分布（i.i.d.）样本的联合分布：

p(x_1,\ldots,x_N\mid\theta)=\prod_{i=1}^{N}p(x_i\mid\theta).

样本对 $(X_i,Y_i)$ 之间独立，不意味着单个样本内部的输入与标签独立。K-means 的代数优化本身不需要先假设 i.i.d.，统计泛化解释则需要抽样假设。

p(x\mid y)=\frac{p(y\mid x)p(x)}{\sum_{x'}p(y\mid x')p(x')}.

先验是观测前的信息，似然描述给定假设下观测的可能性，后验结合观测更新判断。

令 $W=1$ 表示真实唤醒词， $D=1$ 表示检测器触发。课件假设：

P(W=1)=0.0001,\quad P(D=1\mid W=1)=0.99,\quad P(D=1\mid W=0)=0.001.

则：

P(W=1\mid D=1)= \frac{0.99\times0.0001}{0.99\times0.0001+0.001\times0.9999} \approx9\%.

正例极少时，即使召回率高、假正例率低，正类预测也可能以误报为主。不能混淆“有唤醒词时能检出”与“检出时确有唤醒词”。