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

Машинное обучение и интеллектуальный анализ данных
Часть серии по

Проблемы Классификация Кластеризация Регресс Обнаружение аномалий AutoML Правила ассоциации Обучение с подкреплением Структурированный прогноз Функциональная инженерия Особенности обучения Онлайн обучение Полу-контролируемое обучение Обучение без учителя Учимся ранжировать Введение в грамматику
Обучение с учителем ( классификация • регрессия ) Деревья решений Ансамбли Упаковка Повышение Случайный лес k -NN Линейная регрессия Наивный байесовский Искусственные нейронные сети Логистическая регрессия Перцептрон Вектор релевантности (RVM) Машина опорных векторов (SVM)
Кластеризация БЕРЕЗА ИЗЛЕЧИВАТЬ Иерархический k -средство Ожидание – максимизация (EM) DBSCAN ОПТИКА Средний сдвиг
Снижение размерности Факторный анализ CCA ICA LDA NMF PCA PGD t-SNE
Структурированный прогноз Графические модели Сеть Байеса Условное случайное поле Скрытый Марков
Обнаружение аномалий k -NN Фактор местного выброса
Искусственная нейронная сеть Автоэнкодер Когнитивные вычисления Глубокое обучение DeepDream Многослойный перцептрон RNN LSTM ГРУ ESN Ограниченная машина Больцмана GAN SOM Сверточная нейронная сеть U-Net Трансформатор Пиковая нейронная сеть Мемтранзистор Электрохимическая RAM (ECRAM)
Обучение с подкреплением Q-обучение SARSA Временная разница (TD)
Теория Компромисс смещения и дисперсии Теория вычислительного обучения Минимизация эмпирического риска Обучение Оккама PAC обучение Статистическое обучение Теория ВК
Площадки для машинного обучения NeurIPS ICML ML JMLR ArXiv: cs.LG
Статьи по Теме Глоссарий искусственного интеллекта Список наборов данных для исследований в области машинного обучения Краткое описание машинного обучения
v т е

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

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

Методика среднего сдвига была первоначально представлена в 1975 году Фукунагой и Хостетлером. ^[3]

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

Средний сдвиг - это процедура определения максимумов - режимов - функции плотности при дискретных данных, выбранных из этой функции. ^[1] Это итерационный метод, и мы начинаем с начальной оценки . Пусть дана функция ядра . Эта функция определяет вес близлежащих точек для повторной оценки среднего. Обычно используется гауссовское ядро по расстоянию до текущей оценки . Средневзвешенное значение плотности в окне, определяемое как ${\ displaystyle x}$ ${\ displaystyle K (x_ {i} -x)}$ ${\ Displaystyle К (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)}}}

где - окрестность , множество точек для которой . $N(x)$ $x$ $K(x_{i})\neq 0$

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

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

Gaussian Mean-Shift - это алгоритм максимизации ожидания . ^[7]

Подробности [ править ]

Пусть данные конечное множество встроенных в n - мерном евклидовом пространстве . Пусть - плоское ядро, являющееся характеристической функцией -шара в , $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}$ , который может быть случайной точкой входных данных , средний сдвиг вычисляет градиент оценки плотности в точке и делает шаг вверх в этом направлении. ^[8] $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}}{2\sigma ^{2}}}},$

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

Приложения [ править ]

Кластеризация [ править ]

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

Отслеживание [ править ]

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

Сглаживание [ править ]

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

Сильные стороны [ править ]

Среднее смещение - это инструмент, не зависящий от приложения, подходящий для анализа реальных данных.
Не принимает никаких предопределенных форм на кластерах данных.
Он способен обрабатывать произвольные пространства функций.
Процедура основана на выборе одного параметра: пропускной способности.
Ширина полосы пропускания / размер окна 'h' имеет физический смысл, в отличие от k- средних .

Слабые стороны [ править ]

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

Доступность [ править ]

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

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

См. Также [ править ]

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

Ссылки [ править ]

