Что такое дендрограмма? Всегда ли её можно построить?

Дендрограмма — это диаграмма, показывающая иерархическую связь между объектами. Чаще всего он создается как результат иерархической кластеризации. Основное применение дендрограммы — поиск наилучшего способа распределения объектов по кластерам. 

Ключом к интерпретации дендрограммы является сосредоточение внимания на высоте, на которой любые два объекта соединяются вместе.  

В приведенном выше примере мы видим, что E и F наиболее похожи, так как высота звена, соединяющего их вместе, наименьшая. Следующие два наиболее похожих объекта — это A и B. В приведенной выше дендрограмме высота дендрограммы указывает порядок, в котором кластеры были объединены. Можно создать более информативную дендрограмму, где высоты отражают расстояние между кластерами, как показано ниже.  В этом случае дендрограмма показывает нам,что большая разница между кластерами заключается между кластером A и B и кластером C,D,E и F.

Важно понимать, что дендрограмма представляет собой сводку матрицы расстояний, и, как это бывает с большинством сводок, информация теряется. Например, дендрограмма предполагает, что C и D намного ближе друг к другу, чем C к B, но исходные данные (показанные на диаграмме рассеяния) показывают нам, что это не так.

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

Следствием потери информации является то, что дендрограммы наиболее точны в нижней части, показывая, какие элементы очень похожи.

========================================

Данные для задачи кластеризации могут состоять из точек в евклидовом векторном пространстве или более структурированных объектов, таких как последовательности ДНК (в этом случае задача иерархической кластеризации по сути эквивалентна реконструкции эволюционных деревьев и также известна как «филогенез»). Однако многие алгоритмы кластеризации просто предполагают, что входные данные представлены в виде матрицы расстояний. Расстояния могут определять или не определять метрику; одна популярная модель данных состоит в том, что данные образуют «ультраметрическую» или «архимедову метрику», особый тип метрики, в которой расстояния удовлетворяют «ультраметрическому неравенству треугольника».

dist(a,c) <= max(dist(a,b), dist(b,c))

Это неравенство выполняется, например, если точки данных являются листьями рисунка дендрограммы с расстоянием, определенным как высота их наименьшего общего предка; на самом деле это просто эквивалентный способ определения ультраметрики. Неравенство также выполняется для вершин любого дендрограм графа, длина пути определяется как его ребро с максимальным весом.

Ультраметрическое требование может быть слишком сильным, например. в эволюционных деревьях, если измерять расстояние частотой мутаций, это будет означать биологически нереалистичное условие, что все виды эволюционируют с одинаковой скоростью. Более слабое условие состоит в том, что расстояния формируются длинами путей в дереве, без ультраметрического требования, чтобы все пути корня-листа имели одинаковую длину. Функция расстояния, отвечающая этому более слабому требованию, также известна как аддитивная метрика.

=======================================

Произвольные решения

=======================================

При использовании иерархической кластеризации необходимо указать как метрику расстояния, так и критерии связи. Для таких решений редко существует прочная теоретическая база. 

=======================================

Отсутствуют данные

Большинство программ для иерархической кластеризации не работает, если в данных отсутствуют значения