-
于是可以通过半监督聚类来利用监督信息以获取更好的聚类效果。
聚类任务中获得的监督信息大致有两种类型:
第一类是必连与勿连约束:
- 必连:指样本必属于同一个簇。
- 勿连:指样本必不属于同一个簇。
- 第二类是:少量的有标记样本。
约束 均值算法 是利用第一类监督信息的代表。
给定样本集 , 以及必连关系集合 和勿连关系集合 ,则:
- , 表示 与 必属于同簇。
- , 表示 与 必不属于同簇。
约束 均值算法是 均值算法的扩展,它在聚类过程中要确保 与 中的约束得以满足,否则将返回错误提示。
约束 均值算法:
输入:
- 必连关系集合
- 聚类簇数
输出:聚类簇划分
算法步骤:
迭代:
初始化每个簇 :
对每个样本 , 执行下列操作:
初始化可选的簇的集合为
计算 与各均值向量的距离
找出 且 最小的 ,设此时 ,即 最小,则考察将 划入簇 是否会违背 与 中的约束:
若不违背,则 划入簇 :
若违背,则从 中移除 , 继续找出 且 最小的 。
重复上述考察,直到 或者 划入簇 不会违背 与 中的约束。
- 若更新均值向量前后,均值向量变化很小,则迭代结束。
- 根据最新的均值向量划分 , 获得聚类簇划分 。
5.2 约束种子 k 均值算法
给定样本集 。 假定少量的有标记样本为 , 为隶属于第 个聚簇的样本。
直接将 中的样本作为种子,用它们初始化 均值算法的 个聚类中心,并且在聚类簇迭代更新过程中不改变种子样本的簇隶属关系,这样就得到了约束种子 均值算法。
约束种子 均值算法:
输入:
- 少量有标记样本
- 聚类簇数
输出:聚类簇划分
算法步骤:
- 利用有标记样本集合 初始化均值向量:
迭代:
- 初始化每个簇:
- 将有标记样本集合 中的每个样本 分别添加到对应的簇中 。
- 对未标记样本集合 中的每个样本 ,将它划分为距离该样本最近的簇中。其中的距离是样本和簇均值向量的距离。
- 更新簇均值向量:
- 若更新均值向量前后,均值向量变化很小,则迭代结束。
- 根据最新的均值向量划分 , 获得聚类簇划分 。