Разобраться с задачей кластеризации

[owlengineer]

Задача

Необходимо сделать ревью известных алгоритмов и оценить, какой из них:

• Наиболее простой в понимании и реализации
• Имеет больше всего примеров и источников для почитать в интернете
• Работает эффективнее прочих

Поскольку задача довольно нетривиальная и материалов при первом прогоне интернета оказалось не так много как по базовым нейронным сетям, то стоит больше ориентироваться на англоязычные источники.

Что есть почитать сейчас: Хабр-Статья на базовое понимание кластерного анализа Блиц по самоорганизующимся картам Кохонена Блиц по самоорганизующимся картам Кохонена 2 (англ) Курс лекций mail.ru - в этом курсе много всего, но там есть лекции по анализу данных, в которых кластеризация тоже рассматривается

[owlengineer]

Разобраться с задачей кластеризации

[didges]

Просматривая документацию sklearn я нашел результаты многих алгоритмов на разных выборках. Самыми адекватными по-моему мнению являются:

• Метод k-средних Алгоритм разбивает множество элементов векторного пространства на заранее известное число кластеров k. Основная идея заключается в том, что на каждой итерации перевычисляется центр масс для каждого кластера, полученного на предыдущем шаге, затем векторы разбиваются на кластеры вновь в соответствии с тем, какой из новых центров оказался ближе по выбранной метрике. Алгоритм завершается, когда на какой-то итерации не происходит изменения внутрикластерного расстояния. K-means простой в понимании и реализации метод. Его недостатки: 1)необходимо заранее знать количество кластеров 2)алгоритм очень чувствителен к выбору начальных центров кластеров Типичный пример сходимости
• AgglomerativeClustering Идея алгоритма состоит в том, что изначально каждый элемент является кластером, а новые кластеры создаются путем объединения более мелких кластеров. Кластеры объединяются по заданной мере расстояния, например метод ближайшего соседа, метод дальнего сосед, метод средней связи и др. Главной особенностью алгоритма является то, что строиться общее дерево кластеров - Дендрограмма, и нам не нужно будет пересчитывать весь алгоритм если мы захотим изменить число кластеров. Классическая Дендрограмма Из недостатков я бы упомянул, что алгоритм достаточно требователен к потребляемой памяти.
• DBSCAN Идея, положенная в основу алгоритма, заключается в том, что внутри каждого кластера наблюдается типичная плотность точек, которая заметно выше, чем плотность снаружи кластера, а также плотность в областях с шумом ниже плотности любого из кластеров. Ещё точнее, что для каждой точки кластера её соседство заданного радиуса должно содержать не менее некоторого числа точек, это число точек задаётся пороговым значением. Как выполняется алгоритм: 1)Происходит разметка точек на основные, пограничные и шумовые 2)Отсекаем шумовые точки 3)Соединяем основные точки в кластеры и добавляем пограничные элементы Иллюстрация работы DBSCAN DBSCAN отлично себя зарекомендовал в сегментации изображения

Что еще можно почитать: Иерархическая кластеризация Статья на хабре про иерархическую кластеризацию Подробнее про DBSCAN Реализация алгоритма k-means (k-средних) на примере работы с пикселями(на C++)

[SuperSolik]

В библиотеке PyTorch имеются готовые модели для сегментации изображений, примеры их использования. Из этих моделей особенно интересует DeepLabV3 - модель от Google, вот обзорная статья. Модель можно обучить на своем датасете. Репозиторий со скриптами для обучения - в README есть ссылка на статью о том как это использовать, + в примерах модель обучается различать трещины на асфальте, что довольно схоже с тем что нам в теории надо будет делать.

Картинка работы модели из приведенного репозитория:

Оригинальная статья, если вдруг кому интересно

Имеются еще две архитектуры - U-Net и FusionNet, разработанные для медицины, но вполне могут использоваться для любых изображений. Репозиторий с реализованными архитектурами и пример использования.

Начальное изображение: Полученное:

Обзорная статья про U-Net, в конце статьи полезные ссылки.

В целом я думаю использование нейронных сетей дает более гибкий и надежный механизм для сегментации изображений, подходит для нетипичных и сложных датасетов, а сами данные требуют понятной для понимания подготовки, которая может быть осуществлена средствами самого PyTorch.

[NikulinNikitaDev]

• Метод k-средних – строит заданное число кластеров, стараясь минимизировать суммарное квадратичное отклонение элементов кластера от его центра. Является одним из самых известных и наиболее популярных методов, поэтому имеет большое количество примеров. Достаточно прост в понимании и реализации. Также имеет различные улучшения и изменения (k-means++). Страница на вики
• FOREL – основан на идее объединения в один кластер объектов в областях их наибольшего сгущения. Также является достаточно простым в понимании, однако имеет достаточно низкую производительность, сильно зависит от выбора начального объекта. Страница на вики
• Самоорганизующаяся карта Кохонена – представляет собой нейронную сеть, выполняющую задачу кластеризации и визуализации. Сложнее предыдущих алгоритмов, однако имеет устойчивость к зашумлённым данным, а также быстрое обучение. Страница на вики Статья с описанием
• Иерархическая кластеризация – совокупность алгоритмов, которые создают дерево вложенных кластеров. Делятся на два основных типа: разбивающие крупные кластеры на более мелкие (divisive) и объединяющие мелкие кластеры в более крупные (agglomerative). Данный подход является как плюсом (не нужно задавать количество кластеров), так и минусом (дополнительная работа по разбиению или объединению). Страница на вики