Standard

Computational Complexity of Two Problems of Cognitive Data Analysis. / Kutnenko, O. A.

In: Journal of Applied and Industrial Mathematics, Vol. 16, No. 1, 02.2022, p. 89-97.

Research output: Contribution to journalArticlepeer-review

Harvard

Kutnenko, OA 2022, 'Computational Complexity of Two Problems of Cognitive Data Analysis', Journal of Applied and Industrial Mathematics, vol. 16, no. 1, pp. 89-97. https://doi.org/10.1134/S1990478922010082

APA

Vancouver

Kutnenko OA. Computational Complexity of Two Problems of Cognitive Data Analysis. Journal of Applied and Industrial Mathematics. 2022 Feb;16(1):89-97. doi: 10.1134/S1990478922010082

Author

Kutnenko, O. A. / Computational Complexity of Two Problems of Cognitive Data Analysis. In: Journal of Applied and Industrial Mathematics. 2022 ; Vol. 16, No. 1. pp. 89-97.

BibTeX

@article{8b0e436200a6457d8cce972a2beb9ec9,
title = "Computational Complexity of Two Problems of Cognitive Data Analysis",
abstract = "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 ofobjects into disjoint subsets. The other is the problem of sampling a subset of typicalrepresentatives of a classified sample that consists of objects of two images. The first problem canbe considered as a special case of the second problem, provided that one of the images consists ofone object. The function of rival similarity (FRiS-function) is used, which assesses the similarityof an object with the closest typical object, to obtain a quantitative quality estimate for the set ofselected typical representatives of the sample.",
keywords = "function of rival similarity, NP-hardness, taxonomy (clustering), typical object (prototype) selection",
author = "Kutnenko, {O. A.}",
note = "Funding Information: The study was carried out within the framework of the state contract of Sobolev Institute of Mathematics, project no. 0314–2019–0015. Publisher Copyright: {\textcopyright} 2022, Pleiades Publishing, Ltd.",
year = "2022",
month = feb,
doi = "10.1134/S1990478922010082",
language = "English",
volume = "16",
pages = "89--97",
journal = "Journal of Applied and Industrial Mathematics",
issn = "1990-4789",
publisher = "Maik Nauka-Interperiodica Publishing",
number = "1",

}

RIS

TY - JOUR

T1 - Computational Complexity of Two Problems of Cognitive Data Analysis

AU - Kutnenko, O. A.

N1 - Funding Information: The study was carried out within the framework of the state contract of Sobolev Institute of Mathematics, project no. 0314–2019–0015. Publisher Copyright: © 2022, Pleiades Publishing, Ltd.

PY - 2022/2

Y1 - 2022/2

N2 - 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 ofobjects into disjoint subsets. The other is the problem of sampling a subset of typicalrepresentatives of a classified sample that consists of objects of two images. The first problem canbe considered as a special case of the second problem, provided that one of the images consists ofone object. The function of rival similarity (FRiS-function) is used, which assesses the similarityof an object with the closest typical object, to obtain a quantitative quality estimate for the set ofselected typical representatives of the sample.

AB - 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 ofobjects into disjoint subsets. The other is the problem of sampling a subset of typicalrepresentatives of a classified sample that consists of objects of two images. The first problem canbe considered as a special case of the second problem, provided that one of the images consists ofone object. The function of rival similarity (FRiS-function) is used, which assesses the similarityof an object with the closest typical object, to obtain a quantitative quality estimate for the set ofselected typical representatives of the sample.

KW - function of rival similarity

KW - NP-hardness

KW - taxonomy (clustering)

KW - typical object (prototype) selection

UR - http://www.scopus.com/inward/record.url?scp=85134068370&partnerID=8YFLogxK

U2 - 10.1134/S1990478922010082

DO - 10.1134/S1990478922010082

M3 - Article

AN - SCOPUS:85134068370

VL - 16

SP - 89

EP - 97

JO - Journal of Applied and Industrial Mathematics

JF - Journal of Applied and Industrial Mathematics

SN - 1990-4789

IS - 1

ER -

ID: 36770933