Тупиковые тесты
Материал из MachineLearning.
Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |
Алгоритм вычисления оценки, в котором множество опорных множеств является множеством всех тупиковых тестов, называется тестовым алгоритмом. Первый вариант таких АВО был предложен Ю.И. Журавлевым. АВО совмещают метрические и логические принципы классификации. От метрических алгоритмов АВО наследует принцип оценивания сходства через введение множества метрик , а от логических принцип поиска конъюнктивных закономерностей, конъюнкции строятся не над бинарными признаками , а над бинарными функциями близости вида . В этом случае каждой закономерности соответствует не подмножество признаков, а подмножество метрик, называемое опорным множеством. Как правило одного опорного множества недостаточно, поэтому в АВО применяется взвешенное голосование по системе опорных множеств.
Содержание |
Описание АВО, основанных на тупиковых тестах
Формулировка задачи
Задача распознавания: - множество непересекающихся классов объектов.
Первоначальная информация (обучающая) и описание некоторого объекта , .
Объект задается через набор числовых признаков .
Задача распознавания состоит в определении включения заданного объекта в классы .
В случае АВО, основанных на тупиковых тестах, начальная информация задается таблицей:
- - таблица признаков объектов в обучающей выборке;
- - описание объекта из обучающей выборки;
- - выражение, определяющее включение объектов в классы;
Алгоритм распознавания, где .
Строение АВО
- - система опорных множеств;
- Вводится функция близости для двух объектов по опорному множеству :
где неотрицательные числа, называемые порогами,
- Вводится оценка близости объекта к классу
- Вычисление алгоритма проводится по правилу:
- пороги осторожности.
Строение АВО, основанного на тупиковых тестах
- Вводится система опорных множеств ;
- Задается функция близости для двух объектов по опорному множеству :
. Если , объекты не являются близкими по опорному множеству.
Тестом называется набор столбцов таблицы обучения с номерами , если любые два объекта, принадлежащие разным классам , не являются близкими по опорному множеству .
Тупиковым тестом называется тест, у которого его собственное подмножество не является таковым.