The hesitant fuzzy set (HFS) is very significant in dealing with the multi-criteria decision-making problems when the decision makers have hesitancy in providing their assessments. However, with the deepening of the research, it may lose information in its applications. Hence, the probabilistic hesitant fuzzy set (P-HFS) has been proposed to improve the HFS, associating the probability with the HFS and remaining more information than the HFS. Considering the correlation coefficient is one of the most important tools in data analysis, we propose two new correlation coefficient formulas to measure the relationship between the P-HFSs, based on which, a new probabilistic hesitant fuzzy clustering algorithm is also developed. To do so, we define the mean of the probabilistic hesitant fuzzy element and the P-HFS, respectively. Furthermore, a practical case study is conducted to demonstrate practicability and validity of the proposed clustering algorithm.