As a popular clustering method, spectral clustering has wide applications in various fields including machine learning and pattern recognition. However, in processing large datasets, it requires to build a very large pairwise similarity matrix, which can be very time-consuming. The Nyström method is well known for its ability to approximate the feature space with a small number of samples (landmarks), thereby reducing the computation overhead significantly. Motivated by this observation, in this paper we improve spectral clustering by approximating the similarity matrix and eigenvectors based on the Nyström method. First, we propose a sampling method to select landmarks, which are used in the Nyström method in generating the approximate similarity matrix and eigenvectors. By careful utilization of k-means++ method and cosine similarity, our method improves the quality of landmarks. Second, we use incomplete Cholesky decomposition in accelerating the approximation method, and therefore improve the efficiency of the whole algorithm. We use both real and synthetic datasets in experiments to show that our algorithm is effective in comparison with some other approaches.