在数据挖掘和机器学习的基于距离的各种技术中,例如基于距离的聚类和基于距离的分类,如何度量数据间的相似性已经成为了一项基础任务。对于某一具体问题,采用合适的相似性度量,会使问题得到更有效的解决。越来越多的研究表明,通过对成对约束(正约束和负约束)的充分利用,从而得到与问题相匹配的相似性度量,能够大幅度的提升算法性能。目前基于约束的相似性度量研究主要是基于约束的距离度量学习,通过对约束信息的利用,学习一个距离度量矩阵,然后再进行分类或者聚类。本文通过对成对约束尤其是负约束的挖掘,提出种新的基于约束的相似性度量,主要创新和研究工作总结如下(1)通过对最近邻准则和支持向量机的分析,从中提取出中垂面的概念；从负约束对中挖掘出中垂面,提出一种基于约束的中垂面相似度准则,并在人工数据集上对如何计算相似度做了示例。(2)将基于约束的中垂面相似度准则应用于聚类任务中,提出基于约束的中垂面相似度聚类算法MPHS (Mid-Perpendicular Hyperplane Similarity)。分别在数据集线性可分和数据集线性不可分两种情况下进行聚类,提出多个具体算法。在多个UCI标准数据集和多个图像数据集上的实验表明,MPHS算法与所对比的算法在性能上有很大的提升。(3)通过在半监督聚类学习中引入集成学习的思想,提出了基于约束的中垂面相似度聚类集成算法。算法通过对约束的集成,有效的提高了在多个UCI标准数据集和多个图像数据集上的聚类性能。(4)将基于约束的中垂面相似度准则应用于分类任务中,提出了基于约束的中垂面相似度分类算法。在得到相似性矩阵后,分别应用最近邻算法和支持向量机进行分类,得到相应的分类算法mphs-1nn和mphs-svm。同时将集成学习的思想考虑到分类任务中,得到对应的集成学习算法mphs-Inn-bagging和mphs-svm-bagging。在多个UCI标准数据集上的实验结果验证了所提算法的有效性。