Том 28, номер 2, 2021 г., Стр. 60-73

УДК 519.87+519.854
Кутненко О. А., Плясунов А. В.
NP-трудность некоторой задачи цензурирования данных

Аннотация:
Доказана NP-трудность рассматриваемой в работе постановки задачи цензурирования данных. К решению такой задачи сводится одна из проблем анализа данных. В качестве количественной оценки компактности образа используется функция конкурентного сходства (FRiS-функция), с помощью которой оценивается локальное сходство объектов со своими ближайшими соседями.
Ил. 1, библиогр. 23.

Ключевые слова: NP-трудность, цензурирование объектов, компактность образов, функция конкурентного сходства.

DOI: 10.33048/daio.2021.28.692

Кутненко Ольга Андреевна ^1,2
Плясунов Александр Владимирович ^1,2
1. Институт математики им. С. Л. Соболева,
пр. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: olga@math.nsc.ru, apljas@math.nsc.ru

Статья поступила 10 июня 2020 г.
После доработки — 22 декабря 2020 г.
Принята к публикации 24 декабря 2020 г.

Литература

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

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

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

[4] Борисова И. А., Кутненко О. А. Цензурирование ошибочно классифицированных объектов выборки // Машин. обучение и анализ данных. 2015. Т. 1, № 11. С. 1632–1641.

[5] Aggarwal C. C. Data mining. Cham: Springer, 2015. 734 p.

[6] Brighton H., Mellish C. Advances in instance selection for instance-based learning algorithms // Data Min. Knowl. Discov. 2002. Vol. 6, No. 2. P. 153–172.

[7] Delany S. J., Segata N., Mac Namee B. Profiling instances in noise reduction // Knowl.-B. Syst. 2012. Vol. 31. P. 28–40.

[8] Frenay B., Verleysen M. Classification in the presence of label noise: A survey // IEEE Trans. Neural Networks and Learning Systems. 2014. Vol. 25, No. 5. P. 845–869.

[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). Heidelberg: Springer, 2004. P. 598–603. (Lect. Notes Comput. Sci.; Vol. 3070).

[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). Heidelberg: Springer, 2007. P. 92–106. (Lect. Notes Comput. Sci.; Vol. 4626).

[11] Quinlan J. R. Induction of decision trees // Mach. Learn. 1986. Vol. 1. P. 81–106.

[12] Segata N., Blanzieri E. Noise reduction for instance-based learning with a local maximal margin approach // J. Intel. Inf. Syst. 2010. Vol. 35, No. 2. P. 301–331.

[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). Pt. 3. Heidelberg: Springer, 2006. P. 590–599. (Lect. Notes Comput. Sci.; Vol. 3982).

[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). Menlo Park, CA: AAAI Press, 2001. P. 269–273.

[15] Wilson D. R., Martinez T. R. Reduction techniques for instance-based learning algorithms // Mach. Learn. 2000. Vol. 38, No. 3. P. 257–286.

[16] Аркадьев А. Г., Браверман Э. М. Обучение машины распознаванию образов. М.: Наука, 1964. 112 с.

[17] Загоруйко Н. Г. Когнитивный анализ данных. Новосибирск: Акад. изд-во ГЕО, 2013, 186 с.

[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). Heidelberg: Springer, 2011. P. 256–270. (Lect. Notes Comput. Sci.; Vol. 6581).

[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. 2008. Vol. 18, No. 1. P. 1–6.

[20] Загоруйко Н. Г., Борисова И. А., Дюбанов В. В., Кутненко О. А. Количественная мера компактности и сходства в конкурентном пространстве // Сиб. журн. индустр. математики. 2010. Т. 13, № 1. С. 59–71.

[21] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с.

[22] Борисова И. А., Кутненко О. А. Исправление диагностических ошибок в целевом признаке с помощью функции конкурентного сходства // Мат. биология и биоинформатика. 2018. Т. 13, № 1. С. 38–49.

[23] Загоруйко Н. Г., Кутненко О. А. Цензурирование обучающей выборки // Вестн. Томского гос. ун-та. Сер. Управление, вычисл. техника и информатика. 2013. № 22. C. 66–73.