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

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

История[править | править код]

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

Обзор[править | править код]

Сдвиг среднего значения является процедурой для определения местоположения максимумов (мод) плотности вероятности, задаваемой дискретной выборкой по этой функции^[1]. Метод является итеративным, и мы начинаем с начальной оценки ${\displaystyle x}$. Пусть будет задана ядерная функция ${\displaystyle K(x_{i}-x)}$. Эта функция определяет вес ближайших точек для переоценки среднего. Обычно используется гауссово ядро^[en] от расстояния до текущей оценки ${\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^[en]. Средства интеллектуального анализа данных на языке Java со многими алгоритмами кластеризации.
• ImageJ. Фильтрация изображений с помощью фильтра сдвига среднего значения.
• OpenCV содержит реализацию сдвига среднего значения с помощью метода cvMeanShift
• Инструментальный набор Orfeo^[en]. Реализация на языке C++.
• Scikit-learn. Реализация Numpy/Python использует шаровое дерево^[en] для эффективного просмотра соседних точек

См. также[править | править код]

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

Примечания[править | править код]

Литература[править | править код]

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