K-PRSCAN: A clustering method based on PageRank

Many existing clustering approaches are difficult to cluster non-convex or non-isotropic shapes whose centroids are not highly distinguishable. In addition, most of these approaches are often sensitive to outliers and background noise. To this end, we propose a novel clustering approach called K-PRSCAN, where PageRank algorithm is adopted to estimate the importance of data points in K clusters. The importance exhibits both intra-cluster and inter-cluster relations of a data point, enabling our method to distinguish both globular and non-globular clusters. It can also reduce the negative effect of noisy points whose importance tends to be a small value. The experimental results show that our proposed approach outperforms several well-known clustering approach across seven complex and non-isotropic datasets. We also evaluate the effectiveness of our algorithm on two real-world datasets, i.e. a public dataset of digit handwriting recognition and a dataset for race walking recognition collected by ourselves, and find our approach outperforms other existing algorithms in most aspects.