А.В. Кельманов, А.В. Пяткин, В.И. Хандеев. Квадратичная евклидова задача 2-кластеризации 1-Mean и 1-Median с ограничением на размеры кластеров: сложность и аппроксимируемость ... С. 69-78

УДК 519.16+519.85

MSC: 68W25, 68Q25

DOI: 10.21538/0134-4889-2019-25-4-69-78

Работа выполнена при финансовой поддержке РФФИ, проекты 19-01-00308 и 18-31-00398, программы ФНИ РАН, проекты 0314-2019-0014, 0314-2019-0015, а также программы Top-5-100 Министерства образования и науки РФ.

Полный текст статьи (Full text)

Статья переведена: ISSN 0081-5438 

Proceedings of the Steklov Institute of Mathematics, 2021, Vol. 313, Suppl. 1, pp. S117–S124. (Abstract)

В работе рассматривается задача кластеризации $N$-элементного множества точек в $d$-мерном евклидовом пространстве на два кластера. В этой задаче требуется найти $2$-разбиение, минимизирующее сумму (по обоим кластерам) внутрикластерных квадратичных разбросов точек относительно искомых центров. Центр одного кластера определяется как центроид (геометрический центр), а центр другого кластера является искомой точкой во входном множестве. Анализируется вариант задачи, в котором размеры (т. е. мощности) кластеров заданы, а их суммарный размер совпадает с размером входного множества. Доказано, что задача NP-трудна в сильном смысле. Установлено, что для нее не существует полностью полиномиальной аппроксимационной схемы, если P$\neq$ NP.

Ключевые слова: евклидово пространство, кластеризация, $2$-разбиение, квадратичный разброс, центр, центроид, медиана, сильная NP-трудность, несуществование полностью полиномиальной приближенной схемы, эффективная сводимость с сохранением точности

СПИСОК ЛИТЕРАТУРЫ

1.   Aloise D., Deshpande A., Hansen P., Popat P. NP-hardness of Euclidean sum-of-squares clustering // Machine Learning. 2009. Vol. 75, no. 2. P. 245–248. doi: 10.1007/s10994-009-5103-0 

2.   Kariv O., Hakimi S.L. An algorithmic approach to network location problems. Pt. II: The p-Medians // SIAM J. Appl. Math. 1979. Vol. 37, no. 3. P. 513–538. doi: 10.1137/0137041 

3.   Гимади Э.Х., Кельманов А.В., Кельманова М.А., Хамидуллин С.А. Апостериорное обнаружение в числовой последовательности квазипериодического фрагмента при заданном числе повторов // Сиб. журн. индустр. математики. 2006. Т. 9, № 1(25). C. 55–74.

4.   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 Anal. 2008. Vol. 18, no. 1. P. 30–42. doi: 10.1134/S1054661808010057 

5.   Бабурин А.Е., Гимади Э.Х., Глебов Н.И., Пяткин А.В. Задача отыскания подмножества векторов с максимальным суммарным весом // Дискретный анализ и исследование операций. Сер. 2. 2007. Т. 14, № 1. С. 32–42.

6.   James G., Witten D., Hastie T., Tibshirani R. An introduction to statistical learning. N Y: Springer, Science+Business Media, LLC, 2013. 426 p.

7.   Bishop C.M. Pattern recognition and machine learning. N Y: Springer, Science+Business Media, LLC, 2006. 738 p.

8.   Shirkhorshidi A.S., Aghabozorgi S, Wah T.Y., Herawan T. Big data clustering: A review // Computational Science and Its Applications (ICCSA 2014): Proc. / eds. B. Murgante et al. 2014. P. 707–720. (Lecture Notes in Computer Science; vol. 8583). doi: 10.1007/978-3-319-09156-3_49 

9.   Aggarwal C.C. Data mining: The Textbook. N Y etc.: Springer, International Publishing, 2015. 734 p.

10.   Edwards A.W.F., Cavalli-Sforza L.L. A method for cluster analysis // Biometrics. 1965. Vol. 21. P. 362–375. doi: 10.2307/2528096 

11.   Garey M.R., Johnson D.S. Computers and intractability: A guide to the theory of NP-completeness. San Francisco: Freeman, 1979. 338 p.

12.   Papadimitriou C.H. Computational complexity. N Y: Addison-Wesley, 1994. 523 p.

13.   Vazirani V.V. Approximation algorithms. Berlin; Heidelberg; N Y: Springer-Verlag, 2001. 380 p.

14.   Долгушев А.В., Кельманов А.В. Приближенный алгоритм решения одной задачи кластерного анализа // Дискретный анализ и исследование операций. 2011. Т. 18, № 2. С. 29–40.

