| Citation: | ZHANG Man, XU Zhaorui, SHEN Xiangjunet al. A high-speed spectral clustering method in Fourier domain for massive data[J]. Journal of Beijing University of Aeronautics and Astronautics, 2022, 48(8): 1445-1454. doi: 10.13700/j.bh.1001-5965.2021.0537(in Chinese)
|
Spectral clustering is widely used in data mining and pattern recognition. However, due to the high computational cost of eigenvector solutions and the huge memory requirements brought by big data, spectral clustering algorithm is greatly limited when it is applied to large-scale data. Therefore, this paper studies a high-speed spectral clustering method for massive data in the Fourier domain. This method makes full use of the repeatability of data pattern, and uses this characteristic to model in the Fourier domain. To get final eigenvectors, the time-consuming eigenvector pursuitcan be transformed into the selection of the pre-determined discriminant basis in the Fourier domain. The calculation process only needs simple multiplication and addition, so the amount of time for calculation is greatly reduced. On the other hand, due to the characteristics of calculation in the Fourier domain, another advantage of this method is that it can train the samples in batches, that is, only using part of the samples can well estimate eigenvector distribution in the whole data. The experimental results on large-scale data such as Ijcnn1, RCV1, Covtype-mult, Poker and MNIST-8M show that the training time of the proposed method is at most 810.58 times faster than that of algorithms FastESC, LSSHC, SC_RB, SSEIGS and USPEC, on the premise that the clustering accuracy and other indicators are basically maintained, which proves that the proposed method has significant advantages in processing large-scale data.
| [1] |
PAN P, YOSHIDA Y. Average sensitivity of spectral clustering[C]//Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. New York: ACM, 2020: 1132-1140.
|
| [2] |
XING L Q. Intelligent multimedia urban planning construction based on spectral clustering algorithms of large data mining[J]. Multimedia Tools and Applications, 2020, 79: 35183-35194. doi: 10.1007/s11042-019-7572-x
|
| [3] |
ALSHAMMARI M, STAVRAKAKIS J, TAKATSUKA M. Refining a k-nearest neighbor graph for a computationally efficient spectral clustering[J]. Pattern Recognition, 2021, 114: 107869. doi: 10.1016/j.patcog.2021.107869
|
| [4] |
谢娟英, 丁丽娟, 王明钊. 基于谱聚类的无监督特征选择算法[J]. 软件学报, 2020, 31(4): 1009-1024. https://www.cnki.com.cn/Article/CJFDTOTAL-RJXB202004009.htm
XIE J Y, DING L J, WANG M Z. Spectral clustering based unsupervised feature selection algorithms[J]. Journal of Software, 2020, 31(4): 1009-1024(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-RJXB202004009.htm
|
| [5] |
朱光辉, 黄圣彬, 袁春风, 等. SCoS: 基于Spark的并行谱聚类算法设计与实现[J]. 计算机学报, 2018, 41(4): 868-885. https://www.cnki.com.cn/Article/CJFDTOTAL-JSJX201804008.htm
ZHU G H, HUANG S B, YUAN C F, et al. SCoS: The design and implementation of parallel spectral clustering algorithm based on Spark[J]. Chinese Journal of Computers, 2018, 41(4): 868-885(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-JSJX201804008.htm
|
| [6] |
李玉, 袁永华, 赵雪梅. 可变类谱聚类遥感影像分割[J]. 电子学报, 2018, 46(12): 3021-3028. doi: 10.3969/j.issn.0372-2112.2018.12.028
LI Y, YUAN Y H, ZHAO X M. Spectral clustering of variable class for remote sensing image segmentation[J]. Acta Electronica Sinica, 2018, 46(12): 3021-3028(in Chinese). doi: 10.3969/j.issn.0372-2112.2018.12.028
|
| [7] |
ARRIETA J M, NAKASATO J C, PEREIRA M C. The p-Laplacian equation in thin domains: The unfolding approach[J]. Journal of Differential Equations, 2021, 274: 1-34. doi: 10.1016/j.jde.2020.12.004
|
| [8] |
FOWLKES C, BELONGIE S, CHUNG F, et al. Spectral grouping using the Nyström method[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26(2): 214-225. doi: 10.1109/TPAMI.2004.1262185
|
| [9] |
DAKULAGI V. A new Nyström approximation based efficient coherent DOA estimator for radar application[J]. AEU-International Journal of Electronics and Communications, 2020, 124: 153328.
|
| [10] |
DU Y, TSANG L. Accurate calculations of emissivities of polar ocean surfaces between 0.5 and 2 GHz using an NTBC/Nyström/SMCG method[J]. IEEE Transactions on Geosciences and Remote Sensing, 2020, 58(4): 2732-2744. doi: 10.1109/TGRS.2019.2954886
|
| [11] |
薛丽霞, 孙伟, 汪荣贵, 等. 基于密度峰值优化的谱聚类算法[J]. 计算机应用研究, 2019, 36(7): 1948-1950. https://www.cnki.com.cn/Article/CJFDTOTAL-JSYJ201907006.htm
XUE L X, SUN W, WANG R G, et al. Spectral clustering based on density peak value optimization[J]. Application Research of Computers, 2019, 36(7): 1948-1950(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-JSYJ201907006.htm
|
| [12] |
BOUNEFFOUF D. Spectral clustering using eigenspectrum shape based Nyström sampling[EB/OL]. (2020-07-21)[2021-09-01]. https://arxiv.org/abs/2007.11416.
|
| [13] |
WU L F, CHEN P Y, YEN I E, et al. Scalable spectral clustering using random binning features[C]//Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. New York: ACM, 2018: 2506-2515.
|
| [14] |
YANG Y, DENG S, LU J, et al. GraphLSHC: Towards large scale spectral hypergraph clustering[J]. Information Sciences, 2021, 544: 117-134. doi: 10.1016/j.ins.2020.07.018
|
| [15] |
HENRIQUES J F, CASEIRO R, MARTINS P, et al. High-speed tracking with kernelized correlation filters[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2015, 37(3): 583-596. doi: 10.1109/TPAMI.2014.2345390
|
| [16] |
HENRIQUES J F, CARREIRA J, CASEIRO R, et al. Beyond hard negative mining: Efficient detector learning via block-circulant decomposition[C]//Proceedings of the IEEE International Conference on Computer Vision. Piscataway: IEEE Press, 2014: 14144978.
|
| [17] |
BODDETI V N, KANADE T, KUMAR B V K V. Correlation filters for object alignment[C]//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. Piscataway: IEEE Press, 2013: 2291-2298.
|
| [18] |
LI H, RAY N, GUAN Y, et al. Fast large-scale spectral clustering via explicit feature mapping[J]. IEEE Transactions on Cybernetics, 2018, 49(3): 1058-1071.
|
| [19] |
RAHMAN M H, BOUGUILA N. Efficient feature mapping in classifying proportional data[J]. IEEE Access, 2020, 9: 3712-3724.
|
| [20] |
VÁZQUEZ-MARTÍN R, BANDERA A. Spatio-temporal feature-based keyframe detection from video shots using spectral clustering[J]. Pattern Recognition Letters, 2013, 34(7): 770-779. doi: 10.1016/j.patrec.2012.12.009
|
| [21] |
万月, 陈秀宏, 何佳佳. 利用稀疏自编码的局部谱聚类映射方法[J]. 传感器与微系统, 2018, 37(1): 145-148. https://www.cnki.com.cn/Article/CJFDTOTAL-CGQJ201801040.htm
WAN Y, CHEN X H, HE J J. Local spectral clustering mapping algorithm using sparse autoencoders[J]. Transducer and Microsystem Technologies, 2018, 37(1): 145-148(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-CGQJ201801040.htm
|
| [22] |
BARNHILL E, HOLLIS L, SACK I, et al. Nonlinear multiscale regularisation in MR elastography: Towards fine feature mapping[J]. Medical Image Analysis, 2017, 35: 133-145. doi: 10.1016/j.media.2016.05.012
|
| [23] |
HANSEN T J, MAHONEY M W. Semi-supervised eigenvectors for large-scale locally-biased learning[J]. The Journal of Machine Learning Research, 2014, 15(1): 3691-3734.
|
| [24] |
HUANG D, WANG C D, WU J S, et al. Ultra-scalable spectral clustering and ensemble clustering[J]. IEEE Transactions on Knowledge and Data Engineering, 2020, 32(6): 1212-1226. doi: 10.1109/TKDE.2019.2903410
|
| [25] |
DONATELLI M, NOVARA P, ROMANI L, et al. A merged tuning of binary and ternary Loop's subdivision[J]. Computer Aided Geometric Design, 2019, 69: 27-44. doi: 10.1016/j.cagd.2018.12.005
|
| [26] |
GODI P K, KRISHNA B T, KOTIPALLI P. Design optimization of multiplier-free parallel pipelined FFT on field programmable gate array[J]. IET Circuits Devices & Systems, 2020, 14(7): 995-1000.
|
| [27] |
GAO S J. Fast incremental spectral clustering in titanate application via graph Fourier transform[J]. IEEE Access, 2020, 8: 57252-57259. doi: 10.1109/ACCESS.2020.2982439
|
| [28] |
BIBI A, ITANI H, GHANEM B. FFTLasso: Large-scale LASSO in the Fourier domain[C]//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. Piscataway: IEEE Press, 2017: 17355224.
|
| [29] |
ANTOGNINI J M, SOHL-DICKSTEIN J. PCA of high dimensional random walks with comparison to neural network training[EB/OL]. (2018-06-22)[2021-09-01]. https://arxiv.org/abs/1806.08805v1.
|
| [30] |
DRINEAS P, KANNAN R, MAHONEY M W. Fast Monte Carlo algorithms for matrices Ⅱ: Computing a low-rank approximation to a matrix[J]. SIAM Journal on Computing, 2006, 36(1): 158-183. doi: 10.1137/S0097539704442696
|
| [31] |
DRINEAS P, KANNAN R. Fast Monte-Carlo algorithms for approximate matrix multiplication[C]//Proceedings on the 42nd IEEE Symposium on Foundations of Computer Science. Piscataway: IEEE Press, 2001: 452-459.
|
| [32] |
LOOSLI G, CANU S, BOTTOU L. Training invariant support vector machines using selective sampling[M]//BOTTOU L, CHAPELLE O, WESTON J. Large scale kernel machines. Cambridge: MIT Press, 2007.
|
Figures(3) / Tables(6)
Copyright © Journal of Beijing University of Aeronautics and Astronautics
Address: Editorial Department of Journal of Beijing University of Aeronautics and Astronautics, 37 Xueyuan Road, Haidian District, Beijing Post Code: 100191 Email: jbuaa@buaa.edu.cn
Supported by:
Beijing Renhe Information Technology Co., Ltd.
DownLoad:
