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

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

Результат исследований: Вклад в журналСтатья

Аннотация

Одномерная задача кластеризации -medians рассматривается в контексте игры двух лиц с нулевой суммой. Множество стратегий первого игрока совпадает с совокупностью выборок фиксированной длины из отрезка . Стратегиями второго игрока являются всевозможные разбиения произвольной выборки данной длины на заданное число кластеров. В качестве платежной выступает функция, оценивающая качество кластеризации, значение которой численно совпадает с суммой уклонений элементов выборки от центров ближайших к ним кластеров. Как нетрудно убедиться, за исключением редких случаев данная игра не имеет цены. Для произвольных натуральных и строится верхняя оценка нижней цены игры. Обосновывается достижимость найденной оценки при и достаточно больших . Тем самым показывается, что для произвольной выборки длины может быть построена кластеризация методом медиан так, что значение платежной функции не превысит найденной оценки, причем данная оценка достижима при произвольном числе кластеров и выборок достаточно большой длины. Полученные результаты нашли применение в комбинаторной оптимизации при обосновании полиномиальной разрешимости подклассов труднорешаемых экстремальных задач
Переведенное названиеAttainable best guarantee for the accuracy of k-medians clustering in [0,1]
Язык оригиналаРусский
Страницы (с-по)301-310
Число страниц10
ЖурналТруды института математики и механики УрО РАН
Том23
Номер выпуска4
DOI
СостояниеОпубликовано - 2017

Предметные области WoS

  • Математика, Прикладная

ГРНТИ

  • 27.00.00 МАТЕМАТИКА

Уровень публикации

  • Перечень ВАК

Цитировать