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
Pattern Recognition and Image Analysis
Erschienen in: Pattern Recognition and Image Analysis 4/2019

01.10.2019 | MATHEMATICAL THEORY OF PATTERN RECOGNITION

An Accelerated Exact Algorithm for the One-Dimensional M-Variance Problem

verfasst von: A. V. Kel’manov, P. S. Ruzankin

Erschienen in: Pattern Recognition and Image Analysis | Ausgabe 4/2019

Einloggen

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

search-config
loading …

Abstract

The known quadratic \(NP\)-hard (in the strong sense) \(M\)-variance problem is considered. It arises in the following typical problem of data analysis: in a set of \(N\) objects determined by their characteristics (features), find a subset of \(M\) elements close to each other. For the one-dimensional case, an accelerated exact algorithm with complexity \(\mathcal{O}(N{\kern 1pt} \log{\kern 1pt} N)\) is proposed.
Nächster Artikel Subjective Restoration of Mathematical Models for a Research Object, Its Measurements, and Measurement-Data Interpretation

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

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
Literatur
1.
G. James, D. Witten, T. Hastie, and R. Tibshirani, An Introduction to Statistical Learning: With Application in R (Springer Science + Business Media, New York, 2013).
2.
J. W. Osborne, Best Practices in Data Cleaning: A Complete Guide to Everything You Need to Do before and after Collecting Your Data, 1st ed. (SAGE Publ., Los Angeles, 2013).CrossRef
3.
T. de Waal, J. Pannekoek, and S. Scholtus, Handbook of Statistical Data Editing and Imputation (Wiley, Hoboken, NJ, 2011).CrossRef
4.
A. Farcomeni and L. Greco, Robust Methods for Data Reduction (Chapman and Hall/CRC, Boca Raton, 2015).MATH
5.
C. C. Aggarwal, Data Mining: The Textbook (Springer Int. Publ., 2015).MATH
6.
C. M. Bishop, Pattern Recognition and Machine Learning (Springer Science + Business Media, New York, 2006).
7.
T. Hastie, R. Tibshirani, and J. Friedman, The Elements of Statistical Learning: Data Mining, Inference, and Prediction, 2nd ed. (Springer, New York, 2009).CrossRef
8.
I. Goodfellow, Y. Bengio, and A. Courville, Deep Learning, in Adaptive Computation and Machine Learning Series (MIT Press, Cambridge, MA, 2016).MATH
9.
A. Aggarwal, H. Imai, N. Katoh, and S. Suri, “Finding \(k\) points with minimum diameter and related problems,” J. Algorithms 12 (1), 38–56 (1991).MathSciNetCrossRef
10.
A. V. Kel’manov and A. V. Pyatkin, “NP-Completeness of some problems of choosing a vector subset,” J. Appl. Indust. Math. 5 (3), 352–357 (2011).CrossRef
11.
C. H. Papadimitriou, Computational Complexity (Addison-Wesley, New York, 1994).MATH
12.
M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979).MATH
13.
A. V. Kel’manov and S. M. Romanchenko, “An approximation algorithm for solving a problem of search for a vector subset,” J. Appl. Indust. Math. 6 (1), 90–96 (2012).CrossRef
14.
V. V. Shenmaier, “An approximation scheme for a problem of search for a vector subset,” J. Appl. Indust. Math. 6 (3), 381–386 (2012).MathSciNetCrossRef
15.
A. Kel’manov, V. Khandeev, and A. Panasenko, “Randomized algorithms for some clustering problems,” in Optimization Problems and Their Applications, OPTA 2018, Ed. by A. Eremeev, M. Khachay, Y. Kochetov, and P. Pardalos, Communications in Computer and Information Science (Springer, Cham, 2018), Vol. 871, pp. 109–119.
16.
A. V. Kel’manov and S. M. Romanchenko, “An FPTAS for a vector subset search problem,” J. Appl. Indust. Math. 8 (3), 329–336 (2014).CrossRef
17.
A. Kel’manov, A. Motkova, and V. Shenmaier, “An approximation scheme for a weighted two-cluster partition problem,” in Analysis of Images, Social Networks and Texts, AIST 2017, Ed. by W. M. P. van der Aalst, Lecture Notes in Computer Science (Springer, Cham, 2018), Vol. 10716, pp. 323–333.
18.
V. V. Shenmaier, “Solving some vector subset problems by Voronoi diagrams,” J. Appl. Indust. Math. 10 (4), 560–566 (2016).MathSciNetCrossRef
19.
A. V. Kel’manov and S. M. Romanchenko, “Pseudopolynomial algorithms for certain computationally hard vector subset and cluster analysis problems,” Autom. Remote Control 73 (2), 349–354 (2012).MathSciNetCrossRef
Metadaten
Titel
An Accelerated Exact Algorithm for the One-Dimensional M-Variance Problem
verfasst von
A. V. Kel’manov
P. S. Ruzankin
Publikationsdatum
01.10.2019
Verlag
Pleiades Publishing
Erschienen in
Pattern Recognition and Image Analysis / Ausgabe 4/2019
Print ISSN: 1054-6618
Elektronische ISSN: 1555-6212
DOI
https://doi.org/10.1134/S1054661819040072

Weitere Artikel der Ausgabe 4/2019

Pattern Recognition and Image Analysis 4/2019 Zur Ausgabe

APPLIED PROBLEMS

A Method for Predicting Rare Events by Multidimensional Time Series with the Use of Collective Methods

APPLIED PROBLEMS

An Efficient Human Activity Recognition Technique Based on Deep Learning

MATHEMATICAL THEORY OF IMAGES AND SIGNALS REPRESENTING, PROCESSING, ANALYSIS, RECOGNITION AND UNDERSTANDING

Research on Improvement of Stagewise Weak Orthogonal Matching Pursuit Algorithm

MATHEMATICAL THEORY OF IMAGES AND SIGNALS REPRESENTING, PROCESSING, ANALYSIS, RECOGNITION AND UNDERSTANDING

Generalized Spectral-Analytical Method and Its Applications in Image Analysis and Pattern Recognition Problems

PATTERN RECOGNITION AND IMAGE ANALYSIS MILIEU

On Behalf of the National Committee of the Russian Academy of Sciences for Pattern Recognition and Image Analysis

APPLIED ARTIFICIAL INTELLIGENCE SYSTEMS. KNOWLEDGE-BASED AND INTELLIGENCE SYSTEMS

On the Procedures of Generation of Numerical Features over Partitions of Sets of Objects in the Problem of Predicting Numerical Target Variables