Алгоритм сеточной кластеризации

Сеточная кластеризация

Алгоритм сеточной кластеризации

1. Разделить каждое из измерений на $p$ одинаковых интервалов.
2. Получить $p^{D}$ гиперкубов, где $D$ - размерность пространства.
3. Считаем гиперкуб заполненным, если в нем находится не меньше, чем $k$ точек. Это необходимо для того, чтобы гиперкубы с малым числом точек не влияли на кластеризацию.
4. Назовем кубы локально соединенными, если у них есть общие $r$ интервалов в одних измерениях. $r=0$ - считаются соединенным по углам. $r=1$ - по сторонам, $r>1$ - по сторонам.
5. Создаем граф, узлы - заполненные гиперкубы, ребра - между локально соединенными гиперкубами.
6. Тогда кластерами будут компоненты связности в данном графе.

Особенности метода

1. Число кластеров и их размеры определяются самим алгоритмом
2. Необходимо задать $p,k,r$
3. Метод плохо работает с кластерами разной плотности.

Ссылки

Лекции Китова, с. 55-60