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

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

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

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

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

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

Студент: Участник:Mordasova

Преподаватель: Участник:Константин Воронцов

Срок: 15 февраля 2010

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

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

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

Содержание

1 Описание АВО, основанных на тупиковых тестах
2 Тупиковые тесты
- 2.1 Построение тупиковых тестов

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

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

Задача распознавания: $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}$

Строение АВО

$\Omega=\{\omega|\omega \subseteq \{1, \ldots, n\}\}$ - система опорных множеств;

Вводится функция близости для двух объектов по опорному множеству $\omega$ :

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

Вводится оценка близости объекта к классу $\Gamma_c$

Вычисление алгоритма проводится по правилу:

$\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$ - пороги осторожности.

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

Вводится система опорных множеств $\Omega$ ;

Задается функция близости для двух объектов по опорному множеству $\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\}$ . Тупиковым тестом называется тест, у которого его собственное подмножество не является таковым. Задача распознавания на основе тупиковых тестов решается следующим образом. Пусть $\{T\}$ - множество тупиковых тестов таблицы $T_{nml}$ . По тупиковому тесту $j=(j_1,\ldots,j_k$ выделяется подописание для распознаваемого объекта $X=(a_{j_1},\ldots,a_{j_r})$ , а затем сравнивается со всеми подописаниями объектов таблицы. Число совпадений с описаниями объектов i-го класса обозначается через $\Gamma_{ji}(T)$ .
Оценка объекта по i-ому классу $\Gamma_{ji}(X) = \Gamma_i(X_j)=\frac{1}{m_j-m_{j-1}}\sum_{T \in\{T\}}{\Gamma_{ji}(T)}$ .

Далее объект относится к тому классу,по которому он получил максимальную оценку, в случае двух максимумов считается, что объект не классифицируется на заданном тесте.

Если считать, что не все признаки, описывающие объект, равнозначны, то они снабжаются числовыми весами $p(j)=\frac{\tau_j(n,m)}{\tau(n,m)}$ , где $\tau$ - число тупиковых тестов в таблице, $\tau_j$ -число тупиковых тестов в таблице, содержащих j-ый столбец. Чем больше вес, тем важнее признак в описании объектов множества. Весами объектов, составляющих таблицу обучения, называется поощрительная величина $\gamma$ . В случае совпадения распознаваемого объекта $X$ с объектом из таблицы $X_v \in Y_i$ , такое совпадение поощряется: $\Gamma_T(X,X_v) = \gamma(X_v)(p(j_1),\ldots,p(j_r))$ , Оценка объекта по i-ому классу задается таким образом $\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)}$ .