Тупиковые тесты
Материал из MachineLearning.
м |
|||
Строка 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 \epsilon_s]}</tex> | B_\omega(X, X')=\bigwedge_{s \in \omega}{[\rho_s (X, X') \leq \epsilon_s]}</tex> | ||
где <tex>\epsilon_s </tex> неотрицательные числа, называемые порогами, <tex>s=1,\ldots ,n </tex> | где <tex>\epsilon_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) = | ||
Строка 46: | Строка 46: | ||
===Строение АВО, основанного на тупиковых тестах=== | ===Строение АВО, основанного на тупиковых тестах=== | ||
- | + | *Вводится система опорных множеств <tex>\Omega</tex>; | |
- | + | *Задается функция близости для двух объектов по опорному множеству <tex>\omega=\{j_1,\ldots, j_r\}</tex>: | |
<tex> | <tex> | ||
B_\omega(X_{i1}, X_{i2})=\bigwedge^{r}_{t=1}{|a_{i1j_t}-a_{i2j_t}| \leq \epsilon_s\]}</tex>. Если <tex>B=0</tex>, объекты не являются близкими по опорному множеству. | B_\omega(X_{i1}, X_{i2})=\bigwedge^{r}_{t=1}{|a_{i1j_t}-a_{i2j_t}| \leq \epsilon_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>. | '''Тестом''' называется набор столбцов таблицы обучения <tex>T_{nml}</tex> с номерами <tex>j_1,\ldots,\j_r</tex>, если любые два объекта, принадлежащие разным классам <tex>Y_i</tex>, не являются близкими по опорному множеству <tex>\omega =\{j_1,\ldots,\j_r\}</tex>. | ||
- | '''Тупиковым тестом''' называется тест, у которого его собственное подмножество не является таковым. | + | '''Тупиковым тестом''' называется тест, у которого его собственное подмножество не является таковым. |
+ | Задача распознавания на основе тупиковых тестов решается следующим образом. | ||
+ | Пусть <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>, а затем сравнивается со всеми подописаниями объектов таблицы. Число совпадений с описаниями объектов i-го класса обозначается через <tex>\Gamma_{ji}(T)</tex>.<br /> | ||
+ | ''Оценка объекта по i-ому классу'' <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> -число тупиковых тестов в таблице, содержащих j-ый столбец. Чем больше вес, тем важнее признак в описании объектов множества. | ||
+ | Весами объектов, составляющих таблицу обучения, называется поощрительная величина <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>, | ||
+ | Оценка объекта по i-ому классу задается таким образом | ||
+ | <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>. | ||
+ | ===Построение тупиковых тестов=== | ||
+ | Про |
Версия 12:01, 14 февраля 2010
![]() | Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |
Алгоритм вычисления оценки, в котором множество опорных множеств является множеством всех тупиковых тестов, называется тестовым алгоритмом. Первый вариант таких АВО был предложен Ю.И. Журавлевым. АВО совмещают метрические и логические принципы классификации. От метрических алгоритмов АВО наследует принцип оценивания сходства через введение множества метрик , а от логических принцип поиска конъюнктивных закономерностей, конъюнкции строятся не над бинарными признаками
, а над бинарными функциями близости вида
. В этом случае каждой закономерности соответствует не подмножество признаков, а подмножество метрик, называемое опорным множеством. Как правило одного опорного множества недостаточно, поэтому в АВО применяется взвешенное голосование по системе опорных множеств.
Содержание |
Описание АВО, основанных на тупиковых тестах
Формулировка задачи
Задача распознавания: - множество непересекающихся классов объектов.
Первоначальная информация (обучающая) и описание некоторого объекта
,
.
Объект задается через набор числовых признаков .
Задача распознавания состоит в определении включения заданного объекта в классы
.
В случае АВО, основанных на тупиковых тестах, начальная информация задается таблицей:
- таблица признаков объектов в обучающей выборке;
- описание объекта из обучающей выборки;
- выражение, определяющее включение объектов в классы;
Алгоритм распознавания, где
.
Строение АВО
- система опорных множеств;
- Вводится функция близости для двух объектов по опорному множеству
:
где
неотрицательные числа, называемые порогами,
- Вводится оценка близости объекта к классу
- Вычисление алгоритма проводится по правилу:
- пороги осторожности.
Строение АВО, основанного на тупиковых тестах
- Вводится система опорных множеств
;
- Задается функция близости для двух объектов по опорному множеству
:
. Если
, объекты не являются близкими по опорному множеству.
Тупиковые тесты
Тестом называется набор столбцов таблицы обучения с номерами
, если любые два объекта, принадлежащие разным классам
, не являются близкими по опорному множеству
.
Тупиковым тестом называется тест, у которого его собственное подмножество не является таковым.
Задача распознавания на основе тупиковых тестов решается следующим образом.
Пусть
- множество тупиковых тестов таблицы
. По тупиковому тесту
выделяется подописание для распознаваемого объекта
, а затем сравнивается со всеми подописаниями объектов таблицы. Число совпадений с описаниями объектов i-го класса обозначается через
.
Оценка объекта по i-ому классу .
Далее объект относится к тому классу,по которому он получил максимальную оценку, в случае двух максимумов считается, что объект не классифицируется на заданном тесте.
Если считать, что не все признаки, описывающие объект, равнозначны, то они снабжаются числовыми весами , где
- число тупиковых тестов в таблице,
-число тупиковых тестов в таблице, содержащих j-ый столбец. Чем больше вес, тем важнее признак в описании объектов множества.
Весами объектов, составляющих таблицу обучения, называется поощрительная величина
. В случае совпадения распознаваемого объекта
с объектом из таблицы
, такое совпадение поощряется:
,
Оценка объекта по i-ому классу задается таким образом
.
Построение тупиковых тестов
Про