With the development of web service technology, identifying and discovering the users with similar preferences have an important significance to service selection and service optimization in the service environment. In order to divide the users into groups based on their preference similarity in the process of service selection, a combination-based clustering algorithm, named AAK, is presented in this paper. The method combines the K-means algorithm with the Affinity Propagation (AP) algorithm to cluster the users with similar preferences. In the clustering process, the algorithm makes full use of the advantages of the two algorithms, including the high partition accuracy of K-means algorithm and the independence in the prior knowledge of AP algorithm, which breaks the limitation of using a single clustering algorithm. Then a parallel execution model of the algorithm is built and implemented by a high order MapReduce sequence linking technology. Finally AAK algorithm is compared with its serial model and the other combination-based clustering methods on Matlab platform and Hadoop platform. The experimental results show that AAK algorithm can be applied to distinguish user group with different preferences and has a good effectiveness and efficiency.