Следующий алгоритм кластеризации, который мы с вами узнаем, — это DBSCAN. Как работает DBSCAN? Какая основная идея? В отличие от k-means, мы не хотим заранее задавать количество кластеров, мы просто хотим найти кластера, которые являются такими сгустками данных. Поэтому нам нужно задать два параметра. У этого метода всего лишь два параметра. Первый из них — это размер Эпсилон-окрестности, вот это самое Эпсилон, и minPts, что расшифровывается как минимальное количество точек в этой самой Эпсилон-окрестности. Тогда точки, которые у нас есть, которые нам нужно кластеризовать, можно будет разделить на три типа: первые точки, которые являются Core точками (или ядровыми точками), — это такие, у которых в Эпсилон- окрестности как минимум minPts соседей. Далее идут Border точки — это такие граничные точки, которые не являются Core точками, но они достижимы из этих Core точек. А все остальные точки называются шумом (или Noise точками), у которых в Эпсилон-окрестности меньше чем minPts соседей, и они не достижимы из других Core точек. Теперь, когда все наши точки разделились на три таких класса, вот на этой картинке мы можем наблюдать рядом с каждой точкой обозначена Эпсилон-окрестность (это такой круг радиуса Эпсилон). Видно, что для точки N в окрестности никого нет, поэтому она является шумовой точкой. Все красные точки — это Core точки. У них в окрестности как минимум четыре точки, включая их самих. И есть еще две желтые точки B и C — это так называемые Border точки, можете заметить, что у них в Эпсилон-окрестности меньше чем четыре точки, но эти точки достижимы из красных, поэтому они все еще не шум, а они как бы подключаются к этим Core точкам. Теперь, когда мы будем искать кластера как такие сгустки этих самых Core точек и достижимых из них, можно прийти к более или менее естественному алгоритму. Алгоритм выглядит следующим образом (в абстрактном виде): берем следующую случайную точку и проверяем: если она является Core точкой, то мы можем начать поиск связной компоненты из этой Core точки, то есть мы находим ее, берем ее соседей, проверяем, являются ли они Core точками, и делаем такой обход в ширину, если хотите, и мы находим всю эту связную компоненту. Иначе, если в окрестности нашей выбранной точки было меньше чем minPts соседей, то есть она не является Core точкой, а является, возможно, Border или Noise, но пока что мы ее пометим как "Noise", а в дальнейшем она может быть присоединена к какому-то другому кластеру как Border точка, но пока что мы об этом не знаем, поэтому считаем, что она является Noise точкой. Давайте проиллюстрируем на конкретном примере, как этот алгоритм работает. Вот здесь у нас есть несколько точек, и пусть случайная точка, с которой мы начинаем, — это точка P2. У нас зафиксирован размер Эпсилон-окрестности и зафиксирован параметр minPts, который здесь равен двум. Что тогда происходит? Взяли точку P2, нашли ее ближайших соседей, например, это P1 и P3, они попали в Эпсилон-окрестность, теперь всего в окрестности точки три, это больше, чем наш параметр "два", поэтому эта точка является Core точкой, и из нее нам теперь нужно запустить поиск связной компоненты. Как мы это будем делать? Давайте проверим ее соседей. Начнем с P1. У нее в окрестности, этой же фиксированной Эпсилон-окрестности, тоже две точки, она тоже является Core точкой, но никаких новых точек мы из нее получить не можем, то есть если мы возьмем ее соседей, то эти точки мы уже посетили. Поэтому дальше здесь вглубь мы не сможем пройти. Берем следующего соседа, P3. P3 тоже является Core точкой, у нее в окрестности три точки, что больше, чем два, и, таким образом, мы теперь достигаем точку P4. Из нашей точки P2 можем такой цепочкой Core точек найти теперь точку P4. P4 — точно так же берем, ищем ее соседей, она является Core точкой, достигли точки P5. Точку P5 проверяем и никаких новых точек уже найти непосещенных не можем, они все уже покрашены. Поэтому мы делаем какой вывод? Мы стартанули с точки P5, нашли все достижимые точки, все, которые можно найти цепочкой Core точек, — такой путь до каждой точки должен быть. Если ничего нового нет, то мы говорим, что мы нашли на самом деле кластер. Этот кластер, например, пометим "Cluster C'' (возьмем какую-то следующую метку, которая еще не использована), и с кластеризацией вот этого кусочка мы закончили. Теперь берем следующую случайную оставшуюся непомеченную точку, например, это точка P6, для нее ищем ближайших соседей в Эпсилон-окрестности, и оказывается, что их нет. В таком случае нам ничего не остается, как пометить эту точку "Noise точкой" в надежде, что где-то в дальнейшем она, возможно, будет подключена как Border точка к какому-то кластеру, но так как у нас точки закончились, то она так и останется Noise точкой. В итоге наш результат кластеризации — это такой связный кластер слева и одна Noise точка, которая слишком далеко от этого кластера, это мы определяем параметром Эпсилон, который мы задали, поэтому она просто от этого кластера отвалилась. Собственно, этот алгоритм был придуман, чтобы искать вот на таких фотографиях сгустки данных, какую-то структуру, может быть какие-то клетки на фотографиях с микроскопа, и не обращать внимания на шум, потому что в реальных данных всегда есть шум, и этот алгоритм с ним явно уживается. Например, если мы возьмем вот эту картинку и при определенных параметрах ее покластеризуем при помощи алгоритма DBSCAN, то у нас получатся вот такие красивые связные области и вот такой шум на фоне, который, в принципе, можно проигнорировать. Результат этой кластеризации весьма хороший. Собственно, вот и весь алгоритм. Давайте посмотрим на плюсы и минусы. К плюсам можно отнести то, что в этом алгоритме нам не нужно задавать заранее количество кластеров, так как это было в алгоритме k-means, то есть DBSCAN может найти любое количество кластеров. Более того, эти кластеры могут быть причудливой формы, как мы только что увидели на картинке. Они могут быть такими изогнутыми, какими угодно. В отличие от k-means, который ищет только такие выпуклые центроиды. И этот алгоритм по своей природе умеет работать с шумными данными, что тоже можно занести ему в плюс. Что же является минусами этого алгоритма? Как вы можете догадаться, на каждом шаге нам к точке нужно искать ближайших соседе, и, вообще говоря, в худшем случае — это такой квадратичный алгоритм. То есть если у нас есть n точек, то для каждой из них мы проверим все остальные n на то, что они являются к ней ближайшими, и получается, что мы за n квадрат решаем всю эту задачу. Если n достаточно большое, например, миллион, то эта задача решается уже очень долго. К большим данным этот алгоритм применим слабо, но тем не менее он все равно есть в нашей копилке, и его можно использовать, если ваши данные не такие уж большие. Есть еще одна модификация этого алгоритма, которая называется иерархический DBSCAN. Это выходит за рамки нашего курса, но я вам крайне рекомендую про него прочитать. Это, наверное, лучший алгоритм кластеризации на сегодня, хотя он тоже не очень применим к большим данным.
