WikiSort.ru - Не сортированное

Машинное обучение и data mining

Задачи Задача классификации Обучение без учителя Обучение с частичным привлечением учителя Регрессионный анализ AutoML Ассоциативные правила Выделение признаков Обучение признакам Обучение ранжированию Грамматический вывод Онлайновое обучение

Обучение с учителем Метод k-ближайших соседей Наивный байесовский классификатор Дерево решений Метод опорных векторов Линейная регрессия Логистическая регрессия Перцептрон Ансамбли моделей (Бэггинг, Бустинг, Random forest) Метод релевантных векторов

Кластерный анализ Метод k-средних Метод нечёткой кластеризации Иерархическая кластеризация EM-алгоритм BIRCH CURE DBSCAN OPTICS Mean-shift

Снижение размерности Факторный анализ Метод главных компонент CCA ICA LDA Неотрицательное матричное разложение t-SNE

Структурное прогнозирование Графовая вероятностная модель (Байесовская сеть, Скрытая марковская модель, CRF)

Выявление аномалий Метод k-ближайших соседей Локальный уровень выброса

Графовые вероятностные модели Байесовская сеть Марковская сеть Скрытая марковская модель

Искусственные нейронные сети Ограниченная машина Больцмана Самоорганизующаяся карта Функция активации (Сигмоида, Softmax, Радиально-базисная функция) Метод обратного распространения ошибки Глубокое обучение Многослойный перцептрон Рекуррентная нейронная сеть (Долгая краткосрочная память, Управляемый рекуррентный блок) Свёрточная нейронная сеть (U-Net) Автокодировщик

Обучение с подкреплением Марковский процесс Уравнение Беллмана Жадный алгоритм Q-learning SARSA Temporal difference (TD)

Теория Теория Вапника — Червоненкиса Дилемма смещения–дисперсии Теория вычислительного обучения Минимизация эмпирического риска Оккамово обучение PAC learning Статистическая теория обучения

Журналы и конференции NIPS ICML ML JMLR ArXiv:cs.LG

Глоссарий Глоссарий по машинному обучению

Статьи по теме List of datasets for machine-learning research Outline of machine learning

Сдвиг среднего значения — это непараметрическая техника анализа пространства признаков для определения местоположения максимума плотности вероятности, так называемый алгоритм поиска моды^[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}$ .

Приложения

Сильные стороны

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

Недостатки

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

Доступность

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

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

См. также

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

Примечания

Литература

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