Імовірнісний підхід до класифікації образів icon

Імовірнісний підхід до класифікації образів




Скачати 387.75 Kb.
НазваІмовірнісний підхід до класифікації образів
Сторінка1/4
Дата14.09.2012
Розмір387.75 Kb.
ТипЗадача
  1   2   3   4
1. /LekIZSU/Lek3.doc
2. /LekIZSU/Lek4.doc
3. /LekIZSU/lek1.doc
4. /LekIZSU/lek2.doc
5. /LekIZSU/lek5.doc
6. /LekIZSU/lek6.doc
7. /LekIZSU/lek7.doc
Розділ 3 класифікація образів методи класифікації
Імовірнісний підхід до класифікації образів
Розділ 1 вступ
Інформація про зовнішній світ зберігається в згорнутому стані, що дає можливість збільшити її обсяг для запамятовування. Наприклад, одне І теж слово, вимовлене різними особами, має для людини один І той же зміст. Приклад 1
Розділ 6 алгоритми навчання класифікаторів
Розділ 7 вибір множини ознак в системах розпізнавання 1 Характеристика проблеми вибору множини ознак образів

РОЗДІЛ 4

ІМОВІРНІСНИЙ ПІДХІД ДО КЛАСИФІКАЦІЇ ОБРАЗІВ


4.1 Класифікація образів як задача теорії статистичних рішень


В тому випадку, коли між ознаками об’єктів і класами, до яких ці об’єкти можуть бути віднесені, існують імовірнісні зв’язки, побудова алгоритмів класифікації може грунтуватися на положеннях теорії статистичних рішень. Розглянемо коротко основні її ідеї.

Припустимо, що спостерігається деякий об’єкт, описаний вектором в просторі імовірнісних ознак. Цей об’єкт може належати, наприклад, тільки одному із двох образів (рис. 4.1).







Рисунок 4.1 – Функції щільності розподілу ймовірностей ознаки x

для образів 1 і 2

Теорія статистичних рішень дозволяє знайти метод, який після вивчення об’єкта дав би з мінімальною ймовірністю помилки відповідь на те, до якого з двох образів, - чи , - відноситься конкретне значення вектора (наприклад, на рис. 4.1).


В процесі прийняття рішення розрізняють помилки подвійного гатунку. Їх називають помилками першого роду і другого роду. Будемо вважати, що існує дві гіпотези: гіпотеза 1, що об’єкт належить першому образу 1, і гіпотеза 2, що цей об’єкт міститься в другому образі 2. Тоді вважається, що здійснюється помилка першого роду, коли відхиляється перша гіпотеза, в той час як вона дійсно має місце, і помилка другого роду, якщо приймається перша гіпотеза тоді, коли справедливою є друга.

Для прикладу рис. 4.1 помилка першого роду чисельно дорівнює

,

а другого роду

.

Часто помилку першого роду називають пропуском цілі, а помилку другого роду – хибною тривогою. З власного досвіду дуже легко впевнитися, що ці два види помилок часто не є рівноцінними для тих, хто приймає рішення. Наприклад, нехай образ 1 відповідає сигналам землетрусу, а образ 2 - сигналам важко навантаженого поїзда. Зрозуміло, що витрати від того, що сигнал землетрусу буде класифікований сейсмологами як гуркіт навантаженого поїзда (пропуск цілі), будуть набагато вищі, ніж при хибній тривозі.

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

З такої точки зору процес прийняття рішень на класифікацію зручно розглядати як гру статистичного характеру, яку класифікатор системи розпізнавання образів проводить з природою. Формально гра G задається набором з трьох елементів :


, (4.1)


де - множина стратегій природи, причому - зображення об’єкта в ознаковому просторі ; - множина стратегій класифікатора, де - клас, до якого класифікатор відносить подане природою зображення ; - платіжна матриця (або матриця втрат чи штрафів) гри, де - втрати класифікатора при віднесенні зображення до класу .

В такій постановці гра вважається грою з нульовою сумою, тобто втрати одного учасника точно дорівнюють виграшу іншого учасника. Також вважають додатні значення втрат істинними втратами, а нульові – виграшем. Нульові втрати відповідають правильній класифікації, тобто діагональним елементам платіжної матриці .

В іграх даного типу використовуються різні стратегії , зокрема байесівська стратегія, мінімаксна стратегія і стратегія Неймана-Пірсона. Задача класифікатора полягає в тому, щоб знайти таке оптимальне рішення, яке забезпечить мінімізацію середнього ризику чи вартості втрат.

Гра, що розглядається, називається статистичною, оскільки природа вибирає стратегії не усвідомлено, а грунтуючись на ймовірностях класів , і =1,2,…,К. Вона їх притримується, не дивлячись на їх можливу неоптимальність з точки зору максимізації виграшу. Наприклад, звуки мови, як і літери в тексті, зустрічаються з відомою ймовірністю.

