Том 21, номер 1, 2014 г., Стр. 53–66

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

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

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

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

Статья поступила 1 марта 2013 г.
Исправленный вариант — 13 мая 2013 г.

Литература

[1] Кельманов А. В., Пяткин А. В. О сложности некоторых задач поиска подмножеств векторов и кластерного анализа // Журн. вычисл. математики и мат. физики. - 2009. - Т. 49, №11. - С. 2059–2067.
Kel’manov A. V., Pyatkin A. V. Complexity of certain problems of searching for subsets of vectors and cluster analysis // Comput. Math. Math. Physics.  -  2009.  -  Vol. 49, N 11.  -  P. 1966–1971.

[2] Кельманов А. В., Пяткин А. В. О сложности некоторых задач кластерного анализа векторных последовательностей // Дискрет. анализ и исслед. операций. - 2013. - Т. 20, № 2. - С. 47–57.
Kel’manov A. V., Pyatkin A. V. On complexity of some problems of cluster analysis of vector sequences // J. Appl. Industr. Math.  -  2013.  -  Vol. 7, N 3.  -  P. 363–369.

[3] Кельманов А. В., Романченко С. М. Приближённый алгоритм для решения одной задачи поиска подмножества векторов // Дискрет. анализ и исслед. операций. - 2011. - Т. 18, №1. - С. 61–69.
Kel’manov A. V., Romanchenko S. M. An approximation algorithm for solving a problem of search for a vector subset // J. Appl. Industr. Math. - 2012.  -  Vol. 6, N 1. -  P. 90–96.

[4] Кельманов А. В., Хамидуллин С. А. Апостериорное обнаружение заданного числа одинаковых подпоследовательностей в квазипериодической последовательности //Журн. вычисл. математики и мат. физики. - 2001. - Т. 41, №5. - С. 807–820.
Kel’manov A. V., Khamidullin S. A. Posterior detection of a given number of identical subsequences in a quasi-periodic sequence // Comput. Math. Math. Physics. - 2001. - Vol. 41, N 5. - P. 762–774.

[5] Aloise D., Deshpande A., Hansen P., Popat P. NP - hardness of Euclidean sum-of-squares clustering // Les Cahiers du GERAD, G-2008-33. 2008. - 4 p.

[6] Anil K. Jain K. Data clustering: 50 years beyond k-means // Pattern Recognit. Lett. - 2010. - Vol. 31. -  P. 651–666.

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

[8] Hastie T., Tibshirani R., Friedman J. The elements of statistical learning: data mining, inference, and prediction.  -  New York: Springer-Verl., 2001. - 533 p.

[9] 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, N3. - P. 645–656.