Алгоритм FRiS-СТОЛП
Материал из MachineLearning.
(Новая: {{Задание|osa|Константин Воронцов|25 января 2010}}) |
м (→Описание алгоритма) |
||
(18 промежуточных версий не показаны.) | |||
Строка 1: | Строка 1: | ||
- | {{Задание|osa|Константин Воронцов| | + | '''Алгоритм FRiS-СТОЛП''' (FRiS-STOLP) - алгоритм отбора [[Эталон|эталонных объектов]] для [[Метрический классификатор|метрического классификатора]] на основе [[FRiS-функция|FRiS-функции]]. |
+ | |||
+ | ==Назначение алгоритма== | ||
+ | Пусть дана [[Обучающая выборка|обучающая выборка]] <tex>X^l=(x_i, y_i)_{i=1}^l</tex>, где <tex>x_i</tex> - объекты, <tex>y_i=y^*(x_i)</tex> - классы, которым принадлежат эти объекты. Кроме того, задана [[Метрика|метрика]] <tex>\rho: X \times X \rightarrow \mathbb{R}</tex>, такая, что выполняется [[Гипотеза компактности|гипотеза компактности]]. | ||
+ | |||
+ | |||
+ | ==Алгоритм== | ||
+ | ===Входные данные=== | ||
+ | На вход алгоритм получает [[Обучающая выборка|обучающую выборку]] <tex>X^l=(x_i, y_i)_{i=1}^l</tex> | ||
+ | |||
+ | ===Результат=== | ||
+ | В результате работы алгоритма для каждого класса <tex>y \in Y</tex> строятся множества [[эталонный объект|эталонных объектов]] <tex>\Omega_y \subseteq X</tex>. | ||
+ | |||
+ | ===Вспомогательные функции=== | ||
+ | В алгоритме 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> (алгоритм приведён ниже): | ||
+ | |||
+ | 1. '''Для каждого объекта <tex>x \in X_y</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>x</tex> (количественная оценка, насколько объект <tex>x</tex> в роли эталона | ||
+ | класса <tex>y</tex> «не мешает» эталонам других классов): | ||
+ | <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>''': | ||
+ | <tex>E_x = \lambda D_x + (1-\lambda) T_x</tex> <br /> | ||
+ | 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>\lambda \in [0,1]</tex> количественно задаёт относительную «важность» характеристик объектов («обороноспособности» и «толерантности»). Может быть выбран, исходя из специфики конкретной задачи. | ||
+ | |||
+ | ===Описание алгоритма=== | ||
+ | Сам алгоритм FRiS-STOLP состоит из следующих шагов: | ||
+ | 1. '''Инициализировать начальные множества эталонов'''. Для всех классов <tex>y \in Y</tex>: | ||
+ | <tex>\Omega_y^0:=FindEtalon(X_y,X^l \setminus X_y)</tex> <br /> | ||
+ | 2. '''Инициализировать искомые множества эталонов'''. Для всех классов <tex>y \in Y</tex>: | ||
+ | <tex>\Omega_y:=FindEtalon(X_y,\bigcup_{c \in Y \setminus y} \Omega_c^0)</tex> <br /> | ||
+ | 3. '''Повторять пункты 4-6''', пока множество рассматриваемых объектов непусто <tex>\left( X^l \not= \emptyset \right)</tex>: <br /> | ||
+ | 4. '''Сформировать множество <tex>U</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>; | ||
+ | 5. '''Удалить правильно классифицированные объекты из дальнейшего рассмотрения''': <br /> | ||
+ | * '''из множеств эталонов''': для каждого <tex>y \in Y:</tex> <tex>X_y:=X_y \setminus U</tex>; | ||
+ | * '''из обучающей выборки''': <tex>X^l:=X^l \setminus U</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><br /><br /> | ||
+ | 7. '''Вернуть искомые множества эталонов''' <tex>\Omega_y</tex> для каждого класса <tex>y \in Y</tex> | ||
+ | |||
+ | ==Преимущества алгоритма== | ||
+ | |||
+ | Алгоритм FRiS-STOLP создаёт в процессе работы сокращенное описание обучающей выборки. Это позволяет сократить расход памяти, избавиться от ошибок и [[выбросы|выбросов]], содержащихся в ней, но при этом сохранить информацию, необходимую для дальнейшего распознавания новых объектов. | ||
+ | |||
+ | ==См. также== | ||
+ | |||
+ | * [[Алгоритм СТОЛП]] | ||
+ | * [[FRiS-функция]] | ||
+ | |||
+ | |||
+ | {{Задание|osa|Константин Воронцов|21 января 2010}} | ||
+ | |||
+ | [[Категория:Метрические алгоритмы классификации]] |
Текущая версия
Алгоритм FRiS-СТОЛП (FRiS-STOLP) - алгоритм отбора эталонных объектов для метрического классификатора на основе FRiS-функции.
Содержание |
Назначение алгоритма
Пусть дана обучающая выборка , где - объекты, - классы, которым принадлежат эти объекты. Кроме того, задана метрика , такая, что выполняется гипотеза компактности.
Алгоритм
Входные данные
На вход алгоритм получает обучающую выборку
Результат
В результате работы алгоритма для каждого класса строятся множества эталонных объектов .
Вспомогательные функции
В алгоритме FRiS-STOLP используются следующие вспомогательные функции:
- – возвращает ближайший к объект из множества .
- – исходя из набора уже имеющихся эталонов и набора элементов класса , возвращает новый эталон для класса (алгоритм приведён ниже):
1. Для каждого объекта вычисляются две характеристики: * «обороноспособность» объекта :
* «толерантность» объекта (количественная оценка, насколько объект в роли эталона класса «не мешает» эталонам других классов):
2. На основании полученных характеристик вычисляется «эффективность» объекта :
3. Функция FindEtalon возвращает объект с максимальной эффективностью :
Параметр количественно задаёт относительную «важность» характеристик объектов («обороноспособности» и «толерантности»). Может быть выбран, исходя из специфики конкретной задачи.
Описание алгоритма
Сам алгоритм FRiS-STOLP состоит из следующих шагов:
1. Инициализировать начальные множества эталонов. Для всех классов :
2. Инициализировать искомые множества эталонов. Для всех классов :
3. Повторять пункты 4-6, пока множество рассматриваемых объектов непусто :
4. Сформировать множество правильно классифицированных объектов: ; 5. Удалить правильно классифицированные объекты из дальнейшего рассмотрения:
* из множеств эталонов: для каждого ; * из обучающей выборки: ;
6. Добавить новый эталон для каждого класса :
7. Вернуть искомые множества эталонов для каждого класса
Преимущества алгоритма
Алгоритм FRiS-STOLP создаёт в процессе работы сокращенное описание обучающей выборки. Это позволяет сократить расход памяти, избавиться от ошибок и выбросов, содержащихся в ней, но при этом сохранить информацию, необходимую для дальнейшего распознавания новых объектов.
См. также
Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |