Том 18, номер 2, 2011 г., Стр. 29-40
УДК 519.2+621.391
Долгушев А. В., Кельманов А. В.
Приближёный алгоритм решения одной задачи кластерного анализа
Аннотация:
Предложен 2-приближённый алгоритм для труднорешаемой задачи, к которой сводится одна из проблем разбиения множества векторов евклидова пространства на два подмножества (кластера) по критерию минимума суммы квадратов расстояний.
Библиогр. 7.
Ключевые слова: поиск подмножества векторов, кластерный анализ, NP-трудность, эффективный приближённый алгоритм.
Долгушев Алексей Владимирович 2
Кельманов Александр Васильевич 1,2
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2.
Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: dolgushev@math.nsc.ru, kelm@math.nsc.ru
Статья поступила 26 декабря 2010 г.
Исправленный вариант — 18 января 2011 г.
Литература
[1] Бабурин А. Е., Гимади Э. Х., Глебов Н. И., Пяткин А. В. Задача отыскания подмножества векторов с максимальным суммарным весом // Дискрет. анализ и исслед. операций. Сер. 2. — 2007. — Т. 14, № 1. — С. 32–42.
[2] Гимади Э. Х., ГлазковЮ. В., Рыков И. А. О двух задачах выбора подмножества векторов с целочисленными координатами в евклидовом пространстве с максимальной нормой суммой разности // Дискрет. анализ и исслед. операций. — 2008. — Т. 15, № 5. — С. 30–43.
[3] Гимади Э. Х., Кельманов А. В., Кельманова М. А., Хамидуллин С. А. Апостериорное обнаружение в числовой последовательности квазипериодического фрагмента при заданном числе повторов // Сиб. журн. индустр. математики. — 2006. — Т. 9, № 1. — С. 55–74.
[4] Гимади Э. Х., Пяткин А. В., Рыков И. А. О полиномиальной разрешимости некоторых задач выбора подмножества векторов в евклидовом пространстве фиксированной размерности // Дискрет. анализ и исслед. операций. — 2008. — Т. 15, № 6. — С. 11–19.
[5] Кельманов А. В. Проблема off-line обнаружения повторяющегося фрагмента в числовой последовательности // Тр. Ин-та математики и механики УрО РАН. — 2008. — Т. 14, № 2. — С. 81–88.
[6] 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. 1–12.
[7] Wirth Н. Algorithms + data structures = programs. — New Jersey: Prentice Hall, 1976. — 366 p.
|