Отправить статью по E-mail NP-трудность квадратичной евклидовой задачи 2-кластеризации 1-Mean и 1-Median с ограничениями на размеры кластеров
- Авторы: Кельманов А.В.1,2, Пяткин А.В.1,2, Хандеев В.И.1,2
-
Учреждения:
- Институт математики имени С.Л. Соболева Сибирского отделения Российской академии наук
- Новосибирский национальный исследовательский государственный университет
- Выпуск: Том 489, № 4 (2019)
- Страницы: 339-343
- Раздел: Математика
- URL: https://journals.eco-vector.com/0869-5652/article/view/18680
- DOI: https://doi.org/10.31857/S0869-56524894339-343
- ID: 18680
Цитировать
Полный текст
Аннотация
В работе рассматривается задача разбиения N-элементного множества точек в d-мерном евклидовом пространстве на два кластера. В этой задаче требуется найти 2-разбиение, минимизирующее сумму (по обоим кластерам) внутрикластерных квадратичных разбросов точек относительно искомых центров. Центр одного кластера определяется как центроид (геометрический центр), а центр другого кластера является искомой точкой во входном множестве. Анализируется вариант задачи, в котором размеры (т.е. мощности) кластеров заданы, а их суммарный размер совпадает с размером входного множества. Доказано, что задача NP-трудна в сильном смысле.
Ключевые слова
Об авторах
А. В. Кельманов
Институт математики имени С.Л. Соболева Сибирского отделения Российской академии наук; Новосибирский национальный исследовательский государственный университет
Автор, ответственный за переписку.
Email: kelm@math.nsc.ru
Россия, 630090, г. Новосибирск, пр-т акад. Коптюга, 4; 630090, г. Новосибирск, ул. Пирогова, 1
А. В. Пяткин
Институт математики имени С.Л. Соболева Сибирского отделения Российской академии наук; Новосибирский национальный исследовательский государственный университет
Email: artempyatkin@gmail.com
Россия, 630090, г. Новосибирск, пр-т акад. Коптюга, 4; 630090, г. Новосибирск, ул. Пирогова, 1
В. И. Хандеев
Институт математики имени С.Л. Соболева Сибирского отделения Российской академии наук; Новосибирский национальный исследовательский государственный университет
Email: khandeev@math.nsc.ru
Россия, 630090, г. Новосибирск, пр-т акад. Коптюга, 4; 630090, г. Новосибирск, ул. Пирогова, 1
Список литературы
- Aloise D., Deshpande A., Hansen P., Popat P. NP Hardness of Euclidean Sum-of-Squares Clustering // Machine Learning. 2009. V. 75. № 2. P. 245-248.
- Kariv O., Hakimi S.L. An Algorithmic Approach to Network Location Problems. Pt. II: The p-Medians // SIAM J. Appl. Math. 1979. V. 37. P. 513-538.
- Гимади Э.Х., Кельманов А.В., Кельманова М.А., Хамидуллин С.А. Апостериорное обнаружение в числовой последовательности квазипериодического фрагмента при заданном числе повторов // Сиб. журн. индустр. математики. 2006. Т. 9. № 1 (25). C. 55-74.
- Gimadi E.Kh., Kel’manov A.V., Kel’manova M.A., Khamidullin S.A. A Posteriori Detecting a Quasiperiodic Fragment in a Numerical Sequence // Pattern Recognition and Image Analysis. 2008. V. 18. № 1. P. 30-42.
- Бабурин А.Е., Гимади Э.Х., Глебов Н.И., Пяткин А.В. Задача отыскания подмножества векторов с максимальным суммарным весом // Дискрет. анализ и исслед. операций. Сер. 2. 2007. Т. 14. № 1. С. 32-42.
- James G., Witten D., Hastie T., Tibshirani R. An Introduction to Statistical Learning. N.Y.: Springer Science+Business Media, LLC, 2013. 426 p.
- Shirkhorshidi A.S., Aghabozorgi S., Wah T.Y., Herawan T. Big Data Clustering: A Review // LNCS. 2014. V. 8583. P. 707-720.
- Bishop C.M. Pattern Recognition and Machine Learning. N.Y.: Springer Science+Business Media, LLC, 2006. 738 p.
- Aggarwal C.C. Data Mining: The Textbook. Springer International Publishing, 2015. 734 p.
- Edwards A.W.F., Cavalli-Sforza L.L. A Method for Cluster Analysis // Biometrics. 1965. V. 21. P. 362-375.
- Garey M.R., Johnson D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: Freeman, 1979. 338 p.
- Papadimitriou C.H. Computational complexity. N.Y.: Addison-Wesley, 1994. 523 p.
Дополнительные файлы
