Automatic fuzzy-DBSCAN algorithm for morphological and overlapping datasets

doi:10.23919/JSEE.2020.000095

Journal of Systems Engineering and Electronics ›› 2020, Vol. 31 ›› Issue (6): 1245-1253.doi: 10.23919/JSEE.2020.000095

• SYSTEMS ENGINEERING • Previous Articles Next Articles

Automatic fuzzy-DBSCAN algorithm for morphological and overlapping datasets

Aref YELGHI^1,*(), Cemal KÖSE²(), Asef YELGHI³(), Amir SHAHKAR⁴()

¹ Department of Computer Engineering, Avrasya University, Trabzon 61250, Turkey
² Department of Computer Engineering, Karadeniz Technical University, Trabzon 61080, Turkey
³ Department of Business Administration, Gazi University, Ankara 06560, Turkey
⁴ Civil Engineering Department, Karadeniz Technical University, Trabzon 61080, Turkey

Received:2020-01-28 Online:2020-12-18 Published:2020-12-29
Contact: Aref YELGHI E-mail:aref.yelghi@avrasya.edu.tr;ckose@ktu.edu.tr;asefyelghi@gmail.com;amirshahkartrabzon@gmail.com
About author:|YELGHI Aref was born in 1986. He received his B.S. degree and M.S. degree in computer science from the Azad University Sari branch in 2008 and 2012 respectively. He obtained his Ph.D. degree in computer engineering from Karadeniz Technical University in 2018. His research interests include optimization, neural network and data mining. E-mail: aref.yelghi@avrasya.edu.tr||K?SE Cemal was born in 1964. He is a professor in the Department of Computer Engineering at Karadeniz Technical University. He received his Ph.D. degree from Faculty of Engineering, and Department of Computer Science, University of Bristol, in 1997. His research interests include signal and image processing, pattern recognition, and human computer interaction. E-mail: ckose@ktu.edu.tr||YELGHI Asef was born in 1986. He received his B.S. degree in accounting, M.S. degree in capital markets and stock exchange from University of Marmara of Turkey in 2008 and 2014 respectively. He obtained his Ph.D. degree in bussines administration in University of Gazi of Turkey in 2020. Also since 2014, he has been pursuing his Ph.D. degree in banking at University of Marmara of Turkey. His research interests include exchange rate, bond marketing and data mining. E-mail: asefyelghi@gmail.com||SHAHKAR Amir was born in 1989. He received his B.S. degree in civil engineering in 2011 from Azad University of Tabriz. He received his M.S. degree in transportation engineering from Karadeniz Technical University, Trabzon, Turkey, in 2015. He started his Ph.D. learning in traffic engineering in 2016. Currently, he is a Ph.D. student in the Civil Engineering Department, Karadeniz Technical University, Trabzon. His research interests include analyzing traffic accidents through geographic information system (GIS), traffic simulation by Verkehr in Stadten simulations model (VISSIM), and optimizing traffic lights with adaptive neuro fuzzy inference system (ANFIS)-based metaheuristic algorithms. E-mail: amirshahkartrabzon@gmail.com

Abstract

Abstract:

Clustering is one of the unsupervised learning problems. It is a procedure which partitions data objects into groups. Many algorithms could not overcome the problems of morphology, overlapping and the large number of clusters at the same time. Many scientific communities have used the clustering algorithm from the perspective of density, which is one of the best methods in clustering. This study proposes a density-based spatial clustering of applications with noise (DBSCAN) algorithm based on the selected high-density areas by automatic fuzzy-DBSCAN (AFD) which works with the initialization of two parameters. AFD, by using fuzzy and DBSCAN features, is modeled by the selection of high-density areas and generates two parameters for merging and separating automatically. The two generated parameters provide a state of sub-cluster rules in the Cartesian coordinate system for the dataset. The model overcomes the problems of clustering such as morphology, overlapping, and the number of clusters in a dataset simultaneously. In the experiments, all algorithms are performed on eight data sets with 30 times of running. Three of them are related to overlapping real datasets and the rest are morphologic and synthetic datasets. It is demonstrated that the AFD algorithm outperforms other recently developed clustering algorithms.

