Geodesic
NP-hardness of~some data cleaning problem
Diskretnyj analiz i issledovanie operacij, Tome 28 (2021) no. 2, pp. 60-73.

Voir la notice de l'article provenant de la source Math-Net.Ru

We prove the NP-hardness of the problem of outliers detection considered in this paper, to solving which a data analysis problem is reduced. As a quantitative assessment of the compactness of the image, the function of rival similarity (FRiS-function) is used, which evaluates the local similarity of objects with their closest neighbors. Illustr. 1, bibliogr. 23.
Keywords: NP-hardness, detecting outliers, image compactness, function of rival similarity. 
@article{DA_2021_28_2_a2,
     author = {O. A. Kutnenko and A. V. Plyasunov},
     title = {NP-hardness of~some data cleaning problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {60--73},
     publisher = {mathdoc},
     volume = {28},
     number = {2},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2021_28_2_a2/}
}
TY  - JOUR
AU  - O. A. Kutnenko
AU  - A. V. Plyasunov
TI  - NP-hardness of~some data cleaning problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2021
SP  - 60
EP  - 73
VL  - 28
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2021_28_2_a2/
LA  - ru
ID  - DA_2021_28_2_a2
ER  - 
%0 Journal Article
%A O. A. Kutnenko
%A A. V. Plyasunov
%T NP-hardness of~some data cleaning problem
%J Diskretnyj analiz i issledovanie operacij
%D 2021
%P 60-73
%V 28
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2021_28_2_a2/
%G ru
%F DA_2021_28_2_a2
O. A. Kutnenko; A. V. Plyasunov. NP-hardness of~some data cleaning problem. Diskretnyj analiz i issledovanie operacij, Tome 28 (2021) no. 2, pp. 60-73. http://geodesic.mathdoc.fr/item/DA_2021_28_2_a2/

[1] Osborne J. W., Best practices in data cleaning: A complete guide to everything you need to do before and after collecting your data, SAGE Publ., Los Angeles, 2013, 296 pp.

[2] Farcomeni A., Greco L., Robust methods for data reduction, CRC Press, New York, 2015, 297 pp. | Zbl

[3] Waal T. D., Pannekoek J., Scholtus S., Handbook of statistical data editing and imputation, Wiley, Hoboken, NJ, 2011, 456 pp.

[4] I. A. Borisova, O. A. Kutnenko, “Censoring misclassified sample items”, Mash. Obuch. Anal. Dannykh, 1:11 (2015), 1632–1641 (Russian)

[5] Aggarwal C. C., Data mining, Springer, Cham, 2015, 734 pp. | MR | Zbl

[6] Brighton H., Mellish C., Data Min. Knowl. Discov., 6:2 (2002), Advances in instance selection for instance-based learning algorithms | DOI | MR

[7] Delany S. J., Segata N., Mac Namee B., “Profiling instances in noise reduction”, Knowl.-B. Syst., 31 (2012), 28–40 | DOI

[8] Frenay B., Verleysen M., “Classification in the presence of label noise: A survey”, IEEE Trans. Neural Netw. Learn. Syst., 25:5 (2014), 845–869 | DOI

[9] Jankowski N., Grochowski M., “Comparison of instances selection algorithms I. Algorithms survey”, Artificial Intelligence and Soft Computing — ICAISC 2004, Proc. 7th Int. Conf. (Zakopane, Poland, June 7–11, 2004), Lect. Notes Comput. Sci., 3070, Springer, Heidelberg, 2004, 598–603 | DOI | Zbl

[10] Massie S., Craw S., Wiratunga N., “When similar problems don't have similar solutions”, Case-Based Reasoning Research and Development, Proc. 7th Int. Conf. (Belfast, NI, UK, Aug. 13–16, 2007), Lect. Notes Comput. Sci., 4626, Springer, Heidelberg, 2007, 92–106 | DOI

[11] Quinlan J. R., “Induction of decision trees”, Mach. Learn., 1 (1986), 81–106 | MR

[12] Segata N., Blanzieri E., “Noise reduction for instance-based learning with a local maximal margin approach”, J. Intel. Inf. Syst., 35:2 (2010) | DOI

[13] Son S.-H., Kim J.-Y., “Data reduction for instance-based learning using entropy-based partitioning”, Computational Science and Its Applications — ICCSA 2006, Proc. Int. Conf. (Glasgow, UK, May 8–11, 2006), v. 3, Lect. Notes Comput. Sci., 3982, Springer, Heidelberg, 2006, 590–599 | DOI | Zbl

[14] Teng C. M., “A comparison of noise handling techniques”, Proc. 14th Int. Florida Artificial Intelligence Res. Soc. Conf. (Key West, FL, USA, May 21–23, 2001), AAAI Press, Menlo Park, CA, 2001, 269–273

[15] Wilson D. R., Martinez T. R., “Reduction techniques for instance-based learning algorithms”, Mach. Learn., 38:3 (2000), 257–286 | DOI | MR | Zbl

[16] A. G. Arkadyev, Eh. M. Braverman, Machine Learning to Pattern Recognition, Nauka, M., 1964 (Russian)

[17] N. G. Zagoruiko, Cognitive Data Analysis, Akad. Izd. GEO, Novosibirsk, 2013 (Russian)

[18] Borisova I. A., Dyubanov V. V., Kutnenko O. A., Zagoruiko N. G., “Use of the FRiS-function for taxonomy, attribute selection and decision rule construction”, Knowledge Processing and Data Analysis, Rev. Sel. Pap. 1st Int. Conf. KONT 2007, Novosibirsk, Russia, Sept. 14–16, 2007; 1st Int. Conf. KPP 2007, Darmstadt, Germany, Sept. 28–30, 2007, Lect. Notes Comput. Sci., 6581, Springer, Heidelberg, 2011, 256–270 | DOI

[19] Zagoruiko N. G., Borisova I. A., Dyubanov V. V., Kutnenko O. A., “Methods of recognition based on the function of rival similarity”, Pattern Recognit. Image Anal., 18:1 (2008), 1–6 | DOI

[20] N. G. Zagoruiko, I. A. Borisova, V. V. Dyubanov, O. A. Kutnenko, “A quantitative measure of compactness and similarity in competitive space”, Sib. J. Ind. Math., 5:1 (2011), 144–154 | MR

[21] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979 | MR | Zbl

[22] I. A. Borisova, O. A. Kutnenko, “Correction of diagnostic errors in the target attribute with the function of rival similarity”, Mat. Biol. Bioinform., 13:1 (2018), 38–49 (Russian)

[23] N. G. Zagoruiko, O. A. Kutnenko, “Censoring of a train dataset”, Vestn. Tomsk. Gos. Univ., Ser. Upr. Vychisl. Tekh. Inform., 2013, no. 22, 66–73 (Russian)