Алгоритм FRiS-СТОЛП
Материал из MachineLearning.
(оформление) |
м (→Вспомогательные функции) |
||
Строка 18: | Строка 18: | ||
* <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 /> | ||
Строка 24: | Строка 24: | ||
класса <tex>y</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 /> | <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 /> | ||
Версия 18:57, 19 января 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 в учебном процессе. |