^ а б Ченг, Ицзун (август 1995 г.). «Средний сдвиг, поиск режима и кластеризация». IEEE Transactions по анализу шаблонов и машинному анализу . 17 (8): 790–799. CiteSeerX 10.1.1.510.1222 . DOI : 10.1109 / 34.400568 .
^ Comaniciu, Дорин; Питер Меер (май 2002 г.). «Среднее смещение: надежный подход к анализу пространства признаков». IEEE Transactions по анализу шаблонов и машинному анализу . 24 (5): 603–619. CiteSeerX 10.1.1.160.3832 . DOI : 10.1109 / 34.1000236 .
^ a b Фукунага, Кейносукэ; Ларри Д. Хостетлер (январь 1975 г.). «Оценка градиента функции плотности с применением в распознавании образов». IEEE Transactions по теории информации . 21 (1): 32–40. DOI : 10.1109 / TIT.1975.1055330 .
^ a b Алияри Гассабех, Юнесс (2015-03-01). «Достаточное условие сходимости алгоритма среднего сдвига с гауссовым ядром» . Журнал многомерного анализа . 135 : 1–10. DOI : 10.1016 / j.jmva.2014.11.009 .
^ Aliyari Ghassabeh, Юнесс (2013-09-01). «О сходимости алгоритма среднего сдвига в одномерном пространстве». Письма о распознавании образов . 34 (12): 1423–1427. arXiv : 1407.2961 . DOI : 10.1016 / j.patrec.2013.05.004 . S2CID 10233475 .
^ Ли, Сянжу; Ху, Чжаньи; Ву, Фучао (01.06.2007). «Замечание о сходимости среднего сдвига». Распознавание образов . 40 (6): 1756–1762. DOI : 10.1016 / j.patcog.2006.10.016 .
^ Каррейра-Перпинан, Мигель А. (май 2007 г.). «Гауссовский средний сдвиг - это алгоритм ЭМ». IEEE Transactions по анализу шаблонов и машинному анализу . 29 (5): 767–776. DOI : 10.1109 / tpami.2007.1057 . ISSN 0162-8828 . PMID 17356198 . S2CID 6694308 .
^ Ричард Селиски, Компьютерное зрение, алгоритмы и приложения, Springer, 2011 г.
^ Comaniciu, Дорин; Вишванатан Рамеш; Питер Меер (май 2003 г.). «Отслеживание объектов на основе ядра». IEEE Transactions по анализу шаблонов и машинному анализу . 25 (5): 564–575. CiteSeerX 10.1.1.8.7474 . DOI : 10.1109 / tpami.2003.1195991 .
^ Авидан, Шай (2005). Ансамблевое сопровождение . Конференция компьютерного общества IEEE 2005 года по компьютерному зрению и распознаванию образов (CVPR'05) . 2 . Сан-Диего, Калифорния: IEEE. С. 494–501. DOI : 10,1109 / CVPR.2005.144 . ISBN 978-0-7695-2372-9. PMID 17170479 . S2CID 1638397 .
^ Гэри Брэдски (1998). Отслеживание лица с помощью компьютерного зрения для использования в перцепционном пользовательском интерфейсе. Архивировано 17 апреля 2012 г. в Wayback Machine , Intel Technology Journal, № Q2.
^ Emami, Ибрахим (2013). «Онлайн-обнаружение и исправление сбоев для алгоритма отслеживания CAMShift». 2013 8-я Иранская конференция по машинному зрению и обработке изображений (MVIP) . 2013 Иранская конференция по машинному зрению и обработке изображений (MVIP) . 2 . IEEE. С. 180–183. DOI : 10.1109 / IranianMVIP.2013.6779974 . ISBN 978-1-4673-6184-2. S2CID 15864761 .

[PAMI95-1] а б Ченг, Ицзун (август 1995 г.). «Средний сдвиг, поиск режима и кластеризация». IEEE Transactions по анализу шаблонов и машинному анализу . 17 (8): 790–799. CiteSeerX 10.1.1.510.1222 . DOI : 10.1109 / 34.400568 .

[PAMI02-2] Comaniciu, Дорин; Питер Меер (май 2002 г.). «Среднее смещение: надежный подход к анализу пространства признаков». IEEE Transactions по анализу шаблонов и машинному анализу . 24 (5): 603–619. CiteSeerX 10.1.1.160.3832 . DOI : 10.1109 / 34.1000236 .

[Fukunaga-3] Фукунага, Кейносукэ; Ларри Д. Хостетлер (январь 1975 г.). «Оценка градиента функции плотности с применением в распознавании образов». IEEE Transactions по теории информации . 21 (1): 32–40. DOI : 10.1109 / TIT.1975.1055330 .

[:0-4] Алияри Гассабех, Юнесс (2015-03-01). «Достаточное условие сходимости алгоритма среднего сдвига с гауссовым ядром» . Журнал многомерного анализа . 135 : 1–10. DOI : 10.1016 / j.jmva.2014.11.009 .

[5] Aliyari Ghassabeh, Юнесс (2013-09-01). «О сходимости алгоритма среднего сдвига в одномерном пространстве». Письма о распознавании образов . 34 (12): 1423–1427. arXiv : 1407.2961 . DOI : 10.1016 / j.patrec.2013.05.004 . S2CID 10233475 .

[6] Ли, Сянжу; Ху, Чжаньи; Ву, Фучао (01.06.2007). «Замечание о сходимости среднего сдвига». Распознавание образов . 40 (6): 1756–1762. DOI : 10.1016 / j.patcog.2006.10.016 .

[7] Каррейра-Перпинан, Мигель А. (май 2007 г.). «Гауссовский средний сдвиг - это алгоритм ЭМ». IEEE Transactions по анализу шаблонов и машинному анализу . 29 (5): 767–776. DOI : 10.1109 / tpami.2007.1057 . ISSN 0162-8828 . PMID 17356198 . S2CID 6694308 .

[8] Ричард Селиски, Компьютерное зрение, алгоритмы и приложения, Springer, 2011 г.

[PAMI03-9] Comaniciu, Дорин; Вишванатан Рамеш; Питер Меер (май 2003 г.). «Отслеживание объектов на основе ядра». IEEE Transactions по анализу шаблонов и машинному анализу . 25 (5): 564–575. CiteSeerX 10.1.1.8.7474 . DOI : 10.1109 / tpami.2003.1195991 .

[avidan2001-10] Авидан, Шай (2005). Ансамблевое сопровождение . Конференция компьютерного общества IEEE 2005 года по компьютерному зрению и распознаванию образов (CVPR'05) . 2 . Сан-Диего, Калифорния: IEEE. С. 494–501. DOI : 10,1109 / CVPR.2005.144 . ISBN 978-0-7695-2372-9. PMID 17170479 . S2CID 1638397 .

[11] Гэри Брэдски (1998). Отслеживание лица с помощью компьютерного зрения для использования в перцепционном пользовательском интерфейсе. Архивировано 17 апреля 2012 г. в Wayback Machine , Intel Technology Journal, № Q2.

[Emami2001-12] Emami, Ибрахим (2013). «Онлайн-обнаружение и исправление сбоев для алгоритма отслеживания CAMShift». 2013 8-я Иранская конференция по машинному зрению и обработке изображений (MVIP) . 2013 Иранская конференция по машинному зрению и обработке изображений (MVIP) . 2 . IEEE. С. 180–183. DOI : 10.1109 / IranianMVIP.2013.6779974 . ISBN 978-1-4673-6184-2. S2CID 15864761 .