期刊
INFORMATION SCIENCES
卷 374, 期 -, 页码 135-150出版社
ELSEVIER SCIENCE INC
DOI: 10.1016/j.ins.2016.09.032
关键词
Normalized cut; Matrix trace; Weighted kernel k-means; Approximate kernel matrix
资金
- National Natural Science Foundation of China [61379101, 61672522]
- National Key Basic Research Program of China [2013CB329502]
- Priority Academic Program Development of Jiangsu Higer Education Institutions(PAPD)
- Jiangsu Collaborative Innovation Center on Atmospheric Environment and Equipment Technology(CICAEET)
Most traditional weighted graph clustering algorithms are solved by spectral method, which is only suitable for small scale datasets because of the high space and time complexity. How to reduce the computational complexity of graph cut clustering to process the massive complex data has become a challenging problem. To overcome this problem, we design an approximate normalized cuts algorithm without eigen-decomposition for large scale clustering. On the one hand, the space requirement of normalized cut is decreased by sampling a few data points to infer the global features of dataset instead of using the whole affinity matrix; on the other hand, the graph cut clustering procedure is accelerated in an iterative way that using the approximate weighted kernel k-means to optimize the objective function of normalized cut, which avoids the direct eigen-decomposition of Laplacian matrix. We also analyze the approximation error of the proposed algorithm and compare it with other state-of-the-arts clustering algorithms on several benchmark datasets. The experimental results demonstrate that our method can efficiently do the clustering when the number of data objects exceeds tens of thousands. (C) 2016 Elsevier Inc. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据