Вычислительная сложность задачи выбора типичных представителей в конечном множестве точек метрического пространства

Вычислительная сложность задачи выбора типичных представителей в конечном множестве точек метрического пространства

Борисова И. А.
Дискретный анализ и исследование операций, 32, 1, 5-15 (2025)
Скачать статью

УДК 519.254 
DOI: 10.33048/daio.2025.32.812

Аннотация:

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

Ил. 1, библиогр. 14.

Литература:
  1. Zagoruiko N. G., Borisova I. A., Dyubanov V. V., Kutnenko O. A. Methods of recognition based on the function of rival similarity // Pattern Recognit. Image Anal. 2008. V. 18, No. 1. P. 1–6.
     
  2. Борисова И. А. Вычислительная сложность задачи выбора типичных представителей в 2-разбиении конечного множества точек метрического пространства // Дискрет. анализ и исслед. операций. 2020. Т. 27, № 2. С. 5–16.
     
  3. Кутненко О. А., Плясунов А. В. NP-трудность некоторой задачи цензурирования данных // Дискрет. анализ и исслед. операций. 2021. Т. 28, № 2. С. 60–73.
     
  4. Кутненко О. А. Вычислительная сложность двух задач когнитивного анализа данных // Дискрет. анализ и исслед. операций. 2022. Т. 29, № 1. С. 18–32.
     
  5. Aloise D., Deshpande A., Hansen P., Popat P. NP-hardness of Euclidean sum-of-squares clustering // Machine Learn. 2009. V. 75, No. 2. P. 245–248.
     
  6. Dasgupta S. The hardness of $k$-means clustering. Tech. Rep. CS2007-0890. San Diego, CA: Univ. California, 2008. 6 p.
     
  7. Papadimitriou C. H. Worst-case and probabilistic analysis of a geometric location problem // SIAM J. Comput. 1981. V. 10, No. 3. P. 542–557.
     
  8. Har-Peled S., Mazumdar S. On coresets for $k$-means and $k$-median clustering and their applications // Proc. 36th Annu. ACM Symp. Theory of Computing (Chicago, USA, June 13–16, 2004). New York: ACM, 2004. P. 291– 300.
     
  9. Kaufman L., Rousseeuw P. J. Clustering by means of medoids // Statistical data analysis based on the $L_1$-norm and related methods. Amsterdam: North Holland, 1987. P. 405–416.
     
  10. Кельманов А. В., Пяткин А. В., Хандеев В. И. О сложности некоторых максиминных задач кластеризации // Тр. Ин-та математики и механики. 2018. Т. 24, № 4. C. 189–198.
     
  11. Кельманов А. В., Пяткин А. В. NP-трудность некоторых евклидовых задач разбиения конечного множества точек // Журн. вычисл. математики и мат. физики. 2018. Т. 58, № 5. C. 852–856.
     
  12. Aggarwal H., Imai N., Katoh N., Suri S. Finding $k$ points with minimum diameter and related problems // J. Algorithms. 1991. V. 12, No. 1. P. 38–56.
     
  13. Zukhba A. V. NP-completeness of the problem of prototype selection in the nearest neighbor method // Pattern Recognit. Image Anal. 2010. V. 20, No. 4. P. 484–494.
     
  14. Karp R. M. Reducibility among combinatorial problems // Complexity of computer computations. Proc. Symp. (New York, USA, March 20–22, 1972). New York: Plenum Press, 1972. P. 85–103.

Исследование выполнено при финансовой поддержке Российского фонда фундаментальных исследований (проект № 17–01–00710). Дополнительных грантов на проведение или руководство этим исследованием получено не было.

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

E-mail: biamia@mail.ru

Статья поступила 3 сентября 2024 г.
После доработки — 16 сентября 2024 г.
Принята к публикации 22 сентября 2024 г.

Abstract:

We analyze the complexity of one extremal problem of choosing a subset of $p$ points in a given finite set in a metric space. The chosen subset of points is required to describe given clusters in the best way from the point of view of some geometric criterion. This problem is a formalization of one applied problem from data mining that consists in finding a subset of typical representatives of a dataset based on the rival similarity function of. We prove that the problem under consideration is NP-hard by polynomially reducing the well-known NP-hard 3D-Matching problem to this one. 

Illustr. 1, bibliogr. 14.

References:
  1. N. G. Zagoruiko, I. A. Borisova, V. V. Dyubanov, and O. A. Kutnenko, Methods of recognition based on the function of rival similarity, Pattern Recognit. Image Anal. 18 (1), 1–6 (2008).
     
  2. I. A. Borisova, Computational complexity of the problem of choosing typical representatives in a 2-clustering of a finite set of points in a metric space, Diskretn. Anal. Issled. Oper. 27 (2), 5–16 (2020) [Russian] [J. Appl. Ind. Math. 14 (2), 242–248 (2020)].
     
  3. O. A. Kutnenko and A. V. Plyasunov, NP-hardness of some data cleaning problem, Diskretn. Anal. Issled. Oper. 28 (2), 60–73 (2021) [Russian] [J. Appl. Ind. Math. 15 (2), 285–291 (2021)].
     
  4. O. A. Kutnenko, Computational complexity of two problems of cognitive data analysis, Diskretn. Anal. Issled. Oper. 29 (1), 18–32 (2022) [Russian] [J. Appl. Ind. Math. 16 (1), 89–97 (2022)].
     
  5. D. Aloise, A. Deshpande, P. Hansen, and P. Popat, NP-hardness of Euclidean sum-of-squares clustering, Machine Learn. 75 (2), 245–248 (2009).
     
  6. S. Dasgupta, The hardness of $k$-means clustering, Tech. Rep. CS2007-0890 (Univ. California, San Diego, CA, 2008).
     
  7. C. H. Papadimitriou, Worst-case and probabilistic analysis of a geometric location problem, SIAM J. Comput. 10 (3), 542–557 (1981).
     
  8. S. Har-Peled and S. Mazumdar, On coresets for $k$-means and $k$-median clustering and their applications, in Proc. 36th Annu. ACM Symp. Theory of Computing, Chicago, USA, June 13–16, 2004 (ACM, New York, 2004), pp. 291–300.
     
  9. L. Kaufman and P. J. Rousseeuw, Clustering by means of medoids, in Statistical Data Analysis Based on the $L_1$-Norm and Related Methods (North Holland, Amsterdam, 1987), pp. 405–416.
     
  10. 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) [Russian] [Proc. Steklov Inst. Math. 309 (Suppl. 1), S65–S73 (2020)].
     
  11. A. V. Kel’manov and A. V. Pyatkin, NP-hardness of some Euclidean problems of partitioning a finite set of points, Zh. Vychisl. Mat. Mat. Fiz. 58 (5), 852–856 (2018) [Russian] [Comput. Math. Math. Phys. 58 (5), 822–826 (2018)].
     
  12. H. Aggarwal, N. Imai, N. Katoh, and S. Suri, Finding $k$ points with minimum diameter and related problems, J. Algorithms 12 (1), 38–56 (1991).
     
  13. A. V. Zukhba, NP-completeness of the problem of prototype selection in the nearest neighbor method, Pattern Recognit. Image Anal. 20 (4), 484–494 (2010).
     
  14. R. M. Karp, Reducibility among combinatorial problems, in Complexity of Computer Computations (Proc. Symp., New York, USA, March 20–22, 1972) (Plenum Press, New York, 1972), pp. 85–103.