nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

Initial Centroid Selection Method for an Enhanced K-means Clustering Algorithm

verfasst von : Youssef Aamer, Yahya Benkaouz, Mohammed Ouzzif, Khalid Bouragba

Erschienen in: Ubiquitous Networking

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Clustering is an important method to discover structures and patterns in high-dimensional data and group similar ones together. K-means is one of the most popular clustering algorithms. K-means groups observations by minimizing distances between them and maximizing group distances. One of the primordial steps in this algorithm is centroid selection, in which k initial centroids are estimated either randomly, calculated, or given by the user. Existing k-means algorithms uses the ‘k-means++’ option for this selection. In this paper, we suggest an enhanced version of k-means clustering that minimize the runtime of the algorithm using ‘Ndarray’ option. Experiments have shown that if the first choice of centroids is close to the final centers, the results will be quickly found. Thus, we propose a new concept that provides one of the best choices of starting centroids that reduces the execution time by ≈80% on average for UCI, Shape and Miscellaneous 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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel A Congestion Game Analysis for Route-Parking Selection with Dynamic Pricing Policies

Nächstes Kapitel Dependency Between the Distance and International Voice Traffic

http://archive.ics.uci.edu/ml/

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

Bayer, J.: Customer segmentation in the telecommunication industry. J. Database Mark. Cust. Strategy Manag. 17(3/4), 247–256 (2010)CrossRef

Catanese, S.A., De Meo, P., Ferrara, E., Fiumara, G., Provetti, A.: Crawling Facebook for social network analysis purposes. In: Proceedings of the International Conference on Web Intelligence, Mining and Semantics, p. 52. ACM (2011)

Gong, Y., Liu, X.: Generic text summarization using relevance measure and latent semantic analysis. In: SIGIR 2001: Proceedings of the 24th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 19–25 (2001)

Rousseeuw, P.J.: Silhouettes: a graphical aid to the interpretation and validation of cluster analysis. Comput. Appl. Math. 20, 53–65 (1987)CrossRef

Baswade, A.M., Nalwade, P.S.: Selection of initial centroids for k-means algorithm. Int. J. Comput. Sci. Mob. Comput. 2(7), 161–164 (2013)

Kanungo, T., Mount, D.: An efficient k-means clustering algorithm: analysis and implantation. IEEE Trans. PAMI 24, 881–892 (2004)CrossRef

Arthur, D., Vassilvitskii, S.: Worst-case and smoothed analysis of the ICP algorithm, with an application to the k-means method. In: Symposium on Foundations of Computer Science (2006)

10.

Gilpin, S., Davidson, I.: Incorporating SAT solvers into hierarchical clustering algorithms: an efficient and flexible approach. In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, California, USA, 21–24 August 2011 (2011)

11.

Bradley, P.S., Fayyad, U.M.: Refining initial points for k-means clustering. In: Proceedings of the Fifteenth International Conference on Machine Learning, pp. 91–99. Morgan Kaufmann Publishers Inc., San Francisco (1998)

12.

Gustafson, D.E., Kessel, W.C.: Fuzzy clustering with a fuzzy covariance matrix. In: Proceedings of the IEEE Conference on Decision Control, San Diego, CA, pp. 761–766 (1979)

13.

Yu, Y., Wang, Q., Kuang, J., He, J.: An on-line density-based clustering algorithm for spatial data stream. Acta Automatica Sinica 38(6), 1051–1059 (2012)CrossRef

14.

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

15.

Arthur, D., Vassilvitskii, S.: k-means++: the advantages of careful seeding. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete algorithms, SODA 2007, pp. 1027–1035. Society for Industrial and Applied Mathematics, Philadelphia (2007)

16.

Avrithis, Y., Kalantidis, Y., Anagnostopoulos, E., Emiris, I.Z.: Web-scale image clustering revisited. In: Proceedings of the 2015 IEEE International Conference on Computer Vision (ICCV), 07–13 December 2015, pp. 1502–1510 (2015)

17.

Elkan, C.: Using the triangle inequality to accelerate k-means. In: Proceedings of the Twentieth International Conference on International Conference on Machine Learning, Washington, DC, USA, 21–24 August 2003, pp. 147–153 (2003)

18.

Arai, K., Barakbah, A.R.: Hierarchical K-means: an algorithm for centroids initialization for k-means. Rep. Fac. Sci. Eng. Saga Univ. 36(1), 25–31 (2007)

19.

Fahim, A.M, Salem, A.M, Torkey, F.A., Ramadan, M.A.: An efficient enhanced k-means clustering algorithm. J. Zhejiang Univ. Sci. 7, 1626–1633 (2006)

Titel: Initial Centroid Selection Method for an Enhanced K-means Clustering Algorithm
verfasst von: Youssef Aamer
Yahya Benkaouz
Mohammed Ouzzif
Khalid Bouragba
Verlag: Springer International Publishing
Buch: Ubiquitous Networking
Print ISBN: 978-3-030-58007-0

Electronic ISBN: 978-3-030-58008-7

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-58008-7_15

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"