Средний сдвиг

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

История

Процедуру среднего сдвига обычно приписывают работе Фукунаги и Хостетлера в 1975 году. Однако это напоминает более раннюю работу Шнелла 1964 года.

Обзор

Сдвиг среднего — это процедура определения максимумов ( мод ) функции плотности с учетом дискретных данных, выбранных из этой функции. Это итерационный метод, и мы начинаем с начальной оценки $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}-x)\neq 0$.

Разница $m(x)-x$ называется сдвигом среднего по Фукунаге и Хостетлеру. Алгоритм среднего сдвига теперь устанавливает $x\leftarrow m(x)$, и повторяет оценку до тех пор, пока $m(x)$ сходится.

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

Гауссовский средний сдвиг — это алгоритм максимизации ожиданий .

Подробности

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

$K(x)={\begin{cases}1&{\text{if}}\ \|x\|\leq \lambda \\0&{\text{if}}\ \|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$-мерное евклидово пространство, $\mathbb {R} ^{n}$. Норма $x$ является неотрицательным числом, $\|x\|^{2}=x^{\top }x\geq 0$. Функция $K:X\rightarrow \mathbb {R}$ называется ядром, если существует профиль , $k:[0,\infty ]\rightarrow \mathbb {R}$ , такой, что

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

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

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

Плоское ядро

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

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

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

где параметр стандартного отклонения $\sigma$ работает как параметр пропускной способности, $h$.

Приложения

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

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

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

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

Сглаживание

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

• Инициализировать $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 -means .

Слабые стороны

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

Наличие

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

• ЭЛКИ . Инструмент интеллектуального анализа данных Java со множеством алгоритмов кластеризации.
• ИзображениеДж . Фильтрация изображений с использованием фильтра среднего сдвига.
• млпак . Эффективная реализация на основе алгоритма двойного дерева.
• OpenCV содержит реализацию среднего сдвига с помощью метода cvMeanShift.
• Набор инструментов Орфео . Реализация C++.
• scikit-learn Реализация Numpy/Python использует дерево шариков для эффективного поиска соседних точек

См. также

• DBSCAN
• Алгоритм ОПТИКА
• Оценка плотности ядра (KDE)
• Ядро (статистика)