最优化：建模、算法与理论（优化建模——2）

3.10 K-均值聚类

聚类分析是 统计学中的一个基本问题，其在机器学习，数据挖掘，模式识别和图像分析中有着重要应用。聚类不同于分类，在聚类问题中我们仅仅知道数据点本身，而不知道每个数据点具体的标签。聚类分析的任务就是将一些无标签的数据点按照某种相似度来进行归类，进而从数据点本身来学习其内蕴的类别特征。

给定$p$维空间中的$n$个数据点$a_1,a_2,\cdots ,a_n$，假定两个数据点之间的相似性可以通过其欧几里得距离来测量，我们的目标是将相似的点归为一类，同时将不相似的点区分开，为了简单起来我们假设类的个数为已知的，不妨记为$k$，且同一个数据点只属于一个类，因此聚类问题就是要找$k$个不相交的非空集合$S_1,S_2,\cdots ,S_k$，使得
{ a 1 , a 2 , ⋯ , a n } = S 1 ∪ S 2 ∪ ⋯ ∪ S k \{a_1,a_2,\cdots,a_n\}=S_1\cup{S_2}\cup{\cdots}\cup{S_k} {a1​,a2​,⋯,an​}=S1​∪S2​∪⋯∪Sk​
且同类点之间的距离要足够近，为了在数学上描述"同类点之间的距离足够近"，我们定义组内距离平方和为
$$W(S_1,S_2,\cdots ,S_k)=\sum _{i=1}^k\sum _{a\in S_i}||a-c_i|{|}^2\text{\hspace{1em}(3.10.1)}$$
这里$c_i$为第$i$类数据点的中心，注意在问题中就假设了每类为非空的
定义好聚类标准后，就可以建议优化模型了。我们想要找到一个聚类方法，使得组内距离平方和最小，即
min ⁡ S 1 , S 2 , ⋯ , S k ∑ i = 1 k ∑ a ∈ S i ∣ ∣ a − c i ∣ ∣ 2 s . t . { a 1 , a 2 , ⋯ , a n } = S 1 ∪ S 2 ∪ ⋯ ∪ S k S j ∩ S j ≠ ∅ , ∀ i ≠ j (3.10.2) \min_{S_1,S_2,\cdots,S_k}\sum_{i=1}^k\sum_{a{\in}S_i}||a-c_i||^2 \\ s.t. {\quad} \{a_1,a_2,\cdots,a_n\}=S_1\cup{S_2}\cup{\cdots}\cup{S_k} \\ S_j \cap S_j {\not=}\varnothing,\forall{i {\not=}j} \tag{3.10.2} S1​,S2​,⋯,Sk​min​i=1∑k​a∈Si​∑​∣∣a−ci​∣∣2s.t.{a1​,a2​,⋯,an​}=S1​∪S2​∪⋯∪Sk​Sj​∩Sj​=∅,∀i=j(3.10.2)
问题（3.10.2）的自变量是数据点集合的分割方式，看起来比较难以处理，因此有必要将问题写成我们熟悉的形式，接下来给出问题的两种矩阵表达方式，它们之间是等价的。

1. K-均值聚类等价表述一

