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 journalArticleResearchpeer-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

@article{c362affa6ddc4dd7b2fda67dccd19db1,
title = "НЕУЛУЧШАЕМАЯ ГАРАНТИРОВАННАЯ ОЦЕНКА ТОЧНОСТИ ДЛЯ ЗАДАЧИ О МЕДИАНАХ НА ОТРЕЗКЕ [0,1]",
abstract = "Одномерная задача кластеризации -medians рассматривается в контексте игры двух лиц с нулевой суммой. Множество стратегий первого игрока совпадает с совокупностью выборок фиксированной длины из отрезка . Стратегиями второго игрока являются всевозможные разбиения произвольной выборки данной длины на заданное число кластеров. В качестве платежной выступает функция, оценивающая качество кластеризации, значение которой численно совпадает с суммой уклонений элементов выборки от центров ближайших к ним кластеров. Как нетрудно убедиться, за исключением редких случаев данная игра не имеет цены. Для произвольных натуральных и строится верхняя оценка нижней цены игры. Обосновывается достижимость найденной оценки при и достаточно больших . Тем самым показывается, что для произвольной выборки длины может быть построена кластеризация методом медиан так, что значение платежной функции не превысит найденной оценки, причем данная оценка достижима при произвольном числе кластеров и выборок достаточно большой длины. Полученные результаты нашли применение в комбинаторной оптимизации при обосновании полиномиальной разрешимости подклассов труднорешаемых экстремальных задач",
keywords = "clustering, k-medians problem, attainable accuracy guarantee",
author = "Khachai, {Mikhail Yur'evich} and Khachai, {D. M.} and Pankratov, {Vasiliy Sergeevich}",
year = "2017",
doi = "10.21538/0134-4889-2017-23-4-301-310",
language = "Русский",
volume = "23",
pages = "301--310",
journal = "Труды института математики и механики УрО РАН",
issn = "0134-4889",
publisher = "Институт математики и механики им. Н.Н. Красовского УрО РАН",
number = "4",

}

TY - JOUR

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

AU - Khachai, Mikhail Yur'evich

AU - Khachai, D. M.

AU - Pankratov, Vasiliy Sergeevich

PY - 2017

Y1 - 2017

N2 - Одномерная задача кластеризации -medians рассматривается в контексте игры двух лиц с нулевой суммой. Множество стратегий первого игрока совпадает с совокупностью выборок фиксированной длины из отрезка . Стратегиями второго игрока являются всевозможные разбиения произвольной выборки данной длины на заданное число кластеров. В качестве платежной выступает функция, оценивающая качество кластеризации, значение которой численно совпадает с суммой уклонений элементов выборки от центров ближайших к ним кластеров. Как нетрудно убедиться, за исключением редких случаев данная игра не имеет цены. Для произвольных натуральных и строится верхняя оценка нижней цены игры. Обосновывается достижимость найденной оценки при и достаточно больших . Тем самым показывается, что для произвольной выборки длины может быть построена кластеризация методом медиан так, что значение платежной функции не превысит найденной оценки, причем данная оценка достижима при произвольном числе кластеров и выборок достаточно большой длины. Полученные результаты нашли применение в комбинаторной оптимизации при обосновании полиномиальной разрешимости подклассов труднорешаемых экстремальных задач

AB - Одномерная задача кластеризации -medians рассматривается в контексте игры двух лиц с нулевой суммой. Множество стратегий первого игрока совпадает с совокупностью выборок фиксированной длины из отрезка . Стратегиями второго игрока являются всевозможные разбиения произвольной выборки данной длины на заданное число кластеров. В качестве платежной выступает функция, оценивающая качество кластеризации, значение которой численно совпадает с суммой уклонений элементов выборки от центров ближайших к ним кластеров. Как нетрудно убедиться, за исключением редких случаев данная игра не имеет цены. Для произвольных натуральных и строится верхняя оценка нижней цены игры. Обосновывается достижимость найденной оценки при и достаточно больших . Тем самым показывается, что для произвольной выборки длины может быть построена кластеризация методом медиан так, что значение платежной функции не превысит найденной оценки, причем данная оценка достижима при произвольном числе кластеров и выборок достаточно большой длины. Полученные результаты нашли применение в комбинаторной оптимизации при обосновании полиномиальной разрешимости подклассов труднорешаемых экстремальных задач

KW - clustering

KW - k-medians problem

KW - attainable accuracy guarantee

UR - https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=tsmetrics&SrcApp=tsm_test&DestApp=WOS_CPL&DestLinkType=FullRecord&KeyUT=000453521700028

UR - https://elibrary.ru/item.asp?id=30713983&

U2 - 10.21538/0134-4889-2017-23-4-301-310

DO - 10.21538/0134-4889-2017-23-4-301-310

M3 - Статья

VL - 23

SP - 301

EP - 310

JO - Труды института математики и механики УрО РАН

JF - Труды института математики и механики УрО РАН

SN - 0134-4889

IS - 4

ER -