Том 22, номер 4, 2015 г., Стр. 50–62

УДК 519.16+519.85
Кельманов А. В., Хандеев В. И.
Точный псевдополиномиальный алгоритм для одной задачи двухкластерного разбиения множества векторов 

Аннотация:
Рассматривается евклидова NP-трудная в сильном смысле задача разбиения конечного множества векторов на два кластера заданных размеров по критерию минимума суммы квадратов расстояний от элементов кластеров до их центров. Предполагается, что центр одного из искомых кластеров неизвестен и определяется как среднее значение по всем векторам, образующим этот кластер. Центр другого кластера задан в начале координат. Показано, что в случае фиксированной размерности пространства задача разрешима за полиномиальное время. Для случая фиксированной размерности пространства и целочисленных компонент векторов обоснован точный псевдополиномиальный алгоритм.
Библиогр. 27.

Ключевые слова: разбиение, множество векторов, квадраты евклидовых расстояний, NP-трудность, точный псевдополиномиальный алгоритм.

DOI: 10.17377/daio.2015.22.463

Кельманов Александр Васильевич ^1,2
Хандеев Владимир Ильич ¹
1. Институт математики им. С. Л. Соболева
пр. Коптюга, 4, 630090 Новосибирск, Россия 
2. Новосибирский гос. университет
ул. Пирогова, 2, 630090 Новосибирск, Россия
e-mail: kelm@math.nsc.ru, khandeev@math.nsc.ru

Статья поступила 16 сентября 2014 г.
Исправленный вариант — 22 февраля 2015 г.

Литература

[1] Агеев А. А., Кельманов А. В., Пяткин А. В. Труднорешаемость задачи о разрезе максимального веса в евклидовом пространстве // Докл. АН. 2014. Т. 456, №5. С. 511–513.

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

[3] Галашов А. Е., Кельманов А. В. 2-Приближённый алгоритм для одной задачи поиска семейства непересекающихся подмножеств векторов // Автоматика и телемеханика. 2014. № 4. C. 5–19.

[4] Гимади Э. Х., Глазков Ю. В., Рыков И. А. О двух задачах выбора подмножества векторов с целочисленными координатами в евклидовом пространстве с максимальной нормой суммы размерности // Дискрет. анализ и исслед. операций. 2008. Т. 15, № 4. С. 30–43.

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

[6] Гимади Э. Х., Пяткин А. В., Рыков И. А. О полиномиальной разрешимости некоторых задач выбора подмножеств векторов в евклидовом пространстве фиксированной размерности // Дискрет. анализ и исслед. операций. 2008. Т. 15, № 6. С. 11–19.

[7] Долгушев А. В., Кельманов А. В. К вопросу об алгоритмической сложности одной задачи кластерного анализа // Дискрет. анализ и исслед. операций. 2010. Т. 17, №2. С. 39–45.

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

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

[10] Еремин И. И., Гимади Э. Х., Кельманов А. В., Пяткин А. В., Хачай М. Ю. 2-Приближенный алгоритм поиска клики с минимальным весом вершин и ребер // Тр. Ин-та математики и механики УрО РАН. 2013. Т. 19, №2. С. 134–143.

[11] Кельманов А. В. Проблема off-line обнаружения повторяющегося фрагмента в числовой последовательности // Тр. Ин-та математики и механики УрО РАН. 2008. Т. 14, №2. С. 81–88.

[12] Кельманов А. В. О сложности некоторых задач анализа данных // Журн. вычисл. математики и мат. физики. 2010. Т. 50,№11. С. 2045–2051.

[13] Кельманов А. В. О сложности некоторых задач кластерного анализа // Журн. вычисл. математики и мат. физики. 2011. Т. 51, №11. С. 2106–2112.

[14] Кельманов А. В., Пяткин А. В. О сложности одного из вариантов задачи выбора подмножества «похожих» векторов // Докл. АН. 2008. Т. 421, №5. С. 590–592.

[15] Кельманов А. В., Пяткин А. В. О сложности некоторых задач поиска подмножеств векторов и кластерного анализа //Журн. вычисл. математики и мат. физики. 2009. Т. 49, №11. С. 2059–2067.

[16] Кельманов А. В., Пяткин А. В. О сложности некоторых задач кластерного анализа векторных последовательностей // Дискрет. анализ и исслед. операций. 2013. Т. 20, №2. С. 47–57.

[17] Кельманов А. В., Романченко С. М., Хамидуллин С. А. Точные псевдополиномиальные алгоритмы для некоторых труднорешаемых задач поиска подпоследовательности векторов // Журн. вычисл. математики и мат. физики. 2013. Т. 53, №1. С. 143–153.

[18] Кельманов А. В., Хандеев В. И. Полиномиальный алгоритм с оценкой точности 2 для решения одной задачи кластерного анализа // Дискрет. анализ и исслед. операций. 2013. Т. 20, №4. С. 36–45.

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

[20] Aloise D., Deshpande A., Hansen P., Popat P. NP-hardness of Euclidean sum-of-squares clustering // Mach. Learn. 2009. Vol. 75, No. 2. P. 245–248.

[21] Jain A. K. Data clustering: 50 years beyond K-means // Pattern Recognit. Lett. 2010. Vol. 31, No. 8. P. 651–666.

[22] Garey M. R., Johnson D. S. Computers and intractability: a guide to the theory of NP-completeness. San Francisco, CA: Freeman, 1979. 314 p.

[23] Hansen P., Jaumard B. Cluster analysis and mathematical programming // Math. Program., Ser. A. 1997. Vol. 79. P. 191–215.

[24] Hansen P., Jaumard B., Mladenovich N. Minimum sum of squares clustering in a low dimensional space // J. Classif. 1998. Vol. 15, No. 1. P. 37–55.

[25] Inaba M., Katoh N., Imai H. Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering // Proc. 10th Symp. Comput. Geom. (Stony Brook, NY, June 6–8, 1994). New York: ACM, 1995. P. 332–339.

[26] MacQueen J. B. Some methods for classification and analysis of multivariate observations // Proc. 5th Berkeley Symp. Math. Stat. Probab. Vol. 1. Berkeley, CA: Univ. California Press, 1967. P. 281–297.

[27] Rao M. R. Cluster analysis and mathematical programming // J. Amer. Stat. Assoc. 1971. Vol. 66. P. 622–626.