[МУЗЫКА]
[МУЗЫКА] В
некоторых ситуациях мы можем разбить наши
данные на группы на разных уровнях, например, в иерархии.
Как можно понять из названия,
объекты данных группируются в иерархию или в дерево кластеров.
Кластер на каждом уровне создают путем слияния кластеров на следующем
нижнем уровне.
На самом низком уровне у нас каждый кластер содержит одно наблюдение.
На самом высоком уровне существует только один кластер, содержащий все данные.
Кроме того, в некоторых приложениях мы можем полагать,
что данные имеют иерархическую структуру, которую мы можем обнаружить.
Например, иерархическая кластеризация может выявить иерархию для сотрудников
компании, структурированную, например, по зарплате.
Также очень популярным является пример изучения эволюции
группы животных в соответствии с их биологическими особенностями,
чтобы выявить некие эволюционные пути их развития.
Стратегия иерархической кластеризации делится на две основные парадигмы:
агломеративный, то есть подход снизу вверх, и дивизивный – подход сверху вниз.
Основная идея агломерационного метода состоит в том,
что на начальной итерации у нас для n точек существует n кластеров.
То есть в каждом кластера существует ровно одна точка.
Используя меру расстояния,
на каждом шаге метода метод объединяет два ближайших кластера, тем самым уменьшая
количество кластеров и строя последовательно более крупные кластеры.
Процесс продолжается до тех пор, пока не будет получено требуемое
количество кластеров или все точки данных не объединятся в один кластер.
В свою очередь,
дивизивные методы начинают сверху вниз и на каждом уровне рекурсивно разделяют
один из существующихся кластер на том уровне на два новых каких-нибудь кластера.
Раскол выбран для создания двух новых групп с наибольшей разнородностью между
группами.
Рассмотрим пример применения агломерационной иерархической
кластеризации и метода делительной иерархической кластеризации
на наборе данных из пяти объектов.
Первоначально агломерационный метод помещает каждый объект в
свой собственный кластер,
затем кластеры объединяются поэтапно в соответствии с некоторым критерием.
Например, кластеры c1 и c2 могут быть объединены,
если объект в c1 и объект c2 образуют минимальное Евклидово расстояние между
любыми двумя объектами из разных кластеров.
Этот подход с одной связью, поскольку каждый кластер представлен всеми объектами
в этом кластере, а сходство между двумя кластерами измеряется сходством ближайшей
пары данных, принадлежащих разным кластерам.
Процесс объединения кластеров повторяется до тех пор,
пока все объекты не будут объединены в один кластер.
В свою очередь, разделяющий метод идет противоположным образом,
а именно, все объекты используются для формирования одного начального кластера,
кластер разделяется по некоторому принципу, такому как
максимальное Евклидово расстояние между ближайшими соседними объектами в кластере.
Процесс разбиения повторяется до тех пор,
пока в конце концов каждый новый кластер содержит только один объект.
Древовидная структура, называемая дендрограммой,
обычно используется для представления процесса иерархической кластеризации.
Она показывает,
как поэтапно сгруппированы объекты в агломерационном и дивизимном методах.
Справа показана дендрограмма для примера из предыдущего слайда,
где l = 0 показывает пять объектов как одиночные кластеры на уровне 0.
При l = 1 объекты a и b сгруппированы вместе,
чтобы сформировать первый кластер, они остаются вместе на последующих уровнях.
Также мы можем использовать вертикальную ось до отображения шкалы
подобия между кластерами.
Например, сходство двух групп объектов a, b и c, d, e составляет
примерно 0,16, и они объединяются вместе, чтобы сформировать один кластер.
В свою очередь, резко дендрограмма горизонтально на определенной высоте
разбивает данные на непересекающиеся кластеры,
представленные вертикальными линиями, которые пересекают ее.
Эти кластеры могут быть получены путем прекращения процедуры,
когда оптимальная разница между группами превышает некое пороговое значение.
Группы, которые сливаются при больших значениях относительно других значений
слияния подгрупп, являются кандидатами на естественные кластеры.
Агломеративный метод, в основном представляющий собой подход снизу вверх,
включает в себя следующие этапы.
Первый шаг — это нужно выделить каждую точку в собственный кластер.
Таким образом, мы начинаем с n точек и n кластеров,
создаем матрицу расстояний путем вычисления расстояния между всеми
парами кластеров с использованием какой-либо метрики.
На следующем шаге мы находим два кластера,
которые имеют наименьшее расстояние между собой,
удаляем данную пару и объединяем их в новый кластер.
Если остался только один кластер, мы останавливаем данный процесс,
иначе мы вычисляем все расстояния от нового полученного кластера и обновляем
матрицу расстояний после слияния, после чего возвращаемся к шагу 3.
Однако данная реализация также может включать некоторые изменения этих шагов.
В представленном алгоритме агломеративной иерархической кластеризации используется
понятие матрицы расстояний.
Таким образом, вы можете увидеть, сколько необходимо памяти для ее хранения.
Если данная матрица является симметричной,
где за n обозначено количество точек данных.
Пространство, необходимое для хранения кластеров, пропорционально числу
кластеров, поэтому оно равно n − 1, исключая однократный кластер,
следовательно сложность алгоритма по памяти составляет O (n²).
Если говорить о временной сложности данного алгоритма,
то проще говоря, можно сказать следующим образом: мы производим n − 1 итерацию,
просматривая матрицу n на n для наибольшего сходства объектов.
Поэтому данный алгоритм без модификации составит сложность O (n³).
Однако данный алгоритм можно немного оптимизировать,
если мы будем использовать к примеру отсортированный список или
кучу для определения расстояний между объектами.
В таком случае мы повышаем нагрузку на хранение данных,
но в свою очередь, выигрываем во времени обработки данного алгоритма.
Таким образом, общее время обработки этого алгоритма составит n² log n.
Пространственная и временная сложность иерархической кластеризации сильно
ограничивают размер набора данных, которые могут быть обработаны данным методом.
Блеканов Иван Станиславовичдоцент
Севрюков Сергей Юрьевичстарший преподаватель
Просолупов Евгений Викторовичк.ф.-м.н., доцент
Коротков Павел Алексеевичстарший преподаватель
Мишенин Алексей Николаевичстарший преподаватель
Утешев Алексей Юрьевичпрофессор
Вольф Дмитрий Александровичассистент
Малютин Евгений Алексеевичассистент
Камалов Михаил ВалерьевичАспирант
