Please wait a minute...
Big Data Mining and Analytics  2019, Vol. 2 Issue (3): 195-204    DOI: 10.26599/BDMA.2019.9020003
Efficient Preference Clustering via Random Fourier Features
Jingshu Liu, Li Wang*, Jinglei Liu
Jingshu Liu and Li Wang are with the College of Data Science, Taiyuan University of Technology, Jinzhong 030600, China. E-mail:
Jinglei Liu is with the School of Computer and Control Engineering, Yantai University, Yantai 264005, China. E-mail:
Download: PDF (3012 KB)      HTML  
Export: BibTeX | EndNote (RIS)      


Approximations based on random Fourier features have recently emerged as an efficient and elegant method for designing large-scale machine learning tasks. Unlike approaches using the Nystr?m method, which randomly samples the training examples, we make use of random Fourier features, whose basis functions (i.e., cosine and sine ) are sampled from a distribution independent from the training sample set, to cluster preference data which appears extensively in recommender systems. Firstly, we propose a two-stage preference clustering framework. In this framework, we make use of random Fourier features to map the preference matrix into the feature matrix, soon afterwards, utilize the traditional k-means approach to cluster preference data in the transformed feature space. Compared with traditional preference clustering, our method solves the problem of insufficient memory and greatly improves the efficiency of the operation. Experiments on movie data sets containing 100 000 ratings, show that the proposed method is more effective in clustering accuracy than the Nystr?m and k-means, while also achieving better performance than these clustering approaches.

Key wordsrandom Fourier features      matrix decomposition      similarity matrix     
Received: 13 November 2018      Published: 06 January 2020
Corresponding Authors: Li Wang   
About author:

? Jiangcheng Zhu and Shuang Hu contribute equally to this paper. This work was done when they were visiting researchers in Data Science Institute, Imperial College London, London SW7 2AZ, UK.

Cite this article:

Jingshu Liu, Li Wang, Jinglei Liu. Efficient Preference Clustering via Random Fourier Features. Big Data Mining and Analytics, 2019, 2(3): 195-204.

URL:     OR

