Существует множество алгоритмов кластеризации, но иерархическая кластеризация широко используется в областях биоинформатики из-за ее концепции. В этом посте я объясню иерархическую кластеризацию.

Иерархическая кластеризация

Есть много способов начать иерархическую кластеризацию. В нашем примере каждая точка данных будет использоваться в качестве начальных кластеров точек. Затем мы сравниваем расстояния между точками данных и объединяем их, когда они являются ближайшими. Это будет повторяться, и каждый кластер будет объединен. 7 и 8 близки друг к другу, а 41 и 5 близки друг к другу. Мы объединяем их. Однако как нам объединить объединенную точку данных?

Тип расстояния (между точками)

Мы можем использовать расстояние Минковского, расстояние p-нормы.

  • p = 2, это будет евклидово расстояние
  • p = 1, это будет манхэттенское расстояние

Это не метрика, но мы можем использовать корреляцию Пирсона.

Тип расстояния (между кластерами)

  • На основе центроида (критерий Уорда)

Мы находим центроид, средние точки каждого кластера и вычисляем расстояние между центроидами. =› создаются сферические кластеры.

  • Одиночная связь

Мы просматриваем все возможные пары и находим пару с минимальным расстоянием. Ближайшее расстояние между кластерами и будет расстоянием между кластерами. Это самый популярный выбор. =› создаются кластеры цепочечной формы.

  • Средняя связь

Мы рассматриваем все возможные пары и вычисляем среднее значение расстояний. Среднее значение будет расстоянием между кластерами. Вначале он образует очень плотные небольшие кластеры.

  • Полная связь

Это противники Single-Linkage. Он находит максимальное расстояние и присваивает ему расстояние между кластерами.

  • На основе радиуса

Сначала мы объединяем кластеры, до которых хотим узнать расстояние, и вычисляем радиус. Чем меньше радиус, тем ближе кластеры. То же самое можно сделать и с диаметром.

Дендрограмму можно изменить, выбрав измерение расстояния. Вы можете выбрать тип расстояния в зависимости от того, какие типы кластеров вы хотите получить.

Как восстановить кластер?

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

Примечания. Дендрограмма означает дерево… а уровни в дереве означают расстояния.

Алгоритм

Сначала мы выбираем, как измерить расстояние между точками данных и критерием связи.

Вход: матрица расстояний

Выход: Иерархическая кластеризация

В примере используется метод полной компоновки. Мы находим A и B имеют минимальное расстояние. Поэтому мы их объединяем. Расстояния между другими точками будут определяться методом полной связи. Следующим будет C и B. Повторяйте это, пока мы не объединим всю матрицу. => n-1 шагов объединения кластеров.

Простая реализация => O (n³), использование очередей с приоритетами => O (n² logn), в одиночной и полной связи вы можете улучшить до O (n²)

Как?

Формула Лэнса и Уильямса

Лэнс и Уильямс изобрели действительно хороший способ расчета критерия связи. Мы можем вычислить критерий связи, просто изменив константу формулы.

Это формула. Это выглядит сложно, но это ничего. Предполагается, что мы объединили A и B с U и хотим рассчитать расстояние между U и C по исходным расстояниям. Константа расскажет вам, что означает эта формула.

Если вы хотите использовать одну связь, то вы выбираете константу выше, 0,5, 0,5, 0, -0,5. Это означает, что вы суммируете минимум и максимум и вычитаете абсолютное значение разницы между минимумом и максимумом, последний шаг умножает на 0,5. Что это значит? Это минимальное значение. Та же логика для полной связи. Теперь мы можем вычислить критерий связи, просто изменив константу.

Пример

Это данные экспрессии генов. Цветовой код показывает уровень экспрессии. Есть дендрограммы образцов и генов.

Преимущества и недостатки

Преимущества

  • Нет предварительно заданного количества кластеров => Пользователь может указать точку отсечки в иерархии. Мы можем использовать порог расстояния.
  • Организует кластеры иерархически с помощью дендрограмм. Дендрограмма не уникальна. Будьте осторожны с этим.
  • Мы можем использовать его с тепловыми картами.

Недостатки

  • долгое время работы, беспорядочная дендрограмма с большими наборами данных.

Это сообщение опубликовано 22 сентября 2020 г.