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

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

Изображение (описание) объекта – отображение объекта на воспринимающие органы (рецепторы) распознающей системы. Если воспринимающие органы фиксированы, то объект и его изображение отождествляются. Виды изображений : 1) объект в виде n-мерного вектора (вектор признаков) . Н-р, набор технич-х хар-к машины, м/б бинарным. 2) объект в виде лингвистической структуры. Н-р, текст на естественном языке.

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

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

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

Задача распознавания образов заключается в отнесении некоторого объекта из исходного множества к одному из m классов:

X (описание объекта)=> распознающая процедура => класс (образ).

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

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

Задача обучения распознаванию образов.

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

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

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

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

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

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

Пусть объект представлен вектором признаков X=(x₁, …, x_n) и имеется m образов w₁, …, w_m_.. Рассмотрим m(m-1) решающих функций d_ij(x), где i≠ j, i, j = 1…m, обладающих свойствами: 1) d_ij(x)> 0, " j≠ i, если xÎ w_i_. 2) антисимметричность: d_ij(x) =-d_ji (x). Если есть такой набор РФ, то работа распознающей процедуры сводится к проверке для данного объекта х условия (1) для всех i =1…m. В результате м/б, что: а) объект отнесён к классу i*. б) объект не отнесён ни к одному из m заданных классов. Множество объектов, не классифицируемых процедурой, составляет область неопределённости. в) по условию (2) невозможно отнесение процедурой объекта х более чем к одному классу: если при данном х усл (1) выполнено для нек-го i, то для всех j≠ i d_ij(x)< 0, т.е. объект не отнесён ни к какому из классов с номером j≠ i Частный случай: d_ij(x)= d°_i(x)-d°_j(x), i≠ j, где m функций d°i_{обладают свойством:}

₃₎d°_i(x)> d°_j(x) для " j≠ i, если xÎ w_i_, => усл (1, 2) выполняются автомат-и. В этом случае РП описывается так: х относится к классу w_i_{, где}_i₌_argmax_поj d°_j(x) (знач-е арг-ента j, при кот-м достигается мах функции при фиксир-м х).

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

1.Тестированиее комбинационных схем (КС-схема, состоящая из элементов, реализующих основные логические функции).

…….

Её работу можно описать так: ….

Пусть в схеме есть дефект (элемент х не работает). Тогда опишем её набором:

Задача диагностики КС заключается в том, чтобы фиксируя сигналы на входе и выходе схемы, определить, является ли схема исправной, или она имеет данный дефект. Вектор x=(x1, x2, x3, x4, y) размерности n=5, кол-во классов m=2.

2. Контроль состояния ядерного реактора.

……..

Изображение: X=x01, …, x31 – вектор в евклидовом пространстве. Имеются два класса: w1-множество значений вектора Х, соответств-х нормальному состоянию реактора, w2- -//- аномальному состоянию. Задача состоит в определении к какому классу относится объект X.

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

4. Выбор адекватного алгоритма для решения задачи. Имеется некоторое множество задач определенного типа. Предложено m различных эвристических алгоритмов для их решения. Множество задач можно разбить на m классов . Класс - подмножество задач, которое решается алгоритмом наилучшим в некотором смысле образом. Изображение- описание конкретной задачи. ЗР- дана конкретная задача, распознающая процедура должна решить какой алгоритм будет решать ее наилучшим образом.

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

Метод зондов.

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

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

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

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

Пусть есть ОП Z1, …, ZN, причём для каждого вектора Zj известна его принадлежность к одному из классов W1, …, Wm. Пусть D(Zj, x) – нек-я мера близости векторов Zj и x

q-БС-правило (q≥ 1-фиксированное целое число): вычисляется q ближайших соседей х и х относится к тому классу wi, к которому относится большинство из q ближайших соседей.

Алгоритм ISODATA.

{x₁, x₂, ..., x_N} – исходный набор образов. Ш1: Задаются параметры, определяющие процесс кластеризации:

К—необходимое число кластеров; Q_N —параметр, с которым сравнивается количество выборочных образов, вошедших в кластер; Q_s— параметр, характеризующий среднеквадратичное отклонение; Q_c—параметр, характеризующий компактность; L— максимальное количество пар центров кластеров, которые можно объединить; J — допустимое число циклов итерации. Ш2: заданные N образов распределяются по кластерам, соответствующим выбранным исходным центрам, по правилу

