Mean-shift

Mean Shift — плотностной метод кластеризации, связанный с оценкой плотности распределения и поиском ее локальных максимумов. Классическое изложение метода дано Д. Команичиу и П. Меером. **Основная идея:** Каждая точка итеративно смещается в сторону области большей плотности. Направление сдвига задается вектором mean shift: $m(x) = \frac{\sum_i x_i K\left(\frac{x - x_i}{h}\right)}{\sum_i K\left(\frac{x - x_i}{h}\right)} - x$, где $K$ — ядро, $h$ — ширина окна (bandwidth). **Результат:** Точки, сходящиеся к одному и тому же локальному максимуму плотности, образуют кластер. **Преимущества:** Не нужно заранее задавать число кластеров, а форма кластеров может быть сложной. **Ограничения:** Качество сильно зависит от bandwidth. Слишком маленькое окно дробит данные на множество локальных групп, слишком большое — сливает разные структуры. Метод может быть вычислительно тяжелым на больших выборках.