Data explosion drives data analysis tools to update faster and faster, while clustering plays an indispensable role in knowledge discovery. Whereas, most of the clustering algorithms only effect on those linear separable data. Kernel-based clustering methods perform well on data sets with non-linear inner structure, but at the same time, the requirement of large memory and running time induce poor scalability. The method based on random feature mapping was presented to approximate the kernel function. Former experiments show that after applying linear algorithms in this approximated feature space, the clustering results are comparable to the results of kernel-based algorithms. To further improve the clustering accuracy in high-dimensional randomized feature space, we utilize an improved version of fuzzy c-Means algorithm - weighted entropy fuzzy c-Means algorithm. From the experiment results, we can say that better clustering performance is achieved.