Разработка алгоритма

Чтобы найти кластеризацию с максимальным интервалом, мы рассмотрим проце- дуру расширения графа с множеством вершин U. Компоненты связности соответ- ствуют кластерам, и мы постараемся как можно быстрее объединить близлежащие точки в один кластер (чтобы они не оказались в разных кластерах, находящихся поблизости друг от друга).
Начнем с создания ребра между ближайшей парой точек; затем создается ребро между парой точек со следующей ближайшей парой и т. д. Далее мы продолжаем добавлять ребра между парами точек в порядке уве- личения расстояния d(p , pj).

Таким образом граф H с вершинами U наращивает ребро за ребром, при этом компоненты связности соответствуют кластерам. Учтите, что нас интересуют только компоненты связности графа H, а не полное множество ребер; если при добавлении ребра (p., pj) выяснится, чтоp . иp уже принадлежат одному кластеру, ребро добавляться не будет — это не нужно, потому что ребро не изменит мно- жество компонент. При таком подходе в процессе расширения графа никогда не образуется цикл, так что H будет объединением деревьев. Добавление ребра, концы которого принадлежат двум разным компонентам, фактически означает слияние двух соответствующих кластеров. В литературе по кластеризации по- добный итеративный процесс слияния кластеров называется методом одиночной связи — частным случаем иерархической агломератной кластеризации. (Под «агломератностью» здесь понимается процесс объединения кластеров, а под «одиночной связью» — то, что для объединения кластеров достаточно одной связи.) На рис. 4.14 изображен пример для к = 3 кластеров с разбиением точек на естественные группы.

Какое отношение все это имеет к минимальным остовным деревьям? Очень простое: хотя процедура расширения графа базировалась на идее слияния кла- стеров, она в точности соответствует алгоритму минимального остовного де- рева Крускала. Делается в точности то, что алгоритм Крускала сделал бы для графа G, если бы между каждой парой узлов (p., pj) существовало ребро стои- мостью d(p., pj). Единственное отличие заключается в том, что мы стремимся выполнить к-кластеризацию, поэтому процедура останавливается при получении к компонент связности.

Другими словами, выполняется алгоритм Крускала, но он останавливается перед добавлением последних к - 1 ребер. Происходящее эквивалентно построе- нию полного минимального остовного дерева T (в том виде, в каком оно было бы построено алгоритмом Крускала), удалению к - 1 ребер с наибольшей стоимостью (которое наш алгоритм вообще не добавлял) и определению к-кластеризации по


полученным компонентам связности C1, C2,..., Ck. Итак, итеративное слияние кла- стеров эквивалентно вычислению минимального остовного дерева с удалением самых «дорогостоящих» ребер.

Рис. 4.14. Пример кластеризации методом одиночной связи с k = 3 кластерами. Кластеры образуются добавлением ребер между точками в порядке увеличения расстояния

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

Еще по теме Разработка алгоритма:

  1. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  2. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  3. АЛГОРИТМ
  4. АЛГОРИТМ УДАЧИ
  5. Алгоритм исцеления:
  6. Алгоритм избавления от боли
  7. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  8. Алгоритм обработки результатов.
  9. 2. Специфика и алгоритмы работы с источниками.
  10. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  11. Э. ТАНЕНБАУМ, А. ВУДХАЛЛ. ОПЕРАЦИОННЫЕ СИСТЕМЫ Разработка и реализация 3-е издание, 2007
  12. Разработка Плана
  13. 2.7. Разработка анкеты
  14. 6. Разработка перспектив
  15. Разработка и принятие Основного закона
  16. Состояние научной разработки проблемы.
  17. Правило разработки веера версий
  18. Правило разработки графических схем