Алгоритм FRiS-СТОЛП

Материал из MachineLearning.

Перейти к: навигация, поиск

Алгоритм FRiS-СТОЛП (FRiS-STOLP) - алгоритм отбора эталонных объектов для метрического классификатора на основе FRiS-функции.

Содержание

Назначение алгоритма

Пусть дана обучающая выборка X^l=(x_i, y_i)_{i=1}^l, где x_i - объекты, y_i=y^*(x_i) - классы, которым принадлежат эти объекты. Кроме того, задана метрика \rho: X \times X \rightarrow \mathbb{R}, такая, что выполняется гипотеза компактности.


Алгоритм

Входные данные

На вход алгоритм получает обучающую выборку X^l=(x_i, y_i)_{i=1}^l

Результат

В результате работы алгоритма для каждого класса y \in Y строятся множества эталонных объектов \Omega_y \subseteq X.

Вспомогательные функции

В алгоритме FRiS-STOLP используются следующие вспомогательные функции:

  • FindEtalon(X_y;\Omega) – исходя из набора уже имеющихся эталонов \Omega и набора X_y элементов класса Y, возвращает новый эталон для класса Y (алгоритм приведён ниже):
1. Для каждого объекта x \in X_y вычисляются две характеристики:
   * «обороноспособность» объекта x: 
        D_x = \frac{1}{\left| X_y \right| -1}\sum_{u \in X_y \setminus x}S \left(u,x | NN(u,\Omega) \right)  
* «толерантность» объекта x (количественная оценка, насколько объект x в роли эталона класса y «не мешает» эталонам других классов): T_x = \frac{1}{\left| X^l \setminus X_y \right|}\left(\sum_{v \in X^l \setminus X_y}S \left(v,x | NN(v,\Omega) \right)\right)
2. На основании полученных характеристик вычисляется «эффективность» объекта x: E_x = \lambda D_x + (1-\lambda) T_x
3. Функция FindEtalon возвращает объект x \in X^l с максимальной эффективностью E_x: x:=arg\max_{x \in X_y}{E_x}


  • NN(u,U) – возвращает ближайший к u объект из множества U.

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

Сам алгоритм FRiS-STOLP состит из следующих шагов:

1. Инициализировать начальные множества эталонов. Для всех классов y \in Y: 
    \Omega_y^0:=FindEtalon(X_y,X^l \setminus X_y) 
2. Инициализировать искомые множества эталонов. Для всех классов y \in Y: \Omega_y:=FindEtalon(X_y,\bigcup_{c \in Y \setminus y} \Omega_c^0)
3. Пока X^l \not= \emptyset:
3.1 Сформировать множество U правильно классифицированных объектов: U:= \{ x \in X^l | S(x,NN(x_i,\Omega_{y_i})| NN(x_i, \bigcup_{y \not= y_i}{\Omega_y}) > \theta – формируется множество правильно классифицированных объектов 3.2 Удалить правильно классифицированные объекты из дальнейшего рассмотрения:
X_y:=X_y \setminus U для всех классов y \in Y; X_l:=X_l \setminus U; 3.3 Добавить новый эталон для каждого класса y \in Y:
\Omega_y:=\Omega_y \cup FindEtalon(X_y,\bigcup_{c \in Y \setminus y}{\Omega_c}) 4. Вернуть искомые множества эталонов \Omega_y для каждого класса y \in Y

Преимущества алгоритма

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

См. также

Алгоритм СТОЛП

FRiS-функция


Данная статья является непроверенным учебным заданием.
Студент: Участник:osa
Преподаватель: Участник:Константин Воронцов
Срок: 25 января 2010

До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.


Личные инструменты