Существуют различные типы алгоритмов кластеризации в машинном обучении, такие как кластеризация на основе центроида, кластеризация на основе плотности, кластеризация на основе распределения, кластеризация на основе иерархии.
Сегодня мы сосредоточимся на кластеризации на основе плотности или DBSCAN. Прежде чем перейти к DBSCAN, мы поймем, что такое кластеризация?
Например: группа посетителей, сидящих в ресторане. Предположим, есть две таблицы T1 и T2. Люди, сидящие за столом T1, могут быть родственниками друг друга. Даже люди, сидящие за столом T2, связаны друг с другом, но люди, сидящие за столом T1 и T2, не связаны друг с другом. Кластеризация также работает аналогичным образом, точки данных, находящиеся в одном кластере, полностью отличаются от других кластеров.
Кластеризация – это процесс разделения наборов данных на группы, состоящие из схожих точек данных.
Почему мы используем DBSCAN?
Представьте, мы собрали измерения роста и веса группы людей и нанесли их на двухмерный график, где ось X указывает вес, а ось Y указывает рост человека. . На глаз мы можем увидеть два разных кластера. Напротив, люди, которые далеки от всех остальных, выглядят изгоями. Однако, поскольку эти кластеры являются вложенными, то есть зеленый кластер окружает синий кластер, здесь кластеризация K-средних может затруднить идентификацию этих двух кластеров. Вместо этого из-за вложенности простой метод кластеризации выглядит так, как будто точки данных назначаются синему кластеру, даже если они выглядят так, как будто они принадлежат зеленому кластеру. Поэтому нам нужен алгоритм кластеризации, который может обрабатывать вложенные кластеры.
Существуют алгоритмы кластеризации, которые могут идентифицировать вложенные кластеры в больших размерностях. Одним из таких алгоритмов является DBSCAN.
DBSCAN пытается имитировать то, что мы можем легко сделать на глаз. мы можем идентифицировать кластеры на основе плотности точек. Кластеры, как правило, находятся в области высокой плотности, а выбросы — в областях с низкой плотностью.
Как DBSCAN использует плотность точек для идентификации кластеров?
В этой технике мы будем подсчитывать количество точек, которые находятся близко друг к другу. Мы определим основную точку как точку, которая как минимум близка к 4 другим точкам. Количество близких точек для основных точек определяется пользователем.
Мы случайным образом выбираем основную точку и назначаем ее кластеру. Основные точки, находящиеся рядом с первым кластером, будут добавлены в первый кластер. Основные точки, расположенные рядом с растущим первым кластером, объединяются и расширяют его до другой базовой точки, находящейся поблизости. В отличие от основных точек, неосновные точки могут присоединяться только к кластеру. Они не могут продлить его дальше. Теперь мы добавляем все неосновные точки, близкие к основным точкам в первом кластере, в первый кластер.
Основные точки, которые не находятся близко к первому кластеру, сформируют новый второй кластер, и к нему будут добавлены Неосновные точки, которые близки ко второму кластеру.
Остальные неосновные точки, которые не близки к основным точкам в любом кластере, не добавляются в кластер и называются выбросами.
Вывод:
Кластеры создаются последовательно. Это означает, что если у нас есть неосновная точка рядом с обоими кластерами, мы построим первый кластер. Мы добавим неосновные точки, близкие к кластерам.
