Top

Calcolo

Published in:

29-04-2016

Fast indefinite multi-point (IMP) clustering

Authors: S. Chandrasekaran, A. Rajagopal

Published in: Calcolo | Issue 1/2017

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

search-config

AI-assisted search

Off

Abstract

A new class of objective functions and an associated fast descent algorithm that generalizes the K-means algorithm is presented. The algorithm represents clusters as unions of Voronoi cells and an explicit, but efficient, combinatorial search phase enables the algorithm to escape many local minima with guaranteed descent. The objective function has explicit penalties for gaps between clusters. Numerical experiments are provided.

previous article Optimal additive Schwarz preconditioning for hypersingular integral equations on locally refined triangulations

next article An extended Hessenberg form for Hamiltonian matrices

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 "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

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

Available only for authorised users

Aslam, J.A., Pelekhov, E., Rus, D.: The star clustering algorithm for information organization. In: Kogan, J., Nicholas, C., Teboulle, M. (eds.) Grouping multidimensional data. Springer, New York (2006)

Berkhin, P.: A survey of clustering data mining techniques. In: Kogan, J., Nicholas, C., Teboulle, M. (eds.) Grouping multidimensional data. Springer, New York (2006)

Eppstein, D.: Fast hierarchical clustering and other applications of dynamic closest pairs. J. Exp. Algorithmics 5(1) (2000)

Forgy, E.: Cluster analysis of multivariate data: efficiency vs. interpretability of classifications. Biometrics 21(3), 768 (1965)

Jain, A.K.: Data clustering: 50 years beyond \(K\)-means. Pattern Recogn. Lett. 31(8), 651–666 (2010)CrossRef

Kohonen, T.: “Self-Organization and Associative Memory,” Springer series in Information Sciences. Springer, New York (1989)

Larsen, B., Aone, C.: Fast and effective text mining using linear-time document clustering. In: Proceedings of the 5th ACM SIGKDD, pp. 16–22. San Diego (1999)

Lindsten, F., Ohlsson, H., Ljung, L.: Just Relax and Come Clustering! A Convexification of \(k\)-Means Clustering. Technical report from Automatic Control at Linköpings universitet, Report no.: LiTH-ISY-R-2992 (2011)

Lloyd, S.P.: Least squares quantization in PCM. IEEE Trans. Inf. Theory 28(2), 129–137 (1982)MathSciNetCrossRefMATH

10.

Marroquin, J.L., Girosi, F.: Some extensions of the \(k\)-means algorithm for image segmentation and pattern classification. Technical Report A.I. Memo 1390, MIT Press, Cambridge, MA, USA, (1993)

11.

McCallum, A., Nigam, K., Ungar, L.H.: Efficient Clustering of High-Dimensional Data Set with Application to Reference Matching. In: Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 169–178 (2000)

12.

Ohlsson, H., Ljung, L.: A Convex Approach to Subspace Clustering. In: 2011 50th IEEE Conference on Decision and Control and European Control Conference (CDC-ECC). Orlando (2011)

13.

Ostrovsky, R., Rabani, Y., Schulman, L.J., Swamy, C.: The effectiveness of Lloyd-Type Methods for the \(k\)-Means Problem. In: 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06) (2006)

14.

Rose, K., Gurewitz, E., Fox, G.C.: A deterministic annealing approach to clustering. Pattern Recogn. Lett. 11, 589–594 (1990)CrossRefMATH

15.

Rousseeuw, P.J., Kaufman, L., Trauwert, E.: Fuzzy clustering using scatter matrices. Comput. Stat. Data Anal. 23, 135–151 (1996)CrossRefMATH

16.

Steinbach, M., Karypis, G., Kumar, V.: A comparison of document clustering techniques. In: Proceedings of the 6th ACM SIGKDD, World Text Mining Conference. Boston (2000)

17.

Teboulle, M., Berkhin, P., Dhillon, I., Guan, Y., Kogan, J.: Clustering with Entropy-Like \(k\)-Means Algorithms. In: Kogan, J., Nicholas, C., Teboulle, M. (eds.) Grouping Multidimensional Data. Springer, New York (2006)

18.

Vattani, A.: \(K\)-means requires exponentially many iterations even in the plane. DCG (2011)

19.

Volkovich, Z., Kogan, J., Nicholas, C.: Sampling methods for building initial partitions. In: Kogan, J., Nicholas, C., Teboulle, M. (eds.) Grouping multidimensional data. Springer, New York (2006)

20.

Xu, R., Wunsch, D.: Survey of Clustering Algorithms. IEEE Trans. Neural Netw. 16(3) (2005)

21.

Hartigan, J.A., Wong, M.A.: Algorithm AS 136: a k-means clustering algorithm. Appl. Stat. (1979)

22.

Drake, J., Hamerly, G.: Accelerated k-means with adaptive distance bounds. In: 5th NIPS workshop on optimization for machine learning (2012)

23.

Kanungo, T. et al.: An efficient k-means clustering algorithm: analysis and implementation. Pattern analysis and machine intelligence, IEEE Transactions (2002)

24.

Elkan, C.: Using the triangle inequality to accelerate k-means. ICML 3 (2003)

25.

Pelleg, D., Moore, A.W.: X-means: extending K-means with efficient estimation of the number of clusters. ICML (2000)

26.

Arthur, D., Vassilvitskii, S.: k-means++: the advantages of careful seeding. In: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics (2007)

27.

Davies, D.L., Bouldin, D.W.: A cluster separation measure. Pattern Anal. Mach. Intell. IEEE Trans. 2 (1979)

28.

Chen, T.S., et al.: A combined K-means and hierarchical clustering method for improving the clustering efficiency of microarray. Intelligent Signal Processing and Communication Systems. ISPACS. In: Proceedings of 2005 International Symposium on. IEEE (2005)

29.

Muja, M., Lowe, D.G.: Fast approximate nearest neighbors with automatic algorithm configuration. VISAPP 2(1) (2009)

Title: Fast indefinite multi-point (IMP) clustering
Authors: S. Chandrasekaran
A. Rajagopal
Publication date: 29-04-2016
Publisher: Springer Milan
Published in: Calcolo / Issue 1/2017
Print ISSN: 0008-0624
Electronic ISSN: 1126-5434
DOI: https://doi.org/10.1007/s10092-016-0191-2

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 "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1/2017

Finite difference numerical solution of Troesch’s problem on a piecewise uniform Shishkin mesh

Gaussian radial basis function interpolant for the different data sites and basis centers

Sixth-order symplectic and symmetric explicit ERKN schemes for solving multi-frequency oscillatory nonlinear Hamiltonian equations

Generalized Peaceman-Rachford splitting method for multiple-block separable convex programming with applications to robust PCA

Greedy Strategies for Convex Optimization

Virtual element method stabilization for convection-diffusion-reaction problems using the link-cutting condition

Premium Partner