Skip to main content
Erschienen in: Soft Computing 5/2018

15.11.2016 | Methodologies and Application

Fuzzy extensions of the DBScan clustering algorithm

verfasst von: Dino Ienco, Gloria Bordogna

Erschienen in: Soft Computing | Ausgabe 5/2018

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The DBSCAN algorithm is a well-known density-based clustering approach particularly useful in spatial data mining for its ability to find objects’ groups with heterogeneous shapes and homogeneous local density distributions in the feature space. Furthermore, it can be suitable as scaling down approach to deal with big data for its ability to remove noise. Nevertheless, it suffers for some limitations, mainly the inability to identify clusters with variable density distributions and partially overlapping borders, which is often a characteristics of both scientific data and real-world data. To this end, in this work, we propose three fuzzy extensions of the \(\textit{DBSCAN}\) algorithm to generate clusters with distinct fuzzy density characteristics. The original version of \(\textit{DBSCAN}\) requires two precise parameters (minPts and \(\epsilon \)) to define locally dense areas which serve as seeds of the clusters. Nevertheless, precise values of both parameters may be not appropriate in all regions of the dataset. In the proposed extensions of \(\textit{DBSCAN}\), we define soft constraints to model approximate values of the input parameters. The first extension, named \(\textit{Fuzzy Core DBSCAN}\), relaxes the constraint on the neighbourhood’s density to generate clusters with fuzzy core points, i.e. cores with distinct density; the second extension, named \(\textit{Fuzzy Border DBSCAN}\), relaxes \(\epsilon \) to allow the generation of clusters with overlapping borders. Finally, the third extension, named \(\textit{Fuzzy DBSCAN}\) subsumes the previous ones, thus allowing to generate clusters with both fuzzy cores and fuzzy overlapping borders. Our proposals are compared w.r.t. state of the art fuzzy clustering methods over real-world datasets.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Literatur
Zurück zum Zitat Bezdek JC, Ehrlich R, Full W (1984) FCM: the fuzzy c-means clustering algorithm. Comput Geosci 10(2):191–203CrossRef Bezdek JC, Ehrlich R, Full W (1984) FCM: the fuzzy c-means clustering algorithm. Comput Geosci 10(2):191–203CrossRef
Zurück zum Zitat Bordogna, G., Ienco, D.: Fuzzy core dbscan clustering algorithm. In: IPMU, pp. 100–109 (2014) Bordogna, G., Ienco, D.: Fuzzy core dbscan clustering algorithm. In: IPMU, pp. 100–109 (2014)
Zurück zum Zitat Ester M, Kriegel H, Sander J, Xu X (1996) A density-based algorithm for discovering clusters in large spatial databases with noise. KDD 160:226–231 Ester M, Kriegel H, Sander J, Xu X (1996) A density-based algorithm for discovering clusters in large spatial databases with noise. KDD 160:226–231
Zurück zum Zitat Guillén A, González J, Rojas I, Pomares H, Herrera LJ, Valenzuela O, Prieto A (2007) Using fuzzy logic to improve a clustering technique for function approximation. Neurocomputing 70(16–18):2853–2860CrossRef Guillén A, González J, Rojas I, Pomares H, Herrera LJ, Valenzuela O, Prieto A (2007) Using fuzzy logic to improve a clustering technique for function approximation. Neurocomputing 70(16–18):2853–2860CrossRef
Zurück zum Zitat Ji Z, Xia Y, Sun Q, Cao G (2014) Interval-valued possibilistic fuzzy c-means clustering algorithm. Fuzzy Sets Syst 253:138–156MathSciNetCrossRef Ji Z, Xia Y, Sun Q, Cao G (2014) Interval-valued possibilistic fuzzy c-means clustering algorithm. Fuzzy Sets Syst 253:138–156MathSciNetCrossRef
Zurück zum Zitat Kriegel H, Pfeifle M (2005) Density-based clustering of uncertain data. In: KDD’05 vol 17, pp 672–677 Kriegel H, Pfeifle M (2005) Density-based clustering of uncertain data. In: KDD’05 vol 17, pp 672–677
Zurück zum Zitat Nasibov EN, Ulutagay G (2009) Robustness of density-based clustering methods with various neighborhood relations. Fuzzy Sets Syst 160(24):3601–3615MathSciNetCrossRefMATH Nasibov EN, Ulutagay G (2009) Robustness of density-based clustering methods with various neighborhood relations. Fuzzy Sets Syst 160(24):3601–3615MathSciNetCrossRefMATH
Zurück zum Zitat Pal NR, Pal K, Keller JM, Bezdek JC (2005) A possibilistic fuzzy c-means clustering algorithm. IEEE Trans Fuzzy Syst 13(4):517–530CrossRef Pal NR, Pal K, Keller JM, Bezdek JC (2005) A possibilistic fuzzy c-means clustering algorithm. IEEE Trans Fuzzy Syst 13(4):517–530CrossRef
Zurück zum Zitat Parker J, Downs J (2013) Footprint generation using fuzzy-neighborhood clustering. Geoinformatica 17:283–299 Parker J, Downs J (2013) Footprint generation using fuzzy-neighborhood clustering. Geoinformatica 17:283–299
Zurück zum Zitat Parker J, Hall L, Kandel A (2010) Scalable fuzzy neighborhood dbscan. In: IEEE-fuzzy, pp 1–8 Parker J, Hall L, Kandel A (2010) Scalable fuzzy neighborhood dbscan. In: IEEE-fuzzy, pp 1–8
Zurück zum Zitat Sander J, Ester M, Kriegel H, Xu X (1998) Density-based clustering in spatial databases: the algorithm GDBSCAN and its applications. Data Min Knowl Discov 2(2):169–194CrossRef Sander J, Ester M, Kriegel H, Xu X (1998) Density-based clustering in spatial databases: the algorithm GDBSCAN and its applications. Data Min Knowl Discov 2(2):169–194CrossRef
Zurück zum Zitat Shamshirband S, Amini A, Anuar NB, Kiah LM, Wah TY, Furnell S (2014) D-ficca: a density-based fuzzy imperialist competitive clustering algorithm for intrusion detection in wireless sensor networks. Measurement 55:212–226CrossRef Shamshirband S, Amini A, Anuar NB, Kiah LM, Wah TY, Furnell S (2014) D-ficca: a density-based fuzzy imperialist competitive clustering algorithm for intrusion detection in wireless sensor networks. Measurement 55:212–226CrossRef
Zurück zum Zitat Smiti A, Eloudi Z (2013) Soft dbscan: improving dbscan clustering method using fuzzy set theory. Hum Syst Interact 1:380–385 Smiti A, Eloudi Z (2013) Soft dbscan: improving dbscan clustering method using fuzzy set theory. Hum Syst Interact 1:380–385
Zurück zum Zitat Ulutagaya G, Nasibov E (2012) Fuzzy and crisp clustering methods based on the neighborhood concept: a comprehensive review. J Intell Fuzzy Syst 23:1–11 Ulutagaya G, Nasibov E (2012) Fuzzy and crisp clustering methods based on the neighborhood concept: a comprehensive review. J Intell Fuzzy Syst 23:1–11
Zurück zum Zitat Yager R, Filev D (1994) Approximate clustering via the mountain method. IEEE Trans Syst Man Cybern 24(8):1279–1284CrossRef Yager R, Filev D (1994) Approximate clustering via the mountain method. IEEE Trans Syst Man Cybern 24(8):1279–1284CrossRef
Metadaten
Titel
Fuzzy extensions of the DBScan clustering algorithm
verfasst von
Dino Ienco
Gloria Bordogna
Publikationsdatum
15.11.2016
Verlag
Springer Berlin Heidelberg
Erschienen in
Soft Computing / Ausgabe 5/2018
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI
https://doi.org/10.1007/s00500-016-2435-0

Weitere Artikel der Ausgabe 5/2018

Soft Computing 5/2018 Zur Ausgabe