Approximate normalized cuts without Eigen-decomposition

doi:10.1016/j.ins.2016.09.032

	Approximate normalized cuts without Eigen-decomposition
	Jia, Hongjie 1,2; Ding, Shifei 1,2; Du, Mingjing 1,2; Xue, Yu 3
	2016-12-20
发表期刊	INFORMATION SCIENCES
ISSN	0020-0255
卷号	374 页码:135-150
摘要	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.
关键词	Normalized cut Matrix trace Weighted kernel k-means Approximate kernel matrix
DOI	10.1016/j.ins.2016.09.032
收录类别	SCI
语种	英语
资助项目	National Natural Science Foundation of China[61379101] ; National Natural Science Foundation of China[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)
WOS研究方向	Computer Science
WOS类目	Computer Science, Information Systems
WOS记录号	WOS:000386645800009
出版者	ELSEVIER SCIENCE INC
引用统计	被引频次：34[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/7989
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Ding, Shifei
作者单位	1.China Univ Min & Technol, Sch Comp Sci & Technol, Xuzhou 221116, Peoples R China 2.Chinese Acad Sci, Inst Comp Technol, Key Lab Intelligent Informat Proc, Beijing 100190, Peoples R China 3.Nanjing Univ Informat Sci & Technol, Sch Comp & Software, Nanjing 210044, Jiangsu, Peoples R China
推荐引用方式 GB/T 7714	Jia, Hongjie,Ding, Shifei,Du, Mingjing,et al. Approximate normalized cuts without Eigen-decomposition[J]. INFORMATION SCIENCES,2016,374:135-150.
APA	Jia, Hongjie,Ding, Shifei,Du, Mingjing,&Xue, Yu.(2016).Approximate normalized cuts without Eigen-decomposition.INFORMATION SCIENCES,374,135-150.
MLA	Jia, Hongjie,et al."Approximate normalized cuts without Eigen-decomposition".INFORMATION SCIENCES 374(2016):135-150.