Approximation polynomial algorithm for the data editing and data cleaning problem
| Autor: | Sergey A. Khamidullin, Artem V. Pyatkin, Alexander Kel'manov, Alexander A. Ageev, V. V. Shenmaier |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Discrete mathematics
Polynomial Data editing Centroid 02 engineering and technology Computer Graphics and Computer-Aided Design Quadratic variation Set (abstract data type) 020303 mechanical engineering & transports Cardinality 0203 mechanical engineering 0202 electrical engineering electronic engineering information engineering Subset sum problem 020201 artificial intelligence & image processing Computer Vision and Pattern Recognition Finite set Algorithm Mathematics |
| Zdroj: | Pattern Recognition and Image Analysis. 27:365-370 |
| ISSN: | 1555-6212 1054-6618 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink