Задача обучения без учителя.

I. Основные понятия

1. Изображение объекта. Виды изображений.

Изображение объекта – отображение объекта на воспринимающие органы распознающей системы.

Виды изображений - имеются два вида:

1. В виде n-мерного вектора признаков . Н-р, набор атрибутов, часто бинарный.

2.В виде некоторой лингвистической структуры. (в виде цепочек некоторого языка).

Образ (класс).

Пусть задано разбиение множества всех изображений на непересекающиеся подмножества. Каждое такое подмножество назовём классом или образом. Объекты, относящиеся к одному и тому же образу, образуют класс эквивалентности. Иногда под образом понимают множество, элементы которого обладают свойствами рефлексивности и симметричности, но не транзитивности (т.е. отношением толерантности) (для элементов на границе классов).

3. Задача распознавания образов.

Задача распознавания образов – определение некоторым устройством (классификатор, распознающая процедура) к какому классу относится анализируемый объект.

4. Обучающая последовательность.

Обучающая последовательность – выборка из всего множества объектов из различных классов, на основе которой в дальнейшем будет осуществляться построение распознающей процедуры.

Задача обучения РО.

Задача обучения распознаванию образов – построение по данной обучающей последовательности распознающей процедуры, которая бы решала задачу распознавания для любого объекта исходного множества.

Задача обучения с учителем.

Задача обучения с учителем – задача распознавания образов, в которой для каждого объекта из обучающей последовательности указан класс, к которому принадлежит объект (то есть дана маркированная обучающая последовательность).

Задача обучения без учителя.

Задача обучения без учителя – задача распознавания образов, в которой для образов из обучающей последовательности не известны классы, к которым они принадлежат (то есть дана немаркированная выборка).

Решающая функция

Объект представлен вектором признаков X=(x₁, …, x_n), имеется m образов(классов) w₁, …, w_m_.

Решающую ф-ю м-о представить в виде d_ij(x) где i< > j i, j = 1…m

Решающая функция обладает свойствами: 1). d_ij(x)> 0, " i< > j если xÎ w_i 2). d_ij(x) =-d_ji (x)

Примеры задач распознавания.

1) Диагностика комбинационных схем

w1=(x1, x2, x3, x4, y) – недеф-я схема w2=(x1, x2, x3, x4, y) – деф-я схема

Смысл в том, чтобы подавая символ на вход и получая сигнал на выходе решить – явл ли схема деф-ой

Задача в терминах РО:

a) изобр (x1, x2, x3, x4, y) б)имется 2 класса изобр w1 и w2

РП по предъявленному О-у x по конкретному вектору решить к какому классу относится данный О-т

2) Контроль состояния ядерного реактора. а)изобр x=(x0, x1, …, x31) – спектр плотности

w1 – мн-во x, которые соответствуют < ЯР норме> w2– мн-во x, которые соответствуют < аномальное состояние>

В результате работы РП xÎ w1 – реактор в норме, если xÎ w2 – необх принимать меры.

3) Распознавание символов

II Простейшие методы распознавания (сравнение с эталоном)

Вопрос 10. Общая характеристика простейших методов распознавания.

Идея таких методов состоит в том, что для каждого класса выбирается эталон (характерный представитель класса). Распознающая процедура работает так: анализируемый объект сравнивается с эталонами классов и относится к тому классу, с эталоном которого он согласуется наилучшим образом.

11. Метод совмещения с эталоном.

Для каждого класса выбирается эталон (характерный представитель класса). Распознающая процедура: анализируемый объект сравнивается с эталонами классов и относится к тому классу, с эталоном которого он согласуется наилучшим образом. Иногда требуется просто совпадение с эталоном.

Метод зондов

Метод зондов предназначен для распознавания печатных символов. Имеется начертательное поле, в котором расположена система тонкопроводящих зондов. На него накладывается символ-объединение зондов-вырабатывается определенный код символа. Система зондов расположена так, что различным очертаниям одного и того же символа соответствует один и тот же бинарный код. + в том, что зр решается просто. - в сложности построения таких зондов..

Квазитопологический метод.

Квазитопологический метод предназначен для распознавания символов. Каждому символу поставлен в соответствие граф в качестве эталона этого символа. РП: к одному классу относятся все очертания символов, графы которых гомеоморфны, то есть могут быть получены друг из друга с помощью взаимооднозначного непрерывного отображения. -: один и тот же граф может соответствовать нескольким символам

Достоинства и недостатки простейших методов распознавания

Дост: простота, быстродействие

Недостатки: проблема определения эталонов, узкая специализация эталонов.

III Детерминистские методы, основанные на близости описаний

Правило ближайшего соседа.

q-БС правило: вычисляется q ближайших (в смысле некот меры D(z_j, x)) соседей х. И х относ к тому классу w_i, к которому относится большинство из q ближайших соседей.

Алгоритм ISODATA.

Общая структура алгоритма такова:

1. Формирование подмножеств выборочных множеств .

2. Слияние кластеров (если требуется с переходом на 1).

3. Расщепление кластеров (если требуется с переходом на 1).

При этом используются следующие эвристики:

1. Ликвидация кластеров с числом элементов меньше заданного значения.

2. Объединение кластеров, находящихся близко друг к другу.

При объединении кластеров с центрами и образуется один кластер с центром

Расщепление кластера может происходить по одному из следующих критериев:

1. При достаточно сильной разбросанности образов расщепляемого кластера в масштабе общего множества образов.

2. Если требуется получить достаточно большое число кластеров.

Изображающие числа и базис.

Базис - таблица, которая представляет все возможные комбинации значении истинности некоторого набора элементов А, В, С, ....

Для п элементов А₁, ..., А_п базис содержит п строк и 2ⁿ колонок.

Тогда базис для одного элемента: #A=0 1;

для двух элементов A и B:

0 1 2 3

#A = 0 1 0 1

#B = 0 0 1 1

Строки базиса называют изображающими числами соответствующих элементов и обозначают приписыванием слева от элемента знака #. Операции над изобр числами: 1) изображающее число дизъюнкции двух элементов равно сумме изображающих чисел слагаемых: #(A + B)= #А + #B, причем сложение #A, #В выпол-я поразрядно без переносов в высшие разряды по правилу 0+0=0, 0+1=1+0=1, 1+1=1. 2) изображающее число конъюнкции двух элементов опред-я как произведение ич сомножителей: #(A•B)=( #А)•(#B ), причем перемножение #A, #В выпол-я поразрядно по правилу 0•0=0, 0•1=1•0=0, 1•1=1. 3) ич отрицанияА получается из ич А заменой в каждом разряде 0 на 1 и 1 на 0.

Пример логической задачи распознавания

Пусть объект характ-ся единственным бинарным признаком A1 (n=1).

m=2: w1, w2=> Ω 1, W2. Априорная информация (система (*)):

- классы не могут иметь место одновременно: Ω 1=не W2.

- значение признака однозначно определяет класс: A1= Ω 1. Пусть об объекте известно: A1=0 ó не А1=1(**), G≡ не А1. Тогда система (***) имеет вид:

(не не А1UF(Ω 1, W2))=1& Ω 1≡ не W2& А1= Ω 1. => F(Ω 1, W2)=не А1(из1),

F(Ω 1, W2)=не Ω 1 (из 3)=> F(Ω 1, W2)= W2.

Основы МГУА.

МГУА позволяет:

-не заботиться о выборе сложности полинома

-не предусматривает ограничений на размерность вектора x

-позволяет ограничить время определения коэффициентов разумными пределами

-может работать при обучающих выборках малого объема.

Рассмотрим общую схему МГУА.

Вся выборка делится на обучающую и проверочную: . Входной вектор имеет размерность N .

1-ый ряд - на основе обучающей последовательности строятся частные описания от всех попарных комбинаций исходных аргументов, приближающие по МНК выходную переменную:

Из этих моделей выбирается некоторое число лучших по критерию селекции (используя проверочную последовательность).

2-ой ряд - полученные переменные принимаются в качестве аргументов второго ряда, и снова строятся все частные описания от двух аргументов и т.д.

Под опорной функцией будем понимать вид полинома ч/з. кот. будут выражаться переменные k уровня ч/з переменные k-1 уровня.

Виды опорных функций:

А) .

В) .

С) .

D) .

Есть несколько способов отбора лучших кандидатов частичных описаний передаваемых на определенном слое. Рассмотрим критерий регулярности (точности)

Критерий остановки алгоритма МГУАопределяется для каждого уровня значение критерия для всего уровня: либо среднее значение, либо лучшее значение критерия. Пусть значение критерия 1-го уровня -E1 а 2-го –E2, Если E2 «лучше» в смысле заданного критерия (регулярности или несмещенности), то переходим к следующему уровню. Если же нет, то конец работы алгоритма.

Восстановление аппроксимирующей функции по результатам, полученным на пройденных этапах селекции. Двигаясь от конца к началу и делая последовательную замену переменных, вычисляются выражения для искомой модели в исходном пространстве описаний.