Том 23, номер 2, 2016 г., Стр. 21-40

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

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

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

DOI: 10.17377/daio.2016.23.511

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

Статья поступила 15 сентября 2015 г.
Исправленный вариант — 12 января 2016 г.

Литература

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

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

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

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

[5] Долгушев А. В., Кельманов А. В., Шенмайер В. В. Полиномиальная аппроксимационная схема для одной задачи разбиения конечного множества на два кластера // Тр. Ин-та математики и механики УрО РАН. 2015. Т. 21, № 3. С. 100–109.

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

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

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

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

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

[11] Кельманов А. В., Романченко С. М. FPTAS для одной задачи поиска подмножества векторов // Дискрет. анализ и исслед. операций. 2014. Т. 21, № 3. С. 41–52.

[12] Кельманов А. В., Хамидуллин С. А. Апостериорное обнаружение заданного числа одинаковых подпоследовательностей в квазипериодической последовательности // Журн. вычисл. математики и мат. физики. 2001. Т. 41, № 5. С. 807–820.

[13] Кельманов А. В., Хамидуллин С. А. Приближённый полиномиальный алгоритм для одной задачи разбиения последовательности // Дискрет. анализ и исслед. операций. 2014. Т. 21, № 1. С. 53–66.

[14] Кельманов А. В., Хамидуллин С. А. Приближённый полиномиальный алгоритм для одной задачи бикластеризации последовательности // Журн. вычисл. математики и мат. физики. 2015. Т. 55, №6. С. 1076–1085.

[15] Кельманов А. В., Хамидуллин С. А., Хандеев В. И. Точный псевдополиномиальный алгоритм для одной задачи бикластеризации последовательности // Тез. докл. XV Всеросс. конф. «Математическое программирование и приложения» (Екатеринбург, 2–6 марта 2015 г.). Екатеринбург: Ин-т математики и механики УрО РАН, 2015. С. 139–140.

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

[17] Кельманов А. В., Хандеев В. И. Точный псевдополиномиальный алгоритм для одной задачи двухкластерного разбиения множества векторов // Дискрет. анализ и исслед. операций. 2015. Т. 22, № 3. C. 36–48.

[18] Кельманов А. В., Хандеев В. И. Полностью полиномиальная аппроксимационная схема для специального случая одной квадратичной евклидовой задачи 2-кластеризации //Журн. вычисл. математики и мат. физики. 2016. Т. 56, № 2. С. 145–153.

[19] 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.

[20] Bishop M. C. Pattern recognition and machine learning. New York: Springer-Verl., 2006. 738 p.

[21] Carter J. A., Agol E., et al. Kepler-36: a pair of planets with neighboring orbits and dissimilar densities // Science. 2012. Vol. 337, No. 6094. P. 556–559.

[22] Flach P. Machine learning: the art and science of algorithms that make sense of data. New York: Cambridge Univ. Press, 2012. 396 p.

[23] 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 Recognit. Image Anal. 2008. Vol. 18, No. 1. P. 30–42.

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

[25] James G., Witten D., Hastie T., Tibshirani R. An introduction to statistical learning. New York: Springer-Verl., 2013. 426 p.

[26] Kel’manov A. V., Jeon B. A posteriori joint detection and discrimination of pulses in a quasiperiodic pulse train // IEEE Trans. Signal Process. 2004. Vol. 52, No. 3. P. 645–656.

[27] Steger C., Ulrich M., Wiedemann C. Machine vision algorithms and applications. Berlin: Wiley-VCH, 2007. 380 p.