Класифікатор має можливість отримати додаткову інформацію про противника у образі природи шляхом проведення експериментів по множині зображень. В результаті цього в більшості випадків йому відомо апріорна інформація про стратегію природи у вигляді ймовірностей появи образів і функцій правдоподібності образів . Цю інформацію класифікатор використовує для покращення своєї гри, тобто для підвищення точності розпізнавання.

Нехай при реалізації гри між природою і класифікатором природа обирає клас і відтворює зображення . Ймовірність належності до класу визначається як . Якщо класифікатор приймає рішення про те, що в тому випадку, коли в дійсності , то він має втрати . Оскільки образ може належати до будь-якого з класів, то математичне очікування втрат, пов’язане з даним рішенням, визначиться таким виразом :


=/ . (4.2)


В теорії статистичних рішень цю величину часто називають умовним середнім ризиком або умовними середніми втратами .


4. 2 Байесівська класифікація образів


В результаті розпізнавання кожного образу , що пред’являється природою, класифікатор може зарахувати його до одного із можливих класів. Оскільки для кожного зображення обчислюються значення умовних середніх втрат , , …, і класифікатор зараховує його до того класу, якому відповідають найменші умовні втрати, то і математичне очікування повних втрат на множині всіх рішень також буде мінімізоване. Класифікатор, що мінімізує математичне очікування загальних втрат, називається Байесівським класифікатором . Він з статистичної точки зору відповідає оптимальній якості класифікації.

Вираз (4.2) можна подати в іншому вигляді, скориставшись формулою Байеса

, (4.3)

для чого підставимо (4.3) в (4.2) замість :

, (4.5)

де - функція правдоподібності для класу . Оскільки вираз входить до всіх формул обчислення умовних середніх втрат , спільним множником, вираз (4.5) можна на нього скоротити. Одержимо наступну формулу втрат

(4.6)

Для випадку двох класів підрахуємо втрати і .

При виборі стратегії 1, тобто при внесенні до , середні втрати:

(4.7)

а при виборі стратегії 2 -

. (4.8)

Класифікатор Байеса зараховує до класу , якщо , тобто:

або , що одне і те ж ,

. (4.9)

Перепишемо (4.9) у вигляді

(4.10)

Ліву частину виразу (4.10) називають відношенням правдоподібності

, (4.11)

оскільки воно є відношенням двох функцій правдоподібності. Таким чином , для кількості класів =2 байесівське вирішувальне правило формулюється наступним чином :

є , якщо ,

є , якщо ,

рішення вибирається довільно, якщо .

Величина називається порогом і визначається виразом

. (4.12)


Приклад 4.1. Знайти оптимальне вирішувальне правило для класифікатора сигналів, представлених у вигляді одиниць і нулів на виході канала з шумом (рис.4.2).

В інформаційному каналі на вхідний сигнал накладається гаусовський шум з нульовим середнім значенням і дисперсією , в результаті на вхід класифікатора подається суміш сигнала з шумом . Потрібно найти оптимальне вирішувальне правило .





Рисунок 4.2 - Приклад простої задачі класифікації


Розв’язування: Нехай - гіпотеза , що передано символ “0”, а - символ “1”. На основі сприйнятого сигналу потрібно здійснити вибір між і . Інтуїтивно можна вважати , що при значенні вибирається символ “0”, при - символ “1”. Перевіримо зроблені припущення.

Нехай матриця втрат має вигляд

а1 а2

,


де а1 і а2 - рішення про те, що були передані символи 0 і 1 відповідно, - втрати при виборі рішення , коли істинний клас , - втрати при виборі рішення , коли істинний клас .

З платіжної матриці видно, що правильним рішенням відповідають нульові втрати. Нехай і - апріорні ймовірності того, що передані символи 0 і 1 відповідно. Тоді порогове значення дорівнює

.

Рішення, що передано 0, приймається в тому випадку, коли . Щоб знайти , знаходимо і :

.
Підставивши ці значення в (4.11), одержимо значення функції правдоподібності

.

Таким чином, якщо

або ,

то приймається рішення, що передано символ 0.

Цей результат збігається з інтуїтивними припущеннями в тому випадку, коли або . Останнє справедливо при рівних величинах платіжної матриці.

В загальному випадку розподілу на декілька класів зображення зараховується до класу , якщо для всіх ,

, . (4.13)


Cпіввідношення (4.13) можна використати для знаходження відношення правдоподібності (4.10) для загального випадку кількох класів, тобто Воно має вигляд:


, (4.14)

. (4.15)


Тоді правило класифікації вектора для випадку кількох класів має вигляд:

, якщо для всіх . (4.16)

