DBSCAN
На вход подается матрица близости (S=NxN) и два загаочных параметра:
Радиус ε-окресности
- радиус, в котором ищутся ближайшие от точки соседи
Ближайшие k-соседи - точки, попадающие в радиус ε-окрестности от заданной
Алгоритм:
Берем случайную точку
Если для нее k<3 - идем дальше
Иначе:
Точка "зеленая"(k>3) - создает группу. Обходим ее соседей, присоединяем их к группе и исключаем из списка обхода. Если сосед "зеленый", его соседей также добавляем в список обхода. Желтым помечаются точки с k<3, но вошедшие в эту группу. Повторяем пока список обхода не окажется пуст.
Повторяем пункты 1-3, пока не обойдем все точки. Точки, не вошедшие ни в какую группу помечаем красным цветом.
В пункте 4 можно включить дополнительную классификацию для "красных" точек, но здесь это опускается.