15.   Долгушев А.В., Кельманов А.В., Шенмайер В.В. Приближенная полиномиальная схема для одной задачи кластерного анализа // Интеллектуализация обработки информации: 9-я междунар. конф. (Респ. Черногория, г. Будва, 16–22 сентября 2012 г.): cб. докл. М.: Торус Пресс, 2012. C. 242–244.

16.   Кельманов А.В., Хандеев В.И. Рандомизированный алгоритм для одной задачи двухкластерного разбиения множества векторов // Журн. вычисл. математики и мат. физики. 2015. Т. 55, № 2. С. 335–344.

17.   Kel’manov A.V., Motkova A.V., Shenmaier V.V. An approximation scheme for a weighted two-cluster partition problem // Analysis of Images, Social Networks and Texts - 6th Internat. Conf. (AIST 2017): Revised Selected Papers. 2018. P. 323–333. (Lecture Notes in Computer Science; vol. 10716.) doi: 10.1007/978-3-319-73013-4_30 

Поступила 12.08.2019

После доработки 10.09.2019

Принята к публикации 16.09.2019

Кельманов Александр Васильевич
д-р физ.-мат. наук,
зав. лабораторией
Институт математики им. С.Л.Соболева СО РАН;
Новосибирский государственный университет
г. Новосибирск
e-mail: kelm@math.nsc.ru

Пяткин Артем Валерьевич
д-р физ.-мат. наук,
зав. лабораторией
Институт математики им. С.Л.Соболева СО РАН;
Новосибирский государственный университет
г. Новосибирск
e-mail: artem@math.nsc.ru

Хандеев Владимир Ильич
канд. физ.-мат. наук, науч. сотрудник
Институт математики им. С.Л.Соболева СО РАН;
Новосибирский государственный университет
г. Новосибирск
e-mail: khandeev@math.nsc.ru

Ссылка на статью: А.В. Кельманов, А.В. Пяткин, В.И. Хандеев. Квадратичная евклидова  задача 2-кластеризации 1-Mean и 1-Median с ограничением на размеры кластеров: сложность и  аппроксимируемость // Тр. Ин-та математики и механики УрО РАН. 2019. Т. 25, № 4. С. 69-78.

English

A.V. Kel’manov, A.V. Pyatkin, V.I. Khandeev. Quadratic Euclidean 1-Mean and 1-Median 2-Clustering Problem with constraints on the size of the clusters: Complexity and approximability

We consider the problem of partitioning a set of $N$ points in $d$-dimensional Euclidean space into two clusters minimizing the sum of the squared distances between each element and the center of the cluster to which it belongs. The center of the first cluster is its centroid (the geometric center). The center of the second cluster should be chosen among the points of the input set. We analyze the variant of the problem with given sizes (cardinalities) of the clusters; the sum of the sizes equals the cardinality of the input set. We prove that the problem is strongly NP-hard and there is no fully polynomial-time approximation scheme for its solution.

Keywords: Euclidean space, clustering, 2-partition, quadratic variation, center, centroid, median, strong NP-hardness, nonexistence of FPTAS, approximation-preserving reduction

Received August 12, 2019

Revised September 10, 2019

Accepted September 16, 2019

Funding Agency: This work was supported by the Russian Foundation for Basic Research (project nos. 19-01-00308 and 18-31-00398), by Program I.5.1 for Fundamental Research of the Siberian Branch of the Russian Academy of Sciences (project nos. 0314-2019-0014 and 0314-2019-0015), and by the Ministry of Education and Science of the Russian Federation within the Russian Academic Excellence Project.

Alexander Vasil’evich Kel’manov, Dr. Phys.-Math. Sci., Sobolev Institute of Mathematics; Novosibirsk State University, Novosibirsk, 630990 Russia, e-mail: kelm@math.nsc.ru

Artem Valer’evich Pyatkin, Dr. Phys.-Math. Sci., Sobolev Institute of Mathematics; Novosibirsk State University, Novosibirsk, 630990 Russia, e-mail: artem@math.nsc.ru

Vladimir Il’ich Khandeev, Cand. Sci. (Phys.-Math.), Sobolev Institute of Mathematics; Novosibirsk State University, Novosibirsk, 630990 Russia, e-mail: khandeev@math.nsc.ru

Cite this article as: A.V.Kel’manov, A.V.Pyatkin, V.I.Khandeev. Quadratic Euclidean 1-Mean and 1-Median 2-Clustering Problem with constraints on the size of the clusters: Complexity and approximability, Trudy Instituta Matematiki i Mekhaniki URO RAN, 2019, vol. 25, no. 4, pp. 69–78; Proceedings of the Steklov Institute of Mathematics (Suppl.), 2021, Vol. 313, Suppl. 1, pp. S117–S124.