Тупиковые тесты

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
м
м
Строка 27: Строка 27:
===Строение АВО===
===Строение АВО===
#<tex>\Omega=\{\omega|\omega \subseteq \{1, \ldots, n\}\}</tex> - ''система опорных множеств'';
#<tex>\Omega=\{\omega|\omega \subseteq \{1, \ldots, n\}\}</tex> - ''система опорных множеств'';
 +
#Вводится ''функция близости'' для двух объектов по опорному множеству <tex>\omega</tex> :<br />
#Вводится ''функция близости'' для двух объектов по опорному множеству <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>
#Вводится оценка близости объекта к классу <tex>\Gamma_c</tex>
 +
#Вычисление алгоритма проводится по правилу:<br />
#Вычисление алгоритма проводится по правилу:<br />
<tex>
<tex>
Строка 39: Строка 42:
0, & \mathrm{other\ way}.
0, & \mathrm{other\ way}.
\end{cases}
\end{cases}
-
</tex>
+
</tex><br />
 +
<tex>1>\delta_1\leq 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 \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>.
 +
'''Тупиковым тестом''' называется тест, у которого его собственное подмножество не является таковым.

Версия 20:57, 13 февраля 2010

Данная статья является непроверенным учебным заданием.
Студент: Участник:Mordasova
Преподаватель: Участник:Константин Воронцов
Срок: 15 февраля 2010

До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.


Алгоритм вычисления оценки, в котором множество опорных множеств является множеством всех тупиковых тестов, называется тестовым алгоритмом. Первый вариант таких АВО был предложен Ю.И. Журавлевым. АВО совмещают метрические и логические принципы классификации. От метрических алгоритмов АВО наследует принцип оценивания сходства через введение множества метрик \rho_s(x, x'), а от логических принцип поиска конъюнктивных закономерностей, конъюнкции строятся не над бинарными признаками \beta(x), а над бинарными функциями близости вида \beta(x, x') = \[\rho_s(x, x') < \varepsilon_s\]. В этом случае каждой закономерности соответствует не подмножество признаков, а подмножество метрик, называемое опорным множеством. Как правило одного опорного множества недостаточно, поэтому в АВО применяется взвешенное голосование по системе опорных множеств.

Содержание

Описание АВО, основанных на тупиковых тестах

Формулировка задачи

Задача распознавания: Y=\bigcup_{i=1\ldots l}{Y_i}- множество непересекающихся классов объектов.

Первоначальная информация I_0 (обучающая) и описание некоторого объекта I(x), x \in Y.
Объект задается через набор числовых признаков X=(x_1,\ldots,x_n).
Задача распознавания состоит в определении включения заданного объекта x в классы Y_i.

В случае АВО, основанных на тупиковых тестах, начальная информация I_0 задается таблицей:

  • T_{nml}=\parallel a_{ij}\parallel_{m\times n} - таблица признаков объектов в обучающей выборке;
  • I(X_i)=(a_{i1},\ldots,a_{in}) - описание объекта из обучающей выборки;
  • X_{m_{i-1}+1},\ X_{m_{i-1}+2},\ldots,\ X_{m_i}\in Y_i,\ i=1\ldots l,\ m_0=0,\ m_l=m - выражение, определяющее включение объектов в классы;

Алгоритм распознаванияA(I_0,X)=\alpha(X), где \alpha(X) = \alpha_1(I_0,X),\ldots ,\alpha_l(I_0,X).
\alpha_i(X) = \begin{cases} 1, & X\in Y_i\\ 0, & X \notin Y_i \\ \Delta, & \alpha\ \mathrm{doesn't\ accept\ X}. \end{cases}

Строение АВО

  1. \Omega=\{\omega|\omega \subseteq \{1, \ldots, n\}\} - система опорных множеств;
  1. Вводится функция близости для двух объектов по опорному множеству \omega :

B_\omega(X, X')=\bigwedge_{s \in \omega}{[\rho_s (X, X') \leq \epsilon_s]} где \epsilon_s неотрицательные числа, называемые порогами, s=1,\ldots ,n

  1. Вводится оценка близости объекта к классу \Gamma_c
  1. Вычисление алгоритма проводится по правилу:

\alpha_j(I_0, X) = \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)}\\ 0, & \mathrm{other\ way}. \end{cases}
1>\delta_1\leq 1/l,\ \delta_2 \geq 0 - пороги осторожности.

Строение АВО, основанного на тупиковых тестах

  1. Вводится система опорных множеств \Omega;
  1. Задается функция близости для двух объектов по опорному множеству \omega=\{j_1,\ldots, j_r\}:

B_\omega(X_{i1}, X_{i2})=\bigwedge^{r}_{t=1}{|a_{i1j_t}-a_{i2j_t}| \leq \epsilon_s\]}. Если B=0, объекты не являются близкими по опорному множеству.


Тестом называется набор столбцов таблицы обучения T_{nml} с номерами j_1,\ldots,\j_r, если любые два объекта, принадлежащие разным классам Y_i, не являются близкими по опорному множеству \omega =\{j_1,\ldots,\j_r\}. Тупиковым тестом называется тест, у которого его собственное подмножество не является таковым.

Источник — «http://www.recognition.su/wiki/index.php?title=%D0%A2%D1%83%D0%BF%D0%B8%D0%BA%D0%BE%D0%B2%D1%8B%D0%B5_%D1%82%D0%B5%D1%81%D1%82%D1%8B»