RECOME: A new density-based clustering algorithm using relative KNN kernel density

doi:10.1016/j.ins.2018.01.013

	RECOME: A new density-based clustering algorithm using relative KNN kernel density
	Geng, Yangli-ao 1; Li, Qingyong 1; Zheng, Rong 2; Zhuang, Fuzhen 3,4; He, Ruisi 5; Xiong, Naixue 6
	2018-04-01
发表期刊	INFORMATION SCIENCES
ISSN	0020-0255
卷号	436 页码:13-30
摘要	Discovering clusters from a dataset with different shapes, densities, and scales is a known challenging problem in data clustering. In this paper, we propose the RElative COre MErge (RECOME) clustering algorithm. The core of RECOME is a novel density measure, i.e., Relative K nearest Neighbor Kernel Density (RNKD). RECOME identifies core objects with unit RNKD, and partitions non-core objects into atom clusters by successively following higher density neighbor relations toward core objects. Core objects and their corresponding atom clusters are then merged through alpha-reachable paths on a KNN graph. We discover that the number of clusters computed by RECOME is a step function of the a parameter with jump discontinuity on a small collection of values. A fast jump discontinuity discovery (FJDD) method is proposed based on graph theory. RECOME is evaluated on both synthetic datasets and real datasets. Experimental results indicate that RECOME is able to discover clusters with different shapes, densities, and scales. It outperforms six baseline methods on both synthetic datasets and real datasets. Moreover, FJDD is shown to be effective to extract the jump discontinuity set of parameter a for all tested datasets, which can ease the task of data exploration and parameter tuning. (C) 2018 Elsevier Inc. All rights reserved.
关键词	Density-based clustering Density estimation K nearest neighbors Graph theory
DOI	10.1016/j.ins.2018.01.013
收录类别	SCI
语种	英语
资助项目	National Natural Science Foundation of China[61725101] ; National Natural Science Foundation of China[61773361] ; National Natural Science Foundation of China[61771037] ; Beijing Natural Science Foundation[J160004] ; Shanghai Research Program[17511102900] ; National Science and Engineering Council, Canada
WOS研究方向	Computer Science
WOS类目	Computer Science, Information Systems
WOS记录号	WOS:000427311400002
出版者	ELSEVIER SCIENCE INC
引用统计	被引频次：48[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/5708
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Li, Qingyong
作者单位	1.Beijing Jiaotong Univ, Sch Comp & Informat Technol, Beijing, Peoples R China 2.McMaster Univ, Dept Comp & Software, Hamilton, ON, Canada 3.Chinese Acad Sci, Key Lab Intelligen Informat Proc, ICT, Beijing 100190, Peoples R China 4.Univ Chinese Acad Sci, Beijing 100049, Peoples R China 5.Beijing Jiaotong Univ, State Key Lab Rail Traff Control & Safety, Beijing, Peoples R China 6.Northeastern State Univ, Dept Math & Comp Sci, Tahlequah, OK USA
推荐引用方式 GB/T 7714	Geng, Yangli-ao,Li, Qingyong,Zheng, Rong,et al. RECOME: A new density-based clustering algorithm using relative KNN kernel density[J]. INFORMATION SCIENCES,2018,436:13-30.
APA	Geng, Yangli-ao,Li, Qingyong,Zheng, Rong,Zhuang, Fuzhen,He, Ruisi,&Xiong, Naixue.(2018).RECOME: A new density-based clustering algorithm using relative KNN kernel density.INFORMATION SCIENCES,436,13-30.
MLA	Geng, Yangli-ao,et al."RECOME: A new density-based clustering algorithm using relative KNN kernel density".INFORMATION SCIENCES 436(2018):13-30.