基于安全性的成对约束扩充算法

作者：杨帆; 王俊斌; 白亮^*

来源：计算机科学, 2020, 47(09): 324-329.

• 成对约束
• 半监督聚类
• 监督信息的有效性
• 监督信息的扩展

基于成对约束的聚类分析是半监督学习的一个重要研究方向。成对约束的数量已成为影响该类算法有效性的重要因素。然而,在现实应用中,成对约束的获取需要耗费大量的成本。因此,文中提出了一种基于安全性的成对约束扩充方法(Extended Algorithm of Pairwise Constraints Based on Security,PCES)。该算法将传递闭包中最大局部连通距离作为安全值,并根据安全值来修改传递闭包之间的相似性,减少合并传递闭包带来的风险,最后利用图聚类方法合并相似的传递闭包达到扩充成对约束的目的。该算法不仅可以安全有效地扩充成对约束,同时可以将扩充后的成对约束应用到不同半监督聚类算法中。文中在8个基准数据集上进行了成对约束扩充算法的比较。实验结果表明,该算法可以安全有效地扩充成对约束。