Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Deep Neural Network Ensembles Kapitel lesen Erstes Kapitel lesen

2019 | OriginalPaper | Buchkapitel

A Structural Theorem for Center-Based Clustering in High-Dimensional Euclidean Space

verfasst von : Vladimir Shenmaier

Erschienen in: Machine Learning, Optimization, and Data Science

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

We prove that, for any finite set X in Euclidean space of any dimension and for any fixed \(\varepsilon >0\), there exists a polynomial-cardinality set of points in this space which can be constructed in polynomial time and which contains \((1+\varepsilon )\)-approximations of all the points of space in terms of the distances to every element of X. The proved statement allows to approximate a lot of clustering problems which can be reduced to finding optimal cluster centers in high-dimensional space. In fact, we construct a polynomial-time approximation-preserving reduction of such problems to their discrete versions, in which the desired centers must be selected from a given finite set.

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 Using Clustering for Supervised Feature Selection to Detect Relevant Features
Nächstes Kapitel Modification of the k-MXT Algorithm and Its Application to the Geotagged Data Clustering
Literatur
1.
Agarwal, P.K., Har-Peled, S., Varadarajan, K.R.: Geometric approximation via coresets combinatorial and computational geometry. MSRI 52, 1–30 (2005)MATH
2.
Ahmadian S., Norouzi-Fard A., Svensson O., Ward J.: Better guarantees for \(k\)-means and Euclidean \(k\)-median by primal-dual algorithms. In: Proceedings of 58th Symposium on Foundations of Computer Science (FOCS 2017), pp. 61–72 (2017)
3.
Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms. Addison-Wesley, Boston (1974)MATH
4.
Aloise, D., Deshpande, A., Hansen, P., Popat, P.: NP-hardness of Euclidean sum-of-squares clustering. Mach. Learn. 75(2), 245–248 (2009)CrossRef
5.
Bǎdoiu, M., Har-Peled, S., Indyk, P.: Approximate clustering via core-sets. In: Proceedings of 34th ACM Symposium on Theory of Computing (STOC 2002), pp. 250–257 (2002)
6.
Bhattacharya, A., Jaiswal, R., Kumar, A.: Faster algorithms for the constrained \(k\)-means problem. Theory Comput. Syst. 62(1), 93–115 (2018)MathSciNetCrossRef
7.
Chen, K.: On coresets for \(k\)-median and \(k\)-means clustering in metric and euclidean spaces and their applications. SIAM J. Comput. 39(1), 923–947 (2009)MathSciNetCrossRef
8.
9.
Feldman, D., Monemizadeh, M., Sohler, C.: A PTAS for \(k\)-means clustering based on weak coresets. In: Proceedings of 23rd ACM Symposium on Computational Geometry, pp. 11–18 (2007)
10.
Guruswami, V., Indyk, P.: Embeddings and non-approximability of geometric problems. In: Proceedings of 14th ACM-SIAM Symposium on Discrete Algorithms (SODA 2003), pp. 537–538 (2003)
11.
Jaiswal, R., Kumar, A., Sen, S.: A simple \(D^2\)-sampling based PTAS for \(k\)-means and other clustering problems. Algorithmica 70(1), 22–46 (2014)MathSciNetCrossRef
12.
Kel’manov, A.V., Pyatkin, A.V.: NP-completeness of some problems of choosing a vector subset. J. Appl. Industr. Math. 5(3), 352–357 (2011)CrossRef
13.
Kumar, A., Sabharwal, Y., Sen, S.: Linear-time approximation schemes for clustering problems in any dimensions. J. ACM. 57(2), 1–32 (2010)MathSciNetCrossRef
14.
Lee, E., Schmidt, M., Wright, J.: Improved and simplified inapproximability for \(k\)-means. Inf. Proc. Lett. 120, 40–43 (2017)MathSciNetCrossRef
15.
Shenmaier, V.V.: An approximation scheme for a problem of search for a vector subset. J. Appl. Industr. Math. 6(3), 381–386 (2012)MathSciNetCrossRef
16.
Shenmaier, V.V.: The problem of a minimal ball enclosing \(k\) points. J. Appl. Industr. Math. 7(3), 444–448 (2013)MathSciNetCrossRef
17.
Shenmaier, V.V.: Complexity and approximation of the smallest \(k\)-enclosing ball problem. Eur. J. Comb. 48, 81–87 (2015)MathSciNetCrossRef
Metadaten
Titel
A Structural Theorem for Center-Based Clustering in High-Dimensional Euclidean Space
verfasst von
Vladimir Shenmaier
Copyright-Jahr
2019
Buch
Machine Learning, Optimization, and Data Science

Print ISBN: 978-3-030-37598-0

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

Copyright-Jahr: 2019

DOI
https://doi.org/10.1007/978-3-030-37599-7_24