УДК 519.16+519.85
MSC: 68W25, 68Q25
DOI: 10.21538/0134-4889-2017-23-3-159-170
Полная версия статьи
Работа выполнена при поддержке РНФ (проект 16-11-10041).
Рассматривается одна из труднорешаемых задач разбиения конечного множества точек евклидова пространства на два кластера. Критерием решения является минимум суммы по обоим кластерам взвешенных сумм квадратов внутрикластерных расстояний от элементов кластеров до их центров. Центр одного из кластеров неизвестен и определяется как точка пространства, равная среднему значению элементов этого кластера (т. е. равная центроиду этого кластера). Центр другого кластера фиксирован в начале координат. Весовые множители для обеих внутрикластерных сумм заданы на входе. Предложен алгоритм приближенного решения задачи, основанный на адаптивном сеточном подходе поиска центра оптимального кластера. Показано, что алгоритм является полностью полиномиальной приближенной схемой (FPTAS) в случае фиксированной размерности пространства. В случае, когда размерность пространства не фиксирована, но ограничена медленно растущей функцией от мощности входного множества, алгоритм реализует полиномиальную аппроксимационную схему (PTAS).
Ключевые слова: евклидово пространство, кластеризация, NP-трудность, FPTAS, PTAS.
СПИСОК ЛИТЕРАТУРЫ
1. Кельманов А. В., Романченко С. М. FPTAS для одной задачи поиска подмножества векторов // Дискретный анализ и исследование операций. 2014. Т. 21, № 3. С. 41–52.
2. Кельманов А. В., Хандеев В. И. Полностью полиномиальная аппроксимационная схема для специального случая одной квадратичной евклидовой задачи 2-кластеризации // Журн. вычисл. математики и мат. физики. 2016. Т. 56, № 2. С. 332–340. doi: 10.7868/S0044466916020113 .
3. Kel’manov A. V., Motkova A. V. A fully polynomial-time approximation scheme for a special case of a balanced 2-clustering problem // Proc. Internat. Conf. on Discrete Optimization and Operations Research (DOOR 2016). 2016. P. 182–192. (Lecture Notes Comp. Sci.; vol. 9869.)
doi: 10.1007/978-3-319-44914-2-15.
4. Finding k points with minimum diameter and related problems / A. Aggarwal, H. Imai, N. Katoh, S. Suri // J. Algorithms. 1991. Vol. 12, № 1. P. 38–56. doi: 10.1016/0196-6774(91)90022-Q .
5. Кельманов А. В., Пяткин А. В. NP-полнота некоторых задач выбора подмножества векторов // Дискретный анализ и исследование операций. 2010. Т. 17, № 5. С. 37–45.
6. Шенмайер В. В. Решение некоторых задач поиска подмножества векторов с использованием диаграмм Вороного // Дискретный анализ и исследование операций. 2016. Т. 23, № 4. С. 102–115. doi: 10.17377/daio.2016.23.526 .
7. Кельманов А. В, Романченко С. М. Псевдополиномиальные алгоритмы для некоторых труднорешаемых задач поиска подмножества векторов и кластерного анализа // Автоматика и телемеханика. 2012. № 2. С. 156–162.
8. Кельманов А. В., Романченко С. М. Приближенный алгоритм для решения одной задачи поиска подмножества векторов // Дискретный анализ и исследование операций. 2011. Т. 18, № 1. С. 61–69.
9. Шенмайер В. В. Аппроксимационная схема для одной задачи поиска подмножества векторов // Дискретный анализ и исследование операций. 2012. Т. 19, № 2. С. 92–100.
10. Апостериорное обнаружение в числовой последовательности квазипериодического фрагмента при заданном числе повторов / Э. Х. Гимади, А. В. Кельманов, М. А. Кельманова, С. А. Хамидуллин // Сиб. журн. индустр. математики. 2006. Т. 9, № 1(25). С. 55–74.
11. A posteriori detecting a quasiperiodic fragment in a numerical sequence / E. Kh. Gimadi, A. V. Kel’manov, M. A. Kel’manova, S. A. Khamidullin // Pattern Recognition and Image Analysis. 2008. Vol. 18, № 1. P. 30–42. doi:10.1134/S1054661808010057 .
12. Кельманов А. В., Пяткин А. В. О сложности некоторых задач поиска подмножеств векторов и кластерного анализа // Журн. вычисл. математики и мат. физики. 2009. Т. 49, № 11. С. 2059–2065.
13. Задача отыскания подмножества векторов с максимальным суммарным весом / А. Е. Бабурин, Э. Х. Гимади, Н. И. Глебов, А. В. Пяткин // Дискретный анализ и исследование операций. 2007. Т. 14, № 1. С. 32–42.
14. Гимади Э. Х., Пяткин А. В., Рыков И. А. О полиномиальной разрешимости некоторых задач выбора подмножества векторов в евклидовом пространстве фиксированной размерности // Дискретный анализ и исследование операций. 2008. Т. 15, № 6. С. 11–19.
15. Гимади Э. Х., Глазков Ю. В., Рыков И. А. О двух задачах выбора подмножества векторов с целочисленными координатами в евклидовом пространстве с максимальной нормой суммы // Дискретный анализ и исследование операций. 2008. Т. 15, № 4. С. 30–43.
16. Кельманов А. В., Хандеев В. И. Точный псевдополиномиальный алгоритм для одной задачи двухкластерного разбиения множества векторов // Дискретный анализ и исследование операций. 2015. Т. 22, № 4. С. 50–62. doi: 10.17377/daio.2015.22.463.
17. Долгушев А. В., Кельманов А. В. Приближенный алгоритм решения одной задачи кластерного анализа // Дискретный анализ и исследование операций. 2011. Т. 18, № 2. С. 29–40.
18. Долгушев А. В., Кельманов А. В., Шенмайер В. В. Полиномиальная аппроксимационная схема для одной задачи разбиения конечного множества на два кластера // Тр. Ин-та математики и механики УрО РАН. 2015. Т. 21, № 3. С 100–109.
19. Кельманов А. В., Хандеев В. И. Рандомизированный алгоритм для одной задачи двухкластерного разбиения множества векторов // Журн. вычисл. математики и мат. физики. 2015. Т. 55, № 2. С. 335–344. doi: 10.7868/S0044466915020131.
20. Кельманов А. В., Моткова А. В. Точные псевдополиномиальные алгоритмы для задачи сбалансированной 2-кластеризации // Дискретный анализ и исследование операций. 2016. Т. 23, № 3. С. 21–34. doi: 10.17377/daio.2016.23.520
21. Кельманов А. В., Пяткин А. В. NP-трудность некоторых квадратичных евклидовых задач 2-кластеризации // Докл. РАН. 2015. Т. 464, № 5. С. 535–538. doi: 10.7868/S0869565215290058
22. Кельманов А. В., Пяткин А. В. О сложности некоторых квадратичных евклидовых задач 2-кластеризации // Журн. вычисл. математики и мат. физики. 2016. Т. 56, № 3. С. 498–504. doi: 0.7868/S0044466916030091 .
23. Aggarwal C. C. Data Mining: The Textbook. Cham: Springer International Publishing, 2015. 734 p. ISBN: 978-3319141411 .
24. Bishop C. M. Pattern Recognition and Machine Learning. New York: Springer Science+Business Media, LLC, 2006. 738 p. ISBN: 978-0-387-31073-2 .
25. Hastie T., Tibshirani R., Friedman J. The Elements of statistical learning: Data mining, inference, and prediction. New York: Springer-Verlag, 2009. 763 p. doi: 10.1007/978-0-387-84858-7 .
26. An introduction to statistical learning / G. James, D. Witten, T. Hastie, R. Tibshirani. New York: Springer Science+Business Media, LLC, 2013. 426 p. doi: 10.1007/978-1-4614-7138-7 .
27. Jain A. K. Data clustering: 50 years beyond k-means // Pattern Recognition Lett. 2010. Vol. 31. P. 651–666. doi: 10.1016/j.patrec.2009.09.011 .
28. Wirth N. Algorithms + data structures = programs. New Jersey: Prentice Hall, 1976. 366 p. ISBN: 0130224189 .
29. Ball K. An elementary introduction to modern convex geometry. Flavors of geometry // MSRI Publications / ed. S. Levi. 1997. Vol. 31. P. 1–58. ISBN: 0-521-62048-1 .
Поступила 24.05.2017
Кельманов Александр Васильевич
д-р физ.-мат. наук, зав. лабораторией
Институт математики им. С.Л.Соболева СО РАН,
Новосибирский государственный университет,
г. Новосибирск
e-mail: kelm@math.nsc.ru
Моткова Анна Владимировна
студент
Новосибирский государственный университет
г. Новосибирск,
e-mail: anitamo@mail.ru
Шенмайер Владимир Владимирович
канд. физ.-мат. наук
старший науч. сотрудник
Институт математики им. С.Л.Соболева СО РАН,
г. Новосибирск
e-mail: shenmaier@mail.ru
English
A. V. Kel’manov, A. V. Motkova, V. V. Shenmaier. Approximation scheme for the problem of weighted 2-partitioning with a fixed center of one cluster.
We consider the intractable problem of partitioning a finite set of points in Euclidean space into two clusters with minimum sum over the clusters of weighted sums of squared distances between the elements of the clusters and their centers. The center of one cluster is unknown and is defined as the mean value of its elements (i.e., it is the centroid of the cluster). The center of the other cluster is fixed at the origin. The weight factors for the intracluster sums are given as input. We present an approximation algorithm for this problem, which is based on the adaptive grid approach to finding the center of the optimal cluster. We show that the algorithm implements a fully polynomial-time approximation scheme (FPTAS) in the case of fixed space dimension. If the dimension is not fixed but is bounded by a slowly growing function of the number of input points, the algorithm realizes a polynomial-time approximation scheme (PTAS).
Keywords: Euclidean space, partitioning, NP-hardness, FPTAS, PTAS.
The paper was received by the Editorial Office on May 24, 2017.
Aleksander Vasil’evich Kel’manov, Dr. Phys.-Math. Sci., Sobolev Institute of Mathematics; Novosibirsk State University, Novosibirsk, 630990 Russia, e-mail: kelm@math.nsc.ru.
Anna Vladimirovna Motkova, undergraduate student, Novosibirsk State University, Novosibirsk, 630990 Russia, e-mail: anitamo@mail.ru.
Vladimir Vladimirovich Shenmaier, Cand. Sci. (Phys.-Math.), Sobolev Institute of Mathematics, Novosibirsk, 630990 Russia, e-mail: shenmaier@mail.ru.