Key words: clustering, density-based spatial clustering of applications with noise (DBSCAN), fuzzy, overlapping, data mining

Aref YELGHI, Cemal KÖSE, Asef YELGHI, Amir SHAHKAR. Automatic fuzzy-DBSCAN algorithm for morphological and overlapping datasets[J]. Journal of Systems Engineering and Electronics, 2020, 31(6): 1245-1253.

Figures/Tables 12

Fig 1

Fig 2

Fig 3

Fig 4

Fig 5

Fig 6

Fig 7

Fig 8

Fig 9

Table 1

Table 2

References 36

1	JAIN A K, MURTY M N, FLYNN P J Data clustering: a review. ACM Computing Surveys, 1999, 31 (3): 264- 323. doi: 10.1145/331499.331504
2	XU H X, TIAN Z An optimal spectral clustering approach based on Cauchy-Schwarz divergence. Chinese Journal of Electronics, 2009, 18 (1): 105- 108.
3	TANG W Q, LONG W K, SUN L J, et al Multiple model adaptive control of nonlinear systems based on clustering method and neural network. Systems Engineering and Electronics, 2019, 41 (9): 2100- 2106.
4	ZHANG Y X, GUO W P, KANG K, et al Key radar signal fast recognition method based on clustering and time-series correlation. Systems Engineering and Electronics, 2020, 42 (3): 597- 602.
5	ABDALLA A, AHMED M G S, ZHAO Y, et al Deceptive jamming suppression in multistatic radar based on coherent clustering. Journal of Systems Engineering and Electronics, 2018, 29 (2): 269- 277. doi: 10.21629/JSEE.2018.02.07
6	LI H, LIU X J, LI T, et al A novel density-based clustering algorithm using nearest neighbor graph. Pattern Recognition, 2020, 102, 107206. doi: 10.1016/j.patcog.2020.107206
7	GHALLAB H, FAHMY H, NASR M. Detection outliers on internet of things using big data technology. Egyptian Informatics Journal. DOI: 10.1016/j.eij.2019.12.001.
8	GARG S, KAUR K, BATRA S, et al A multi-stage anomaly detection scheme for augmenting the security in IoT-enabled applications. Future Generation Computer Systems, 2019, 104, 105- 118.
9	SAHA S K, SCHMITT I Non-TI clustering in the context of social networks. Procedia Computer Science, 2020, 170, 1186- 1191. doi: 10.1016/j.procs.2020.03.031
10	XU D, TIAN Y A comprehensive survey of clustering algorithms. Annals of Data Science, 2015, 2, 165- 193. doi: 10.1007/s40745-015-0040-1
11	MACQUEEN J B. Some methods for classification and analysis of multivariate observations. Proc. of the 5th Berkeley Symposium on Mathematical Statistics and Probability, 1967: 281–297.
12	PARK H S, JUN C H A simple and fast algorithm for Kmedoids clustering. Expert Systems with Applications, 2009, 36 (2): 3336- 3341. doi: 10.1016/j.eswa.2008.01.039
13	KAUFMAN L, ROUSSEEUW P J. Partitioning around medoids (program PAM). Finding groups in data: an introduction to cluster analysis. New York: Wiley, 1990.
14	KAUFMAN L, ROUSSEEUW P J. Finding groups in data: an introduction to cluster analysis. New York: Wiley, 1990.
15	ZHANG T, RAMAKRISHNAN R, LIVNY M BIRCH: an efficient data clustering method for very large databases. ACM SIGMOD Record, 1999, 25 (2): 103- 114.
16	GUHA S, RASTOGI R, SHIM K CURE: an efficient clustering algorithm for large databases. Information Systems, 2001, 26 (1): 35- 58. doi: 10.1016/S0306-4379(01)00008-4
17	GUHA S, RASTOGI R, SHIM K Rock: a robust clustering algorithm for categorical attributes. Information Systems, 2000, 25 (5): 345- 366. doi: 10.1016/S0306-4379(00)00022-3
18	KARYPIS G, HAN E H, KUMAR V Chameleon: hierarchical clustering using dynamic modeling. Computer, 1999, 32 (8): 68- 75. doi: 10.1109/2.781637
19	BOUDAILLIER E, HEBRAIL G Interactive interpretation of hierarchical clustering. Intelligent Data Analysis, 1998, 2, 229- 244. doi: 10.3233/IDA-1998-2306
20	RODRIGUES P P, GAMA J, PEDROSO J Hierarchical clustering of time-series data streams. IEEE Trans. on Knowledge and Data Engineering, 2008, 20 (5): 615- 627. doi: 10.1109/TKDE.2007.190727
21	ERTOZ L, STEINBACH M, KUMAR V. Finding clusters of different sizes, shapes, and densities in noisy, high dimensional data. Proc. of the 3rd SIAM International Conference on Data Mining, 2003: 47–58.
22	ESTER M, KRIEGEL H P, SANDER J, et al. A density-based algorithm for discovering clusters in large spatial databases with noise. Proc. of the 2nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 1996: 226 – 231.
23	ANKERST M, BREUNIG M M, KRIEGEL H P, et al OPTICS: ordering points to identify the clustering structure. ACM SIGMOD Record, 1999, 28 (2): 49- 60. doi: 10.1145/304181.304187
24	BIRANT D, KUT A ST-DBSCAN: an algorithm for clustering spatial-temporal data. Data & Knowledge Engineering, 2007, 60 (1): 208- 221.
25	FAHIM A M, SAAKE G, SALEM A B M, et al. An enhanced density based spatial clustering of applications with noise. Proc. of the International Conference on Data Mining, 2009: 517–523.
26	RASMUSSEN C E The infinite Gaussian mixture model. Advances in Neural Information Processing Systems, 2000, 12, 554- 560.
27	GUNGOR E, OZMEN A Distance and density based clustering algorithm using Gaussian kernel. Expert Systems with Applications, 2017, 69, 10- 20. doi: 10.1016/j.eswa.2016.10.022
28	VISWANATH P, BABU V Rough-DBSCAN: a fast hybrid density based clustering method for large data sets. Pattern Recognition Letters, 2009, 30 (16): 1477- 1488. doi: 10.1016/j.patrec.2009.08.008
29	BEZDEK J C, EHRLICH R, FULL W FCM: The fuzzy c-means clustering algorithm. Computers & Geosciences, 1984, 10 (2/3): 191- 203.
30	NASIBOV E N, ULUTAGAY G Robustness of densitybased clustering methods with various neighborhood relations. Fuzzy Sets and Systems, 2009, 160 (24): 3601- 3615. doi: 10.1016/j.fss.2009.06.012
31	HIMMELSPACH L, CONRAD S. Density-based clustering using fuzzy proximity relations. Proc. of the Annual Meeting of the North American Fuzzy Information Processing Society, 2011. DOI: 10.1109/NAFIPS.2011.5751999.
32	CHEN W Y, SONG Y Q, BAI H J, et al Parallel spectral clustering in distributed systems. IEEE Trans. on Pattern Analysis and Machine Intelligence, 2011, 33 (3): 568- 586. doi: 10.1109/TPAMI.2010.88
33	BREUNIG M M, KRIEGEL H P, NG R T, et al LOF: identifying density-based local outliers. ACM SIGMOD Record, 2020, 29 (2): 93- 104.
34	ARBELAITZ O, GURRUTXAGA I, MUGUERZA J, et al An extensive comparative study of cluster validity indices. Pattern Recognition, 2013, 46 (1): 243- 256. doi: 10.1016/j.patcog.2012.07.021
35	ZHAO Q, XU M, FRAONTI P. Epanding external validity measures for determining the number of clusters. Proc. of the 11th International Conference on Intelligent Systems Design and Applications, 2011: 931–936.
36	POWERS D M W Evaluation: from precision, recall and f-measure to ROC, informedness, markedness & correlation. Journal of Machine Learning Technologies, 2011, 2 (1): 37- 63.

