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

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

(Различия между версиями)

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

Версия 12:01, 14 февраля 2010

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

Студент: Участник: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)}$ .

Построение тупиковых тестов

Про

Источник — «http://www.machinelearning.ru/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»

Категория: Непроверенные учебные задания

@@ Строка 26: / Строка 26: @@
 ===Строение АВО===
-#<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>
 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>\Gamma_c</tex>
+*Вводится оценка близости объекта к классу <tex>\Gamma_c</tex>
-#Вычисление алгоритма проводится по правилу:<br />
+*Вычисление алгоритма проводится по правилу:<br />
 <tex>
 \alpha_j(I_0, X) =
@@ Строка 46: / Строка 46: @@
 ===Строение АВО, основанного на тупиковых тестах===
-#Вводится система опорных множеств <tex>\Omega</tex>;
+*Вводится система опорных множеств <tex>\Omega</tex>;
-#Задается функция близости для двух объектов по опорному множеству <tex>\omega=\{j_1,\ldots, j_r\}</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>.
 '''Тупиковым тестом''' называется тест, у которого его собственное подмножество не является таковым.
+Задача распознавания на основе тупиковых тестов решается следующим образом.
+Пусть <tex>\{T\}</tex> - множество тупиковых тестов таблицы <tex>T_{nml}</tex>. По тупиковому тесту<tex>j=(j_1,\ldots,j_k</tex>  выделяется подописание для распознаваемого объекта <tex>X=(a_{j_1},\ldots,a_{j_r})</tex>, а затем сравнивается со всеми подописаниями объектов таблицы. Число совпадений с описаниями объектов i-го класса обозначается через <tex>\Gamma_{ji}(T)</tex>.<br />
+''Оценка объекта по i-ому классу'' <tex>\Gamma_{ji}(X) = \Gamma_i(X_j)=\frac{1}{m_j-m_{j-1}}\sum_{T \in\{T\}}{\Gamma_{ji}(T)}</tex>.
+Далее объект относится к тому классу,по которому он получил максимальную оценку, в случае двух максимумов считается, что объект не классифицируется на заданном тесте.<br />
+Если считать, что не все признаки, описывающие объект, равнозначны, то они снабжаются числовыми весами <tex>p(j)=\frac{\tau_j(n,m)}{\tau(n,m)}</tex>, где <tex>\tau</tex> - число тупиковых тестов в таблице, <tex>\tau_j</tex> -число тупиковых тестов в таблице, содержащих j-ый столбец. Чем больше вес, тем важнее признак в описании объектов множества.
+Весами объектов, составляющих таблицу обучения, называется поощрительная величина <tex>\gamma</tex>. В случае совпадения распознаваемого объекта <tex>X</tex> с объектом из таблицы <tex>X_v \in Y_i</tex>, такое совпадение поощряется: <tex>\Gamma_T(X,X_v) = \gamma(X_v)(p(j_1),\ldots,p(j_r))</tex>,
+Оценка объекта по i-ому классу задается таким образом
+<tex>\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)}</tex>.
+===Построение тупиковых тестов===
+Про

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

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

Версия 12:01, 14 февраля 2010

Содержание

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

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

Строение АВО

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

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

Построение тупиковых тестов

Просмотры

Личные инструменты

Навигация

Поиск

Инструменты