xÎ Sj, если ||х – zj|| < ||х – zi||, i=1, 2, ..., N_c; i¹ j, где

Sj-подмножество образов выборки, включённых в кластер с центром Zj. Ш3: ликвидируются подмножества образов, в состав которых входит менее Q_N элементов, т. е. если для некоторого j выполняется условие N_j < Q_N, то подмножество S_j исключается из рассмотрения и значение N_c уменьшается на 1. Ш4: каждый центр кластера z_j, j=1, 2, ..., N_c, локализуется и корректируется посредством приравнивания его выборочному среднему, найденному по соответствующему подмножеству S_j, т. е.

j=1..Nc, где N_j —число объектов, вошедших в подмножество Sj. Ш5: вычисляется среднее расстояние D_j между объектами, входящими в подмножество S_j, и соответствующим центром кластера по формуле Ш6: вычисляется обобщённое среднее расстояние между объектами, находящимися в отдельных кластерах, и соответствующими центрами кластеров по ф-ле Ш7: а) если текущий цикл итерации – последний, то задается Q_c=0, переход к шагу 11. б) Если условие N_c< =К/2 выполняется, то переход к шагу 8. в) Если текущий цикл итерации имеет четный порядковый номер или выполняется условие N_c> =K/2, то переход к шагу 11; в противном случае процесс итерации продолжается. Ш8: для каждого подмножества выборочных образов с помощью соотношения , i=1..n, j=1..Nc вычисляется вектор среднеквадратичного отклонения σ _j = (σ _1j, σ _2j, ..., σ _nj)', где п есть размерность образа, x_ik, есть i-я компонента k-ro объекта в подмножестве S_j, z_ij есть i-я компонента вектора, представляющего центр кластера z_j, и N_j —количество выборочных образов, включенных в подмножество S_c. Каждая компонента вектора среднеквадратичного отклонения σ _j характеризует среднеквадратичное отклонение образа, входящего в подмножество S_j, по одной из главных осей координат.

Ш9: в каждом векторе среднеквадратичного отклонения s_j, j=1, 2, ..., N_c, отыскивается максимальная компонента s_j_max. Ш10: Если для любого s _j_max, j=1, 2, ..., N_c, выполняются условия s _j_max> Q_s, и а) и

Nj> 2(QN+1), или б) N_j < К/2, то кластер с центром z_j расщепляется на два новых кластера с центрами z_j⁺ и z_j^- соответственно, кластер с центром z_j ликвидируется, а значение N_c увеличивается на 1. Для определения центра кластера z_j+ к компоненте вектора z_j, соот-й макс-й компоненте вектора s _j, прибавляется заданная величина g_j; центр кластера z_j^- опред-я вычитанием этой же величины g_j из той же самой компоненты вектора z_j. В качестве величины g_j можно выбрать некоторую долю значения макс-й среднеквадратичной компоненты s_j_max, т. е. положить g_j = ks _j_max, где 0 < k ≤ 1. При выборе g_j следуег руковод-я в основном тем, чтобы ее величина была достаточно большой для различения разницы в расстояниях от произвольного образа до новых двух центров кластеров, но достаточно малой, чтобы общая структура кластеризации существенно не изменилась. Если расщепление происходит на этом шаге, надо перейти к шагу 2, в противном случае продолжать выполнение алгоритма. Ш11: вычисляются расстояния D_ij между всеми парами центров кластеров:

D_ij =l| z_i - z_j ||, i=1, 2, ..., N_c-1; j=i+1, 2, ..., N_c. Ш12: Расстояния D_ij сравниваются с параметром Q_c. Те L расстояний, которые оказались меньше Q_c, ранжируются в порядке возрастания:

[D_i1j1, D_i2j2,..., D_iLjL,] причем D_i1j1< D_i2j2< ... < D_iLjL,. a L—максимальное число пар центров кластеров, которые можно объединить. Следующий шаг осуществляет процесс слияния кластеров. Ш13: кластеры с центрами z_il и z_jl, i=1, 2, ..., L, объединяются (при усл, что в текущем цикле итерации процедура слияния не прим-ь ни к тому, ни к др-у кластеру), причем новый центр кластера опр-я по формуле

