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

Knn

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

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

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

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

Эталоны

• Эталоны — это такое подмножество выборки $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 \mathbb {Y} \setminus y_{i}}\Gamma _{y}(x_{i})$ — отступ на объекте $x_{i}$ при обучающей выборке $\Omega$, где $\Omega$ — множество эталонов.

DANGER! Это место вызывает сомнения или непонимание! Что такое Г?

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

Алгоритм STOLP

Вход

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

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

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

Результат

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

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

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

• for each class $c=1,2,\ldots C$ #add the most
  • $x(c)=\mathrm {arg} \max _{x_{i}:c_{i}=c}(M(x_{i},c_{i}))$ # representative example

• Initialize etalons: $\Omega =\{x(c),c=1,2,\ldots C\}$
• repeat while accuracy significantly increases
  • $x_{i}=\mathrm {arg} \max _{x_{i}\in TS\backslash \Omega }(M(x,\Omega ))$ # add object
  • $\Omega =\Omega \cup \{x_{i}\}$ #with smallest margin
• return $\Omega$

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

Ссылки

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

Алгоритм STOLP