By generalizing batch edge-removal clustering algorithm, the clustering problem can be separated into the deterministic problem of edge-remove and the construction problem of adjacent graph. Firstly, in this paper, an edge-removal criterion is proposed according to the shifting under the local Gaussian smoothing of data objects. Secondly, the properties of adjacent graph suitable for clustering are studied, and a random kNN (RkNN) graph is suggested by introducing the random factor into the kNN graph. A proof is given to show that RkNN graph can lead to the enhancement of the local connectivity of graph and less dependency between clustering results and the removal of certain edges. The RkNNClus is simple and efficient without specifying the number of clusters. The experiments on synthetic datasets and real datasets demonstrate the effectiveness of the method.