Більш зручною для класифікації в випадку кількох класів є функція втрат спеціального вигляду, отримати яку можна, зробивши декілька припущень.

Припущення 1. В більшості задач розпізнавання образів втрати від правильної класифікації дорівнюють нулю :

Припущення 2. Втрати від неправильного рішення однакові: Будемо також вважати, що всі втрати пронормовано, тобто

При таких припущеннях елемент матриці втрат можна записати у вигляді:

,

де . (4.17)

Підстановка виразу (4.17) в (4.6) приводить до виразу :


. (4.18)

Оскільки класи , є незалежними подіями і утворюють повну групу подій, а - умовна густина ймовірності вектора ознак , то, відповідно з теорією ймовірності:


. (4.19)


Підставимо (4.19) в (4.18), одержимо:




Правило байесівської класифікації тепер можна записати наступним чином :





або

(4.20)


Якщо записати

(4.21)


то правило (4.20) байесівської класифікації еквівалентне вирішувальним функціям розділу 3, для яких , якщо для всіх .

Враховуючи те, що вираз (4.21) можна переписати у вигляді:


(4.22)

оскільки імовірність не залежить від і.

В випадку (4.21) для класифікації використовується функція правдоподібності , а у випадку (4.22) використовується ймовірність належності зображення до образа .

Одержані висновки дозволяють реалізувати схему розпізнавання на основі байесівського класифікатора таким чином, як це показано на рисунку 4.3.





  1   2   3   4

Схожі:

Імовірнісний підхід до класифікації образів iconВимір ризику (імовірнісний підхід)
Необхідно вибрати варіант з більшим очікуваним прибутком І визначити, який із варіантів є більш ризикованим. Якому з варіантів (А...
Імовірнісний підхід до класифікації образів iconСумський державний університет Бібліотека. Інформаційно-бібліографічний відділ
Беда, Ф. П. Науковий підхід до визначення суті, класифікації та відбору факторів виробництва / Ф. П. Беда, О. М. Майсюра //Інвестиції:...
Імовірнісний підхід до класифікації образів iconСумський державний університет Бібліотека. Інформаційно-бібліографічний відділ
Беда, Ф. П. Науковий підхід до визначення суті, класифікації та відбору факторів виробництва / Ф. П. Беда, О. М. Майсюра //Інвестиції:...
Імовірнісний підхід до класифікації образів iconСмкэс-2004 удк 681. 518: 004. 93 Вплив потужності алфавіту класів розпізнавання на достовірність класифікації козинець М. В, асп
Мфсв), який дозволяє здійснювати нормалізацію образів безпосередньо в процесі навчання системи шляхом цілеспрямованої ітераційної...
Імовірнісний підхід до класифікації образів iconЛ. Г. Дротянко, Київський національний університет ім. Тараса Шевченка
Класифікація наукового знання на фундаментальне та прикладне певним чином пояснює принципово новий підхід до принципів його функіонування...
Імовірнісний підхід до класифікації образів iconПроблеми слов’янознавства problemy slov´ianoznavstva 2007. Вип. 56. С. 103-111 2007. Vol. 56. Р. 103-111
З’ясовуються витоки пое­тики фантастичного, її трансформація та основні ознаки у романтичних баладах. Пропонується варіант класифікації...
Імовірнісний підхід до класифікації образів icon4. плани практичних занять тема Загальні положення господарського договірного права України
Класифікації договорів за універсальним критерієм поділу. Одноступенева та багатоступенева класифікації господарських договорів
Імовірнісний підхід до класифікації образів iconСумський державний університет Кафедра «Інформатики» Завдання для комплексної контрольної роботи з курсу «Теорія розпізнавання образів» Варіант №
Сформувати лінійне вирішальне правило для розпізнавання двох образів за допомогою одношарового персептрону. При оптимізації параметрів...
Імовірнісний підхід до класифікації образів iconСумський державний університет Кафедра «Інформатики» Завдання для комплексної контрольної роботи з курсу «Теорія розпізнавання образів» Варіант №
Сформувати лінійне вирішальне правило для розпізнавання двох образів за допомогою одношарового персептрону. При оптимізації параметрів...
Імовірнісний підхід до класифікації образів iconЕтнокультурний дискурс роману ю. Полякова “грибний цар”
Полякова “Грибний цар” визначаються особ­ливості етнокультурної самоідентифікації росіян у постперебудовний період та ху­дожнє сприйняття...
Імовірнісний підхід до класифікації образів iconАвторське коментування пейзажних образів (на матеріалі поетичного дискурсу корелюючих мов) Ірина Карпівна Кобякова, Владислава Куліш (м. Суми, Україна)
У статті йдеться про авторське коментування пейзажних образів у поетичному дискурсі (об'єкт дослідження), фокусується увага не у...
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи