[БЕЗ_ЗВУКА] В этом видео мы поговорим про агломеративную иерархическую кластеризацию. Итак, сначала вспомним, что такое вообще иерархическая кластеризация, затем о том, как устроена агломеративная иерархическая кластеризация, о том, как можно вводить расстояние между кластерами, эта тема плавно приведет нас к формуле Ланса-Уильямса. Затем мы обсудим очень удобную визуализацию для иерархической кластеризации, а именно дендрограммы, и после этого рассмотрим некоторые примеры работы метода кластеризации на реальных данных. Итак, иерархическая кластеризация — это кластеризация, в которой кластеры вложены друг в друга. Но в то же время этого можно добиваться двумя разными способами. С одной стороны, можно сначала сказать, что пусть все объекты образуют по кластеру, и будем сливать в дальнейшем эти кластеры и в итоге получим какой-то итоговый результат. А можно подойти к этому по-другому: давайте сначала всё объединим в один большой кластер, этот кластер на каждом шаге будем делить и в итоге получим сколько-то кластеров. Эти подходы называются: агломеративный, когда мы объединяем кластеры, и дивизимный, или дивизионный — по-русски говорят и так, и так, по-английски это будет divisive — тот случай, когда мы делим один большой кластер на кластеры поменьше. Мы будем говорить про агломеративную кластеризацию, и вообще, когда говорят «иерархическая кластеризация», часто имеют в виду именно ее. Поэтому приходится понимать из контекста, что имеется в виду: кластеризация с иерархией кластеров или именно агломеративная. Как устроена агломеративная кластеризация? Ну давайте всё поместим в отдельный кластер, ну то есть каждая точка будет представителем отдельного кластера, причем единственным представителем. Ну почему бы и нет? Между прочим, среднее внутрикластерное расстояние для такой кластеризации будет очень ничего. Затем объединим те точки, которые ближе друг к другу. Теперь мы попадаем в не очень удобную ситуацию: нам нужно объединить какие-то кластеры, но уже не все кластеры представлены одной точкой. Таким образом, нам нужно как-то уметь считать расстояние от кластера, который может состоять из более чем одной точки, до какой-то точки. Ну давайте считать, что мы как-то это расстояние введем и продолжим дальше объединять кластеры. Продолжаем, вот уже какие-то кластеры расширяются, ну и постепенно кластеров становится все меньше, точки попадают в уже существующий кластер, при этом какие-то точки могут долгое время оставаться вне всего этого процесса объединения кластеров. Но потом и они к этому присоединяются, и в какой-то момент мы получаем какое-то небольшое количество кластеров, ну вот, например, в данном случае получилось 3 кластера, и, казалось бы, можно было бы уже здесь закончить. Но нет, нам этого недостаточно, мы продолжим объединять, таким образом, получив два кластера и, наконец, один огромный кластер, в который все попало. Зачем же нужно было продолжать? Главная особенность метода агломеративной иерархической кластеризации в том, что если мы захотим получить другое количество кластеров, нам не нужно будет заново запускать алгоритм. У нас есть все это дерево объединений кластеров, и мы можем остановиться в любой момент. Ну то есть сначала мы вычисляем все дерево, а потом говорим, что хотим его в каком-то месте обрезать. Ну то есть если нам нужно 2 кластера или если нам нужно 3 кластера, мы просто не делаем последние итерации объединения. Теперь о расстоянии между кластерами. Как его можно ввести? Ну, во-первых, можно просто посмотреть на среднее расстояние между объектами из двух кластеров. Можно посмотреть на максимальное расстояние между объектами, можно — на минимальное, можно придумать еще что-нибудь. Оказывается, есть такая формула, называемая формулой Ланса-Уильямса, которая обобщает множество разных способов ввести расстояния между кластерами. Она выражает расстояние между кластером, которым получается в результате слияния двух U и V, и каким-то третьим кластером, кластером S. Как вы видите, формула получается рекурсивной, то есть она определяет расстояние между кластерами через расстояние между кластерами, но при этом через расстояние между более простыми кластерами. То есть, например, если U, V и S — кластеры из одной точки, то с помощью формулы Ланса-Уильямса мы сразу же получаем определение для расстояния между кластером из двух точек и кластером из одной точки. И так далее, можно продолжать рассуждение, увеличивая количество точек в кластерах. Ну и вот оказывается, что достаточно просто рассмотреть сумму нескольких слагаемых, описывающих расстояние от кластера U до кластера S, от кластера V до кластера S, между сливаемыми кластерами U и V и модуль разности расстояний от сливаемого кластера до S. Ну то есть для U и для V. И оказывается, что при разных коэффициентах в этой формуле можно получить разные уже знакомые нам способы вычислять расстояния между кластерами. Ну например, можно получить расстояние ближайшего соседа, то есть минимальное из расстояний между объектами из двух кластеров. Можно получить максимальное из расстояний между точками кластеров. Можно получить среднее расстояние. Можно получить расстояние между центрами кластеров и расстояние Уорда, которое особенно хорошо работает в случае евклидовой метрики. Также есть очень удобный способ визуализировать иерархическую кластеризацию. Давайте снова посмотрим на процесс кластеризации. Изначально у нас кластеров столько же, сколько точек в выборке. Затем мы сливаем какие-то два кластера. Давайте посмотрим на расстояние между этими кластерами. Такое же расстояние мы откладываем на графике, который мы сейчас будем строить, называемом дендрограммой. Затем происходит следующее слияние. Здесь мы снова откладываем такое же расстояние, то есть на изображении, приведенном на слайде, расстояние между кластерами — это просто высота дуги, которой мы соединяем метки кластеров. Ну и давайте продолжать эту процедуру, таким образом выстраивая вот такую вот интересную древовидную структуру, в которой мы также сохранили информацию о том, какое расстояние было между кластерами в момент слияния. [ЗВУК_НАЖАТИЯ_КНОПКИ] Ну вот, теперь можно посмотреть на эту структуру и понять, в какой момент можно всё обрезать, исходя из того, что расстояния между кластерами при слиянии стали уж слишком большие. Но в то же время это еще не очень наглядно, может быть, будет интересно построить график зависимости расстояния между сливаемыми кластерами от номера итерации. Ну и конечно, мы можем отсечь всё в каком-то определенном моменте и получить нужное нам количество кластеров. Рассмотрим графики, полученные на реальных данных в задаче кластеризации писем по теме. На слайде показана дендрограмма, полученная на таком датасете. Если посмотреть на небольшие подвыборки и строить дендрограммы по ним, построить по ним уже упомянутый график зависимости расстояния между сливаемыми кластерами от номера итерации, то мы увидим интересное явление. Смотрите: ближе к последним итерациям расстояние между кластерами быстро взмывает вверх, то есть есть ощущение, что существует некоторое разумное количество кластеров, то есть какое-то количество групп точек, которые друг от друга уже более-менее серьезно удалены. Если мы возьмем выборку побольше, то мы увидим, что график, с одной стороны, стал более гладким, что ожидаемо — итераций у нас стало больше, с другой стороны, и дендрограмма получилась поразнообразнее, и эффект сохранился. Ну и на еще более большой выборке из 10000 писем мы видим, что дендрограмма уже совсем разрослась, а график по-прежнему имеет точку, в которой начинается особенно быстрый рост. Ну, точнее говоря, не точку, а какой-то регион. Ну вот если мы сравним эти три графика, то мы увидим, что, с одной стороны, действительно, с увеличением выборки график получался глаже, но это, в принципе, ожидаемо, а с другой стороны, что любопытно, вот этот вот изгиб на графике возникал при разном расстоянии между сливаемыми кластерами. Чем же это может быть вызвано? С одной стороны, можно подумать: «Ну конечно, у нас больше кластеров, поэтому следующие слияния уже, определенно, при существенно большем расстоянии, нежели первые». Это все, конечно, правда. Но, в каком-то смысле, здесь тогда настораживает, что получается, прошлые изгибы потерялись на графике. Но есть еще другое объяснение. Другое объяснение связано с тем, что мы использовали разные подвыборки, и в этих подвыборках была разная лексика, а в качестве признаков здесь мы использовали частоты слов. Поэтому фактически признаковые пространства здесь разные, количества признаков тоже разные, и поэтому эти расстояния между собой сравнивать некорректно. Было бы это делать корректно, если бы мы сначала получили весь словарь, а потом бы уже делали кластеризацию. Другая интересная особенность иерархической кластеризации в том, что часто возникает какой-то один большой кластер и несколько кластеров маленьких. Это не всегда хорошо, иногда хочется выделить какие-то более-менее похожие по размеру кластеры. Здесь можно начать придумывать какие-нибудь ухищрения. Ну например, можно подумать, что слишком много шума в наших признаках и попробовать понизить размерность. Ну например, сделать SVD, которое мы уже использовали в одном из примеров в прошлом уроке и о котором еще поговорим подробнее в следующих уроках. Ну вот мы видим, что, если понизить размерность с помощью SVD, дендрограмма выглядит вроде бы разнообразнее, хотя это все еще зависит от того, в какой момент отсекать. Если еще больше уменьшить количество компонентов, то кажется, гигантская компонента становится меньше. Но в то же время не стоит забывать анализировать результаты по-разному. Ну, в частности, можно снова построить график, который мы строили ранее, и увидеть, что здесь уже перегиб совершенно пропал, и, возможно, мы уж слишком сильно понизили размерность, и теперь уже явно кластеры не выделяются. Итак, подведем итог. Мы с вами поговорили про иерархическую кластеризацию; о том, как устроена агломеративная кластеризация; как можно вводить расстояния между кластерами, в том числе с помощью формулы Ланса-Уильямса; как можно строить дендрограммы; и обсудили некоторые примеры использования кластеризации на реальных датасетах.
