Алгоритм FRiS-СТОЛП
Материал из MachineLearning.
Алгоритм 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 в учебном процессе. |