Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра програмного забезпечення
Інформація про роботу
Рік:
2001
Тип роботи:
Методичні вказівки до лабораторної роботи
Предмет:
Інформаційні технології
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Факультет комп’ютерної техніки та
інформаційних технологій
Кафедра програмного забезпечення
доцент Заяць В.М.
Методичні вказівки до лабораторних робіт
з курсу “Методи розпізнавання образів”
для студентів спеціальності 7.08.04
“Програмне забезпечення автоматизованих систем”
Затверджено
на засіданні кафедри
програмного забезпечення
Протокол № 2 від 14.09. 2000р.
Львів 2001
Методичні вказівки до виконання лабораторних робіт з дисципліни “Методи розпізнавання образів для студентів спеціальності 7.08.04. “Програмне забезпечення автоматизованих систем” / Укл. В.М. Заяць. Львів: НУЛП.- 18с.
Укладач: В.М. Заяць, канд. техн. наук, доц.
Рецензенти: В.Ф. Ємець, докт.техн.наук, доц.
Є.Н.Федорчук, канд.техн.наук, доц.
Мета курсу “Методи розпізнавання образів” є освоєння та реалізація основних методів та підходів до побудови систем розпізнавання об’єктів та явищ різної природи.
Незважаючи на те, що методи та алгоритми розпізнавання стають невід’ємною частиною систем діагностики, метеорологічного проектування, геологічної розвідки, систем вводу текстової, графічної та мовної інформації, експертних та навчальних систем як у вітчихняній так і в зарубіжній літературі системний підхід до вирішення задач розпізнавання не став домінантним. Зусилля дослідників спрямовані на розв’язання хоча й важливих, але часткових задач. До них відносяться задачі розподілу ознак, на мові яких описані класи, на області, що відповідають кожному із класів. Тобто задача зводиться до встановлення найкращих границь між класами з метою достовірного розпізнавання об’єкту заданого класу. Ця задача може бути повністю визначена лише у випадку, коли дослідник володіє повною апріорною інформацією про ознаки, які описують всі можливі класи об’єктів. В реальних ситуаціях дослідник не володіє всією інформацією про систему дослідження та тими технічними засобами, які необхідні для отримання цієї інформації.
При розробці довільних систем розпізнавання необхідний системний підхід, коли поряд з системою розпізнавання будується система управління, яка дозволяє в умовах обмежень на роботу системи розпізнавання реалізувати потенційно досяжну ефективність.
Дане методичне видання стосується практичної реалізації основних методів та алгоритмів при побудові системи розпізнавння з забезпеченням її максимальної ефективності. В кожній із наведених лабораторних робіт дається методика побудови алгоритму при вирішенні задачі розпізнавання, опис його характерних рис та особливостей.
Дані методичні вказівки допоможуть студентам засвоїти різні підходи до проблеми розпізнавання на основі єдиного системного підходу та забезпечити їх програмну реалізацію.
Лабораторна робота N 1.
Тема роботи - побудова детермінованої системи розпізнавання образів.
Мета роботи -навчитися проектувати системи розпізнавання образів на прикладі системи розпізнавання літаків.
1. Теоретичні відомості.
Вважатимемо, що образи - це деякі об'єкти (тіла, модулі), які можна виділити в досліджуваному середовищі як його незалежно існуючі складові і які ми можемо охарактеризувати скінченим числом числових чи описових характеристик.
Клас подібних образів - це сукупність образів, що мало відрізняються по заданих чи усіх характеристиках у порівнянні з іншими образами.
Система розпізнавання образів - це система, що по певному алгоритму відносить досліджуваний образ до відомих їй (системі) класів подібних образів.
Побудувати систему розпізнавання образів означає:
1. Виділити у заданих системі об’єктів характеристики, що є. спільними для деякого набору об’єктів.
2. Розбити усю множину відомих образів по класах подібності, проаналізувавши їх за характеристиками подібності.
3. Побудувати алгоритм віднесення невідомого образу до одного із. класів подібності на основі характеристик подібності.
У нашій системі розпізнавання образів літаки - це образи, а система розпізнавання літаків - це система розпізнавання образів.
Спосіб побудови системи розпізнавання наступний:
Образи (літаки.) представляються у вигляді точок у N - мірному просторі, де N - кількість характеристик, що характеризують образ (отже, кожна характеристика представляється одним із напрямів простору). У літаків можна виділити слідуючі характеристики: вага, швидкість, площа відбиття, рівень шуму, ширина крил і т.п. Тепер, якщо, наприклад, вісь Х відповідає за вагу літака, вісь Y відповідає за швидкість літака, то точки, у яких координата X дорівнює 1000,а координата Y дорівнює 300 представляють літаки з вагою 1000 і швидкістю 300. Для характеристик, які виражаються у символьному виді, наприклад колір, потрібно вводити свою шкалу значень, де кожне значення шкали відповідає певному значенню характеристики.
Характеристика подібності між образами (D), що виділені у один клас, вираховується як середня квадратична відстань між образами. Для цього обчислюються відстані між усіма можливими парами образів із класу подібності і знаходиться їх середнє значення:
де F - клас подібності;
L - відстань між і-им та j-им образами F-класу;
М - кількість можливих пар.
Система може сама виділяти групи образів, які можна віднести до одного класу подібності. Для полегшення завдання будемо працювати із заданими класами подібних образів. На початку роботи системі задається список відомих нам літаків, з вказанням їх характеристик і класу подібності (бомбардувальник, штурмовик, винищувач). З цього списку система виділяє літаки, що належать одному класу і обчислює його характеристику подібності. Характеристика подібності кожного класу покаже нам рівень згрупування образів у кожному класі і дозволить класифікувати невідомий літак.
Нехай маємо невідомий об'єкт (у нашому випадку літак), описаний певними характеристиками. Визначаємо належність невідомого об'єкта до відомих нам класів. Характеристику належності до відомого класу (S) обчислюється як середнє значення відстані між невідомим об'єктом і всіма образами подібності.
де k – невідомий образ;
F - клас подібності;
і - і-тий образ F-класу;
L - відстань між невідомим та і-им образом F-класу;
N - кількість образів у F-класі.
На основі отриманих S-характеристик невідомого образу робимо висновок про клас невідомого об'єкта: він належить класу, до якого середня відстань найменша (S - найменша).
Ймовірність належності класу (Р) обчислюється як процентне співвідношення відстані до досліджуваного класу порівняно із відстанями до інших класів.
де k - невідомий образ;
F - досліджуваний клас подібності;
W - кількість класів подібності.
2. Хід роботи.
Побудувати систему розпізнавання образів.
1. Виділити серед відомих образів характеристики, що є спільними для всіх об'єктів.
2. Розбити усю множину відомих образів за класами подібності.
3. Проаналізувати класи характеристиками подібності.
4. Побудувати алгоритм віднесення невідомого образу до одного із класів подібності на основі характеристик подібності і обчислити ймовірності належності до класу подібності.
3. Контрольні запитання.
1. Що таке система розпізнавання?
2. Дати класифікацію ознак системи розпізнавання.
3. Які є критерії віднесення об'єкту до класу?
4. Як визначається величина ймовірності приналежності об'єкту до даного класу?
5. В чому суть системного підходу до побудови системи розпізнавання?
Лабораторна робота N 2.
Тема роботи - розпізнавання періодичних режимів по моментах пе реходу через нуль однієї із змінних досліджуваної системи.
Мета роботи - набути навиків розпізнавання періодичного процесу та визначення величини періоду.
1. Теоретичні відомості.
В процесі розпізнавання того чи іншого об'єкту, явища, про цесу необхідно створити модель досліджуваної системи. В загаль ному випадку ця модель задається диференціальним рівнянням, по рядок якого визначається кількістю змінних, зв'язки між якими враховуються при дослідженні системи.
При аналізі таких систем доцільно їх привести до системи диференціальних рівнянь першого порядку. Вибравши метод число вого диференціювання (явний чи неявний Ейлера, трапецій, Шічмена та інші) система приводиться до різницевих рівнянь, але вже алгебраїчних. Вибір методу числового інтегрування зв'язаний з точністю, яка вимагається при аналізі. Слід відзначити, що на величину похибки розрахунку такої системи впливає також і вели чина кроку, з яким проводиться дискретизація.
Для того, щоб розпізнавати чи в системі існуватиме періо дичний режим, необхідно зафіксувати момент переходу через нуль однієї із змінних системи і провести диференціювання системи до наступного переходу через нуль вибраної змінної. Якщо тепер ча совий інтервал між 0 і 1 переходом через нуль вибраної змінної системи несуттєво відрізнятиметься від часового інтервалу між 1 і 2 переходом через нуль, то це означатиме, що в системі існує періодичний режим. Для визначення величини періоду коливань не обхідно визначити часовий інтервал між сусідніми переходами че рез нуль вибраної змінної стану. Цей інтервал відповідатиме по ловині величини періоду коливань. В якості критерію існування періодичного режиму можна взяти умову, що величина часових ін тервалів між сусідніми переходами через нуль вибраної змінної стану відрізняються не більше ніж на 10%.
2. Хід роботи.
1. Для заданої моделі системи у випадку диференціального рівняння певного порядку отримати систему рівнянь першого порядку
2. Використовуючи метод трапецій, отримати різницеву алгеб раїчну систему рівнянь.
3. Записати алгоритм знаходження розв'язку системи вико ристовуючи метод Ньютона.
4. Сформувати алгоритм знаходження періоду коливань по мо ментах переходу через нуль однієї із змінних стану.
5. На основі даного алгоритму реалізувати програму розпіз навання періодичного режиму і протестувати її для конкретної системи.
6. Задавшись критерієм періодичності, переконатись в існу ванні чи відсутності періодичного режиму в даній системі.
3. Контрольні запитання.
1. Сформувати алгоритм визначення періоду коливань дослід жуваної системи.
2. Привести формулу трапецій для дискретизації системи.
3. В чому суть методу Ньютона ?
4. Які шляхи підвищення точності знаходжуваного розв'язку ?
5. Запропонуйте можливі критерії розпізнавання періодичнос ті досліджуваної системи.
Лабораторна робота N 3.
Тема роботи - розпізнавання встановлених процесів по моментах переходу через максимум однієї із змінних стану.
Мета роботи - набути навиків розпізнавання встановлених проце сів досліджуваної системи
1. Теоретичні відомості.
Під встановленим процесом будемо розуміти таркий процес, при якому змінні стану системи у відповідні проміжки часу приймають одне і те ж значення, Очевидно, що при аналізі періодичного ре жиму спочатку слід добитися встановленого процесу. В якості критерію встановленості режиму можна розглядати значення однієї і тієї ж змінної в моменти досягнення нею максимального значення. Якщо значення змінних між сусідніми максимумами відрізня ються несуттєво, то процес можна вважати встановленим. Після цього можна аналізувати процес на періодичність, використовуючи критерій періодичності з роботи N 2. Можна запропонувати визначати період коливань і по моментах переходу через максимум деякої із змінних стану. Величина часового інтервалу між сусідніми максимумами відповідатиме періоду коливань.
2. Хід роботи.
1. Для заданого варіанту моделі системи отримати систему диференціальних рівнянь першого порядку.
2. Використовуючи неявний метод Ейлера, отримати різницеву систему рівнянь.
3. Використовуючи ітераційну процедуру Ньютона, записати алгоритм знаходження розв'язку отриманої системи.
4. Описати алгоритм знаходження періоду коливань по момен тах переходу через максимум однієї із змінних стану.
5. Реалізувати програму розпізнавання періодичного режиму після того, як досягнуто встановленого режиму.
6. Переконатися в існуванні періодичного режиму для заданої системи та визначити величину періоду коливань.
3. Контрольні запитання.
1. Який режим називається встановленим ?
2. Привести формулу неявного методу Ейлера для дискретизації системи.
3. В чому переваги і недоліки критеріїв визначення періоду коливань по переходах через максимум та переходах через нуль?
4. Запропонуйте шляхи уточнення визначення моменту максимуму змінної стану системи.
Лабораторна робота N 4.
Тема роботи - розпізнавання встановлених періодичних режимів по моментах переходу через мінімум однієї із змін них стану.
Мета роботи - набути практичних навиків при розпізнаванні пері одичних встановлених режимів та шляхах його пок ращення .
1. Теоретичні відомості.
Необхідність використання різних критеріїв при розпізнаванні періодичних встановлених режимів зумовлена різною поведінкою досліджуваних систем. Так може існувати в системі режим, коли вибрана змінна стану не має переходів через нуль. В цьому випадку використання критерію періодичності з роботи N 2 не має змісту. При деяких значеннях параметрів системи може статися, що вибрана змінна досягає свого максимуму при великих значеннях, тобто існує стрибок в моменти максимуму змінної. Тоді використання критерію періодичності із роботи N 3 недоцільне, оскільки похибка визначення періоду буде суттєвою. Більше того, можна зробити неправильний висновок про відсутність періодичного режиму в такій системі. В цих випадках доцільно використовувати для визначення періоду коливань моменти часу, коли деяка змінна стану приймає мінімальне значення. Величина часового інтервалу між сусідніми мінімумами відповідатиме величина періоду коливань. При цьому в якості критерію встановленості процесу можна вважати те, що значення деякої змінної в сусідніх мінімумах відрізняються не більше ніж на 1%. З метою уточнення моменту мінімуму змінної можна проводити інтерполяцію по Лагранжу для трьох точок, які найближчі до мінімуму, або зменшувати крок дискредитації на останньому періоді після досягнення встановле ного режиму.
2. Хід роботи.
1. Привести досліджувану модель до системи диференціальних рівнянь першого порядку.
2. Використовуючи метод Ейлера, отримати систему різницевих рівнянь.
3. Сформувати алгоритм знаходження розв'язку системи на основі ітераційної процедури Ньютона.
4. Описати алгоритм знаходження періоду коливань на основі визначення мінімуму однієї із змінних стану.
5. Реалізувати програму розпізнавання періодичного режиму з автоматичним визначенням періоду коливань.
6. Провести дослідження заданої системи, використовуючи різні критерії періодичності.
3. Контрольні запитання.
1. Чим зумовлена необхідність існування різних критеріїв періодичності?
2. Привести формулу явного методу Ейлера для дискретизації системи.
3. В чому суть процедури інтерполяції по Лагранжу?
4. Які шляхи уточнення знаходження величини періоду коливань?
5. Сформулювати критерії періодичності досліджуаної системи.
Лабораторна робота N 5.
Тема роботи - побудова найпростішої системи розпізнаванн з навчанням.
Мета роботи - набути навиків побудови системи розпізнавання з навчанням.
1. Теоретичні відомості.
Методи навчання для побудови системи розпізнавання необхідні в тих випадках, коли відсутня повна апріорна інформація про досліджуваний об'єкт, її об'єм є достатній, щоб здійснити розбиття об’єктів на класи і визначити апріорний словник ознак. Але не достатній, щоб здійснити опис класів по масці апріорнрого слоника ознак, тобто визначити функції розділення об’єктів на класи, або апріорні ймовірності появи об’єктів різних класів та функції умовної густини розподілу.
В таких випадках для уточнення описів об’єктів по класах використовується апріорна інформація, яка утворюється в результаті функціонування попередньо сформованої системи розпізнавання невідомих об’єктів, що не відносяться до навчальної вибірки. Якщо навчальна вибірка містить об’єкти, які рівномірно розміщені розміщені в областях однакового простору, що відповідають класам, то така процедура забезпечує достатньо точний опис класів.
Більшість сучасних ефективних алгоритмів навчання грунтується на методі потенціальних функцій і можуть бути отримані шляхом використання методів стохастичної апроксимації.
Суть методу для сукупності об’єктів , якщо відомо, до якого класу кожен з них належить, зводиться до реалізації наступних двох етапів.
Етап 1. На основі апріорної інформації про приналежність об’єктів до заданого класу і заданому числі об’єктів можна в першому наближенні оцінити ймовірність появи об’єктів кожного класу .
Якщо оцінити в першому наближенні й функції умовної густини розподілу, то на цьому перший етап закінчується.
Етап 2. На цьому етапі проводиться уточнення ймовірностей появи об’єктів в класах шляхом використання апріорної інформації, яка міститься в результатах віднесення нових об’єктів до відповідних класів.
Нехай Si – кількість об’єктів класу, що є в навчальній вибірці, – кількість об’єктів, віднесена до класу в результаті розпізнавання n+1 об’єкту. Тоді оцінка апріорної ймовірності віднесення об’єкту до класу на n+1 кроці визначається, як
де – оцінка , отримана при розпізнаванні n об’єктів, .
На цьому завершується другий етап роботи системи з навчанням.
2. Хід роботи
1. Задатися трьома класами об'єктів, причому в першому класі 5 об'єктів, другому - 15, третьому - 40.
2. В нульовому наближенні оцінити ймовірність віднесення об'єктів до заданого класу.
3. Реалізувати алгоритм ітераційної оцінки ймовірності віднесення об'єктів до класів на основі методу стохастичної апроксимації.
4. Уточнити оцінки ймовірнісних характеристик на 1, 2, 3 кроках, вважаючи, що зберігається закон розподілу об'єктів по класах згідно пункту 1.
5. Провести такі оцінки на 3 кроках у випадку рівноймовірної появи об'єктів в класах.
3. Контрольні запитання
1. В яких ситуаціях використовуються алгоритми навчання при побудові систем розпізнавання?
2. Дати загальну постаноивку задачі розпізнавання з навчанням.
3. В чому суть методу стохастичної апроксимації?
4. Як здійснити оцінку ймовірності віднесення об'єкту даного класу в першому наближенні?
Лабораторна робота №6.
Тема роботи – реалізація елементів самонавчальної системи розпізнавання на основі використання міри подібності .
Мета роботи – набути навиків практичної реалізації систем розпізнавання з самонавчанням.
Теоретичні відомості.
На практиці часто мають місце випадки необхідності побудови систем розпізнавння в умовах, коли класифікацію об’єктів провести неможливо або ж недоцільно. В якості прикладу можна розглянути задачу, коли до одного класу необхідно віднести об’єкти, значення параметрів яких є в межах наперед заданого діапазону. В такій ситуації число класів наперед невідоме, а тому інформації про приналежність об’єкту до того чи іншого немає і єдиний спосіб формування системи розпізнавання – використання методів самонавчання, або, як їх ще називають, таксономії. До самонавчання також слід звертатися і в тих випадках, коли відомо число класів, але навчальна вибірка не задана. Відомі лише об’єкти, що розглядаються, та задані ознаки, якими характеризується кожен з об’єктів. При цьому не вказано, до яких класів відносяться ці об’єкти. Загальний підхід до розв’язання таких задач кластеризації грунтується на методі стохастичної апроксимації. Хоча й цей метод є доволі універсальним, його реалізація пов’язана з рядом труднощів математичного характеру. На практиці для розв’язання задач таксономії використовуються нескладні методи, які грунтуються на вимірюванні міри подібності, що задається віддаллю між парами об’єктів (k та (1 в ознаковому просторі X=(x1, . . .,xN).
Для визначення віддалі між об’єктами можна використати співвідношення:
,
де та – j-та ознака k-го і l –го об’єктів відповідно,
є – підмножина ознак, які використовуються для обчислення віддалі.
Далі, для виділення кластерів, необхідно задати пороги за кожною з ознак, що використовується для обчислення віддалі .Якщо
,
то об’єкти відносяться до одного класу.
Алгоритм розбиття вихідної множини об’єктів на кластери можна сформувати наступним чином:
Проводиться нумерація об’єктів в порядку зростання однієї з ознак, для прикладу x1.
Далі, з того, що відповідає об’єкту (1 проводяться лінії, паралельні осям ознакового простору і на них відкладаються значення порогів . З кінців відрізків проводяться лінії, паралельні осям. Так формується перший кластер – клас об’єктів.
Та ж послідовність операцій виконується по віношенню до точки , яка є найближчою до класу . При цьому буде сформовано клас і так далі, поки весь простір не буде розбито на класи. Така геометрична інтерпритація прцедури самонавчання дозволяє реалізувати програму для здійснення автоматичного розбиття об’єктів на класи.
Хід роботи.
Довільним чином задати 15 об’єктів в двовимірному ознаковому просторі (xi,x2), вважаючи, що значення ознаки не перевищує 10.
Вибравши величину порогів , реалізувати алгоритм розбиття об’єктів на кластери, використовуючи міру подібности.
При виявленні об’єктів, які не ввійшли до виділених класів, сформувати додаткові класи, кожен раз починаючи з об’єкта, який не ввійшов в жоден з класів.
В якості результату видати кількість класів з об’єктами, що входять до кожного з них.
Реалізувати процедуру розбиття трьохвимірного ознакового простору на класи при таких же вхідних даних, вибравши .
3. Контрольні запитання.
В яких випадках при побудові систем розпізнавання використовуються методи самонавчання?
В чому суть методу стохастичної апроксимації при розв’язанні задач кластеризації?
Сформувати алгоритм розбиття ознакового простору на класи з використанням міри подібности.
Чи може значення вибраних порогів перевищувати максимальне значення відповідних ознак?
Лабораторна робота N 7.
Тема роботи - реалізація процедури послідовних розв'язків при прийнятті рішення.
Мета роботи - освоїти метод послідовних розв'язків при відне сенні об'єкту до заданого класу.
1. Теоретичні відомості.
Загальноприйнятий підхід при віднесенні об'єкту до того чи іншого класу полягає в тому, що рішення приймається після того, як визначені всі ознаки даного об'єкту. Однак можливий і інший підхід до розв'язання цієї задачі: після визначення чергової ознаки: x1; х1, x2; x1, x2, xз і так далі включається алгоритм розпізнавання і розв'язується задача розпізнавання на основі даних про виміряні на біжучий момент часу ознаки даного об'єк-ту. Така процедура носить назву послідовної. Її доцільно приміняти в тих випадках, коли вимірювання ознак даного об'єкту вимагає значних затрат.
Для розгляду суті цієї процедури будемо вважати, що множина об'єктів може бути розбита на два класи W1 і W2, в робочому словнику ознак міститься N-ознак х1, x2 ..., хN і задані функ ції умовної густини fi(x1); fi(x1, х2); fi(x1, xn) для кожного із класів. Нехай проведена серія експериментів, в результаті чого визначені ознаки х1, х2 ..., хn, причому n < N. Співстави мо відношення n-мірних функцій умовної густини
ln = f1(X1, .... Хn) / f2(Х1, ..., Хn)
з величинами А і В, які носять назву відповідно верхнього та нижнього порогу. Для оцінки цих порогів використовуються спів відношення
А < ((1 - Q1) / Q2) та В > Q1 / (1 - Q2),
де Q1 і Q2 - похибки першого та другого роду. При цьому будемо вважати, що якщо ln > А, то об'єкт відноситься до класу W1; як що ln < В, то об'єкт відноситься до класу В; якщо В < ln < А, то приймається рішення про необхідність продовжувати визначати ознаки і визначається n + 1 ознака.
У випадку, коли границі двох класів описуються часовими функціями густини з математичним очікуванням m1 і m2 та диспер сією G2, то якщо значення першої виміряної ознаки
Х10 > G 2 /(m1-m2) log А + 0,5 (m1 +m2),
приймається рішення про віднесення об'єкту w до класу W1; якщо
Х01 < G 2 /(m1-m2)log В + 0,5 (m1 + m2),
приймається рішення про віднесення об'єкту w до класу W2; в противному випадку необхідно визначити другу ознаку Х20. В загальному випадку після вимірювання n ознак, маємо: якщо
< G 2 /(m1-m2) log A + 0,5n (m1 + m2), тоє w є W1;
> G 2 /(m1-m2) log В + 0,5n (m1 + m2), то w є W2;
в противному випадку необхідно визначити n + 1 ознаку і прийня ти рішення.
2. Хід роботи.
1. Вважаючи, що границі двох класів (m = 2) задовільняють нормальному закону розподілу, задатися величинами математичних сподівань m1=, m2=, та дисперсією G2=4, вектором виміряних оз нак х° = (1, 3, 5, 7, ..., 2n + 1) як набором непарних чисел та величинами похибок першого роду Q1 = 0,1 і другого роду 0,2-0,3.
2. Визначити величини верхнього та нижнього порогів відпо відно А та В.
3. Реалізувати алгоритм послідовних розв'язків для довіль ного числа експериментів n.
4. Прийняти рішення про віднесення об'єкту до класу W1 або W2, починаючи з використання лише одного значення ознаки, двох і так далі.
5. В якості результату видати рішення про віднесення об'єк ту до класу W1 чи W2 та кількості ознак, які при цьому викорис тані.
3. Контрольні запитання.
1. Суть процедури послідовних розв'язків при прийнятті рі шень.
2. Що таке коефіцієнт правдоподібності?
3. Дати означення похибок першого та другого роду.
4. Привести вираз для коефіцієнту правдоподібності у випад ку розподілу умовної функції густини по нормальному закону.
5. Сформулювати критерій прийняття рішення в методі послі довних розв'язків при використанні довільного числа ознак для двох класів, що описуються гаусівськими функціями густини роз поділу ймовірностей.
6. Описати процедуру послідовних розв'язків для довільного числа класів n.
7. Як визначаються пороги класів та коефіцієнти правдопо дібності при довільному числі класів?
8. Сформулювати критерій прийняття рішення при довільному числі класів в методі послідовних розв'язків.
Лабораторна робота N 8.
Тема роботи - побудова робочого словника детермінованих ознак при обмежених ресурсах.
Мета роботи - набути практичних навиків по створенню робочого словника ознак при мінімальних затратах.
1. Теоретичні відомості.
В теoрії розпізнавання побудова робочого словника самостійна і складна задача. При його створенні необхідно враховувати нас тупні обмеження:
1) в робочий словник включають лише ті ознаки, відносно яких може бути отримана апріорна інформація;
2) деякі із ознак недоцільно включати в словник, оскільки вони малоінформативні;
З) деякі із ознак не можуть бути включені в словник внас лідок відсутності відповідної вимірювальної апаратури або її дороговизни.
В цілому задача побудови робочого словника зводиться до то го, щоб в межах виділених асигнувань визначити перелік техніч них засобів, створення яких забезпечить вимірювання найбільш інформативних ознак апріорного словника, що дозволить реалізу вати максимально можливу ефективність системи розпізнавання.
Нехай в результаті класифікації вся множина об'єктів W= {w} розбита на підмножини W1, W2, .... Wn які не перетинаються. Позначимо об'єкти, що відносяться до кожного класу, наступним чином:
W1={w11, w12, w1k1}; W2 ={w21, w22, w2k2};
Wр={wp1, wp2, wpkp}; ... Wm={wml, wm2, wmkm}..
Якщо ознаки об'єктів позначити XJ, то в N - вимірному просторі ознак кожен об'єкт зобразиться вектором Х = (х1, х2, ..., хN).
Для визначення міри близькості чи подібності слід ввести поняття метрики. Будемо користуватися євклідовою метрикою
d2(wpk, wq1) = (Xpk - Xq1.)2
де p, q = 1, 2, . . . , m; k = 1, 2, . . . , kk; l = 1, 2, . . ., kl;
XJpk - значення j - тої ознаки к - того об'єкту р - того класу.
Надалі необхідно буде розглядати міру близькості -між всіма об'єктами даного класу і міру близькості між всіма об'єктами даної пари класів.
В якості міри близькості між всіма об'єктами даного класу розглядатимемо величину
,
яку назвемо середньоквадратичним розкидом класу.
В якості міри близькості між об’єктами даної пари класів Wp і Wq будемо використовувати величину
,
яка є середньоквадратичним розкидом об’єктів класів Wp і Wq .
Сукупність ознак об’єктів, що використовуються в робочому словнику опишемо N- вимірним вектором ( = ((1, (2 , ........., (n), компоненти якого приймають значення 0 або 1 в залежності від того , чи є можливість визначення даної ознаки. Тоді
Витрати на створення технічних засобів позначимо
,
де Сj – затрати на створення j-тої ознаки.
В якості критерію ефективності розглянемо функціонал
Величина L(w,{wy}) - міра близькості між досліджуваним об’єктом w і об’єктами даної пари класів:
Даний об’єкт w є Wy, якщо L(w, {wy}) = ext L(w,{wi}). Зменшення S(Wp) при одночасному збільшенні R(Wp,Wq) в кінцевому підсумку пріводіть до покращення ефективності системи.
Якщо на створення системи розпізнавання виділені ресурси С0, то задача зводиться до визначення (0, яке забезпечують
при
Якщо необхідна ефективність досягається шляхом рознесення
Об’єктів, що належать до різних класів при дотриманні деяких умов відносно об'єктів всередині класу, то розв'язок зводиться до знаходження
при і
Розглянемо метод розв'язання цієї задачі. Якщо перенумеру вати всі пари об'єктів із m класів, ввівши індекс
Г=1, 2, ... , n, де
то квадрат віддалі для n - ної пари
, Г=1, ... , n ,
де
де - інформативність j - тої ознаки для n - ної пари. Тепер задачу можна представити у вигляді
де
Отже, задача зводиться до знаходження максміну. Загально прийнятий підхід до її розв'язання - це використання методу штрафних функцій. В простих ситуаціях, які і розглядаються в даній роботі при невеликих значеннях N * n задача може бути розв'язана методом звичайного перебору.
2. Хід роботи.
1. Вибрати вектор ознак з чотирьох компонент для трьох кла сів довільним чином.
2. Вважати, що виділені асигнування на побудову системи є достатніми для визначення всіх ознак і в кожному класі є по три об'єкти.
3. Методом простого перебору реалізувати алгоритм пошуку максимуму величини R2Г.
4. Сформувати вектор L і видати значення середньоквадратичного розкиду об'єктів між класами.
5. Переконатися, що отриманий результат є оптимальним.
3. Контрольні запитання.
1. Що таке апріорний словник ознак?
2. Чим зумовлена необхідність створення робочого словника ознак?
3. Дати визначення міри близькості між об'єктами даного класу та об'єктами даної пари класів.
4. Сформулювати вирішальне правило при побудові робочого словника в загальному випадку.
5. Привести часткові випадки критерію ефективності при по будові робочого словника ознак.
6. В чому суть методу штрафних функцій?
7. Що таке умовний екстремум функції?
8. Дати визначення інформативності j - ної ознаки для Г - ї пари класів.
Література
Дуда Р., Харт П. Распознавание образов и анализ сцен. -М.: Мир, 1976.
Фукунага К. Введение в статистическую теорию распознавания. М.: Наука, 1979.
Ту Дж., Гонсалес Р. Принципы распознавания образов. М.:1978.
Себестиан Г.С. Процессы принятия решений при распознавании образов. - К.: Техника, 1965.
Горелик А.Л., Скрипкин В.А. Методы распознавания. - М.: Выс шая школа, 1989.
НАВЧАЛЬНЕ ВИДАННЯ
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторних робіт з курсу
“Методи розпізнавання образів”
для студентів факультету комп‘ютерної техніки та інформаційних технологій
стаціонарної форми навчання
Укладачі Заяць Василь Михайлович
Редактор
Комп‘ютерне складання
Підписано до друку
Формат 70 ( 100 1/16. Папір офсетний.
Друк на різографі. Умовн. друк. арк. ..... Обл.-вид.арк. .....
Наклд. ..... прим. Зам. .....
Поліграфічний центр
Видавництва Державного університету “Львівська політехніка”
вул. Ф. Колеси, 2, 79000, Львів
11.11.2013 00:11-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора