About Journal 
Editorial Board
Publishing Ethics
Author Guide 
Submission
Prepare Your Manuscript
Peer review
Archive
Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
Volume 28, No 2, 2021, P. 60-73
UDC 519.87+519.854
O. A. Kutnenko and A. V. Plyasunov
NP-hardness of some data cleaning problem
Abstract:
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.
DOI: 10.33048/daio.2021.28.692
Olga A. Kutnenko 1,2
Aleksandr V. Plyasunov 1,2
1. Sobolev Institute of Mathematics,
4 Koptyug Ave., 630090 Novosibirsk, Russia
2. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: olga@math.nsc.ru, apljas@math.nsc.ru
Received June 10, 2020
Revised December 22, 2020
Accepted December 24, 2020
References
[1] J. W. Osborne, 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).[2] A. Farcomeni and L. Greco, Robust Methods for Data Reduction (CRC Press, New York, 2015).
[3] T. D. Waal, J. Pannekoek, and S. Scholtus, Handbook of Statistical Data Editing and Imputation (Wiley, Hoboken, NJ, 2011).
[4] I. A. Borisova and O. A. Kutnenko, Censoring misclassified sample items, Mash. Obuch. Anal. Dannykh 1 (11), 1632–1641 (2015) [Russian].
[5] C. C. Aggarwal, Data Mining (Springer, Cham, 2015).
[6] H. Brighton and C. Mellish, Advances in instance selection for instance-based learning algorithms, Data Min. Knowl. Discov. 6 (2), 153–172 (2002).
[7] S. J. Delany, N. Segata, and B. Mac Namee, Profiling instances in noise reduction, Knowl.-B. Syst. 31, 28–40 (2012).
[8] B. Frenay and M. Verleysen, Classification in the presence of label noise: A survey, IEEE Trans. Neural Netw. Learn. Syst. 25 (5), 845–869 (2014).
[9] N. Jankowski and M. Grochowski, Comparison of instances selection algorithms I. Algorithms survey, in Artificial Intelligence and Soft Computing — ICAISC 2004 (Proc. 7th Int. Conf., Zakopane, Poland, June 7–11, 2004) (Springer, Heidelberg, 2004), pp. 598–603 (Lect. Notes Comput. Sci., Vol. 3070).
[10] S. Massie, S. Craw, and N. Wiratunga, When similar problems don’t have similar solutions, in Case-Based Reasoning Research and Development (Proc. 7th Int. Conf., Belfast, NI, UK, Aug. 13–16, 2007) (Springer, Heidelberg, 2007), pp. 92–106 (Lect. Notes Comput. Sci., Vol. 4626).
[11] J. R. Quinlan, Induction of decision trees, Mach. Learn. 1, 81–106 (1986).
[12] N. Segata and E. Blanzieri, Noise reduction for instance-based learning with a local maximal margin approach, J. Intel. Inf. Syst. 35 (2), 301–331 (2010).
[13] S.-H. Son and J.-Y. Kim, Data reduction for instance-based learning using entropy-based partitioning, in Computational Science and Its Applications — ICCSA 2006 (Proc. Int. Conf., Glasgow, UK, May 8–11, 2006), Pt. 3, (Springer, Heidelberg, 2006), pp. 590–599 (Lect. Notes Comput. Sci., Vol. 3982).
[14] C. M. Teng, A comparison of noise handling techniques, in Proc. 14th Int. Florida Artificial Intelligence Res. Soc. Conf., Key West, FL, USA, May 21–23, 2001 (AAAI Press, Menlo Park, CA, 2001), pp. 269–273.
[15] D. R. Wilson and T. R. Martinez, Reduction techniques for instance-based learning algorithms, Mach. Learn. 38 (3), 257–286 (2000).
[16] A. G. Arkadyev and Eh. M. Braverman, Machine Learning to Pattern Recognition (Nauka, Moscow, 1964) [Russian].
[17] N. G. Zagoruiko, Cognitive Data Analysis (Akad. Izd. GEO, Novosibirsk, 2013) [Russian].
[18] I. A. Borisova, V. V. Dyubanov, O. A. Kutnenko, and N. G. Zagoruiko, Use of the FRiS-function for taxonomy, attribute selection and decision rule construction, in 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) (Springer, Heidelberg, 2011), pp. 256–270 (Lect. Notes Comput. Sci., Vol. 6581).
[19] N. G. Zagoruiko, I. A. Borisova, V. V. Dyubanov, and O. A. Kutnenko, Methods of recognition based on the function of rival similarity, Pattern Recognit. Image Anal. 18 (1), 1–6 (2008).
[20] N. G. Zagoruiko, I. A. Borisova, V. V. Dyubanov, and O. A. Kutnenko, A quantitative measure of compactness and similarity in competitive space, Sib. Zh. Ind. Mat. 13 (1), 59–71 (2010) [Russian] [Sib. J. Ind. Math. 5 (1), 144–154 (2011)].
[21] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979; Mir, Moscov, 1982 [Russian]).
[22] I. A. Borisova and O. A. Kutnenko, Correction of diagnostic errors in the target attribute with the function of rival similarity, Mat. Biol. Bioinform. 13 (1), 38–49 (2018) [Russian].
[23] N. G. Zagoruiko and O. A. Kutnenko, Censoring of a train dataset, Vestn. Tomsk. Gos. Univ., Ser. Upr. Vychisl. Tekh. Inform., No. 22, 66–73 (2013) [Russian].
