Question

1. 聚类是一种典型的无监督学习任务，然而在现实聚类任务中，往往能够获取一些额外的监督信息。

   于是可以通过半监督聚类semi-supervised clustering来利用监督信息以获取更好的聚类效果。

2. 聚类任务中获得的监督信息大致有两种类型：

   • 第一类是必连must-link与勿连cannot-link约束：

     • 必连：指样本必属于同一个簇。
     • 勿连：指样本必不属于同一个簇。

   • 第二类是：少量的有标记样本。

5.1 约束 k 均值算法

1. 约束 $ MathJax-Element-537 $ 均值算法Constrained-k-means 是利用第一类监督信息的代表。

2. 给定样本集 $ MathJax-Element-538 $ ， 以及必连关系集合 $ MathJax-Element-523 $ 和勿连关系集合 $ MathJax-Element-524 $ ，则：

   • $ MathJax-Element-479 $ ， 表示 $ MathJax-Element-548 $ 与 $ MathJax-Element-484 $ 必属于同簇。
   • $ MathJax-Element-482 $ ， 表示 $ MathJax-Element-548 $ 与 $ MathJax-Element-484 $ 必不属于同簇。

   约束 $ MathJax-Element-537 $ 均值算法是 $ MathJax-Element-537 $ 均值算法的扩展，它在聚类过程中要确保 $ MathJax-Element-523 $ 与 $ MathJax-Element-524 $ 中的约束得以满足，否则将返回错误提示。

3. 约束 $ MathJax-Element-537 $ 均值算法：

   • 输入：

     • $ MathJax-Element-538 $
     • 必连关系集合 $ MathJax-Element-523 $
     • 勿连关系集合 $ MathJax-Element-524 $
     • 聚类簇数 $ MathJax-Element-540 $

   • 输出：聚类簇划分 $ MathJax-Element-550 $

   • 算法步骤：

     • 从 $ MathJax-Element-549 $ 中随机选取 $ MathJax-Element-540 $ 个样本作为初始均值向量 $ MathJax-Element-497 $

     • 迭代：

       • 初始化每个簇 ： $ MathJax-Element-543 $

       • 对每个样本 $ MathJax-Element-499 $ ， 执行下列操作：

         • 初始化可选的簇的集合为 $ MathJax-Element-500 $

         • 计算 $ MathJax-Element-548 $ 与各均值向量的距离 $ MathJax-Element-502 $

         • 找出 $ MathJax-Element-517 $ 且 $ MathJax-Element-518 $ 最小的 $ MathJax-Element-537 $ ，设此时 $ MathJax-Element-506 $ ，即 $ MathJax-Element-507 $ 最小，则考察将 $ MathJax-Element-548 $ 划入簇 $ MathJax-Element-522 $ 是否会违背 $ MathJax-Element-523 $ 与 $ MathJax-Element-524 $ 中的约束：

           • 若不违背，则 $ MathJax-Element-548 $ 划入簇 $ MathJax-Element-522 $ ： $ MathJax-Element-514 $

           • 若违背，则从 $ MathJax-Element-515 $ 中移除 $ MathJax-Element-516 $ ， 继续找出 $ MathJax-Element-517 $ 且 $ MathJax-Element-518 $ 最小的 $ MathJax-Element-537 $ 。

           • 重复上述考察，直到 $ MathJax-Element-525 $ 或者 $ MathJax-Element-548 $ 划入簇 $ MathJax-Element-522 $ 不会违背 $ MathJax-Element-523 $ 与 $ MathJax-Element-524 $ 中的约束。

             如果 $ MathJax-Element-525 $ ，则返回错误提示。这意味着 $ MathJax-Element-548 $ 与所有的簇都发生冲突。

       • 更新均值向量：

       $ \vec\mu_k=\frac{1}{|\mathbb C_k|}\sum_{\mathbf{\vec x}_j\in \mathbb C_k}\mathbf{\vec x}_j,\quad k=1,2,\cdots,K $
       • 若更新均值向量前后，均值向量变化很小，则迭代结束。

     • 根据最新的均值向量划分 $ MathJax-Element-549 $ ， 获得聚类簇划分 $ MathJax-Element-550 $ 。

5.2 约束种子 k 均值算法

1. 约束种子 k 均值Constrained Seed k-means算法是利用第二类监督的代表。

2. 给定样本集 $ MathJax-Element-538 $ 。 假定少量的有标记样本为 $ MathJax-Element-539 $ ， $ MathJax-Element-531 $ 为隶属于第 $ MathJax-Element-537 $ 个聚簇的样本。

   直接将 $ MathJax-Element-544 $ 中的样本作为种子，用它们初始化 $ MathJax-Element-540 $ 均值算法的 $ MathJax-Element-540 $ 个聚类中心，并且在聚类簇迭代更新过程中不改变种子样本的簇隶属关系，这样就得到了约束种子 $ MathJax-Element-537 $ 均值算法。

3. 约束种子 $ MathJax-Element-537 $ 均值算法：

   • 输入：
     

     • $ MathJax-Element-538 $
     • 少量有标记样本 $ MathJax-Element-539 $
     • 聚类簇数 $ MathJax-Element-540 $

   • 输出：聚类簇划分 $ MathJax-Element-550 $

   • 算法步骤：

     • 利用有标记样本集合 $ MathJax-Element-544 $ 初始化均值向量：
     $ \vec\mu_k=\frac {1}{|\mathbb S_k|}\sum_{\mathbf{\vec x}_i \in \mathbb S_k}\mathbf{\vec x}_i,\quad k=1,2,\cdots,K $

     • 迭代：

       • 初始化每个簇： $ MathJax-Element-543 $
       • 将有标记样本集合 $ MathJax-Element-544 $ 中的每个样本 $ MathJax-Element-548 $ 分别添加到对应的簇中 $ MathJax-Element-546 $ 。
       • 对未标记样本集合 $ MathJax-Element-547 $ 中的每个样本 $ MathJax-Element-548 $ ，将它划分为距离该样本最近的簇中。其中的距离是样本和簇均值向量的距离。
       • 更新簇均值向量：
       $ \vec\mu_k=\frac {1}{|\mathbb C_k|}\sum_{\mathbf{\vec x}_j \in \mathbb C_k}\mathbf{\vec x}_j,\quad k=1,2,\cdots,K $
       • 若更新均值向量前后，均值向量变化很小，则迭代结束。

     • 根据最新的均值向量划分 $ MathJax-Element-549 $ ， 获得聚类簇划分 $ MathJax-Element-550 $ 。