О сложности задачи выбора кластеров большого размера

О сложности задачи выбора кластеров большого размера

Пяткин А. В.
Дискретный анализ и исследование операций, 31, 2, 136–143 (2024)
Скачать статью

УДК 519.8+518.25 
DOI: 10.33048/daio.2024.31.787

Аннотация:

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

Литература:
  1. Berkhin P. A survey of clustering data mining techniques // Grouping multidimensional data: Recent advances in clustering. Heidelberg: Springer, 2006. P. 25–71. DOI: 10.1007/3-540-28349-8_2.
     
  2. Jain A. K., Dubes R. C. Algorithms for clustering data. Englewood Cliffs, NJ: Prentice Hall, 1988. 320 p.
     
  3. Ghoreyshi S., Hosseinkhani J. Developing a clustering model based on $K$-means algorithm in order to creating different policies for policyholders in insurance industry // Int. J. Adv. Comput. Sci. Inf. Technol. 2015. V. 4, No. 2. P. 46–53.
     
  4. Fisher W. D. On grouping for maximum homogeneity // J. Am. Stat. Assoc. 1958. V. 53, No. 284. P. 789–798.
     
  5. MacQueen J. Some methods for classification and analysis of multivariate observations // Proc. 5th Berkeley Symp. Mathematics, Statistics and Probability (Berkeley, USA, June 21 – July 18, 1965; Dec. 27, 1965 – Jan. 7, 1966). V. 1. Berkeley: Univ. Calif. Press, 1967. P. 281–297.
     
  6. Blömer J., Lammersen C., Schmidt M., Sohler C. Theoretical analysis of the $k$-means algorithm — A survey // Algorithm engineering: Selected results and surveys. Cham: Springer, 2016. P. 81–116. (Lect. Notes Comput. Sci.; V. 9220). DOI: 10.1007/978-3-319-49487-6.
     
  7. Aloise D., Deshpande A., Hansen P., Popat P. NP-hardness of Euclidean sum-of-squares clustering // Mach. Learn. 2009. V. 75, No. 2. P. 245–248.
     
  8. Pyatkin A. V., Aloise D., Mladenovic N. NP-hardness of balanced minimum sum-of-squares clustering // Pattern Recognit. Lett. 2017. V. 97. P. 44–45.
     
  9. Bertoni A., Goldwurm M., Lin J., Saccà F. Size constrained distance clustering: Separation properties and some complexity results // Fund. Inform. 2012. V. 115, No. 1. P. 125–139. DOI: 10.3233/FI-2012-620.
     
  10. Кельманов А. В., Пяткин А. В. NP-полнота некоторых задач выбора подмножества векторов // Дискрет. анализ и исслед. операций. 2010. Т. 17, № 5. С. 37–45.
     
  11. Кельманов А. В., Пяткин А. В., Хандеев В. И. О сложности некоторых максиминных задач кластеризации // Тр. Ин-та математики и механики. 2018. Т. 24, № 4. С. 189–198. DOI: 10.21538/ 0134-4889-2018-24-4-189-198.
     
  12. Khandeev V. I., Neshchadim S. M. Constant-factor approximation algorithms for some maximin multi-clustering problems // Mathematical optimization theory and operations research. Proc. 22nd Int. Conf. (Yekaterinburg, Russia, July 2–8, 2023). Cham: Springer, 2023. P. 85–100. (Lect. Notes Comput. Sci.; V. 13930). DOI: 10.1007/978-3-031-35305-5_6.
     
  13. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с.
     
  14. Dailey D. P. Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete // Discrete Math. 1980. V. 30, No. 3. P. 289–293. DOI: 10.1016/0012-365X(80)90236-8.
     
  15. Кельманов А. В., Пяткин А. В. Об одном варианте задачи выбора подмножества векторов // Дискрет. анализ и исслед. операций. 2008. Т. 15, № 5. С. 20–34.

Работа выполнена в рамках государственного задания Институт математики им. С. Л. Соболева СО РАН (проект № FWNF–2022–0019).

Пяткин Артём Валерьевич
  1. Институт математики им. С. Л. Соболева, 
    пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

E-mail: artempyatkin@gmail.com

Статья поступила 8 ноября 2023 г. 
После доработки — 20 ноября 2023 г. 
Принята к публикации 22 декабря 2023 г.

