А.В. Кельманов, А.В. Пяткин, В.И. Хандеев. О сложности некоторых максиминных задач кластеризации ... C. 189-198

УДК 519.16+519.85

MSC: 68W25, 68Q25

DOI: 10.21538/0134-4889-2018-24-4-189-198

Исследования поддержаны Российским научным фондом, грант 16-11-10041.

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

Ключевые слова: евклидово пространство, кластеризация, максиминная задача, квадратичный разброс, NP-трудность

СПИСОК ЛИТЕРАТУРЫ

1.   An introduction to statistical learning / G. James, D. Witten, T. Hastie, R. Tibshirani. N Y: Springer Science+Business Media, LLC, 2013. 426 p.

2.   Aggarwal C. C. Data mining: The textbook. N Y: Springer International Publishing, 2015. 734 p. doi: 10.1007/978-3-319-14142-8

3.   Bishop C. M. Pattern recognition and machine learning. N Y: Springer Science+Business Media, LLC, 2006. 738 p.

4.   Big data clustering: A review / A. S. Shirkhorshidi, S. Aghabozorgi, T. Y. Wah, T. Herawan // Lecture Notes in Computer Science. 2014. Vol. 8583. P. 707–720. doi: 10.1007/978-3-319-09156-3_49

5.   Alessio Farcomeni, Greco Luca. Robust methods for data reduction. Boca Raton: CRC Press, 2015. 297 p.

6.   Osborne, Jason W. Best practices in data cleaning: A complete quide to everything you need to do before and after collecting your data. Los Angeles: SAGE Publication, Inc., 2013. 296 p.

7.   NP-hardness of Euclidean sum-of-squares clustering / D. Aloise, A. Deshpande, P. Hansen, P. Popat // Machine Learning, 2009. Vol. 75, no. 2. P. 245–248. doi: 10.1007/s10994-009-5103-0

8.   Papadimitriou C. H. Worst-case and probabilistic analysis of a geometric location problem // SIAM J. Comput. 1981. Vol. 10, no. 3. P. 542–557. doi: 10.1137/0210040

9.   Masuyama S., Ibaraki T., Hasegawa T. The computational complexity of the m-center problems in the plane // Trans. IECE Jpn. 1981. Vol. 64, no. 2. P. 57–64.

10.   Hatami B, Zarrabi-Zade H. A streaming algorithm for 2-center with outliers in high dimensions // Computational Geometry. 2017. Vol. 60. P. 26–36. doi: 10.1016/j.comgeo.2016.07.002

11.   Кельманов А. В., Пяткин А. В. NP-трудность некоторых евклидовых задач разбиения конечного множества точек // Журн. вычисл. математики и мат. физики. 2018. Vol. 58, no. 5. C. 852–856. doi: 10.7868/S0044466918050149

12.   Garey M. R., Johnson D. S. Computers and intractability: A quide to the theory of NP-completeness. San Francisco: Freeman, 1979. 338 p.

Поступила 30.07.2018

После доработки 08.10.2018

Принята к публикации 12.11.2018

Кельманов Александр Васильевич
д-р физ.-мат. наук, зав. лабораторией
Институт математики им. С.Л.Соболева СО РАН;
Новосибирский государственный университет,
г. Новосибирск
e-mail: kelm@math.nsc.ru

Пяткин Артем Валерьевич
д-р физ.-мат. наук, зав. лабораторией
Институт математики им. С.Л.Соболева СО РАН;
Новосибирский государственный университет,
г. Новосибирск
e-mail: artem@math.nsc.ru

Хандеев Владимир Ильич
канд. физ.-мат. наук, науч. сотрудник
Институт математики им. С.Л.Соболева СО РАН;
Новосибирский государственный университет,
г. Новосибирск
e-mail: khandeev@math.nsc.ru

English

A.V. Kel’manov, A.V. Pyatkin, V.I. Khandeev. On the complexity of some max–min clustering problems

Two similar problems of searching for a family of disjoint subsets (clusters) in a finite set of points in Euclidean space are considered. In these problems the size of the smallest cluster should be maximized so that in each cluster the intracluster quadratic variation of the points with respect to its center would not exceed a given (constant) fraction of the total quadratic variation of the points of the input set with respect to its centroid. In the first problem the centers of intracluster variations are arbitrary points given at the input. In the second problem the centers of the intracluster variation are unknown (to be found) but they must lie in the input set. It is proved that both problems are NP-hard even on the real line both in the general case when the number of the clusters is a part of the input and in the parametric case when the number of the clusters is fixed.

Keywords: Euclidean space, clustering, max-min problem, quadratic variation, NP-hardness

Received July 30, 2018

Revised October 08, 2018

Accepted November 12, 2018

Funding Agency: This work was supported by the Russian Science Foundation (project no. 16-11-10041).

Alexander Vasil’evich Kel’manov, Dr. Phys.-Math. Sci., Sobolev Institute of Mathematics; Novosibirsk State University, Novosibirsk, 630090 Russia, e-mail: kelm@math.nsc.ru

Artem Valer’evich Pyatkin, Dr. Phys.-Math. Sci., Sobolev Institute of Mathematics; Novosibirsk State University, Novosibirsk, 630090 Russia, e-mail: artem@math.nsc.ru

Vladimir Il’ich Khandeev, Cand. Sci. (Phys.-Math.), Sobolev Institute of Mathematics; Novosibirsk State University, Novosibirsk, 630090 Russia, e-mail: khandeev@math.nsc.ru