Rough-DBSCAN: A fast hybrid density based clustering method for large data sets

被引:187
作者
Viswanath, P. [2 ]
Babu, V. Suresh [1 ]
机构
[1] Univ Bedfordshire, Inst Res Applicable Comp, Dept Comp & Informat Syst, Luton LU1 3JU, Beds, England
[2] NRI Inst Technol, Pattern Recognit Res Lab, Dept Comp Sci & Engn, Guntur 522009, Andhra Pradesh, India
关键词
Clustering; Density based clustering; DBSCAN; Leaders; Rough sets;
D O I
10.1016/j.patrec.2009.08.008
中图分类号
TP18 [人工智能理论];
学科分类号
140502 [人工智能];
摘要
Density based clustering techniques like DBSCAN are attractive because it can find arbitrary shaped clusters along with noisy outliers. Its time requirement is O(n(2)) where n is the size of the dataset, and because of this it is not a suitable one to work with large datasets. A solution proposed in the paper is to apply the leaders clustering method first to derive the prototypes called leaders from the dataset which along with prototypes preserves the density information also, then to use these leaders to derive the density based clusters. The proposed hybrid clustering technique called rough-DBSCAN has a time complexity of O(n) only and is analyzed using rough set theory. Experimental studies are done using both synthetic and real world datasets to compare rough-DBSCAN with DBSCAN. It is shown that for large datasets rough-DBSCAN can find a similar clustering as found by the DBSCAN, but is consistently faster than DBSCAN. Also some properties of the leaders as prototypes are formally established. (C) 2009 Elsevier B.V. All rights reserved.
引用
收藏
页码:1477 / 1488
页数:12
相关论文
共 28 条
[1]
Tree structure for efficient data mining using rough sets [J].
Ananthanarayana, VS ;
Murty, MN ;
Subramanian, DK .
PATTERN RECOGNITION LETTERS, 2003, 24 (06) :851-862
[2]
A rough fuzzy approach to web usage categorization [J].
Asharaf, S ;
Murty, MN .
FUZZY SETS AND SYSTEMS, 2004, 148 (01) :119-129
[3]
An adaptive rough fuzzy single pass algorithm for clustering large data sets [J].
Asharaf, S ;
Murty, MN .
PATTERN RECOGNITION, 2003, 36 (12) :3015-3018
[4]
MULTIDIMENSIONAL BINARY SEARCH TREES USED FOR ASSOCIATIVE SEARCHING [J].
BENTLEY, JL .
COMMUNICATIONS OF THE ACM, 1975, 18 (09) :509-517
[5]
Cheu E.Y., 2004, INT C ARTIFICIAL INT, P138
[6]
Duda R.O., 1973, Pattern Classification and Scene Analysis
[7]
Ester M., 1996, P 2 INT C KNOWL DISC, V96, P226, DOI DOI 10.5555/3001460
[8]
A survey of kernel and spectral methods for clustering [J].
Filippone, Maurizio ;
Camastra, Francesco ;
Masulli, Francesco ;
Rovetta, Stefano .
PATTERN RECOGNITION, 2008, 41 (01) :176-190
[9]
Guha S., 1998, SIGMOD Record, V27, P73, DOI 10.1145/276305.276312
[10]
GUTTMAN A, 1984, 13 ACM SIGMOD INT C, V2, P47