SA-DBSCAN:A self-adaptive density-based clustering algorithm

doi:10.7523/j.issn.2095-6134.2009.4.015

Abstract

Abstract:

DBSCAN is a classic density-based clustering algorithm. It can automatically determine the number of clusters and treat clusters of arbitrary shapes. In the clustering process of DBSCAN, two parameters, Eps and minPts,have to be specified by uses. In this paper an adaptive algorithm named SA-DBSCAN was introduced to determine the two parameters automatically via analysis of the statistical characteristics of the dataset, which enabled clustering process of DBSCAN fully automated. Experimental results indicate that SA-DBSCAN can select appropriate parameters and gain a rather high validity of clustering.

Key words: data mining, clustering, DBSCAN, SA-DBSCAN

CLC Number:

TP181

XIA Lu-Ning, JING Ji-Wu. SA-DBSCAN:A self-adaptive density-based clustering algorithm[J]. , 2009, 26(4): 530-538.

References

[1] MacQueen J. Some methods for classification and analysis of multivariate observations //LeCam L, Neyman J, eds. Proceedings of the Fifth Berkeley Symposium on Mathematics, Statistics and Probability. Berkeley: University of California Press, 1967:281-297.

[2] Leonard Kaufman, Peter J Rousseeuw. Finding groups in data: An introduction to cluster analysis
[M]. New York: Wiley Press, 2005.

[3] Tan P N, Steinbach M, Kumar V著, 范明,范宏建,等译. 数据挖掘导论(Introduction to Data Mining).北京: 人民邮电出版社, 2006.

[4] Ester M, Kriegel H P,Sander J. A density-based algorithm for discovering clusters in large spatial databases with noise //Simoudis E, Han JW, Fayyad UM, eds. Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining. Portland: AAAI Press, 1996:226-231.

[5] Ankerst M,Breunig M M, Kriegel H P. OPTICS: ordering points to identify the clustering structure //Alex Delis, Christos Faloutsos,Shahram Ghandeharizadeh eds. Proceedings of the ACM SIGMOD'99 Int Conf on Management of Data. Philadelphia Pennsylvania: ACM Press, 1999: 49-60.

[6] Hinneburg A,Keim D A. An efficient approach to clustering in large multimedia databases with noise //Rakesh Agrawal,Paul Stolorz,eds. Proceedings of the 4^th Int Conf on Knowledge Discovery and Data Mining. New York: AAAI Press, 1998: 58-65.

[7] Feng P J,Ge L D. Adaptive DBSCAN-based algorithm for constellation reconstruction and modulation identification //Keyun Tang, Dayong Liu,eds. Proceedings of Radio Science Conference 2004. Beijing: Pub House of Electronics Industry, 2004: 177-180.

[8] Halkidi M, Vazirgiannis M. Clustering validity assessment: finding the optimal partitioning of a data set //Nick Cercone, Tsau Young Lin,Xindong Wu eds. Proceedings of the 2001 IEEE International Conference on Data Mining. California: IEEE Computer Society, 2001: 187-194.

[9] Yue S H, Li P,Guo J D, et al. A statistical information-based clustering approach in distance space
[J]. Journal of Zhejiang University Science, 2005, 6A(1): 71-78.

[10] Xu X, Ester M,Kriegel H P, et al. A distribution-based clustering algorithm for mining in large spatial databases //Philip S Yu,eds. Proceedings of the 14th international conference on data engineering (ICDE'98). Orlando: IEEE Computer Society Press, 1998: 324-331.

[11] Lin C Y, Chang C C, Lin C C. A new density-based scheme for clustering based on genetic algorithm
[J]. Fundamenta Informaticae, 2005, 68(4): 315-331.

[12] Cai Y K, Xie K Q, Ma X J. An improved DBSCAN algorithm which is insensitive to input parameters
[J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2004, 40(3): 480-486 (in Chinese). 蔡颖琨, 谢昆青, 马修军. 屏蔽了输入参数敏感性的DBSCAN改进算法
[J]. 北京大学学报:自然科学版, 2004, 40(3): 480-486.

[13] Su Z, Ma S P, Yang Q, et al. Document clustering based on web-log mining
[J]. Journal of Software, 2002, 13(1): 99-104(in Chinese). 苏中, 马少平, 杨强,等. 基于Web-Log Mining的Web文档聚类
[J]. 软件学报, 2002, 13(1): 99-104.

[14] 吴梅村编著. 数理统计学基本原理和方法
[M]. 成都: 西南财经大学出版社, 2006.

[15] Steinbach M, Karypis G, Kumar V. A comparison of document clustering techniques:technical report .Minnesota: University of Minnesota-Computer Science and Engineering, 2000.