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

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

История

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

Обзор

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

$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)}}$

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

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

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

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

Детали

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

$K(x)={\begin{cases}1&\ \|x\|\leqslant \lambda \\0&\ \|x\|>\lambda \\\end{cases}}$

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

$f(x)=\sum _{i}K(x-x_{i})=\sum _{i}k\left({\frac {\|x-x_{i}\|^{2}}{h^{2}}}\right)$

,

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

Виды ядер

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

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

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

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

Плоское ядро

$k(x)={\begin{cases}1&\ x\leqslant \lambda \\0&\ x>\lambda \\\end{cases}}$

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

$k(x)=e^{-{\frac {x}{2\sigma ^{2}}}},$

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

Приложения

Кластеризация

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

Отслеживание

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

Сглаживание

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

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