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

Сдвиг среднего значения — это непараметрическая техника анализа пространства признаков для определения местоположения максимума плотности вероятности, так называемый алгоритм поиска моды^[1]. Область применения техники — кластерный анализ в компьютерном зрении и обработке изображений^[2].

Процедуру сдвига среднего значения представили в 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}$.

Рассмотрим набор точек в двухмерном пространстве. Рассмотрим круглое окно с центром в C с радиусом r в качестве ядра. Метод сдвига среднего значения является алгоритмом поиска экстремума, который сдвигает это ядро итеративно к области с большей плотностью, пока процесс не сойдётся. Любой сдвиг определяется вектором сдвига среднего значения. Вектор сдвига среднего значения всегда указывает в направлении максимального увеличения плотности. На каждой итерации ядро сдвигается к центру тяжести или среднему значению точек внутри его. Метод вычисления этого среднего зависит от выбора ядра. Если выбрано гауссово ядро вместо плоского ядра, то каждой точке будет назначен вес, который уменьшается экспоненциально по мере увеличения расстояния от центра ядра. Когда процесс сойдётся, не будет направления, в котором сдвиг может вместить больше точек внутрь ядра.

Алгоритм сдвига среднего значения можно использовать для визуального отслеживания. Простейший алгоритм такого рода мог бы создавать карту согласованности в новом изображении, основываясь на цветовой гистограмме объекта в предыдущем изображении, и использовать сдвиг среднего значения для нахождения пика карты согласованности рядом со старой позицией объекта. Карта согласованности является плотностью вероятности на новом изображении, назначающей каждой точке нового изображения вероятность, которая равна вероятности цвета точки объекта на предыдущем изображении. Несколько алгоритмов, таких как отслеживание на основе ядер^[8], ансамблевое отслеживание^[9], CAMshift^[10][11] расширяют эту идею.

Пусть ${\displaystyle x_{i}}$ будет d-мерным входом и ${\displaystyle z_{i},i=1,...,n,}$ будет отфильтрованными пикселями изображения в пространственных областях. Для каждого пикселя,

• Присваиваем начальные значения ${\displaystyle j=1}$ и ${\displaystyle y_{i,1}=x_{i}}$
• Вычисляем ${\displaystyle y_{i,j+1}}$ согласно ${\displaystyle m(\cdot )}$, пока не сойдётся, ${\displaystyle y=y_{i,c}}$.
• Назначаем ${\displaystyle z_{i}=(x_{i}^{s},y_{i,c}^{r})}$. Верхние индексы s и r означают пространственные и интервальные компоненты вектора соответственно. Назначение указывает, что отфильтрованные данные по пространственным осям будут иметь интервальную компоненту точки сходимости ${\displaystyle y_{i,c}^{r}}$.

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

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

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

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

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

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии. После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки.