Строгое полиномиальное отделение двух множеств

Авторы

  • Василий Николаевич Малоземов
  • Артем Владимирович Плоткин

Аннотация

Одной из основных задач математической диагностики является строгое отделение двух конечных множеств в евклидовом пространстве. Широко известно строгое линейное отделение, которое сводится к решению задачи линейного программирования. Мы вводим понятие строгого полиномиального отделения и показываем, что строгое полиномиальное отделение двух множеств также сводится к решению задачи линейного программирования. Целевая функция предложенной в статье задачи линейного программирования имеет следующую особенность: ее оптимальное значение может равняться только нулю или единице - нулю, если множества допускают строгое полиномиальное отделение, и единице в противном случае. Приведены наглядные примеры строгого отделения двух множеств на плоскости с помощью алгебраических полиномов четвертой степени от двух переменных. Анализируется эффективность применения строгого полиномиального отделения при решении задач бинарной классификации данных.

Скачивания

Данные скачивания пока недоступны.

Библиографические ссылки

1. Bennett K.P., Mangasarian O.L. Robust linear programming discrimination of two linearlyinseparable sets // Optimization Methods and Software. 1992. Vol.1. P.23–34.

2. Гавурин М.К., Малоземов В.Н. Экстремальные задачи с линейными ограничениями. Л.:Изд-во ЛГУ, 1984. 176 с.

3. Hastie T., Tibshirani R., Friedman J. H. The Elements of Statistical Learning: Data Mining,Inference, and Prediction. New York: Springer, 2009.

4. Dua D., Karra Taniskidou E. UCIMachine Learning Repository. Irvine, CA:University of California,School of Information and Computer Science.Availableat:http://archive.ics.uci.edu/ml(accessedDecember 20, 2018).

5. Chih-Chung C., Chih-Jen L. LIBSVM: a library for support vector machines // ACM Trans-actions on Intelligent Systems and Technology. 2011. Vol.2(3). P.27:1–27:27. Software available athttp://www.csie.ntu.edu.tw/ cjlin/libsvm (accessed December 20, 2018).

Загрузки

Опубликован

17.08.2020

Как цитировать

Малоземов, В. Н., & Плоткин, А. В. (2020). Строгое полиномиальное отделение двух множеств. Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия, 6(2), 232–240. извлечено от https://math-mech-astr-journal.spbu.ru/article/view/8414

Выпуск

Том 6 № 2 (2019)

Раздел

Математика

Лицензия

Статьи журнала «Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия» находятся в открытом доступе и распространяются в соответствии с условиями Лицензионного Договора с Санкт-Петербургским государственным университетом, который бесплатно предоставляет авторам неограниченное распространение и самостоятельное архивирование.

Наиболее читаемые статьи этого автора (авторов)