Clustering plays a vital role in computational intelligence and machine learning. Fuzzy C-Means (FCM) has emerged as one of the most well-known iterative optimization clustering methods. In most cases, the FCM model is based on spherical clusters. Kernel method shows great power when modeling highly nonlinear data by projecting input data into a higher dimensional space. Thus the kernel-based fuzzy c-means (KFCM) algorithm has been proposed and verified that it yields better performance than traditional FCM algorithm. In order to avoid incurring huge cost in feature space, we suggest to apply an elegant technique called random Fourier features for approximating kernel methods. In our research, a novel clustering scheme consists of random feature maps, certain feature selection methods and linear clustering algorithms was proposed. The original data is first mapped into a high-dimensional feature space yielded by random Fourier features. Since the dimensionality of random feature space is often quite large, we employ some feature selection methods to refine the feature space. Then a linear learning algorithm will be performed on the random feature space or the refined one. From experiment results, we conclude that after applying the random feature method on original data sets, outcomes of most proposed schemes are superior to results of single baseline algorithms. The clustering performance has been enhanced highly.