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

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

(Различия между версиями)
Перейти к: навигация, поиск
м
Строка 3: Строка 3:
==Описание АВО, основанных на тупиковых тестах==
==Описание АВО, основанных на тупиковых тестах==
 +
===Формулировка задачи===
 +
'''Задача распознавания:''' <tex>Y=\bigcup_{i=1\ldots l}{Y_i}</tex>- множество непересекающихся классов объектов.<br />
-
'''Дано:''' <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>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 />
Строка 12: Строка 13:
*<tex>T_{nml}=\parallel a_{ij}\parallel_{m\times n}</tex> - таблица признаков объектов в обучающей выборке;
*<tex>T_{nml}=\parallel a_{ij}\parallel_{m\times n}</tex> - таблица признаков объектов в обучающей выборке;
*<tex>I(X_i)=(a_{i1},\ldots,a_{in})</tex> - описание объекта из обучающей выборки;
*<tex>I(X_i)=(a_{i1},\ldots,a_{in})</tex> - описание объекта из обучающей выборки;
-
*<tex>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</tex> - выражение, определяющее включение объектов в классы;
+
*<tex>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</tex> - выражение, определяющее включение объектов в классы;
-
Алгоритм распознавания <tex>A(I_0,X)=\alpha(X)</tex>, где <tex>\alpha(X) = \alpha_1(I_0,X),\ldots ,\alpha_l(I_0,X)</tex>.<br />
+
'''Алгоритм распознавания'''<tex>A(I_0,X)=\alpha(X)</tex>, где <tex>\alpha(X) = \alpha_1(I_0,X),\ldots ,\alpha_l(I_0,X)</tex>.<br />
<tex>
<tex>
\alpha_i(X) =
\alpha_i(X) =
Строка 20: Строка 21:
1, & X\in Y_i\\
1, & X\in Y_i\\
0, & X \notin Y_i \\
0, & X \notin Y_i \\
-
\Delta, & - \text{объект не распознается алгоритмом.}
+
\Delta, & \alpha\ \mathrm{doesn't\ accept\ X}.
\end{cases}
\end{cases}
</tex>
</tex>
 +
 +
===Строение АВО===
 +
# {}
 +
#
 +
#
 +
#

Версия 19:24, 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. {}
Личные инструменты