Кластеризация по максимальному интервалу

Минимальные остовные деревья играют важную роль в одной из базовых фор- мализаций, которая будет описана ниже. Допустим, имеется множество U из n объектов р1, p2, ..., pn.
Для каждой пары р и р, определяется числовое расстояние d(р ,, рj). К функции расстояния предъявляются следующие требования: d(р ,, р) = 0; d(р,Рj) > 0 для разныхр ир, а также d(р ,рj) = d(р, р) (симметричность).

Предположим, объекты из U требуется разделить на k групп для заданного па- раметра k. Термином «k-кластеризация U» обозначается разбиение U на k непустых множеств C1, C2, ..., Ck. «Интервалом k-кластеризации» называется минимальное расстояние между любой парой точек, находящихся в разных кластерах. С учетом того, что точки разных кластеров должны находиться далеко друг от друга, есте- ственной целью является нахождение к-кластеризации с максимально возможным интервалом.

Мы приходим к следующему вопросу. Количество разных к-кластеризаций множества U вычисляется по экспоненциальной формуле; как эффективно найти кластеризацию с максимальным интервалом?

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Кластеризация по максимальному интервалу:

  1. Наличие максимально полной информации о допрашиваемом
  2. 6. Таблица минимальных и максимальных размеров и сроков наказаний по Уголовному кодексу РФ 1996 г.
  3. Очень сложно обосновать
  4. Интервальная шкала
  5. V. 1. 3. Музыкальная шкала.
  6. Статья 763. Срок договора аренды
  7. ПОРОГ ОПЕРАТИВНЫЙ
  8. ВРЕМЯ: ВОСПРИЯТИЕ: НАРУШЕНИЕ
  9. Первое правило - "полдень-полночь".
  10. ИСТИННЫЙ ИСТОЧНИК СЧАСТЬЯ
  11. МЕТОД ШКАЛИРОВАНИЯ
  12. 1. Ищет себе дело по душе или находит в себе мудрость делать дело с душой.
  13. Стратегическая линия сбалансирования
  14. ДИАПАЗОН РАСПРЕДЕЛЕНИЯ
  15. АВТОРИТАРНОСТЬ
  16. АКТИВАЦИЯ: УРОВЕНЬ ОПТИМАЛЬНЫЙ
  17. ПАМЯТЬ КРАТКОВРЕМЕННАЯ: ОБЪЕМ
  18. Сефера: Есть ли на борту нашего корабля другие, посторонние, те, которые не прибыли с Атлантиды с нами?
  19. АКУСТИКА ФИЗИОЛОГИЧЕСКАЯ
  20. ШКАЛА ОЦЕНОК