Алгоритм FRiS-СТОЛП
Материал из MachineLearning.
м (уточнение) |
(→Вспомогательные функции: уточнение, оформление) |
||
Строка 21: | Строка 21: | ||
* «толерантность» объекта <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 /> | ||
Строка 28: | Строка 28: | ||
- | * <tex>NN(u,U)</tex> – возвращает ближайший к <tex>u</tex> объект из множества <tex>U</tex>. | + | * <tex>NN(u,U)</tex> – возвращает ближайший к <tex>u</tex> объект из множества <tex>U</tex>. |
===Описание алгоритма=== | ===Описание алгоритма=== |
Версия 22:47, 3 января 2010
Алгоритм FRiS-СТОЛП (FRiS-STOLP) - алгоритм отбора эталонных объектов для метрического классификатора на основе FRiS-функции.
Содержание |
Назначение алгоритма
Пусть дана обучающая выборка , где
- объекты,
- классы, которым принадлежат эти объекты. Кроме того, задана метрика
, такая, что выполняется гипотеза компактности.
Алгоритм
Входные данные
На вход алгоритм получает обучающую выборку
Результат
В результате работы алгоритма для каждого класса строятся множества эталонных объектов
.
Вспомогательные функции
В алгоритме FRiS-STOLP используются следующие вспомогательные функции:
-
– исходя из набора уже имеющихся эталонов
и набора
элементов класса
, возвращает новый эталон для класса
(алгоритм приведён ниже):
1. Для каждого объектавычисляются две характеристики: * «обороноспособность» объекта
:
![]()
* «толерантность» объекта(количественная оценка, насколько объект
в роли эталона класса
«не мешает» эталонам других классов):
![]()
2. На основании полученных характеристик вычисляется «эффективность» объекта:
![]()
3. Функция FindEtalon возвращает объектс максимальной эффективностью
:
![]()
-
– возвращает ближайший к
объект из множества
.
Описание алгоритма
Сам алгоритм FRiS-STOLP состит из следующих шагов:
1. Инициализировать начальные множества эталонов. Для всех классов:
![]()
2. Инициализировать искомые множества эталонов. Для всех классов:
![]()
3. Пока:
3.1 Сформировать множествоправильно классифицированных объектов:
– формируется множество правильно классифицированных объектов 3.2 Удалить правильно классифицированные объекты из дальнейшего рассмотрения:
для всех классов
;
; 3.3 Добавить новый эталон для каждого класса
:
4. Вернуть искомые множества эталонов
для каждого класса
![]()
Преимущества алгоритма
Алгоритм FRiS-STOLP создаёт в процессе работы сокращенное описание обучающей выборки. Это позволяет сократить описание выборки, избавиться от ошибок и «выбросов», содержащихся в ней, но при этом сохранить информацию, необходимую для дальнейшего распознавания новых объектов.
См. также
![]() | Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |