基于图的半监督聚类是较为典型的半监督学习方法,通常以无符号图表征数据,以非负权重衡量节点间相似性。真实复杂系统中,无符号图难以区分无关和对立关系,而符号图中负边则可将对立关系显式表达,为聚类提供更多有效信息,近来在一些领域,如图像分割,取得了良好的效果。本文关注基于符号图规范化割(Signed Normalized cut,SNcut)的半监督聚类离散优化及其在图像分割上的应用,现有研究成果较少,且存在明显不足。在图像分割问题上,仅考虑了划线交互形式,对于其它更弱的监督形式,如何构建符号图尚无解决方案。在模型优化方面,主要采用谱方法,需在实域空间中求解离散的聚类问题,所得结果较为粗糙,且当图的规模较大时,计算复杂度明显增加。尽管有研究使用其它方法对个别SNcut目标的一阶近似函数进行离散优化求解,但其效果尚未得到进一步验证。本文以图像分割为实验对象,讨论了符号图的构建与SNcut聚类目标的离散优化方法,主要工作包括:(1)利用高斯混合模型构造符号图,将符号图聚类应用于box形式下的图像分割。box监督信息难以直接表达为成对约束,采用高斯混合模型将其转换为成对约束,构造符号图,利用谱方法优化。实验结果表明,符号图中负边的引入提升了聚类效果,符号图聚类性能优于无符号图。(2)为多种SNcut构建了一阶上界函数,采用核割求解并应用于box形式下的图像分割。引入了加强分割目标边界对齐性的马尔科夫随机场(Markov Random Fields,MRF)正则化子,使用界优化与图割组合的核割方法离散优化求解。实验结果表明,符号图中负边的引入提升了聚类效果,符号图聚类性能优于无符号图。(3)为一大类图聚类目标构建了二阶近似函数,局部次模优化后纳入信赖域搜索框架优化求解,并应用于box形式下的图像分割。针对一阶近似可能丢失成对信息的问题,为一大类图聚类目标构建了二阶近似函数。将非次模的MRF正则化的二阶近似函数局部次模优化,再纳入信赖域搜索框架并采用图割算法求解。实验结果表明,信赖域优化结果优于核割,且符号图中负边的引入提升了聚类效果,符号图聚类性能优于无符号图。