Abstract:

The paper considers the following problem. Given a set of Euclidean vectors, find several clusters with a restriction on the maximum scatter of each cluster so that the size of the minimum cluster would be maximum. Here the scatter is the sum of squared distances from the cluster elements to its centroid. The NP-hardness of this problem is proved in the case where the dimension of the space is a part of the input. 
Bibliogr. 15.

References:
  1. P. Berkhin, A survey of clustering data mining techniques, in Grouping Multidimensional Data: Recent Advances in Clustering (Springer, Heidelberg, 2006), pp. 25–71, DOI: 10.1007/3-540-28349-8_2.
     
  2. A. K. Jain and R. C. Dubes, Algorithms for Clustering Data (Prentice Hall, Englewood Cliffs, NJ, 1988).
     
  3. S. Ghoreyshi and J. Hosseinkhani, Developing a clustering model based on $K$-means algorithm in order to creating different policies for policyholders in insurance industry, Int. J. Adv. Comput. Sci. Inf. Technol. 4 (2), 46–53 (2015).
     
  4. W. D. Fisher, On grouping for maximum homogeneity, J. Am. Stat. Assoc. 53 (284), 789–798 (1958).
     
  5. J. MacQueen, Some methods for classification and analysis of multivariate observations, in Proc. 5th Berkeley Symp. Mathematics, Statistics and Probability, Berkeley, USA, June 21 – July 18, 1965; Dec. 27, 1965 – Jan. 7, 1966, Vol. 1 (Univ. Calif. Press, Berkeley, 1967), pp. 281–297.
     
  6. J. Blömer, C. Lammersen, M. Schmidt, and C. Sohler, Theoretical analysis of the $k$-means algorithm — A survey, in Algorithm Engineering: Selected Results and Surveys (Springer, Cham, 2016), pp. 81–116 (Lect. Notes Comput. Sci., Vol. 9220), DOI: 10.1007/978-3-319-49487-6_3.
     
  7. D. Aloise, A. Deshpande, P. Hansen, and P. Popat, NP-hardness of Euclidean sum-of-squares clustering, Mach. Learn. 75 (2), 245–248 (2009).
     
  8. A. V. Pyatkin, D. Aloise, and N. Mladenovic, NP-hardness of balanced minimum sum-of-squares clustering, Pattern Recognit. Lett. 97, 44–45 (2017).
     
  9. A. Bertoni, M. Goldwurm, J. Lin, and F. Saccà, Size constrained distance clustering: Separation properties and some complexity results, Fund. Inform. 115 (1), 125–139 (2012), DOI: 10.3233/FI-2012-620.
     
  10. A. V. Kel’manov and A. V. Pyatkin, NP-completeness of some problems of choosing a vector subset, Diskretn. Anal. Issled. Oper. 17 (5), 37–45 (2010) [Russian] [J. Appl. Ind. Math. 5 (3), 352–357 (2011)].
     
  11. A. V. Kel’manov, A. V. Pyatkin, and V. I. Khandeev, On the complexity of some max–min clustering problems, Tr. Inst Mat. Mekh. 24 (4), 189–198 (2018), DOI: 10.21538/0134-4889-2018-24-4-189-198 [Russian] [Proc. Steklov Inst. Math. 309 (Suppl. 1), S65–S73 (2020), DOI: 10.1134/ S0081543820040082].
     
  12. V. I. Khandeev and S. M. Neshchadim, Constant-factor approximation algorithms for some maximin multi-clustering problems, in Mathematical Optimization Theory and Operations Research (Proc. 22nd Int. Conf., Yekaterinburg, Russia, July 2–8, 2023) (Springer, Cham, 2023), pp. 85–100 (Lect. Notes Comput. Sci., Vol. 13930), DOI: 10.1007/978-3-031-35305-5_6.
     
  13. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979; Mir, Moscow, 1982 [Russian]).
     
  14. D. P. Dailey, Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete, Discrete Math. 30 (3), 289–293 (1980), DOI: 10. 1016/0012-365X(80)90236-8.
     
  15. A. V. Kel’manov and A. V. Pyatkin, On a version of the problem of choosing a vector subset, Diskretn. Anal. Issled. Oper. 15 (5), 20–34 (2008) [Russian] [J. Appl. Ind. Math. 3 (4), 447–455 (2009)].