Fig. 1 An undirected graph.
Fig. 2 Partition of graph.
Fig. 3 Score of users to movies.
Data set nameTypeNumber of rowsNumber of columns
JokeReal data24 938101
MovielenReal data9431682
EpinionReal data106963 718
ReuterReal data1000672
Table 1 Characteristic of preference datasets.
True resultsPredicted results
Table 2 A confusion matrix.
Fig. 4 Accuracy evaluation on different datasets.
Fig. 5 NMI evaluation on different datasets.
Fig. 6 NMI of different clustering methods by fixed sampling.
Fig. 7 NMI of different clustering methods by sampling percentage.
Data setd×nMethodAccNMI
Joke24 938×101PCA-k-means0.42310.51
Epinion1069×63 718PCA-k-means0.34560.62
Table 3 Performance comparison on different preference clustering methods.
[1]   Arias-Castro E., Lerman G., and Zhang T., Spectral clusteringbased on local PCA, Journal of Machine Learning Research, vol. 18, no. 1, pp. 253-309, 2017.
[2]   Yang Y., Shen F., Huang Z., Shen H. T., and Li X., Discrete nonnegative spectral clustering, IEEE Transactions on Knowledge and Data Engineering, vol. 29, no. 9, pp. 1834-1845, 2017.
[3]   Wang L., Bezdek J. C., Leckie C., and Kotagiri R., Selective sampling for approximate clustering of very large data sets, International Journal of Intelligent Systems, vol. 23, no. 3, pp. 313-331, 2008.
[4]   Xu R. and Ii D. C. W., Survey of clustering algorithms, IEEE Transactions on Neural Networks, vol. 16, no. 3, pp. 645-678, 2005.
[5]   Sun S., Zhao J., and Zhu J., A review of nystrom methods for large-scale machine learning, Information Fusion, vol. 26, no. 1, pp. 36-48, 2015.
[6]   Langone R., Mall R., Alzate C., and Suykens J. A. K., Kernel spectral clustering and applications, in Unsupervised Learning Algorithms. 2016, pp. 135-161.
[7]   Zhang X., Zong L., You Q., and Yong X., Sampling for nystrom extension-based spectral clustering: Incremental perspective and novel analysis, ACM Transactions on Knowledge Discovery from Data, vol. 11, no. 1, pp. 7: 1-7: 25, 2016.
[8]   Fowlkes B. C., Belongie S., Chung F., and Malik J., Spectral grouping using the nystroquotom method, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, no. 2, pp. 214-225, 2010.
[9]   Sun Y., Gao J., Hong X., Mishra B., and Yin B., Heterogeneous tensor decomposition for clustering via manifold optimization, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 38, no. 3, pp. 476-489, 2016.
[10]   Wang S. and Zhang Z., Efficient algorithms and error analysis for the modified nystrom method, in Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics, Reykjavik, Iceland, 2014, pp. 996-1004.
[11]   Wang W. and Zhang Z., Improving CUR matrix decomposition and the Nystrom approximation via adaptive sampling, Journal of Machine Learning Research, vol. 14, no. 1, pp. 2729-2769, 2013.
[12]   Chen X. and Cai D., Large scale spectral clustering with landmark-based representation. in Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence, San Francisco, CA, USA, 2011, pp. 313-318.
[13]   Wang L. and Dong M., Exemplar-based low-rank matrix decomposition for data clustering, Data Mining and Knowledge Discovery, vol. 29, no. 2, pp. 324-357, 2015.
[14]   Wang S., Luo L., and Zhang Z., SPSD matrix approximation via column selection: Theories, algorithms, and extensions, Journal of Machine Learning Research, vol. 17, no. 1, pp. 1697-1745, 2016.
[15]   Wang S., Zhang Z., and Zhang T., Towards more efficient SPSD matrix approximation and CUR matrix decomposition, Journal of Machine Learning Research, vol. 17, no. 1, pp. 7329-7377, 2016.
[16]   Bradley P. S. and Fayyad U. M., Refining initial points for kmeans clustering, in Fifteenth International Conference on Machine Learning, 1998, pp. 91-99.
[17]   Zha H., He X., Ding C., Simon H., and Gu M., Spectral relaxation for k-means clustering, in Proceedings of the 14th International Conference on Neural Information Processing Systems: Natural and Synthetic, Vancouver, Canada, 2001, pp. 1057-1064.
[18]   Wang L., Rege M., Dong M., and Ding Y., Low-rank kernel matrix factorization for large-scale evolutionary clustering, IEEE Transactions on Knowledge and Data Engineering, vol. 24, no. 6, pp. 1036-1050, 2012.
[19]   Bach F. R. and Jordan M. I., Learning spectral clustering, Advances in Neural Information Processing Systems, vol. 16, no. 2, pp. 305-312, 2004.
[20]   Dempster A., Maximum likelihood from incomplete data via the em algorithm, Journal of the Royal Statistical Society, vol. 39, no. 1, pp. 1-38, 1977.
[21]   Spielman D. A., Spectral graph theory and its applications, in Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, Washington, DC, USA, 2007, pp. 29-38.
[22]   Chen W. Y., Song Y., Bai H., Lin C. J., and Chang E. Y., Parallel spectral clustering in distributed systems, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 33, no. 3, pp. 568-586, 2010.
[23]   Alzate C. and Suykens J. A. K., Multiway spectral clustering with out-of-sample extensions through weighted kernel PCA, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 32, no. 2, pp. 335-347, 2010.
[24]   Lauer F. and Schnorr C., Spectral clustering of linear subspaces for motion segmentation, in Proceedings of the IEEE 12th International Conference on Computer Vision, Kyoto, Japan, 2009, pp. 678-685.
[25]   Malik J. and Shi J., Normalized cuts and image segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 22, no. 8, pp. 888-905, 2000.
[26]   Hartigan J. A. and Wong M. A., A k-means clustering algorithm, Applied Statistics, vol. 28, no. 1, pp. 100-108, 1979.
[27]   Alaoui A. E. and Mahoney M. W., Fast randomized kernel ridge regression with statistical guarantees, in Proceedings of the 28th International Conference on Neural Information Processing Systems, Montreal, Canada, 2015, pp. 775-783.
[28]   Vedaldi A. and Zisserman A., Efficient additive kernels via explicit feature maps, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 34, no. 3, pp. 480-492, 2012.
[29]   Rahimi A. and Recht B., Random features for large-scale kernel machines, in Proceedings of the 20th International Conference on Neural Information Processing Systems, Vancouver, Canada, 2007, pp. 1177-1184.
[30]   He L., Ray N., Guan Y., and Zhang H., Fast large-scale spectral clustering via explicit feature mapping, IEEE Transactions on Cybernetics, vol. 49, no. 3, pp. 1058-1071, 2019.
No related articles found!