Точные алгоритмы поиска кластера наибольшего размера для двух целочисленных задач 2-кластеризации
А.В. Кельманов1,2, А.В. Панасенко1,2, В.И. Хандеев1,2
1Институт математики им. С.Л. Соболева Сибирского отделения Российской академии наук, Новосибирск, 630090, Россия
kelm@math.nsc.ru
2Новосибирский национальный исследовательский государственный университет, Новосибирск, 630090, Россия
a.v.panasenko@math.nsc.ru
Ключевые слова: евклидово пространство, 2-кластеризация, наибольшее подмножество, NP-трудность, целочисленная задача, псевдополиномиальная разрешимость, Euclidean space, 2-clustering, largest subset, NP-hardness, exact algorithm, pseudo- polynomial-time solvability
Страницы: 121-136
Аннотация
Рассматриваются две родственные дискретные экстремальные задачи выбора (поиска) подмножества в конечном множестве точек евклидова пространства. Обе задачи индуцируются вариантами фундаментальной проблемы анализа данных - выбором в совокупности объектов подмножества похожих элементов. В обеих задачах требуется в заданном множестве точек найти кластер (подмножество) наибольшей мощности при ограничении на значение квадратичной кластеризационной функции. Совокупность точек входного множества вне искомого кластера соответствует второму (дополняющему) кластеру. В первой задаче кластеризационной функцией (из ограничения) является сумма по обоим кластерам внутрикластерных сумм квадратов расстояний между элементами кластеров и их центрами. Центр одного из кластеров неизвестен и определяется как центроид (геометрический центр), а центр другого фиксирован в заданной точке пространства (без ограничения общности в начале координат). Во второй задаче кластеризационной функцией является сумма по обоим кластерам мощностно-взвешенных внутрикластерных сумм квадратов расстояний между элементами кластеров и их центрами. Как и в первой задаче, центр одного из кластеров неизвестен и определяется как центроид, а центр другого фиксирован в начале координат. В настоящей работе установлено, что обе задачи NP-трудны в сильном смысле. Для вариантов задач, в которых точки входного множества имеют целочисленные координаты, предложены точные алгоритмы. Время работы алгоритмов псевдополиномиально, если размерность пространства ограничена константой.
DOI: 10.15372/SJNM20190201 |
