Top

Neural Processing Letters

Published in:

30-11-2017

Density Based Cluster Growing via Dominant Sets

Authors: Jian Hou, Xu E, Weixue Liu

Published in: Neural Processing Letters | Issue 2/2018

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Although there are a lot of clustering algorithms available in the literature, existing algorithms are usually afflicted by practical problems of one form or another, including parameter dependence and the inability to generate clusters of arbitrary shapes. In this paper we aim to solve these two problems by merging the merits of dominant sets and density based clustering algorithms. We firstly apply histogram equalization to eliminate the parameter dependence problem of the dominant sets algorithm. Noticing that the obtained clusters are usually smaller than the real ones, a density threshold based cluster growing step is then used to improve the clustering results, where the involved parameters are determined based on the initial clusters. This is followed by the second cluster growing step which makes use of the density relationship between neighboring data. Data clustering experiments and comparison with other algorithms validate the effectiveness of the proposed algorithm.

previous article Soft-Constrained Neural Networks for Nonparametric Density Estimation

next article A New Conjugate Gradient Method with Smoothing Regularization Based on a Modified Secant Equation for Training Neural Networks

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

Achtert E, Bohm C, Kroger P (2006) Deli-clu: boosting robustness, completeness, usability, and efficiency of hierarchical clustering by a closest pair ranking. In: International conference on knowledge discovery and data mining, pp 119–128CrossRef

Ankerst M, Breunig MM, Kriegel HP, Sander J (1999) Optics: ordering points to identify the clustering structure. In: ACM SIGMOD international conference on management of data, pp 49–60

Brendan JF, Delbert D (2007) Clustering by passing messages between data points. Science 315:972–976MathSciNetCrossRef

Bulo SR, Pelillo M, Bomze IM (2011) Graph-based quadratic optimization: a fast evolutionary approach. Comput Vis Image Underst 115(7):984–995CrossRef

Chang H, Yeung DY (2008) Robust path-based spectral clustering. Pattern Recognit 41(1):191–203CrossRef

Cheng Y (1995) Mean shift, mode seeking, and clustering. IEEE Trans Pattern Anal Mach Intell 17(8):790–799CrossRef

Comaniciu D, Peter M (2002) Mean shift: a robust approach toward feature space analysis. IEEE Trans Pattern Anal Mach Intell 24(5):603–619CrossRef

Daszykowski M, Walczak B, Massart DL (2001) Looking for natural patterns in data: part 1. Density-based approach. Chemometr Intell Lab Syst 56(2):83–92CrossRef

Ding J, Chen Z, He X, Zhan Y (2016) Clustering by finding density peaks based on Chebyshev’s inequality. In: Chinese control conference, pp 7169–7172

10.

Ester M, Kriegel HP, Sander J, Xu XW (1996) A density-based algorithm for discovering clusters in large spatial databases with noise. In: International conference on knowledge discovery and data mining, pp 226–231

11.

Evanno G, Regnaut S, Goudet J (2005) Detecting the number of clusters of individuals using the software structure: a simulation study. Mol Ecol 14(8):2611–2620CrossRef

12.

Fraley C, Raftery AE (1998) How many clusters? which clustering method? Answers via model-based cluster analysis. Comput J 41(8):578–588CrossRef

13.

Fränti P, Virmajoki O, Hautamäki V (2006) Fast agglomerative clustering using a k-nearest neighbor graph. IEEE Trans Pattern Anal Mach Intell 28(11):1875–1881CrossRef

14.

Fu L, Medico E (2007) Flame, a novel fuzzy clustering method for the analysis of DNA microarray data. BMC Bioinformatics 8(1):1–17CrossRef

15.

Gionis A, Mannila H, Tsaparas P (2007) Clustering aggregation. ACM Trans Knowl Discov Data 1(1):1–30CrossRef

16.

Hinnerberg A, Keim D (1998) An efficient approach to clustering large multimedia databases with noise. In: International conference on knowledge discovery and data mining pp 58–65

17.

Hou J, Gao H, Li X (2016) DSets-DBSCAN: a parameter-free clustering algorithm. IEEE Trans Image Process 25(7):3182–3193MathSciNetCrossRef

18.