Центры кластеров z_il и z_jl ликвидируются и значение N_c уменьшается на 1.

Ш14: если текущий цикл итерации—послед-й, то выполнение алг-ма прекращ-ся. В противном случае следует возврат-я либо к ш1, если по предписанию польз-ля меняется к-л из параметров, определяющих процесс кластеризации, либо к ш2, если в очередном цикле итерации параметры процесса должны остаться неизменными. Завершением цикла итерации считается каждый переход к ш1 или 2.

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

Базис - таблица, которая представляет все возможные комбинации значений истинности некоторого набора элементов А, В, С, .... Для п элементов А₁, ..., А_п базис содержит п строк и 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.

Элементы задачи решения.

Введем в рассм-е след. Элементы задачи принятия решения:

W={w1, …, wm}-конечное множество m состояний природы(ситуаций)

D={d1, …, dp} – конечное множество p возможных решений (действий)

L(di, wj) – ф-я потерь, кот. интерпретируется след. обр.: потери от принятия решения di, когда реализуется состояние wj.

X=(x1, …, xn) – в-р признаков. Б. Считать что он явл. реализ-ей сист. СВ X=(X1, …, Xn), которая для состояния природы wj характеризуется:

- Плотностью вероятности p(x/wj), если X – сист. абс. непр. СВ

- Законом распределения (набором вероятностей) P(x/wj)=P(X=x/wj), если X – сист дискретных СВ.

Пусть P(wj) вероятность появления состояния природы wj и пусть P(wj/x) – условная вероятность появления состояния природы wj при условии, что будет наблюдаться значение случ вектора X=x.

48. Условный риск. Общий риск.

Введем вел-ну

- усл-е мат. ожидание потерь от принятия реш-я di при усл-и, что X=x.

-усл. риск

Введем в рассм-е функцию d(x) – каждому в-ру x ставит в соотв-е некот реш-е из мн-ва реш-й D.

-усл. мат. ожид-е потерь при усл-и, что исп. реш. ф-я d(x)

Безусловное мат ожид-е потерь при использовании решающего правила d(x) есть

R(d) назыв. общим риском.

49. Постановка байесовской задачи решения. Оптимальное решающее правило. Связь с задачей распознавания.

Поставим следующую задачу: найти решающее правило d(x) такое, которое доставляет минимум R(d). Эта задача решается очень просто. Т.к. R(d) будет минимально, если d(x) выбрано так, что R(d(x)/x) имеет минимальное значение для каждого возможного x, то оптимальное решающее правило можно описать следующим образом: для данного x вычислить R(di/x) для i=1, …, p и выбрать то di, при котором R(di/x) минимально, т.е.

Такое решающее правило называется байесовским решающим правилом, а соответствующее минимальное значение общего риска R(dopt) – байесовским риском.

Задача распознавания образов получается, если между элементами множества W и D установим взаимооднозначное соответствие

Решение di заключается в отнесении объекта, имеющего изображение х к одному из классов w₁, w₂,..., w_m. ( в этом случае p=m)

50. Классификация с минимальной вероятностью ошибки.

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

Для заданной L байесовское решающее правило будет обеспечивать минимальную вероятность ошибки классификации.

51. Минимаксное решающее правило.

52. Процедура Неймана-Пирсона.

f(x) – ЗР, H₀: xÎ w₁или f(x). g(x) – ЗР, H_1: xÎ w₂или g(x). Если в результате проведения наблюдения , то Н₀ отвергаем, т.е. xà w₂ (в случае Х-С ДСВ); Если , то гипотезу Н₀ отвергаем, т.е. xà w₂ (в случае Х-С НСВ).

54. Обучение байесовской процедуры распознавания: оценка неизвестных параметров.

1) вид любого УЗР известен, но ЗР содержат неизвестные параметры. Тогда это параметр-я задача обучения, решение кот-й сводится к оценке неизвестных параметров с помощью статист-х методов (максимального правдоподобия, метод моментов). 2) вид УЗР неизвестен. Обучение: а) представление неизвестного ЗР в виде ряда разложения по системе определённых функций с последующим определением по данным наблюдения оценок коэф-в ряда, отбрасывания ряда. б) минимизация общего риска: R(d)à решается заданием à min

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

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

12 3 4 5 Следующая ⇒