Skip to content

EdgeFirewalk/dbscan-react-visualization

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

12 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Визуализация DBSCAN на React

Приложение доступно по ссылке: https://edgefirewalk.github.io/dbscan-react-visualization/

Об алгоритме

Кластеризация — это процесс разделения множества объектов на группы (кластеры) таким образом, чтобы объекты в одной группе были более похожи друг на друга, чем на объекты из других групп. Методы кластеризации, основанные на концентрации объектов (Density-based methods), фокусируются на выявлении областей с высокой плотностью объектов. Эти методы особенно полезны для обнаружения кластеров произвольной формы и для работы с данными, содержащими шум.

Одним из наиболее известных методов кластеризации, основанных на концентрации объектов, является алгоритм DBSCAN (Density-Based Spatial Clustering of Applications with Noise, Основанная на плотности пространственная кластеризация для приложений с шумами). Это алгоритм кластеризации, основанной на плотности: если дан набор точек в некотором пространстве, алгоритм группирует вместе точки, которые тесно расположены (точки со многими близкими соседями), помечая как выбросы точки, которые находятся одиноко в областях с малой плотностью (ближайшие соседи которых лежат далеко).

DBSCAN был изобретен в 1996 году Мартином Эстером, Хансом-Петером Кригелем, Йоргом Сэндером и Ксавьером Ксао.

Вот некоторые из ключевых областей применения DBSCAN:

  1. Анализ данных и машинное обучение:

    • Кластеризация данных: DBSCAN используется для выявления групп (кластеров) в данных, особенно когда форма кластеров неизвестна заранее.
    • Обнаружение аномалий: DBSCAN может выявлять шумовые точки, которые не принадлежат ни к одному кластеру, что полезно для обнаружения аномалий.
  2. Геопространственный анализ:

    • Анализ пространственных данных: DBSCAN часто используется для кластеризации геопространственных данных, таких как GPS-координаты, для выявления плотных областей.
    • Городское планирование: Анализ плотности населения, транспортных потоков и других городских данных.
  3. Биоинформатика:

    • Анализ генетических данных: Кластеризация генетических последовательностей или экспрессионных данных для выявления групп генов с похожими характеристиками.
    • Анализ протеомных данных: Кластеризация белковых данных для выявления функциональных групп.
  4. Маркетинг и анализ потребителей:

    • Сегментация клиентов: Кластеризация клиентов на основе их поведения, предпочтений или демографических данных.
    • Анализ рынка: Выявление групп потребителей с похожими характеристиками для целевого маркетинга.
  5. Обработка изображений и компьютерное зрение:

    • Сегментация изображений: Кластеризация пикселей для выявления объектов или областей на изображениях.
    • Анализ видео: Кластеризация движущихся объектов в видеопотоках.
  6. Социальные сети и анализ текста:

    • Анализ социальных сетей: Кластеризация пользователей на основе их взаимодействий или интересов.
    • Анализ текста: Кластеризация документов или текстов на основе их содержания.
  7. Финансовый анализ:

    • Обнаружение мошенничества: Кластеризация транзакций для выявления аномальных операций.
    • Анализ рисков: Кластеризация клиентов или транзакций для оценки рисков.
  8. Научные исследования:

    • Анализ данных экспериментов: Кластеризация данных из научных экспериментов для выявления закономерностей и аномалий.
    • Астрономия: Кластеризация данных о звездах, галактиках и других космических объектах.

У алгоритма есть всего два параметра:

  • Eps (ε): Радиус, в пределах которого ищется минимальное количество точек.
  • MinPts: Минимальное количество точек, необходимое для формирования плотной области (кластера).

Также, в ходе работы алгоритма, может быть обнаружено 4 вида точек:

  • Точка p называется основной, если по меньшей мере minPts точек находятся на расстоянии, не превосходящем Eps до неё (включая саму точку p).
  • Точка называется прямо достижимой из основной, если эта точка находится на расстоянии, не большем Eps, от основной точки.
  • Точка называется достижимой, если до неё имеется путь, состоящий из прямо достижимых точек.
  • Все точки, не достижимые из основных точек, называются точками шума и считаются выбросами.

Преимущества DBSCAN:

  • Обнаружение кластеров произвольной формы: DBSCAN может находить кластеры любой формы, в отличие от методов, основанных на расстоянии, таких как K-means.
  • Устойчивость к шуму: DBSCAN может игнорировать шумные точки, которые не принадлежат ни к одному кластеру.
  • Не требует заранее заданного количества кластеров: DBSCAN автоматически определяет количество кластеров на основе данных.

Недостатки DBSCAN:

  • Чувствительность к выбору параметров: Выбор значений Eps и MinPts может существенно влиять на результаты кластеризации.
  • Неэффективность на данных с разной плотностью: DBSCAN может не справляться с данными, где кластеры имеют разную плотность.

Пример работы приложения

About

Реализация алгоритма DBSCAN на React с визуализацией на Canvas

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published