Том 20, номер 4, 2013 г., Стр. 36-45
УДК 519.2+621.391
Кельманов А. В., Хандеев В. И.
Полиномиальный алгоритм с оценкой точности 2 для решения одной задачи кластерного
анализа
Аннотация:
Предложен 2-приближённый полиномиальный алгоритм для труднорешаемой задачи, к которой сводится одна из проблем разбиения конечного множества векторов евклидова пространства на два подмножества (кластера) по критерию минимума суммы квадратов расстояний от элементов кластеров до их центров. Центром первого кластера является среднее значение векторов в этом кластере, а центром второго — нуль-вектор.
Библиогр. 16.
Ключевые слова: кластерный анализ, поиск подмножества векторов, алгоритмическая сложность, полиномиальный приближённый алгоритм.
Кельманов Александр Васильевич 1,2
Хандеев Владимир Ильич 2
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2.
Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: kelm@math.nsc.ru, vladimir.handeev@gmail.com
Статья поступила 12 июня 2012 г.
Исправленный вариант — 21 октября 2012 г.
Литература
[1] Гимади Э. Х., Кельманов А. В., Кельманова М. А., Хамидуллин С. А. Апостериорное обнаружение в числовой последовательности квазипериодического фрагмента при заданном числе повторов // Сиб. журн. индустр. математики. - 2006. - Т. 9, № 1. - С. 55–74.
[2] Гимади Э. Х., Пяткин А. В., Рыков И. А. О полиномиальной разрешимости некоторых задач выбора подмножества векторов в евклидовом пространстве фиксированной размерности // Дискрет. анализ и исслед. операций. - 2008. - Т. 15, № 6. - С. 11–19.
[3] Долгушев А. В., Кельманов А. В. Приближённый алгоритм решения одной задачи кластерного анализа // Дискрет. анализ и исслед. операций. - 2011. - Т. 18, № 2. - С. 29–40.
[4] Кельманов А. В. Проблема off-line обнаружения повторяющегося фрагмента в числовой последовательности // Тр. Ин-та математики и механики УрО РАН. - 2008. - Т. 14, № 2. - С. 81–88.
[5] Кельманов А. В., Пяткин А. В. О сложности некоторых задач поиска подмножеств векторов и кластерного анализа //Журн. вычисл. математики и мат. физики. - 2009. - Т. 49, № 11. - С. 2059–2067.
[6] Кельманов А. В., Пяткин А. В. О сложности одного из вариантов задачи выбора подмножества «похожих» векторов // Докл. РАН. - 2008. - Т. 421, № 5. - С. 590–592.
[7] Кельманов А. В., Пяткин А. В. Об одном варианте задачи выбора подмножества векторов // Дискрет. анализ и исслед. операций. - 2008. - Т. 15, № 5. - С. 20–34.
[8] 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.
[9] Aloise D., Hansen P. On the complexity of minimum sum-of-squares clustering // Les Cahiers du GERAD, G-2007-50. - 2007. - 12 p.
[10] Anil K., Jain K. Data clustering: 50 years beyond k-means // Pattern Recognit. Lett. - 2010. - Vol. 31. - P. 651–666.
[11] Edwards A. W. F., Cavalli-Sforza L. L. A method for cluster analysis // Biometrics. - 1965. - Vol. 21. - P. 362–375.
[12] Garey M. R., Johnson D. S. Computers and intractability: a guide to the theory of NP-completeness. - San Francisco: Freeman, 1979. - 314 p.
[13] 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, N 3. - P. 645–656.
[14] MacQueen J. B. Some methods for classification and analysis of multivariate observations // Proc. 5th Berkeley Symp. Math. Stat. Probab. Vol. 1. - 1967. - P. 281–297.
[15] Mahajan M., Nimbhorkar P., Varadarajan K. The planar k-means problem is NP-hard // Lect. Notes Comput. Sci. - 2009. - Vol. 5431. - P. 284–285.
[16] Rao M. Cluster analysis and mathematical programming // J. Amer. Stat. Assoc. - 1971. - Vol. 66. - P. 622–626.
