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

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

Версия от 19:08, 13 февраля 2010; Mordasova (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Перейти к: навигация, поиск

Данная статья является непроверенным учебным заданием.

Студент: Участник: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 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, & - \text{объект не распознается алгоритмом.} \end{cases}$