Все
 
 
 


Рандомизированный алгоритм для задачи двухкластерного разбиения последовательности
 
Код статьиS004446690003560-7-1
DOI10.31857/S004446690003560-7
Тип публикации Статья
Статус публикации Опубликовано
Авторы
Кельманов Александр Васильевич. 
Аффилиация:
Институт математики им. С. Л. Соболева Сибирского отделения РАН
Новосибирский государственный университет
Адрес: Российская Федерация
Хамидуллин С. А.
Аффилиация: Институт математики им. С. Л. Соболева Сибирского отделения РАН
Адрес: Российская Федерация
Хандеев В. И.
Аффилиация: Институт математики им. С. Л. Соболева Сибирского отделения РАН
Адрес: Российская Федерация
Название журналаЖурнал вычислительной математики и математической физики
ВыпускТом 58 Номер 12
Страницы2169-2178
Аннотация

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

Ключевые словаразбиение, последовательность, евклидово пространство, минимум суммы квадратов расстояний, NP-трудность, рандомизированный алгоритм, асимптотическая точность
Источник финансированияРабота выполнена при финансовой поддержке РНФ (проект №16-11-10041).
Получено23.01.2019
Дата публикации23.01.2019
Цитировать   Скачать pdf Для скачивания PDF необходимо авторизоваться
Размещенный ниже текст является ознакомительной версией и может не соответствовать печатной.

всего просмотров: 1155

Оценка читателей: голосов 0 

1. Кельманов А.В., Хамидуллин С.А. Апостериорное обнаружение заданного числа одинаковых подпоследовательностей в квазипериодической последовательности // Журн. вычисл. математики и мат. физики. 2001. Т. 41, 5. С. 807–820.
2. Kel’manov A.V., Jeon B. A Posteriori Joint Detection and Discrimination of Pulses in a Quasiperiodic Pulse Train // IEEE Trans. on Signal Processing. 2004. Vol. 52, 3. P. 645–656.
3. Agol E., Carter J.A., et all. Kepler-36: A Pair of Planets with Neighboring Orbits and Dissimilar Densities //
Science. 2012. Vol. 337. 6094. P. 556–559.
4. Bishop M.C. Pattern Recognition and Machine Learning. New York: Springer Science+Business Media,
LLC, 2006.
5. Кельманов А.В., Хамидуллин С.А. Приближённый полиномиальный алгоритм для одной задачи бикластеризации последовательности // Журн. вычисл. математики и мат. физики. 2015. Т. 55, 6. С. 1076–1085.
6. Tak-chung Fu. A review on time series data mining // Engineering Applications of Artificial Intelligence. 2011. Vol. 24, 1. P. 164–181.
7. Гимади Э.Х., Кельманов А.В., Кельманова М.А., Хамидуллин С.А. Апостериорное обнаружение в числовой последовательности квазипериодического фрагмента при заданном числе повторов // Сиб. журн. индустр. математики. 2006. Т. 9, 1(25). С. 55–74.
8. 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 Recognition and Image Analysis. 2008. Vol. 18, 1. P. 30–42.
9. Кельманов А.В. Проблема off-line обнаружения повторяющегося фрагмента в числовой последовательности // Труды Института математики и механики УрО РАН. 2008. Т. 14, 2. С. 81–88.
10. Кельманов А.В., Пяткин А.В. О сложности некоторых задач поиска подмножеств векторов и кластерного анализа // Журн. вычисл. математики и мат. физики. 2009. Т. 49, 11. С. 2059–2065.
11. Кельманов А.В., Пяткин А.В. О сложности некоторых задач кластерного анализа векторных последовательностей // Дискрет. анализ и исслед. операций. 2013. Т. 20, 2. С. 47–57.
12. Кельманов А.В., Хамидуллин С.А. Приближённый полиномиальный алгоритм для одной задачи разбиения последовательности // Дискрет. анализ и исслед. операций. 2014. Т. 21, 1. С. 53–66.
13. Rajeev Motwani, Prabhakar Raghavan. Randomized аlgorithms. New York: Cambridge University Press,
1995.
14. Кельманов А.В., Хамидуллин С.А., Хандеев В.И. Точный псевдополиномиальный алгоритм для одной
задачи разбиения последовательности // Автоматика и телемеханика. 2017. № 1. С. 80–90. 
15. Кельманов А.В., Хамидуллин С.А., Хандеев В.И. Полностью полиномиальная аппроксимационная схема для одной задачи двухкластерного разбиения последовательности // Дискрет. анализ и исслед.
операций. 2016. Т. 23. № 2. С. 21–40.
16. Кельманов А.В., Хандеев В.И. Полностью полиномиальная аппроксимационная схема для специального случая одной квадратичной евклидовой задачи 2-кластеризации // Ж. вычисл.матем. и матем.
физ. 2016, Т. 56. № 2. С. 332–340.
17. Garey M.R., Johnson D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness. San
Francisco: Freeman, 1979.
18. Кельманов А.В., Хандеев В.И. Рандомизированный алгоритм для одной задачи двухкластерного разбиения множества векторов // Ж. вычисл.матем. и матем. физ. 2015, Т. 55. № 2. С. 335–344.
19. Wirth Н. Algorithms + Data Structures = Programs. New Jersey: Prentice Hall, 1976.

Система Orphus

Загрузка...
Вверх