Методы фильтрации обучающей выборки

Knn

Не требует обучения

Сложность предсказания $O(KD)$

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

Удаление выбросов. Рассмотри отступы $M(x_{i},c_{j})=g_{c_{j}}(x_{i})-{\underset {c\in {\textbf {C}}\backslash \{c_{j}\}}{max}}g_{c}(x_{i})$ и удалим все объекты, которые являются выбросами, т.е. ${x_{i}:M(x_{i},c_{j})}$

${\textbf {C}}$ - множество всех классов.

Алгоритм STOLP

Эталоны

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

Простой перебор для отбора эталонов не эффективен, так как число способов выбора по t эталонов для каждого класса (число классов k) составляет $\prod _{j=1}^{k}C_{m_{j}}^{t}$. Алгоритм STOLP позволяет сократить этот перебор

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

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

• При использовании метода ближайшего соседа можно считать $W(x_{i})=\rho _{in}(x_{i})/\rho _{out}(x_{i})$, где $\rho _{in}$ — расстояние от объекта $x_i$ до ближайшего к нему объекта (или эталона) из «своего» класса, $\rho _{out}$ — до ближайшего объекта (или эталона) «чужого» класса.
• При использовании любого метрического метода можно положить $W(x_{i})=-M(x_{i},\Omega )$, где $M(x_{i},\Omega )=\Gamma _{y_{i}}-\max _{y\in Y\setminus y_{i}}\Gamma _{y}(x_{i})$ — отступ на объекте $x_i$ при обучающей выборке $\Omega$, где $\Omega$ — множество эталонов.

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

Алгоритм STOLP

Вход

• Выборка $X^{l}$
• Допустимая доля ошибок $l_0$
• Порог отсечения выбросов δ
• Алгоритм классификации
• Формула для вычисления величины риска W.

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

• Отбросить выбросы (объекты $X^{l}$ с W>δ)
• Сформировать начальное приближение $\Omega$ — из объектов выборки $X^{l}$ выбрать по одному объекту каждого класса, обладающему среди объектов данного класса максимальной величиной риска либо минимальной величиной риска
• Наращивание множества эталонов (пока число объектов выборки $X^{l}$, распознаваемых неправильно, не станет меньше $l_0$):
  • Классифицировать объекты $X^{l}$, используя в качестве обучающей выборки $\Omega$
  • Пересчитать величины риска для всех объектов $X^{l}\setminus \Omega$ с учетом изменения обучающей выборки
  • Среди объектов каждого класса, распознанных неправильно, выбрать объекты с максимальной величиной риска и добавить их к $\Omega$

Результат

Множество эталонов $\Omega \in X^{l}$ для каждого класса представляет собой некоторый набор объектов, находящихся на границе класса, и, если в качестве начального приближения выбирались объекты с минимальной величиной риска, один объект, находящийся в центре класса.