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

doi:10.1016/j.ins.2018.01.013

CORC > 计算技术研究所 > 中国科学院计算技术研究所 > 中国科学院计算技术研究所期刊论文 > 英文

	RECOME: A new density-based clustering algorithm using relative KNN kernel density
	Geng, Yangli-ao 6; Li, Qingyong 6; Zheng, Rong 5; Zhuang, Fuzhen 3,4; He, Ruisi 2; Xiong, Naixue 1
刊名	INFORMATION SCIENCES
	2018-04-01
卷号	436 页码:13-30
关键词	Density-based clustering Density estimation K nearest neighbors Graph theory
ISSN号	0020-0255
DOI	10.1016/j.ins.2018.01.013
英文摘要	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.
资助项目	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
语种	英语
出版者	ELSEVIER SCIENCE INC
WOS记录号	WOS:000427311400002
内容类型	期刊论文
源URL	[http://119.78.100.204/handle/2XEOYT63/5707]
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Li, Qingyong
作者单位	1.Northeastern State Univ, Dept Math & Comp Sci, Tahlequah, OK USA 2.Beijing Jiaotong Univ, State Key Lab Rail Traff Control & Safety, Beijing, Peoples R China 3.Univ Chinese Acad Sci, Beijing 100049, Peoples R China 4.Chinese Acad Sci, Key Lab Intelligen Informat Proc, ICT, Beijing 100190, Peoples R China 5.McMaster Univ, Dept Comp & Software, Hamilton, ON, Canada 6.Beijing Jiaotong Univ, Sch Comp & Informat Technol, Beijing, Peoples R China
推荐引用方式 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.