Name	Index	Wine	Glass	Iris	Cluster in cluster	Corner separate	Four separate cluster	Two separate cluster	Two spiral
	RandIndx	9.28E-01	7.96E-01	9.42E-01	1	1	1	1	1
ADF	AdjRandIndx	8.39E-01	4.87E-01	8.68E-01	1	1	1	1	1
	F-measure	9.48E-01	4.66E-01	9.53E-01	1	1	1	1	1
	RandIndx	5.81E-01	6.55E-01	8.64E-01	1	1	5.87E-01	1	1
DBSCAN	AdjRandIndx	2.43E-01	3.03E-01	7.16E-01	1	1	3.36E-01	1	1
	F-measure	4.47E-01	5.70E-01	6.72E-01	1	1	2.58E-01	1	1
	RandIndx	8.69E-01	7.97E-01	8.80E-01	5.00E-01	1	1	1	5.34E-01
Fuzzy means	AdjRandIndx	7.09E-01	4.49E-01	7.29E-01	–9.15E-04	1	1	1	6.73E-02
	F-measure	8.85E-01	4.70E-01	8.93E-01	5.04E-01	1	1	1	6.30E-01
	RandIndx	9.42E-01	7.65E-01	8.74E-01	5.00E-01	8.31E-01	8.84E-01	1	5.26E-01
