Top

Journal of Applied and Industrial Mathematics

Published in:

01-02-2022

Computational Complexity of Two Problems of Cognitive Data Analysis

Author: O. A. Kutnenko

Published in: Journal of Applied and Industrial Mathematics | Issue 1/2022

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

search-config

AI-assisted search

Off

Abstract

The NP-hardness in the strong sense is proved for two problems of cognitive data analysis. One of them is the problem of taxonomy (clustering), i.e., splitting an unclassified sample of objects into disjoint subsets. The other is the problem of sampling a subset of typical representatives of a classified sample that consists of objects of two images. The first problem can be considered as a special case of the second problem, provided that one of the images consists of one object. The function of rival similarity (FRiS-function) is used, which assesses the similarity of an object with the closest typical object, to obtain a quantitative quality estimate for the set of selected typical representatives of the sample.

previous article Mathematical Modeling of a High-Speed Collision of White Dwarfs—the Explosion Mechanism of Type Ia/Iax Supernovae

next article On Perfect Colorings of Paths Divisible by a Matching

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

N. G. Zagoruiko, I. A. Borisova, V. V. Dyubanov, and O. A. Kutnenko, “Methods of recognition based on the function of rival similarity,” Pattern Recognit. Image Anal. 18 (1), 1–6 (2008).CrossRef

I. A. Borisova, V. V. Dyubanov, N. G. Zagoruiko, and O. A. Kutnenko, “Similarity and compactness,” in Proc. All-Russ. Conf. Math. Methods Pattern Recognit.-14 (Suzdal, Russia, September 21–25, 2009), (Maks Press, Moscow, 2009) 89–92 [in Russian].

C. J. C. Burges, “A tutorial on support vector machines for pattern recognition,” Data Mining Knowl. Discovery 2 (2), 121–167 (1998).CrossRef

M. Tipping, “The relevance vector machine,” in Adv. Neural Inf. Process. Syst. (Morgan Kaufmann, San Mateo, CA, 2000).

N. G. Zagoruiko, Applied Methods of Data and Knowledge Analysis (Izd. Inst. Mat., Novosibirsk, 1999) [in Russian].

K. V. Vorontsov and A. O. Koloskov, “Compactness profiles and prototype object selection in metric classification algorithms,” Iskusstv. Intell. (2), 30–33 (2006).

M. N. Ivanov and K. V. Vorontsov, “Prototypes selection based on minimization of complete follow control functional,” in Proc. All-Russ. Conf. Math. Methods Pattern Recognit.-14 (Suzdal, Russia, September 21–25, 2009), (Maks Press, Moscow, 2009) 119–122 [in Russian].

S. Bermejo and J. Cabestany, “Learning with Nearest Neighbor Classifiers,” Neural Proc. Lett. 13 (2), 159–181 (2001).CrossRef

V. N. Vapnik, The Task of Learning Pattern Recognition (Znanie, Moscow, 1971) [in Russian].

10.

N. G. Zagoruiko, I. A. Borisova, V. V. Dyubanov, and O. A. Kutnenko, “A quantitative measure of compactness and similarity in a competitive space,” Sib. Zh. Ind. Math 13 (1), 59–71 (2010) [J. Appl. Ind. Math. 5 (1), 144–154 (2011)].CrossRef

11.

I. A. Borisova, “Taxonomy algorithm FRiS-Tax,” Nauchn. Vestn. NGTU (3), 3–12 (2007).

12.

I. A. Borisova and N. G. Zagoruiko, “FRiS-TDR algorithm for solving a generalized taxonomy and recognition problem,” in Proc. All-Russ. Conf. Knowl.-Ontology-Theory, KONT-09 (Novosibirsk, Russia, October 22–24 2009) (Novosibirsk, 2009), 1, 93–102 [in Russian].

13.

J. MacQueen, “Some methods for classification and analysis of multivariate observations,” in Proc. 5th Berkeley Symp. Math. Stat. Probab. (California, June 21–July 18, 1965 and December 27, 1965–January 7, 1966) (California Univ. Press, California, 1967), 1, 281—297.

14.

A. V. Zukhba, “NP-completeness of the problem of prototype selection in the nearest neighbor method,” Pattern Recognit. Image Anal. 20 (4), 484–494 (2010).CrossRef

15.

I. A. Borisova, V. V. Dyubanov, O. A. Kutnenko, and N. G. Zagoruiko, “Use of the FRiS-function for taxonomy, attribute selection and decision rule construction,” in Proc. First Int. Conf. KONT 2007 (Novosibirsk, Russia, September 14–16, 2007) and First Int. Conf. KPP 2007 (Darmstadt, Germany, September 28–30, 2007) Revised Selected Papers. Lect. Notes Comput. Sci. (Springer, Heidelberg, 2011), 6581, 256–270.

16.

N. G. Zagoruiko, I. A. Borisova, O. A. Kutnenko, and V. V. Dyubanov, “A construction of a compressed description of data using a function of rival similarity,” Sib. Zh. Ind. Mat. 16 (1), 29–41 (2013) [J. Appl. Ind. Math. 7 (2), 275–286 (2013)].MathSciNetCrossRef

17.

I. A. Borisova, “Computational complexity of the problem of choosing typical representatives in a 2-clustering of a finite set of points in a metric space,” Diskretnyi Anal. Issled. Oper. 27 (2), 5–16 (2020) [J. Appl. Ind. Math. 14 (2), 242–248 (2020)].MathSciNetCrossRef

18.

M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979; Mir, Moscow, 1982).MATH

Title: Computational Complexity of Two Problems of Cognitive Data Analysis
Author: O. A. Kutnenko
Publication date: 01-02-2022
Publisher: Pleiades Publishing
Published in: Journal of Applied and Industrial Mathematics / Issue 1/2022
Print ISSN: 1990-4789
Electronic ISSN: 1990-4797
DOI: https://doi.org/10.1134/S1990478922010082

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"

Other articles of this Issue 1/2022

On the Maximum Number of Open Triangles in Graphs with the Same Number of Vertices and Edges

On the Qualitative Analysis of the Equations of Motion of a Rigid Body in a Magnetic Field

On Perfect Colorings of Paths Divisible by a Matching

Properties of Boolean Functions with Extremal Number of Prime Implicants

Unsteady Flows of a Maxwell Viscoelastic Fluid near a Critical Point with a Countercurrent at the Initial Moment

On Complexity of Search for the Periods of Functions Given by Polynomials over a Prime Field

Premium Partners