Содержание
Knn[]
Метод ближайших соседей не требует обучения, Сложность предсказания . При большом количестве объектов возникает проблема, связанная с большим объемом вычислений для нахождения ближайшего соседа для распознаваемого объекта. Для борьбы с этой проблемой могут применяться методы фильтрации обучающей выборки или же структуризация пространства.
Методы фильтрации[]
Удаление выбросов. Рассмотрим отступы и удалим все объекты, которые являются выбросами, т.е. .
— множество всех классов.
Алгоритм STOLP по версии Воронцова[]
Эталоны[]
- Эталоны — это такое подмножество выборки , что все объекты (или их большая часть) классифицируются правильно при использовании в качестве обучающей выборки множества эталонов.
- Эталонами методом ближайшего соседа может служить такое подмножество объектов этого класса, что расстояние от любого принадлежащего ему объекта из выборки до ближайшего «своего» эталона меньше, чем до ближайшего «чужого» эталона. -го класса при классификации
Простой перебор для отбора эталонов не эффективен, так как число способов выбора по
эталонов для каждого класса (число классов ) составляет . Алгоритм STOLP позволяет сократить этот переборВеличина риска[]
Величина риска (
) — величина, характеризующая степень риска для объекта быть классифицированным не в тот класс, которому он принадлежит.- При использовании метода ближайшего соседа можно считать , где — расстояние от объекта до ближайшего к нему объекта (или эталона) из «своего» класса, — до ближайшего объекта (или эталона) «чужого» класса.
- При использовании любого метрического метода можно положить , где — отступ на объекте при обучающей выборке , где — множество эталонов.
DANGER! Это место вызывает сомнения или непонимание! Что такое Г? |
![]() |
Кроме того, в зависимости от используемого метода классификации можно подобрать и другие оценки величины риска. Главное, чтобы они принимали большие значения на объектах-выбросах, меньшие — на объектах, находящихся на границе класса, и еще меньшие — на объектах, находящихся в глубине своего класса.
Алгоритм STOLP[]
Вход[]
- Выборка
- Допустимая доля ошибок
- Порог отсечения выбросов
- Алгоритм классификации
- Формула для вычисления величины риска
Описание алгоритма[]
- Отбросить выбросы (объекты с )
- Сформировать начальное приближение — из объектов выборки выбрать по одному объекту каждого класса, обладающему среди объектов данного класса максимальной величиной риска либо минимальной величиной риска
- Наращивание множества эталонов (пока доля числа объектов выборки
- Классифицировать объекты , используя в качестве обучающей выборки
- Пересчитать величины риска для всех объектов с учетом изменения обучающей выборки
- Среди объектов каждого класса, распознанных неправильно, выбрать объекты с максимальной величиной риска и добавить их к
, распознаваемых неправильно, не станет меньше ):
Результат[]
Множество эталонов
для каждого класса представляет собой некоторый набор объектов, находящихся на границе класса, и, если в качестве начального приближения выбирались объекты с минимальной величиной риска, один объект, находящийся в центре класса.Алгоритм удаления неинформативных объектов по версии Китова[]
Идея: удалить неинформативные объекты, которые не дают информации о классе, которому они принадлежат.
- for each class
- # representative example
#add the most
- Initialize etalons:
- repeat while accuracy significantly increases
- # add object
- #with smallest margin
- return
Краткое содержание: сначала добавляем объекты по одному на класс с наибольшим отступом. А потом, пока увеличивается точность, добавляем с наименьшим отступом.