Тупиковые тесты
Материал из MachineLearning.
м |
м (→Формулировка задачи) |
||
(26 промежуточных версий не показаны.) | |||
Строка 1: | Строка 1: | ||
{{Задание|Mordasova|Константин Воронцов|15 февраля 2010}} | {{Задание|Mordasova|Константин Воронцов|15 февраля 2010}} | ||
- | [[Алгоритмы вычисления оценок| | + | [[Алгоритмы вычисления оценок|Алгоритмы вычисления оценки]], в которых опорные множества являются '''тупиковыми тестами''', называются тестовыми алгоритмами. Первый вариант таких [[АВО]] был предложен [[Журавлёв, Юрий Иванович|Ю.И. Журавлевым]]. [[АВО]] совмещают метрические и логические принципы классификации. От [[Метрический классификатор|метрических алгоритмов]] [[АВО]] наследуют принцип оценивания сходства через введение ''множества метрик'' <tex>\rho_s(x, x')</tex>, а от логических принцип поиска конъюнктивных закономерностей, конъюнкции строятся не над бинарными признаками <tex>\beta(x)</tex>, а над бинарными функциями близости вида <tex>\beta(x, x') = \[\rho_s(x, x') < \varepsilon_s\]</tex>. В этом случае каждой закономерности соответствует не подмножество признаков, а подмножество метрик, называемое ''опорным множеством''. Как правило одного опорного множества недостаточно, поэтому в [[АВО]] применяется [[взвешенное голосование]] по системе опорных множеств. |
==Описание АВО, основанных на тупиковых тестах== | ==Описание АВО, основанных на тупиковых тестах== | ||
===Формулировка задачи=== | ===Формулировка задачи=== | ||
- | '''Задача распознавания:''' <tex>Y=\bigcup_{i=1\ldots l}{Y_i}</tex> | + | '''Задача распознавания:''' Дано <tex>\ Y=\bigcup_{i=1\ldots l}{Y_i}\ </tex> — множество непересекающихся классов объектов.<br /> |
- | + | Дана первоначальная информация <tex>I_0</tex> (обучающая) и описание некоторого объекта <tex>I(x)</tex>, <tex>x \in Y</tex>.<br /> | |
Объект задается через набор числовых признаков <tex>X=(x_1,\ldots,x_n)</tex>.<br /> | Объект задается через набор числовых признаков <tex>X=(x_1,\ldots,x_n)</tex>.<br /> | ||
Задача распознавания состоит в определении включения заданного объекта <tex>x</tex> в классы <tex>Y_i</tex>.<br /> | Задача распознавания состоит в определении включения заданного объекта <tex>x</tex> в классы <tex>Y_i</tex>.<br /> | ||
Строка 26: | Строка 26: | ||
===Строение АВО=== | ===Строение АВО=== | ||
- | + | *<tex>\Omega=\{\omega|\omega \subseteq \{1, \ldots, n\}\}</tex> - ''система опорных множеств''; | |
- | + | ||
+ | *Вводится ''функция близости'' для двух объектов по опорному множеству <tex>\omega</tex> :<br /> | ||
<tex> | <tex> | ||
- | B_\omega(X, X')=\bigwedge_{s \in \omega}{[\rho_s (X, X') \leq \ | + | B_\omega(X, X')=\bigwedge_{s \in \omega}{[\rho_s (X, X') \leq \varepsilon_s]}</tex>, |
- | где <tex>\ | + | где <tex>\varepsilon_s </tex> неотрицательные числа, называемые порогами, <tex>s=1,\ldots ,n </tex>; |
- | + | ||
- | + | *Вводится оценка близости объекта к классу <tex>\Gamma_c</tex>; | |
+ | |||
+ | *Вычисление алгоритма проводится по правилу:<br /> | ||
<tex> | <tex> | ||
\alpha_j(I_0, X) = | \alpha_j(I_0, X) = | ||
\begin{cases} | \begin{cases} | ||
- | 1, & \Gamma_j(X)>\Gamma_i(X)+\delta_2;\ i=1,\ldots,l, \ i \neq j;\ \Gamma_j(X)>\delta_1\sum^{l}_{i=1}{\Gamma_j(X)}\\ | + | 1, & \Gamma_j(X)>\Gamma_i(X)+\delta_2;\ i=1,\ldots,l, \ i \neq j;\ \Gamma_j(X)>\delta_1\sum^{l}_{i=1}{\Gamma_j(X)};\\ |
0, & \mathrm{other\ way}. | 0, & \mathrm{other\ way}. | ||
\end{cases} | \end{cases} | ||
- | </tex> | + | </tex><br /> |
+ | <tex>1>\delta_1\geq 1/l,\ \delta_2 \geq 0</tex> - ''пороги осторожности''. | ||
+ | |||
+ | ===Строение АВО, основанного на тупиковых тестах=== | ||
+ | *Вводится система опорных множеств <tex>\Omega</tex>; | ||
+ | |||
+ | *Задается функция близости для двух объектов по опорному множеству <tex>\omega=\{j_1,\ldots, j_r\}</tex>: | ||
+ | <tex> | ||
+ | B_\omega(X_{i1}, X_{i2})=\bigwedge^{r}_{t=1}{\[|a_{i1j_t}-a_{i2j_t}| \leq \varepsilon_s\]}</tex>. Если <tex>B=0</tex>, объекты не являются близкими по опорному множеству. | ||
+ | |||
+ | ==Тупиковые тесты== | ||
+ | '''Тестом''' называется набор столбцов таблицы обучения <tex>T_{nml}</tex> с номерами <tex>j_1,\ldots,\j_r</tex>, если любые два объекта, принадлежащие разным классам <tex>Y_i</tex>, не являются близкими по опорному множеству <tex>\omega =\{j_1,\ldots,\j_r\}</tex>. | ||
+ | '''Тупиковым тестом''' называется тест, у которого его собственное подмножество не является таковым. <br /> | ||
+ | Задача распознавания на основе тупиковых тестов решается следующим образом. | ||
+ | Пусть <tex>\{T\}</tex> - множество тупиковых тестов таблицы <tex>T_{nml}</tex>. По тупиковому тесту<tex>j=(j_1,\ldots,j_k)</tex> выделяется подописание для распознаваемого объекта <tex>X=(a_{j_1},\ldots,a_{j_r})</tex>, а затем сравнивается со всеми подописаниями объектов таблицы. Число совпадений с описаниями объектов <tex>i</tex>-го класса обозначается через <tex>\Gamma_{ji}(T)</tex>.<br /> | ||
+ | ''Оценка объекта по <tex>i</tex>-ому классу'' <tex>\Gamma_{ji}(X) = \Gamma_i(X_j)=\frac{1}{m_j-m_{j-1}}\sum_{T \in\{T\}}{\Gamma_{ji}(T)}</tex>. | ||
+ | |||
+ | Далее объект относится к тому классу,по которому он получил максимальную оценку, в случае двух максимумов считается, что объект не классифицируется на заданном тесте.<br /> | ||
+ | |||
+ | Если считать, что не все признаки, описывающие объект, равнозначны, то они снабжаются числовыми весами <tex>p(j)=\frac{\tau_j(n,m)}{\tau(n,m)}</tex>, где <tex>\tau</tex> - число тупиковых тестов в таблице, <tex>\tau_j</tex> -число тупиковых тестов в таблице, содержащих <tex>j</tex>-ый столбец. Чем больше вес, тем важнее признак в описании объектов множества. | ||
+ | Весами объектов, составляющих таблицу обучения, называется поощрительная величина <tex>\gamma</tex>. В случае совпадения распознаваемого объекта <tex>X</tex> с объектом из таблицы <tex>X_v \in Y_i</tex>, такое совпадение поощряется: <tex>\Gamma_T(X,X_v) = \gamma(X_v)(p(j_1),\ldots,p(j_r))</tex>, | ||
+ | Оценка объекта по <tex>i</tex>-ому классу задается таким образом | ||
+ | <tex>\Gamma_i(X)=\frac{1}{m_i-m_i-1}\sum_{T\in\{T\}}\sum^{m_i}_{m_{i-1}+1}{\Gamma_T(X_v,X)}</tex>. | ||
+ | ===Построение тупиковых тестов=== | ||
+ | Процесс построения всех тупиковых тестов очень трудоемкий, так как зачастую приходится использовать метод перебора. Для решения задач большой размерности применяются стохастические методы. Для обработки таблиц с относительно большим числом строк по сравнению с числом столбцов может применяться следующий метод. <br /> | ||
+ | |||
+ | *Пусть <tex>i_1,i_2 \in(1,\ldots,m)</tex>. | ||
+ | Паре объектов <tex>S_{i_1}</tex> и <tex>S_{i_2}</tex> ставится в соответствие строка <tex>I(X_{i_1})\oplus I(X_{i_2})=(a_{i_11}\oplus a_{i_21}, \dots, a_{i_1n}\oplus a_{i_1n})</tex>, если :<br /> | ||
+ | <tex> | ||
+ | a_{i_1j}\oplus a_{i_2j} = | ||
+ | \begin{cases} | ||
+ | 0, & |a_{i_1j}-a_{i_2j}|\leq \varepsilon_j\\ | ||
+ | 1, & \mathrm{other\ way}. | ||
+ | \end{cases} | ||
+ | </tex><br /> | ||
+ | *Составим булеву матрицу <tex>L_{nml}</tex> из всех таких строк для объектов из разных классов. | ||
+ | * <tex>U_i</tex> - совокупность всех подмножеств множества <tex>\{1,2,\ldots,h\}</tex> мощности <tex>i</tex>, где <tex>i</tex> - выбранное число из этого множества. <tex>h</tex> - число строк в матрице <tex>L_{nml}</tex>. Элементы множества <tex>U_i</tex> называются наборами. | ||
+ | *Алгоритм построения тупиковых тестов: | ||
+ | #Пусть <tex>i=h, \ U_i=\{1,2,\ldots,h\}</tex>, задача построения множества всех тупиковых тестов таблицы <tex>T_{nml}</tex> сводится к построению множества всех неприводимых покрытий матрицы <tex>L_{nml}</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,i_r</tex>.<br /> | ||
+ | ##Тест таблицы <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>u_1,\ldots,u_v</tex> приводит к построению случайной выборки <tex>\mathcal{T}'(T_{nml})=\bigcup^{v}_{t=1}{\mathcal{T}(T_{nml},u_t)}</tex>. В этом случае используется стохастический способ построения тупиковых тестов. | ||
+ | '''Замечание:''' Требуемая точность алгоритмов зависит от выбора параметров <tex>i</tex> и <tex>v</tex>. При определенных условия выбора этих величин стохастический алгоритм почти всегда совпадает с детерминированным, <tex>i=\log^{\gamma}_2 n, \ \gamma >3</tex>. для решения практических задач достаточно выбрать <tex>i=\log_2 n,\ v=20</tex>. | ||
+ | |||
+ | ==Литература== | ||
+ | #''К.В. Воронцов'', [[Машинное обучение (курс лекций, К.В.Воронцов)|Машинное обучение (курс лекций)]]. | ||
+ | #{{книга | ||
+ | |автор = Журавлев Ю. И. | ||
+ | |часть = Об алгебраических методах в задачах распознавания и классификации | ||
+ | |заглавие = Распознавание, классификация, прогноз | ||
+ | |год = 1988 | ||
+ | |том = 1 | ||
+ | |страницы = 9--16 | ||
+ | |ссылка = http://www.ccas.ru/frc/papers/zhuravlev88rkp.pdf | ||
+ | }} | ||
+ | #{{книга | ||
+ | |автор = Бушманов О. Н., Дюкова Е. В., Журавлев Ю. И., Кочетков Д. В., Рязанов В. В. | ||
+ | |часть = Система анализа и распознавания образов | ||
+ | |заглавие = Распознавание, классификация, прогноз | ||
+ | |год = 1989 | ||
+ | |место = М. | ||
+ | |издательство = Наука | ||
+ | |том = 2 | ||
+ | |страницы = 250–273 | ||
+ | |ссылка = http://www.ccas.ru/frc/papers/bushmanov89obraz.pdf | ||
+ | }} |
Текущая версия
![]() | Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |
Алгоритмы вычисления оценки, в которых опорные множества являются тупиковыми тестами, называются тестовыми алгоритмами. Первый вариант таких АВО был предложен Ю.И. Журавлевым. АВО совмещают метрические и логические принципы классификации. От метрических алгоритмов АВО наследуют принцип оценивания сходства через введение множества метрик , а от логических принцип поиска конъюнктивных закономерностей, конъюнкции строятся не над бинарными признаками
, а над бинарными функциями близости вида
. В этом случае каждой закономерности соответствует не подмножество признаков, а подмножество метрик, называемое опорным множеством. Как правило одного опорного множества недостаточно, поэтому в АВО применяется взвешенное голосование по системе опорных множеств.
Содержание |
Описание АВО, основанных на тупиковых тестах
Формулировка задачи
Задача распознавания: Дано — множество непересекающихся классов объектов.
Дана первоначальная информация (обучающая) и описание некоторого объекта
,
.
Объект задается через набор числовых признаков .
Задача распознавания состоит в определении включения заданного объекта в классы
.
В случае АВО, основанных на тупиковых тестах, начальная информация задается таблицей:
- таблица признаков объектов в обучающей выборке;
- описание объекта из обучающей выборки;
- выражение, определяющее включение объектов в классы;
Алгоритм распознавания, где
.
Строение АВО
- система опорных множеств;
- Вводится функция близости для двух объектов по опорному множеству
:
,
где
неотрицательные числа, называемые порогами,
;
- Вводится оценка близости объекта к классу
;
- Вычисление алгоритма проводится по правилу:
- пороги осторожности.
Строение АВО, основанного на тупиковых тестах
- Вводится система опорных множеств
;
- Задается функция близости для двух объектов по опорному множеству
:
. Если
, объекты не являются близкими по опорному множеству.
Тупиковые тесты
Тестом называется набор столбцов таблицы обучения с номерами
, если любые два объекта, принадлежащие разным классам
, не являются близкими по опорному множеству
.
Тупиковым тестом называется тест, у которого его собственное подмножество не является таковым.
Задача распознавания на основе тупиковых тестов решается следующим образом.
Пусть - множество тупиковых тестов таблицы
. По тупиковому тесту
выделяется подописание для распознаваемого объекта
, а затем сравнивается со всеми подописаниями объектов таблицы. Число совпадений с описаниями объектов
-го класса обозначается через
.
Оценка объекта по -ому классу
.
Далее объект относится к тому классу,по которому он получил максимальную оценку, в случае двух максимумов считается, что объект не классифицируется на заданном тесте.
Если считать, что не все признаки, описывающие объект, равнозначны, то они снабжаются числовыми весами , где
- число тупиковых тестов в таблице,
-число тупиковых тестов в таблице, содержащих
-ый столбец. Чем больше вес, тем важнее признак в описании объектов множества.
Весами объектов, составляющих таблицу обучения, называется поощрительная величина
. В случае совпадения распознаваемого объекта
с объектом из таблицы
, такое совпадение поощряется:
,
Оценка объекта по
-ому классу задается таким образом
.
Построение тупиковых тестов
Процесс построения всех тупиковых тестов очень трудоемкий, так как зачастую приходится использовать метод перебора. Для решения задач большой размерности применяются стохастические методы. Для обработки таблиц с относительно большим числом строк по сравнению с числом столбцов может применяться следующий метод.
- Пусть
.
Паре объектов и
ставится в соответствие строка
, если :
- Составим булеву матрицу
из всех таких строк для объектов из разных классов.
-
- совокупность всех подмножеств множества
мощности
, где
- выбранное число из этого множества.
- число строк в матрице
. Элементы множества
называются наборами.
- Алгоритм построения тупиковых тестов:
- Пусть
, задача построения множества всех тупиковых тестов таблицы
сводится к построению множества всех неприводимых покрытий матрицы
. В этом случае используется детерминированный алгоритм.
- Пусть
.
- Случайным образом выбираем набор
, определяющий подматрицу
, образованную строками с номерами
.
- Тест таблицы
, состоящий из столбцов
называется u-тестом, если набор столбцов матрицы
с теми же номерами является неприводимым покрытием.
- множество всех u-тестов в таблице
.
- Каждому неприводимому покрытию матрицы
соответствует набор столбцов таблицы
, который проверяется на тестовость.
- Обработка последовательности
приводит к построению случайной выборки
. В этом случае используется стохастический способ построения тупиковых тестов.
- Случайным образом выбираем набор
Замечание: Требуемая точность алгоритмов зависит от выбора параметров и
. При определенных условия выбора этих величин стохастический алгоритм почти всегда совпадает с детерминированным,
. для решения практических задач достаточно выбрать
.
Литература
- К.В. Воронцов, Машинное обучение (курс лекций).
- Журавлев Ю. И. Об алгебраических методах в задачах распознавания и классификации // Распознавание, классификация, прогноз. — 1988 T. 1. — С. 9--16.
- Бушманов О. Н., Дюкова Е. В., Журавлев Ю. И., Кочетков Д. В., Рязанов В. В. Система анализа и распознавания образов // Распознавание, классификация, прогноз. — М.: Наука, 1989. — T. 2. — С. 250–273.