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

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

(Различия между версиями)
Перейти к: навигация, поиск
м (уточнение)
м (→Описание алгоритма)
 
(15 промежуточных версий не показаны.)
Строка 14: Строка 14:
===Вспомогательные функции===
===Вспомогательные функции===
В алгоритме FRiS-STOLP используются следующие вспомогательные функции:
В алгоритме FRiS-STOLP используются следующие вспомогательные функции:
 +
 +
* <tex>NN(u,U)</tex> – возвращает ближайший к <tex>u</tex> объект из множества <tex>U</tex>.
* <tex>FindEtalon(X_y;\Omega)</tex> – исходя из набора уже имеющихся эталонов <tex>\Omega</tex> и набора <tex>X_y</tex> элементов класса <tex>Y</tex>, возвращает новый эталон для класса <tex>Y</tex> (алгоритм приведён ниже):
* <tex>FindEtalon(X_y;\Omega)</tex> – исходя из набора уже имеющихся эталонов <tex>\Omega</tex> и набора <tex>X_y</tex> элементов класса <tex>Y</tex>, возвращает новый эталон для класса <tex>Y</tex> (алгоритм приведён ниже):
-
1. Для каждого объекта <tex>x \in X_y</tex> вычисляются две характеристики:
+
1. '''Для каждого объекта <tex>x \in X_y</tex> вычисляются две характеристики''':
* «обороноспособность» объекта <tex>x</tex>:
* «обороноспособность» объекта <tex>x</tex>:
<tex>D_x = \frac{1}{\left| X_y \right| -1}\sum_{u \in X_y \setminus x}S \left(u,x | NN(u,\Omega) \right)</tex> <br />
<tex>D_x = \frac{1}{\left| X_y \right| -1}\sum_{u \in X_y \setminus x}S \left(u,x | NN(u,\Omega) \right)</tex> <br />
* «толерантность» объекта <tex>x</tex> (количественная оценка, насколько объект <tex>x</tex> в роли эталона
* «толерантность» объекта <tex>x</tex> (количественная оценка, насколько объект <tex>x</tex> в роли эталона
класса <tex>y</tex> «не мешает» эталонам других классов):
класса <tex>y</tex> «не мешает» эталонам других классов):
-
<tex>T_x = \frac{1}{\left| X^l \setminus X_y \right|}\sum_{v \in X^l \setminus X_y}S \left(v,x | NN(v,\Omega) \right)</tex> <br />
+
<tex>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)</tex> <br />
-
2. На основании полученных характеристик вычисляется «эффективность» объекта <tex>x</tex>:
+
2. '''На основании полученных характеристик вычисляется «эффективность» объекта <tex>x</tex>''':
<tex>E_x = \lambda D_x + (1-\lambda) T_x</tex> <br />
<tex>E_x = \lambda D_x + (1-\lambda) T_x</tex> <br />
-
3. Функция FindEtalon возвращает объект <tex>x \in X^l</tex> с максимальной эффективностью <tex>E_x</tex>:
+
3. '''Функция FindEtalon возвращает объект <tex>x \in X^l</tex> с максимальной эффективностью''' <tex>E_x</tex>:
<tex>x:=arg\max_{x \in X_y}{E_x}</tex> <br />
<tex>x:=arg\max_{x \in X_y}{E_x}</tex> <br />
-
 
