Алгоритм 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 в учебном процессе. |