Инструмент Кластеризация на основе плотности определяет области концентрации точек, отделяя их от пустых и разреженных областей. Точки, не являющиеся частью кластера, помечаются, как шум.
Инструмент использует алгоритмы автоматической кластеризации без обучения, автоматически определяющие основанные на пространственном положении расстоянии до заданного числа соседей наборы. Эти алгоритмы называются алгоритмами «без обучения», так как для них не требуется описания того, что такое кластер.
Подсказка:
Кластеризация, группировка и классификация - одни из самых часто используемых.методов машинного обучения. Инструменты Многовариантная классификация и Пространственно ограниченная многовариантная кластеризация также используют методы обработки «без обучения» для нахождения естественных кластеров ваших данных. Эти методы классификации называются классификацией «без обучения», так как не требуют набора классифицированных заранее объектов для «тренировки» алгоритма для дальнейшего поиска кластеров в ваших данных.
Возможное применение
Некоторые способы использования этого инструмента перечислены здесь:
- Городские сети водоснабжения - важнейшие подземные структуры. Кластеризация трещин и разрывов в трубах может быть индикатором надвигающихся проблем. С помощью инструмента Кластеризация на основе плотности инженер может найти расположение кластеров и предпринять превентивные меры в зонах повышенной опасности сетей водоснабжения.
- Представьте, что у вас есть координаты мест, с которых были выполнены все удачные и неудачные броски игроков NBA. Кластеризация на основе плотности покажет вам зоны удачных и неудачных мест для броска для каждого игрока. Эта информация может оказаться очень полезной для выбора стратегии на матч.
- Допустим, вы изучаете какую-то болезнь, вызванную переносчиками инфекции и у вас есть набор точечных данных о домашних хозяйствах изучаемой области, некоторые из которых являются зараженными, а некоторые - нет. Посредством инструмента Кластеризация на основе плотности можно выделить наибольшие кластеры зараженных переносчиками инфекции домашних хозяйств, чтобы выделить места, в которых нужно начать лечение и уничтожение паразитов.
- Твиты с геолокацией. связанные с природными опасностями или террористическими атаками, могут быть кластеризованы и, на основе размера и местоположения кластеров, получена информация о необходимых мерах по спасению и эвакуации.
Методы кластеризации
Инструмент Кластеризация на основе плотности включает три разных Метода кластеризации для выделения кластеров в точечных данных:
- Указанное расстояние (DBSCAN) — Использует указанное расстояние для отделения плотных кластеров от окружающего шума. Алгоритм DBSCAN самый быстрый из методов кластеризации,но применим только в случае, если четко ясно, какое Расстояние поиска использовать для получения хороших результатов для всех потенциальных кластеров. Это происходит в ситуации сходных плотностей всех важных кластеров.
- Автонастройка (HDBSCAN) — Использует различные расстояния для отделения кластеров с различными плотностями от окружающего шума. HDBSCAN является наиболее ориентированным на данные методом кластеризации, для него требуется минимум участия пользователя.
- Многомасштабный (OPTICS) — Использует расстояние между соседними объектами для получения поля доступности, которое применяется для отделения кластеров различных плотностей от шума. OPTICS предлагает наибольшую гибкость в тонких настройках определения кластеров, хотя и требует интенсивных вычислений, особенно с большим Расстоянием поиска.
Этот инструмент принимает на входе Входные точечные объекты, путь к Выходным объектам и значение минимального числа объектов, которые будут считаться кластером. В зависимости от Метода кластеризации могут быть дополнительные параметры, как, например, показано ниже.
Минимальное число объектов для кластера (необходимо для всех методов)
Этот параметр определяет минимальное количество объектов, которые могут быть сгруппированы в кластер. Например, если у вас несколько различных кластеров размером от 0 до 100 точек и вы выберете Минимальное количество объектов для кластера равным 20, все кластеры размером менее 20 будут либо считаться шумом (так как не формируются в кластер подходящего размера), либо будут слиты с соседними кластерами, чтобы минимальное количество объектов было соблюдено. Напротив, задав значение Минимального числа объектов в кластере, меньшее, чем предполагаемый вами размер наименьшего значимого кластера, вы можете добиться разбиения этих кластеров на меньшие. Другими словами, чем меньше Минимальное число объектов в кластере, тем большее количество кластеров будет обнаружено. Чем больше Минимальное число объектов в кластере, тем меньше кластеров будет обнаружено.
Подсказка:
Идеальное значение Минимального числа объектов в кластере зависит от того, чего вы пытаетесь добиться и в чем цель вашего анализа. Оно должно соответствовать минимальному размеру, который будет считаться значимым кластером. Увеличение Минимального числа объектов в кластере может привести к слиянию некоторых небольших кластеров.
Параметр Минимальное число объектов в кластере также является очень значимым для вычисления кластерного расстояния, которое применяется всеми тремя методами нахождения кластеров. Концептуально кластерное расстояние для каждой точки - это дистанция, требуемая для достижения каждой точкой заданного минимального числа объектов. Если выбрано большое значение Минимального числа объектов в кластере, соответственно, и кластерное расстояние будет большим. Если выбрано маленькое значение Минимального числа объектов в кластере, то и кластерное расстояние будет небольшим. На границах кластеров у точек будут большие кластерные расстояния (и такие точки вообще могут не попасть в кластер). Кластерное расстояние связано с параметром Расстояние поиска, использующимся методами Указанное расстояние (DBSCAN) и Многомасштабный (OPTICS).
Расстояние поиска (DBSCAN и OPTICS)
Для метода Указанное расстояние (DBSCAN) в случае, если Минимальное число объектов в кластере не может быть найдено в пределах Расстояния поиска от конкретной точки, такая точка помечается, как шум. Другими словами, если кластерное расстояние (расстояние для достижения минимального числа объектов) для объекта больше Расстояния поиска, точка считается шумом. Расстояние поиска при выборе алгоритма Указанное расстояние (DBSCAN) рассматривается, как отсечение поиска.
Для метода Многомасштабный (OPTICS) Расстояние поиска, рассматривается, как максимальное расстояние, сравниваемое с кластерным расстоянием. Метод Многомасштабный (OPTICS) использует концепцию максимально достижимого расстояния, являющегося расстоянием от точки до ее ближайшего соседа, еще не появлявшегося в поиске (помните: OPTICS i- упорядоченный алгоритм, начинающий работу с объекта с OID=0 и следующим дальше от точки к точке. Порядок точек влияет на результаты его работы. Метод Многомасштабный (OPTICS) будет проверять все соседние расстояния в пределах заданного Расстояния поиска, сравнивая каждое из них с кластерным расстоянием. Если какое-то расстояние окажется меньше кластерного, то объекту присваивается это кластерное расстояние в качестве достижимого. Если все расстояния оказываются большими, чем кластерное расстояние, наименьшее из них считается достижимым. Эти расстояния затем используются для создания графика достижимости, являющегося упорядоченным графиком расстояний достижимости, который применим для определения кластеров.
Для обоих методов, Заданное расстояние (DBSCAN) и Мультимасштабный (OPTICS), по умолчанию Расстоянием поиска является наибольшее значение кластерного расстояния, найденное в наборе данных, исключая те, которые попадают в верхние 1% (т.е., исключая наивысшие значения кластерного расстояния).
График достижимости (OPTICS)
После того как будут вычислены все расстояния достижимости набора данных, создается график достижимости, упорядочивающий расстояния и показывающий кластерную структуру точек.
Понижения графика означают, что между точками небольшое расстояние. То есть эти участки соответствуют кластерам точек. Чем более плотным является кластер, тем меньше будут расстояния достижимости и тем глубже будет впадина на графике (например, розовый кластер - самый плотный в показанном выше примере). У менее плотных кластеров большие расстояния доступности и более высокие области на графике (например, темно-зеленый кластер - наименее плотный в показанном выше примере). Пики отображают расстояния, необходимые для перемещения от кластера к кластеру либо от кластера до шума и снова до кластера - в зависимости от конфигурации набора точек.
Плоские области появляются, если Расстояние поиска меньше наибольшего кластерного расстояния. Ключевым моментом использования метода кластеризации OPTICS является способ определения кластеров на графике достижимости, контролирующийся параметром Чувствительность кластера.
Чувствительность кластера
Параметр Чувствительность кластера определяют, как форма пиков (и уклон, и высота) на графике достижимости будет использоваться для разделения кластеров. Очень высокое значение Чувствительности кластера (близкое к 100) приведет к рассмотрению даже минимального пика в качестве разделения между кластерами, в результате чего будет получено очень большое их количество. Очень низкая Чувствительность кластера (близкое к 0) будет рассматривать в качестве границ для кластеров только наиболее крутые и высокие пики - и мы получим меньшее их число.
По умолчанию Чувствительность кластера вычисляется, как допуск, при котором при добавлении новых кластеров не появляется дополнительной информации, вычисляется, как Дивергенция Кулбака-Лейблера между исходным графиком достижимости и сглаженным графиком достижимости, полученным после кластеризации.
Сравнение методов интерполяции
Хотя только алгоритм Мультимасштабный (OPTICS) применяет для определения кластеров график достижимости, этот график может использоваться для иллюстрации отличий методов друг от друга. Для данной иллюстрации представленный далее график достижимости будет использован для объяснения различий трех методов. На графике отображены кластеры различной плотности и разных расстояний разделения. Мы с помощью этого изображения изучим результаты использования каждого из методов кластеризации.
Для Заданного расстояния (DBSCAN) представьте себе линию, пересекающую график на указанном Расстоянии поиска. Области под Расстоянием поиска соответствуют кластерам, а пики над Расстоянием поиска - точкам шума. Алгоритм DBSCAN - самый быстрый из методов кластеризации,но применим только в случае, если четко ясно, какое Расстояние поиска использовать и это Расстояние поиска подходит для всех потенциальных кластеров. Это происходит в ситуации сходных плотностей всех важных кластеров.
Для Самонастраивающегося (HDBSCAN) алгоритма расстояния достижимости можно рассматривать как вложенные уровни кластеров. Каждый уровень кластеризации приведет к обнаружению разных наборы кластеров. Самонастраивающийся (HDBSCAN) алгоритм выбирает, на каком уровне кластеров в каждом наборе вложенных кластеров будут созданы наиболее стабильные кластеры, включающие максимально возможное количество объектов и не содержащие шумов. Подробнее об алгоритме см. в прекрасной документации от создателей HDBSCAN. Самонастраивающийся (HDBSCAN) является наиболее ориентированным на данные методом кластеризации, для него требуется минимум участия пользователя.
В алгоритме Мультимасштабный (OPTICS) определение кластеров основывается не на конкретном расстоянии, а на пиках и впадинах графика. Предположим, что у пика есть уровни: малый, средний и большой.
Если выбрать очень высокую Чувствительность кластера, то, как правило, все пики - от малых и до больших - будут считаться разделяющими классы (что приводит к большому числу классов).
При выборе средней Чувствительности кластеров будут использоваться только Большие и Средние пики, а малые - нет.
При выборе низкой Чувствительности кластеров будут использоваться только Большие пики, в результате чего будет обнаружено наименьшее число кластеров.
Мультимасштабный (OPTICS) предлагает наибольшую гибкость в тонких настройках определения кластеров, хотя и является самым медленным из трех методов кластеризации.
Результаты
Этот инструмент создает выходной класс объектов с новым целочисленным полем CLUSTER_ID, где обозначается принадлежность объектов кластерам. Отображение по умолчанию основано на поле COLOR_ID. Разным кластерам присваиваются различные цвета. Цвета распределяются и повторяются таким образом, что каждый кластер визуально отличается от соседних.
Если Методом кластеризации выбран Автонастройка (HDBSCAN), выходной класс объектов также будет содержать следующие поля: PROB, в котором хранится вероятность принадлежности объекта к группе, OUTLIER, означающее,что объект может быть выбросом в своем кластере (чем выше значение, тем больше вероятность, что объект является выбросом) и EXEMPLAR, где обозначаются объекты, наиболее характерные для данного кластера.
Этот инструмент также создает сообщения и диаграммы, которые помогают понять характеристики идентифицированных кластеров. Вы можете получить доступ к сообщениям, переместив курсор мыши на индикатор выполнения, щелкнув на всплывшую кнопку или развернув раздел Сообщения в панели Геообработка. Вы также можете открыть сообщения, касающиеся ранее запущенного инструмента Кластеризация на основе плотности с панели История геообработки. Созданные диаграммы можно открыть с помощью панели Содержание.
Помимо создающегося при работе алгоритма Мультимасштабный (OPTICS) графика достижимости, все методы кластеризации создают столбчатую диаграмму со всеми уникальными значениями Cluster ID. Эту диаграмму можно использовать для быстрого выбора всех объектов, попадающих внутрь заданного кластера и изучения размера кластеров.
Дополнительные источники
Подробнее о DBSCAN:
- Ester, M., Kriegel, H. P., Sander, J., & Xu, X. (1996, August). Основанный на плотности алгоритм изучения кластеров в больших пространственных базах данных с шумом. In Kdd (Vol. 96, No. 34, pp. 226-231).
Подробнее о HDBSCAN:
- Campello, R. J., Moulavi, D., & Sander, J. (2013, April). Основанная на плотности кластеризация с иерархическими оценками плотности. In Pacific-Asia Conference on Knowledge Discovery and Data Mining (pp. 160-172). Springer, Berlin, Heidelberg.
Подробнее о OPTICS:
- Ankerst, M., Breunig, M. M., Kriegel, H. P., & Sander, J. (1999, June). OPTICS: упорядочение точек для идентификации структуры кластеров. In ACM Sigmod record (Vol. 28, No. 2, pp. 49-60). ACM.