  It has always been a great challenge for clustering algorithms to
automatically determine the cluster numbers according to the distribution of
datasets. Several approaches have been proposed to address this issue,
including the recent promising work which incorporate Bayesian Nonparametrics
into the $k$-means clustering procedure. This approach shows simplicity in
implementation and solidity in theory, while it also provides a feasible way to
inference in large scale datasets. However, several problems remains unsolved
in this pioneering work, including the power-law data applicability, mechanism
to merge centers to avoid the over-fitting problem, clustering order problem,
e.t.c.. To address these issues, the Pitman-Yor Process based k-means (namely
\emph{pyp-means}) is proposed in this paper. Taking advantage of the Pitman-Yor
Process, \emph{pyp-means} treats clusters differently by dynamically and
adaptively changing the threshold to guarantee the generation of power-law
clustering results. Also, one center agglomeration procedure is integrated into
the implementation to be able to merge small but close clusters and then
adaptively determine the cluster number. With more discussion on the clustering
order, the convergence proof, complexity analysis and extension to spectral
clustering, our approach is compared with traditional clustering algorithm and
variational inference methods. The advantages and properties of pyp-means are
validated by experiments on both synthetic datasets and real world datasets.
