Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
ДОСЛІДЖЕННЯ АЛГОРИТМІВ РОЗПІЗНАВАННЯ ОБРАЗІВ. ЗАДАЧА ВИЗНАЧЕННЯ КОЕФІЦІЕНТІВ ЛРФ ДЛЯ ДВОХ МНОЖИН ОБРАЗІВ.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Методичні вказівки до лабораторної роботи
Предмет:
Основи проектування систем штучного інтелекту
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ УКРАЇНИ
Національний університет “Львівська політехніка”
ДОСЛІДЖЕННЯ АЛГОРИТМІВ РОЗПІЗНАВАННЯ ОБРАЗІВ. ЗАДАЧА ВИЗНАЧЕННЯ КОЕФІЦІЕНТІВ ЛРФ ДЛЯ ДВОХ МНОЖИН ОБРАЗІВ
Методичні вказівки
до лабораторної роботи №5
з курсу “Основи проектування систем штучного інтелекту”
1.Мета роботи
Вивчити принципи алгоритмів побудови лінійних рішаючих функцій для двох класів.
Написати програму реалізації алгоритму з графічним інтерфейсом користувача.
2. Короткі теоретичні відомості
2.1. Основні поняття теорії розпізнавання образів
Окремі предмети і явища оточуючого нас світу, котрі необхідно розпізнати, володіють спільними властивостями і мають деякі відмінні властивості. Стосовно властивостей, якими володіють предмети і явища вони поділяються на класи.
Класом або образом можна назвати множину предметів або об'єктів, які мають деякі спільні властивості. Як правило в предметній області існує деякий набір (алфавіт) класів, який позначається наступним чином:
, де - окремий клас, m - кількість класів
Якщо m=1, проблеми розпізнавання немає, оскільки існує один клас, до якого входять всі об'єкти.
При m=2 має місце дихотомічне розпізнавання образів.
При принципово розпізнати образ неможливо.
Кожен клас об'єктів може бути представлений деякою кількістю конкретних об'єктів або реалізацій. Сукупність різних реалізацій для всіх класів утворює множину можливих реалізацій.
В цю множину реалізацій ввійшли всі об'єкти, які належать до кожного класу . Звідси і виникла умова .
При введенні поняття "клас" ми сказали, що до класу відносяться об'єкти, які мають певні спільні властивості. Вони називаються ознакою класу.
Якщо вважати, що всі класи характеризуються однією і тією ж кількістю ознак , тоді сукупність ознак для заданого алфавіту класів можна записати наступний вектор ознак:
Практично числові значення ознак змінюються в деяких межах:
- будь-яка ознака може приймати властивий їй діапазон значень.
2.2. Основні задачі, які виникають при розробці системи розпізнавання образів
1. Перша задача пов'язана з представленням вхідних даних, котрі отримані як результати вимірювання для належного розпізнавання об'єкта.
Кожен з векторів ознак може бути представлений як точка в к-мірному просторі. Вектори образів містять всю інформацію про образи, яка піддається вимірюванню. При цьому процес вимірювання можна розглядати як процес побудування образу, а кожен образ - як точку в М-мірному просторі.
Рис 1. Графічне представлення образів
2. Виділення характерних ознак або властивостей із отриманих даних і зниження розмірності вектора образів.
Вектори, отримані на першому кроці будемо називати векторами образів.
Потрібно виділити характерні ознаки і властивості із отриманих даних. Ознаки можна класифікувати наступним чином:
1. Ознаки, які характеризують відмінності між окремими класами.
2. Ознаки, які є спільними для всіх класів.
Друга група ознак не є корисною для розпізнавання образів і тому у векторі ознак потрібно залишити лише першу групу ознак. Вибір ознак вважається однією із найбільш важливих задач для розпізнавання образів. Якщо результати вимірювання дозволяють отримати повний набір ознак із першої групи, тоді класифікація не викликає великих труднощів. Якщо ознаки вибрані із другої групи, то класифікація неможлива.
3. Задача полягає у відшуканні оптимальних рішаючих процедур, котрі необхідні при ідентифікації і класифікації образів:
а) Виділення класів.
б) Коли на розпізнавання поступає новий образ, його потрібно віднести до котрогось існуючого класу або утворити новий клас.
В подальшому для групування образів у класи ми будемо використовувати процедури кластеризації, які працюють по критерію відстані між точками. Будемо вважати, що образи оптимально згруповані в класи, якщо в межах класу відстань між образами є мінімальною, а між центрами ваг кластерів - максимальна.
Коли класи визначені, тоді на другому етапі переходять до побудови рішаючих функцій. Рішаючі функції - скалярні і однозначні функції від вектора ознак. У двовимірному випадку це прямі лінії, а в n-вимірному - площини, які ділять простір на декілька областей, кожна з яких відповідає певному класу. Дальше використовується сукупність правил порівняння значень рішаючих функцій для кожного нового вектора ознак. На основі цього порівняння роблять висновки про віднесення нового образу до одного з існуючих класів.
2.3. Поняття рішаючої функції та її застосування
Рис. 2. Графічне представлення рішаючої функції
Процедура віднесення будь-якого образу до певного класу полягає в обчисленні значення рішаючої функції від вектора ознак цього образу . Потрібно обчислити .Якщо тоді , якщо тоді , якщо ж , то ми попадаємо на границю між класами. Тоді потрібно:
а) самому віднести дану точку до якогось класу;
б) поміняти рівняння рішаючої функції;
Цей метод справедливий і при . Також його можна застосовувати і для випадку нелінійних рішаючих функцій.
Рівняння лінійної рішаючої функції для двохвимірного простору виглядає наступним чином:
, де - вагові коефіціенти
Успіх застосування схеми розпізнавання образів за допомогою рішаючих функцій залежить від двох факторів:
1. Вигляду рішаючої функції (лінійна чи нелінійна).
2. Практичної можливості визначення вагових коефіціентів.
Починається процедура вибору рішаючої функції з її лінійного вигляду. Лише коли алгоритм вибору рішаючої функції покаже, що класи лінійно нерозділимі, переходять до вибору нелінійної рішаючої функції.
Процедура визначення вагових коефіціентів ітеративна. Ітераційний процес починається з нульового наближення вектора вагових коефіціентів і за певну скінченну кількість кроків повинен дати кінцеві значення. Якщо процедура не збігається, коефіценти не будуть отримані або будуть отримані неправильні значення.
2.4. Лінійні рішаючі функції
Лінійна рішаюча функція в n-вимірному випадку виглядає наступним чином:
, де
,
Замість вектора вводять розширений вектор
- поповнений (розширений) вектор вагових коефіціентів
- поповнений (розширений) вектор ознак образів.
Тоді лінійна рішаюча функція виглядає наступним чином:
У випадку розділення на два класи лінійна рішаюча функція володіє наступною властивістю:
Якщо тоді , якщо тоді .
Нехай є m класів . Для цього випадку покажемо які є можливі застосування лінійних рішаючих функцій.
Кожен клас відділяється від решти класів однією розділяючою функцією. В такому випадку повинно існувати М рішаючих функцій, які володіють наступною властивістю:
Якщо тоді , якщо тоді
Якщо є М рішаючих функцій, то умова, що образ належить класу полягає в тому, що і-та лінійна рішаюча функція повинна бути додатньою, а значення всіх решта лінійних рішаючих функцій повинні бути від'ємними для даного вектора ознак.
Рис. 3. Перший спосіб застосування ЛРФ
ОНР - область невизначених рішень.
Умови належності образу до класу:
Як правило, в області не виконується умова належності вектора ознак образу до певного класу.
ОНР1:
ОНР2:
ОНР3:
ОНР4:
Кожен клас відділяється від будь-якого іншого взятого окремо класу індивідуально, або окремою розділяючою поверхнею, тобто класи попарно розділені. В такому випадку існує рішаючих функцій. При цьому лінійні рішаючі функції мають наступний вигляд:
- рішаюча функція, яка відділяє клас від класу .
Якщо тоді
У такому випадку має місце наступна властивість:
Рис.4. Другий спосіб застосування ЛРФ
Умови належності образу до класу:
Очевидно, що в порівнянні з першим випадком суттєво зменшилась область невизначених рішень.
Існує М рішаючих функцій наступного вигляду:
таких, що коли , тоді
Цей випадок включає в себе другий варіант. Перехід до другого варіанту відбувається наступним чином:
Тобто, якщо класи розділимі як у випадку 3, то вони автоматично розділимі як у випадку 2, але зворотнє твердження не завжди правильне.
Графічно краще зображати
Рис. 5. Третій спосіб застосування ЛРФ
Якщо лінійні рішаючі функції побудовані правильно, тоді їхні різниці повинні перетинатись в одній точці.
Умови належності образу до класу:
2.5. Процедури навчання класифікаторів образів
Рішаючі функції класифікаторів будуються по заданій вибірці образів за допомогою ітеративних алгоритмів навчання. Загальний вигляд рішаючої функції:
Задача полягає у визначенні вектора . Очевидно, що необхідною умовою однозначності визначення є лінійна розділимість класів.
2.6. Задача визначення коефіціентів ЛРФ для двох множин образів
Нехай ми маємо дві множини образів і , які є лінійно розділимими, причому таке, що коли тоді , якщо тоді .
В такому випадку
Рис. 6 ЛРФ у випадку двох класів
Для визначення вектора необхідно розв'язати наступну систему нерівностей:
Якщо ми поміняємо знаки координат вектора на протилежні тоді ми прийдемо до наступної системи нерівностей:
,
де матриця Тоді задача зводиться до розв'язку такої системи нерівностей якимось чисельним методом. Якщо існує такий вектор вагових коефіціентів , який задовільняє такій нерівності, тоді ця система нерівностей є сумісною, а наші класи - лінійно розділимі.
Специфікації
ЛРФ
лінйна рішаюча функція
А
Алфавіт класів
В
Множина реалізацій
вектор ознак
розширений вектор ознак
вектор вагових коефіціентів
розширений вектор вагових коефіціентів
рішаюча функція
коректуючий приріст
ОНР
область невизначених рішень
3. КОНТРОЛЬНІ ЗАПИТАННЯ
3.1. Основні поняття розпізнавання образів.
3.2. Представленням вхідних даних, котрі отримані як результати вимірювання для належного розпізнавання об'єкта.
3.3. Виділення характерних ознак або властивостей із отриманих даних і зниження розмірності вектора образів.
3.4. Відшукання оптимальних рішаючих процедур, котрі необхідні при ідентифікації і класифікації образів.
3.5. Поняття рішаючої функції та її застосування.
3.6. Лінійні рішаючі функції. Можливі застосування лінійних рішаючих функцій
3.7. Процедури навчання класифікаторів образів.
3.7. Задача визначення коефіціентів ЛРФ для двох множин образів.
4. ІНДИВІДУАЛЬНЕ ЗАВДАННЯ
Побудувати рішаючі футкції∙ із застосуванням алгоритму перцептрона для двох класів.
4.1. W1:{(1,8)}, W2:{(8,10)}.
4.2. W1:{(2,9)}, W2:{(15,8)}.
4.3. W1:{(6,2)}, W2:{(11,5)}.
4.4. W1:{(-2,1)}, W2:{(1,-3)}.
4.5. W1:{(1,8)}, W2:{(14,9)}.
4.6. W1:{(4,9)}, W2:{(8,10)}.
4.7. W1:{(6,2)}, W2:{(10,6)}.
4.8. W1:{(6,2)}, W2:{(8,-1)}.
4.9. W1:{(-4,1)}, W2:{(0,1)}.
4.10. W1:{(8,11)}, W2:{(13,8)}.
4.11. W1:{(10,6)}, W2:{(14,2)}.
4.12. W1:{(9,-1)}, W2:{(11,5)}.
4.13. W1:{(0,0)}, W2:{(1,-3)}.
4.14 W1:{(13,3)}, W2:{(14,8)}.
4.15 W1:{(12,3)}, W2:{(14,8)}.
4.16 W1:{(11,3)}, W2:{(14,8)}.
4.17. W1:{(10,3)}, W2:{(14,8)}.
4.18. W1:{(11,5)}, W2:{(13,2)}.
4.19. W1:{(0,-5)}, W2:{(3,2)}.
4.20. W1:{(1,8)}, W2:{(14,9)}.
4.21. W1:{(3,10)}, W2:{(9,12)}.
4.22. W1:{(6,0)}, W2:{(11,7)}.
4.23. W1:{(6,1)}, W2:{(10,-2)}.
4.24. W1:{(8,11)}, W2:{(14,8)}.
4.25. W1:{(4,9)}, W2:{(17,7)}.
4.26. W1:{(2,7)}, W2:{(16,9)}.
4.27. W1:{(4,2)}, W2:{(14,3)}.
5. ЗМІСТ ЗВІТУ
5.1. Мета роботи.
5.2. Блок схема алгоритму перцептрона для 2-х класів.
5.3. Лабораторне завдання.
5.4. Результати виконання індивідуального завдання.
5.5. Аналіз результатів та помилок, допущених при виконанні роботи.
5.6. Висновки.
6. Література
6.1. Ту Дж., Гонсалес Р. Принцыпы распознавания образов.М.,Мир,1978
6.2. Фор А. Восприятие и распознавание образов.М.,Машиностроение,1989
6.3. А.Л.Горелик, В.А.Скрипкин. Методы распознавания: Учеб. Пособие для вузов. 3-е изд., перераб. И доп.- М.: Высш.шк., 1989.-232 с.
6.4. А.Л.Горелик, В.А.Скрипкин. Некоторые вопросы построения систем распознавания. М., Сов. Радио, 1974, 224 с.
6.5. Нильсон Н. Искусственный интеллект. Методы поиска решений.М.,Мир, 1973.
6.6. Попов Э.В., Фридман Г.Р. Алгоритмические основы интеллектуальных роботов и искусственного интеллекта.М.,Наука,1976.
6.7. Слэйг Дж. Искусственный интеллект. Подход на основе эвристического програмирования.М.,Мир,1973.
6.8. Уинстон П. Искусственный интеллект.М.,Мир,1980.
6.9. Таунсенд К., Фохт Д. Проектирование и програмная реализация экспертных систем на персональных ЭВМ.М.,Мир,1990.
6.10. Нильсон Н. Принципы искусственного интеллекта.М.,Радио и связь,1985.
6.11. Левин Р., Дранг Д., Эделсон Б. Практическое введение в технологию искусственного интеллекта и экспертных систем с илюстрациями на Бейсике. М.,Финансы и статистика,1991.
6.12. Братко И. Програмирование на языке Пролог для искуственного интелекта: Пер. с англ. -М.: Мир, 1990.- 560 с., ил.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора