Computational Complexity of Two Problems of Cognitive Data Analysis Full article
| Journal |
Journal of Applied and Industrial Mathematics
ISSN: 1990-4789 , E-ISSN: 1990-4797 |
||||
|---|---|---|---|---|---|
| Output data | Year: 2022, Volume: 16, Number: 1, Pages: 89-97 Pages count : 9 DOI: 10.1134/s1990478922010082 | ||||
| Tags | NP-hardness, taxonomy (clustering), typical object (prototypes) selection, function of rival similarity | ||||
| Authors |
|
||||
| Affiliations |
|
Funding (1)
| 1 | Sobolev Institute of Mathematics | 0314-2019-0015 |
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.
Cite:
Kutnenko O.A.
Computational Complexity of Two Problems of Cognitive Data Analysis
Journal of Applied and Industrial Mathematics. 2022. V.16. N1. P.89-97. DOI: 10.1134/s1990478922010082 Scopus РИНЦ OpenAlex
Computational Complexity of Two Problems of Cognitive Data Analysis
Journal of Applied and Industrial Mathematics. 2022. V.16. N1. P.89-97. DOI: 10.1134/s1990478922010082 Scopus РИНЦ OpenAlex
Original:
Кутненко О.А.
Вычислительная сложность двух задач когнитивного анализа данных
Дискретный анализ и исследование операций. 2022. Т.29. №1. С.18-32. DOI: 10.33048/daio.2022.29.713 РИНЦ OpenAlex
Вычислительная сложность двух задач когнитивного анализа данных
Дискретный анализ и исследование операций. 2022. Т.29. №1. С.18-32. DOI: 10.33048/daio.2022.29.713 РИНЦ OpenAlex
Dates:
| Submitted: | Apr 26, 2021 |
| Accepted: | Dec 3, 2021 |
| Published print: | Jul 10, 2022 |
Identifiers:
| Scopus: | 2-s2.0-85134068370 |
| Elibrary: | 51450384 |
| OpenAlex: | W4285410638 |
Citing:
Пока нет цитирований