М.Ю. Хачай, Д.М. Хачай, В.С. Панкратов. Неулучшаемая гарантированная оценка точности для задачи о k медианах на отрезке [0,1] ... С. 301-310

УДК: 519.16 + 519.85

MSC: 90C27, 90C05, 62H30

DOI: 10.21538/0134-4889-2017-23-4-301-310

Полная версия статьи

Исследования поддержаны Российским фондом фундаментальных исследований, гранты 16-07-00266 и 17-08-01385.

Одномерная задача кластеризации $k$-medians рассматривается в контексте игры двух лиц с нулевой суммой. Множество стратегий первого игрока совпадает с совокупностью выборок фиксированной длины из отрезка $[0,1]$. Стратегиями второго игрока являются всевозможные разбиения произвольной выборки данной длины на заданное число кластеров. В качестве платежной выступает функция, оценивающая качество кластеризации, значение которой численно совпадает с суммой уклонений элементов выборки от центров ближайших к ним кластеров. Как нетрудно убедиться, за исключением редких случаев данная игра не имеет цены. Для произвольных натуральных $n$ и $k$ строится верхняя оценка $0.5n/(2k-1)$ нижней цены игры. Обосновывается достижимость найденной оценки при $k>1$ и достаточно больших $n=n(k)$. Тем самым показывается, что для произвольной выборки длины $n$ может быть построена кластеризация методом $k$ медиан так, что значение платежной функции не превысит найденной оценки, причем данная оценка достижима при произвольном числе кластеров и выборок достаточно большой длины. Полученные результаты нашли применение в комбинаторной оптимизации при обосновании полиномиальной разрешимости подклассов труднорешаемых экстремальных задач

Ключевые слова: кластеризация, задача о $k$ медианах, достижимая оценка точности.

Список литературы

1.   Aggarwal C.C., Reddy C.K. Data clustering: algorithms and applications. Bosa Roca: Taylor & Francis Inc., 2013. 652 p. (Chapman & Hall/CRC Data Mining and Knowledge Discovery Ser.) ISBN: 9781466558212.

2.   Ben-David S. Computational feasibility of clustering under clusterability assumptions [e-resource]. CoRR abs/1501.00437, 2015. URL: http://arxiv.org/abs/1501.00437.

3.   Duda R.O., Hart P.E., Stork D.G. Pattern classification. N. Y.: Wile, 2001. 680 p. ISBN: 978-0-471-05669-0.

4.   Fast exact $k$-means, $k$-medians and bregman divergence clustering in 1d [e-resource] / A. Gronlund, K.G. Larsen, A. Mathiasen, J.S. Nielsen // CoRR abs/1701.07204, 2017. URL: http://arxiv.org/abs/1701.07204.

5.   Guruswami V., Indyk P. Embeddings and non-approximability of geometric problems // Proc. of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '03). Philadelphia: Society for industrial and applied mathematics, 2003. P. 537-538. ISBN: 0-89871-538-5.

6.   Har-Peled S., Mazumdar S. On coresets for $k$-means and $k$-median clustering // Proc. of the Thirty-Sixth Annual ACM Symposium on Theory of Computing (STOC '04). N. Y.: ACM, 2004. P. 291-300. doi: 10.1145/1007352.1007400.

7.   Khachay M., Neznakhina K. Generalized pyramidal tours for the generalized traveling salesman problem // Lecture Notes in Computer Science. 2017. Vol.10627. P. 265-277. doi: 10.1007/978-3-319-71150-8-23.

8.   Khachay M., Pankratov V., Khachay D. Attainable best guarantee for the accuracy of $k$-medians clustering in [0,1]// 8^th International Conf. Optimization and Applications (OPTIMA2017) / eds. Y.G. Evtushenko, et al. Aachen: CEUR Workshop Proceedings, 2017. P. 322-327.

9.   Kumar A., Sabharwal Y., Sen S. Linear-time approximation schemes for clustering problems in any dimensions // J. ACM. Feb. 2010. Vol. 57(2). P. 5:1-5:32. doi: 10.1145/1667053.1667054.

Поступила 22.09.17

Хачай Михаил Юрьевич 
д-р физ.-мат. наук, проф. РАН, зав. отделом
Инcтитут математики и механики им. Н.Н. Красовского УрО РАН
Уральский федеральный университет, Омский государственный технический университет
e-mail: mkhachay@imm.uran.ru

Хачай Даниил Михайлович
студент, математик
Инcтитут математики и механики им. Н.Н. Красовского УрО РАН
Уральский федеральный университет
e-mail: dmx@imm.uran.ru

Панкратов Василий Сергеевич
аспирант, математик
Инcтитут математики и механики им. Н.Н. Красовского УрО РАН
e-mail: pankratov.vs@gmail.com

English

M.Yu. Khachai, D.M. Khachai, V. S. Pankratov. Attainable best guarantee for the accuracy of $k$-medians clustering in [0,1].

The scalar $k$-medians clustering problem is considered in the context of a two-player zero-sum game. The set of strategies of the first player coincides with a family of fixed-length samples from the interval $[0,1]$. The strategies of the second player are all possible partitions of an arbitrary sample of a given length into a given number of clusters. The quality of the clustering is evaluated by the payoff function equal to the sum of deviations of the elements from the centers of clusters nearest to them. It is easy to see that the game has no value except for rare cases. For arbitrary positive integers $n$ and $k$, we establish an upper bound $0.5n/(2k-1)$ for the lower value of the game and prove its attainability for $k>1$ and sufficiently large $n=n(k)$. Thus, we show that a clustering of an arbitrary sample of length $n$ can be constructed by the $k$ medians method so that the payoff does not exceed the obtained bound, and the bound is attainable for an arbitrary number of clusters and for sufficiently long samples. These results are applicable in combinatorial optimization in the proof of polynomial solvability of subclasses of intractable extremal problems.

Keywords: clustering, $k$-medians problem, attainable accuracy guarantee.

The paper was received by the Editorial Office on September 22, 2017

Mikhail Yur’evich Khachai, Dr. Phys.-Math. Sci., Prof., Krasovskii Institute of Mathematics and
Mechanics, Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620990 Russia; Ural
Federal University, Ekaterinburg, 620002 Russia; Omsk State Technical University, Omsk, 644050
Russia, e-mail: mkhachay@imm.uran.ru .

Daniil Mikhailovich Khachai, graduate student, Krasovskii Institute of Mathematics and Mechanics,
Ural Branch of the Russian Academy of Sciences, Ekaterinburg, 620990 Russia; Institute of Mathematics
and Computer Science, Ural Federal University, Ekaterinburg, 620002 Russia,
e-mail: dmx@imm.uran.ru .

Vasiliy Sergeevich Pankratov, doctoral student, Krasovskii Institute of Mathematics and Mechanics,
Ural Branch of the Russian Academy of Sciences, Ekaterinburg, 620990 Russia,
e-mail: pankratov.vs@gmail.com.