|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)
Точные алгоритмы поиска кластера наибольшего размера для двух целочисленных задач 2-кластеризации
А. В. Кельмановab, А. В. Панасенкоba, В. И. Хандеевab a Институт математики им. С.Л. Соболева Сибирского отделения Российской академии наук, просп. Акад. Коптюга, 4,
Новосибирск, 630090
b Новосибирский национальный исследовательский государственный университет (НГУ), ул. Пирогова, 2, Новосибирск, 630090
Аннотация:
Рассматриваются две родственные дискретные экстремальные задачи выбора (поиска) подмножества в конечном множестве точек евклидова пространства. Обе задачи индуцируются вариантами фундаментальной проблемы анализа данных — выбором в совокупности объектов подмножества похожих элементов. В обеих задачах требуется в заданном множестве точек найти кластер (подмножество) наибольшей мощности при ограничении на значение квадратичной кластеризационной функции. Совокупность точек входного множества вне искомого кластера соответствует второму (дополняющему) кластеру. В первой задаче кластеризационной функцией (из ограничения) является сумма по обоим кластерам внутрикластерных сумм квадратов расстояний между элементами кластеров и их центрами. Центр одного из кластеров неизвестен и определяется как центроид (геометрический центр), а центр другого фиксирован в заданной точке пространства (без ограничения общности в начале координат). Во второй задаче кластеризационной функцией является сумма по обоим кластерам мощностно-взвешенных внутрикластерных сумм квадратов расстояний между элементами кластеров и их центрами. Как и в первой задаче, центр одного из кластеров неизвестен и определяется как центроид, а центр другого фиксирован в начале координат. В настоящей работе установлено, что обе задачи NP-трудны в сильном смысле. Для вариантов задач, в которых точки входного множества имеют целочисленные координаты, предложены точные алгоритмы. Время работы алгоритмов псевдополиномиально, если размерность пространства ограничена константой.
Ключевые слова:
евклидово пространство, 2-кластеризация, наибольшее подмножество, NP-трудность, целочисленная задача, псевдополиномиальная разрешимость.
Статья поступила: 15.05.2018 Переработанный вариант: 26.06.2018
Образец цитирования:
А. В. Кельманов, А. В. Панасенко, В. И. Хандеев, “Точные алгоритмы поиска кластера наибольшего размера для двух целочисленных задач 2-кластеризации”, Сиб. журн. вычисл. матем., 22:2 (2019), 121–136; Num. Anal. Appl., 12:2 (2019), 105–115
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/sjvm705 https://www.mathnet.ru/rus/sjvm/v22/i2/p121
|
Статистика просмотров: |
Страница аннотации: | 163 | PDF полного текста: | 28 | Список литературы: | 19 | Первая страница: | 11 |
|