K-means	AdjRandIndx	8.69E-01	3.37E-01	7.16E-01	–5.28E-04	8.25E-01	7.22E-01	1	5.24E-02
	F-measure	0.954 9	4.50E-01	8.85E-01	5.10E-01	7.47E-01	7.16E-01	1	6.06E-01

Name	Wine	Glass	Iris	Cluster in cluster	Corner separate	Four separate cluster	Two separate cluster	Two spiral
AFD	Eps1 = 0.19	Eps1 = 0.60	Eps1 = 0.60	Eps1 = 0.7	Eps1 = 0.8	Eps1 = 0.7	Eps1 = 0.2	Eps1 = 0.7
AFD	MinPoint = 4	MinPoint = 3	MinPoint = 3	MinPoint = 10	MinPoint = 31	MinPoint = 10	MinPoint = 5	MinPoint = 10
DBSCAN	MinPoint = 4,	MinPoint = 5,	MinPoint = 5,	MinPoint = 1,	MinPoint = 4,	MinPoint = 4,	MinPoint = 3,	MinPoint = 3,
DBSCAN	Eps = 0.5	Eps = 0.5,	Eps = 0.895 0	Eps = 0.001	Eps = 0.895 0	Eps = 0.9	Eps = 0.5	Eps = 0.5
Fuzzy means	M = 2, Cluster	M = 2, Cluster	M = 2, Cluster	M = 2, Cluster	M = 2, Cluster	M = 2, Cluster	M = 2, Cluster	M = 2, Cluster
	number = 3,	number = 6,	number = 3,	number = 2,	number = 4,	number = 4,	number = 2,	number = 2,
	M = 3, Cluster	M = 3, Cluster	M = 3, Cluster	M = 3, Cluster	M = 3, Cluster	M = 3, Cluster	M = 3, Cluster	M = 3, Cluster
	number = 3,	number = 6,	number = 3,	number = 2,	number = 4,	number = 4,	number = 2,	number = 2,
	M = 4, Cluster	M = 4, Cluster	M = 4, Cluster	M = 4, Cluster	M = 4, Cluster	M = 4, Cluster	M = 4, Cluster	M = 4, Cluster
	number = 3	number = 6	number = 3	number = 2	number = 4	number = 4	number = 2	number = 2
K-means	Cluster	Cluster	Cluster	Cluster	Cluster	Cluster	Cluster	Cluster
	number = 3	number = 6	number = 3	number = 2	number = 4	number = 4	number = 2	number = 2

