|
|
Семинар отдела математического программирования
13 октября 2017 г. 12:00–13:00, г. Екатеринбург, Институт математики и механики им. Н. Н. Красовского УрО РАН, ул. Софьи Ковалевской 16,
актовый зал
|
|
|
|
|
|
Достижимая гарантия качества кластеризации методом k-медиан на отрезке [0,1]
М. Ю. Хачайab a Уральский федеральный университет им. первого Президента России Б. Н. Ельцина, г. Екатеринбург
b Институт математики и механики им. Н. Н. Красовского Уральского отделения РАН, г. Екатеринбург
|
Количество просмотров: |
Эта страница: | 230 |
|
Аннотация:
Исследуется одномерная задача кластеризации методом k медиан в контексте антагонистической игры, стратегиями игроков которой являются n-элементная выборка из отрезка [0,1] и разбиение ее на k кластеров, соответственно. Для произвольной выборки длины n и произвольного фиксированного числа k>1, приводится неулучшаемая оценка наилучшего качества кластеризации 0.5n/(2k-1), совпадающая с нижней ценой этой игры.
|
|