期刊
IEEE TRANSACTIONS ON CYBERNETICS
卷 49, 期 3, 页码 1058-1071出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TCYB.2018.2794998
关键词
Kernel matrix; Nystrom approximation; pattern recognition; random Fourier features; spectral clustering
类别
资金
- National Natural Science Foundation of China [61673125, 61703115]
- Leading Talents of Guangdong Province Program
- State International Science and Technology Cooperation Special Items [2015DFA11700]
- Frontier and Key Technology Innovation Special Funds of Guangdong Province [2015B010917003]
We propose an efficient spectral clustering method for large-scale data. The main idea in our method consists of employing random Fourier features to explicitly represent data in kernel space. The complexity of spectral clustering thus is shown lower than existing Nystrom approximations on large-scale data. With in training points from a total of n data points, Nystrom method requires O(nmd + m(3) + nm(2)) operations, where d is the input dimension. In contrast, our proposed method requires O(nDd + D-3 + n'D-2), where n' is the number of data points needed until convergence and D is the kernel mapped dimension. In large-scale datasets where n' << n hold true, our explicitly mapping method can significantly speed up eigenvector approximation and benefit prediction speed in spectral clustering. For instance, on MNIST (60000 data points), the proposed method is similar in clustering accuracy to Nystrom methods while its speed is twice as fast as Nystrom.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据