注明：
原理部分的内容均来自周志华的西瓜书，真正的大师之作。
其他内容来自开源包文档、开源电子书、ipynb文档等。

# 半监督聚类 （semi-supervised clustering）

聚类是一种典型的无监督学习任务，然而在现实聚类任务中我们往往能获得一些额外的监督信息，于是可以通过半监督聚类来利用额外监督信息以获得更好的聚类效果。

聚类任务中获得额外监督信息大致有两种类型：

• 样本约束：

  必连 (must-link): 指的是样本必属于同一个簇

  勿连 (cannot-link): 样本必不属于同一个簇

• 样本标签：

  监督信息来自少量带有标签的样本

## 约束$k$均值算法 (pseudo-code)

约束$k$均值算法 (Constrained k-means) 是利用第一类监督信息的代表。给定样本集 $D={x_1, x_2, \ldots, x_m}$ 以及 “必连” 关系集合 $\cal{M}$ 和 “勿连” 关系集合 $\cal{C}$ ，$(x_i, x_j) \in \cal{M}$ 表示 $x_i, x_j$ 必属于同簇，$(x_i, x_j) \in \cal{C}$ 表示 $x_i, x_j$ 必不属于同簇。该算法是 $k$-means 算法的扩展，它在聚类过程中要确保样本的约束得到满足，否则返回错误提示，算法如下：

输入： 样本集 $D = {x_1, x_2, \ldots, x_m}$;

​ 必连约束集合 $\cal{M}$ ;

​ 勿连约束集合 $\cal{C}$ ;