|
Неулучшаемая гарантированная оценка точности для задачи о $k$ медианах на отрезке $[0,1]$
М. Ю. Хачайabc, Д. М. Хачайab, В. С. Панкратовa a Инcтитут математики и механики им. Н. Н. Красовского УрО РАН
b Уральский федеральный университет
c Омский государственный технический университет
Аннотация:
Одномерная задача кластеризации $k$-medians рассматривается в контексте игры двух лиц с нулевой суммой. Множество стратегий первого игрока совпадает с совокупностью выборок фиксированной длины из отрезка $[0,1]$. Стратегиями второго игрока являются всевозможные разбиения произвольной выборки данной длины на заданное число кластеров. В качестве платежной выступает функция, оценивающая качество кластеризации, значение которой численно совпадает с суммой уклонений элементов выборки от центров ближайших к ним кластеров.
Как нетрудно убедиться, за исключением редких случаев данная игра не имеет цены. Для произвольных натуральных $n$ и $k$ строится верхняя оценка $0.5n/(2k-1)$ нижней цены игры. Обосновывается достижимость найденной оценки при $k>1$ и достаточно больших $n=n(k)$. Тем самым
показывается, что для произвольной выборки длины $n$ может быть построена кластеризация методом $k$ медиан так, что значение платежной функции не превысит найденной оценки, причем данная оценка достижима при произвольном числе кластеров и выборок достаточно большой длины. Полученные результаты нашли применение в комбинаторной оптимизации при обосновании полиномиальной разрешимости подклассов труднорешаемых экстремальных задач.
Ключевые слова:
кластеризация, задача о $k$ медианах, достижимая оценка точности.
Поступила в редакцию: 22.09.2017
Образец цитирования:
М. Ю. Хачай, Д. М. Хачай, В. С. Панкратов, “Неулучшаемая гарантированная оценка точности для задачи о $k$ медианах на отрезке $[0,1]$”, Тр. ИММ УрО РАН, 23, № 4, 2017, 301–310
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/timm1489 https://www.mathnet.ru/rus/timm/v23/i4/p301
|
Статистика просмотров: |
Страница аннотации: | 223 | PDF полного текста: | 46 | Список литературы: | 32 | Первая страница: | 7 |
|