Constrained Kmeans详细讲解

算法简介

Kmeans原本是用于无标签数据集，但一种很实际的情况是，数据集有少量是有标签的，忽略这些标签会造成聚类结果的退化，而标签的数量又比较少。这时候，我们可以用一种半监督聚类的方式来做，比如说Constrained Kmeans。

算法流程

假定数据集为X（n*m，n为样本数，m为feature数），X又分为X-label（简记L）和X-unlabel（简记U）。根据L我们可以定义储存Must-link信息的矩阵（Con=）和储存Cannot-link信息的矩阵（Con~=）。定义方法显而易见：在n*n矩阵（Con=）中，Label信息一样的点对应元素值为1，其他为0；在n*n矩阵（Con~=）中，Label信息不一样的点对应元素值为1，其他为0。完成此定义后，我们只需在寻常的Kmeans算法中加入一条判定机制，具体的算法如下：

• 初始化 k 个簇，随机选择 k 个样本作为 k 个簇的初始均值向量
• 不断迭代以下几步步骤

1. 对每个样本 x ，计算其与每个簇均值向量的距离 d，
   找出距离样本 x 最近的簇 i ，判断将 x 放进 i 是否违反“约束”
2. 如果不违反，则将簇 i 作为 x 的簇标记，并将 x 放入该簇集合$C_i$中；如果违反，则找次近的簇，以此类推直到找到满足约束的最近簇 i’，将x 放入该簇集合 $C_{i’}$中
3. 对所有的簇集合，根据本次迭代得到的簇集合计算新的均值向量
   当均值向量均未更新时，退出迭代步骤

• 最终，我们获得了聚类计算的结果簇划分

下面是算法的伪代码，图来自于周志华的《机器学习》

约束举例

假设训练集X={1,2,3,4,5}，对应的标签Y={A,B,A,未知,未知}，那么构造的Must-link矩阵如下:
$\begin{vmatrix} 1 &0 &1 & 0 & 0\\ 0&1 & 0 & 0 & 0\\ 1 & 0 &1 & 0 &0 \\ 0 & 0 & 0 & 1 &0 \\ 0 & 0 & 0 &0 & 1 \end{vmatrix}$

构造的Cannot-link矩阵如下:
$\begin{vmatrix} 0&1 &0& 0 & 0\\ 1&0 & 1 & 0 & 0\\ 0& 1&0 & 0 &0 \\ 0 & 0 & 0 & 0 &0 \\ 0 & 0 & 0 &0 & 0 \end{vmatrix}$

是不是很清楚了呀，关注微信公众号“算法岗从零到无穷”，更多算法知识点告诉你