must-link 与 cannot link 约束介绍

爱被打了一巴掌 2022-12-29 04:34 190阅读 0赞

在看一些论文时，经常会看到关于must-link 与 cannot link 约束的一些相关工作介绍，特别是在聚类这个领域。

## 维基百科介绍： ##

A must-link constraint is used to specify that the two instances in the must-link relation should be associated with the same cluster. A cannot-link constraint is used to specify that the two instances in the cannot-link relation should not be associated with the same cluster.

## must-link constraints: ##

必连约束， 是指样本必属于同一个簇。 如果2个样本**满足必连约束**，那么在聚类时这2个样本**应该被分到同一个簇中**。

## cannot-link constraints: ##

勿连约束，是指样本不必属于同一个簇。 如果2个样本**满足勿连约束**，那么在聚类时这2个样本**不应该**被分到同一个簇中。

这2个约束一般作为成对约束来作为指导信息，在度量学习或者半监督聚类工作中比较常用。

## **矩阵分解** ##

矩阵分解工作中也会出现这2个约束，如下图这个（在使用流行正则项时）：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDYzMTc1_size_16_color_FFFFFF_t_70]  
约束矩阵中的值对于**不相似的对象是正**的，而对于**相似的对象是负**的。 前者被称为勿连约束，因为它们对矩阵因子的当前近似施加惩罚，后者是必链约束，这是在优化过程中减少目标方程loss。

对于must-link约束，即一对同类型对象应该在潜在表示空间更加接近。 例如，满足必链约束的一个例子，药物-药物相互作用，而勿连约束的例子这里指不同类型对象在潜在表示空间更加远才好。 通常，具有必须链接约束的数据源更丰富。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDYzMTc1_size_16_color_FFFFFF_t_70]: /images/20221120/76433ed3b9374c5bbd6066339f081468.png