Оглавление
ОПТИЧЕСКИЙ алгоритм
-
Основы кластеризации OPTICS
- OPTICS – это алгоритм кластеризации, разработанный для обработки пространственных данных с различной плотностью.
- Он устраняет проблему обнаружения значимых кластеров в данных с различной плотностью, аналогичную DBSCAN.
-
Алгоритм и его параметры
- OPTICS требует два параметра: ε (радиус) и minPts (минимальное количество точек для формирования кластера).
- Точка p является центральной, если в ее ε-окрестности находится minPts точек.
- OPTICS также рассматривает точки в более плотно упакованных кластерах, присваивая каждой точке основное расстояние.
-
Псевдокод и извлечение кластеров
- OPTICS использует приоритетную очередь для сохранения обработанных данных и выводит точки в порядке их наименьшего расстояния достижимости.
- Извлечение кластеров выполняется путем анализа графика достижимости, который отображает иерархическую структуру кластеров.
-
Сложность и расширения
- OPTICS обрабатывает каждую точку один раз и выполняет одно ε-запрос окрестностей.
- Сложность алгоритма составляет O(n⋅logn), но может быть квадратичной при неправильном выборе ε.
- Существуют расширения OPTICS, такие как OPTICS-OF для обнаружения выбросов и другие методы иерархической кластеризации.
-
Доступность
- Существуют реализации OPTICS на различных языках программирования, включая Java, R, Python и C++.
- HDBSCAN* – это улучшенная версия DBSCAN, исключающая пограничные точки из кластеров.