Отправить статью по E-mail O полиномиальной разрешимости одной квадратичной евклидовой задачи кластеризации в одномерном случае
- Авторы: Кельманов А.В.1,2, Хандеев В.И.1,2
-
Учреждения:
- Институт математики имени С.Л. Соболева Сибирского отделения Российской академии наук
- Новосибирский национальный исследовательский государственный университет
- Выпуск: Том 487, № 2 (2019)
- Страницы: 126-129
- Раздел: Математика
- URL: https://journals.eco-vector.com/0869-5652/article/view/15456
- DOI: https://doi.org/10.31857/S0869-56524872126-129
- ID: 15456
Цитировать
Полный текст
Аннотация
Рассматривается задача разбиения конечного множества точек евклидова пространства на кластеры. В этой задаче требуется минимизировать сумму по всем кластерам внутрикластерных сумм квадратов расстояний от элементов кластеров до их центров. Центры некоторых кластеров заданы на входе, а центры других кластеров определяются как центроиды (геометрические центры). Известно, что в общем случае задача NP‑трудна в сильном смысле. Мы доказываем, что существует точный полиномиальный алгоритм для одномерного случая задачи.
Об авторах
А. В. Кельманов
Институт математики имени С.Л. Соболева Сибирского отделения Российской академии наук; Новосибирский национальный исследовательский государственный университет
Email: kelm@math.nsc.ru
Россия, 630090, г. Новосибирск, пр-т акад. Коптюга, 4; 630090, г. Новосибирск, ул. Пирогова, 1
В. И. Хандеев
Институт математики имени С.Л. Соболева Сибирского отделения Российской академии наук; Новосибирский национальный исследовательский государственный университет
Автор, ответственный за переписку.
Email: khandeev@math.nsc.ru
Россия, 630090, г. Новосибирск, пр-т акад. Коптюга, 4; 630090, г. Новосибирск, ул. Пирогова, 1
Список литературы
- Fisher R.A. Statistical Methods and Scientific Inference. N.Y.: Hafner, 1956.
- MacQueen J.B. Some Methods for Classification and Analysis of Multivariate Observations. In: Proc. 5th Berkeley Symp. on Mathematical Statistics and Probability. Berkeley: Univ. of California Press, 1967. V. 1. P. 281-297.
- Aloise D., Deshpande A., Hansen P., Popat P. NP hardness of Euclidean Sum-of-Squares Clustering // Mach. Learn. 2009. V. 75. № 2. P. 245-248.
- Rao M. Cluster Analysis and Mathematical Programming // J. Amer. Stat. Assoc. 1971. V. 66. P. 622-626.
- Bellman R. Dynamic Programming. Princeton: Prince-ton Univ. Press, 1957.
- Grønlund A., Larsen K.G., Mathiasen A., Nielsen J.S., Schneider S., Song M. Fast Exact k-Means, k-Medians and Bregman Divergence Clustering in 1D. CoRR arXiv:1701.07204 (2017).
- Кельманов А.В., Хамидуллин С.А., Кельманова М.А. Совместное обнаружение и оценивание повторяющегося фрагмента в зашумленной числовой последовательности при заданном числе повторов // Тез. докл. Рос. конф. “Дискретный анализ и исследование операций” (ДАИО-4). Новосибирск: Изд-во ИМ СО РАН, 2004. С. 185.
- Gimadi E.Kh., Kel’manov A.V., Kel’manova M.A., Khamidullin S.A. A Posteriori Detection of a Quasi Periodic Fragment in Numerical Sequences with Given Number of Recurrences // Sib. J. Industrial Math. 2006. V. 9. № 1 (25). P. 55-74.
- 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 Recogn. and Image Anal. 2008. V. 18. № 1. P. 30-42.
- Kel’manov A.V., Khamidullin S.A. Posterior Detection of a Given Number of Identical Subsequences in a Guasi-Periodic Sequence // Comput. Math. Math. Phys. 2001. V. 41. № 5. P. 762-774.
- Kel’manov A.V., Jeon B. A Posteriori Joint Detection and Discrimination of Pulses in a Quasiperiodic Pulse Train // IEEE Trans. Signal Processing. 2004. V. 52. № 3. P. 645-656.
- Carter J.A., Agol E., et al. Kepler 36: A Pair of Planets with Neighboring Orbits and Dissimilar Densities // Science. 2012. V. 337. № 6094. P. 556-559.
- Кельманов А.В., Пяткин И.В. // ДАН. 2009. Т. 471. № 5. С. 590-592.
- Kel’manov A.V., Pyatkin A.V. On a Version of the Problem of Choosing a Vector Subset // J. Appl. Ind. Math. 2009. V. 3. № 4. P. 447-455.
- Kel’manov A. V., Pyatkin A.V. Complexity of Certain Problems of Searching for Subsets of Vectors and Cluster Analysis // Comput. Math. Math. Phys. 2009. V. 49. № 11. P. 1966-1971.
Дополнительные файлы
