Неконтролируемое обучение
Кластеризация. Эвристика на K и как бороться с шумом
Кластеризация — это широко известный метод обучения без учителя, позволяющий находить неявную структуру в наборе данных без явных указаний, что искать.
Существует множество алгоритмов для выполнения этой задачи, но они основаны на разных методах и поэтому не дают одинаковых результатов.
Затем цель состоит в том, чтобы создать K групп или кластеров точек (каждый элемент из нашего набора данных), которые близки друг к другу, где близкое расположение зависит от того, какие функции мы используем для представления данных и как мы измеряем ошибку.
В этом посте мы будем использовать простой набор данных с географическими точками и обсудим некоторые способы и идеи для создания кластеров на основе того, насколько физически близки эти точки в пространстве, сравним и используем различные алгоритмы, оценим результаты и рассмотрим возможные выбросы.
Давайте посмотрим на наш набор данных.
Если мы посмотрим на общую картину (слева), мы можем подумать, что у нас всего несколько групп. И в каком-то контексте это может быть полезно, но, присмотревшись повнимательнее, мы обнаружим, что у нас могут быть тяжелые плотные области внутри региона. Итак... какое число K мы выбираем? т. е. Сколько групп мы должны создать?
Кластеризация на основе плотности. Нахождение К.
Ответ на эти вопросы очевиден: это зависит.
Не так уж очевидно, что существуют какие-то категории для алгоритмов кластеризации, и мы должны найти ту, которая лучше всего соответствует нашей модели. Некоторые из них основаны на центроиде, плотности, распределении и иерархической кластеризации. Наиболее используемые и известные методы кластеризации основаны на центроидах; но для их использования нам нужно определить число K.
Первый подход может заключаться в применении метода локтя, и все, мы берем не только значение K, но и кластеры, которые минимизируют ошибку. Проблема применения такого слепого поиска в том, что это очень дорого.
Воспользуемся тем, что у нас есть набор данных с большим количеством плотных облаков точек, и попробуем более разумный метод: кластеризация на основе плотности.
В кластеризации плотности кластер в пространстве данных представляет собой непрерывную область с высокой плотностью точек, отделенную от других таких кластеров смежными областями с низкой плотностью точек. Точки данных в разделяющих областях с низкой плотностью точек обычно считаются шумом/выбросами.
Одним из недостатков алгоритмов кластеризации является высокая сложность (проблема кластеризации np сложна), поэтому мы должны быть осторожны, если у нас есть большой (или многомерный) набор данных. В этом случае мы решили взять репрезентативную выборку из нашего набора данных для тестирования различных алгоритмов и настройки гиперпараметров; затем запустите выбранный алгоритм со всеми данными.
Другим недостатком является то, что кластеризация плотности создает выбросы (шум) в зонах, которые находятся в середине других регионов (границы), или в зонах, которые находятся далеко. В этом аспекте мы можем работать, настраивая минимальный размер кластера (в нашем случае мы не возражаем против небольших кластеров) и значение эпсилон; в основном это мера достижимости из одной точки внутри кластера, чтобы решить, принадлежат ли ее соседи к этому кластеру или нет. Значения эпсилон ведут себя по-разному для разных алгоритмов плотности, но основная идея остается неизменной.
Наиболее популярными алгоритмами на основе плотности являются DBSCAN и OPTICS. Мы выбрали улучшение DBSCAN, HDBSCAN, и сравнили результаты кластеризации с аналогичными значениями параметров на OPTICS. Полученный результат показывает нам, что HDBSCAN является более быстрой реализацией и гораздо более бесшумным с таким же количеством извлеченных центроидов (см. график ниже). Для малых значений эпсилон у OPTICS немного меньше ошибок, создающих почти одинаковое количество кластеров на каждой итерации. Хорошая попытка ОПТИКА, но HDBSCAN сходится намного быстрее, возможно, в следующий раз.
Также справедливо отметить, что HDBSCAN, как правило, плохо работает с многомерными данными, но сейчас это не совсем наш случай.
Кажется, у нас есть победитель…
Эпсилон против ошибки против выбросов. Выберите один, вы не можете иметь все.
Хорошо, мы нашли наш метод. Теперь давайте найдем лучшую кластеризацию. При кластеризации лучшее зависит от нашей модели, нашего контекста и того, что мы хотим сделать. Зависит, опять же.
Основная концепция этого раздела посвящена тому, как мы можем выбрать значения эпсилон в соответствии с нашей моделью. Поскольку это значение указывает расстояние между одной точкой и другой, чтобы решить, принадлежат ли они к одному и тому же кластеру, давайте выясним, где находятся все соседи нашей точки. Для каждой точки рассчитаем расстояние до ближайшего соседа. Для этого мы использовали реализацию sklearn. Будь осторожен. Это очень дорогой метод, который может занять много времени. Подумайте о том, чтобы сделать это с подмножеством ваших данных, чтобы иметь хотя бы представление о значениях эпсилон.
В этом случае более 99% находятся на расстоянии менее 0,1 от ближайшего соседа. Расстояние между точками задается нормой2, поэтому мы не предполагаем ничего конкретного из нашего набора данных (например, тот факт, что они привязаны к местности).
Давайте запустим HDBSCAN.
У нас есть два аспекта, о которых нужно позаботиться: Ошибка и Количество произведенных выбросов. Итак, мы будем визуализировать эти значения как функцию эпсилон.
С этими графиками у нас есть хорошая основа, чтобы решить, какое значение эпсилон взять. Мы видим, что если мы сохраним пороговое значение 0,1, у нас будет очень мало выбросов, но высокая ошибка. Если мы не готовы платить эту цену за ошибку, нам придется выбирать меньшие значения эпсилон и иметь дело с шумом. Давайте с этим…
Не волнуйтесь, мы почти закончили…
Минимизация ошибок и удаление шума с помощью KMeans
Если мы хотим, чтобы все точки были близки к кластеру его центроида, нам нужно выбрать небольшое значение эпсилон. Давайте подгоним нашу модель под значение 0,001 эпсилон и запустим HDBSCAN.
У нас очень маленькое значение ошибки (можно посмотреть вверху графика), мы создали более тысячи кластеров (центроиды отмечены x), но мы также получили почти 10% выбросов. Так что же нам делать с этими точками?
Ну, теперь у нас есть центроиды. Так почему бы нам не запустить алгоритм кластеризации на основе центроида? Мы знаем, что эти алгоритмы генерируют K разделов в пространстве, поэтому они вообще не производят шума.
Для этого мы будем использовать хорошо известный алгоритм: KMeans. Конечно, вы можете попробовать другой (Mean Shift, Spectral Clustering и т. д.) в зависимости от ваших потребностей. Для наших тестов KMeans помог.
Мы использовали sklearn реализацию KMeans. Мы подгоняем нашу модель, проходящую через центроиды HDBSCAN, и устанавливаем небольшой допуск для сходимости, исходя из идеи, что работа почти выполнена, и для KMeans это должно быть легко.
Конечно, шум пропадет, но погрешность обязательно возрастет. Кроме того, когда мы запускаем kmeans, центроиды будут иметь тенденцию немного смещаться от своего исходного положения, чтобы свести к минимуму увеличение этой ошибки. Давай посмотрим что происходит.
Мы сделали это! KMeans потребовалось всего 10 итераций, чтобы прийти к решению. Наши центроиды немного смещаются, чтобы свести к минимуму ошибку, которая, конечно же, увеличилась, но сохранили тот же порядок величин, что и у нас, и теперь у нас есть полная бесшумная классификация.
Это не единственное решение. Мы уже узнали, что можем передать другое значение эпсилон и пройти весь процесс заново, чтобы найти оптимальное решение для ваших нужд.
Если вы хотите еще…
Здесь мы представим некоторые альтернативы, которые могут подойти вам в зависимости от ваших потребностей. Мы попробовали все это и получили наименьшее значение ошибки с помощью шагов, упомянутых выше. У вас также могут быть другие потрясающие идеи для изучения.
- Выполнить kmeans с заданным значением K (или его значением) из результата HDBSCAN, но не передавать массив центроидов. Конечно, мы игнорируем собранную информацию, и это может занять гораздо больше времени, чтобы прийти к решению.
- Не запускать kmeans, назначьте каждую точку шума ближайшему кластеру. Если у нас есть только несколько точек шума, это довольно хорошее решение, потому что мы избегаем настройки алгоритма на основе центроида и являемся быстрым решением.
- Если наш контекст позволяет это, создайте новый кластер для каждой точки выброса. Аналогично варианту выше, но у нас будут унитарные кластеры. Это может быть полезно, если в будущем могут появиться новые точки.
[ДОПОЛНИТЕЛЬНО] HDBSCAN без выбросов
Если вы дойдете до этой части, значит, вы действительно занимаетесь кластеризацией. слава!
Как вы можете видеть из графиков выбросов, существует значение эпсилон, которое не дает никакого шума при работе только с HDBSCAN. Это значение довольно велико, это означает, что многие точки будут принадлежать одному кластеру, следовательно, у нас будет небольшое количество кластеров. Посмотрим на результат.
У нас всего 9 кластеров. Этот подход удобен для обнаружения областей с наибольшей плотностью наших данных, и, возможно, мы даже могли бы определить другую стратегию для каждого найденного кластера.
