问题描述

聚类应用于生活的方方面面，如人脸识别，每一个人就是一个类，将数据库中的照片与现拍的照片进行特征值的比较后划分到一个类中（即确定一个人）；又如疫情健康码，有绿码、黄码和红码三个类，根据人的居住地、最近去向、接触人群等属性将其划分到一个类中（即分配一个健康码）。

聚类问题可以描述如下：假设有$n$个无标记样本

$D = \{x_1,x_2,...,x_n\}$

任一样本为$d$维向量

$x_i = \{x_{i1},x_{i2}, ..., x_{id}\}^T$

将其按照某种相似性准则划分为若干个互不相交的子集。

k-means聚类就是指定$k$，将其划分为$k$个互不相交的子集。

问题建模

简单的想法

k-means聚类的相似性准则为样本间的欧式距离，将离得近的样本看作一个类，离得远的看作不同类。

因此，对于一个划分

$C=\{C_1,C_2,...,C_k\}$

要使其最优，所有类样本到各自类中心的距离之和就应该最小。

对于类$C_i$，其类中心为

$M_i=\frac{1}{|c_i|}\sum_{x \in C_i}x, 1 \leq i \leq k$

即类中心是该类所有类样本和的平均值，则该类所有类样本到类中心的距离之和为

$\sum_{x \in C_i}\|x-M_i\Vert_2$

上式是用$l_2$-范数表示欧式距离，这是十分常见的，更多关于范数的知识可参见：如何通俗易懂地解释「范数」？

将$k$个类累加起来，就可以得到所有类样本到各自类中心的距离之和为

$\sum_{i=1}^k\sum_{x \in C_i}\|x-M_i\Vert_2$

那么，我们的模型就可以写出来了：

$\begin{aligned} min \sum_{i=1}^k\sum_{x \in C_i} \|x-M_i\Vert_2^2 \\ \begin{equation} s.t. \left\{\begin{array}{l} \cup_{i=1}^k C_i = D \\ C_i \cap C_j = \varnothing \\ i,j \in {1, 2, ..., k} \\ i \neq j \end{array} \right. \end{equation} \end{aligned}$

注意，我们这里目标函数写成平方是为了求解方便，若不加平方，求距离就会带开方，计算不便。