Участник:LuarSoll/Песочница
Материал из MachineLearning.
Алгоритм СТОЛП (STOLP) - алгоритм отбора эталонных объектов для метрического классификатора; алгоритм минимизации набора эталонов.
Задача
Дана выборка . Необходимо оставить в качестве обучающей выборки только ее часть, то есть построить множество эталонов, не менее чем по одному эталону на класс.
Эталоны
- Эталонами для i-го класса могут служить такие объекты этого класса, что расстояние от любого принадлежащего ему объекта из обучающей выборки расстояние до ближайшего "своего" эталона больше, чем расстояние до ближайшего "чужого" эталона, то есть все объекты обучающей выборки классифицируются правильно по набору эталонов.
- Иначе эталон можно определить как объект с большим положительным отступом.
Простой перебор для отбора эталонов не подходит, так как число способов выбора по t эталонов для каждого класса (число классов k) составляет . Но перебор вариантов можно сократить при помощи алгоритма STOLP
Суть алгоритма STOLP
- Первый шаг: отбросить выбросы (то есть элементы выборки с отступом, меньшим некоторой константы δ)
- Второй шаг: сформировать начальное приближение
- Третий шаг: "жадное" наращивание множества эталонов, пока число ошибок станет не меньше некоторой константы l0
