0:00
[ТИШИНА] Должно быть, вы уже думаете, ну, сколько можно обсуждать задачу,
давайте обсудим хоть какой-нибудь алгоритм, который ее решает.
В этом видео именно этим мы и займемся.
Мы рассмотрим сразу несколько алгоритмов, конечно, достаточно обзорно,
и увидим, как по-разному можно решать задачу кластеризации.
Конечно, впоследствии мы поговорим об этих алгоритмах подробнее.
Итак, мы уже знаем, что кластеры могут выглядеть совершенно по-разному.
И универсального метода кластеризации, как следствие, мы не придумаем.
При этом, разные методы тоже работают по-разному.
Например, сейчас на слайде показаны результаты работы двух разных
методов кластеризации, метода k средних и ЕМ-алгоритма,
на модельном дата-сете Mouse dataset.
Как вы видите, результаты действительно существенно отличаются.
Ну, давайте начнем с простого метода, с метода k средних.
Предполагается, что мы откуда-то знаем, сколько хотим сделать кластеров.
Это и есть константа k,
и изначально мы выбираем k случайных точек в качестве центров кластеров.
После этого мы распределяем точки выборки по этим центрам,
в зависимости от того, к какому центру точка ближе.
Таким образом, мы получаем некоторое первое разбиение на кластеры.
Но, наверняка, оно будет не очень хорошо.
Поэтому мы можем взять и пересчитать центры просто
как среднее арифметическое точек, попавших в один кластер.
Пересчитав центры, мы можем увидеть, что теперь можем распределить точки заново,
снова смотря на расстояние до центров.
Мы можем продолжать этот алгоритм до тех пор,
пока он не сойдется к какому-то довольно неплохому на вид решению.
Этот алгоритм можно модифицировать, для того чтобы подбирать количество кластеров.
Так можно придумать алгоритм Bisect k Means, который заключается в том,
чтобы на каждом шаге делать 2 means, ну, то есть k means с k равным 2.
После того, как мы сделали 2 means, мы смотрим на каждый
получившийся кластер и запускаем 2 means в нем, если кластер все еще нужно дробить.
Более сложный метод как раз тот,
который лучше всего справлялся с задачей кластеризации на модельном dataset,
показанном в начале видео, это EM-алгоритм.
EM-алгоритм исходит из предположения, что у каждого кластера есть какая-то своя
плотность, pj (x), из какого-то семейства, например, из нормального.
И мы смотрим на плотность всех точек как на взвешенную сумму плотностей кластеров.
Дальше мы последовательно повторяем E- и M-шаг.
На E-шаге мы оцениваем некоторые вспомогательные переменные,
зафиксировав которые, удобней максимизировать правдоподобие.
А на M-шаге мы выполняем некоторые действия,
чтобы оценить те переменные, которые нам нужно знать,
то есть веса разных компонент pj и параметры распределения этих компонент.
По сути, мы решаем задачу разделения смеси распределений.
То есть мы считаем, что у нас есть смесь, ну, то есть взвешенная сумма плотностей,
и нам нужно оценить веса и оценить параметры отдельных компонентов.
Эту задачу можно было бы попробовать решать в лоб, просто выписав правдоподобие
и подбирая параметры таким образом, чтобы правдоподобие было максимальным.
Но оказывается, что это не очень удобно, и, если попытаться аналитически
выписать решения этой задачи, скорее всего вы потерпите неудачу.
А вот с помощью EM-алгоритма, повторяя E- и M-шаг,
можно справиться довольно неплохо.
Для примера рассмотрим простой иллюстративный случай,
когда мы сгенерировали две компоненты из нормальных распределений на плоскости.
Вот вы видите на слайде два сгустка, их можно проинтерпретировать как кластеры.
И вот, что получается, если применить к этой выборке EM-алгоритм.
Обратите внимание, так как мы предположили, что плотности нормальные,
можно выписать EM-алгоритм более точно, то есть на M-шаге, там,
где у нас решалась задача максимизации некоторой функции,
можно выписать явные аналитические решения.
Ну, если все эти формулы немножко ввергли вас в уныние, не расстраивайтесь,
есть и более простые методы кластеризации, а о EM-алгоритме мы еще поговорим позднее.
Например, есть методы, основанные на плотности точек.
В основном они используют следующую идею.
Давайте смотреть на окрестность точки, и, если в окрестности точки
много других точек, будем считать, что это основная точка из внутренности кластера.
Если в окрестности точки мало других точек, но есть уже какая-то другая
основная точка, то будем называть эти точки пограничными,
если же в окрестности точки вообще мало чего есть, эти точки будут шумовыми.
Один из density-based методов, то есть методов,
основанных на плотности точек, это DBSCAN.
Он устроен следующим образом.
Сначала мы помечаем все точки как основные, пограничные, шумовые,
затем мы отбрасываем из рассмотрения шумовые точки,
соединяем все основные точки, находящиеся на малом расстоянии друг от друга,
дальше объединяем каждую группу соединенных основных точек в отдельный
кластер и назначаем пограничную точку к тому кластеру,
который больше представлен в ее окрестности основными точками.
Можно придумать и другой подход к кластеризации, так называемую
иерархическую кластеризацию, которая устроена следующим образом.
Изначально будем считать, что кластеров у нас по числу объектов выборки,
каждый объект это кластер из одного элемента.
Дальше мы введем некоторое расстояние на кластерах и на каждом шаге
будем объединять те кластеры, расстояние между которыми самое маленькое.
Таким образом мы можем изобразить все эти
объединения кластеров и получить дерево, вершины в котором являются кластерами.
Это дерево можно обрезать на разной глубине, получая разное количество
кластеров, не перезапуская алгоритм кластеризации заново,
как это потребовалось бы в случае, если бы мы делали, ну, например, k means.
Можно заметить, что это все напоминает ситуацию из биологии,
когда мы пытаемся систематизировать виды и понять,
как они произошли, и в какие группы они объединяются.
Иерархические методы кластеризации позволяют строить
довольно удобную визуализацию их работы, так называемые дендрограммы.
Дендрограммы выглядят следующим образом.
На одной оси отмечены точки, соответствующие объектам выборки,
на другой оси мы откладываем расстояние между кластерами в момент слияния.
Так, можно посмотреть, как это расстояние меняется
в разных по счету слияниях, и выбрать то самое место,
где мы начнем уже отсекать дендрограмму и решать,
что вот, наши отдельные кластеры, которые мы будем выделять.
Ну, то есть понимать, после какого слияния нам уже сливать кластеры неинтересно.
Расстояние между кластерами можно вводить по-разному.
Можно посчитать среднее расстояния между объектами кластеров,
можно посчитать максимальное расстояние,
можно минимальное, можно придумать еще много разных методов.
Разные методы будут приводить к разным результатам,
которые могут вас в разной степени устраивать.
Теперь, когда мы уже знаем, что задачи кластеризации
бывают разными, из прошлого видео, и из этого видео мы знаем,
что есть много разных методов, можно попробовать систематизировать все.
Ну, то есть можно подумать,
какие из рассказанных методов к каким видам методов относятся.
Ведь методы кластеризации могут различаться, во-первых, по структуре
кластеров, они могут быть иерархическими, то есть сложенными кластерами, и плоскими.
Иерархические, в свое время, делятся на агломеративные,
то есть заключающиеся в том, что мы последовательно объединяем кластеры,
и дивизионные, то есть заключающиеся в том,
что мы все помещаем в один большой кластер и потом делим.
Методы могут хорошо работать на разных формах кластеров.
Подумайте, на каких формах какие методы будут работать лучше.
И по присвоению объектов кластерам.
Какие-то методы позволяют легко сделать жесткую или мягкую кластеризацию,
а какие-то позволяют делать только жесткую.
Подведем итог.
В этом видео мы обзорно познакомились с несколькими методами кластеризации,
с методом k средних, с EM-алгоритмом, с методами, основанными на плотности точек,
то есть с density-based методами, и с иерархической кластеризацией.
В дальнейшем мы еще поговорим об этих и других методах подробнее, и о том,
какие методы лучше применять в каких-то конкретных ситуациях.
Evgeniy RyabenkoSenior Data Scientist, Veon, Amsterdam
Evgeny Sokolov
Victor Kantor
Emeli Dral
Константин Воронцовдоктор физико-математических наук, профессор
