论文部分内容阅读
在机器学习和数据挖掘领域中，大量的带标签样本的获取需要付出昂贵的代价，但未标记数据却随手可得。基于此，一种新的学习方式半监督学习产生了，由于半监督学习既可以利用带标签数据进行监督学习又可以利用无标签数据进行无监督学习，所以它成为了数据挖掘领域的研究热点。谱聚类算法是一种高性能计算方法，此算法的聚类空间可以是任意形状的，并且能够收敛于全局最优解。半监督谱聚类算法将监督信息加入到谱聚类中，对聚类效果起到改进的作用，因此该算法具有很高的研究价值。本文主要的研究工作是半监督谱聚类以及在图像分割中的应用，首先基于NSDR（Near Strangers or Distant Relatives）模型提出一种基于NSDR模型的半监督谱聚类算法；然后提出了一种约束扩展方法，并基于该约束扩展方法提出了一种基于约束扩展的半监督谱聚类。通过实验验证，新算法具有可行性并且对聚类的改进效果较明显；最后将新算法应用到了图像分割中。本文的创新点主要表现在以下几个方面：（1）提出一种基于NSDR模型的半监督谱聚类（NSDR-SSC，Semi-supervised SpectralClustering based NSDR, NSDR-SSC）算法。该算法基于NSDR模型，利用数据的空间结构假设以及监督信息指导数据间的相似性估计，并以此来修正相似度矩阵，进而实现监督信息指导谱聚类的效果。（2）提出一种基于约束扩展的半监督谱聚类（CE-SSC，Semi-supervised SpectralClustering based Constraints Expansion）算法。该算法首先通过一种基于密度的约束扩展方法来对有限的成对约束信息进行扩展，然后将较多的监督信息应用在（1）中所述的NSDR-SSC算法中，以达到监督信息更好地指导聚类的效果。（3）将两种半监督谱聚类算法成功应用在了图像分割中。将谱聚类相关算法应用在图像分割中是有一定挑战的，因为谱聚类算法需要求相似度矩阵以及特征值，导致谱聚类在处理大规模数据集时的开销会非常大，并且在图像分割中会随着图像的增大，相似矩阵成幂级数增长，本文使用了Nystr(o|¨)m逼近方法来解决此问题。