Hou J, Gao H, Xia Q, Qi N (2016) Feature combination and the knn framework in object classification. IEEE Trans Neural Netw Learn Syst 27(6):1368–1378CrossRef

19.

Hou J, Liu W, Xu E (2016) Density based clustering via dominant sets. In: IAPR-TC3 workshop on artificial neural networks in pattern recognition, pp 80–91CrossRef

20.

Hou J, Liu W, Xu E, Cui H (2016) Towards parameter-independent data clustering and image segmentation. Pattern Recogn 60:25–36CrossRef

21.

Hou J, Pelillo M (2013) A simple feature combination method based on dominant sets. Pattern Recogn 46(11):3129–3139CrossRef

22.

Jain AK, Law MHC (2005) Data clustering: a user’s dilemma. In: International conference on pattern recognition and machine intelligence, pp 1–10

23.

Kärkkäinen I, Fränti P (2002) Dynamic local search algorithm for the clustering problem. Research report A-2002-6, University of Joensuu

24.

Pavan M, Pelillo M (2003) A graph-theoretic approach to clustering and segmentation. In: IEEE international conference on computer vision and pattern recognition, pp 145–152

25.

Pavan M, Pelillo M (2005) Efficient out-of-sample extension of dominant-set clusters. In: Advances in neural information processing systems, pp 1057–1064

26.

Pavan M, Pelillo M (2007) Dominant sets and pairwise clustering. IEEE Trans Pattern Anal Mach Intell 29(1):167–172CrossRef

27.

Rodriguez A, Laio A (2014) Clustering by fast search and find of density peaks. Science 344:1492–1496CrossRef

28.

Rosenberg A, Hirschberg J (2007) V-measure: a conditional entropy-based external cluster evaluation measure. In: Joint conference on empirical methods in natural language processing and computational natural language learning, pp 410–420

29.

Roy S, Bhattacharyya DK (2005) An approach to find embedded clusters using density based techniques. LNCS 3816:523–535

30.

Shi J, Malik J (2000) Normalized cuts and image segmentation. IEEE Trans Pattern Anal Mach Intell 22(8):167–172

31.

Torsello A, Bulo SR, Pelillo M (2006) Grouping with asymmetric affinities: a game-theoretic perspective. IEEE Int Conf Comput Vis Pattern Recognit 1:292–299

32.

Veenman CJ, Reinders M, Backer E (2002) A maximum variance cluster algorithm. IEEE Trans Pattern Anal Mach Intell 24(9):1273–1280CrossRef

33.

Wang XF, Xu Y (2016) Fast clustering using adaptive density peak detection. Stat Methods Med Res. https://doi.org/10.1177/0962280215609948.MathSciNetCrossRef

34.

Yang N, Liu Q, Li Y, Xiao L, Liu X (2016) Star-scan: a stable clustering by statistically finding centers and noises. In: Asia-Pacific web conference on web technologies and applications, pp 456–467CrossRef

35.

Zahn CT (1971) Graph-theoretical methods for detecting and describing gestalt clusters. IEEE Trans Comput 20(1):68–86CrossRef

36.

Zhu X, Loy CC, Gong S (2014) Constructing robust affinity graphs for spectral clustering. In: IEEE International conference on computer vision and pattern recognition, pp 1450–1457

Title: Density Based Cluster Growing via Dominant Sets
Authors: Jian Hou
Xu E
Weixue Liu
Publication date: 30-11-2017
Publisher: Springer US
Published in: Neural Processing Letters / Issue 2/2018
Print ISSN: 1370-4621
Electronic ISSN: 1573-773X
DOI: https://doi.org/10.1007/s11063-017-9767-3

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 2/2018

Adaptive Finite-Time Synchronization of Neutral Type Dynamical Network with Double Derivative Coupling

Domain Adaptation with Twin Support Vector Machines

On the Impact of Using Utilities Rather than Costs for Graph Matching

A New Conjugate Gradient Method with Smoothing Regularization Based on a Modified Secant Equation for Training Neural Networks

Dynamic Hybrid Random Fields for the Probabilistic Graphical Modeling of Sequential Data: Definitions, Algorithms, and an Application to Bioinformatics

Theoretical Foundations for the Alpha-Beta Associative Memories: 10 Years of Derived Extensions, Models, and Applications