Standard

Approximation polynomial algorithm for the data editing and data cleaning problem. / Ageeva, A. A.; Kel’manov, A. V.; Pyatkin, A. V. et al.

In: Pattern Recognition and Image Analysis, Vol. 27, No. 3, 01.07.2017, p. 365-370.

Research output: Contribution to journal › Article › peer-review

Harvard

Ageeva, AA, Kel’manov, AV, Pyatkin, AV, Khamidullin, SA & Shenmaier, VV 2017, 'Approximation polynomial algorithm for the data editing and data cleaning problem', Pattern Recognition and Image Analysis, vol. 27, no. 3, pp. 365-370. https://doi.org/10.1134/S1054661817030038

APA

Ageeva, A. A., Kel’manov, A. V., Pyatkin, A. V., Khamidullin, S. A., & Shenmaier, V. V. (2017). Approximation polynomial algorithm for the data editing and data cleaning problem. Pattern Recognition and Image Analysis, 27(3), 365-370. https://doi.org/10.1134/S1054661817030038

Vancouver

Ageeva AA, Kel’manov AV, Pyatkin AV, Khamidullin SA, Shenmaier VV. Approximation polynomial algorithm for the data editing and data cleaning problem. Pattern Recognition and Image Analysis. 2017 Jul 1;27(3):365-370. doi: 10.1134/S1054661817030038

Author

Ageeva, A. A. ; Kel’manov, A. V. ; Pyatkin, A. V. et al. / Approximation polynomial algorithm for the data editing and data cleaning problem. In: Pattern Recognition and Image Analysis. 2017 ; Vol. 27, No. 3. pp. 365-370.

BibTeX

@article{4a03a55aba4b4008a7764d31ca3a58a3,
title = "Approximation polynomial algorithm for the data editing and data cleaning problem",
abstract = "The work considers the mathematical aspects of one of the most fundamental problems of data analysis: search (choice) among a collection of objects for a subset of similar ones. In particular, the problem appears in connection with data editing and cleaning (removal of irrelevant (not similar) elements). We consider the model of this problem, i.e., the problem of searching for a subset of maximal cardinality in a finite set of points of the Euclidean space for which quadratic variation of points with respect to its unknown centroid does not exceed a given fraction of the quadratic variation of points of the input set with respect to its centroid. It is proved that the problem is strongly NP-hard. A polynomial 1/2-approximation algorithm is proposed. The results of the numerical simulation demonstrating the effectiveness of the algorithm are presented.",
keywords = "data analysis, Euclidean space, maximal cardinality, NP-hard problem, polynomial approximation algorithm, square variation, subset of similar elements",
author = "Ageeva, {A. A.} and Kel{\textquoteright}manov, {A. V.} and Pyatkin, {A. V.} and Khamidullin, {S. A.} and Shenmaier, {V. V.}",
year = "2017",
month = jul,
day = "1",
doi = "10.1134/S1054661817030038",
language = "English",
volume = "27",
pages = "365--370",
journal = "Pattern Recognition and Image Analysis",
issn = "1054-6618",
publisher = "Maik Nauka Publishing / Springer SBM",
number = "3",

}

RIS

TY - JOUR

T1 - Approximation polynomial algorithm for the data editing and data cleaning problem

AU - Ageeva, A. A.

AU - Kel’manov, A. V.

AU - Pyatkin, A. V.

AU - Khamidullin, S. A.

AU - Shenmaier, V. V.

PY - 2017/7/1

Y1 - 2017/7/1

N2 - The work considers the mathematical aspects of one of the most fundamental problems of data analysis: search (choice) among a collection of objects for a subset of similar ones. In particular, the problem appears in connection with data editing and cleaning (removal of irrelevant (not similar) elements). We consider the model of this problem, i.e., the problem of searching for a subset of maximal cardinality in a finite set of points of the Euclidean space for which quadratic variation of points with respect to its unknown centroid does not exceed a given fraction of the quadratic variation of points of the input set with respect to its centroid. It is proved that the problem is strongly NP-hard. A polynomial 1/2-approximation algorithm is proposed. The results of the numerical simulation demonstrating the effectiveness of the algorithm are presented.

AB - The work considers the mathematical aspects of one of the most fundamental problems of data analysis: search (choice) among a collection of objects for a subset of similar ones. In particular, the problem appears in connection with data editing and cleaning (removal of irrelevant (not similar) elements). We consider the model of this problem, i.e., the problem of searching for a subset of maximal cardinality in a finite set of points of the Euclidean space for which quadratic variation of points with respect to its unknown centroid does not exceed a given fraction of the quadratic variation of points of the input set with respect to its centroid. It is proved that the problem is strongly NP-hard. A polynomial 1/2-approximation algorithm is proposed. The results of the numerical simulation demonstrating the effectiveness of the algorithm are presented.

KW - data analysis

KW - Euclidean space

KW - maximal cardinality

KW - NP-hard problem

KW - polynomial approximation algorithm

KW - square variation

KW - subset of similar elements

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

U2 - 10.1134/S1054661817030038

DO - 10.1134/S1054661817030038

M3 - Article

AN - SCOPUS:85029482767

VL - 27

SP - 365

EP - 370

JO - Pattern Recognition and Image Analysis

JF - Pattern Recognition and Image Analysis

SN - 1054-6618

IS - 3

ER -

ID: 9912698