Сдвиг среднего значения

Процедуру сдвига среднего значения представили в 1975 Фукунага и Хостетлер [3].

Сдвиг среднего значения является процедурой для определения местоположения максимумов (мод) плотности вероятности, задаваемой дискретной выборкой по этой функции[1]. Метод является итеративным, и мы начинаем с начальной оценки ${\displaystyle x}$. Пусть будет задана ядерная функция ${\displaystyle K(x_{i}-x)}$. Эта функция определяет вес ближайших точек для переоценки среднего. Обычно используется гауссово ядро от расстояния до текущей оценки ${\displaystyle K(x_{i}-x)=e^{-c||x_{i}-x||^{2}}}$. Взвешенное среднее плотности в окне, определённом функцией ${\displaystyle K}$ равно

${\displaystyle m(x)={\frac {\sum _{x_{i}\in N(x)}K(x_{i}-x)x_{i}}{\sum _{x_{i}\in N(x)}K(x_{i}-x)}}}$

где ${\displaystyle N(x)}$ является окрестностью точки ${\displaystyle x}$, то есть набором точек, для которых ${\displaystyle K(x_{i})\neq 0}$.

Разность ${\displaystyle m(x)-x}$ в статье Фукунаги и Хостетлера названа сдвигом среднего значения[3].

Алгоритм сдвига среднего значения теперь назначает ${\displaystyle x\leftarrow m(x)}$ и повторяет оценку, пока ${\displaystyle m(x)}$ не сойдётся.

Хотя алгоритм сдвига среднего значения широко используется во многих приложениях, строгое доказательство сходимости алгоритма, использующего ядро общего вида в пространствах высокой размерности, отсутствует[4]. Алийари Гассабех показал сходимость алгоритма сдвига среднего значения в одномерном пространстве с дифференцируемой, выпуклой и строго убывающей функцией профиля[5]. Однако случай одной размерности имеет ограниченное применение для реальных задач. Была доказана сходимость алгоритма для случаев высокой размерности с конечным числом (или изолированных) стационарных точек[4][6]. Однако достаточные условия, чтобы функция ядра имела конечное число (или изолированные) стационарных точек, приведены не были.

Пусть данные представляют собой конечный набор точек ${\displaystyle S}$ в n-мерном евклидовом пространстве X. Пусть K будет плоским ядром, которое является характеристической функцией на ${\displaystyle \lambda }$-шаре в X,

На каждой итерации алгоритма выполняется ${\displaystyle s\leftarrow m(s)}$для всех ${\displaystyle s\in S}$ одновременно. Первый вопрос тогда, как оценить плотность вероятности по заданному пространственному набору точек. Простейший подход — просто сгладить данные, то есть осуществить свёртку с фиксированным ядром ширины ${\displaystyle h}$,

,

где ${\displaystyle x_{i}}$ являются входными точками, а ${\displaystyle k(r)}$ является ядерной функцией (или окном Парзена). Параметр h является единственным параметром в алгоритме и он называется шириной пропускания. Этот подход известен как техника оценки плотности ядра или как окно Парзена. Как только мы вычислили ${\displaystyle f(x)}$ из уравнения выше, мы можем найти локальный максимум функции с помощью техники градиентного спуска или другой оптимизационной техники. Проблема с таким подходом «грубой силы» в том, что для высоких размерностей становится вычислительно невозможно вычислить ${\displaystyle f(x)}$ по всему пространству. Вместо этого алгоритм сдвига среднего значения использует вариант, который в оптимизационной литературе известен как градиентный спуск с многократным рестартом. Начиная с некоторого предположения о местоположении локального максимума ${\displaystyle y_{k}}$, который может быть случайной точкой входных данных ${\displaystyle x_{1}}$, сдвиг среднего значения вычисляет оценку градиента плотности ${\displaystyle f(x)}$ в точке ${\displaystyle y_{k}}$ и осуществляет шаг в этом направлении (в сторону увеличения)[7].

Определение ядра: Пусть X будет n-мерным евклидовым пространством ${\displaystyle R^{n}}$. Обозначим i-тую компоненту x через ${\displaystyle x_{i}}$. Нормой вектора x является неотрицательное число ${\displaystyle \|x\|^{2}=x^{T}x}$. Говорят, что функция K: ${\displaystyle X\rightarrow R}$ является ядром, если существует профиль ${\displaystyle k:[0,\infty ]\rightarrow R}$, такой, что

${\displaystyle K(x)=k(\|x\|^{2})}$ и

• k неотрицателен.
• k невозрастающий: ${\displaystyle k(a)\geqslant k(b)}$, если ${\displaystyle a<b}$.
• k кусочно непрерывен и ${\displaystyle \int _{0}^{\infty }k(r)\,dr<\infty \ }$

Два часто используемых ядерных профиля для сдвига среднего значения:

Плоское ядро

Гауссово ядро

где параметр стандартного отклонения ${\displaystyle \sigma }$ служит параметром ширины пропускания ${\displaystyle h}$.

1. Сдвиг среднего значения является независимым от приложения средством, пригодным для анализа реальных данных.
2. Метод не предполагает предварительного задания формы кластеров.
3. Алгоритм способен обрабатывать произвольные пространства признаков.
4. Процедура опирается на выбор единственного параметра — ширина полосы.
5. Размер полосы пропускания/окна h имеет физический смысл, не совпадающий с k-средним.

1. Выбор размера окна нетривиален.
2. Неподходящий размер окна может привести к слиянию мод или образованию дополнительных «теневых» мод.
3. Часто требуется использования самонастраиваемого размера окна.

Варианты алгоритма можно найти в пакетах обучения машин и обработки изображений:

• ELKI. Средства интеллектуального анализа данных на языке Java со многими алгоритмами кластеризации.
• ImageJ. Фильтрация изображений с помощью фильтра сдвига среднего значения.
• OpenCV содержит реализацию сдвига среднего значения с помощью метода cvMeanShift
• Инструментальный набор Orfeo. Реализация на языке C++.
• Scikit-learn. Реализация Numpy/Python использует шаровое дерево для эффективного просмотра соседних точек

• DBSCAN
• OPTICS
• Ядерная оценка плотности
• Ядро (статистика)