Том 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. |