НЕУЛУЧШАЕМАЯ ГАРАНТИРОВАННАЯ ОЦЕНКА ТОЧНОСТИ ДЛЯ ЗАДАЧИ О МЕДИАНАХ НА ОТРЕЗКЕ [0,1]

Translated title of the contribution: Attainable best guarantee for the accuracy of k-medians clustering in [0,1]

Mikhail Yur'evich Khachai, D. M. Khachai, Vasiliy Sergeevich Pankratov

Research output: Contribution to journalArticlepeer-review

Abstract

Одномерная задача кластеризации -medians рассматривается в контексте игры двух лиц с нулевой суммой. Множество стратегий первого игрока совпадает с совокупностью выборок фиксированной длины из отрезка . Стратегиями второго игрока являются всевозможные разбиения произвольной выборки данной длины на заданное число кластеров. В качестве платежной выступает функция, оценивающая качество кластеризации, значение которой численно совпадает с суммой уклонений элементов выборки от центров ближайших к ним кластеров. Как нетрудно убедиться, за исключением редких случаев данная игра не имеет цены. Для произвольных натуральных и строится верхняя оценка нижней цены игры. Обосновывается достижимость найденной оценки при и достаточно больших . Тем самым показывается, что для произвольной выборки длины может быть построена кластеризация методом медиан так, что значение платежной функции не превысит найденной оценки, причем данная оценка достижима при произвольном числе кластеров и выборок достаточно большой длины. Полученные результаты нашли применение в комбинаторной оптимизации при обосновании полиномиальной разрешимости подклассов труднорешаемых экстремальных задач
Translated title of the contributionAttainable best guarantee for the accuracy of k-medians clustering in [0,1]
Original languageRussian
Pages (from-to)301-310
Number of pages10
JournalТруды института математики и механики УрО РАН
Volume23
Issue number4
DOIs
Publication statusPublished - 2017

Keywords

  • clustering
  • k-medians problem
  • attainable accuracy guarantee

WoS ResearchAreas Categories

  • Mathematics, Applied

GRNTI

  • 27.00.00 MATHEMATICS

Level of Research Output

  • VAK List

Cite this