[1]	Jun CHEN, Xudong GAO, Jia RONG, Xiaoguang GAO. A situation awareness assessment method based on fuzzy cognitive maps [J]. Journal of Systems Engineering and Electronics, 2022, 33(5): 1108-1122.
[2]	Hao FENG, Jianzhong WU, Lu ZHANG, Mingsheng LIAO. Unsupervised change detection of man-made objects using coherent and incoherent features of multi-temporal SAR images [J]. Journal of Systems Engineering and Electronics, 2022, 33(4): 896-906.
[3]	Qi HAN, Weimin LI, Qiling XU, Minrui ZHAO, Runze HUO, Tao ZHANG. Lanchester equation for cognitive domain using hesitant fuzzy linguistic terms sets [J]. Journal of Systems Engineering and Electronics, 2022, 33(3): 674-682.
[4]	Jinfeng LYU, Fucai LIU, Yaxue REN. Fuzzy identification of nonlinear dynamic system based on selection of important input variables [J]. Journal of Systems Engineering and Electronics, 2022, 33(3): 737-747.
[5]	Zhuoqian LI, Yajie DOU, Boyuan XIA, Kewei YANG, Mengjun LI. System portfolio selection based on GRA method under hesitant fuzzy environment [J]. Journal of Systems Engineering and Electronics, 2022, 33(1): 120-133.
[6]	Sader MALIKA, Fuyong WANG, Zhongxin LIU, Zengqiang CHEN. Distributed fuzzy fault-tolerant consensus of leader-follower multi-agent systems with mismatched uncertainties [J]. Journal of Systems Engineering and Electronics, 2021, 32(5): 1031-1040.
[7]	Zhongxiang CHANG, Zhongbao ZHOU, Feng YAO, Xiaolu LIU. Observation scheduling problem for AEOS with a comprehensive task clustering [J]. Journal of Systems Engineering and Electronics, 2021, 32(2): 347-364.
[8]	Xuhao GUI, Junfeng ZHANG, Zihan PENG. Trajectory clustering for arrival aircraft via new trajectory representation [J]. Journal of Systems Engineering and Electronics, 2021, 32(2): 473-486.
[9]	Pengcheng GUO, Zheng LIU, Jingjing WANG. Radar group target recognition based on HRRPs and weighted mean shift clustering [J]. Journal of Systems Engineering and Electronics, 2020, 31(6): 1152-1159.
[10]	Qinghua XING, Jiale GAO. A super-network equilibrium optimization method for operation architecture with fuzzy demands [J]. Journal of Systems Engineering and Electronics, 2020, 31(5): 969-982.
[11]	Hongwei WANG, Penglong FENG. Fuzzy modeling of multirate sampled nonlinear systems based on multi-model method [J]. Journal of Systems Engineering and Electronics, 2020, 31(4): 761-769.
[12]	Fang YE, Ping BAI, Yuan TIAN. An algorithm based on evidence theory and fuzzy entropy to defend against SSDF [J]. Journal of Systems Engineering and Electronics, 2020, 31(2): 243-251.
[13]	Wen JIANG, Xiongjun FU, Jiayun CHANG. Improved de-interleaving algorithm of radar pulses based on dual fuzzy vigilance ART [J]. Journal of Systems Engineering and Electronics, 2020, 31(2): 303-311.
[14]	Qinzi XIAO, Miyuan SHAN, Mingyun GAO, Xinping XIAO. Grey information coverage interaction relational decision making and its application [J]. Journal of Systems Engineering and Electronics, 2020, 31(2): 359-369.
[15]	Gaofeng WU, Kaifang WAN, Xiaoguang GAO, Xiaowei FU. Placement of unmanned aerial vehicles as communication relays in two-tiered multi-agent system: clustering based methods [J]. Journal of Systems Engineering and Electronics, 2020, 31(2): 231-242.

Automatic fuzzy-DBSCAN algorithm for morphological and overlapping datasets

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 12

References 36

Related Articles 15

Recommended Articles

Metrics

Comments