Тупиковые тесты
Материал из MachineLearning.
м |
м (→Построение тупиковых тестов) |
||
Строка 82: | Строка 82: | ||
#Пусть <tex>i=h, \ U_i=\{1,2,\ldots,h\}</tex>, задача построения множества всех тупиковых тестов таблицы <tex>T_{nml}</tex> сводится к построению множества всех неприводимых покрытий матрицы <tex>L_{nml}</tex>. В этом случае используется детерминированный алгоритм. | #Пусть <tex>i=h, \ U_i=\{1,2,\ldots,h\}</tex>, задача построения множества всех тупиковых тестов таблицы <tex>T_{nml}</tex> сводится к построению множества всех неприводимых покрытий матрицы <tex>L_{nml}</tex>. В этом случае используется детерминированный алгоритм. | ||
#Пусть <tex>i<h</tex>. | #Пусть <tex>i<h</tex>. | ||
- | ##Случайным образом выбираем набор <tex>u=\{i_1,\ldots,\i_r\} \in U_i</tex>, определяющий подматрицу <tex>L^u_{nml}</tex>, образованную строками с номерами <tex>i_1,\ldots, | + | ##Случайным образом выбираем набор <tex>u=\{i_1,\ldots,\i_r\} \in U_i</tex>, определяющий подматрицу <tex>L^u_{nml}</tex>, образованную строками с номерами <tex>i_1,\ldots,i_r</tex>.<br /> |
- | ##Тест таблицы <tex>T_{nml}</tex>, состоящий из столбцов <tex>j_1,\ldots,\j_r</tex> называется ''u-тестом'', если набор столбцов матрицы <tex>L^u_{nml}</tex> с теми же номерами является неприводимым покрытием. <tex>\ | + | ##Тест таблицы <tex>T_{nml}</tex>, состоящий из столбцов <tex>j_1,\ldots,\j_r</tex> называется ''u-тестом'', если набор столбцов матрицы <tex>L^u_{nml}</tex> с теми же номерами является неприводимым покрытием. <tex>\mathcal{T}(T_{nml},u)</tex> - множество всех u-тестов в таблице <tex>T_{nml}</tex>. |
##Каждому неприводимому покрытию матрицы <tex>L_{nml}</tex> соответствует набор столбцов таблицы <tex>T_{nml}</tex>, который проверяется на тестовость. | ##Каждому неприводимому покрытию матрицы <tex>L_{nml}</tex> соответствует набор столбцов таблицы <tex>T_{nml}</tex>, который проверяется на тестовость. | ||
- | ##Обработка последовательности <tex>u_1,\ldots,u_v</tex> приводит к построению случайной выборки <tex>\ | + | ##Обработка последовательности <tex>u_1,\ldots,u_v</tex> приводит к построению случайной выборки <tex>\mathcal{T}'(T_{nml})=\bigcup^{v}_{t=1}{\mathcal{T}(T_{nml},u_t)}</tex>. В этом случае используется стохастический способ построения тупиковых тестов. |
'''Замечание:''' Требуемая точность алгоритмов зависит от выбора параметров i и v. При определенных условия выбора этих величин стохастический алгоритм почти всегда совпадает с детерминированным, <tex>i=\log^{\gamma}_2 n, \ \gamma >3</tex>. для решения практических задач достаточно выбрать <tex>i=\log_2 n, v=20</tex>. | '''Замечание:''' Требуемая точность алгоритмов зависит от выбора параметров i и v. При определенных условия выбора этих величин стохастический алгоритм почти всегда совпадает с детерминированным, <tex>i=\log^{\gamma}_2 n, \ \gamma >3</tex>. для решения практических задач достаточно выбрать <tex>i=\log_2 n, v=20</tex>. | ||
Версия 13:55, 14 февраля 2010
![]() | Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |
Алгоритм вычисления оценки, в котором множество опорных множеств является множеством всех тупиковых тестов, называется тестовым алгоритмом. Первый вариант таких АВО был предложен Ю.И. Журавлевым. АВО совмещают метрические и логические принципы классификации. От метрических алгоритмов АВО наследует принцип оценивания сходства через введение множества метрик , а от логических принцип поиска конъюнктивных закономерностей, конъюнкции строятся не над бинарными признаками
, а над бинарными функциями близости вида
. В этом случае каждой закономерности соответствует не подмножество признаков, а подмножество метрик, называемое опорным множеством. Как правило одного опорного множества недостаточно, поэтому в АВО применяется взвешенное голосование по системе опорных множеств.
Содержание |
Описание АВО, основанных на тупиковых тестах
Формулировка задачи
Задача распознавания: - множество непересекающихся классов объектов.
Первоначальная информация (обучающая) и описание некоторого объекта
,
.
Объект задается через набор числовых признаков .
Задача распознавания состоит в определении включения заданного объекта в классы
.
В случае АВО, основанных на тупиковых тестах, начальная информация задается таблицей:
- таблица признаков объектов в обучающей выборке;
- описание объекта из обучающей выборки;
- выражение, определяющее включение объектов в классы;
Алгоритм распознавания, где
.
Строение АВО
- система опорных множеств;
- Вводится функция близости для двух объектов по опорному множеству
:
где
неотрицательные числа, называемые порогами,
- Вводится оценка близости объекта к классу
- Вычисление алгоритма проводится по правилу:
- пороги осторожности.
Строение АВО, основанного на тупиковых тестах
- Вводится система опорных множеств
;
- Задается функция близости для двух объектов по опорному множеству
:
. Если
, объекты не являются близкими по опорному множеству.
Тупиковые тесты
Тестом называется набор столбцов таблицы обучения с номерами
, если любые два объекта, принадлежащие разным классам
, не являются близкими по опорному множеству
.
Тупиковым тестом называется тест, у которого его собственное подмножество не является таковым.
Задача распознавания на основе тупиковых тестов решается следующим образом.
Пусть
- множество тупиковых тестов таблицы
. По тупиковому тесту
выделяется подописание для распознаваемого объекта
, а затем сравнивается со всеми подописаниями объектов таблицы. Число совпадений с описаниями объектов i-го класса обозначается через
.
Оценка объекта по i-ому классу .
Далее объект относится к тому классу,по которому он получил максимальную оценку, в случае двух максимумов считается, что объект не классифицируется на заданном тесте.
Если считать, что не все признаки, описывающие объект, равнозначны, то они снабжаются числовыми весами , где
- число тупиковых тестов в таблице,
-число тупиковых тестов в таблице, содержащих j-ый столбец. Чем больше вес, тем важнее признак в описании объектов множества.
Весами объектов, составляющих таблицу обучения, называется поощрительная величина
. В случае совпадения распознаваемого объекта
с объектом из таблицы
, такое совпадение поощряется:
,
Оценка объекта по i-ому классу задается таким образом
.
Построение тупиковых тестов
Процесс построения всех тупиковых тестов очень трудоемкий, так как зачастую приходится использовать метод перебора. Для решения задач большой размерности применяются стохастические методы. Для обработки таблиц с относительно большим числом строк по сравнению с числом столбцов может применяться следующий метод.
- Пусть
.
Паре объектов и
ставится в соответствие строка
, если :
- Составим булеву матрицу
из всех таких строк для объектов из разных классов.
-
- совокупность всех подмножеств множества
мощности i - выбранного числа из этого множества. h - число строк в матрице
. Элементы множества
называются наборами.
- Алгоритм построения тупиковых тестов:
- Пусть
, задача построения множества всех тупиковых тестов таблицы
сводится к построению множества всех неприводимых покрытий матрицы
. В этом случае используется детерминированный алгоритм.
- Пусть
.
- Случайным образом выбираем набор
, определяющий подматрицу
, образованную строками с номерами
.
- Тест таблицы
, состоящий из столбцов
называется u-тестом, если набор столбцов матрицы
с теми же номерами является неприводимым покрытием.
- множество всех u-тестов в таблице
.
- Каждому неприводимому покрытию матрицы
соответствует набор столбцов таблицы
, который проверяется на тестовость.
- Обработка последовательности
приводит к построению случайной выборки
. В этом случае используется стохастический способ построения тупиковых тестов.
- Случайным образом выбираем набор
Замечание: Требуемая точность алгоритмов зависит от выбора параметров i и v. При определенных условия выбора этих величин стохастический алгоритм почти всегда совпадает с детерминированным, . для решения практических задач достаточно выбрать
.
Литература
- К.В. Воронцов, Машинное обучение (курс лекций)
- Журавлев Ю. И. Об алгебраических методах в задачах распознавания и классификации // Распознавание, классификация, прогноз. — 1988 T. 1. — С. 9--16.
- Бушманов О. Н., Дюкова Е. В., Журавлев Ю. И., Кочетков Д. В., Рязанов В. В. Система анализа и распознавания образов // Распознавание, классификация, прогноз. — М.: Наука, 1989. — T. 2. — С. 250–273.