Non-rigid point set registration of significantly uneven deformations is a challenging problem for many applications such as pose estimation, three-dimensional object reconstruction, human movement tracking. In this dissertation, we present a novel probabilistic non-rigid registration method to align point sets with significantly uneven deformations by enforcing constraints from corresponding key points and preserving local neighborhood structures. The registration method is treated as a density estimation problem. Incorporating correspondence among key points regulates the optimization process for large, uneven deformations. In addition, by leveraging neighborhood embedding using Stochastic Neighbor Embedding (SNE) as well as an alternative means based on Locally Linear Embedding (LLE), our method penalizes the incoherent transformation and hence preserves the local structure of point sets. Also, our method detects key points in the point sets based on geodesic distance. Correspondences are established using a new cluster-based, region-aware feature descriptor. This feature descriptor encodes the association of a cluster to the left-right (symmetry) or upper-lower regions of the point sets. We conducted comparison studies using public point sets and our Human point sets. Our experimental results demonstrate that our proposed method successfully reduced the registration error by at least 42.2% in contrast to the state-of-the-art method. Especially, our method demonstrated much superior performance in the case of a large degree of deformations. Experimental results show more than 30% improvements when key point correspondence is used. Our study shows that the influence of the global constraint (key point correspondences) is greater than that of the local constraint. Our analysis of using incorrect key point correspondence reveals the sensitivity of the proposed method. Given erroneous but symmetric correspondence, our method was able to produce fairly good results. In addition, our study on time reports a competitive computational efficiency of the proposed method.