五、半监督聚类

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

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

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

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

     • 必连：指样本必属于同一个簇。
     • 勿连：指样本必不属于同一个簇。
   • 第二类是：少量的有标记样本。

5.1 约束 k 均值算法

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

2. 给定样本集 ， 以及必连关系集合 和勿连关系集合 ，则：

   • ， 表示 与 必属于同簇。
   • ， 表示 与 必不属于同簇。

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

3. 约束 均值算法：

   • 输入：

     • 
     • 必连关系集合
     • 勿连关系集合
     • 聚类簇数

   • 输出：聚类簇划分

   • 算法步骤：

     • 从 中随机选取 个样本作为初始均值向量

     • 迭代：

       • 初始化每个簇 ：

       • 对每个样本 ， 执行下列操作：

         • 初始化可选的簇的集合为

         • 计算 与各均值向量的距离

         • 找出 且 最小的 ，设此时 ，即 最小，则考察将 划入簇 是否会违背 与 中的约束：

           • 若不违背，则 划入簇 ：

           • 若违背，则从 中移除 ， 继续找出 且 最小的 。

           • 重复上述考察，直到 或者 划入簇 不会违背 与 中的约束。

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

       • 更新均值向量：

       

       • 若更新均值向量前后，均值向量变化很小，则迭代结束。
     • 根据最新的均值向量划分 ， 获得聚类簇划分 。

5.2 约束种子 k 均值算法

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

2. 给定样本集 。 假定少量的有标记样本为 ， 为隶属于第 个聚簇的样本。

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

3. 约束种子 均值算法：

   • 输入：

     • 
     • 少量有标记样本
     • 聚类簇数

   • 输出：聚类簇划分

   • 算法步骤：

     • 利用有标记样本集合 初始化均值向量：

     

     • 迭代：

       • 初始化每个簇：
       • 将有标记样本集合 中的每个样本 分别添加到对应的簇中 。
       • 对未标记样本集合 中的每个样本 ，将它划分为距离该样本最近的簇中。其中的距离是样本和簇均值向量的距离。
       • 更新簇均值向量：

       

       • 若更新均值向量前后，均值向量变化很小，则迭代结束。
     • 根据最新的均值向量划分 ， 获得聚类簇划分 。