+
Параметр <tex>\lambda \in [0,1]</tex> количественно задаёт относительную «важность» характеристик объектов («обороноспособности» и «толерантности»). Может быть выбран, исходя из специфики конкретной задачи.
-
* <tex>NN(u,U)</tex> – возвращает ближайший к <tex>u</tex> объект из множества <tex>U</tex>.
+
===Описание алгоритма===
===Описание алгоритма===
-
Сам алгоритм FRiS-STOLP состит из следующих шагов:
+
Сам алгоритм FRiS-STOLP состоит из следующих шагов:
-
1. Инициализировать начальные множества эталонов. Для всех классов <tex>y \in Y</tex>:
+
1. '''Инициализировать начальные множества эталонов'''. Для всех классов <tex>y \in Y</tex>:
<tex>\Omega_y^0:=FindEtalon(X_y,X^l \setminus X_y)</tex> <br />
<tex>\Omega_y^0:=FindEtalon(X_y,X^l \setminus X_y)</tex> <br />
-
2. Инициализировать искомые множества эталонов. Для всех классов <tex>y \in Y</tex>:
+
2. '''Инициализировать искомые множества эталонов'''. Для всех классов <tex>y \in Y</tex>:
<tex>\Omega_y:=FindEtalon(X_y,\bigcup_{c \in Y \setminus y} \Omega_c^0)</tex> <br />
<tex>\Omega_y:=FindEtalon(X_y,\bigcup_{c \in Y \setminus y} \Omega_c^0)</tex> <br />
-
3. Пока <tex>X^l \not= \emptyset</tex>: <br />
+
3. '''Повторять пункты 4-6''', пока множество рассматриваемых объектов непусто <tex>\left( X^l \not= \emptyset \right)</tex>: <br />
-
3.1 Сформировать множество <tex>U</tex> правильно классифицированных объектов:
+
4. '''Сформировать множество <tex>U</tex> правильно классифицированных объектов''':
-
<tex>U:= \{ x \in X^l | S(x,NN(x_i,\Omega_{y_i})| NN(x_i, \bigcup_{y \not= y_i}{\Omega_y}) > \theta </tex> – формируется множество правильно классифицированных объектов
+
<tex>U:=</tex> <tex> \{ x \in X^l | S(x,NN(x_i,\Omega_{y_i})| NN(x_i, \bigcup_{y \not= y_i}{\Omega_y}) > \theta \} </tex>;
-
3.2 Удалить правильно классифицированные объекты из дальнейшего рассмотрения: <br />
+
5. '''Удалить правильно классифицированные объекты из дальнейшего рассмотрения''': <br />
-
<tex>X_y:=X_y \setminus U</tex> для всех классов <tex>y \in Y</tex>;
+
* '''из множеств эталонов''': для каждого <tex>y \in Y:</tex> <tex>X_y:=X_y \setminus U</tex>;
-
<tex>X_l:=X_l \setminus U</tex>;
+
* '''из обучающей выборки''': <tex>X^l:=X^l \setminus U</tex>; <br />
-
3.3 Добавить новый эталон для каждого класса <tex>y \in Y</tex>: <br />
+
6. '''Добавить новый эталон для каждого класса <tex>y \in Y</tex>''': <br />
-
<tex>\Omega_y:=\Omega_y \cup FindEtalon(X_y,\bigcup_{c \in Y \setminus y}{\Omega_c})</tex>
+
<tex>\Omega_y:=\Omega_y \cup FindEtalon(X_y,\bigcup_{c \in Y \setminus y}{\Omega_c})</tex><br /><br />
-
4. Вернуть искомые множества эталонов <tex>\Omega_y</tex> для каждого класса <tex>y \in Y</tex>
+
7. '''Вернуть искомые множества эталонов''' <tex>\Omega_y</tex> для каждого класса <tex>y \in Y</tex>
==Преимущества алгоритма==
==Преимущества алгоритма==
-
Алгоритм FRiS-STOLP создаёт в процессе работы сокращенное описание обучающей выборки. Это позволяет сократить описание выборки, избавиться от ошибок и «выбросов», содержащихся в ней, но при этом сохранить информацию, необходимую для дальнейшего распознавания новых объектов.
+
Алгоритм FRiS-STOLP создаёт в процессе работы сокращенное описание обучающей выборки. Это позволяет сократить расход памяти, избавиться от ошибок и [[выбросы|выбросов]], содержащихся в ней, но при этом сохранить информацию, необходимую для дальнейшего распознавания новых объектов.
==См. также==
==См. также==
-
[[Алгоритм СТОЛП]]
+
* [[Алгоритм СТОЛП]]
 +
* [[FRiS-функция]]
-
[[FRiS-функция]]
 
 +
{{Задание|osa|Константин Воронцов|21 января 2010}}
-
{{Задание|osa|Константин Воронцов|25 января 2010}}
+
[[Категория:Метрические алгоритмы классификации]]

Текущая версия

Алгоритм 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 используются следующие вспомогательные функции:

  • NN(u,U) – возвращает ближайший к u объект из множества U.
  • 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}

Параметр \lambda \in [0,1] количественно задаёт относительную «важность» характеристик объектов («обороноспособности» и «толерантности»). Может быть выбран, исходя из специфики конкретной задачи.

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

Сам алгоритм 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. Повторять пункты 4-6, пока множество рассматриваемых объектов непусто \left( X^l \not= \emptyset \right): 

  4. Сформировать множество 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 \} ;
  5. Удалить правильно классифицированные объекты из дальнейшего рассмотрения: 

        * из множеств эталонов: для каждого y \in Y: X_y:=X_y \setminus U;
        * из обучающей выборки: X^l:=X^l \setminus U; 

  6. Добавить новый эталон для каждого класса y \in Y:  

        \Omega_y:=\Omega_y \cup FindEtalon(X_y,\bigcup_{c \in Y \setminus y}{\Omega_c})


7. Вернуть искомые множества эталонов \Omega_y для каждого класса y \in Y

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

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

См. также


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

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

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

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_FRiS-%D0%A1%D0%A2%D0%9E%D0%9B%D0%9F»
Личные инструменты