Abstract: Measuring the similarity between data objects is one of the primary tasks for distance-based techniques in data mining and machine learning, e.g., distance-based clustering or classification. For a certain problem, using proper similarity measurement will make it easier to be solved. Recently, more and more researches have shown that pairwise constraints can help to obtain a good similarity measurement for certain problem with significantly improved performances. Most existing works on similarity measurement with pairwise constraints are on distance metric learning, which use pairwise constraints to learn a distance matrix for subsequent classification or clustering. In this paper, inspired by the hyperplance used in nearest neighbor and support vector machine classifiers, we propose a new similarity measurement criterion called mid-perpendicular hyperplane similarity (MPHS) which can effectively learn from pairwise constraints, especially cannot-link constraints. Then we apply it for clustering and classification tasks. Finally, we validate the effectiveness of our proposed method by comparing it with several state-of-the-art algorithms through extensive experiments on a number of benchmark datasets.