Том 20, номер 2, 2013 г., Стр. 47-57
УДК 519.2+621.391
Кельманов А. В., Пяткин А. В.
О сложности некоторых задач кластерного анализа векторных последовательностей
Аннотация:
Доказана NP-полнота двух задач кластеризации (разбиения) конечной последовательности векторов евклидова пространства. В оптимизационных вариантах обеих задач требуется разбить элементы последовательности на фиксированное число кластеров по критерию минимума суммы квадратов расстояний от элементов кластеров до их центров. В одной из задач мощности кластеров заданы на входе задачи, а в другой неизвестны (являются оптимизируемыми величинами). За исключением центра одного (специального кластера) центры остальных кластеров определяются как средние значения по всем векторам, образующим эти кластеры. Центр специального кластера полагается равным нулю. При этом разбиение подчинено условию: для всех векторов, не входящих в специальный кластер, разность между номерами последующего и предыдущего векторов, входящих в любой из этих кластеров, ограничена сверху и снизу заданными константами.
Библиогр. 20.
Ключевые слова: кластеризация, последовательность евклидовых векторов, минимум суммы квадратов расстояний, ограничение на номера векторов, алгоритмическая сложность.
Кельманов Александр Васильевич 1
Пяткин Артем Валерьевич 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: kelm@math.nsc.ru, artem@math.nsc.ru
Статья поступила 27 июня 2012 г.
Исправленный вариант — 11 октября 2012 г.
Литература
[1] Гимади Э. Х., Кельманов А. В., Кельманова М. А., Хамидуллин С. А. Апостериорное обнаружение в числовой последовательности квазипериодического фрагмента при заданном числе повторов // Сиб. журн. индустр. математики. - 2006. - Т. 9, №1. - С. 55–74.
[2] Долгушев А. В., Кельманов А. В. К вопросу об алгоритмической сложности одной задачи кластерного анализа // Дискрет. анализ и исслед. операций. - 2010. - Т. 17, №2. - С. 39–45.
[3] Кельманов А. В. Проблема off-line обнаружения повторяющегося фрагмента в числовой последовательности // Тр. Ин-та математики и механики УрО РАН. - 2008. - Т. 14, № 2. - С. 81–88.
[4] Кельманов А. В., Михайлова Л. В. Совместное обнаружение в квазипериодической последовательности заданного числа фрагментов из эталонного набора и ее разбиение на участки, включающие серии одинаковых фрагментов //Журн. вычисл. математики и мат. физики. - 2006. - Т. 46, №1. - С. 172–189.
[5] Кельманов А. В., Михайлова Л. В. Хамидуллин С. А. Об одной задаче поиска упорядоченных наборов фрагментов в числовой последовательности // Дискрет. анализ и исслед. операций. - 2009. - Т. 16, № 4. - С. 31–46.
[6] Кельманов А. В., Пяткин А. В. О сложности одного из вариантов задачи выбора подмножества «похожих» векторов // Докл. РАН. - 2008. - Т. 421, № 5. - С. 590–592.
[7] Кельманов А. В., Пяткин А. В. Об одном варианте задачи выбора подмножества векторов // Дискрет. анализ и исслед. операций. - 2008. - Т. 15, № 5. - С. 20–34.
[8] Кельманов А. В., Пяткин А. В. О сложности некоторых задач поиска подмножеств векторов и кластерного анализа //Журн. вычисл. математики и мат. физики. - 2009. - Т. 49, № 11. - С. 2059–2067.
[9] Кельманов А. В., Хамидуллин С. А. Апостериорное обнаружение заданного числа одинаковых подпоследовательностей в квазипериодической последовательности //Журн. вычисл. математики и мат. физики. - 2001. - Т. 41, № 5. - С. 807–820.
[10] 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.
[11] Aloise D., Hansen P. On the complexity of minimum sum-of-squares clustering // Les Cahiers du GERAD, G-2007-50. - 2007. - 12 p.
[12] Anil K., Jain K. Data clustering: 50 years beyond k-means // Pattern Recognit. Lett. - 2010. - Vol. 31. - P. 651–666.
[13] Edwards A. W. F., Cavalli-Sforza L. L. A method for cluster analysis // Biometrics. - 1965. - Vol. 21. - P. 362–375.
[14] Garey M. R., Johnson D. S. Computers and intractability: a guide to the theory of NP-completeness. - San Francisco: Freeman, 1979. - 314 p.
[15] Inaba M., Katch N., Imai H. Applications of weighted Voronoi diagrams and randomization to variance-based clustering // Proc. 10th Ann. Symp. Comput. Geom. (Stony Brook, New York, June 06–08, 1994). - Stony Brook, New York, NY: ACM Press, 1994. - P. 332–339.
[16] Kel’manov A. V., Jeon B. A posteriori joint detection and discrimination of pulses in a quasiperiodic pulse train // IEEE Trans. Signal Processing. - 2004. - Vol. 52, N 3. - P. 645–656.
[17] Kel’manov A. V., Khamidullin S. A. An algorithm for recognition of a vector alphabet generating a sequence with a quasi-periodic structure // Pattern Recognition Image Anal. - 2010. - Vol. 20, N 4. - P. 451–458.
[18] Mahajan M., Nimbhorkar P., Varadarajan K. The planar k-means problem is NP-hard // Theor. Comput. Sci. - 2012. Vol. 442. - P. 13–21.
[19] MacQueen J. B. Some methods for classification and analysis of multivariate observations // Proc. 5th Berkeley Symp. Math. Statist. Probab. (California, Berkeley, June 21–July 18, 1965; December 27, 1965–January 7, 1966). Vol. 1. - Berkeley, California: University of California Press, 1967. - P. 281–297.
[20] Rao M. Cluster analysis and mathematical programming // J. Amer. Stat. Assoc. - 1971. - Vol. 66. - P. 622–626.
