Research output: Contribution to journal › Article › peer-review
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 journal › Article › peer-review
}
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