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

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

(Различия между версиями)
Перейти к: навигация, поиск

Mordasova (Обсуждение | вклад)
(Новая: {{Задание|Mordasova|Константин Воронцов|15 февраля 2010}} [[Алгоритмы вычисления оценок|Алгоритм вычисления о...)
К следующему изменению →

Версия 18:59, 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).</br> Задача распознавания состоит в определении включения заданного объекта 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 K_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 K_i\\
 0, & X \notin K_i \\

\end{cases} 

=

\begin{cases} 

 n/2,  & \mbox{if }n\mbox{ is even} \\
 3n+1, & \mbox{if }n\mbox{ is odd}

\end{cases}

Источник — «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»