Машинное обучение вики
Advertisement

Knn[]

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

Методы фильтрации[]

Удаление выбросов. Рассмотрим отступы и удалим все объекты, которые являются выбросами, т.е. .

— множество всех классов.

Алгоритм STOLP по версии Воронцова[]

Эталоны[]

  • Эталоны — это такое подмножество выборки , что все объекты (или их большая часть) классифицируются правильно при использовании в качестве обучающей выборки множества эталонов.
  • Эталонами -го класса при классификации методом ближайшего соседа может служить такое подмножество объектов этого класса, что расстояние от любого принадлежащего ему объекта из выборки до ближайшего «своего» эталона меньше, чем до ближайшего «чужого» эталона.

Простой перебор для отбора эталонов не эффективен, так как число способов выбора по эталонов для каждого класса (число классов ) составляет . Алгоритм STOLP позволяет сократить этот перебор

Величина риска[]

Величина риска () — величина, характеризующая степень риска для объекта быть классифицированным не в тот класс, которому он принадлежит.

  • При использовании метода ближайшего соседа можно считать , где  — расстояние от объекта до ближайшего к нему объекта (или эталона) из «своего» класса,  — до ближайшего объекта (или эталона) «чужого» класса.
  • При использовании любого метрического метода можно положить , где  — отступ на объекте при обучающей выборке , где  — множество эталонов.
DANGER! Это место вызывает
сомнения или непонимание!

Что такое Г?

Hard.png

Кроме того, в зависимости от используемого метода классификации можно подобрать и другие оценки величины риска. Главное, чтобы они принимали большие значения на объектах-выбросах, меньшие — на объектах, находящихся на границе класса, и еще меньшие — на объектах, находящихся в глубине своего класса.

Алгоритм STOLP[]

Вход[]

  • Выборка
  • Допустимая доля ошибок
  • Порог отсечения выбросов
  • Алгоритм классификации
  • Формула для вычисления величины риска

Описание алгоритма[]

  • Отбросить выбросы (объекты с )
  • Сформировать начальное приближение  — из объектов выборки выбрать по одному объекту каждого класса, обладающему среди объектов данного класса максимальной величиной риска либо минимальной величиной риска
  • Наращивание множества эталонов (пока доля числа объектов выборки , распознаваемых неправильно, не станет меньше ):
    • Классифицировать объекты , используя в качестве обучающей выборки
    • Пересчитать величины риска для всех объектов с учетом изменения обучающей выборки
    • Среди объектов каждого класса, распознанных неправильно, выбрать объекты с максимальной величиной риска и добавить их к

Результат[]

Множество эталонов для каждого класса представляет собой некоторый набор объектов, находящихся на границе класса, и, если в качестве начального приближения выбирались объекты с минимальной величиной риска, один объект, находящийся в центре класса.

Алгоритм удаления неинформативных объектов по версии Китова[]

Идея: удалить неинформативные объекты, которые не дают информации о классе, которому они принадлежат.

  • for each class #add the most
    • # representative example
  • Initialize etalons:
  • repeat while accuracy significantly increases
    • # add object
    • #with smallest margin
  • return

Краткое содержание: сначала добавляем объекты по одному на класс с наибольшим отступом. А потом, пока увеличивается точность, добавляем с наименьшим отступом.

Ссылки[]

Китовослайды

Алгоритм STOLP

Advertisement