[ЗАСТАВКА] В этом видео мы поговорим про кластеризацию на основе плотности точек. То есть density-based кластеризацию. Сначала мы поговорим об идее этих методов, затем рассмотрим пример основных граничных и шумовых точек, вспомним, как работает алгоритм DBSCAN, посмотрим на примеры его работы, поговорим про определение числа кластеров в DBSCANе, насколько оно может быть верным или неверным. Ну и, наконец, обсудим, как же подобрать параметры в DBSCANе. Итак, идея density-based методов, мы уже с вами обсуждали, заключается в том, чтобы рассматривать плотность точек в окрестности каждого объекта выборки. Если в некоторой окрестности некоторого заданного радиуса точек много, ну то есть больше какого-то, опять же, заданного количества, радиус и количество точек — это параметры алгоритма, то мы будем говорить, что эта точка основная. Если точек меньше, чем нужно, но в то же время в окрестность попадает основная точка, мы будем говорить, что эта точка граничная. Ну и если в окрестности очень мало точек, и никакой основной точки туда не попадает, мы будем говорить, что эта точка шумовая. Ну вот сейчас на слайде изображён пример, в котором точки классифицированы на шумовые (это точка N), граничные точки (B и C) и основные точки. Что происходит в алгоритме DBSCAN? Сначала мы помечаем все точки как основные, пограничные или шумовые. Затем мы отбрасываем шумовые точки. Ну то есть не рассматриваем их в дальнейшей кластеризации. После этого мы можем соединить точки, находящиеся на расстоянии меньше заданного радиуса окрестности одна от другой. Таким образом, мы получим некоторый граф. Дальше мы можем объединить каждую группу соединённых основных точек в отдельный кластер, ну то есть выделить связанные компоненты в получившемся графе. Дальше каждую пограничную точку можно назначить одному из кластеров, ассоциированных с одной из основных точек, находящихся в окрестности пограничной. Ну и вот результаты работы этого алгоритма могут быть довольно впечатляющими. То есть на примере, который вы сейчас видите на слайде можно хорошо увидеть, что DBSCAN хорошо справляется с нетривиальными формами кластеров: кластерами-лентами, вложенными друг в друга, какими-то отдельными частями кластерами, и в то же время успешно отделяет шумовые точки, которые могли бы сильно испортить работу других алгоритмов кластеризации. В то же время не стоит думать, что DBSCAN прямо-таки идеально определяет количество кластеров. Всё это, конечно, зависит от того, какой радиус рассматривать в окрестности, но в каких-то случаях всё работает хорошо, а в каких-то случаях мы можем совершенно неправильно определить количество кластеров. Ну, например, на картинке, показанной сейчас на слайде, вы видите ситуацию, когда кластеров явно 4, но они достаточно хорошо перетекали друг в друга, и поэтому три кластера слились воедино. В то же время, если бы один из этих кластеров был чуть подальше, то этого бы не произошло. Ну и наконец возникает вопрос: как же понять, какое количество точек достаточно, чтобы считать, что плотность точек в окрестности велика? И какого радиуса брать окрестность? Для этого можно построить следующий любопытный график. Давайте по оси x расположим количество точек, отсортированных по расстоянию от этих точек до их k-того соседа. Ну, например, четвертого соседа, третьего, пятого. Зафиксировав число k и отсортировав точки по расстоянию до k-того соседа, мы можем построить график зависимости этого расстояния от номера точки в отсортированном массиве и увидеть интересную вещь. Оказывается, что у хвоста массива, то есть у тех точек, для которых расстояние до k-того соседа очень большое, будет резкий рост этого расстояния. Что это означает? Это означает, что мы можем выбрать то расстояние, которое соответствует началу этого резкого роста, в качестве радиуса окрестности. А число k ну, в случае этого графика 4, выбрать в качестве количества точек, которые должны быть в окрестности, чтобы сказать, что точка, в окрестность которой мы смотрим, основная. Поперебирав разные k, мы можем получить разные графики. А дальше посмотреть на то, как много точек мы готовы сделать шумовыми, потому что хвост вот этого отсортированного по расстоянию массива, будет в основном представлен шумовыми точками. Итак, мы вспомнили основную идею методов, которые используют понятие плотности точек. Мы рассмотрели примеры основных граничных и шумовых точек, вспомнили алгоритм DBSCAN и посмотрели, как он может работать на разных модельных данных. Обсудили вопрос определения числа кластеров DBSCAN и вопрос настройки параметров DBSCAN.