在原始聚类问题中，组内距离平方和定义为(3.10.1)，即需要计算$S_i$中的点到它们中心点$c_i$的平方和，实际上，选取中心点$c_i$作为参考点并不是必须的，我们完全可以选取其他点$h_i$来作为参照来计算组内距离（其实这个$h_i$通过优化最后也是表示的中心点），因此组内距离平方和可以推广为
$$W(S_1,S_2,\cdots ,S_k,H)=\sum _{i=1}^k\sum _{a\in S_i}||a-h_i|{|}^2$$
其中$H\in R^{k\times p}$（k个类的一个点（维度为p））且第$i$行的向量为$h_i^T$，为了表示聚类方式$S_1,S_2,\cdots ,S_k$，一个很自然的想法是使用一个向量${\varphi }_i\in R^k$来表示$a_i$所处的类别
$${({\varphi }_i)}_j=\{\begin{array}{c}1，a_i\in S_j\\ 0，a_i\notin S_j\end{array}$$
聚类问题等价描述为
$$\begin{gathered} \underset{\varphi ,H}{\min }||A-\Phi H|{|}_F^2 \\ s.t.\Phi \in R^{n\times k}，每一行只有一个元素为1，其余为0 \\ H\in R^{k\times p}\text{\hspace{1em}(3.10.3)} \end{gathered}$$
这里的$\Phi$的第$i$行的向量就是${\varphi }_i^T$

接下来说明3.10.3和原问题3.10.2是等价的，为此只需要说明参考点集$H$的取法实际上就是每一类的中点，当固定$Phi$时，第$i$类点的组内距离平方和为
$$\sum _{a\in S_i}||a-h_i|{|}^2$$
根据二次函数的性质，当$h_i=\frac{1}{n}{\sum }_{a\in S_i}a$时，组内距离平方和最小
所以$h_i$一定会被优化成第$i$类的中心点的

我们引入问题（3.10.3）的理由有两个
（1）形式简洁，且将不易处理的自变量“分割方式”转化为矩阵
（2）可以看成是一个矩阵分解问题，便于我们设计算法

2.K-均值聚类等价表述二

K-均值聚类的第二种等价表述利用了列正交矩阵的性质，这种表达方式比问题（3.10.3）相比更为简洁，首先定义$I_{S_t}，1\le t\le k$为$n$维空间中每个分量取值0或1的向量，且
$$I_{S_j}(i)=\{\begin{array}{c}1，a_i\in S_t\\ 0，a_i\notin S_t\end{array}$$
可以证明，第$t$类$S_t$中每个点到其中心点的距离平方和可以写成$\frac{1}{2n_t}Tr(D{I}_{S_t}{I}_{S_t}^T)$，其中$D\in R^{n\times n}$的元素为$D_{ij}=||a_i-a_j|{|}^2$。这说明$S_t$中每个点到中心点的距离平方和与$S_t$中所有点两两之间距离平方和有关，因此，我们将问题（3.10.2）转化为
min ⁡ S 1 , S 2 , ⋯ , S k 1 2 T r ( D X ) s . t . X = ∑ t = 1 k 1 n t I S t I S t T S 1 ∪ S 2 ∪ ⋯ ∪ S k = { a 1 , a 2 , ⋯ , a n } S i ∩ S j = ∅ , ∀ i ≠ j (3.10.4) \min_{S_1,S_2,\cdots,S_k}\frac{1}{2}Tr(DX) \\ s.t. {\quad}X={\sum}_{t=1}^k\frac{1}{n_t}I_{S_t}I_{S_t}^T \\ S_1{\cup}S_2{\cup}\cdots{\cup}S_k=\{a_1,a_2,\cdots,a_n\} \\ S_i{\cap}S_j={\varnothing},\forall{i{\not=}j}\tag{3.10.4} S1​,S2​,⋯,Sk​min​21​Tr(DX)s.t.X=∑t=1k​nt​1​ISt​​ISt​T​S1​∪S2​∪⋯∪Sk​={a1​,a2​,⋯,an​}Si​∩Sj​=∅,∀i=j(3.10.4)
对半正定举证$X$进行分解$X=Y{Y}^T,Y\in R^{n\times k}$，我们可以进一步得到如下矩阵优化问题（这里$I$是$n$维向量且分量全为1）
$$\begin{gathered} \underset{Y\in R^{n\times k}}{\min }Tr(Y^{T}DY) \\ s.t.Y{Y}^{T}I=I, \\ Y{Y}^T=I_k，Y\ge 0\text{\hspace{1em}(3.10.5)} \end{gathered}$$
求得3.10.5的解$Y{Y}^T$就对应（3.10.4）的解（说实话这一块我没看懂，Kmeans直接去做的话还是蛮简单的）