机器学习-周志华-个人练习13.10

13.10 试为图13.7算法第10行写出违约检测算法（用以检测是否有约束未被满足）

根据题意可知，我们的目的是检测将 xi 划入聚类簇 Cr 是否会违背 M与C 中的约束。
在这里不能只简单考虑该样本是否满足与某些约束条件内样本的“必连”和“勿连”条件，而是需要分析到底是待聚类样本违约还是其约束集合中的样本存在违约，同时需要考虑必连样本的传递性。

必连约束违约检测

对于必连样本，考虑如下图1的情况，左右两图中的 r,rm 代表样本 xi 和它的一个必连（相连）样本 xm 对应的两个聚类中心，虚线代表聚类簇边界（即聚类中心垂直平分线），圆的大小代表各点离相应聚类中心的距离，显然，此时有样本违反了必连约束。

首先考虑图（1）和图（3），此时 ∥xi−r∥>∥xm−rm∥ ，按照欧氏距离聚类，我们会觉得 xi,xm 分类都很正确，但由于两样本是必连的，所以肯定有一个的聚类结果是错误的。此时，我们可以将 xi,xm 同时分到 r,rm 簇中，然后比较孰优孰劣，那么距离更相近的样本，聚到一类可能性更高，假设各簇 r,rm 到图中自己的对应样本 xi,xm 的聚类概率均为100%，向外逐渐减小，则显然在圆圈外的样本离圆圈越近，其被聚到这一簇的可能性越高。由此原则可知，对于黑色的一对必连样本，

∥xi−rm∥−∥xm−rm∥>∥xm−r∥−∥xi−r∥,

此时 xm 违反了相连约束， xi 并未违反必连约束，我们是要对 xi 聚类，因此在这种情况下 xi 并未违反必连约束；而当 xm 与 r 的距离比 xi 还小时（甚至出现（3）这种情况），依然是 xm 违反了相连约束。

而对于灰色的一对必连样本，我们按照 ∥xi−rm∥−∥xm−rm∥ 的大小同时扩展黑色的簇边界为灰色的簇边界，显然两条簇边界具有相同的聚类可能性，但由于 xm 落到了灰色大圆外，使得

∥xi−rm∥−∥xm−rm∥≤∥xm−r∥−∥xi−r∥,

此时 xi 违反了相连约束。

对于图（2）和图（4）， ∥xi−r∥≤∥xm−rm∥ ，此时同理可得：当

∥xi−rm∥−∥xm−rm∥>∥xm−r∥−∥xi−r∥,

此时 xm 违反了相连约束。
当

∥xi−rm∥−∥xm−rm∥≤∥xm−r∥−∥xi−r∥,

此时 xi 违反了相连约束。

综上所述可知，对于必连样本，若存在 xm 满足

∥xi−rm∥+∥xi−r∥≤∥xm−rm∥+∥xm−r∥

那么 xi 违反必连约束。

勿连约束违约检测

对于勿连约束条件，我们可考虑如下所示的两种情况，即勿连样本的最近聚类簇中心一致，但我们需要分析是待聚类样本 xi 还是勿连样本 xc 违反了勿连约束。

对于左图，显然 ∥xi−r∥<∥xc−r∥ ，根据上述方法同样的原理可知，若 xc 的最佳聚类簇为 r ，则距离 r 更近的 xi 更应该属于簇 r ，因此出现矛盾，而若 xi 的最佳聚类簇为 r ，则距离 r 更远的 xc 不见得属于簇 r ，因此此时应当是 xc 违反勿连约束。

而对于右图，显然情况相反， ∥xi−r∥>∥xc−r∥ ，与上段同理可知：此时应当是 xi 违反勿连约束。

综上可知，对于勿连样本，若存在 xc 满足

∥xi−r∥>∥xc−r∥

那么 xi 违反勿连约束。

违约检测算法

显然，对于 (x1,x2),(x2,x3)∈M ，满足相连的传递性，因此可先将满足相互连通关系的 {xj}∪xi 记为集合 Xm ，且满足 X1+X2+…Xm=M .

同理，对于 (x1,x2),(x2,x3)∈C ，不满足传递性，因此可直接将含有 xi 的 {xj} 记为 Xc ，满足 X1+X2+…Xc=C .

基于上述对必连约束和勿连约束的检测，可以得到如下的违约检测算法。

01: is_violate=False
02: 找到 xi 所属的连通关系集合 Xm={xm}
03: ifX≠∅:
04: forxm∈Xm :
05: 基于K找到与xm距离最近的簇rm=argminj∈K∥xm−μj∥
06: ifrm≠rand∥xm−μrm∥+∥xm−μr∥≥∥xi−μrm∥+∥xi−μr∥ :
07: is_violate=True
08: break
09: if ¬is_violate:
10: 找到xi 所属的勿连关系集合 Xc={xc}
11: ifX≠∅:
12: for xc∈Xc :
13: 基于K找到与xc距离最近的簇rc=argminj∈K∥xc−μj∥
14: if rm=rand∥xc−μr∥<∥xi−μr∥ :
15: is_violate=True
16: break