在机器学习、模式识别和数据挖掘等领域的研究中，聚类分析是一类极为重要的数据分析方法。聚类分析方法在图像分析、生物信息学、web数据分析、社交网络分析、天文学等诸多领域有着广泛的应用。利用聚类分析方法，人们对来自于这些领域的大规模应用数据有了更深刻的理解，同时聚类分析的结果也是对大规模数据做进一步处理的基础。研究更为有效的数据聚类分析方法具有极为重要的现实意义。但是，应当注意到传统的数据聚类分析本身是一个病态的问题，这主要是因为聚类分析是一类完全无监督的学习方法。为了进一步改进聚类分析的性能，人们希望能够在数据聚类分析中引入一些监督信息来指导聚类过程。数据点之间存在的成对约束关系就是这样的一类监督信息，它包括了两种成对约束关系，分别是必然连接（must-link）关系，用来表示数据集中的两个数据点必然属于同一类别，和必然不连接（cannot-link）关系，用来表示数据集中的两个数据点必然属于不同类别。考虑了成对约束关系的聚类分析被称为是基于成对约束的约束聚类问题。在基于成对约束的约束聚类问题中，通常可获得的数据点之间的成对约束关系是非常有限的。成对约束关系传递问题是指对可获得的初始有限的成对约束关系在数据集上进行传递，通过成对约束传递可获得大量可靠的数据点之间的成对约束信息，利用这样大量的成对约束信息就可以显著地提高约束聚类的性能。由于初始可获得的成对约束关系非常有限，所以成对约束关系传递问题具有半监督学习的结构，可以利用大量的无监督信息的数据帮助完成约束传递任务。人们已经提出了一些解决成对约束关系传递问题的算法，但是现有的算法具有一定的局限性。例如数据点之间存在的成对约束关系具有对称的形式，但是目前的成对约束关系传递算法并没有考虑到这种成对约束关系的对称性；再者，成对约束关系传递过程需要首先计算数据点之间的一个相似图，目前的相似图构造算法中并没有考虑到将成对约束关系作为一种先验信息引入到相似图的构造过程中；此外，已提出的成对约束关系传递算法主要集中在处理单模态数据上，但是在现实世界中存在着大量的多模态数据，如何能够充分利用多模态数据各个模态之间的关系来完成成对约束关系传递任务也是一个非常重要的研究问题。针对现有约束传递算法存在的问题，本论文对成对约束关系传递算法及其在约束聚类中的应用做了深入研究，主要工作和创新点包括以下几个方面：（1）首先从成对约束关系所具有的对称性特征出发，研究具有对称结构的约束传递问题，提出了一个对称图正则的成对约束关系传递算法（symmetric graph regularizedpairwise constraint propagation，SRCP）。在对称图正则框架下，指出了成对约束关系传递等价于求解一个李雅普诺夫矩阵方程。此外，还将成对约束关系传递过程建模为一个动态的对称信息扩散过程，证明了这样的一个对称信息扩散过程具有时间不变的扩散结果，并且指出了时不变的扩散结果同样等价于求解相同的李雅普诺夫矩阵方程。本论文的研究将对称形式的成对约束传递同在控制论研究中被广泛采用的李雅普诺夫矩阵方程联系起来，具有重要的理论价值。实验结果表明对称图正则约束传递算法在约束聚类任务中可以获得很好的聚类性能。（2）建立在半监督学习框架下的成对约束关系传递算法需要首先计算一个定义在数据集上的相似图，用来反映数据点之间的相似程度。本论文提出一种相似度学习算法，提出的算法同时考虑了最小化局部重构误差和最小化局部约束误差，提出的相似度学习问题可以被建模为一个二次优化问题。进一步将学习到的数据相似度用于成对约束关系传递任务，基本思想是使相似度高的两个数据点彼此之间应该具有相同的关于其它数据点的成对约束关系配置。实验结果表明将学习到的数据相似度应用到成对约束关系传递问题可以有效地提高算法的性能。（3）针对多模态数据集上的成对约束传递问题，本论文首先提出了一种基于多图随机行走的多模态成对约束关系传递算法。该算法首先在多模态数据集的每一个数据模态上建立了相似图，然后在每一个模态相似图上定义了随机行走过程，并利用多个图上的随机行走过程将多个相似图连接起来，形成多图结构，进而在多图上利用多图标记传递技术解决了多模态数据集上的成对约束关系传递问题。进一步提出了一种方法可以自动地学习多图组合过程中各个数据模态的权重。多模态的成对约束关系传递问题可以通过求解一个无约束的二次规划问题来计算，并且所提出的模型具有解析解的形式。实验结果表明，提出的多模态成对约束关系传递算法可以有效地利用多个数据模态上的信息，获得比单模态算法要好得多的性能。（4）针对多模态数据约束传递问题，进一步提出了一个模态一致性的框架，并将该框架用于解决多模态成对约束关系传递问题。所提出的模态一致性框架利用了一个模态一致性的正则项将各个数据模态上约束传递结果统一起来，希望各个数据模态上的传递结果能够彼此一致。为了有效地求解模态一致性框架，采用了一种可分离的模态一致性正则项，多模态成对约束传递问题可以通过一种简单的交替优化的方式求解。交替优化过程包括了在每一个数据模态上的独立成对约束传递过程和各个模态之间的一致传递过程。利用所提出的模态一致性框架，两个单模态成对约束传递算法可以直接转化成了两个多模态的成对约束传递解决方案。实验结果表明，采用了模态一致性框架的多模态成对约束传递算法是目前效果最好的多模态算法。